Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima Lachlan Ewen MacDonald René Vidal Innovation in Data Engineering and Science (IDEAS) University of Pennsylvania Pennsylvania, PA 19104 [email protected]
arXiv:2607.08380v1 [cs.LG] 9 Jul 2026
Abstract An important quantity in the theory of gradient descent (GD) is the sharpness, defined as the largest eigenvalue of the objective Hessian. Classical analyses typically require the step size to be uniformly smaller than twice the reciprocal of the sharpness, but this condition is frequently violated in the training of deep neural networks. Recent work [39] bridges this gap in the setting of overparametrised leastsquares with a single scalar output, providing a normal form for large-step GD in a neighbourhood of an isolated flat minimum and establishing three corresponding convergence results. In this paper, we extend this theory in two directions: (1) to overparametrised least-squares with vector-valued outputs (including regression with arbitrarily many observations), and (2) to a neighbourhood of a manifold of flat minima (which we show is essential for applications such as matrix factorisation). We generalise both the normal form and all three convergence theorems of [39] to this broader setting, overcoming several technical challenges, including the solution of a singular partial differential equation via a novel method that may be of independent interest. We further show that our framework applies to deep matrix factorisation under mild assumptions, yielding several new structural results. In particular, we prove that the set of flat minima forms a fibre bundle over a product of spheres, and that the sharpness is Morse-Bott along this manifold.
1
Introduction
A natural way of finding a minimum of a smooth function ℓ : Rp → R is by iterating the gradient descent (GD) map x 7→ x − η∇ℓ(x)
(1)
for some choice of step size η > 0. Originally introduced by Cauchy almost two centuries ago [10], the method has more recently found success as the quintessential technique for training deep neural networks (DNNs). Unfortunately, despite its age, fame and simplicity, GD remains poorly understood in its application to deep learning (DL). A critical quantity in the theory of GD is the sharpness, i.e. the largest eigenvalue λ1 of the Hessian of ℓ. Classical theories of the convergence of GD typically assume both convexity of the objective ℓ and the pointwise stability condition η < 2/λ1 (x),
(2)
without which GD diverges in the case of quadratic objectives. Both of these conditions are typically violated in the training of DNNs in practice, but convergence to a global minimiser is frequently observed nonetheless. The use of large step size in particular is often observed to accelerate convergence [13] and results in an implicit bias toward “flat minima” (i.e. minima with small sharpness Preprint.
λ1 ), which have been associated with better statistical performance [31]. Although tools from optimisation theory have shown some success in removing the stability condition (2) in convex settings [23, 24, 25, 4, 5, 52, 51, 53], convergence proofs with large step size in the non-convex settings of DL have stubbornly resisted analysis by these means. It is gradually becoming clear that analysis of GD in the regimes appropriate to DL instead require the tools of dynamical systems theory [35, 15, 39]. Of special significance for the present work is [39], which vindicates the dynamical systems approach in giving quantitative convergence theorems for gradient descent with large step size in “codimension 1” least squares problems, corresponding to a single scalar output and (p − 1)-dimensional manifold M ⊂ Rp of minimisers. Since extension of the results of [39] is the central concern of the present paper, we briefly recall them here. The contributions of [39]: A normal form is a change of coordinates in which the equations defining a dynamical system become easier to analyse. For codimension 1 least squares problems, [39] provides conditions for such a normal form for GD with large step size in a neighbourhood of an isolated flat minimum x∗ ∈ M . This normal form makes apparent that GD implicitly performs Riemannian gradient descent on the sharpness λ1 along the minima manifold M (systematising insights of [6, 15]) with step size controlled by the square distance of the iterates from M ; these distances meanwhile evolve as a bifurcating dynamical system in the direction orthogonal to M . Armed with this normal form, [39] proves that the dynamics of GD bifurcate into three regimes in terms of the sharpness value λ∗ := λ1 (x∗ ) at the flat minimum. In the subcritical regime, when η < 2/λ∗ , exponential convergence to a suboptimally flat minimum is guaranteed following an initial period of non-monotonic iterate behaviour; in the critical regime, when η = 2/λ∗ , the iterates converge non-monotonically with a polynomial rate to the flat minimum; and in the supercritical regime, when η > 2/λ∗ is sufficiently small, the iterates converge exponentially to a stable period-2 orbit along the span of the normal vector through the flat minimum. These theorems rigorously make sense of a number of empirical observations made in prior work [11, 16], but their codimension 1 hypothesis is impractically restrictive, applying to regression of only a single datum. Technical challenges of analysis: Although of limited practical interest, the codimension 1 setting considered in [39] is theoretically far from trivial. The normal form in [39] arises from the composite of several non-trivial coordinate transformations, one of which has a flawed proof in [39] whose highly non-trivial rectification we perform in this paper. The convergence theorems that follow are also highly non-trivial, requiring the application of deep invariant manifold theorems. Extending these results to higher codimension problems and thus obtaining theory of more practical relevance makes the technical challenges faced in [39] vastly more difficult. 1. Increasing the codimension of the problem increases the dimension of the bifurcating component of the system, thus necessitating the introduction of a dimension-reduction technique for analysis. 2. Natural examples of higher codimension problems do not admit isolated flat minima but instead admit manifolds of flat minima (see Subsection 3.3), further increasing the degrees of freedom that must be dealt with by any theoretical analysis. 3. Correct proof of the normal form presented in [39] requires the solution of a partial differential equation (PDE) which is singular at flat minima. In the isolated flat minimum case considered in [39], existing literature can be used to solve this problem [56]; however, when the PDE is singular along a manifold of flat minima, new techniques are required. Paper contributions: In this paper, we overcome all of these technical challenges and prove a vast generalisation of the theory of [39] beyond the codimension 1 setting, encompassing underdetermined least squares problems of arbitrary codimension corresponding to overparametrised regression of arbitrarily many data. The high-level takeaway is a generalisation of that of [39]: For least squares problems of arbitrary codimension, in a neighbourhood of a manifold of flat minima, GD with a large step size implicitly performs Riemannian GD on the sharpness along the solution manifold, and oscillates as a bifurcating dynamical system in the directions orthogonal to the solution manifold. Specifically, we establish the following results for least squares problems of arbitrary codimension: 2
1. We provide a set of geometric hypotheses (see Subsection 3.2) sufficient to prove a normal form for gradient descent with large step size in a neighbourhood of a manifold of flat minima (see Section 4), vastly generalising the normal form of [39] which considers only codimension 1 problems with isolated flat minima . Our normal form reveals that GD acts as Riemannian GD on the sharpness along the solution manifold, oscillates as a bifurcating dynamical system along the top eigendirection of the Hessian orthogonal to the solution manifold, and contracts exponentially to zero along the other eigendirections of the Hessian. 2. We prove generalisations of the subcritical, critical and supercritical convergence theorems derived in [39] to this more general setting (see Section 5). While our critical convergence theorem is an honest generalisation of that of [39] when the Hessian of λ1 is a scalar multiple of the identity along the flat minima manifold, in examples such as matrix factorisation this hypothesis does not hold; for such cases we reduce the result to a conjecture which may be of independent interest. 3. We prove that deep matrix factorisation problems fit into our framework (see Subsection 3.3). In particular, we prove a number of novel results about the loss landscapes of matrix factorisation problems, including that the flat minima of such problems are a smooth fibre bundle over a product of spheres, and that the sharpness λ1 is Morse-Bott (i.e., “normally strongly convex") along this manifold. 4. We verify our theory with numerical experiments for matrix factorisation problems (see Section 5).
2
Related work
Gradient descent in DL with small step size: A large body of work has analysed gradient descent (GD) for training deep neural networks under small step sizes by invoking the Polyak–Łojasiewicz (PL) inequality [30]. In overparametrised settings, this inequality can be deduced from the full-rank condition of the neural tangent kernel (NTK), i.e. the Gram matrix of parameter derivatives of the model [29], leading to numerous convergence guarantees for GD with step size satisfying the classical stability condition (2); see, e.g., [3, 18, 17, 34, 44, 43, 45, 8]. In this context, overparametrisation has a precise technical meaning: that the NTK is full-rank. In our setting, this corresponds to Assumption 3.1, which ensures a smooth manifold structure for the solution set of least-squares problems and is equivalent to the NTK being full-rank along this set. While these approaches yield strong convergence guarantees, the small step size and initialisation regimes they require are known to limit feature learning [12]. Moreover, by relying on a PL inequality, they do not naturally capture implicit bias phenomena, which are central to understanding deep learning. In contrast, the present work focuses explicitly on the dynamics of GD iterates. Gradient descent in DL with large step size: Classical stability analysis shows that (2) is necessary for convergence to a minimum of a given sharpness even in simple settings [54]. However, empirical studies beginning with [13] demonstrated that, in deep learning, GD with large step sizes often does not diverge; instead, it can converge at an accelerated rate. This behaviour is typically characterised by an initial progressive sharpening phase, in which the sharpness increases along the iterates, followed by an edge of stability regime in which the sharpness stabilises around 2/η and the loss decreases in a non-monotonic fashion. A substantial body of work has since sought to explain these phenomena [2, 6, 49, 47, 48, 15, 36, 57, 1, 11, 32, 52, 51, 9, 16, 37, 21, 55, 53]. Broadly speaking, these works either aim to identify general mechanisms underlying edge-of-stability dynamics [6, 15, 14], or to obtain detailed analyses for specific model classes [47, 48, 57, 1, 11, 32, 52, 51, 9, 16, 37, 55, 21, 53]. While the former provide conceptual explanations, the latter often yield stronger guarantees, including convergence theorems in certain settings [52, 51, 53, 37]. The work of [39] bridges these perspectives by introducing geometric hypotheses that abstract from problem-specific details while remaining verifiable in concrete settings, and which are sufficiently strong to establish convergence results. The present paper continues this program by substantially extending these geometric hypotheses and their associated guarantees.
3
Theoretical setting
3.1
Notation
The Euclidean norm on Euclidean space will be denoted ∥ · ∥, and I will denote the identity operator. Given a C k function f : Rm → Rn , Dk f will denote its k th order derivative. Beyond this, our 3
geometric setting must be expressed in the language of differential geometry; the following notation will be used throughout. The tangent bundle of a manifold M is denoted T M , with tangent space fibres Tx M for x ∈ M . If M is Riemannian, dM (x, y) will denote the geodesic distance (the length of the shortest curve) between x, y ∈ M . If S ⊂ M is a submanifold, then we denote dM (x, S) := inf y∈S dM (x, y), and denote by ν M S the normal bundle of S in M , whose fibre over x ∈ S is the orthogonal complement of Tx S ⊂ Tx M ; if M is clear from context we will use νS in place of ν M S. If f : M → N is a map of manifolds and S ⊂ M , then f |S : S → N will denote restriction. If N = R and f is C 2 , then ∇M f and ∇2M f will denote its Riemannian gradient and Riemannian Hessian respectively; when M is Euclidean, these are the ordinary gradient ∇f and Hessian ∇2 f . Given a fibre bundle B → M and a subset S ⊂ M , B|S → S will denote the restriction of B to S. 3.2
Problem setting
In this subsection, we describe the geometric setting for our results, which generalises that of [39]. We consider a C ∞ model f : Rp → Rq , where p > q ≥ 1. Given τ ∈ Rq , we consider the least squares objective ℓ : Rp → [0, ∞) given by ℓ(w) :=
1 ∥τ − f (w)∥2 , 2
w ∈ Rp .
(3)
With ℓ assumed, the notation GD : R × Rp → R × Rp will denote gradient descent, with step size η > 0 included as the first parameter: GD(η, w) := η, w − η∇ℓ(w) , w ∈ Rp . (4) This augmentation is necessary for the η-dependent normal form we provide in Theorem 4.1. Our first assumption gives a manifold structure to the minimisers of (3). Assumption 3.1. The target vector τ ∈ Rq is contained in the range of f and is a regular value of f .1 By the regular value theorem [26, Chapter 1, Theorem 3.2], Assumption 3.1 implies that the minimisers M := f −1 {τ } of ℓ form a nonempty C ∞ submanifold of Rp ; M inherits from this embedding a Riemannian metric with which we assume it to be equipped in what follows. From here on, we will denote points in M by x to distinguish them from arbitrary points w of Rp . Observe that at any point x ∈ M , since f (x) = τ one has ∇2 ℓ(x) = Df (x)T Df (x) + (f (x) − τ )T D2 f (x) = Df (x)T Df (x),
(5)
from which the following result is immediate. Proposition 3.2. At any x ∈ M : 1. The kernels of ∇2 ℓ(x) and Df (x) coincide and are equal to Tx M . 2. The eigenvectors (respectively, left-singular vectors) of ∇2 ℓ(x) (resp. Df (x)) with nontrivial eigenvalue (resp. singular value) span the normal space νx M . Proposition 3.2 plays a key conceptual role: it gives a correspondence between the linear geometry of ∇2 ℓ (via its kernel and cokernel) and the differential geometry of M (via its tangent and normal directions). It is ultimately these directions which appear (at least to first order) as the coordinates x and y respectively in our normal form (Theorem 4.1). We will denote by λ1 ≥ · · · ≥ λq : M → (0, ∞) the nonzero eigenvalue fields of ∇2 ℓ along M . Our normal form requires λ1 to be differentiable, however in general this only holds where λ1 ̸= λ2 . Our next assumption says that this set is non-empty. Assumption 3.3. The closed set S := {x ∈ M : λ1 (x) = λ2 (x)}, outside of which λ1 is C ∞ , is not equal to M ; thus λ1 is simple, hence C ∞ , on a nonempty open subset of M . 1 τ is a regular value of f if and only if Df (x) : Rp → Rq is full-rank for all x ∈ f −1 {τ }.
4
We will denote by ν1 the top eigenvector field of ∇2 ℓ on M \ S; by Assumption 3.3, ν1 is C ∞ . While Proposition 3.2 says that the directions normal to M are spanned by all the non-kernel eigenvectors of ∇2 ℓ, as we will see in Section 4 it is the ν1 direction (corresponding, to first order, to the variable y1 in Theorem 4.1) that is the most important of these for the dynamics of GD. While Assumption 3.3 guarantees nice behaviour in the ν1 direction orthogonal to M , our next assumption guarantees nice behaviour along M toward a manifold of flat minima. Assumption 3.4. There is a submanifold F ⊂ M \ S of local minima for λ1 |M \S such that: 1. λ1 is Morse-Bott along F : more precisely, denoting ν M F ⊂ T M for the normal bundle of F in M , ∇2M λ1 |ν M F ≻ 0. 2. An open neighbourhood of zero in the span of ν1 |F is invariant under gradient descent on ℓ. That λ1 is Morse-Bott along F reduces to the geodesic strong convexity of λ1 in [39] when F is a single point; thus the MorseBott assumption is a kind of strong convexity of λ1 in the directions normal to F in M . Invariance of the span of ν1 |F is a technical assumption required for correct decay in the higher order terms of the normal form; without it, GD is not necessarily attracted to F .
Assumption 3.1 Solution manifold M well-defined tangent/normal directions
Assumption 3.4 Nicely behaved tangent direction
Assumption 3.3 Nicely behaved normal direction
Assumption 3.5 Regularity of normal form PDE
Theorem 4.1 Normal form for GD
Our next and final assumption is used in the solution of a singular partial differential Figure 1: Roles of the assumptions in establishing the equation (PDE) required for our normal normal form for gradient descent. form. Assumption 3.5. Denote by ν1 M and ν2:q M the span of ν1 and its orthogonal complement in νM |M \S respectively, with P1 : T Rp |M \S → ν1 M and P2:q := I − ν1 ν1T : T Rp |M \S → ν2:q M the orthogonal projections. For each η ∈ R, define Aη : M → Rp×p by −1 −1 Aη := (λ1 I − ∇2 ℓ)|−1 P1 , ν2:q M P2:q + λ1 (1 − ηλ1 )
and define αη : M → R by 1 αη := − D3 ℓ[ν1 , ν1 , Aη ∇3 ℓ[ν1 , ν1 ]] + D4 ℓ[ν1 , ν1 , ν1 , ν1 ] 3
(6)
(7)
Then, for all x ∈ F and all η in a neighbourhood of 2/λ1 |F , one has αη (x) > 0 and Dαη (x) = 0. As shown in Proposition B.6, αη of Assumption 3.5 appears as a coefficient in the PDE that must be solved for our normal form (Theorem 4.1); that αη |F > 0 guarantees that this PDE can be solved to zeroth order, while Dαη |F = 0 guarantees that its solution is C 1 . Collectively, these assumptions should be understood as forming a hierarchy of geometric conditions underpinning our analysis, see Figure 1. Viewed in this way, the assumptions are not merely technical, but rather reflect a structured loss landscape geometry underlying the dynamics of large-step GD. 3.3
Case study: matrix factorisation
In this subsection, we tie down these abstract assumptions by illustrating their application to a class of examples of interest in deep learning. Fixing L ∈ N \ {0, 1}, consider L-layer matrix factorisation, PL QL for which p = l=1 dl × dl−1 , q = dL × d0 and f : l=1 Rdl ×dl−1 → RdL ×d0 is given by f (W1 , . . . , WL ) := WL · · · W1 .
(8)
Assumption 3.1 then holds when dl ≥ dL for all l ≤ L and τ has full rank dL with simple top singular value σ1 (Proposition E.1). Assumptions 3.3, 3.4 and 3.5 also all apply under these conditions; see Appendix E for details. The flat minima manifold F in this case has a particularly interesting structure, not noted in prior work [42, 40], which we now describe. 5
First note that up to a linear isometry which preserves f , τ may be assumed to be (rectangular) diagonal, τ = diag(σ1 , . . . , σdL ). Proposition E.2 then says that the global minimisers F of QL−1 λ1 in M \ S form a fibre bundle over the product l=1 S dl −1 of unit spheres S dl −1 ⊂ Rdl , QL whose typical fibre is an open subset of the solution manifold M ⊂ l=1 R(dl −1)×(dl−1 −1) for the lower-dimensional factorisation of τ2:d = diag(σ2 , . . . , σd ) (see Figure 2 for a simple example). Moreover, up to a linear isometry that preserves f , every point of F has the form 1/L !L σ1 0 (9) 0 Wl l=1
for some (W 1 , . . . , W L ) ∈ M . This fibre bundle structure has important consequences for the computation of the spectrum of ∇2M λ1 |F : it turns out that the directions in M that are normal to F correspond to either (i) conjugations of the factors of (9) by scalings of the top standard basis vector; (ii) conjugations of the factors of (9) by certain linear maps sending the top standard basis vector into other subspaces. The eigenvalues of ∇2M λ1 |F corresponding to 2−4/L (i) are all constant, equal to 4σ1 (and in particular equal to 4 when L = 2). Those corresponding to (ii) blow up to infinity approaching S and, when L = 2 achieve a lower-bound of 4σ1 /(σ1 − σd2 ) > 4 at the “balanced solution" studied in prior work [21]. In either case, all eigenvalues of ∇2 λ1 |ν M F are strictly positive, making λ1 Morse-Bott along F (Proposition E.5).
4 Normal form for GD in arbitrary codimension near flat minima manifold
Figure 2: The base (left), connected component of fibre (centre) and connected component of total space (right) of F for 2-layer matrix factorisation with d0 = d1 = d2 = 2. The base is the circle S 1 , while the fibre is an open subset of the solution manifold of the factorisation problem of 1 dimension lower (which, for d0 = d1 = d2 = 2, is simply a 1-dimensional hyperbola). The total space is obtained by attaching a copy of the fibre to each point in the base. This total space is a 2dimensional submanifold of the 4-dimensional solution manifold M , which is itself a submanifold of the 8-dimensional parameter space R2×2 × R2×2 .
In this section, we state our normal form for large-step GD in a neighbourhood of the flat minima manifold F (Theorem 4.1). Like the normal form in [39], our more general normal form splits the dynamics of GD into directions tangent to M (which we coordinatise by x) having the form of Riemannian GD (RGD) on the sharpness λ1 , and orthogonal to M (which we coordinatise by y = (y1 , y2:q )). Unlike in [39], however, in which the entire orthogonal direction is only 1-dimensional and evolves as a flip bifurcation, in our more general setting there are q independent orthogonal directions corresponding to our codimension q setting. The first of these orthogonal coordinates, y1 , aligns to first order with the top eigendirection ν1 of ∇2 ℓ and has the same flip bifurcation form as in [39]; the q − 1 remaining directions, y2:q , correspond to the smaller eigendirections of ∇2 ℓ and are stable contracting directions. Theorem 4.1 (Informal). Under Assumptions 3.1, 3.3, 3.4 and 3.5, about any x̄ ∈ F there is a C 1 change of coordinates (x, y1 , y2:q ) ∈ M × R × Rq−1 , depending on η, in which GD takes the form GD(η, x, y1 , y2:q ) = η, GDx (η, x, y1 ), GDy1 (η, x, y1 ), GDy2:q (η, x, y1 , y2:q ) , where GDx (η, x, y1 ) = x − ζ(η, x)y12 ∇M λ1 (x) + O |y1 |3 dM (x, F ) , (10) 3 4 GDy1 (η, x, y1 ) = (1 − ηλ1 (x))y1 + y1 + O y1 , (11) 2 GDy2:q (η, x, y1 , y2:q ) = Iq−1 − ηΛ2:q (x) y2:q + O |y1 |∥y2:q ∥, ∥y2:q ∥ (12) uniformly over all η in a neighbourhood of 2/λ1 |F and over all (x, y) in a neighbourhood of x̄ as y1 , y2:q → 0 and x → F . Here ζ is a C 1 function such that ζ(η, ·)|F ≡ αη−1 |F , and Λ2:q is a C ∞ field of symmetric matrices whose eigenvalues coincide at each x ∈ M with those of ∇2 ℓ(x)|ν2:q M . 6
At an intuitive level, our Theorem 4.1 allows us to anticipate how the dynamics will behave even without heavy analysis. For η near 2/λ1 |F , the spectral norm ∥Iq−1 − ηΛ2:q (x̄)∥2 < 1, so that GD2:q acts as a linear contraction near x̄. Meanwhile, GDx acts as RGD on λ1 , with step size controlled by y12 and ζ, while GDy1 makes y1 evolve as a flip bifurcation from dynamical systems theory [33] with linear component differing from −1 by a perturbation of ηλ1 |F − 2. In particular: 1. If ηλ1 |F < 2, GDy1 contracts linearly to zero, so GDx behaves as RGD with exponentially decaying step size, leading to exponential convergence to a suboptimally flat minimum of ℓ. 2. If ηλ1 |F = 2, GDy1 contracts sub-linearly to zero, so GDx behaves as RGD with polynomially decaying step size, leading to polynomial convergence to F . 3. If ηλ1 |F > 2, GDy1 tends exponentially toward a nonzero periodic orbit, so GDx behaves as RGD with constant step size, leading to exponential convergence to a periodic orbit centred on F . These behaviours are formalised in convergence theorems in the next section. On a technical level, our Theorem 4.1 is substantially more difficult than the corresponding result in [39]. First, a dimension reduction must be undertaken using a centre manifold theorem [38] to reduce the effective dimension of the problem from q > 1 to q = 1, which is unnecessary in the q = 1 setting of [39]. Second, the dynamics along this centre manifold can be transformed into the claimed normal form only by solving a PDE which is singular along F (Theorem C.4). Proving the existence of a sufficiently regular solution to this PDE (without which the normal form is impossible) required the introduction of arguments which are, to our knowledge, new even in the context of PDE theory and may be of independent interest (see Section C for our proof and literature review); in contrast, the corresponding PDE in [39] is singular only at a point, and can be solved using existing literature [56].
5
Convergence theorems
In this section we state our convergence theorems and provide the results of numerical simulations supporting them. As in [39], the dynamics of GD admit three qualitatively different convergence behaviours: subcritical, critical and supercritical, corresponding to the value of η relative to the stability threshold 2/λ1 |F . Given a point (x, y) := (x, y1 , y2:q ) in the coordinates of Theorem 4.1, its GD iterates will be denoted by GDt (x, y1 , y2:q ) =: (xt , y1,t , y2:q,t ) =: (xt , yt ). 5.1
Subcritical regime
We first state our convergence theorem in the subcritical regime, where the step size satisfies η < 2/λ1 |F . In this case, after a possible transient period of initial instability (in which the iterates move further away from the solution manifold), due to the descent on λ1 appearing in Theorem 4.1 the iterates eventually reach the stable set η < 2/λ1 |M and thereafter converge exponentially to a suboptimally flat global minimum of ℓ, see Figure 3. After appropriately accounting for the generalisation from λ1 being geodesically strongly convex about a single flat minimum, as in [39], to λ1 being Morse-Bott along the manifold F , as in this setting, the proof of Theorem 5.1 follows a similar argument to that of [39, Theorem 5.1]. See Subsection D.2 for details. Theorem 5.1. Suppose that Assumptions 3.1, 3.3, 3.4 and 3.5 hold, and that η < 2/λ1 |F . Then there is γ > 0 such that for all (x, y) ̸∈ M sufficiently close to F there is γ −2 λ1 (x) − λ1 |F T = O y1 (13) 2/η − λ1 |F such that η < 2/λ1 (xt ) for all t ≥ T , following which, setting β := 1 − (2 − ηλ1 (xT )) < 1 the iterates (xt , yt ) converge with rate O(β t ) to a suboptimally flat global minimum (x∞ , 0) for which 2 λ1 (x∞ ) − λ1 |F ≥ exp − O(y1,T (1 − β 2 )−1 ) (λ1 (xT ) − λ1 |F ). (14) 5.2
Critical regime
The critical regime is when η = 2/λ1 |F . In this regime, one observes the iterates converge nonmonotonically at a t−1/2 rate to a flat minimiser in F , see Figure 4. As in [39], the convergence 7
dM(xt, F)
‖yt‖ 10−2 10−3 10−4 10−5 10−6 10−7 10−2
10−8 10−9 10−10 0
40000
80000
0
Iteration
40000
80000
Iteration
Figure 3: Log y-scale plots of ∥yt ∥ (left) and dM (xt , F ) (right) for 5 independent trials of gradient descent in the subcritical regime on a 3 layer, 2 × 2 matrix factorisation problem. Initial instability (rising ∥yt ∥) is overcome in finite time followed by exponential convergence to a suboptimally flat minimum. theorem for this regime is the hardest to prove. The more general case we consider is, however, even more difficult than the codimension 1 case considered in [39]. The difficulties centre on the spectral properties of ∇2M λ1 |ν M F . Unlike in [39] where ∇2M λ1 |ν M F is a constant multiple of the identity, in our more general setting the dynamics must be separated according to the eigendirections of ∇2M λ1 |ν M F , with the dynamics in the smallest eigendirection controlling the convergence rate. Our proof requires both an assumption that the submanifold formed from this smallest eigendirection and the top eigenvector field ν1 of ∇2 ℓ is invariant (Assumption D.12), as well as an assumption that a conjectured analogue of the well-known strong-stable foliation theorem for normally hyperbolic manifolds [27, Theorem 4.1(e)] holds for the normally parabolic setting we consider (Conjecture D.7). While we can demonstrate (see Proposition E.7) that Assumption D.12 holds for two-layer matrix factorisation (and Theorem 5.2 itself appears to hold empirically even for L ̸= 2, see Figure 4), the latter conjecture lies in pure dynamical systems theory and is outside the scope of this paper. In the appendix following Conjecture D.7, we outline why we believe this conjecture is plausible, given its resemblance to the well-known stable foliation result in the normally hyperbolic case [27, Theorem 4.1(3)]. We refer the reader to Subsection D.3 for our proof of the following. Theorem 5.2. Suppose that Assumptions 3.1, 3.3, 3.4 and 3.5 hold, and that either ∇2M λ1 |ν M F is a constant multiple of the identity, or that Assumption D.12 and Conjecture D.7 hold. Then the iterates (xt , yt ) of any (x, y) ∈ / M sufficiently close to F converge to a point in F with rate Θ(t−1/2 ). 5.3
Supercritical regime
The supercritical regime is that in which the step size η is (slightly) larger than the stability threshold 2/λ1 |F . In this regime, the iterates converge exponentially to a period-two cycle along the span of the vector field ν1 |F , see Figure 5. Our proof of this follows from a similar argument to that of [39] after some minor modifications to account for our more general setting. See Subsection D.4 for details. Theorem 5.3. Suppose that Assumptions 3.1, 3.3, 3.4 and 3.5 hold. Then there is a constant C > 0 such that for all sufficiently small η > 2/λ1 |F and all (x, y) ∈ / M sufficiently close to F , the iterates (xt , yt ) of (x, y) under GD converge to a period-two orbit of amplitude Θ((ηλ1 |F − 2)1/2 ) along the span of ν1 |F with rate O((1 − C(ηλ1 |F − 2))t ).
6
Limitations, discussion and conclusion
Our work addresses one of the open questions left by [39], namely the extension of the theory to higher codimension. Our extension reveals that the insights of [39] persist in higher dimension, 8
dM(xt, F)
‖yt‖ 10−2
10−2
10−3
107
107
Iteration
Iteration
Figure 4: Log-log plots of ∥yt ∥ (left, solid) and dM (xt , F ) (right, solid) for 5 independent trials of gradient descent in the critical regime on a 3 layer, 2 × 2 matrix factorisation problem. Dotted lines show t−1/2 passing through the final values of each trial for reference. All trials exhibit the predicted asymptotic t−1/2 convergence to an element of F . dM(xt, F)
‖yt‖
10−2
10−3 10−2
10−4
0
40000
80000
0
Iteration
40000
80000
Iteration
Figure 5: Log y-scale plots of ∥yt ∥ (left) and dM (xt , F ) (right) for 5 independent trials of gradient descent in the supercritical regime on a 3 layer, 2 × 2 matrix factorisation problem. All trials exhibit the same exponential convergence rate to the claimed period-2 cycle along ν1 |F .
with GD dynamics splitting into RGD along M coupled to a flip bifurcation and contracting stable directions orthogonal to M . However, several questions remain unaddressed by our work. Beyond the supercritical regime: Prior work indicates that further increasing the step size beyond the supercritical limit considered in this work results in attractors of higher periodicity and chaos [16]. Addressing this higher order behaviour remains an open problem, for which we hope our work will serve as foundation. Global convergence: Although our convergence theorems hold in a neighbourhood of any point along the flat minima manifold, they remain merely local in that they say nothing of convergence away from this manifold. In particular, we do not believe that our results address either the “progressive sharpening” or “edge of stability” regimes identified in [13], except at the tail-end after the flat minima manifold has been found. Nonetheless, we anticipate that the geometric spirit of our analysis will be useful in providing rigorous theory for these regimes in future work. Geometry of flat minima: The popular hypothesis that flat minima generalise better [28, 31] has recently been challenged, with [22, 50] showing that flatness is not sufficient for good generalisation. Our discovery of the manifold structure of flat minima in matrix factorisation raises the intriguing possibility that flat minima are not all equal from the perspective of generalisation. A promising 9
avenue for future research is the identification of disinguished submanifolds of flat minima which do exhibit better generalisation, and more efficient algorithms directed toward such submanifolds. Parabolic foliations conjecture: In its most general form, our Theorem 5.2 relies on a stable foliation conjecture for parabolic dynamical systems (Conjecture D.7). Although a proof would complement our theory, it would likely be difficult to produce and may be of limited further utility to DL.
References [1] Atish Agarwala, Fabian Pedregosa, and Jeffrey Pennington. Second-order regression models exhibit progressive sharpening to the edge of stability. In ICML, 2023. [2] K. Ahn, J. Zhang, and S. Sra. Understanding the unstable convergence of gradient descent. In ICML, 2022. [3] Z. Allen-Zhu, Y. Li, and Z. Song. A Convergence Theory for Deep Learning via OverParameterization. In ICML, pages 242–252, 2019. [4] J. M. Altschuler and P. Parrilo. Acceleration by Stepsize Hedging: Multi-Step Descent and the Silver Stepsize Schedule. Journal of the ACM, 2023. [5] J. M. Altschuler and P. Parrilo. Acceleration by stepsize hedging: Silver Stepsize Schedule for smooth convex optimization. Mathematical Programming, pages 1–14, 2024. [6] S. Arora, Z. Li, and A. Panigrahi. Understanding Gradient Descent on Edge of Stability in Deep Learning. In ICML, 2022. [7] I. Baldomá and E. Fontich. Stable manifolds associated to fixed points with linear part equal to identity. Journal of Differential Equations, 197:45–72, 2004. [8] S. Bombari, M. H. Amani, and M. Mondelli. Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization. In NeurIPS, 2022. [9] Y. Cai, J. Wu, S. Mei, M. Lindsey, and P. L. Bartlett. Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization. In NeurIPS, 2024. [10] Augustin-Louis Cauchy. Méthode générale pour la résolution des systèmes d’équations simultanées. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences, 25:536–538, 1847. [11] Lei Chen and Joan Bruna. Beyond the Edge of Stability via Two-step Gradient Updates. In ICML, 2023. [12] L. Chizat, E. Oyallon, and F. Bach. On Lazy Training in Differentiable Programming . In NeurIPS, 2019. [13] J. Cohen, S. Kaur, Y. Li, J. Zico Kolter, and A. Talwalkar. Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability. In ICLR, 2021. [14] Jeremy Cohen, Alex Damian, Ameet Talwalkar, J Zico Kolter, and Jason D. Lee. Understanding Optimization in Deep Learning with Central Flows. In ICLR, 2025. [15] A. Damian, E. Nichani, and J. Lee. Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability. In ICLR, 2023. [16] Dayal Singh Kalra and Tianyu He and Maissam Barkeshli. Universal Sharpness Dynamics in Neural Network Training: Fixed Point Analysis, Edge of Stability, and Route to Chaos. In ICLR, 2025. [17] S. S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. In ICML, pages 1675–1685, 2019. [18] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient Descent Provably Optimizes Overparameterized Neural Networks. In ICLR, 2019. 10
[19] G. Frobenius. Uber die Integration der linearen Differentialgleichungen durch Reihen. Journal für die reine und angewandte Mathematik, 76:214–235, 1873. [20] R. Gérard and H. Tahara. Holomorphic and Singular Solutions of Nonlinear Singular First Order Partial Differential Equations. Publ. RIMS, Kyoto Univ., 26:979–1000, 1990. [21] Avrajit Ghosh, Soo Min Kwon, Rongrong Wang, Saiprasad Ravishankar, and Qing Qu. Learning dynamics of deep matrix factorization beyond the edge of stability. In ICLR, 2025. [22] D. Granziol. Flatness is a False Friend. arXiv:2006.09091, 2020. [23] B. Grimmer. Provably faster gradient descent via long steps. SIAM Journal on Optimization, 34:2588–2608, 2024. [24] B. Grimmer, K. Shu, and A. L. Wang. arXiv:2309.09961, 2023.
Accelerated gradient descent via long steps.
[25] B. Grimmer, K. Shu, and A. L. Wang. Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS Journal on Optimization, 7:156–169, 2025. [26] M. W. Hirsch. Differential Topology. Springer, 1976. [27] M. W. Hirsch, C. C. Pugh, and M. Schub. Invariant Manifolds. Springer, 1977. [28] S. Hochreiter and J. Schmidhuber. Flat minima. Neural Computation, 9(1):1–42, 1997. [29] A. Jacot, F. Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In NeurIPS, pages 8571–8580, 2018. [30] H. Karimi, J. Nutini, and M. Schmidt. Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition. In ECML PKDD, pages 795—-811, 2016. [31] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, P. Tak, and P. Tang. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. In ICLR, 2017. [32] Itai Kreisler, Mor Shpigel Nacson, Daniel Soudry, and Yair Carmon. Gradient descent monotonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. In ICML, 2023. [33] Y. A. Kuznetsov. Elements of Applied Bifurcation Theory, Fourth Edition. Springer, 2023. [34] J. Lee, L. Xiao, S. Schoenholtz, Y. Bahri, R. Novak, J. Sohl-Dickstein, and J. Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. NeurIPS, 2019. [35] J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient Descent Only Converges to Minimizers. In COLT, 2016. [36] S. Lee and C. Jang. A new characterization of the edge of stability based on a sharpness measure aware of batch gradient distribution. In ICLR, 2023. [37] Liming Liu, Zixuan Zhang, Simon Du, and Tuo Zhao. A minimalist example of edge-of-stability and progressive sharpening. In NeurIPS, 2025. [38] L. E. MacDonald. Centre manifold theorem for maps along manifolds of fixed points. arXiv:2604.18202, 2026. [39] L. E. MacDonald, H. Min, L. Palma, S. Tarmoun, Z. Xu, and R. Vidal. Convergence Rates for Gradient Descent on the Edge of Stability for Overparametrised Least Squares. In NeurIPS, 2025. [40] P. Marion and L. Chizat. Deep linear networks for regression are implicitly regularized towards flat minima. In NeurIPS, 2024. [41] E. Mengi, E. A. Yildirim, and M. Kilic. Numerical Optimization of Eigenvalues of Hermitian Matrix Functions. SIAM Journal on Matrix Analysis and Applications, 35, 2014. 11
[42] R. Mulayoff and T. Michaeli. Unique Properties of Flat Minima in Deep Networks. In ICML, 2020. [43] Q. Nguyen. On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths. In NeurIPS, 2021. [44] Q. Nguyen and M. Mondelli. Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology. In NeurIPS, 2020. [45] Q. Nguyen, M. Mondelli, and G. Montufar. Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks. In ICML, 2021. [46] H. Tahara. Solvability of partial di¤erential equations of nonlinear totally characteristic type with resonances. J. Math. Soc. Japan, 55:1095–1113, 2003. [47] Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect. In ICLR, 2022. [48] Yuqing Wang, Zhenghao Xu, Tuo Zhao, and Molei Tao. Good regularity creates large learning rate implicit biases: edge of stability, balancing, and catapult. In NeurIPS 2023 Workshop on Mathematics of Modern Machine Learning, 2023. [49] Z. Wang, Z. Li, and J. Li. Analyzing Sharpness along GD Trajectory: Progressive Sharpening and Edge of Stability. In NeurIPS, 2022. [50] K. Wen, Z. Li, and T. Ma. Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization. In NeurIPS, 2023. [51] J. Wu, P. L. Bartlett, M. Telgarsky, and B. Yu. Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency. In COLT, 2024. [52] J. Wu, V. Braverman, and J. Lee. Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability. In NeurIPS, 2023. [53] J. Wu, P. Marion, and P. L. Bartlett. Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression. In NeurIPS, 2025. [54] L. Wu, C. Ma, and W. E. How SGD Selects the Global Minima in Over-parameterized Learning: A Dynamical Stability Perspective. In NeurIPS, 2018. [55] Yoo, G. and Song, M. and Yun, C. Understanding Sharpness Dynamics in NN Training with a Minimalist Example: The Effects of Dataset Difficulty, Depth, Stochasticity, and More. In ICML, 2025. [56] M. Yoshino and A. Shirai. Singular solutions of nonlinear partial differential equations with resonances. J. Math. Soc. Japan, 60:237–263, 2008. [57] X. Zhu, Z. Wang, X. Wang, M. Zhou, and R. Ge. Understanding Edge-of-Stability Training Dynamics with a Minimalist Example. In ICLR, 2023.
12
A
Additional notation
Given vector bundles E and E ′ over a space X denote by Hom(E, E ′ ) the vector bundle over X whose fibre over x ∈ X is the space of linear maps Ex → Ex′ . Given another vector bundle E ′′ over X and sections σ, σ ′ of Hom(E, E ′ ) and Hom(E ′ , E ′′ ) respectively, σ ′ ◦ σ will denote the section of Hom(E, E ′′ ) given by fibrewise composition of σ and σ ′ . The notation E ⊗ E ′ will be used to denote the tensor product bundle whose fibre over x ∈ X is Ex ⊗ Ex′ . Given k ∈ N, E ⊗k will denote the k th tensor power of E, which is the vector bundle over X whose fibre over x ∈ X is the k th tensor power Ex⊗k := Ex ⊗ · · · ⊗ Ex | {z }
(15)
k times
of the vector space Ex . Given additional vector bundles F, F ′ over X and sections σE , σF of Hom(E, E ′ ) and Hom(F, F ′ ) respectively, their tensor product σE ⊗ σF is the section of Hom(E ⊗ F, E ′ ⊗ F ′ ) defined by (σE ⊗ σF )(x)[v ⊗ w] := σE (x)[v] ⊗ σF (x)[w],
x ∈ X,
v ∈ Ex , w ∈ Fx .
(16)
Given k ∈ N, σ ⊗k will denote the section of Hom(E ⊗k , (E ′ )⊗k ) defined by σ ⊗k (x)[v1 ⊗ · · · ⊗ vk ] := σ(x)[v1 ] ⊗ · · · ⊗ σ(x)[vk ],
(x, vi ) ∈ E
∀i = 1, . . . , k.
(17)
Symmetric tensor products E ⊙ E ′ , σE ⊙ σF and powers E ⊙k and σ ⊙k are defined in a formally identical fashion with ⊗ replaced by ⊙.
B
Normal form for GD
In this section, we prove the normal form Theorem 4.1 for GD. We will in fact prove the more precise Theorem B.7. We adopt the notation used throughout the main body of the paper as well as that of Appendix A. Our proof will factor through four distinct coordinate changes; the first merely rewrites GD in tubular neighbourhood coordinates; the second invokes a centre manifold theorem to distinguish an appropriately invariant orthogonal coordinate corresponding to the top eigenvalue of the Hessian; the third coordinate transformation deforms this distinguished centre manifold coordinate into a form more amenable to convergence analysis by solving a partial differential equation (see Section C; the final disentangles the exponentially decaying coordinates from those which determine the dynamics of the system using a strong-stable foliation theorem. Let us fix x̄ ∈ F as in the statement of Theorem 4.1. Although ν2:q M need not be globally trivialisable2 , it is locally trivial, so there is an open neighbourhood Vx ⊂ M \ S of x̄ on which we can find a C ∞ orthonormal frame field ν2:q : Vx → ν2:q M |Vx , which is completed by ν1 to a local orthonormal frame field ν : Vx → νM |Vx for νM . We will assume this ν to be fixed in what follows; note that Vx may be shrunk if necessary in what follows to achieve the neighbourhood Vx in the statement of Theorem B.7. We must specify some notation concerning derivatives of ν. The field ν : Vx → Rp×q acts on vectors z ∈ Rq to give ν(x)z ∈ νx M ⊂ Tx Rp for any x ∈ Vx′ . Its derivative DM ν(x) therefore acts on a pair of vectors, one corresponding to the direction in which it is differentiated in Vx ⊂ M , and the other corresponding to the evaluation of ν on q-vectors as in the previous sentence; thus, given vx ∈ Tx M and z ∈ Rq , we will denote DM ν(x)[vx ]z ∈ Tx Rp for this dual evaluation. A similar remark holds for the higher derivatives of ν; given k vectors v1 , . . . , vk ∈ Tx M and z ∈ Rq , we will k denote DM ν(x)[v1 , . . . , vk ]z ∈ Tx Rp for the k th order derivative of ν evaluated on the v1 , . . . , vk in the M -directions. With the local frame ν1:q in hand, recall that we can find an open neighbourhood V ⊂ M \ S × Rq of (x̄, 0), with V ∩ M = Vx , on which the normal exponential map E : V → Rp defined by E(x, y) := x + ν(x)z,
(x, z) ∈ V
(18)
is a diffeomorphism onto its image. Our first result gives a leading order expression for the inverse of this map, and generalises [39, Proposition C.3] to the case where q may be greater than 1. 2 Consider, for instance, the model f : R3 × R2 → R3 defined by f (x, y) := (∥x∥2 − 1, y)
13
Lemma B.1. Given x ∈ Vx and v ∈ Tx Rp , write v = vx + ν1:q (x)vz , where vx ∈ Tx M and vz ∈ Rq . Then for all x ∈ Vx and all v ∈ Tx Rp sufficiently small that x + v ∈ E(V ), one has x + vx − PT M (x)DM ν(x)[vx ]vz E −1 (x + v) = + O ∥vx ∥3 , ∥vx ∥2 ∥vz ∥, ∥vx ∥∥vz ∥2 (19) vz − ν(x)T DM ν(x)[vx ]vz uniformly over V as v → 0. Proof. Since E −1 is C ∞ , by Taylor’s theorem, one has 1 E −1 (x + v) = E −1 (x) + DE −1 (x)[v] + D2 E −1 (x)[v, v] + error(x, v), (20) 2 for some C ∞ remainder function error(x, v). By [39, Lemma C.3], since E(x, z) = x + ν(x)z has all z-derivatives of order > 1 vanishing, this remainder function satisfies error(x, v) = O ∥vx ∥3 , ∥vx ∥2 ∥vz ∥, ∥vx ∥∥vz ∥2 (21) uniformly over V as v → 0. Now, to compute the leading order terms of (20), observe first that for any (x, z) ∈ V , one has vx DE(x, z) = vx + DM ν(x)[vx ]z + ν(x)vz (22) vz so that in particular DE(x, 0)
vx = vx + ν(x)vz , vz
(23)
while ⊙2 vx 2 D E(x, z) = DM ν(x)[vx⊙2 ]z + 2DM ν(x)[vx ]vz vz 2
(24)
so that in particular D2 E(x, 0)
vx = 2DM ν(x)[vx ]vz . vz
By differentiating the identity E −1 ◦ E = identity, one then obtains PT M (x) DE −1 (x) = DE(x, 0)−1 = , ν(x)T
(25)
(26)
while D2 E −1 (x)[v, v] = −DE(x, 0)−1 D2 E(x, 0)[DE(x, 0)−1 v, DE(x, 0)−1 v] PT M (x)DM ν(x)[vx ]vz = −2 . ν(x)T DM ν(x)[vx ]vz
(27) (28)
This completes the proof. We remark that the term ν T DM ν that appears in Lemma B.1 is, in general, the expression of the connection on the vector bundle νM → M inherited from its embedding into the trivial bundle T Rp |M → M (with its trivial connection) and expressed in the frame ν. Since this connection is metric-compatible and ν is an orthonormal frame field, one is guaranteed that ν T DM ν evaluates on any tangent vector vx ∈ Tx M to give an antisymmetric q × q matrix ν(x)T DM ν(x)[vx ]; if q = 1, this is enough to force the term to vanish, however it need not vanish in general. Having fixed the local orthonormal frame field ν1:q , it will be convenient to introduce the following notation. Letting PT M : T Rp |M → T M denote the orthogonal projection, we denote ⊙(k−1) ∇k ℓν := ∇k ℓ ◦ ν1:q ∈ Hom Vx × (Rq )⊙(k−1) , T Rp |M \S , (29) ⊙(k−1) ∇k ℓ∥ν := PT M ◦ ∇k ℓ ◦ ν1:q ∈ Hom Vx × (Rq )⊙(k−1) , T M |M \S (30) and ⊙(k−1) T k ∇k ℓ⊥ ∈ Hom Vx × (Rq )⊙(k−1) , (M \ S) × Rq . (31) ν := ν1:q ◦ ∇ ℓ ◦ ν1:Q The following lemma gives the expression for GD in tubular neighbourhood coordinates associated to the local frame ν. 14
Proposition B.2. Consider the embedding Φ1 : R × V → Rp defined by Φ1 (η, x, z) := (η, E(x, z)),
(η, x, z) ∈ R × V.
(32)
Let U1 ⊂ R × V be any open neighbourhood of (2/λ1 |F , x̄, 0) such that GD ◦ Φ1 (U1 ) ⊂ Φ1 (R × V ). Then one has Φ−1 (33) 1 ◦ GD ◦ Φ1 (η, x, z) =: η, GDx (η, x, z), GDz (η, x, z) η 2 = x − ηz21 ∇M λ1 (x) + O |z1 |3 dM (x, F ), |z1 |∥z2:q ∥ , (34) T1 (η, x)[z] + T2 (η, x)[z ⊗2 ] + T3 (η, x)[z ⊗3 ] + O(∥z∥4 ) for all (η, x, z) ∈ U1 , where η T2 (η, ·) = − ∇3 ℓ⊥ ν, 2
T1 (η, ·) = I − η∇2 ℓ⊥ ν,
(35)
and η T 3 ∥ T3 (η, ·) = − ∇4 ℓ⊥ ν − η ν ◦ DM ν ◦ (∇ ℓν ⊗ T1 ) 6
(36)
Proof. For (η, x, z) ∈ U1 , one has E −1 GD(η, E(x, z)) = E −1 x + ν(x)z − η∇ℓ(x + ν(x)z) .
(37)
We therefore apply Lemma B.1 with v = ν(x)z − η∇ℓ(x + ν(x)z). We begin by computing PT M (x)[v], for which we first make the observation that by Assumption 3.4, for any x∗ ∈ F sufficiently close to x̄, one has PT M (x∗ ) ∇ℓ(x∗ + z1 ν1 (x∗ )) = 0 for all z1 ∈ R sufficiently small, from which it follows by differentiability of PT M , ∇ℓ and ν1 that PT M (x) ∇ℓ(x + z1 ν1 (x)) = O(dM (x, F )) (38) as x → F . One then computes vx = PT M (x)[v] = −η PT M (x) ∇ℓ(x + ν(x)z) = −η PT M (x) ∇ℓ(x + z1 ν1 (x)) + O(|z1 |∥z2:q ∥)
(39) (40)
ηz12
PT M (x)∇3 ℓ[ν1⊙2 ](x) + O |z1 |3 dM (x, F ), |z1 |∥z2:q ∥ (41) 2 2 ηz = − 1 ∇M λ1 (x) + O |z1 |3 dM (x, F ), |z1 |∥z2:q ∥ (42) 2 uniformly over U1 as z → 0 and x → F , where on the second line we have used the fact that ∇ℓ|M ≡ 0 and on the final line we have used the fact that PT M ∇3 ℓ[ν1⊙2 ] = PT M ∇λ1 = ∇M λ1 . On the other hand, letting PνM : T Rp |M → νM denote the projection, one has η η 3 ⊥ ⊙2 ⊙3 ] − ∇4 ℓ⊥ ] + O(∥z∥4 ) (43) vz = PνM (x)[v] = (I − η∇2 ℓ⊥ ν (x)[z ν (x)z − ∇ ℓν (x)[z 2 6 uniformly over U1 as z → 0 by Taylor expansion. Finally, noting the coarser estimates ∥vx ∥ = O z12 dM (x, F ), |z1 |∥z2:q ∥ , ∥vz ∥ = O ∥z∥ (44) =−
and applying Lemma B.1 gives the result. We now give a lemma which provides a local invariant manifold tangent to the top-eigenbundle of ∇2 ℓ, with respect to which our next coordinate transformations will be defined. The lemma is an immediate application of [38, Theorem 1.2] to the problem at hand. Lemma B.3. Shrinking Vx if necessary so that its closure does not intersect S, there is a C 4 submanifold W c ⊂ R × Rp containing (2/λ1 |F , x̄) which: 1. Intersects R × M ⊂ R × Rp in a neighbourhood Ve of {2/λ1 |F } × M which is open relative to R × M . 2. Is tangent at each point (η, x) ∈ Ve to T(η,x) (R × M ) ⊕ span(ν1 (x)). 15
3. Is invariant under GD, i.e. GD(W c ) ⊂ W c . We now demonstrate how the invariant manifold of Lemma B.3 can be applied to reduce the orthogonal dynamics to being essentially 1-dimensional. In the (η, x, z) coordinates of Lemma B.2, there is an open subset V1′′ ⊂ R containing 0 such that the manifold W c is given by the graph of a C 4 function h : Ve × V1′′ → Rq−1 : Φ−1 W c = {(η, x, z1 , h(η, x, z1 )) : (η, x, z1 ) ∈ Ve × V1′′ }. (45) 1
c
Note that since W intersects R × M in Ve one has h(η, x, 0) = 0, Dη h(η, x, 0) = 0, Dx h(η, x, 0) = 0,
∀(η, x) ∈ Ve ;
(46)
c
since moreover W is tangent at (η, x) ∈ Ve to T(η,x) (R × M ) ⊕ span(ν1 (x)), one has Dz1 h(η, x, 0) = 0, ∀(η, x) ∈ Ve . Furthermore, splitting GDz = (GDz1 , GDz2:q ), since W c is invariant under GD, one has
(47)
GDz2:q (η, x, z1 , h(η, x, z1 )) = h η, GDx (η, x, z1 , h(η, x, z1 )), GDz1 (η, x, z1 , h(η, x, z1 )) . (48) For the purposes of proving convergence theorems, it is convenient to have coordinates (x, z1 , y2:q ) in which W c is given by {y2:q = 0}. This can be achieved by defining Φ2 : Ve × V1′′′ × Rq−1 → Ve × V1′′′ × Rq−1 by Φ2 (η, x, z1 , y2:q ) := (η, x, z1 , h(η, x, z1 ) + y2:q ), (η, x, z1 , y2:q ) ∈ Ve × V1′′ × Rq−1 , (49) ′ and defining U2′ := Φ−1 2 U1 , so that Φ2 : U2 → U1 . ′ Proposition B.4. Let U2 ⊂ U2 be an open neighbourhood of (2/λ1 |F , x̄, 0) such that GD ◦ Φ1 ◦ Φ2 (U2 ) ⊂ Φ1 ◦ Φ2 (U2′ ). Then one has (Φ1 ◦ Φ2 )−1 ◦ GD ◦ (Φ1 ◦ Φ2 ) (η, x, z1 , y2:q ) (50) η ηz12 3 x − ∇ λ (x) + O |z M 1 1 | dM (x, F ), |z1 |∥y 2:q ∥ 2 (51) = eT T1 (η, x)[z] + T2 (η, x)[z ⊙2 ] + T3 (η, x)[z ⊙3 ] + O(∥z∥4 ) 1 eT2:q T1 (η, x)[e2:q y2:q ] + O(|z1 |∥y2:q ∥, ∥y2:q ∥2 )
for all (η, x, z1 , y2:q ) ∈ U2 , where z = (z1 , h(η, x, z1 ) + y2:q ), e1 ∈ Rq is the first standard basis vector, and e2:q ∈ Rq×(q−1) is the last (q − 1) columns of the q × q identity matrix. Proof. The only things that must be checked are the error term in the x-update and the form taken by the y2:q -update. Both follow from invariance of the graph of h. Concerning the x-update, its error term is initially of the form O(|z1 |3 dM (x, F ), |z1 |∥z2:q ∥), where z2:q = h(x, z1 ) + y2:q = O(|h(x, z1 )|, ∥y2:q ∥). Now the Taylor expansion of h about any point (η, x, 0) ∈ Ve × V1′′′ is uniquely determined by the invariance equation (48). On the other hand, by Assumption 3.4, for any x∗ ∈ F sufficiently close to x̄, there is ϵ > 0 such that the line {(x∗ , z1 , 0) : z1 ∈ (−ϵ, ϵ)} is invariant. Thus at any such x∗ one has D2 h(η, x∗ , 0) = 0, from which it follows that h(η, x, z1 ) = O(z12 dM (x, F )) as x → F and z1 → 0. Thus the error term in the x-update takes the claimed form O(|z1 |3 dM (x, F ), |z1 |∥y2:q ∥). Suppressing evaluation at η for notational convenience, concerning the y2:q update, note that since φ−1 (x, u, v) = (x, u, v − h(x, u)), the y2:q update is given by GDz2:q (x, z1 , h(x, z1 ) + y2:q ) − h GDx (x, z1 , h(x, z1 ) + y2:q ), GDz1 (x, z1 , h(x, z1 ) + y2:q ) (52) 2
=GDz2:q (x, z1 , h(x, z1 )) + Dz2:q GDz2:q (x, z1 , h(x, z1 ))[y2:q ] + O(∥y2:q ∥ )
(53)
− h(GDx (x, z1 , h(x, z1 )), GDz1 (x, z1 , h(x, z1 )))
(54) Dz2:q GDx (x, z1 , h(x, z1 )) + Dh(GDx (x, z1 , h(x, z1 )), GDz1 (x, z1 , h(x, z1 ))) [y2:q ] + O(∥y2:q ∥2 ) Dz2:q GDz1 (x, z1 , h(x, z1 )) (55)
=Dz2:q GDz2:q (x, 0, 0)[y2:q ] + O(|z1 |∥y2:q ∥, ∥y2:q ∥2 ), 16
(56)
where Dz2:q denotes the derivative with respect to the z2:q variable, and for the final equality we have invoked (48) and Dh(x, z1 ) = O(z1 ). This proves the result. We now expose a further coordinate transformation which simplifies the dynamics of the z1 variable to the form seen in Theorem 4.1. For this, it is necessary to compute the second derivative of h in the following lemma. Lemma B.5. For any (η, x) ∈ Ve , one has Dz21 h(η, x, 0) = λ1 (x)Iq−1 − eT2:q ∇2 ℓ⊥ ν (x)e2:q
−1 T 3 ⊥ e2:q ∇ ℓν (x)[e⊙2 1 ].
(57)
where e2:q ∈ Rq×(q−1) is the final (q − 1) columns of the q × q identity matrix. Proof. The proof is by Taylor expansion of both sides of (48) in z1 and equating coefficients. Denote H(η, x, z1 ) := (z1 , h(η, x, z1 )) and observe that H(η, x, 0) = 0, Dz1 H(η, x, 0) = (1, Dz1 h(η, x, 0))T = (1, 0)T and Dz21 H(x, 0) = (0, Dz21 h(x, 0))T . Then the right hand side has Taylor expansion GDz2:q (η, x, z1 , h(η, x, z1 ))
(58)
=GDz2:q (η, x, 0, 0) + Dz1:q GDz2:q (η, x, 0, 0)Dz1 H(η, x, 0)z1 + + (1/2)Dz21:q GDz2:q (η, x, 0, 0)[Dz1 H(η, x, 0), Dz1 H(η, x, 0)]z12 + + (1/2)Dz1:q GD2:q (η, x, 0, 0)Dz21 H(η, x, 0)z12 + O(z13 ) 2 1 2 T 3 ⊥ 3 = eT2:q (Iq − η∇2 ℓ⊥ ν (x))e2:q Dz1 h(η, x, 0) − η e2:q ∇ ℓν (x)[e1 , e1 ] z1 + O z1 . 2
(59) (60) (61) (62)
Since GDx (η, x, 0) = x, GDz1 (η, x, 0) = 0, using h|Ve ×{0} ≡ 0 and Dh|Ve ×{0} ≡ 0 one sees that the left hand side has the Taylor expansion h η, GDx (η, x, H(x, z1 )), GDz1 (η, x, H(x, z1 )) (63) 2 ⊙2 =(1/2)Dx h(η, x, 0) Dz1:q GDx (η, x, 0) Dz1 H(η, x, 0)[z1 ] + (64) 2 + Dx,z1 h(η, x, 0) Dz1:q GDx (η, x, 0) Dz1 H(η, x, 0)[z1 ], Dz1:q GDz1 (η, x, 0) Dz1 H(η, x, 0)[z1 ] + (65) ⊙2 3 2 + O z1 (66) + (1/2)Dz1 h(η, x, 0) Dz1:q GDz1 (η, x, 0) Dz1 H(η, x, 0)[z1 ] 1 = (1 − ηλ1 (x)) Dz21 h(η, x, 0) z12 (67) 2 since Dz1:q GDx (η, x, 0) = 0. Equating coefficients, therefore, one has ⊙2 2 T 3 ⊥ eT2:q (Iq − η∇2 ℓ⊥ (x))e D h(η, x, 0) − η e ∇ ℓ (x)[e = (1 − ηλ1 (x)) Dz21 h(η, x, 0), ] 2:q ν z1 2:q ν 1 (68) which may be rearranged to obtain the claimed formula. We now come to simplifying the dynamics along the centre manifold via another change of coordinates. It is this step which requires the solution of a singular PDE, and in which the proof of the corresponding result in [39] is erroneous since it cites a classical algebraic argument for the isolated y1 -system [33, Theorem 4.3] (in which x is assumed to be fixed) without accounting for the fact that the y1 -component of the system is actually coupled to the x-component of the system. As we demonstrate below, properly accounting for this coupling is what necessitates the solution of a PDE. Proposition B.6. Shrinking Ve if necessary, there is an open neighbourhood V1′ ⊂ V1′′ of 0 in R and a C 1 map ψ : Ve × V ′ → R of the form 1
1 ψ(η, x, y1 ) = ψ1 (η, x)y1 + ψ2 (η, x)y12 2 17
(69)
for C 1 functions ψ1 and ψ2 on Ve such that, with Φ3 (η, x, y1 , y2:q ) = (η, x, ψ(η, x, y1 ), y2:q ), one has (Φ1 ◦ Φ2 ◦ Φ3 )−1 ◦ GD ◦ (Φ1 ◦ Φ2 ◦ Φ3 ) (η, x, y1 , y2:q ) (70) η x − ηψ1 (η,x)y12 ∇M λ1 (x) + O |y1 |3 dM (x, F ), |y1 |∥y2:q ∥) , 2 (71) = (1 − ηλ1 (x))y1 + y13 + O y14 , |y1 |∥y2:q ∥ eT2:q T1 (η, x)[y2:q ] + O |y1 |∥y2:q ∥, ∥y2:q ∥2 2
for all (η, x, y1 , y2:q ) in some open neighbourhood U3 of (2/λ1 |F , x̄, 0, 0), with ηψ1 (η,·) |F ≡ αη−1 2 where αη is defined in Assumption 3.5. Proof. We begin by assuming a general form for ψ in y1 ; it will later be shown that the higher order terms can be taken to be zero. Write 1 1 ψ(η, x, y1 ) := ψ1 (η, x)y1 + ψ2 (η, x)y12 + ψ3 (η, x)y13 + O y14 . (72) 2 6 From the desired identity GDy1 η, x, ψ(η, x, y1 ), h(x, ψ(η, x, y1 )) ηψ(η, x, y1 )2 = ψ η, x − ∇M λ1 (x) + O y13 , (1 − ηλ1 (x))y1 + y13 + O y14 (73) 2 we derive expressions for ψi (η, x), i = 1, 2, 3, by Taylor-expanding both sides and equating coefficients. To expand the left hand side, first note that 1 h(η, x, ψ(η, x, y1 )) = Dz21 h(η, x, 0)ψ1 (η, x)2 y12 + O y13 (74) 2 Then: GDy1 η, x, ψ(η, x, y1 ), h(η, x, ψ(η, x, y1 )) (75) T =e1 T1 (x) e1 ψ(η, x, y1 ) + e2:q h(η, x, ψ(η, x, y1 )) (76) ⊗2 + eT1 T2 (x) e1 ψ(η, x, y1 ) + e2:q h(η, x, ψ(η, x, y1 )) (77) ⊗3 T 4 + e1 T3 (x) e1 ψ(η, x, y1 ) + e2:q h(η, x, ψ(η, x, y1 )) + O y1 (78) =(1 − ηλ1 (x))ψ1 (η, x)y1 2 1 ⊗2 + (1 − ηλ1 (x))ψ2 (η, x) − η ψ1 (η, x)2 eT1 ∇3 ℓ⊥ ν (x)[e1 ] y1 2 1 2 + (1 − ηλ1 (x))ψ3 (η, x) − 3η ψ1 (η, x)3 eT1 ∇3 ℓ⊥ ν (x)[e1 , e2:q Dz1 h(η, x, 0)]] 6 ⊗2 ⊗3 3 T 4 ⊥ − 3η ψ1 (η, x)ψ2 (η, x)eT1 ∇3 ℓ⊥ ν (x)[e1 ] − ηψ1 (η, x) e1 ∇ ℓν (x)[e1 ] 3 4 − 6η ψ1 (η, x)3 eT1 ν T ◦ DM ν ◦ (∇3 ℓ∥ν ⊗ T1 ) (x)[e⊗3 1 ] y1 + O y1 .
(79) (80) (81) (82) (83)
Note that the matrix-valued function ν T ◦ DM ν ◦ [w, ·] is antisymmetric for any tangent field w on T M since ν is an orthonormal frame; hence eT1 ν T ◦ DM ν ◦ (∇3 ℓ∥ν ⊗ T1 ) [e⊗3 (84) 1 ] T T 2 ∥ ⊗2 = (1 − ηλ1 (x))e1 ν ◦ DM ν ◦ [∇ ℓν [e1 ], e1 ] = 0. (85) Thus
(86)
= (1 − ηλ1 (x))ψ1 (η, x)y1 2 1 ⊗2 + (1 − ηλ1 (x))ψ2 (η, x) − η ψ1 (η, x)2 eT1 ∇3 ℓ⊥ ν (x)[e1 ] y1 2 1 2 + (1 − ηλ1 (x))ψ3 (η, x) − 3η ψ1 (η, x)3 eT1 ∇3 ℓ⊥ ν (x)[e1 , e2:q Dz1 h(η, x, 0)] 6 3 ⊗2 ⊗3 3 T 4 ⊥ 4 − 3η ψ1 (η, x)ψ2 (η, x)eT1 ∇3 ℓ⊥ ν (x)[e1 ] − ηψ1 (η, x) e1 ∇ ℓν (x)[e1 ] y1 + O y1 .
(87)
GDy1 η, x, ψ(η, x, y1 ), h(η, x, ψ(η, x, y1 ))
18
(88) (89) (90)
On the other hand, ψ(η, x, y1 )2 3 3 4 ψ η, x − η ∇M λ1 (x) + O y1 , (1 − ηλ1 (x))y1 + y1 + O y1 (91) 2 η =ψ1 (η, x) (1 − ηλ1 (x))y1 + y13 − ⟨∇M ψ1 (η, x), ∇M λ1 (x)⟩(1 − ηλ1 (x))ψ1 (η, x)2 y13 (92) 2 1 1 + ψ2 (η, x)(1 − ηλ1 (x))2 y12 + ψ3 (η, x)(1 − ηλ1 (x))3 y13 (93) 2 6 =(1 − ηλ1 (x))ψ1 (η, x)y1 (94) 1 (95) + (1 − ηλ1 (x))2 ψ2 (η, x)y12 2 1 2 3 + 6ψ1 (η, x) − 6η⟨∇M ψ1 (η, x), ∇M λ1 (x)⟩(1 − ηλ1 (x))ψ1 (η, x) + ψ3 (η, x)(1 − ηλ1 (x)) y13 . 6 (96) For notational convenience, let us from now on suppress function evaluation, with evaluation assumed from the above. Equating coefficients of y1 gives the trivial equation (1 − ηλ1 )ψ1 = (1 − ηλ1 )ψ1 . Equating coefficients of y12 gives ⊗3 2 (1 − ηλ1 )ψ2 − ηψ12 ∇3 ℓ⊥ ν [e1 ] = (1 − ηλ1 ) ψ2 ,
(97)
from which it follows that −1 2 3 ⊥ ⊗3 ψ2 = λ−1 ψ1 ∇ ℓν [e1 ]. 1 (1 − ηλ1 )
(98)
Substituting this and equating coefficients of y13 gives −1 ⊗3 −1 3 ⊥ ⊗2 2 2 ∇ ℓ [e ] − ηψ13 eT1 ∇4 ℓ⊥ (1 − ηλ1 )ψ3 − 3ηψ13 eT1 ∇3 ℓ⊥ [e , e D h] + λ (1 − ηλ ) 1 ν 1 ν [e1 ] ν 1 2:q z1 1 (99) = 6ψ1 − 3η⟨∇M ψ1 , ∇M λ1 ⟩(1 − ηλ1 )ψ12 + ψ3 (1 − ηλ1 )3 ,
(100)
which gives ψ3 (1 − ηλ1 )(1 − (1 − ηλ1 )2 ) = ψ1 6 − 3η⟨∇M ψ1 , ∇M λ1 ⟩(1 − ηλ1 )ψ1 −1 2 T 3 ⊥ 2 −1 3 ⊥ ⊗3 2 + 3ηψ1 e1 ∇ ℓν [e1 , e2:q Dz1 h] + λ1 (1 − ηλ1 ) ∇ ℓν [e1 ] ⊗3 + ηψ12 eT1 ∇4 ℓ⊥ ν [e1 ] .
(101) (102) (103) (104)
Finally, substituting ⊗2 −1 Dz21 h = (λ1 I2:q − eT2:q ∇2 ℓ⊥ e2:q ∇3 ℓ⊥ ν e2:q ) ν [e1 ],
(105)
one obtains ψ3 (1 − ηλ1 )(1 − (1 − ηλ1 )2 ) (106) = ψ1 6 − 3η⟨∇M ψ1 , ∇M λ1 ⟩(1 − ηλ1 )ψ1 (107) −1 2 ⊥ −1 3 ⊥ −1 3 ⊥ ⊙2 + 3ηψ12 ∇3 ℓ⊥ ∇ ℓ2:q [e⊙2 ∇ ℓ1 [e1 ] (108) 1 (x) e1 , (λ1 I2:q − ∇ ℓ2:q ) 1 ] + λ1 (1 − ηλ1 ) 2 T 4 ⊥ ⊗3 + ηψ1 e1 ∇ ℓν [e1 ] . (109) One sees then that it suffices for ψ1 to solve the partial differential equation 1 4 ⊥ ⊙3 2 3 ⊥ ⊙2 ∇ ℓ [e ] ψ12 + , ⟨∇M ψ1 , ∇M λ1 ⟩ψ1 = (1 − ηλ1 )−1 ∇3 ℓ⊥ e , A∇ ℓ [e ] + 1 1 1 1 ν 1 3 η(1 − ηλ1 ) (110) 19
where −1 T −1 A := e2:q (λ1 I2:q − ∇2 ℓ⊥ e2:q + λ−1 e1 eT1 , 2:q ) 1 (1 − ηλ1 )
(111)
in which case one can take ψ3 (and all higher order terms) to be zero. Setting u := 12 ψ12 , it thus suffices to solve the PDE 1 4 ⊥ ⊙3 2 2 3 3 ⊥ ⊙2 ⟨∇M u, ∇M λ1 ⟩ = ∇ ℓ1 e1 , A∇ ℓν [e1 ] + ∇ ℓ1 [e1 ] u + . (112) 1 − ηλ1 3 η(1 − ηλ1 ) That this PDE admits a C 1 solution which is positive on Ve after shrinking if necessary is a consequence of Assumption 3.5 and Theorem C.4. Note in particular that along F , the left side of this PDE is zero so that the solution u = (1/2)ψ12 must satisfy −1 1 4 ⊥ ⊙3 ⊙2 ∇ ℓ [e u|F = − η ∇3 ℓ1 [e1 , A∇3 ℓ⊥ [e ]] + ] . (113) 1 1 ν 1 3 Now, setting ζη := (1/2)ηψ1 (η, ·)2 , one sees that this function restricts to F to yield −1 1 4 ⊥ ⊙3 ⊙2 ℓ [e ] ∇ = −αη−1 ζη = η − η ∇3 ℓ1 [e1 , A∇3 ℓ⊥ [e ]] + 1 1 ν 1 3
(114)
as claimed. Finally, we remove the O(|y1 |∥y2:q ∥) terms from the x and y1 update formulae of Proposition B.6 using the strong stable foliation associated to the normally hyperbolic manifold y2:q = 0 to obtain the final normal form. Theorem B.7. There is an open neighbourhood U4 of (2/λ1 |F , x̄, 0, 0) in R × M × R × Rq−1 and a C 1 change of coordinates Φ4 : U4 → U3 such that (Φ1 ◦ Φ2 ◦ Φ3 ◦ Φ4 )−1 ◦ GD ◦ (Φ1 ◦ Φ2 ◦ Φ3 ◦ Φ4 ) (η, x, y1 , y2:q ) (115) η x − ηψ1 (η,x)y12 ∇M λ1 (x) + O |y1 |3 dM (x, F )) . 2 = (116) (1 − ηλ1 (x))y1 + y13 + O y14 T 2 e2:q T1 (η, x)[y2:q ] + O |y1 |∥y2:q ∥, ∥y2:q ∥ g := (Φ1 ◦Φ2 ◦Φ3 )−1 ◦GD◦(Φ1 ◦Φ2 ◦Φ3 ) is normally hyperbolic Proof. Shrinking U3 if necessary, GD (in the sense of [27, Definition 1, p.3]) along the submanifold y2:q = 0 of U3 . Consequently, (cf. [27, Theorem 4.1(e)]), U3 is invariantly C 1 -foliated by strong-stable leaves W ss (η, x, y1 ) tangent to the y2:q -coordinate directions at any (η, x, y1 , 0) ∈ U3 . Invariance of the foliation here means that ss g g η,x,y (η, x, y1 )) GD(W (η, x, y1 )) ⊂ W ss (GD 1
(117)
for all (η, x, y1 , 0) ∈ U3 . Thus we may choose U4 as in the theorem statement and foliation coordinates Φ4 : U4 → U3 in which W ss (η, x, y1 ) = {y2:q = 0}. The invariance equation (117) then gives the result.
C
Singular PDE
In this section, we consider a singular partial differential equation of the form Xu = αu + β
(118)
on Rn+m , with X, α and β all C ∞ . The singularity of the PDE takes the following form. We assume there are coordinates (x, y) ∈ Rn × Rm and a C ∞ , positive-definite m × m matrix-valued function x 7→ A(x) such that X admits the asymptotic expansion X X ∼ Y1 + Xk + Yk , Y1 (x, y) = A(x)y · ∂y (119) k≥2
20
and with Xk , Yk being vector fields differentiating in the x and y directions respectively, whose coefficients are both C ∞ in x and polynomial of degree k in y. We also assume that Dα(x, 0) = Dβ(x, 0) = 0 for all x. Before proving that this PDE admits local C 1 solutions, we briefly review related literature. When n = 0 and m = 1, the equation is a classical “regular singular" ODE which can be solved by the classical Frobenius method, which posits a certain series expansion for a solution and recursively solves for its coefficients [19]. More recent work has identified similar series solutions when n = 0 and m = 1 in the complex domain [20, 46], which was followed by the proof of analogous series solutions when n = 0 and m > 1 in the complex domain [56]. In all of these cases, it is important to include logarithms in the series expansions for solutions to account for resonances, which are orders at which the linear equation defining the coefficients of the series do not admit unique solutions. Our setting is similar, in that resonances can occur; however, our setting is more complicated in the sense that for us, n > 0 in general, and the presence of resonances at any given order varies as a function of x. This prevent the straightforward use of polylogarithms in our setting if we want to retain regularity. The techniques we introduce to circumvent this obstacle are, to our knowledge, novel. The following lemma gives a “logarithm" which is naturally adapted to the problem, with which we augment a series expansion to account for the singularity in a manner similar to the isolated singularity case [56]. Lemma C.1. For any z0 = (x0 , y0 ) ∈ Rn × Rm , there is a neighbourhood U0 of z0 and, on U0 \ {y = 0}, a C ∞ solution w to the equation Xw ≡ 1. With µ+ and µ− being uniform upper and lower bounds on {spec(A(x)) : (x, 0) ∈ U0 }, there is a constant C > 0 such that any such w satisfies 1 1 log ∥y∥ − C ≤ w(x, y) ≤ log ∥y∥ + C µ+ µ−
(120)
for all (x, y) ∈ U0 \ {y = 0}. Proof. Local existence of C ∞ functions w defined outside of y = 0 such that Xw ≡ 1 follows from the regularity of X away from y = 0. To obtain the estimates, let U0 be a compact neighbourhood of z0 , and let µ+ , µ− be uniform upper and lower bounds on {spec(A(x)) : (x, 0) ∈ U0 } respectively. Letting r = ∥y∥, one has X(log r) = Y1 (log r) + O(r) =
⟨A(x)y, y⟩ + O(r) ⇒ µ+ + O(r) ≥ X(log r) ≥ µ− + O(r) ∥y∥2 (121)
uniformly over U0 as r → 0. Let Φt be the flow of X and, fixing ϵ > 0 sufficiently small, let Tϵ (x, y) be the first forward time such that ∥ΦTϵ (x,y) (x, y)Y ∥ = ϵ; since A takes values in the positive-definite matrices, r increases along this flow making Tϵ (x, y) well-defined for all r = ∥y∥ sufficiently small. Using (121), one obtains Z Tϵ (x,y) Tϵ (x, y) µ− + O(r) ≤ log(ϵ/r) = X(log r)(Φt (x, y)) dt ≤ Tϵ (x, y) µ+ + O(r) 0
(122) uniformly over U0 as r → 0, from which it follows that 1 1 log(ϵ/r) + O(r) ≥ Tϵ (x, y) ≥ log(ϵ/r) + O(r) µ− µ+
(123)
uniformly over U0 as r → 0. Now, fixing any solution w to Xw ≡ 1, one has w(x, y) = w ◦ ΦTϵ (x,y) (x, y) − Tϵ (x, y). Substituting (123) then gives the result. We will also be making use of certain particular solutions to nonsingular ODE. Lemma C.2. Let V be a finite-dimensional inner-product space, and let Rn ∋ x 7→ B(x) be a C ∞ field of invertible, self-adjoint linear operators on V . Let U ⊂ Rn be a compact neighbourhood, and let δ > 0 satisfy δ < inf x∈U σmin (B(x)). Then, if f : U × (−∞, 0] → V is C ∞ and there 21
exists C > 0 such that ∥f (x, t)∥, ∥Dx f (x, t)∥ ≤ Ceδ|t| uniformly over U × (−∞, 0], there is a C 1 particular solution vp : U × R → V to the differential equation ∂t v(x, t) = B(x)v(x, t) + f (x, t)
(124)
such that ∥vp (x, t)∥, ∥Dx vp (x, t)∥ ≤ C ′ eδ|t| for some C ′ > 0, uniformly over U × (−∞, 0]. Proof. Given x ∈ U , let P+ (x) and P− (x) be the positive and negative spectral projectors for the linear map B(x) : V → V . Since ∥f (x, t)∥ ≤ Ce−δs for all s ∈ (−∞, 0], the integrals defining Z t Z 0 vp (x, t) := exp(tB(x)) exp(−sB(x))P− (x)f (x, s) ds − exp(tB(x)) exp(−sB(x))P+ (x)f (x, s) ds −∞
t
(125) −δs
converge. The estimate ∥Dx f (x, t)∥ ≤ Ce converges, so that vp (x, t) is C 1 .
implies that the integral defining Dx vp (x, t) also
It is straightforwardly checked that vp is a solution of (124), and using the bound ∥f (x, t)∥ ≤ Ce−δs for all s ∈ (−∞, 0] it is also easily checked that ∥vp (x, t)∥ ≤ C ′ e−δs uniformly over U × (−∞, 0] for a sufficiently large constant C ′ . Lemmas C.1 and C.2 are used demonstrate the existence of approximate C 1 solutions to (118), from which it is straightforward to prove the existence of exact C 1 solutions using the classical variation of constants formula. Note that one could consider the variation of constants formula from the beginning, however since the points of interest are zeroes of the vector field X in (118), the “basepoint" limits of integration in the variation of constants formula must be taken to be −∞, at which point well-definedness of the integral must be called into question. In general, this indefinite integral converges only if the non-homogeneous term (i.e. β in (118)) is of sufficiently high order in y, whence the need to first subtract an approximate solution of sufficiently high order. The construction of such an approximate solution is a delicate task, so before diving into it we first remark on our proof technique and how it relates to prior literature. At a high level, the strategy we adopt for the construction of approximate solutions is classical: we consider an expansion of uK into a Taylor-like series and then recursively solve for the coefficients by plugging the series into (118). In this classical method, at each step k, the coefficients are determined by inverting a certain linear operator on the space of homogeneous polynomials of degree k in y. Unfortunately, in our case, this classical procedure is obstructed by the potential presence of resonances, namely points x where this linear operator has a nontrivial kernel and so cannot be inverted. This problem occurs also in prior literature on singular PDE [56], wherein the vector field under consideration vanishes only at a single point, and the resonances are dealt with via the introduction of poly-logarithms in the y variables. This method, too, fails in our setting since we consider a submanifold of zeroes, across which resonances vary with the submanifold parameter. We overcome this obstruction by expanding in terms which depend in a potentially non-polynomial fashion on the values of a solution w to Xw ≡ 1 which, as in Lemma C.1, grows logarithmically in y as y → 0. Lemma C.3. For any z0 = (x0 , 0) ∈ Rn × Rm , any natural number K ≥ 2 and any real number ∆ ∈ (0, 1), there is a neighbourhood U0∆ of z0 and a C 1 function uK : U0∆ → R such that XuK − αuK − β = O(∥y∥K+1−∆ )
(126)
uniformly over U0∆ as y → 0. Proof. Fix a compact neighbourhood U0 of z0 . For each k ∈ N, let Pk denote the vector space of polynomials in a vector-variable y which are homogeneous of degree k. This vector space carries the inner product X X X ⟨p, q⟩k := ν! pν qν , p[y ⊙k ] := pν y ν , q[y ⊙k ] := qν y ν , (127) |ν|=k
|ν|=k m
|ν|=k
P ν where ν denotes a multi-index (ν1 , . . . , νm ) ∈ N for which we define |ν| := := i νi , y ν1 νm y1 · · · ym and ν! := ν1 ! · · · νm !. Denote ei ∈ Nm for the “ith standard basis vector" multiindex consisting of zeros in all slots except the ith , whose value is 1. Then, with respect to this 22
P P ν+ei inner product, the linear operators Myi : Pk ∋ pν y ν 7→ ∈ Pk+1 and |ν|=k |ν|=k pν y P P ∂yi : Pk+1 ∋ |ν|=k+1 qν y ν 7→ |ν|=k+1 νi qν y ν−ei ∈ Pk are adjoints of one another, so that for each (x, 0) ∈ U0 the map Ak := (A(x)y) · ∂y : Pk → Pk is self-adjoint. For each (x, 0) ∈ U0 , we then denote Bk (x) := α0 IPk − Ak (x) : Pk → Pk , which is also self-adjoint, making Bk : x 7→ Bk (x) a C
∞
(128)
field of self-adjoint endomorphisms of Pk .
For all k ≥ 2, let Nk (x0 ) denote the kernel of Bk (x0 ) and let Rk (x0 ) denote its range. Since x 7→ Bk (x) is C ∞ and each Bk (x) is self-adjoint, for any δk , ϵk > 0, there exists a neighbourhood V0δk ,ϵk of x0 in Rn such that Nk (x0 ) and Rk (x0 ) extend uniquely to C ∞ , Bk -invariant, complementary subbundles Nk , Rk → V0δk ,ϵk of the trivial bundle V0δk ,ϵk × Pk , with sup σmax (Bk (x)|Nk (x) ) < δk , inf σmin Bk (x)|Rk (x) > σmin (Bk (x0 )|Rk (x0 ) − ϵk . δ ,ϵk
x∈V0 k
δ ,ϵk
x∈V0 k
(129) Let us in particular choose 1 δk := min 4(K − 1)
1 ϵk := σmin Bk (x0 )|Rk (x0 ) , 4
(
1 min σmin Bk (x0 )|Rk (x0 ) , µ− ∆ . k=2,...,K 2 (130)
TK We then denote U0∆ := U0 ∩ ( k=2 (V0δk ,ϵk × Rm )) and set V0∆ to be the projection of U0∆ onto Rn . Now, we propose as an ansatz that uK (x, y) :=
K X
vk (w(x, y), x)[y ⊙k ],
(131)
k=0
with vk : (−∞, 0] × V0∆ → Pk a mapping into degree k homogeneous polynomials Pk in y. Our goal is to demonstrate that these vk can be chosen to be C 1 in the w and x variables, with growth Pk
vk (w, x) = O(e
l=2 4δl |w|
Pk
),
Dx vk (w, x) = O(e
l=2 4δk |w|
)
(132)
in the norm on Pk uniformly over x ∈ V0∆ as y → 0 and |w| → ∞, and such that XuK = αuK + β holds on terms homogeneous of all degrees up to K in y. Substituting (131) into (118) and using the fact that Xw ≡ 1, this latter requirement amounts to requiring that ∂w vk − Bk vk = Fk ,
∀k = 0, . . . , K,
(133)
where, for any k ∈ N, Fk = βk +
l X l=1
αl vk−l −
k X
Xl (vl−k ) −
l=2
k+1 X
Yl (vl−k+1 ).
(134)
l=2
Should the equations (133) admit solutions with the growth estimates (132), then since w(x, y) = O(log(∥y∥1/µ− )) as y → 0 by Lemma C.1 and 4δk ≤ µ− ∆/(K − 1) by definition, one would then have X PK 1/µ− ) Fk = O(∥y∥K+1− k=2 4δk log(∥y∥ ) = O(∥y∥K+1−∆ ) (135) XuK − αuK − β ∼ − k=K+1
as desired. We thus prove that the equations (133) can be solved recursively to obtain vk of the desired growth and regularity. The k = 0, 1 cases can be solved without difficulty. For k = 0, the equation reduces to −α0 v0 = β0 ,
(136)
which may be solved simply by setting v0 ≡ −β0 /α0 . For k = 1, one has the equation (∂w − B1 )v1 = β1 + α1 = 0 23
(137)
by the hypothesis that Dα(x, 0) = Dβ(x, 0) = 0 for all x, which may be solved by setting v1 ≡ 0. Both v0 and v1 are manifestly C 1 and trivially satisfy the desired growth conditions (132). Now suppose as an inductive hypothesis that for all l = 0, . . . , k − 1, one has vl (w, x, y) being C 1 Pl in w and x, with the growth estimate vl (w, x) = O(e l′ =2 2δl′ |w| ). We must then solve (133) for vk . The subbundles Nk , Rk of V0∆ × Pk extend trivially to subbundles of (−∞, 0] × V0∆ × Pk over (−∞, 0] × V0∆ and as such are invariant under the operator ∂w − Bk ; so we are reduced to solving the equations (∂w − Bk )vkN = FkN ,
(∂w − Bk )vkR = FkR ,
(138)
where the superscript N (respectively, R) denotes the projectionPonto Nk (resp. Rk ). By the k−1 inductive hypothesis, we have ∥Fk (w, x)∥, ∥Dx Fk (w, x)∥ = O(e l=2 4δl |w| ) with respect to the P k−1 k−2 1 norm on Pk uniformly over V0∆ ; consequently, since l=2 4δl < K−1 σmin Bk (x0 )|Rk (x0 ) < 2 inf x∈V0∆ σmin Bk (x)|Rk (x) , Lemma C.2 applies to give a C 1 solution vkR to (∂w − Bk )vkR = FkR Pk−1
with growth estimate ∥vkR (w, x)∥, ∥Dx vkR (x, w)∥ = O(e l=2 4δl |w| ) the same as that of Fk as |w| → ∞. On the other hand the formula Z 0 N vk (w, x) = − exp(wBk (x)) exp(−sBk (x))FkN (s, x) ds (139) w 1
defines a C solution to (∂w − Bk )vkN = FkN ; moreover, this solution admits growth estimates Pk ∥vkN (w, x)∥, ∥Dx vkN (w, x)∥ = O(e l=2 4δl |w| ) as |w| → ∞ in Pk as can be seen using the facts that supx∈V0∆ σmax (Bk (x)|Nk (x) ) ≤ δk by construction, and ∥Fk (w, x)∥, ∥Dx Fk (w, x)∥ = Pk l=2 4δl |w| O(e
) as follows from the inductive hypothesis. This completes the proof.
Finally, we can prove existence of C 1 solutions to (118). Theorem C.4. Any point (x0 , 0) ∈ Rn × Rm admits a neighbourhood U and a C 1 function u : U → R solving (118). Proof. Set λ0,min := λmin (A(x0 )) and λ0,max := λmax (A(x0 )), and given (x, y) near (x0 , 0) denote (xt , yt ) := Φt (x, y) the flow of X applied to (x, y). Fix 0 < ϵ < λ0,min and a neighbourhood U of (x0 , 0) which are each sufficiently small that X d 2 ∥yt ∥ = 2 Ym (xt , yt ), yt ≥ 2(λ0,min − ϵ)∥yt ∥2 , (140) dt m≥1
sup |α(x, y)| < |α0 | + ϵ,
(141)
(x,y)∈U
sup ∥Dα(x, y)∥ ≤ ϵ
(142)
(x,y)∈U
and sup ∥DX(x, y)∥ ≤ λ0,max + ϵ.
(143)
(x,y)∈U
Fix ∆ ∈ (0, 1) and choose K ∈ N sufficiently large that (K − ∆)(λ0,min − ϵ) − (λ0,max + α0 + 2ϵ) > 0.
(144)
Taking U to be smaller if necessary, Lemma C.3 applies to give a C 1 approximate solution uK to (118) such that γ := αuK + β − XuK = O(∥y∥K+1−∆ ) uniformly over U as y → 0. We seek a C 1 function u e such that uK + u e is a solution to (118), which is equivalent to u e satisfying Xu e = αe u + γ.
(145)
We solve for this u e using the method of characteristics. Specifically, denoting (xt , yt ) := Φt (x, y) for the flow of X applied to a point (x, y) and abusing notation to write α(t, x, y) := α(Φt (x, y)), 24
γ(t, x, y) := γ(Φt (x, y)) and u e(t, x, y) := u e(Φt (x, y)), along this flow (145) becomes the ordinary differential equation ∂t u e(t, x, y) = α(t, x, y)e u(t, x, y) + γ(t, x, y). (146) By the variation of constants formula, this ordinary differential equation admits a general solution of the form Z t Z s Z t u e(t, x, y) = exp α(s, x, y)ds u e(t0 , x, y) + exp − α(r, x, y) dr γ(s, x, y) ds . t0
t0
t0
(147) Since we seek a solution u e which vanishes at y = 0, and since Φt0 (x, y) converges to y = 0 as t0 → −∞, we substitute t0 = −∞ and u e(−∞, x, y) = 0 into the above to obtain the formula Z t Z t u e(t, x, y) := exp α(r, x, y) dr γ(s, x, y) ds (148) −∞
s
for our desired particular solution. We must now show that this integral converges, and that u e(x, y) := u e(0, x, y) defines a C 1 function. To see that the integral in (148) converges, apply Grönwall’s inequality to (140) to give ∥yt ∥ ≤ e(λ0,min −ϵ)t ∥y∥
(149) K+1−∆
for all t ≤ 0. Combining this with (141) and the fact that γ(x, y) = O(∥y∥ ), we may estimate the integrand of (148) by Z t exp |α(r, x, y)| dr |γ(s, x, y)| ≤ e(α0 +ϵ)t es (K+1−∆)(λ0,min −ϵ)−(α0 +ϵ) (150) s
for all s ≤ t ≤ 0 and all (x, y) ∈ U . By (144), however, es (K+1−∆)(λ0,min −ϵ)−(α0 +ϵ) goes to zero exponentially fast as s → −∞ so that the integral (148) converges, and u e is well-defined. To see that u e(x, y) := u e(0, x, y) is C 1 , note that De u(x, y) is given formally by the integral Z 0 Z 0 Z 0 Dα|Φr (x,y) DΦr (x, y) dr exp α(r, x, y) dr γ(s, x, y) −∞
s
(151)
s
Z 0 + exp
α(r, x, y) dr Dγ|DΦs (x,y) DΦs (x, y) ds,
(152)
s
assuming that this integral converges. Concerning the integrand of (151), applying (142), (143) and Grönwall’s inequality, there is C > 0 such that ∥Dα|Φr (x,y) DΦr (x, y)∥ ≤ ϵ∥DΦr (x, y)∥ ≤ Cϵe−r(λmax,0 +ϵ) ,
(153)
implying that Z 0 Z 0 ∥Dα|DΦr (x,y) DΦr (x, y)∥ dr exp |α(r, x, y)|dr = O(e−s(λmax,0 +α0 +2ϵ) ) (154) s
s
uniformly over U as s → −∞. Similarly, applying Dγ(t, x, y) = O(et(K−∆)(λ0,min −ϵ) ), (143) and Grönwall’s inequality gives ∥Dγ|Φs (x,y) DΦs (x, y)∥ = O es (K−∆)(λ0,min −ϵ)+(λ0,max +ϵ) (155) −∞, so that finally the integrand of (151) is O e as s → −∞; invoking (144) once more then implies that the integral (151) converges, so that u e is C 1 . uniformly over U
as s
→
s (K−∆)(λ0,min −ϵ)−(λ0,max +α0 +2ϵ)
D
Convergence theorems
In this section, we prove the convergence theorems stated in the main body of the paper. All three theorems require that one can choose arbitrarily small invariant neighbourhoods of any point in F . This is taken up in Subsection D.1. Following this, we present our proofs of Theorems 5.1, 5.2 and 5.3 in Subsections D.2, D.3 and D.4 respectively. 25
D.1
Existence of invariant neighbourhoods
The following lemma will be key to all of the convergence theorems. The lemma says that we can always work in an invariant neighbourhood in which the decay of the y2:q variables is faster than the decay of the x or y1 variables. Lemma D.1. For any x̄ ∈ F , let V ⊂ R × Rp be an open neighbourhood of (2/λ1 |F , x̄) in which the coordinates (η, x, y) of Theorem 4.1 are defined and for which there is C > 0 such that GDy2:q (η, x, y1 , y2:q ) = (Iq−1 − ηΛ2:q (x))y2:q + error(x, y1 , y2:q )
(156)
error(x, y1 , y2:q ) ≤ C(|y1 | + ∥y2:q ∥)∥y2:q ∥
(157)
where
uniformly over V . Then there is ∆ > 0 such that for all ρ > 0 sufficiently small, the sets Iρ := (2/λ1 |F − ρ2 , 2/λ1 |F + ρ2 )
(158)
and Uρ,∆ := {(x, y) : (λ1 (x) − λ1 |F ) + ∥y2:q ∥2 ≤ ρ2 ,
|y1 | ≤ (2/λ1 |F + λ1 |F + 1)1/2 ρ}
(159)
satisfy the following. 1. The set Vρ,∆ := Iρ × Uρ,∆ ⊂ V is invariant under GD. 2. For any (η, x, y) ∈ Vρ,∆ one has ∥Iq−1 − ηΛ2:q (x)∥ + C(|y1 | + ∥y2:q ∥) − min{|1 − ηλ1 (x)|, 1} ≤ −∆.
(160)
Proof. Consider the continuous function β : V → R defined by β(η, x, y) := ∥I − ηΛ2:q (x)∥ + C |y1 | + ∥y2:q ∥ − min{|1 − ηλ1 (x)|, 1}.
(161)
Since x̄ ∈ F one has ∥Λ2:q (x̄)∥ < λ1 |F , and since Λ2:q (x̄) is moreover positive-definite there is ∆ > 0 such that β(2/λ1 |F , x̄, 0) = −2∆.
(162)
′
Thus there is a neighbourhood V ⊂ V of (2/λ1 |F , x̄) on which β|V ′ ≤ −∆. Then for any ρ > 0 sufficiently small, the set Vρ,∆ as defined in the statement is contained in V ′ , hence in V , and satisfies β|Vρ,∆ ≤ −∆. It remains to show that Vρ,∆ is invariant under GD for ρ sufficiently small. For notational convenience, denote L := λ1 − λ1 |F
(163)
Q(x, y2:q ) := L(x) + ∥y2:q ∥2
(164)
α := (2/λ1 |F + λ1 |F + 1)1/2
(165)
and
so that Uρ,∆ = {(x, y) : Q(x, y2:q ) ≤ ρ2 , |y1 | ≤ αρ}. We first show that (η, x, y) ∈ Vρ,∆ implies that Q(GDx (η, x, y), GDy2:q (η, x, y)) ≤ ρ2 . Since λ1 is √ Morse-Bott along F it satisfies ∥∇M λ1 ∥ = Θ( L) near F . Then a covariant Taylor expansion of λ1 yields constants c1 , c2 > 0 such that L(GDx (η, x, y)) ≤ L(x) − c1 y12 L(x) + c2 |y1 |3 L(x)
(166)
for all (η, x, y) ∈ Vρ,∆ . For any (η, x, y) ∈ Vρ,∆ , however, one has |y1 | ≤ αρ; thus for ρ sufficiently small then one has L(GDx (η, x, y)) ≤ L(x) 26
(167)
for all (η, x, y) ∈ Iρ × Uρ,∆ . One then sees that Q(GDx (η, x, y), GDy2:q (η, x, y)) ≤ L(x) + (1 − ∆)2 ∥y2:q ∥2 ≤ Q(x, y2:q ) ≤ ρ2
(168)
for all sufficiently small ρ > 0 and all (η, x, y) ∈ Vρ,∆ . We now turn to demonstrating that (η, x, y) ∈ Vρ,∆ implies that |GDy1 (η, x, y)| ≤ αρ for all ρ sufficiently small. Since (η, x, y) ∈ Vρ,∆ implies that |y1 | ≤ αρ, for all ρ sufficiently small one has |GDy1 (η, x, y)| ≤ |y1 | 1 + (ηλ1 (x) − 2) − y12 + (1/2)ρ2 (169) for all (η, x, y) ∈ Vρ,∆ and all ρ sufficiently small. On the other hand, one has (ηλ1 (x) − 2) ≤ (2/λ1 |F + ρ2 )(λ1 |F + ρ2 ) − 2 ≤ ρ2 (2/λ1 |F + λ1 |F + (1/2))
(170)
for all (η, x, y) ∈ Vρ,∆ and all ρ sufficiently small. Thus |GDy1 (η, x, y)| ≤ |y1 | 1 − y12 + α2 ρ2 . (171) Now, the function ϕ(t) := t 1 − t2 + α2 ρ2 is increasing on [0, αρ] for all ρ sufficiently small, hence its maximum value on this domain is ϕ(αρ) = αρ(1 − α2 ρ2 + α2 ρ2 ) = αρ.
(172)
Since ϕ(|y1 |) upper-bounds |GDy1 (η, x, y)| for any (η, x, y) ∈ Vρ,∆ , it follows that (η, x, y) ∈ Vρ,∆ implies GDy1 (η, x, y) ∈ Vρ,∆ . This completes the proof.
D.2
Subcritical regime
In this section, we prove Theorem 5.1. With Lemma D.1 in hand, the result follows from a similar argument to that used in the proof of [39, Theorem D.4]. We thus first recall the following lemmas from [39], which will be used without change in this paper. We refer to [39] for their proofs. Lemma D.2. [39, Lemma D.2] For α ∈ R, define fα : R → R by fα (z) := −(1 + α)z + z 3 + O(z 4 ).
(173)
For α0 , α1 ∈ R, consider the composite fα1 α0 := fα1 ◦ fα0 . Then for all γ > 0 sufficiently small and all α0 , α1 ∈ [0, γ]: √ √ 1. fα1 α0 is monotonically increasing on [−2 γ, 2 γ]. 2. fα1 α0 admits the sole fixed points 0, r α0 + α1 z− = − + O(α0 + α1 ), 2 √ √ in the interval [−2 γ, 2 γ].
r z+ =
α0 + α 1 + O(α0 + α1 ) 2
(174)
Lemma D.3. [39, Lemma D.3] Let {λt }t∈N be a monotonically decreasing sequence of numbers. Then for all η > 2/λ0 sufficiently small and all z0 ∈ R sufficiently close to zero, the iterates zt+1 := (1 − ηλt )zt + zt3 + O(zt4 )
(175)
satisfy |z0 | p
1 + 3z02 t
p ≤ |zt | ≤ 2 ηλ0 − 2
(176)
for all t ∈ N such that ηλt ≥ 2 Our next lemma generalises the descent lemma [39, Lemma D.1] from the case where λ1 is geodesically strongly convex and F is a single point, to the more general case where λ1 is Morse-Bott along the manifold F . 27
Lemma D.4 (Descent lemma for x-update on Vρ,∆ ). Let Vρ,∆ be as in Lemma D.1. Then there is C > 0 such that λ1 (GDx (η, x, y)) − λ1 |F ≤ (1 − Cy12 ) λ1 (x) − λ1 |F (177) for all (η, x, y) ∈ Vρ,∆ . Proof. That λ1 is Morse-Bott implies that ∥∇M λ1 (x)∥2 = Θ(λ1 (x) − λ1 |F ) = Θ(dM (x, F )2 ) as x → F . There is then δ(y1 , x) = O(|y1 |3 dM (x, F )) ∈ Tx M such GDx (η, x, y) = expx − ζ(η, x)y12 ∇M λ1 (x) + δ(y1 , x) . (178) There is then a constant C > 0 such that, shrinking ρ if necessary and using a covariant Taylor expansion for λ1 around x, one has λ1 (GDx (η, x, y)) − λ1 |F = λ1 (x) − ζ(η, x)y12 ∥∇M λ1 (x)∥2 + O(|y1 |3 dM (x, F ))
(179)
≤ (1 − Cy12 )(λ1 (x) − λ1 |F )
(180)
for all (η, x, y) ∈ Vρ . Finally, we can prove our subcritical convergence theorem, which follows from a similar argument to that of [39, Theorem D.4]. Theorem D.5. Let Vρ,∆ be an invariant neighbourhood of x̄ ∈ F as in Lemma D.1. Then, shrinking ρ further if necessary, for any (η, x, y) ∈ Vρ,∆ , with η < 2/λ1 |F , there is γ −2 λ1 (x) − λ1 |F T = O y1 (181) 2/η − λ1 |F such that η < 2/λ1 (xt ) for all t ≥ T , following which, setting β := 1 − (2 − ηλ1 (xT )) < 1 the iterates (xt , yt ) converge with rate O(β t ) to a suboptimally flat global minimum (x∞ , 0) for which 2 λ1 (x∞ ) − λ1 |F ≥ exp − O(y1,T (1 − β 2 )−1 ) (λ1 (xT ) − λ1 |F ). (182) Proof. For notational convenience, denote L(x) := λ1 (x) − λ1 |F ,
Lt := L(xt ).
(183)
By Lemma D.1, after shrinking ρ if necessary, the iterates remain in Vρ,∆ and ∥y2:q,t ∥ ≤ (1 − ∆)t ∥y2:q ∥.
(184)
Thus the y2:q variables decay exponentially and, in particular, do not affect the estimates below. We now prove that ηλ(xt ) < 2 in finite time. If η < 2/λ1 (x), there is nothing to prove, so suppose that ηλ1 (x) ≥ 2. By Lemma D.4, there is c0 > 0 such that 2 Lt+1 ≤ (1 − c0 y1,t )Lt
(185)
for all t, so that {λ1 (xt )}t∈N is monotonically decreasing. Hence Lemma D.3 applies to the y1 iterates, yielding |y1 | |y1,t | ≥ p 1 + 3y12 t for all t such that ηλ1 (xt ) ≥ 2. Therefore, as long as ηλ1 (xt ) ≥ 2, c0 y12 Lt+1 ≤ 1 − Lt . 1 + 3y12 t
(186)
(187)
Taking logarithms, using log(1 − z) ≤ −z, and summing gives t−1 X
y12 1 + 3y12 s s=0
(188)
≤ −c1 log(1 + 3y12 t)
(189)
log Lt − log L0 ≤ −c0
28
for some c1 > 0. Thus Lt ≤ L0 (1 + 3y12 t)−c1 .
(190)
ϵη := 2/η − λ1 |F
(191)
Since η < 2/λ1 |F , the quantity is positive. Consequently, if t ≥ Cy1−2
L0 ϵη
1/c1 (192)
with C > 0 sufficiently large, then Lt < ϵη , equivalently η < 2/λ1 (xt ). Hence, setting γ := 1/c1 , there is γ −2 λ1 (x) − λ1 |F T = O y1 (193) 2/η − λ1 |F such that η < 2/λ1 (xT ). Since λ1 (xt ) is monotonically decreasing, it follows that η < 2/λ1 (xt ) for all t ≥ T . We now prove convergence after time T . Since ηλ1 (xt ) < 2 for all t ≥ T , the y1 update satisfies 2 3 |y1,t+1 | = |y1,t | 1 − (2 − ηλ1 (xt )) − y1,t + O(y1,t ).
(194)
Shrinking ρ if necessary and using the monotonicity of λ1 (xt ), we obtain |y1,t+1 | ≤ β|y1,t |,
β := 1 − (2 − ηλ1 (xT )) < 1,
(195)
for all t ≥ T . Thus y1,t = O(β t−T ), while Lemma D.1 gives ∥y2:q,t ∥ = O((1 − ∆)t ). The x update has size 2 dM (xt+1 , xt ) = O(y1,t ∥∇M λ1 (xt )∥) + O(|y1,t |3 dM (xt , F )) = O(β 2(t−T ) ),
(196)
for all t ≥ T ; hence xt converges to some x∞ ∈ M . It remains to prove the claimed suboptimal flatness bound. By the Morse–Bott condition, there is C ′ > 0 such that ∥∇M λ1 (x)∥2 ≤ C ′ (λ1 (x) − λ1 |F )
(197)
throughout Vρ,∆ . Using the normal form for the x update and a covariant Taylor expansion from below gives, for all t ≥ T , 2 Lt+1 ≥ Lt − C ′ y1,t ∥∇M λ1 (xt )∥2 + O(|y1,t |3 Lt ) 2 ≥ (1 − Cy1,t )Lt ,
(198) (199)
after shrinking ρ once more if necessary. Since |y1,t | ≤ |y1,T |β t−T for t ≥ T , it follows that Lt ≥ LT
t−1 Y
2 1 − C ′ y1,T β 2(s−T ) .
(200)
s=T
Taking Vρ,∆ sufficiently small, the factors in the product are positive and log(1 − z) ≥ −2z applies. Therefore t−1 t−1 Y X ′ 2 2(s−T ) ′ 2 log 1 − C y1,T β ≥ −2C y1,T β 2(s−T ) (201) s=T
s=T 2 y1,T ≥ −2C ′ . 1 − β2
(202)
Letting t → ∞ yields λ1 (x∞ ) − λ1 |F ≥ exp
2 y1,T −O 1 − β2
as claimed. 29
λ1 (xT ) − λ1 |F ,
(203)
D.3
Critical regime
In this subsection, we prove convergence in the critical regime, η = 2/λ1 |F , as in Theorem 5.2. As we will see in Theorem D.13, the result can be reduced to a system of the following form. Fix real numbers 0 < a < c, b, b′ > 0, and β > α > a and positive natural numbers dz , dv , du , q. Let A : Rdz → Rdv ×dv be a C 1 , positive-definite matrix valued function satisfying the uniform bounds αIdv ⪯ A(z) ⪯ βIdv ,
∀z ∈ Rdz ,
(204)
and let B : Rdz × Rdv × Rdu → R(q−1)×(q−1) be a C 1 , symmetric matrix-valued function satisfying the uniform bound ∥B(z, v, u)∥ ≤ 1 − ∆
(205)
for some fixed ∆ > 0. Consider then a C 1 map T : Rdz × Rdv × Rdu × Rq → Rdz × Rdv × Rdu × Rq for which Tz (z, v, u, y) = z + Rz (z, v, u, y),
(206)
Tv (z, v, u, y) = (Idv − 2y12 A(z))v + Rv (z, v, u, y),
(207)
Tu (z, v, u, y) = (1 − 2ay12 )u + Ru (z, v, u, y),
(208)
Ty1 (z, v, u, y) = y1 (1 + 2b∥u∥2 + 2b′ v T A(z)v − 2cy12 ) + Ry1 (z, v, u, y),
(209)
Ty2:q (z, v, u, y) = B(z, v, u)2 y2:q + Ry2:q (z, v, u, y),
(210)
where Rz , Rv , Ru , Ry1 and Ry2:q are C 1 , with Rz (z, v, u, y), Rv (z, v, u, y) = O(y13 ∥v∥, y12 ∥v∥(∥v∥ + ∥u∥)),
(211)
Ru (z, v, u, y) = O(y13 (∥u∥ + ∥v∥), y12 (∥u∥ + ∥v∥)2 ),
(212)
Ry1 (z, v, u, y) = O(y14 , y1 (∥u∥ + ∥v∥)3 ),
(213)
Ry2:q (z, v, u, y) = O(y1 ∥y2:q ∥, ∥y2:q ∥2 , y12 (∥u∥ + ∥v∥)∥y2:q ∥).
(214)
and
Furthermore, we assume that Rz , Rv , Ru , Ry1 are independent of y2:q and, letting W := {v = 0, y2:q = 0}, we assume that Rz |W is zero, and that Ru |W and Ry1 |W are independent of z. Finally, we assume that for any z̄ ∈ Rdz and any sufficiently small ρ > 0, there is an open neighbourhood Vρ of (z̄, 0, 0, 0) of diameter at most ρ which is invariant under T . We will denote Wρ := W ∩ Vρ . Fix any sufficiently small ρ > 0, and given (z, v, u, y) ∈ Vρ denote by (zt , vt , ut , yt ) the tth iterate of (z, v, u, y) under T . We will prove that, subject to Conjecture D.7 below and shrinking ρ if necessary, (1) these iterates converge to a neighbourhood of an invariant submanifold Wϕ ⊂ W in finite time and (2) once inside that neighbourhood, the iterates converge to some (z ′ , 0, 0, 0) ∈ Wρ with rate Θ(t−1 ). In preparation for (1), we first demonstrate the existence of the claimed invariant submanifold Wϕ ⊂ W . Set r b κ := . (215) c−a Lemma D.6. For any (z, v, u, y) ∈ Vρ , shrinking ρ if necessary, over any convex open cone U ⊂ Rdu containing u, with 0 ̸∈ U being the apex of the cone, there is a Lipschitz function ϕ : U → R for which the following hold. 1. For any ϵ > 0, there is δ > 0 such that Lip(ϕ|{u∈U :∥u∥<δ} ) ≤ κ + ϵ. 30
2. The graph Wϕ := {(z ′ , 0, u, ϕ(u), 0) : u ∈ U, z ′ near z} ⊂ W is invariant under T . Proof. We will apply [7, Theorem 3.1]. This requires the coordinate transformation y1 = κ∥u∥ + ye1 .
(216)
With respect to the new coordinates (z, v, u, ye1 , y2:q ), denoting ε := ∥u∥ + ∥v∥ + ye1 for notational ease, the map T is given to leading order by Tz (z, u, v, ye1 , y2:q ) = z + O(∥v∥ε3 )
(217)
Tv (z, v, u, ye1 , y2:q ) = v − 2(κ∥u∥ + ye1 )2 A(z)v + O(∥v∥ε3 ),
(218)
Tu (z, v, u, ye1 , y2:q ) = u − 2a(κ∥u∥ + ye1 )2 u + O(ε4 ),
(219)
Tye1 (z, v, u, ye1 , y2:q ) = ye1 − 2(2c − a)κ∥u∥2 − 2(3c − a)κ∥u∥e y12 − 2ce y13 + 2b′ (κ∥u∥ + ye1 )v T A(z)v + O(ε4 ), (220) Ty2:q (z, v, u, ye1 , y2:q ) = B(z, v, u)2 y2:q + O(ε∥y2:q ∥, ∥y2:q ∥2 ).
(221)
Observe that T is C 1 in these coordinates outside of u = 0. Now, fix z and recall that the slice Wz := {(z, 0, u, ye1 , 0) ∈ W } is invariant by the assumptions on T . Then for any (z, 0, u, ye1 , 0) ∈ Wz , the hypotheses of [7, Theorem 3.1] hold over any convex open cone U ∋ u which has 0 ̸∈ U as its apex; thus over any such neighbourhood there is a Lipschitz function ϕ′ : U → R such that the graph {(z, 0, u, ϕ′ (u), 0) : u ∈ U }
(222)
of ϕ′ is invariant under T |Wz , and by [7, Remark 3.16] this ϕ′ is differentiable at zero with derivative equal to zero. Since T |Wz does not depend on z, this ϕ′ extends trivially to give a function ϕ′ (z, u) := ϕ′ (u) with the same properties defined on {(z, u) : (z, 0, u, 0, 0) ∈ Wρ }. Finally, converting back to the original coordinate y1 gives ϕ(z, u) := ϕ′ (z, u) + κ∥u∥ = ϕ′ (u) + κ∥u∥ which completes the proof. So far as we can determine, the invariant manifold Wϕ ⊂ W is not, by itself, sufficient to prove the desired convergence theorem. The theorem seems also to require the following conjecture, which is a parabolic analogue of the strong stable foliation theorem for normally hyperbolic invariant manifolds [27, Theorem 4.1(e)]. Conjecture D.7. For ρ sufficiently small, the invariant set Vρ ∩ {y2:q = 0} is invariantly Lipschitzfoliated by leaves parametrised by the points (z, 0, u, y1 , 0) ∈ Wρ , and tangent at any such point to the v-axes. Although we cannot yet prove this conjecture, we believe it to be reasonable by the assumption that α > a and that Rz is order four. These assumptions imply that the “weak contraction" of the system (given by the terms of up to cubic order in Tz , Tv , Tu ) is stronger in the v-direction than in the base (z, u, y1 ) directions. In the normally hyperbolic case, this stronger contraction in the transverse direction is sufficient to guarantee an invariant foliation of the above form. To our knowledge, an analogous result in the parabolic setting of Conjecture D.7 has not yet been explored. The conjecture enables the following coordinate transformation. Lemma D.8. If Conjecture D.7 holds, then there is a bi-Lipschitz change of coordinates on Wρ with respect to which T takes the form Tz (z, v, u, y) = z
(223)
Tv (z, v, u, y) = (Idv − 2y12 A(z)v) + Rv (z, v, u, y),
(224)
Tu (z, v, u, y) = (1 − 2ay12 )u + Ru (u, y1 ),
(225)
Ty1 (z, v, u, y) = y1 (1 + 2b∥u∥2 − 2cy12 ) + Ry1 (u, y1 ),
(226)
31
Ty2:q (z, v, u, y) = B(z, v, u)2 y2:q + Ry2:q (z, v, u, y),
(227)
Rv (z, v, u, y) = O(y13 ∥v∥, y12 ∥v∥(∥u∥ + ∥v∥)),
(228)
Ru (u, y1 ) = O(y13 ∥u∥, y12 ∥u∥2 ),
(229)
Ry1 (u, y1 ) = O(y14 , y1 ∥u∥3 )
(230)
Ry2:q (z, v, u, y) = O(y1 ∥y2:q ∥, ∥y2:q ∥2 , y12 (∥u∥ + ∥v∥)∥y2:q ∥)
(231)
where
and as u, v, y → 0. Proof. Simply change the coordinates (z, u, y1 ) for the base Vρ ∩ {y2:q = 0} such that the leaf of the invariant foliation of Conjecture D.7 passing through (z, 0, u, y1 , 0) is given by L(z,0,u,y1 ,0) = {(z, v, u, y1 , 0) : v near zero }. Since this foliation is Lipschitz, this coordinate change is bi-Lipschitz. Since this foliation is invariant, one has T (L(z,0,u,y1 ,0) ) ⊂ LT (z,0,u,y1 ,0) , (232) from which the claimed formulae follow. Taking Conjecture D.7 as a hypothesis, we now prove our convergence theorem working in the coordinates supplied by Lemma D.8. Consider now the iterates (zt , vt , ut , yt ) of T starting from some point (z, v, u, y) ∈ Vρ for some small ρ > 0. Our next lemma gives rates of decay of ∥vt ∥ and ∥y2:q,t ∥ to zero, guaranteeing relatively rapid convergence to the invariant manifold W . Following this, we will prove convergence within W to the invariant manifold Wϕ , from which the result will follow. Lemma D.9. For any 0 < ϵ < α − a and any ρ sufficiently small, the iterates (zt , vt , ut , y1 ) starting from any point (z, v, u, y) ∈ Vρ satisfy ∥vt+1 ∥ ∥vt ∥ 2 ≤ (1 − 2(α − a − ϵ)y1,t ) , ∥y2:q,t ∥ ≤ (1 − ∆)t ∥y2:q ∥ (233) ∥ut+1 ∥ ∥ut ∥ for any t ∈ N. Proof. Since ∥u∥, ∥v∥, |y1 | ≤ ρ, one has ∥Ty2:q (z, v, u, y)∥ ≤ (1 − 2∆ + ∆2 + O(ρ))∥y2:q ∥, so taking ρ sufficiently small gives the claimed y2:q estimate. For the v estimate, one has 2 2 (1 − 2αy1,t + O(ρy1,t ))∥vt ∥ ∥vt+1 ∥ ≤ 2 2 ∥ut+1 ∥ (1 − 2ay1,t + O(ρy1,t ))∥ut ∥
∥vt ∥ . ∥ut ∥ Thus, fixing any 0 < ϵ < α − a, taking ρ sufficiently small concludes the proof. 2 ≤ (1 − 2(α − a − O(ρ))y1,t )
(234)
(235) (236)
We now prove convergence in the (u, y1 ) variables, subject to the assumption that Conjecture D.7 is true. This convergence is a consequence of the following lemma which proves attraction to the invariant graph of Lemma D.6. Lemma D.10. For any ρ > 0 sufficiently small and any (z, v, u, y) ∈ Vρ with u ̸= 0, y1 ̸= 0, fix a convex open neighbourhood U ⊂ Rdu of u, containing zero in its boundary, and a corresponding Lipschitz function ϕ : U → R with invariant graph as in Lemma D.6. Define e y1 ) := Φ(u, y1 ) , Φ(u, y1 ) := y1 − ϕ(u), Φ(u, u ∈ dom(ϕ). (237) ∥u∥ Then, assuming Conjecture D.7, there is τ = O(∥u∥−2 ) (238) √ √ e t , y1,t )| ≤ ( 2 − 1)κ/(2 2), and such that for all t ≥ τ one has |Φ(u 2 e ◦ Tu,y (ut , y1,t )| ≤ (1 − (c − a)y1,t e t , y1,t )|. |Φ )|Φ(u 1
32
(239)
√ e assuming that |Φ(u, e y1 )| ≤ ( 2 − Proof. √ We begin by demonstrating the descent lemma √ for Φ, 1)κ/(2 2). Note that this estimate implies that y1 ≥ (κ/ 2)∥u∥. Without loss of generality, assume y1 is positive. Fix ϵ > 0 sufficiently small that κ 6ϵ(a + c) √ ≥ . c−a 2 Shrinking ρ if necessary, assume that ϕ has Lipschitz constant ≤ κ + ϵ over its domain.
(240)
We first derive an upper bound on |Φ ◦ Tu,y1 |. Since Φ is Lipschitz and Tu,y1 is C 1 , setting y1 (s) := (1 − s)ϕ(u) + sy1 for s ∈ [0, 1], the fundamental theorem of calculus applies to give Φ ◦ Tu,y1 (u, y1 ) = Φ ◦ Tu,y1 (u, y1 ) − Φ ◦ Tu,y1 (u, ϕ(u)) (241) Z 1 d = (Φ ◦ Tu,y1 (x, y1 (s)) ds (242) 0 ds Z 1 ∂y1 Ty1 (u, y1 (s)) − Dϕ(Tu (u, y1 (s)))∂y1 Tu (u, y1 (s)) ds = Φ(u, y1 ) 0
(243) (244)
=: Φ(u, y1 ) I(u, y1 ),
where invariance of the graph of ϕ under Tu,y1 has been invoked on the first line to give Φ ◦ T (u, ϕ(u)) = 0, with Dϕ making sense almost everywhere by Rademacher’s theorem. Using the estimates ∥Dϕ∥ ≤ κ + ϵ and ϕ(u) ∈ [(κ − ϵ)∥u∥, (κ + ϵ)∥u∥], one then estimates: Z 1 Z 1 2 2 I(u, y1 ) = 1 + 2b∥u∥ − 6c y1 (s) ds + 4a(κ + ϵ)∥u∥ y1 (s) ds + O(∥u∥3 , y13 , ∥u∥2 y1 , ∥u∥y12 ) 0
0
(245) 2
= 1 + 2b∥u∥ − 2c(ϕ(u)
2
+ ϕ(u)y1 + y12 ) + 2a(κ + ϵ)∥u∥(ϕ(u) + y1 ) + O(∥u∥3 , y13 , ∥u∥2 y1 , y12 ∥u∥) (246)
≤ 1 − 2cy12 − κ(c − a)∥u∥y1 + 6κϵ(a + c)∥u∥2 ≤ 1 − 2cy12
(247)
(248) √ by taking ρ yet smaller if necessary to obtain the third line and using y1 ≥ (κ/ 2)∥u∥ together with (240) to obtain the fourth. Thus |Φ ◦ Tu,y1 (u, y1 )| ≤ |Φ(u, y1 )|(1 − 2cy12 ). √ We now turn to lower-bounding Tu (u, y1 )/∥u∥. Since y ≥ (κ/ 2)∥u∥, one has c−a 2 2 3 Tu (x, y1 )/∥u∥ ≥ 1 − 2ay1 − O(y ) ≥ 1 − 2 a + y 4
(249)
(250)
by taking ρ yet smaller if necessary. Finally, taking ρ yet smaller if necessary so that 1/(1 − 2(a + c−a 2 c−a 2 4 )y1 ) ≤ 1 + 2(a + 2 )y1 , one sees that |Φ ◦ Tu,y1 (u, y1 )| (1 − 2cy12 ) |Φ(u, y1 )| 2 e e y1 )| |Φ ◦ Tu,y1 (u, y1 )| = ≤ ≤ 1 − (c − a)y1 |Φ(u, 2 |Tu (u, y1 )| ∥u∥ (1 − 2(a + c−a 4 )y1 ) (251) √ √ e ≤ ( 2 − 1)κ/(2 2) is invariant. as claimed. Note that this also proves that the set |Φ| √ √ e t , y1,t )| ≤ ( 2 − 1)κ/(2 2) can be met from any We now demonstrate that the condition |Φ(u −2 sufficiently small, nonzero initial √ condition√in at most O(∥u∥ ) iterations. Consider the ratio q := y1 /∥u∥. Setting γ := ( 2 − 1)κ/(2 2) and shrinking ρ yet further if necessary so that |ϕ(u)/∥u∥ − κ| < γ/2, either q ∈ [κ − γ/2, κ + γ/2], in which case we can set τ := 0, or q is outside of [κ − γ/2, κ + γ/2]. In the latter case, observe that q ◦ Tu,y1 (u, y1 ) = q
1 + 2b∥u∥2 − 2cq 2 ∥u∥2 + O(∥u∥3 ) 1 − 2aq 2 ∥u∥2 + O(∥u∥3 )
(252)
= q 1 + 2(b − (c − a)q 2 )∥u∥2 + O(∥u∥3 ) 2
2
2
(253)
3
(254)
= q(1 + 2(c − a)(κ − q )∥u∥ + O(∥u∥ )) 33
using b = (c − a)κ2 . Suppose first that q < q− . Define 2 θ− := (c − a)(κ2 − q− ) > 0.
(255)
Since q ≤ q− in this regime, after shrinking ρ if necessary the error term in (254) may be absorbed to give q ◦ Tu,y1 (u, y1 ) ≥ q(1 + θ− ∥u∥2 ).
(256)
Moreover, since y1 = q∥u∥ ≤ q− ∥u∥, the update equation for u gives ∥Tu (u, y1 )∥ ≥ (1 − C− ∥u∥2 )∥u∥
(257)
for some C− > 0, after possibly shrinking ρ once more. Assuming also that ρ is small enough that 1 (1 − C− ∥u∥2 )2
≤ 1 + 3C− ∥u∥2 ,
(258)
it follows that whenever qt < q− one has 1 1 ≤ + 3C− . ∥ut+1 ∥2 ∥ut ∥2
(259)
Hence, if qs < q− for all s = 0, . . . , t − 1, then ∥ut ∥2 ≥
∥u∥2 . 1 + 3C− t∥u∥2
(260)
Combining (256) with (260), one obtains θ− ∥u∥2 1 + 3C− t∥u∥2
qt+1 ≥ qt 1 +
.
Taking logarithms, using log(1 + s) ≥ s/2 for all sufficiently small s and s−1 log(1 + rs), and summing gives t−1 X θ− ∥u∥2 log qt ≥ log q0 + log 1 + 1 + 3C− s∥u∥2 s=0
(261) Pt−1
s=0 (1 + rs)
−1
≥
(262)
t−1
≥ log q0 +
1 θ− ∥u∥2 X 2 2 1 + 3C − s∥u∥ s=0
(263)
≥ log q0 +
θ− log(1 + 3C− t∥u∥2 ), 6C−
(264)
and therefore qt ≥ q0 (1 + 3C− t∥u∥2 )θ− /(6C− ) .
(265)
Consequently, if 1 t≥ 3C− ∥u∥2
q− q0
6C− /θ− ,
(266)
then (265) forces qt−1 ≥ q− , contradicting the assumption that qs < q− for all s = 0, . . . , t − 1. Thus the orbit enters [q− , q+ ] in at most & #' " 6C− /θ− q− 1 τ− := −1 (267) 3C− ∥u∥2 q0 iterations. Suppose next that q > q+ . Define 2 θ+ := (c − a)(q+ − κ2 ) > 0.
34
(268)
Since q ≥ q+ in this regime, after shrinking ρ if necessary the error term in (254) may be absorbed to give q ◦ Tu,y1 (u, y1 ) ≤ q(1 − θ+ ∥u∥2 ).
(269)
In particular, as long as qt > q+ the sequence (qt ) is decreasing, and hence qt ≤ q0
(270)
y1,t = qt ∥ut ∥ ≤ q0 ∥ut ∥,
(271)
for all such t. Consequently, so the update equation for u implies that ∥ut+1 ∥ ≥ (1 − C+ ∥ut ∥2 )∥ut ∥
(272)
for some constant C+ = C+ (q0 ) > 0, after possibly shrinking ρ once more. Assuming also that ρ is small enough that 1 ≤ 1 + 3C+ ∥u∥2 , (1 − C+ ∥u∥2 )2
(273)
it follows that whenever qt > q+ one has 1 ∥ut+1
∥2
1 + 3C+ . ∥ut ∥2
(274)
∥u∥2 . 1 + 3C+ t∥u∥2
(275)
≤
Hence, if qs > q+ for all s = 0, . . . , t − 1, then ∥ut ∥2 ≥ Combining (269) with (275), one obtains qt+1 ≤ qt
θ+ ∥u∥2 1− 1 + 3C+ t∥u∥2
Taking logarithms and using log(1 − s) ≤ −s gives t−1 X log qt ≤ log q0 + log 1 − s=0
.
θ+ ∥u∥2 1 + 3C+ s∥u∥2
t−1 X
(276)
(277)
1 1 + 3C+ s∥u∥2 s=0
(278)
θ+ log(1 + 3C+ t∥u∥2 ), 3C+
(279)
≤ log q0 − θ+ ∥u∥2 ≤ log q0 −
and therefore qt ≤ q0 (1 + 3C+ t∥u∥2 )−θ+ /(3C+ ) .
(280)
Consequently, if t≥
1 3C+ ∥u∥2
q0 q+
3C+ /θ+ ,
(281)
then (280) forces qt−1 ≤ q+ , contradicting the assumption that qs > q+ for all s = 0, . . . , t − 1. Thus the orbit enters [q− , q+ ] in at most & " #' 3C+ /θ+ 1 q0 τ+ := −1 (282) 3C+ ∥u∥2 q+ iterations. Having established all of these lemmas, the convergence proof now follows from a similar argument to that of [39, Theorem D.8]. 35
Theorem D.11. Assuming Conjecture D.7, the iterates (zt , vt , ut , yt ) under T of any point (z, v, u, y) with v, u, y sufficiently small converge to some point (z̄, 0, 0, 0) with rate Θ(t−1/2 ). Proof. By Lemma D.10, one is assured of (239) holding for all time t ≥ τ1 = O(∥u∥−2 ). Following −2 this, the argument of [39, Theorem D.8] applies to show that in at most a further τ2 := O(y1,τ )= 1 −2 O(∥u∥ ) iterations, there are constants c2 > c1 > 0 such that c2 c1 ∥ut ∥ ∈ , (283) (1 + (t − τ2 ))1/2 (1 + (t − τ2 ))1/2 and |y1,t | ∈ [(κ/2)∥ut ∥, (3κ/2)∥ut ∥]
(284)
for all t ≥ τ2 . Thus (ut , y1,t ) = Θ(t−1/2 ). On the other hand, by Lemma D.9, vt and y2:q,t go to zero strictly faster thanm ut . Thus the overall rate of convergence is the claimed Θ(t−1/2 ). Assumption D.12. The smallest eigenvalue of ∇2M λ1 |F is constant, with constant multiplicity m. Moreover, about any x̄ ∈ F there is a choice of local frame ξ for the bottom eigenspace of ∇2M λ1 |F such the image of the map F × Rm × R ∋ (z, u, y1 ) 7→ expz (ξ(z)u) + y1 ν1 (expz (ξ(z)u))
(285)
is locally invariant under GD with step size 2/λ1 |F , and such that in the coordinates (z, u, y1 ) one has GDu and GDy1 being independent of z. Theorem D.13. Suppose that Assumptions 3.1, 3.3, 3.4 and 3.5 hold. Assume furthermore that either ∇2 λ1 |F |ν M F is a constant scalar multiple of the identity, or that Assumption D.12 and Conjecture D.7 hold. Let Vρ,∆ be an invariant neighbourhood of x̄ ∈ F as in Lemma D.1. Then, shrinking ρ further if necessary, for any (2/λ1 |F , x, y) ∈ Vρ,∆ such that y1 ̸= 0, the iterates (xt , yt ) converge to F with rate Θ(t−1/2 ). Proof. Gradient descent takes the form GDx (η, x, y) = x − ζ(η, x)y12 ∇M λ1 (x) + O(y13 dM (x, F ))
(286)
GDy1 (η, x, y) = (1 − ηλ1 (x))y1 + y13 + O(y14 )
(287)
by Theorem 4.1. Recalling that η = 2/λ1 |F , denoting xF = PF (x) for x ∈ M for the nearest point projection onto F , and Taylor expanding ζ(η, x) = ζ + O(dM (x, F )) where 2 ζ := ζ(2/λ1 |F , ·)|F , λ1 (x) = λ1 |F + (1/2)DM λ1 (xF )[logxF (x)⊙2 ] + O(dM (x, F )3 ) and 2 ∇M λ1 (x) = ΠxF →x ∇M λ1 (xF )[logxF (x)] + O(dM (x, F )2 ) where ΠxF →x is parallel transport in M , these formulae reduce to GDx (η, x, y) = x − ζy12 ΠxF →x ∇2M λ1 (xF )[logxF (x)] + R∥ (x, y)
(288)
2 ⊙2 GDy1 (η, x, y) = −y1 (1 + λ|−1 ] − y12 + R1⊥ (x, y)) F DM λ1 (xF )[logxF (x)
(289)
where R∥ (x, y) = O(y13 dM (x, F ), y12 dM (x, F )2 ) and R1⊥ (x, y) = O(y13 , dM (x, F )3 ). Recall now that, by Assumption D.12, the smallest eigenvalue of ∇2M λ1 |F is constant (equal to µ, say) and of constant multiplicity along F . Consider then the C ∞ decomposition νF = E1 ⊕ E2
(290)
of the normal bundle νF ⊂ T M |F , with E1 being the eigenbundle for the smallest eigenvalue of ∇2M λ1 |F and with E2 being its orthogonal complement. Denoting by m the codimension of F in m, in a neighbourhood U of x̄ in F that is contained in Vρ,∆ , fix an orthonormal frame field ν1:m : U → Rp×m for νF ⊂ T M |F that is adapted to this decomposition in the sense that ν1:rank(E1 ) pointwise spans E1 and νrank(E1 )+1:m pointwise spans E2 . Consider then the Fermi coordinates (xF , u, v) defined by x = xF , expxF (ν1:rank(E1 ) (xF )u + νrank(E1 )+1:m (xF )v) (291) 36
T T for a tubular neighbourhood of U , and denote P1 := ν1:rank(E and P2 := νrank(E 1) 1 )+1:m so that xF = PF (x), u = P1 (xF ) logxF (x) and v = P2 (xF ) logxF (x). Setting δ(x, y) := −ζy12 ΠxF →x ∇2M λ1 (xF )[logxF (x)] = O(y12 dM (x, F )) and applying Assumption D.12, observe that PF (GDx (η, x, y)) = PF (x + δ(x, y) + R∥ (x, y)) (292) ∥ ∥ 2 = PF (x) − DPF (x)[δ(x, y) + R (x, y)] + O (δ(x, y) + R (x, y)) (293)
= xF + O(y13 ∥v∥, y12 ∥v∥(∥u∥ + ∥v∥)) (294) using the fact that DPF (x)[ΠxF →x v] = v + O(∥v∥dM (x, F )) as v → 0 and x → F , while P1 (xF ) logPF (GDx (η,x,y)) (x + δ(x, y) + R∥ (x, y))
(295)
∥
= P1 (xF ) logxF (x + δ(x, y) + R (x, y)) + O(y13 dM (x, F ), y12 dM (x, F )2 ) (296) 2 2 3 = P1 (xF ) logxF (x) − ζy1 P1 D logxF (x)[ΠxF →x ∇M λ1 (xF )[logxF (x)]] + O(y1 dM (x, F ), y12 dM (x, F )2 ) (297) = (1 − ζy12 µ)u + O(y13 (∥u∥ + ∥v∥), y12 (∥u∥ + ∥v∥)2 )
(298) using the fact that D logxF (x)[ΠxF →x v] = v + O(∥v∥dM (x, F )) as v → 0 and x → F , and similarly P2 (xF ) logPF (GDx (η,x,y)) (x + δ(x, y) + R∥ (x, y)) = (I − ζy12 H(xF ))v + O(y13 ∥v∥, y12 ∥v∥(∥u∥ + ∥v∥)), (299) where H(xF ) = P2 (xF )∇2M λ1 (xF )P2 (xF )2 , and where in obtaining the remainder term we have used Assumption D.12, which says that v = 0 is invariant. Thus, letting z denote the coordinate in F , in the (z, u, v, y) coordinates gradient descent is given by GDz (η, z, u, v, y) = z + O(y13 ∥v∥, y12 ∥v∥(∥u∥ + ∥v∥)),
(300)
GDu (η, z, u, v, y) = (1 − ζy12 µ)u + O(y13 (∥u∥ + ∥v∥), y12 (∥u∥ + ∥v∥)2 ),
(301)
GDv (η, z, u, v, y) = (I − ζy12 H(z))v + O(y13 ∥v∥, y12 ∥v∥(∥u∥ + ∥v∥)),
(302)
−1 T 2 2 3 3 GDy1 (η, z, u, v, y) = −y1 (1 + λ1 |−1 F µ∥u∥ + λ1 |F (v H(z)v) − y1 + O(y1 , (∥u∥ + ∥w∥) )). (303)
It is then apparent that GD2 takes the form required for the result to follow from Theorem D.11. D.4
Supercritical regime
In this subsection, we prove Theorem 5.3. As we will demonstrate at the end, the result follows from the following more abstract theorem. Theorem D.14. Given α > 0 and constants ξ > 0 and ζ > 0, let A(z) be a C ∞ family of positive definite matrices, and consider the functions Tz (z, u, y) = z + O(y 3 ∥u∥, y 2 ∥u∥2 ), (304) Tu (z, u, y) = (I − ζy 2 A(z))u + O(y 3 ∥u∥, y 2 ∥u∥2 ), T
2
3
(305) 3
Ty (z, u, y) = −(1 + α + ξu A(z)u − y + O(∥u∥ , y ))y. (306) Assume moreover that Ty (z, 0, y) is independent of z, and that for every sufficiently small ρ > 0 there exists a neighbourhood Vρ of diameter at most ρ which is invariant under T . Then, there are constants C1 , C2 , C3 , ρ > 0 such that for all α sufficiently small, the map T = (Tz , Tu , Ty ) admits, for every z ∈ Vρ , a stable, period-2 orbit {(z, 0, ξ+ ), (z, 0, ξ− )} (307) √ with ξ± = ± α + O(α), and the iterates (zt+1 , ut+1 , yt+1 √ √ ) := T (zt , ut , yt ) starting from any (z0 , u0 , y0 ) ∈ Vρ0 with 0 < |y0 | ≤ C1 α and ∥u0 ∥ ≤ C2 α converge to one of these orbits at a rate of O (1 − C3 α)t . More precisely, there exists z∞ ∈ Vρ0 such that zt → z∞ ,
(u2t , y2t ) → (0, ξsign(y0 ) ),
(u2t+1 , y2t+1 ) → (0, ξ−sign(y0 ) ),
(308)
and dist (zt , ut , yt ), {(z∞ , 0, ξ+ ), (z∞ , 0, ξ− )} = O (1 − C3 α)t . 37
(309)
Proof. The proof essentially the same as that of [39, Theorem D.11], but requires some minor modications due to the higher dimensionality of the system. The subspace u = 0 is preserved by T , and thereon one sees that Ty takes the form Ty (z, 0, ·) : y 7→ −(1 + α)y + y 3 + O(y 4 ),
(310)
independently of z. Hence, by Lemma D.2, there is a period-two orbit {ξ+ , ξ− } of the form √ ξ± = ± α + O(α). It follows that for every z the pair {(z, 0, ξ+ ), (z, 0, ξ− )} is a period-two orbit of T . We will show that the iterates of the square T 2 of T converge in the (u, y) variables to (0, ξ± ), while the z-variable converges because its increments are summable. Just as in [39, Theorem D.11], this former part will be achieved by showing that the derivative of the (u, y)-part of T 2 is uniformly contracting over a neighbourhood of (0, ξ± ), followed by proving a guarantee of convergence to this neighbourhood in finite time. Via a routine calculation one sees that
z + O(y 3 ∥u∥, y 2 ∥u∥2 ) (I − ζ(1 + (1 + α)2 )y 2 A(z))u + O(y 3 ∥u∥, y 2 ∥u∥2 ) T 2 (z, u, y) = y (1 + α)2 + 2(1 + α)ξuT A(z)u − (1 + α)(1 + (1 + α)2 )y 2 . +O(∥u∥3 , ∥u∥2 y, ∥u∥y 2 , y 3 )
(311)
Let Gz (u, y) denote the (u, y)-part of T 2 with z regarded as a parameter. Differentiating with respect to (u, y) gives I − ζ(1 + (1 + α)2 )y 2 A(z) −2ζ(1 + (1 + α)2 )yA(z)u D(u,y) Gz (u, y) = 4(1 + α)ξy uT A(z) (1 + α)2 + 2(1 + α)ξuT A(z)u (312) −3(1 + α)(1 + (1 + α)2 )y 2 + O(∥u∥3 , ∥u∥2 y, ∥u∥y 2 , y 3 ),
(313)
where the O(·) term denotes a (dim u + 1) × (dim u + 1) matrix whose operator norm is bounded by the displayed quantity. Now choose ρ0 > 0 so small that Vρ0 is invariant and that there exist constants 0 < µ∗ ≤ µ∗ < ∞ satisfying µ∗ I ≤ A(z) ≤ µ∗ I
(314)
for all z ∈ Vρ0 . In particular, for all y satisfying α ≤ y 2 ≤ 4α, (1 + α)(1 + (1 + α)2 )
(315)
√ ∥u∥ ≤ C2 α
(316)
and all u satisfying
for a sufficiently small C2 > 0, the matrix D(u,y) Gz (u, y) has block entries with operator norms upper-bounded by ∗α 1 − ζµ O(α3/2 ) 1+α + O(α3/2 ) (317) O(α3/2 ) 1−α for all α sufficiently small, uniformly in z ∈ Vρ . Now, using the fact that for a block matrix B11 B12 B= one has B21 B22 ∥B∥2 ≤
∥B11 ∥2 ∥B21 ∥2
∥B12 ∥2 ∥B22 ∥2
(318) 2
it follows exactly as in [39, Theorem D.11] that there is C3 > 0 such that ∥D(u,y) Gz (u, y)∥2 ≤ 1 − C3 α. 38
(319)
Finally, denoting by W the intersection of Vρ with (315) and (316), it follows exactly as in [39, Theorem D.11] that for any point (z, u, v) ∈ W , its iterates (u2t , y2t ) converge toward (0, ξsign(y) ) according to the estimate ∥(u2t , y2t − ξsign(y) )∥ ≤ (1 − C3 α)t ∥(u, y − ξsign(y) )∥. (320) We next show that the corresponding z-iterates converge, which is not necessary in [39] since they consider an isolated √ flat minimum. Starting again from (z, u, y) ∈ W , since (z2t , u2t , y2t ) remain in Vρ and y2t = O( α), one has 3 2 ∥z2(t+1) − z2t ∥ = O(y2t ∥u2t ∥, y2t ∥u2t ∥2 ) = O(α3/2 ∥u2t ∥, α∥u2t ∥2 ). (321) t Since ∥u2t ∥ = O (1 − C3 α) , the right-hand side is summable in t, so (z2t )t≥0 is Cauchy and hence converges to some z∞ . Moreover, ∥z2t − z∞ ∥ = O (1 − C3 α)t . (322) Applying one further iterate of T gives the same conclusion for the odd subsequence, and therefore the full orbit converges to the period-two orbit {(z∞ , 0, ξ+ ), (z∞ , 0, ξ− )} at the stated rate.
The proof is completed by showing that the iterates starting from any u satisfying (316) and any y satisfying α (323) 0 < y2 ≤ (1 + α)(1 + (1 + α)2 ) are eventually drawn into W , for which the corresponding argument from [39, Theorem D.11] may be invoked without change. Theorem 5.3 now follows from Theorem D.14 by choosing appropriate coordinates. Theorem D.15. Let Vρ,∆ be an invariant neighbourhood of x̄ ∈ F as in Lemma D.1. Then, shrinking ρ further if necessary, there is C > 0 such that any (η, x, y) ∈ Vρ,∆ with y1 ̸= 0 has iterates (xt , yt ) of p GD(η, ·) converging to a stable, period-two orbit about some point z∞ ∈ F with amplitude Θ( ηλ|F − 2) with rates dM (xt , F ), |y1,t | = O (1 − C(ηλ|F − 2))t Proof. As in Theorem 4.1, gradient descent takes the form GDx (η, x, y) = x − ζ(η, x)y12 ∇M λ1 (x) + O(y13 dM (x, F ))
(324)
GDy1 (η, x, y) = (1 − ηλ1 (x))y1 + y13 + O(y14 )
(325)
2 GD⊥ y2:q (η, x, y) = (I − ηΛ2:q (x))y2:q + O(y1 ∥y2:q ∥, ∥y2:q ∥ ).
(326)
Given x ∈ M sufficiently close to F , write xF := PF (x) is the projection of x onto F . One has Taylor expansions ζ(η, x) = ζ(η) + O(dM (x, F )) where ζ(η) := ζ(η, ·)|F , λ1 (x) = λ1 |F + 2 (1/2)DM λ1 (x)[logxF (x)⊗2 ] + O(dM (x, F )3 ) and ∇M λ1 (x) = ΠxF →x ∇2M λ1 (xF )[logxF (x)] + O(dM (x, F )2 ), where ΠxF →x is parallel transport. Using these expansions, the x and y1 -updates for the gradient descent equations become GDx (η, x, y) = x − ζ(η)y12 ΠxF →x ∇2M λ1 (xF )[logxF (x)] + O(y13 dM (x, F )) (327) 2 GDy1 (η, x, y) = −y1 (1 + (η/2)DM λ1 (xF )[logxF (x)⊗2 ] − y12 + O(dM (x, F )3 , y13 )).
(328)
Finally, shrinking ρ if necessary, choose an orthonormal frame field ν for νM F ⊂ T M |F defined over Vρ ∩ F with respect to which Fermi coordinates x = (z, expz (ν(z)u)) are defined, where z := xF denotes the F -coordinate. Then similar calculations to those employed in the proof of Theorem D.13 apply to show that with respect to the (z, u, y) coordinates, gradient descent becomes GDz (η, z, u, y) = z + O(y13 ∥u∥, y12 ∥u∥2 ) (329) GDu (η, z, u, y) = (I − ζ(η)y12 A(z))u + O(y13 ∥u∥, y12 ∥u∥2 )
(330)
GDy1 (η, z, u, y) = −y1 (1 + (ηλ|F − 2) + (η/2)uT A(z)u − y12 + O(∥u∥3 , y12 )), 2
GDy2:q (η, z, u, y) = (I − ηΛ2:q (z, u))y2:q + O(y1 ∥y2:q ∥, ∥y2:q ∥ ).
(331) (332)
Shrinking ρ if necessary and applying Theorem D.14 gives (ut , y1,t ) converging with rate O (1 − C(ηλF − 2))1/2 for some C > 0 and all (η, z, u, y) ∈ Vρ,∆ , and shrinking ρ further if necessary one sees that the iterates y2:q,t go to zero at least as fast as O (1 − C(ηλ|F − 2))t , from which the result follows. 39
E
Matrix factorisation
In this section we prove that deep matrix factorisation problems satisfy all of the assumptions made in QL the paper. Given L ∈ N≥2 and d0 , . . . , dL ∈ N, consider f : l=1 Rdl ×dl−1 → RdL ×d0 defined by f (w) := WL · · · W1 ,
w := (W1 , . . . , WL ) ∈
L Y
Rdl ×dl−1 .
(333)
l=1
Given l ≥ m, we denote Wl:m := Wl · · · Wm ; if l < m then Wl:m will denote the identity. Proposition E.1. Assume that dl ≥ dL for all l ≤ L, and let τ ∈ RdL ×d0 have singular values σ1 > σ2 ≥ · · · ≥ σdL > 0. Then τ is in the range of f and is a regular value of f . Proof. That τ is contained in the range of f is obvious from the assumption that dl ≥ dL for all l ≤ L. To see that it is a regular value of f , note that the derivative of f evaluates on a tangent vector QL (ξ1 , . . . , ξL ) ∈ l=1 Rdl ×dl−1 to give Df (w)[ξ1 , . . . , ξL ] =
L X
WL:l+1 ξl Wl−1:1 .
(334)
l=1
Since τ has rank dL , any w ∈ M := f −1 {τ } must have WL · · · W2 being of rank dL , implying that range(Df (w)) ⊇ {WL · · · W2 ξ1 : ξ1 ∈ RdL ×d0 } = Range(WL · · · W2 ⊗ Id0 ) = RdL ×d0 , (335) implying that Df (w) is full-rank and thus making τ a regular value of f as claimed. Define ℓ(w) :=
1 ∥τ − f (w)∥2F , 2
w := (W1 , . . . , WL ) ∈
L Y
Rdl ×dl−1 .
(336)
l=1
Since we are concerned only with quantities that depend on the metric and the derivatives of f , we may assume without loss of generality that τ = diag(σ1 , . . . , σdL ) is diagonal. We now consider the eigendata of the Hessian ∇2 ℓ|M = Df T Df , whose eigenvalue fields we denote λ1 ≥ λ2 ≥ . . . . Denote S := {w ∈
L Y
Rdl ×dl−1 : λ1 (w) = λ2 (w)}
(337)
l=1
for the singular set; since the λi are continuous, S is closed. The set of nonsingular flat minima F will be realised as an analytic fibre bundle over a product of spheres. To see this, first observe that the subset {(W 1 , . . . , W L ) : W L · · · W 1 = diag(σ2 , . . . , σdL )}
(338)
QL
of l=1 R(dl −1)×(dl−1 −1) is in fact a submanifold by the argument of Proposition E.1. Given QL w := (W 1 , . . . , W L ) ∈ l=1 R(dl −1)×(dl−1 −1) , define the linear maps ∆01 (w) :=
L X
2(L−l)/L
σ1
W Tl−1:1 W l−1:1 ∈ R(d0 −1)×(d0 −1)
(339)
2(l−1)/L
W L:l+1 W TL:l+1 ∈ R(dL −1)×(dL −1)
(340)
l=1
∆10 (w) e :=
L X
σ1
l=1
∆11 (w) e :=
L X
W L:l+1 W TL:l+1 ⊗ W Tl−1:1 W l−1:1 : R(dL −1)×(d0 −1) → R(dL −1)×(d0 −1)
l=1
40
(341)
Denote by M the intersection of the manifold (338) with the open set {w e : 2−2/L }; as the intersection of a submanifold max{λ1 (∆01 (w)), λ1 (∆10 (w)), λ1 (∆11 (w))} < Lσ1 with an open set, M is itself a manifold, and will be the typical fibre of the fibre bundle F . To construct the bundle itself, letting O(d) denote the orthogonal group in d dimensions, observe that QL−1 M carries an action of the group O := l=1 O(dl ) defined by (Q1 , . . . , QL−1 ) · (W 1 , . . . , W L ) := (Q1 W 1 , Q2 W 2 QT1 , . . . , W L QTL ). (342) Q L−1 Letting S d−1 ⊂ Rd denote the sphere, consider the principal O-bundle P → l=1 S dl −1 whose QL−1 dl ×(dl −1) fibre over (u1 , . . . , uL−1 ) is the space of tuples (U1 , . . . , UL−1 ) ∈ l=1 R of orthonormal ⊥ frames for the orthogonal complements (u⊥ 1 , . . . , uL−1 ). Note that such a tuple (U1 , . . . , UL−1 ) uniquely determines a its corresponding (u1 , . . . , uL−1 ) up to a sign, and that P carries the canonical right action (U1 , . . . , UL−1 ) · (Q1 , . . . , QL−1 ) := (U1 Q1 , . . . , UL−1 QL−1 )
(343)
of O. Finally, consider the associated bundle B := P ×O M →
L−1 Y
S dl −1 ,
(344)
l=1
whose total space is the quotient of the product P × M by the group action of O given by (Q1 , . . . , QL−1 ) · (U1 , . . . , UL−1 ; W 1 , . . . , W L )
(345)
:= (U1 Q1 , . . . , UL−1 QL−1 , QT1 W 1 , QT2 W 2 Q1 , . . . , W L QL−1 ). QL−1
Since P and M are analytic, O is compact and its action on P × M is free, B → l=1 S analytic fibre bundle with typical fibre M . Proposition E.2. The map ϕ : B → M defined by 1/L L 0 [u , U ]T ϕ [U1 , . . . , UL−1 ; W 1 , . . . , W L ] := [ul , Ul ] σ1 , l−1 l−1 0 Wl l=1
(346) dl −1
is an
(347)
where [u0 , U0 ] := Id0 and [uL , UL ] := IdL , is an analytic embedding whose range coincides with F ; QL−1 consequently, F is an analytic fibre bundle over l=1 S dl −1 with typical fibre M . Moreover, any w ∈ F may be mapped via an isometry which preserves f to a point of the form 1/L !L σ1 0 (348) Wl 0 l=1
for some (W 1 , . . . , W L ) ∈ M . Proof. It must first be demonstrated that ϕ is well-defined. Given (Q1 , . . . , QL−1 ) ∈ O and (U1 , . . . , UL−1 ; W 1 , . . . , W L ) ∈ B × M , define ′ (U1′ , . . . , UL−1 ; W ′1 , . . . , W ′L ) := (Q1 , . . . , QL−1 ) · (U1 , . . . , UL−1 ; W 1 , . . . , W L ).
(349)
Then simply observe that for any l ∈ {1, . . . , L}, 1/L 1/L σ 0 ′ ′ 1 [ul , Ul ] [ul−1 , Ul−1 ] = [ul , Ul Ql ] σ1 0 W ′l 0 1/L = [ul , Ul ] σ1 0
0 [ul−1 , Ul−1 Ql−1 ]T QTl W l QTl−1 (350) 0 [u , U ]T , (351) l−1 l−1 Wl
so that ϕ is well-defined. It is also easy to see that ϕ is injective; supposing that ′ (U1 , . . . , UL−1 ; W 1 , . . . , W L ), (U1′ , . . . , UL−1 ; W 1 , . . . , W L ) ∈ P × M satisfy 1/L 1/L 0 [u , U ]T = [u′ , U ′ ] σ1 0 [u′ , U ′ ]T , [ul , Ul ] σ1 (352) l−1 l−1 l l l−1 l−1 0 Wl 0 W ′l 41
then T ′T ′T = Ul′ W ′l Ul−1 ⇒ W l = (Ul′T Ul )T W ′l (Ul−1 Ul−1 ) (353) Ul W l Ul−1 ′ ′T while clearly Ul = Ul (Ul Ul ) for all l; thus U1 , . . . , UL−1 ; W 1 , . . . , W L ] = ′ [U1′ , . . . , UL−1 ; W ′1 , . . . , W ′L ] in B. Finally, that ϕ is an analytic embedding is clear from its definition via matrix multiplication.
It remains to be shown that the range of ϕ coincides with F . We argue in a similar fashion to [42]. We first derive a lower-bound for λ1 ≡ λ1 (∇2 ℓ|M ) ≡ λ1 (Df Df T |M ); we then prove that this lower-bound is met on the desired manifold F and prove the normal form. First, the lower-bound. For any w = (W1 , . . . , WL ) ∈ M , one has Df Df T (w) =
L X
T T WL:l+1 WL:l+1 ⊗ Wl−1:1 Wl−1:1 ,
(354)
l=1
so that λ1 (w) =
sup ⟨Z, Df Df T (w)[Z]⟩ = ∥Z∥F =1
sup
L X
∥Z∥F =1 l=1
T T ∥WL:l+1 ZWl−1:1 ∥2F .
(355)
Consider in particular Z := e1 eT1 , where the former e1 is the first standard basis vector in RdL and the latter is the first standard basis vector in Rd0 (these being the top left and right singular vectors of the diagonal τ respectively). One has λ1 (w) ≥
L X
T ∥WL:l+1 e1 ∥2 ∥Wl−1:1 e1 ∥2
l=1
=
L X
T ∥WL:l+1 e1 ∥2 ∥Wl:1 e1 ∥2
l=1
∥Wl−1:1 e1 ∥2 ∥Wl:1 e1 ∥2
L X ∥Wl−1:1 e1 ∥2 T ⟨WL:l+1 e1 , Wl:1 e1 ⟩2 ≥ ∥Wl:1 e1 ∥2 l=1
L X ∥Wl−1:1 e1 ∥2 = ⟨e1 , WL:1 e1 ⟩2 ∥Wl:1 e1 ∥2 l=1
= σ12
L X ∥Wl−1:1 e1 ∥2 l=1
≥ Lσ12
∥Wl:1 e1 ∥2
Y L
l=1 2−2/L = Lσ1 ,
∥Wl−1:1 e1 ∥ ∥Wl:1 e1 ∥
L2 (356) (357)
where the third line follows from Cauchy-Schwarz and the sixth follows from the inequality between arithmetic and geometric means. We next consider when these estimates are equalities, so that the lower-bound is achieved. T The Cauchy-Schwarz estimate is an equality precisely when WL:l+1 e1 is a scalar multiple of Wl:1 e1 d0 for all l = 1, . . . , L. Setting u0 := e1 ∈ R and ul := Wl:1 u0 /∥Wl:1 u0 ∥ for l = 1, . . . , L so that uL = e1 ∈ RdL , it follows that (uL , ul ) is a singular vector pair for WL:l+1 with singular value σ1 /∥Wl:1 u0 ∥, for all l = 1, . . . , L. Indeed, for any l = 1, . . . , L, equality in the Cauchy-Schwarz T estimate implies that there is a scalar cl such that WL:l+1 uL = cl ul . Taking the inner product of both sides with Wl:1 u0 then gives σ1 cl ∥Wl:1 u0 ∥ = uTL WL:l+1 Wl:1 u0 = σ1 ⇒ cl = (358) ∥Wl:1 u0 ∥ so that σ1 1 σ1 T WL:l+1 uL = ul , and WL:l+1 ul = WL:1 u0 = uL . (359) ∥Wl:1 u0 ∥ ∥Wl:1 u0 ∥ ∥Wl:1 u0 ∥
42
This further implies that the ul are a chain of common singular vectors for the Wl ; indeed, for any l one straightforwardly has Wl−1:1 u0 1 ∥Wl:1 u0 ∥ = Wl:1 u0 = ul , ∥Wl−1:1 u0 ∥ ∥Wl−1:1 u0 ∥ ∥Wl−1:1 u0 ∥
(360)
∥Wl:1 u0 ∥ T ∥Wl:1 u0 ∥ T ∥Wl:1 u0 ∥ WL:l+1 uL = WL:l uL = ul−1 . σ1 σ1 ∥Wl−1:1 u0 ∥
(361)
Wl ul−1 = Wl while (359) implies that WlT ul = WlT
Setting sl := ∥Wl:1 u0 ∥/∥Wl−1:1 u0 ∥ for these singular values, equality between the arithmetic and geometric means above occurs if and only if the sl are all equal, with L Y
1/L
sl = σ1 ⇒ sl = σ1
,
∀l ∈ {1, . . . , L}.
(362)
l=1
It follows that for any (W1 , . . . , WL ) achieving the lower-bound (357), with u0 , . . . , uL as above there must exist orthonormal frames (U1 , . . . , UL−1 ) in the fibre of the principal bundle P over (u1 , . . . , uL−1 ) and, since w ∈ / S, (W 1 , . . . , W L ) ∈ M such that 1/L σ 0 1 Wl = [ul , Ul ] [ul−1 , Ul−1 ]T , ∀l ∈ [L]. (363) 0 Wl This proves that F is in the range of ϕ; that every element in the range of ϕ meets the lower-bound (357) is then clear, thus proving the first claim. For the second claim, fix w ∈ range(ϕ) of the form 1/L [ul , Ul ] σ1 0
!L 0 [u , U ]T , l−1 l−1 Wl
(364)
l=1
with [u0 , U0 ] = Id0 and [uL , UL ] = IdL . This w may then be transformed into a point of the desired QL−1 form (348) by acting on it via the element ([u1 , U1 ]T , . . . , [uL−1 , UL−1 ]T ) of l=1 O(dl ) according to the 1-higher-dimensional version of (342). QL−1 With F identified as the fibre bundle B → l=1 S dl −1 , it is relatively easy to characterise the directions normal and tangent to F , and in this way to prove that λ1 is Morse-Bott along F . By the final claim of Proposition E.2, it suffices to work at a point of the form (348). Proposition E.3. At a point w ∈ F of the form (348), given a := (al )L−1 ∈ RL−1 , b := QL−1 dl −1 QL−1 (dl −1)×(dl=1 L−1 L−1 L−1 −1) l (bl )l=1 , c := (cl )l=1 ∈ l=1 R and D := (Dl )l=1 ∈ l=1 R , denote 1/L !L−1 σ (a − a ) 0 l l−1 1 , (365) v1 (w; a) := 0 0 l=1
v2 (w; b, c) :=
1/L
W Tl bl − σ1 0
0 1/L σ1 cl − W l cl−1
bl−1
T ! !L−1 (366) l=1
and 0 v3 (w; D) := 0
0 Dl W l − W l Dl−1
L−1 ,
(367)
l=1
where a0 , b0 , c0 , D0 are taken to be zero. Then all such v1 (w; a), v2 (w; b, c), v3 (w; D) span the tangent space Tw M . Moreover, the tangent space to F at w is L−1 L−1 Y Y dl −1 (dl −1)×(dl −1) Tw (F ) = span v2 (w, ξ, −ξ), v2 (w, D) : ξ ∈ R ,D∈ R (368) l=1
43
l=1
and its orthogonal complement νw (F ) in Tw M is L−1 Y νw (F ) = span v1 (w, a), v2 (w, b, c) : a ∈ RL−1 , b, c ∈ Rdl −1 s.t. K1 (w)[b] = K2 (w)[c] , l=1
(369) where
2/L
K1 (w)[b] :=
σ1
1/L 1/L Idl −1 + W l W Tl bl − σ1 W l bl−1 − σ1 W Tl+1 bl+1
L−1 (370) l=1
and K2 (w)[c] :=
2/L
σ1
1/L 1/L Idl −1 + W Tl+1 W l+1 cl − σ1 W l cl−1 − σ1 W Tl+1 cl+1
L−1 .
(371)
l=1
Proof. That the v1 (w; a), v2 (w; b, c), v3 (w; D) determine elements of Tw M follows from the fact that (a, b, c, D) parametrise the family
A :=
al Al := cl
bTl Dl
!L ∈ l=1
L−1 Y
Rdl ×dl ,
(372)
l=1
and that for any sufficiently small balls Bl ⊂ Rdl ×dl , one has a chart φ : w = (W1 , . . . , WL ) defined by
QL−1 l=1
Bl → M about
φ(A1 , . . . , AL−1 ) := exp(A1 )W1 , exp(A2 )W2 exp(−A2 ), . . . , WL exp(−AL−1 ) for (A1 , . . . , AL−1 ) ∈
QL−1 l=1
(373)
Bl . Thus the derivatives at zero of the curves
t 7→ exp(tA1 )W1 , exp(tA2 )W2 exp(−tA1 ), . . . , WL exp(−tAL−1 )
(374)
QL−1 parametrised by l=1 Rdl ×dl form the tangent space Tw M . Fixing (a, b, c, D) defining A ∈ QL−1 dl ×dl , this tangent vector is given by l=1 R 1/L
σ1 (al − al−1 ) 1/L σ1 cl − W l cl−1
T ! !L−1 1/L W Tl bl − σ1 bl−1 , Dl W l − W l Dl−1 l=1
(375)
with a0 , b0 , c0 , D0 equal to zero. Thus the family of all v1 (w; a), v2 (w; b, c), v3 (w; D) determine Tw M . We now turn to the tangent and normal spaces to F , exploiting the fibre bundle structure thereof worked out in Proposition E.2. At w ∈ F , the tangent directions are either tangent to the base QL−1 dl −1 of the bundle B, or tangent to its fibre. At w in the normal form (348), tangents to the l=1 S base correspond to rotating the first standard basis vector into any of the others in each of the L − 1 QL−1 factors; these tangents are precisely of the v2 (w; ξ, −ξ) for any ξ ∈ l=1 Rdl −1 . On the other hand, tangents to the fibre are precisely those which act solely on the bottom-right block of each of the QL−1 L − 1 factors, and are thus precisely of the form v3 (w; D) for any D ∈ l=1 R(dl −1)×(dl −1) . Finally, νw (F ) consists precisely of those elements of Tw M that are orthogonal to Tw (F ) with respect to the factor-wise Frobenius inner product. Since v3 (w; D) ∈ Tw (F ) for all D ∈ QL−1 (dl −1)×(dl −1) , νw (F ) must be spanned only by some subset of v1 (w; a) and v2 (w; b, c) l=1 R QL−1 for a ∈ RL−1 and b, c ∈ l=1 Rdl −1 . Since Tw (F ) contains no nonzero vectors of the form v1 (w; a), all such vectors are contained in νw (F ) and correspond to changes of the top singular 1/L values of the factors away from σ1 . To determine which of the v2 (w; b, c) lie in νw (F ), fix 44
b, c, ξ ∈ 0=
L−1 X
QL−1 l=1
Rdl −1 ; orthogonality of v2 (w; b, c) to v2 (w; ξ, −ξ) requires
tr v2 (w; ξ, −ξ)Tl v2 (w; b, c)l
(376)
l=1
=
L−1 X
tr
l=1
=
L−1 X
1/L T T W Tl ξl − ξl−1
0 1/L T −W l ξl + σ1 ξl−1
σ1
!
0 1/L σ1 cl − W l cl−1
1/L
bTl W l − σ1 bTl−1 0 (377)
ξlT K2 (w)[c] − K1 (w)[b] .
(378)
QL−1
Rdl −1 , it follows that K1 (w; b) = K2 (w; c). This concludes
l=1
Since this must hold for all ξ ∈ the proof.
l=1
Having determined νw (F ), we may now move to proving that λ1 is Morse-Bott along F , i.e. that the restriction of ∇2M λ1 to ν(F ) is positive-definite. We first recall the following lemma. Lemma E.4. [[41, 3.2.2]] Let t 7→ A(t) be a C 2 family of symmetric matrices. Assume that the top eigenvalue function λ1 : t 7→ λ1 (A(t)) has λ1 (0) being simple with corresponding eigenvector u1 (0). Then: (λ1 ◦ A)′′ (0) = u1 (0)T A′′ (0)u1 (0) + 2u1 (0)T A′ (0)T λ1 (0)I − A(0) |−1 A′ (0)u1 (0), (379) u1 (0)⊥ where (λ1 (0)I − A(0))|u1 (0)⊥ refers to the restriction of λ1 (0)I − A(0) to the subspace u1 (0)⊥ , on which the inverse makes sense. We also require some additional notation. Given w ∈ F of the form (348), define Γ01 (w) : QL−1 dl −1 QL−1 → Rd0 and Γ10 (w) : l=1 Rdl −1 → RdL by l=1 R Γ01 (w)[z] :=
L−1 X
(L−l−1)/L
σ1
W Tl:1 zl ,
Γ10 (w)[z] :=
l=1
L−1 X
(l−1)/L
σ1
W L:l+1 zl .
(380)
l=1
Proposition E.5. Let w ∈ F be of the form (348). With λ1 := λ1 (Df T Df ), the subspaces L−1 V1 (w) := span v1 (w; a) : a ∈ R ,
(381)
L−1 Y V2 (w) := span v2 (w; b, c) : b, c ∈ Rdl −1 s.t. K1 (w; b) = K2 (w; c)
(382)
l=1
of νw (F ) are invariant under ∇2M λ1 (w), with 2−4/L
spec(∇2M λ1 (w)|V1 (w) ) = 4σ1
,
(383)
spec(∇2M λ1 (w)|V2 (w) ) = solutions µ(w) of generalised eigenproblem H(w)v = µ(w)G(w)v, (384) where, suppressing evaluation at w, 2−2/L
H := 2σ1
IQL−1 Rdl −1 + ΓT01 (λ1 Id0 −1 − ∆01 )−1 Γ01 + ΓT10 (λ1 IdL −1 − ∆10 )−1 Γ10
(385)
l=1
and G := (K1−1 + K2−1 )−1
(386)
are positive-definite. Consequently, λ1 is Morse-Bott along F . Moreover, when L = 2, one has 4σ1 2 spec(∇M λ1 (w)|V2 ) ⊂ ,∞ , (387) σ1 − σdL 1/L
with the lower-bound being met at the balanced solution where W l = diag(σ2 l ∈ [L]. 45
1/L
, . . . , σdL ) for all
!!
Proof. We first demonstrate invariance of the subspaces V1 and V2 . Consider the tuple !L L Y 1 0 L ∈ J := (Jl )l=0 := Rdl ×dl . 0 −Idl −1 l=1
(388)
l=0
This J acts as an involutive isometric symmetry
(389)
DΘ(w)∇2M λ1 (w)[v] = ∇2M λ1 (Θ(w))[DΘ(w)[v]].
(390)
Θ : (W1 , . . . , WL ) 7→ J1 W1 J0 , . . . , JL WL JL−1 of f , hence ∇2M λ1 is equivariant with respect to Θ in the sense that
Since w of the form (348) is fixed by Θ, this equivariance reduces to commutativity: DΘ(w) · ∇2M λ1 (w) = ∇2M λ1 (w) · DΘ(w).
(391)
It is moreover easily checked that DΘ(w) preserves νm (F ). It thus follows that ∇2M λ1 (w) preserves the +1 and −1 eigenspaces of DΘ(w)|νw (F ) , which are precisely V1 (w) and V2 (w) respectively. Having demonstrated invariance of V1 and V2 , we now compute the spectrum of ∇2M λ1 (w) restricted to each of these subspaces. We first consider V1 (w). Fix a ∈ RL−1 , and consider the curve !L 1/L exp(t(a − a ))σ 0 l l−1 1 γ : t 7→ , (392) 0 Wl l=1
where aL = a0 = 0. One then computes λ1 (γ(t)) = λ1 (Df Df T (γ(t))) =
L Y X
2/L
σ1
(393)
exp(2t(am − am−1 )).
(394)
l=1 m̸=l
QL 1/L exp(t(al − al−1 )) = σ1 , implying that Since γ(t) ∈ M for all t, one has l=1 σ1 Q 1/L 1/L exp(t(am − am−1 )) = σ1 / σ1 exp(t(al − al−1 )) , so that m̸=l σ1 λ1 (γ(t)) =
L X
σ12
2−2/L
2/L exp(2t(al − al−1 )) l=1 σ1
= σ1
L X
exp − 2t(al − al−1 ) .
(395)
l=1
Differentiating twice and evaluating at t = 0 then gives 2−2/L
(λ1 ◦ γ)′′ (0) = 4σ1
L X (al − al−1 )2 .
(396)
l=1 2/L PL 2 l=1 (al − al−1 ) , one deduces that
Finally, noting that ∥v1 (w; a)∥2 = σ1
⟨v1 (w; a), ∇2M λ1 (w)v1 (w; a)⟩ 1 2−4/L = (λ1 ◦ γ)′′ (0) = 4σ1 , 2 ∥v1 (w; a)∥ ∥v1 (w, a)∥2 2−4/L
so that spec(∇2M λ1 (w)|V1 (w) ) = 4σ1
(397)
as claimed.
We now turn to computing the spectrum of ∇2M λ1 (w)|V2 (w) . Fix b, c ∈ K1 (w)[b] = K2 (w)[c], and set b0 = c0 = bL = cL = 0. Define 0 bTl Al := ∈ Rdl ×dl , l = 1, . . . , L − 1, cl 0
QL−1 l=1
Rdl −1 with
and set A0 := 0 ∈ Rd0 ×d0 and AL := 0 ∈ RdL ×dL . Consider the curve in the chart of Proposition E.3 L L t 7→ w(t) := Wl (t) l=1 := exp(tAl )Wl exp(−tAl−1 ) l=1 . (398) 46
Then w(0) = w and Ẇl (0) = Al Wl − Wl Al−1 =
0 1/L σ1 cl − W l cl−1
1/L
W Tl bl − σ1 0
bl−1
T ! ,
(399)
so that ẇ(0) = v2 (w; b, c) as required. Since the intermediate exponentials telescope, one has WL:l+1 (t) = WL:l+1 exp(−tAl ), Wl−1:1 (t) = exp(tAl−1 )Wl−1:1 . Writing zl := bl + cl for l = 0, . . . , L, note that 0 zlT T Al + A l = , zl 0
(400)
(401)
and T b c + ∥cl ∥2 = l l 0 2 T 1 b c + ∥bl ∥2 Al ATl + A2l + (ATl )2 = l l 0 2 1 ATl Al +
A2l + (ATl )2
0 , 1 T T T 2 cl bl + bl cl + 2bl bl 0 . 1 T c b + b cTl + 2cl cTl l l l 2
(402) (403)
Using the expansions exp(tA) = I +tA+ 21 t2 A2 +O(t3 ) and exp(−tA) = I −tA+ 12 t2 A2 +O(t3 ), it follows that 1 exp(tATl−1 ) exp(tAl−1 ) = I + t(Al−1 + ATl−1 ) + t2 ATl−1 Al−1 + (A2l−1 + (ATl−1 )2 ) + O(t3 ), 2 (404) 1 (405) exp(−tAl ) exp(−tATl ) = I − t(Al + ATl ) + t2 Al ATl + (A2l + (ATl )2 ) + O(t3 ). 2 Hence, defining ! (l−1)/L T 0 σ1 zl−1 W l−1:1 Pl := , (406) (l−1)/L W Tl−1:1 zl−1 0 σ1 ! (L−l)/L T 0 σ1 zl W TL:l+1 Ql := , (407) (L−l)/L σ1 W L:l+1 zl 0 2(l−1)/L σ1 bTl−1 cl−1 + ∥cl−1 ∥2 0 Rl := , 1 T T T T 0 2 W l−1:1 bl−1 cl−1 + cl−1 bl−1 + 2bl−1 bl−1 W l−1:1 (408) 2(L−l)/L T 2 σ1 bl cl + ∥bl ∥ 0 T , (409) Sl := 1 T T T W b c + c 0 L:l+1 l l l bl + 2cl cl W L:l+1 2 one obtains T Wl−1:1 + tPl + t2 Rl + O(t3 ), (410) Wl−1:1 (t)T Wl−1:1 (t) = Wl−1:1 T WL:l+1 (t)WL:l+1 (t)T = WL:l+1 WL:l+1 − tQl + t2 Sl + O(t3 ).
(411)
Therefore Df Df T (w(t)) =
L X
WL:l+1 (t)WL:l+1 (t)T ⊗ Wl−1:1 (t)T Wl−1:1 (t)
(412)
T T WL:l+1 WL:l+1 ⊗ Wl−1:1 Wl−1:1
(413)
l=1
=
L X l=1
+t
L X
T T WL:l+1 WL:l+1 ⊗ Pl − Ql ⊗ Wl−1:1 Wl−1:1
(414)
l=1
+ t2
L X T T WL:l+1 WL:l+1 ⊗ Rl + Sl ⊗ Wl−1:1 Wl−1:1 − Ql ⊗ Pl + O(t3 ). l=1
(415) 47
Let E00 := e1 eT1 ∈ RdL ×d0 , where the first e1 is the first standard basis vector in RdL and the second is the first standard basis vector in Rd0 . Then E00 , (Df Df T ◦ w)′′ (0)E00 = 2
L X
2(L−l)/L 2(l−1)/L σ1
σ1
bTl−1 cl−1 + ∥cl−1 ∥2 + bTl cl + ∥bl ∥2
l=1
(416) L X
2−2/L
= 2σ1
∥bl ∥2 + ∥cl ∥2 + 2bTl cl
(417)
l=1 L−1 X
2−2/L
= 2σ1
∥zl ∥2 .
(418)
l=1
On the other hand, (Df Df T ◦ w)′ (0)E00 =
L X
2(L−l)/L
σ1
E00 Pl −
l=1
2(l−1)/L
Ql E00 σ1
(419)
l=1
1−1/L = σ1
L X l=1
1−1/L
= σ1
L X
(L−l)/L T zl−1 W l−1:1
0 (l−1)/L −σ1 W L:l+1 zl
σ1
Γ01 (w)[z]T 0
0 −Γ10 (w)[z]
!
0 ,
(420) (421)
where z := (zl )L−1 l=1 = b + c. 2−2/L
Applying Lemma E.4, and using that λ1 (w) = Lσ1 while the restriction of λ1 (w)I − Df Df T (w) to the top-right and bottom-left blocks is λ1 (w)I − ∆01 (w) and λ1 (w)I − ∆10 (w) respectively, gives 2−2/L (λ1 ◦ w)′′ (0) = 2σ1 ∥z∥2 + Γ01 (w)[z], (λ1 (w)I − ∆01 (w))−1 Γ01 (w)[z] (422) + Γ10 (w)[z], (λ1 (w)I − ∆10 (w))−1 Γ10 (w)[z] (423) (424)
= ⟨z, H(w)z⟩, where 2−2/L
H(w) := 2σ1
I + Γ01 (w)T (λ1 (w)I − ∆01 (w))−1 Γ01 (w) + Γ10 (w)T (λ1 (w)I − ∆10 (w))−1 Γ10 (w) . (425)
Finally, since K1 (w)[b] = K2 (w)[c], setting δ := K1 (w)[b] = K2 (w)[c] gives Hence so that
z = b + c = (K1 (w)−1 + K2 (w)−1 )δ. δ = (K1 (w)−1 + K2 (w)−1 )−1 z = G(w)z, b = K1 (w)−1 G(w)z,
c = K2 (w)−1 G(w)z.
Therefore ∥ẇ(0)∥2 = ⟨b, K1 (w)b⟩ + ⟨c, K2 (w)c⟩ = ⟨b + c, G(w)z⟩ = ⟨z, G(w)z⟩. Thus the spectrum of ∇2M λ1 (w)|V2 (w) consists of the critical values of the Rayleigh quotient z 7→
⟨z, H(w)z⟩ , ⟨z, G(w)z⟩ 48
(426)
equivalently the solutions of the generalised eigenvalue problem H(w)z = µ G(w)z. Since H(w) and G(w) are positive-definite, all such eigenvalues are strictly positive. Finally, we consider the special case of L = 2. In this case, Γ01 (w) = W T1 , Γ10 w) = W 2 , λ1 |F = 2σ1 , ∆01 (w) = σ1 I + W T1 W 1 and ∆10 (w) = σ1 I + W 2 W T2 so that H(w) = 2σ1 (Id1 + W 1 (σ1 Id1 − W T1 W 1 )−1 W T1 + W T2 (σ1 Id1 − W 2 W T2 )−1 W 2 ),
(427)
and G(w) = (σ1 Id1 + W 1 W T1 )−1 + (σ1 Id1 + W T2 W 2 )−1
−1
.
(428)
Substituting A := W 1 W T1 and B := W T2 W 2 and using a singular value decomposition, one sees that H(w) = 2σ1 (I + A(σ1 I − A)−1 + B(σ1 I − B)−1 ).
(429)
Fixing z ∈ Rd1 , we now lower-bound ⟨z, H(w)z⟩ and upper-bound ⟨z, G(w)z⟩. Defining a := ⟨z, Az⟩ and b := ⟨z, Bz⟩, one has 0 < a, b < σ1 . To lower-bound ⟨z, H(w)z⟩, note that the function h(t) := t/(σ1 − t) is convex on (0, σ1 ), so by Jensen’s inequality applied to the spectral measures of A and B one has ⟨z, h(A)z⟩ ≥ h(⟨z, Az⟩) =
a , σ1 − a
⟨z, h(B)z⟩ ≥ h(⟨z, Bz⟩) =
b , σ1 − b
(430)
so that ⟨z, H(w)z⟩ ≥ 2σ1
b a + . 1+ σ1 − a σ1 − b
(431)
To upper-bound ⟨z, G(w)z⟩ it suffices to lower-bound ⟨z, G(w)−1 z⟩. Running the same argument as before using the convex function t 7→ 1/(σ12 + t), one has ⟨z, G(w)z⟩−1 ≥
1 1 + . σ1 + a σ1 + b
(432)
Thus ⟨z, H(w)z⟩ 1 a b 1 ≥ 2σ1 + 1+ + . (433) ⟨z, G(w)z⟩ σ1 + a σ1 + b σ1 − a σ1 − b √ Subject to the constraint ab ≥ σd enforced by the fact that w is a solution to the factorisation problem, this bound is maximised at a = b = σd , giving ⟨z, H(w)z⟩ 4σ1 ≥ . ⟨z, G(w)z⟩ σ1 − σd
(434)
Finally, direct substitution reveals that this lower-bound is achieved by the balanced solution w = 1/L 1/L L diag(σ1 , . . . , σdL ) l=1 . We now recall the function α defined in Assumption 3.5 by the formula 2 1 4 ⊗4 ⊗2 ⊗2 3 3 αη (x) := D ℓ[ν1 , Aη ∇ ℓ[ν1 ]](x) + D ℓ[ν1 ](x) 1 − ηλ1 (x) 3
(435)
for all x ∈ M and η in a neighbourhood of 2/λ1 (x), where Aη (x) := λ1 (x)−1 (1 − ηλ1 (x))−1 ν1 (x)ν1 (x)T + ν2:q (x)(λ1 (x)I − ∇2 ℓ(x))ν2:q (x)T
(436)
and where ν1:q = (ν1 , ν2:q ) is an orthonormal frame field for ν(M \ S) where ν1 is a top eigenvector field for Df T Df . In order to carry out computations of αη in our matrix factorisation example, we introduce some notation. 49
Speaking generally, given symmetric multilinear maps A and B taking k and l inputs respectively and taking values in an inner product space V , we will denote X 1 ⟨A ⊙ B⟩[v1 , . . . , vk+l ] := ⟨A[vπ(1) , . . . , vπ(k) ], B[vπ(k+1) , . . . , vπ(k+l) ]⟩ (437) (k + l)! π∈Π(k+l)
where Σ(k + l) denotes the set of all permutations of k + l elements. Then in the general setup of Subsection 3.2, since ℓ = 21 ⟨f − τ, f − τ ⟩ one has Dℓ = ⟨Df, f − τ ⟩ ⇒ Dℓ|M ≡ 0,
(438)
D2 ℓ = ⟨Df ⊙ Df ⟩ + ⟨D2 f, f − τ ⟩ ⇒ D2 ℓ|M = ⟨Df ⊙ Df ⟩,
(439)
D3 ℓ = 3⟨D2 f ⊙ Df ⟩ + ⟨D3 f, f − τ ⟩ ⇒ D3 ℓ|M = 3⟨D2 f ⊙ Df ⟩,
(440)
D4 ℓ = 4⟨D3 f ⊙ Df ⟩ + 3⟨D2 f ⊙ D2 f ⟩ + ⟨D4 f, f − τ ⟩ ⇒ D4 ℓ|M = 4⟨D3 f ⊙ Df ⟩ + 3⟨D2 f ⊙ D2 f ⟩. (441) QL For the matrix factorisation function f : l=1 Rdl ×dl−1 → RdL ×d0 of (333), at a point w = i (W1 , . . . , WL ) and for tangent vectors ξ i := (ξ1i , . . . , ξL ), i = 1, . . . , k, one in particular has X X σ(1) σ(k) WL:lk +1 ξlk Wlk −1:lk−1 +1 · · · Wl2 −1:l1 +1 ξl1 Wlk −1:1 . Dk f (w)[ξ 1 , . . . , ξ k ] = 1≤l1 <···<lk ≤L π∈Π(k)
(442) We now prove that αη has the desired properties. Proposition E.6. For the matrix factorisation model f of (333), the function αη of (435) is constant on F , with 2(L − 1)(7L − 11) 2−4/L 18(L − 1)2 αη |F = + σ1 , (443) (1 − ηλ1 |F )2 3(1 − ηλ1 |F ) for all η in a neighbourhood of 2/λ1 |F , and in particular satisfies 2−4/L 40L − 32 α2/λ1 |F = (L − 1)σ1 >0 3
(444)
for all L ≥ 2. Moreover, Dαη |F = 0. Proof. Since αη is defined solely in terms of derivatives of f and in terms of the metric, it suffices to do the computations at a point w of the form (348), i.e. 1/L !L σ 0 1 w= (445) 0 Wl l=1
for some (W 1 , . . . , W L ) ∈ M . It is then clear that one has L 1 ν1 (w) = √ e1 (dl )e1 (dl−1 )T l=1 . L
(446)
We begin by proving that αη is constant on F for all η sufficiently close to 2/λ1 |F . Suppressing evaluation at w for notational convenience, using (442) one computes √ 1−1/L Df [ν1 ] = Lσ1 e1 (dL )e1 (d0 )T , (447) 1−2/L
D2 f [ν1⊙2 ] = (L − 1)σ1
e1 (dL )e1 (d0 )T ,
(448)
and D3 f [ν1⊙3 ] =
(L − 2)(L − 1) 1−3/L √ σ1 e1 (dL )e1 (d0 )T . L 50
(449)
Using (441), these identities imply that D4 ℓ[ν1⊙4 ] = 4⟨D3 f [ν1⊙3 ], Df [ν1 ]⟩ + 3⟨D2 f [ν1⊙2 ], D2 f [ν1⊙2 ]⟩ 2−4/L = (L − 1)(7L − 11)σ1 .
To compute the term D ℓ[ν1⊙2 , A∇3 ℓ[ν1⊙2 ]], using QL (h1 , . . . , hL ) ∈ l=1 Rdl ×(dl −1) , one computes 3
D2 f [ν1 , h] =
L 1−2/L X
σ1 √
L
X
(450) (451)
(442) and fixing a tangent vector h =
e1 (dl )T hl e1 (dl−1 ) e1 (dL )e1 (d0 )T + B,
(452)
l1 =1 l2 ̸=l1
and 1−1/L
Df [h] = σ1
X L
e1 (dl )T hl e1 (dl−1 ) e1 (dL )e1 (d0 )T + B ′
(453)
l=1
where B, B ′ ∈ e1 (dL )e1 (d0 )T
⊥
. Then by (440) one has
D ℓ[ν1⊙2 , h] = 2⟨D2 f [ν1 , h], Df [ν1 ]⟩ + ⟨D2 f [ν1⊙2 ], Df [h]⟩ L X 2−3/L e1 (dl )T hl e1 (dl−1 ) = 3(L − 1)σ1 3
√
l=1 √ 2−3/L ⟨ν1 , h⟩. = 3 L(L − 1)σ1
(454) (455) (456)
2−3/L
It follows that ∇3 ℓ[ν1⊙2 ] = 3 L(L − 1)σ1
ν1 , hence that √ 2−3/L 3 L(L − 1)σ1 A∇3 ℓ[ν1⊙2 ] = ν1 , λ1 (1 − ηλ1 )
(457)
implying further that 3 D ℓ[ν1⊙2 , A∇3 ℓ[ν1⊙2 ]] = 3
√
2−3/L
L(L − 1)σ1 λ1 (1 − ηλ1 )
D3 ℓ[ν1⊙3 ]
(458)
4−6/L
=
9L(L − 1)2 σ1 λ1 (1 − ηλ1 )
=
9(L − 1)2 σ1 1 − ηλ1
(459)
2−4/L
2−2/L
with the final line following from λ1 |F = Lσ1 claimed formula for αη .
,
(460)
. Putting everything together, one arrives at the
We now move on to proving that Dαη (w) = 0. Since αη |F is constant, it suffices to show that Dαη (w) kills the normal directions to F as worked out in Proposition E.3. Recall from Proposition E.5 that νw (F ) splits into subspaces V1 (w) and V2 (w) consisting of modifications to the top-left entries of the factors and of rotations of their corresponding singular vectors respectively. It is relatively easy to show that Dαη (w)|V2 (w) ≡ 0. Recall the isometry Θ from (389), under which f is invariant and for which DΘ(w) has −1 eigenspace precisely equal to V2 (w). Since f is invariant and since Θ(w) = w, Dα(w) if also invariant under Θ so that for any ξ ∈ V2 one has Dαη (w)[ξ] = Dαη (w)[DΘ(w)ξ] = −Dαη (w)[ξ],
(461)
implying that Dαη (w)[ξ] = 0 and hence that Dαη (w)|V2 (w) ≡ 0. L−1 We now turn to demonstrating Dαη (w)|V1 (w) ≡ 0. Fix a tuple a = (al )L−1 and for l=1 ∈ R notational convenience denote rl := al − al−1 for all l = 1, . . . , L, where we set a0 , aL := 0. As in Proposition E.5, we consider the curve !L 1/L exp(tr )σ 0 l 1 γ : t 7→ , (462) 0 Wl l=1
51
with γ(0) = w, and evaluate αη (γ(t)). To this end, we denote Sj (t) :=
L X
exp(−2jtrl ),
j = 1, 2, 3.
(463)
l=1
One has ν1 (γ(t)) =
1 ∥Df (w(t))T [e1 (dL )e1 (d0 )T ]∥
Df (w(t))T [e1 (dL )e1 (d0 )T ]
L = S1 (t)−1/2 exp(−trl )e1 (dl )e1 (dl−1 )T l=1 .
(464) (465)
From now on, we suppress evaluation at γ(t) for notational convenience. Using the fact that QL l=1 exp(trl ) = σ1 , note that for any tuple l1 < · · · < lk one has Y
exp(trm ) =
k Y
exp(−trlj ).
(466)
j=1
m̸=l1 ,...,lk
We now turn to computing the quantities appearing in (435). Invoking (442) gives Df [ν1 ] =
X L
−1/2 1−1/L S1 exp(−trl )σ1
l=1
Y
exp(trm ) e1 (dL )e1 (d0 )T
(467)
m̸=l
−1/2 1−1/L σ1
= S1
X L
exp(−2trl ) e1 (dL )e1 (d0 )T
(468)
l=1 1−1/L
= σ1
1/2
S1 e1 (dL )e1 (d0 )T
(469)
by invoking (466) for the second line. Similarly, invoking (442) and (466) gives 1−2/L −1 S1 D f [ν1⊙2 ] = σ1 2
X L X
exp(−trl1 ) exp(−trl2 )
l1 =1 l2 ̸=l1
Y
exp(trm ) e1 (dL )e1 (d0 )T
m̸=l1 ,l2
(470) 1−2/L
= σ1
S1−1
X L
X exp(−2trl1 ) exp(−2trl2 ) e1 (dL )e1 (d0 )T
2 1−2/L S1 − S2
= σ1
by using the identity
S1
e1 (dL )e1 (d0 )T
P
P
l1 ̸=l2 pl1 pl2 =
−3/2 1−3/L σ1
D3 f [ν1⊙3 ] = S1
(471)
l2 ̸=l1
l1 =1
X L X
l pl
2
X
(472) −
2 l pl for the final line, and
P
exp(−t(rl1 + rl2 + rl3 ))
l1 =1 l2 ̸=l1 l3 ̸=l2 ,l1
Y
exp(trm ) e1 (dL )e1 (d0 )T
m̸=l1 ,l2 ,l3
(473) −3/2 1−3/L σ1
= S1
X
exp(−2t(rl1 + rl2 + rl3 )) e1 (dL )e1 (d0 )T
(474)
l1 ̸=l2 ̸=l3 3 1−3/L S1 − 3S2 S1 + 2S3 e1 (dL )e1 (d0 )T 3/2 S1
= σ1
(475)
P P 3 P P 2 P 3 by using the identity l1 ̸=l2 ̸=l3 pl1 pl2 pl3 = −3 l pl l pl l pl + 2 l pl for the final line. It follows from (441) that 3 2 2 S − 3S1 S2 + 2S3 S − S2 2−4/L D4 ℓ[ν1⊙4 ] = σ1 4 1 +4 1 . (476) S1 S1 52
Finally, we come to computing the term D3 ℓ[ν1⊙2 , A∇3 ℓ[ν1⊙2 ]]. For arbitrary h = (h1 , . . . , hL ) ∈ QL dl ×dl−1 , using (442) and (466) one has l=1 R X L Y 1−1/L Df [h] = σ1 exp(trm ) e1 (dl )T hl e1 (dl−1 ) e1 (dL )e1 (d0 )T + C (477) l=1 m̸=l 1−1/L
= σ1
X L
exp(−trl ) e1 (dl )T hl e1 (dl−1 ) e1 (dL )e1 (d0 )T + C
(478)
l=1
⊥ for some C ∈ e1 (dL )e1 (d0 ) , and X L X Y 1−2/L −1/2 S1 exp(−trl1 ) e1 (dl2 )T hl2 e1 (dl2 −1 ) exp(trm ) e1 (dL )e1 (d0 )T + C ′ D2 f [ν1 , h] = σ1 l=1 l2 ̸=l1
1−2/L
= σ1
−1/2
S1
X L X
m̸=l1 ,l2
(479) exp(−t(2rl1 + rl2 ))e1 (dl2 )T hl2 e1 (dl2 −1 ) e1 (dL )e1 (d0 )T + C ′
l1 =1 l2 ̸=l1
(480) ⊥ for some C ′ ∈ e1 (dL )e1 (d0 ) . By (440), it follows that D3 ℓ[ν1⊙2 , h] = 2⟨D2 f [ν1 , h], Df [ν1 ]⟩ + ⟨D2 f [ν1⊙2 ], Df [h]⟩ (481) 2 X L S − S2 2−3/L exp(−trl ) 1 = σ1 + 2(S1 − exp(−2trl )) e1 (dl )T hl e1 (dl−1 ), S1 l=1 (482) so that ∇ ℓ[ν1⊙2 ] = 3
2−3/L σ1 exp(−trl )
L S12 − S2 T + 2(S1 − exp(−2trl )) e1 (dl )e1 (dl−1 ) . S1 l=1 (483)
Since each of the components of this tuple is nonzero only in the top-left entry, its projection into the span of ν2:q is zero while its projection into the span of ν1 is given by 2 2−3/L S1 − S2 1/2 S1
ν1T ∇3 ℓ[ν1⊙2 ] = D3 ℓ[ν1⊙3 ] = 3σ1
(484)
by (440), hence −1 D3 ℓ[ν1⊙2 , A∇3 ℓ[ν1⊙2 ]] = λ−1 D3 ℓ[ν1⊙3 ] 1 (1 − ηλ1 ) 2−4/L 9σ (S12 − S2 )2 = 1 (1 − ηλ1 )S12 2−2/L
after substituting λ1 = σ1
2
(485) (486)
S1 . Thus, along the curve γ(t) one has
2−4/L 2σ 9(S12 − S2 )2 4(S13 − 3S2 S1 + 2S3 ) (S12 − S2 )2 αη = 1 + + . (487) 1 − ηλ1 (1 − ηλ1 )S12 3S1 S12 PL PL Finally, note that for any j = 1, 2, 3 one has Ṡj (0) = −2j l=1 rl = −2j l=1 (al − al−1 ) = 0 2−2/L since a0 = aL = 0, and similarly λ˙1 (0) = σ1 Ṡ1 (0) = 0. It follows that α̇η (0) = 0, thus completing the proof. Finally, we prove that the additional Assumption D.12 required for Theorem D.13 holds for deep matrix factorisation. At a point w ∈ F of the form (348), consider the chart !L 1/L σ1 0 T φ(A, Q) := Ql Ql−1 (488) 0 Al W̄ A−1 l−1 l=1
53
defined for any Q ∈ O(d) sufficiently close to the identity and rotating the first basis vector into any of the other basis directions, and any A ∈ GL(d − 1) sufficiently close to the identity. By Proposition E.5, the smallest eigenspace (at least when L = 2) of ∇2 λ1 (φ(A, Q)) is ( !L ) 1/L σ (a − a ) 0 T L−1 l l−1 1 V1 (φ(A, Q)) = span Ql Ql−1 :a∈R . (489) 0 0 l=1
Using the local frame for V1 |range(φ) defined by the standard basis in RL−1 and exponentiating, one obtains the V1 -exponentiated chart !L 1/L eul −ul−1 σ1 0 T ψ(A, Q, u) := Ql Ql−1 (490) 0 Al W̄l A−1 l−1 l=1
L−1
defined for u ∈ R sufficiently close to zero and all A, Q as above sufficiently close to the identity that the range of ψ is contained in M \ S. On the range of ψ, the top eigenvector field ν1 of ∇2 ℓ is given by L ν1 (ψ(A, Q, u)) = αl (u)e1 (dl )e1 (dl−1 )T l=1 , (491) where e1 (d) denotes the first standard basis vector in Rd and where e−(ul −ul−1 ) αl (u) := qP L −2(ul −ul−1 ) l=1 e
(492)
is independent of A, Q. We thus finally consider the exponentiated chart ϕ(A, Q, u, y) := ψ(A, Q, u) + yν1 (ψ(A, Q, u)) !L 1/L eul −ul−1 σ1 + yαl (u) 0 = Ql QTl−1 . 0 Al W̄l A−1 l−1
(493) (494)
l=1
Proposition E.7. At a point w ∈ F of the form (348), consider the chart (494). For any η > 0, there is a subset U ⊂ dom(ϕ) such that GD(η, U ) ⊂ range(ϕ), and in the coordinates (A, Q, u, y) one has GDA,Q (η, A, Q, u, y) = (A, Q),
GDu,y (η, A, Q, u, y) = g(η, u, y)
(495)
for some C ∞ function g independent of A and Q. In particular, Assumption D.12 holds when L = 2. Proof. Writing 1/L
βl (u) := σ1 eul −ul−1 , with the convention u0 = uL = 0, one computes GD(η, ϕ(A, Q, u, y)) =
Ql
l ∈ [L],
βl (u) + yαl (u) + hl (u, y) 0
!L 0 QTl−1 Al W̄l A−1 l−1
(496)
l=1
for some C ∞ functions hl (u, y) independent of A and Q. ϕ(A, Q, u, 0), one has hl (u, 0) = 0, ∀l ∈ [L]. Thus it suffices to show that the map Φ : RL−1 × R → RL ,
Since GD(η, ϕ(A, Q, u, 0)) =
L (u, y) 7→ βl (u) + yαl (u) l=1
is a local diffeomorphism at every point (u, 0). We first compute the Jacobian of Φ at (u, 0). Since l = j, βj (u), ∂uj βl (u) = −βj+1 (u), l = j + 1, 0, otherwise, 54
(497)
for each j ∈ [L − 1], it follows that ∂uj Φ(u, 0) = βj (u)ej − βj+1 (u)ej+1 ,
(498)
where e1 , . . . , eL denotes the standard basis of RL . Moreover, L ∂y Φ(u, 0) = αl (u) l=1 . Hence ··· .. . −β2 (u) β2 (u) . DΦ(u, 0) = 0 −β3 (u) . . . .. .. . . . . 0 ··· 0 β (u)
0
1
0 .. . 0 βL−1 (u) −βL (u)
α1 (u) α2 (u) .. . . αL−1 (u) αL (u)
(499)
Factoring βl (u) out of the lth row gives det DΦ(u, 0) =
L Y
! βl (u) det B(u),
(500)
l=1
where 1
0
−1 B(u) := 0 . . . 0
1 −1 .. . ···
··· .. . .. . .. . 0
0 .. . 0 1 −1
α1 (u)/β1 (u)
α2 (u)/β2 (u) .. .
. αL−1 (u)/βL−1 (u) αL (u)/βL (u)
(501)
Now, for each l ∈ [L], replace the lth row of B(u) by the sum of the first l rows. Since this is achieved by left multiplication by a lower-triangular matrix with diagonal entries all equal to 1, the determinant is unchanged. One obtains the matrix 1 0 ··· 0 γ1 (u) . .. 0 1 . .. γ1 (u) + γ2 (u) . .. .. e , .. B(u) = (502) .. . . 0 . PL−1 0 · · · 0 1 γm (u) Pm=1 L 0 ··· ··· 0 m=1 γm (u) where γl (u) :=
αl (u) . βl (u)
Thus e det B(u) = det B(u) =
L X αl (u) l=1
βl (u)
.
(503)
We now use the explicit formula for the coefficients αl (u) of the top singular vector, namely αl (u) = qP
e−(ul −ul−1 )
,
l ∈ [L].
(504)
L −2(um −um−1 ) m=1 e
1/L ul −ul−1
Since βl (u) = σ1
e
, one has αl (u) e−2(ul −ul−1 ) −1/L qP = σ1 . βl (u) L −2(um −um−1 ) e m=1 55
(505)
Summing over l therefore yields L X αl (u) l=1
βl (u)
v u L uX −1/L t =σ e−2(ul −ul−1 ) . 1
(506)
l=1
On the other hand, L Y
βl (u) =
l=1
L Y
1/L ul −ul−1
σ1
e
= σ1 euL −u0 = σ1 ,
l=1
since u0 = uL = 0. Substituting these identities into the preceding formula for det DΦ(u, 0) gives v u L uX 1−1/L t det DΦ(u, 0) = σ1 e−2(ul −ul−1 ) > 0. (507) l=1
Thus DΦ(u, 0) is invertible for every u ∈ RL−1 . By the inverse function theorem, for each u there exist neighbourhoods Uu of (u, 0) and Vu of Φ(u, 0) such that Φ : Uu → Vu is a C ∞ diffeomorphism. Since hl (u, 0) = 0 for all l, shrinking Uu if necessary ensures that L βl (u) + yαl (u) + hl (u, y) l=1 ∈ Vu , ∀(u, y) ∈ Uu . Hence on Uu one may define gu (η, u, y) := Φ−1
L βl (u) + yαl (u) + hl (u, y) l=1 ,
(508)
which is C ∞ and independent of A and Q. By uniqueness of the inverse, the maps gu agree on overlaps, and therefore glue to a global C ∞ map [ U := g : U → RL−1 × R, Uu . u∈RL−1
Setting U := ϕ dom(A, Q) × U ⊂ dom(ϕ), it follows that GD(η, U ) ⊂ range(ϕ) and that, in the coordinates (A, Q, u, y), GDA,Q (η, A, Q, u, y) = (A, Q),
GDu,y (η, A, Q, u, y) = g(η, u, y),
(509)
as claimed. The final statement for L = 2 is immediate.
F
Experimental supplement
Our experimental results can be reproduced by running neurips26_plots.py, which runs the experiments and plots everything with a log-y scale. To obtain the log-log scale for the critical experiment, run plotting_script.py. All experiments can be run on a single CPU in minutes.
56