Normalization layers are ubiquitous and play a fundamental role in modern deep learning, e.g., Batch Normalization (Ioffe & Szegedy, 2015), Group Normalization (Wu & He, 2018), Layer Normalization (Ba et al., 2016), and Weight Normalization (Salimans & Kingma, 2016). Normalization layers not only greatly facilitate optimization and improve trainability, it also brings intriguing new optimization behaviors to neural networks. For example, Li & Arora (2020) showed that normalized networks can be trained by SGD with exponentially increasing learning rates, because training with exponentially increasing learning rates turns out to be equivalent to training with constant learning rates but with weight decay turned on, as shown in (2). Here x k ∈ R d is the parameter of a neural network after the k-th step and is updated by
where λ and η are respectively the weight decay parameter and the learning rate, and L B k is the loss function evaluated using a randomly chosen mini-batch B k .
The result of Li & Arora (2020) holds not only for normalized networks but more broadly for all scale invariant training losses, which is a popular abstraction of normalized networks in optimization analysis. Mathematically, scale invariance refers to the following property of the loss: L B (cx) = L B (x), ∀c > 0, x ∈ R d and every batch B.
Later, Li et al. (2020); Wan et al. (2021) discovered that it is the intrinsic learning rate ηλ that controls the long-term convergence behavior for SGD on scale invariant loss with weight decay, (1). The approach that Li et al. (2020) takes to study (1) is to approximate by the stochastic differential equation (SDE) model Li et al. (2017;2019), which is quite common in literature.
dX t = (-η∇L(X t ) -ηλX t )dt -ησ(X t )dB K t .
(2)
Here L is the average
is a d × K matrix, and B K t is the K-dimensional Wiener process. Scale invariance of L B implies that L is scale-invariant and that σ is (-1)-homogeneous, i.e. L(cx) = L(x), σ(cx) = c -foot_0 σ(x), ∀c > 0, x ∈ R d .
(3) Li et al. (2020) further proposed the following Fast Equilibrium Conjecture for the SDE approximation of SGD. Conjecture 1.1. [Fast Equilibrium Conjecture] (Li et al., 2020) If F (X, input) denotes the output of a neural network NN with parameters X, and X t denotes the value of SDE (2) at time t, starting from initial parameter X 0 . Suppose NN has normalization steps so that the F (X, input) is scaleinvariant in X, i.e. F (X, input) = F (cX, input) for all c > 0. Then for all input values input, the probability distribution of F (X t , input) stabilizes to an equilibrium in O( 1 ηλ ) steps of SGD updates.
Experiments where the empirically observed rates of convergence are polynomial were contained in the original paper Li et al. (2020) where the Fast Equilibrium Conjecture was first asked. The rate O( 1 ηλ ) is considered to be fast because according to Langevin dynamics, the time it takes to converge to the Gibbs equilibrium is of exponential order e O((ηλ) -1
2 ) . This can be done by following a similar analysis to those in (Bovier et al., 2004;Shi et al., 2020). The works by (Bovier et al., 2004) and (Shi et al., 2020) dealt with models without normalization, and the convergence times there are of order e O((ηλ) -1 ) . Using the similar method as in (Bovier et al., 2004) and (Shi et al., 2020), when normalization is used the convergence time can be shown to be of order e O((ηλ) -1
2 ) . This is because Li et al. (2020) proved that the intrinsic learning rate ηλ is replaced by an effective learning rate (γ Li et al. (2020)) for the renormalized parameter vector, which is of order O((ηλ)
The recent paper (Li et al., 2022c), using a mathematical framework from (Li et al., 2022b), established the fast equilibrium conjecture for ηλ → 0 under a mixed set of generic and non-generic assumptions. See (Damian et al., 2021), (Gu et al., 2022) for more work on analyzing the dynamics of SGD near the manifold of minimizers. The goal of the current paper is to remove the non-generic ones and thus provide a general proof in the aforementioned range of parameters.
To introduce assumptions from previous authors as well as our results, we need to set up a few notations first. Let Γ ⊆ R d \{0} be the set of local minima of L. Notice that by (3), Γ is a cone, i.e.
x ∈ Γ if and only if cx ∈ Γ for all c > 0. For all r > 0, write Γ r = {x ∈ Γ : |x| = r}. In particular Γ 1 is a subset of the unit sphere S d-1 = {|x| = 1}.
In general, Γ may have multiple connected components. Decompose Γ = Γ i where each Γ i is a connected cone. We then write Γ i r = Γ i ∩ {|x| = r}. Then Γ i 1 are the connected components of Γ 1 . In particular, there are only finitely many Γ i 's and we index them by i = 1, • • • , m.
In addition to the scaling properties (3) guaranteed by the use of normalization, (Li et al., 2022c) made certain assumptions, which we will need in the following. Assumption 1.2. The functions L and σ satisfy: (ii). (Regular critical locus) Each loss function L B k is C 4 on R d \{0}, the critical points of L form a C 2 submanifold Ω. 1 For all x ∈ Ω, ∇ 2 L(x) is of rank d -dim T x Ω.
(iii). (Controllability) For all x ∈ Γ 1 , span{∂Φ(x)σ k (x)} K k=1 = T x Γ 1 . Here and below, Φ(x) = lim t→∞ X t , with X t being the solution to the deterministic gradient descent X t = -∇L(X t ) with initial value x.
By (Arora et al., 2022, Lemma B.15), under Assumption 1.2.(i) & (ii), Φ is well defined and C 2differentiable on a neighborhood of Γ as long as L is C 4 differentiable. We also note that in general the noise structure does affect the convergence rate. But as long as Assumption 1.2 (iii) is satisfied, the noise structure won't affect the asymptotic order of the convergence rate.
On the other hand, we will not need the following assumptions.
Assumption 1.3. Γ satisfies:
(i). (Unique basin) Γ 1 is compact and connected;
(ii). (Analyticity) Γ is a real analytic manifold and Tr Σ is a real analytic function on R d \{0} where Σ = σσ ⊤ .
Restricting to an attracting basin U of Γ and assuming both Assumptions 1.2 and 1.3, Li et al. (2022c) proved Conjecture 1.1 when λη → 0 in the natural range of η ≤ O(λ) ≤ O(1) and the parameter X 0 is initialized within U . Note that since U is an attracting basin, Ω and Γ coincide in U and thus Assumption 1.2 is equivalent to (Li et al., 2022c, Assumption 2.1) for the purpose of that paper. Note that Γ is always a submanifold of Ω.
Remark 1.4. All three assumptions in Assumption 1.2 are very natural for the following reasons:
• As remarked earlier, the scale-invariance (3) is a consequence of the use of normalization steps inside neural networks.
• It is a widely used assumption, at least in the case of local minimizers, that the locus is a manifold for overparametrized neural networks, for example in (Fehrman et al., 2020;Arora et al., 2022;Li et al., 2022b). For the locus of global minimizers, this assumption was proved by Cooper (2021). As remarked in (Li et al., 2022b;Cooper, 2021), a main reason for the local minimizers to form manifolds is the overparametrization of modern neural networks. S ¸ims ¸ek et al. ( 2021) further identifies the reason as symmetries arising from overparametrization. In fact, they studied loci of critical points that are not necessarily minima and proved that symmetry-induced critical points form a manifold that satisfies Assumption 1.2.(ii).
• The philosophy behind Assumption 1.2.(iii) is that the generation of random batches in training is independent of the aforementioned symmetries in the setup of the neural network, and thus generically should not live in subspaces that are invariant under such symmetries. In particular, the same symmetries are generically capable of move the noises from the random batches to span a tangent space of the same dimension as that of the local manifold of critical points.
Remark 1.5. On the other hand, both conditions in Assumption 1.3 are non-generic:
• Certain evidences from (Draxler et al., 2018) suggests that all local minima appearing in realistic training generically come from connected relatively flat region of small variation in height, so empirically Assumption 1.3.(i) could be a reasonable approximate assumption. However, the experiments in (Draxler et al., 2018, Fig. 5) shows at the same time that in many settings, this region is not completely flat and contains non-trivial saddle points. In particular, there could be multiple disconnected basins. In light of these, it is more reasonable work in the absence of assumption Assumption 1.3.(i).
• The analyticity of the Γ and Tr Σ depends on that of the activation functions chosen in the neural network. While many popular activation functions are real analytic, one may always choose to use functions that are differentiable but not analytic, in which case Assumption 1.3.(ii) is in general not guaranteed.
In this paper, we will give a general proof of Conjecture 1.1 in the same natural range as in (Li et al., 2022c), assuming only the generic conditions from Assumption 1.2. In particular, we will introduce two arguments that respectively remove both hypothesis (Unique basin and Analyticity) in Assumption 1.3.
Here we would like to provide comments on why Assumption 1.3 are restrictive. Assuming analyticity is restrictive because the regularity of the loss function is decided by that of the activation function. Even though popular activation functions such as Sigmoid are analytic, a priori one could use smooth but not analytic functions. The one basin assumption is restrictive as we do not see empirical evidence of proof that L only has one basin. In fact, the experiments at the end of the paper suggests that there are multiple basins.
We would also like to give remarks on why the three assumptions in Assumption 1.2 are essential. (i) is essential because without this assumption, the SDE would not be equivalent to a SDE on the sphere S d-1 , which is crucial to our analysis. Without this assumption, similar analysis can probably be formulated on R d instead of the S d-1 coordinate but there will be new technical obstacles to overcome. Since the original fast equilibrium conjecture was asked for normalized neural nets, we restrict our study to the current setting. (ii) is important because if not a trajectory may stay near a critical point (for example a saddle point) for a very long period of time, it would not be able to converge within a polynomial time. Finally, the reason why we need (iii) is that if the span is not the whole tangent space, but instead a subspace of the tangent space, then the diffusion will be restrained to this subspace, which a priori may be very fractal and existing mathematical theory is not sufficient to guarantee a unique equilibrium in limit.
It is worthy to explain in more details what happens when the basin is not unique, i.e Γ has multiple connected components and Assumption 1.3.(i) fails. In this situation, our analysis generalizes the work of Wang & Wang (2022) and reveals a three-stage equilibrium phenomenon. The most important property of this phenomenon is the mismatching between practical training and theoretical bounds: the equilibrium distribution of network parameters observed in the time window under a realistic budget is both local in space and temporary in time. It is concentrated near the bottom of the same attracting basin containing the initial parameter, and differs from the eventual global Gibbs equilibrium that the distribution of parameters will eventually converge to in exponentially long time. This phenomenon interprets the gap between the empirically based Conjecture 1.1 and the previous theoretical estimate from e.g. (Bovier et al., 2004;Shi et al., 2020). See (Frankle et al., 2020), (Gupta et al., 2019) for more work about the iterates stay in the same basin for a significant amount of time when starting from the same initialization.
The major short-come of (Wang & Wang, 2022) is that, while not relying on the uniqueness of the basin, the arguments therein are subject to other non-generic assumptions, namely: (1) all basins are isolated points; (2) the noise σ is a standard isotropic Gaussian noise.
Our methods allow to remove these assumption simultaneously together with Assumption 1.3. This is made possible by avoiding using the semi-classical analysis of spectra of differential operators, which was developed by Simon (Simon, 1983) and used in an essential way by previous authors in (Bovier et al., 2004;Shi et al., 2020;Wang & Wang, 2022). Instead, our method is purely probabilistic and predicts that the exiting time from a given basin is exponentially long. This method is based on an adaptation of the large deviation principle of Dembo & Zeitouni (2010).
A polar coordinate system has been adopted in (Li et al., 2020) to study the SDE model (2). For this purpose, denote by X t = Xt |Xt| the unit renormalization of X t , and
. By (Li et al., 2020, Theorem 5.1), ( 2) is equivalent to
Recall that Σ = σσ ⊤ is a d × d positive semidefinite symmetric matrix.
One may view the motion of X t as an intrinsic one inside the unit sphere S d-1 , instead of one inside R d . From this perspective, (Wang & Wang, 2022, Theorem 3.1) shows that (4) can be rewritten as an intrinsic SDE on S d-1
where σ(•)
1 2 is a tensor field along S d-1 whose value is given by the restriction of σ(•)
1 2 and ∇ is the gradient operator on S d-1 . (See the remark after (Wang & Wang, 2022, Theorem 3.1) for the meaning of being intrinsic. In particular, ∇L(X t )dt, σ(X t )dB K t are viewed as vector fields along S d-1 .) Remark 2.1. Instead of the term σ(X t )dB K t in (4) and ( 6), the papers (Li et al., 2020;Wang & Wang, 2022) actually used the restriction of Σ(X t ) 1 2 dB d t to S d-1 . However, these two expressions are equivalent as Wiener processes because Σ = σσ ⊤ .
Since ( 6) is a perturbation with Brownian noise of the gradient flow dX t = -γ -1 2 ∇L(X t ) with varying learning rate γ -1 2 t , it makes sense to first understand the constant speed gradient flow X t = -∇L(X t ), (7) which is an ODE on the compact manifold S d-1 . Following earlier notation, the local minima of L on S d-1 is Γ 1 and has connected components
for the attracting basin of Γ i 1 , i.e. the set of X 0 ∈ S d-1 such that the solution X t to (7) with initial value X 0 satisfies lim t→∞ X t ∈ Γ i 1 ). Lemma 2.2. Under Assumption 1.2.(ii), the
The proof of Lemma 2.2 is standard and we left it to the reader. The key observation is that the complement
1 is the union of attracting basins of the connected components of critical points that are not local minima. By Assumption 1.2.(i), those critical points are saddle like and their attracting basins are proper submanifolds.
Note that L is constant on Γ i 1 and Γ i , and
Then U i the attracting basin of Γ i under the gradient flow X t = -∇L(X t ).
(8) By (Arora et al., 2022, Lemma B.15), under Assumption 1.2.(i), U i is open and the function Φ(x) = lim t→∞ X t is C 2 -differentiable on U i .
Definition 2.3. We define the Lipschitz distance between two probability measures µ, ν on a metric space X as
where the Lipschitz norm of a function φ is given by ∥φ∥
.
We are now able to state our main theorem, which is a mutual reinforcement to both (Li et al., 2022c, Theorem 5.5) and (Wang & Wang, 2022, Theorem 4.6). Theorem 2.4. Under Assumption 1.2, for all ϵ > 0 and compact interval [ρ -, ρ + ] ⊂ (0, ∞), there exist a constant c > 0 and a set Λ ⊆
|x0| ∈ Λ, all growth rates K such that K → ∞ as ηλ → 0, and all time values
the random trajectory to (2) with initial value x 0 satisfies dist P X0=x0 (X t ), ν i < ϵ, where ν i is a probability measure supported on the attractor Γ i of the unique attracting basin U i containing x 0 , and ν i only depend on L, σ and i.
Here vol S d-1 is the renormalized volume on the sphere S d-1 so that the total mass of S d-1 is 1.
In this part, we will prove that Assumption 1.3.(ii) on analyticity (which is (Li et al., 2022c, Assumption 5.3)) is unnecessary for (Li et al., 2022c, Theorem 5.4), and thus (Li et al., 2022c, Theorem 1.2) holds without such an assumption as well. Proposition 3.1. Under Assumption 1.2 and Assumption 1.3.(i), the conclusion of (Li et al., 2022c, Theorem 1.2) hold.
For this purpose, we temporarily adopt the setting of (Li et al., 2022c) for now. In other words, Assumption 1.3.(i) is being assumed and Γ 1 is a compact connected submanifold of S d-1 and Γ = {rx : r > 0; x ∈ Γ 1 }. By (Li et al., 2022c, Theorem 4.1) it suffices to prove the (qualitative) mixing of the SDE (Li et al., 2022c, Equation (13)) on Γ towards a unique invariant probability measure.
Using the notations from (Li et al., 2022c, Chapter E.3), this SDE writes:
where f k are certain vector fields along the radial cone
and they span T x Γ ∩ x ∥ = T x Γ |x| for all x ∈ Γ, where Γ r = {x ∈ Γ : |x| = r}, and f 0 has the form
In the proofs from (Li et al., 2022c), analyticity is only used in Chapter F.4, when Tr Σ is not a constant on Γ 1 . In this case, it was proved there (without using analyticity) that Γ * := {y ∈ Γ :
is the unique invariant control set for the control problem corresponding to (9).
Instead of using Kliemann's condition (Kliemann, 1987), which requires the vector field Lie algebra l generated by f 0 , • • • , f N to be of maximal dimension at all points in Γ * and is the reason for the need of analyticity in (Li et al., 2022c), we will use Arnold-Kliemann's condition (Arnold & Kliemann, 1987), which only requires that the vector field Lie algebra l to be of maximal dimensional at one point in Γ * . This condition is true because the projection of f 0 to the radial direction is not constantly 0 if Tr Σ is not a constant. (Otherwise Γ * wouldn't be the unique invariant set.) Under this condition, (Arnold & Kliemann, 1987, Theorem 5.1) proved that there is a unique invariant probability measure ν supported on Γ * . The measure ν then has to be ergodic. Moreover, (Arnold & Kliemann, 1987, Theorem 5.2) showed that ν is absolutely continuous with respect to the Riemannian volume on the manifold Γ. In particular, ν(∂Γ * ) = 0 and ν(Γ * ) = 1.
The main issue is to prove the convergence of the distribution S t,x towards ν as t → ∞, where S t,x denotes the measure of all trajectories of solutions to (9) at time t starting from x ∈ Γ * . A priori, such convergence is only known to hold for 1 T T 0 S t,x dt by ergodic theorem. Applying (Duflo & Revuz, 1969, Theorem II.4) to (Γ * , ν), it suffices to check two conditions to guarantee S t,x → ν (in total variation distance):
(Harris's recurrence condition) For all sets A with ν(A) > 0 and all x ∈ Γ * ,
Let us first verify (Harris's recurrence condition). Define D ⊂ Γ * by
Then D is open in Γ * . For all x ∈ Γ * and A ⊆ Γ * , we define the random variable τ x,A ≥ 0 to be the first entering time into A for a trajectory of (9) starting at y. Lemma 3.2.
Proof of (Harris's recurrence condition). By (Arnold & Kliemann, 1987, Theorem 6.1), ( 11) holds for all x ∈ D ∩ intΓ * = D. By Lemma 3.2, it then holds for all x ∈ Γ * . This verifies Harris's recurrence condition.
We now verify the (Regularity condition): In addition to the Lie algebra l and set D, define a Lie algebra l 0 ⊆ T Γ and an open set D 0 by
It is easy to see that l 0 is indeed a Lie algebra and D 0 is a relatively open subset in Γ * Lemma 3.3. The set D 0 has non-empty interior.
We postpone the proofs of Lemma 3.2 and 3.3 to Appendix A. Lemma 3.4. For all x ∈ D 0 and t > 0, S 0 t,x (Γ * ) > 0.
Proof. By (Ichihara & Kunita, 1974, Lemma 2.1), at every x ∈ intD 0 , the second order differential operator on the right hand side of ( 9) is elliptic (non-degenerate) at x. The lemma follows.
Proof of (Regularity condition). By (Harris's recurrence condition) and Lemma 3.3, for all x ∈ Γ * , P(τ x,D0 < ∞) > 0, and thus there exists t 0 (x) > 0 such that P(τ x,D0 < t 0 (x)) > 0. In other words, on a subset Ω x,D0 ⊂ Ω of stochastic incidences ω with P(Ω x,D0 ) > 0, there exists
) (Γ * ) > 0. This shows that the statement "For ν-a.e. x, S 0 t,x (Γ * ) = 0 for all t > 0" is false. By (Duflo & Revuz, 1969, Proposition, p235), this guarantees (Regularity condition).
We have by now completed the proof of the mixing property S t,x → ν under the generic Assumption 1.2, and the Assumption 1.3.(i).
We now stop assuming Assumption 1.3.(i) and decompose Γ = Γ i where each
] is an invariant control set of (2). Moreover, it was proved in (Li et al., 2020) that for a given initial radius |x 0 |, the radius |X t | of (2) starting at x 0 will be almost surely inside
Then Γ i 1 are the connected components of the manifold Γ 1 . In particular, there are only finitely many Γ i 's. Write
Fix from now on a sufficiently small parameter p 0 such that U i 1,p0 are disjoint for distinct i's, and Γ i 1 is the set of all critical points of L inside U i 1,10p0 . This is possible because of Assumption 1.2.(ii). Proposition 4.1. For all sufficiently small p 1 (to be determined later), given K > 1, ϵ > 0, there exists a subset
|x0| ∈ Λ K,ϵ , with probability > 1 -ϵ, the trajectory of (2) starting at x 0 will remain inside
Published as a conference paper at ICLR 2024
The proof of the proposition, which we omit, is a simple combination of (Li et al., 2020, Equation (7)) and the proof of (Wang & Wang, 2022, Theorem 4.5).
The proposition allows us to assume that our initial point is inside one of finitely many basins U i #,p1 . To prove the main result, it now suffices to make two observations: First, with very high probability, the trajectory will not escape from the basin in exponential time. Second, as long as the trajectory remains in the basin, its distribution always mixes towards a unique probability measure ν i supported at the bottom Γ i of the basin.
The first property is stated as Proposition 4.2 below. Proposition 4.2. There exist C > 0, and sufficiently small p 0 > p 1 > 0, such that for all i and
The convergence is uniform with respect to the inital data x 0 .
It is similar in nature to (Wang & Wang, 2022, Lemma E.6) but requires a more sophisticated proof. This is the main theoretical component of this paper. The argument will be based on the large deviation principle of Dembo-Zeitouni in Dembo & Zeitouni (2010, Chapter 5), which was an adaptation of (Freidlin & Wentzell, 2012, Chapter 6). The reason for which Freidlin-Wentzell's original theory cannot be applied here like in (Wang & Wang, 2022) is that the diffusion in the SDE system ( 44), ( 45) is degenerate. Dembo-Zeitouni's work allows degenerate diffusions. However, further modifications to (Dembo & Zeitouni, 2010) are needed in our case as the first order drift in (45) depends on the γ t = |X t | 4 η -2 . We will treat γ t as a control variable. The full proof will be in Appendix B.
The second property follows from the main results (Theorem 5.1 & Theorem 6.7) in (Li et al., 2022c)) and is restated as Proposition 4.3 here with an additional emphasis on uniformity. A more detailed discussion can be found in Appendix C. Recall that (Li et al., 2022c)) also assumes Assumption 1.3.(ii), but that can be dropped by the discussion in Chapter 3 above. Proposition 4.3. Under Assumption 1.2 For all K > 0 and sufficiently small p 0 > p 1 > 0, such that in the regime η ≤ O(λ) ≤ O(1) and ηλ → 0, the following holds: For each index i and for all initial parameter x 0 ∈ U i #,p1 , the distribution of all trajectories X t 0≤t≤
that do not leave U i #,p1 converges in distribution to the trajectories { Xt } to a fixed SDE model (the Katzenberger model) supported on Γ i with initial position Φ(x 0 ). The convergence is uniform in x 0 . Moreover, as K → ∞ the trajectories { Xt } are uniformly mixing (with respect to different x 0 's) towards a fixed equilibrium measure ν i .
Our main theorem, Theorem 2.4, then follows from combining Propositions 4.1, 4.2 and 4.3.
Proof of Theorem 2.4. By Proposition 4.1, after ignoring O( 1ηλ ) time at the beginning, as well as an o(1) portion of stochastic incidences. One may assume x 0 ∈ U i #,p for some i. For t within the range in the statement of Theorem 2.4, again after ignoring an o(1) portion of incidences, one may assume that all trajectories under consideration stay within U i #,p up to time t. Because of the lower bound for t, one may consider a window of length K log(1+ λ η ) ηλ that ends at t where K → ∞. The distribution of trajectories along this window is the average of distributions over different initial positions. By Proposition 4.3, all such components uniformly mix toward ν i . The proof is completed.
Mixing on local manifold: The key technical observation of this paper (Proposition 4.2) is that the distribution of trajectories with an initial position is trapped locally in the attracting basin containing the initial position during any practical observation windows. Using the method from (Wang & Wang, 2022, Fig. 13), this observation is supported by the experiment below: using a reduced MNIST dataset with only 1280 samples and a small CNN with 1786 parameters (so that the model is still overparametrized), we ran 15 independent instances of SGD, at λ = η = 1 32 , for each of two randomly chosen initial parametrizations. Each instance lasts 0.8 million steps of SGD. A smilar experiment was ran for reduced CIFAR10 dataset with 1280 samples, a CNN model with 2658 parameters, η = 1 1024 , λ = 1 32 and 1.28 million SGD steps. In order to show that the distribution arising from each initial position does stabilize toward an equilibrium and the two equilibria are different, we track the variance within each group, and compare them with the average distance square over all pairs of point s from different groups. Namely, denoting by {X k i,t } the i-th trajectory starting at initial point x k where k = 1, 2, we compute the following quantities: 2 shows that V 11 and V 22 stabilizes near similar but different values, but V 12 stabilizes at a much bigger value. This suggests that the distributions of trajectories with starting point x 1 and x 2 mixes towards equilibria whose support have similar scales, but these two equilibria are far apart from each other. Figure 4: small CIFAR: Comparison between training losses before and after SWAP
Prediction on the failure of stochastic weight averaging in parallel (SWAP): Our theory predicts that if the local minima manifold of minimizes Γ i has non-trivial geometry, that is, the average of parameters on the manifold may fall off the manifold, then it might fail to decrease loss, or even increase the loss, once the SGD mixes to the local manifold.
We apply stochastic weight average over trajectories (SWAP) to the neural network parameters at each step over the 15 independent instances with the same initial position and compute the loss function at the averaged parameter. SWAP, a variant of stochastic weight average (SWA) from Izmailov et al. (2018), was proposed by Gupta et al. (2020). Figures 3, 4 show that although the loss of the SWAP parameter improves the average loss over the independent instances at the beginning, the improvement quickly breaks after a couple thousands of training steps. This phenomenon verifies our theoretical prediction and also suggests that the support of the equilibrium is not a convex set but rather a manifold of curved shape.
We give rigorous proof of fast equilibrium conjecture in generic situations, removing previous assumptions that there is only one basin and the set of minima is analytic. The main technical contribution is that we justify most of the trajectories of SDE would not escape from one basin within exponential time. Instead of using spectral analysis, we adopt the large deviation principle type of argument. Possible interesting direction may include understanding the dependence of mixing time on dimension, architecture and noise structure.
7 ACKNOWLEDGEMENT Y.W. and Z.W. acknowledge respectively supports from NSF. Barry Simon. Semiclassical analysis of low lying eigenvalues. I. Nondegenerate minima: asymptotic expansions. Ann. Inst. H. Poincaré Sect. A (N.S.), 38(3):295-308, 1983. ISSN 0246-0211. Ruosi Wan, Zhanxing Zhu, Xiangyu Zhang, and Jian Sun. Spherical motion dynamics: Learning dynamics of neural network with normalization, weight decay, and sgd. In Advances in Neural Information Processing Systems, volume 34, 2021. Yi Wang and Zhiren Wang. Three-stage evolution and fast equilibrium for SGD with non-degenerate critical points. In Proceedings of the 39th International Conference on Machine Learning, pp. 23092-23113, 2022. Yuxin Wu and Kaiming He. Group normalization. In European Conference on Computer Vision, 2018.
A PROOFS FOR SECTION 3
Proof. of Lemma 3.2. Instead of ( 9), define
where
thus the solutions Y and Y ∥ to ( 9) and ( 12) starting at y coincide up to τ x,D . Moreover, the trajectories of ( 12 Proof. of Lemma 3.4. The proof is similar to that of (Li et al., 2022c, Lemma F.18). Recall that Tr Σ is (-2)-homogeneous and assumed to be non-constant on Γ 1 . Therefore, there is an open set
By homogeneity, this is also true on rV 1 ⊆ Γ r for all r > 0. As Tr Σ(x) = -1 2 ⟨x, f 0 (x) +
x 2 ⟩ and ⟨x, f * ⟩ = 0, this implies ⟨∇⟨x, f 0 (x)⟩, f * ⟩ ̸ = 0 on rV 1 . By (Li et al., 2022c, Lemma F.16)
In this appendix, we establish a probabilistic lower bound to the exiting time of a stochastic process from a basin (Theorem B.21), based on a one-sided large deviation principle (Theorem B.12). Our proofs adapt those from the work of Dembo-Zeitouni (Dembo & Zeitouni, 2010, Chapter 5) to a more general setting. The main differences in the setting are:
1. The stochastic process in the basin is now governed not only by the current location and an Brownian motion, but also by an extra control variable as stated in equation ( 17);
2. The local minima set in the basin is no longer assumed to be a unique isolated fixed point.
The diffusion in the stochastic process is allowed to be degenerate, which was the main novelty in the Dembo-Zeitouni theory compared to the earlier work of Freidlin-Wentzell (Freidlin & Wentzell, 2012, Chapter 6).
This appendix will solely consist of mathematical analysis. With the exception of §B.4, all notations are chosen independently from those used in other parts of the current paper.
In this section we define the notion of upper large deviation principle (upper LDP). This is the upper bound part of the large deviation principle defined in (Dembo & Zeitouni, 2010, Chapter 1.2). The principles proved in (Dembo & Zeitouni, 2010, Chapter 4.1 & 4.2), which allows to pass the LDP property between random processes, are still valid for upper LDP because the upper and lower bounds are treated separately in their proofs. The purpose of this section is to briefly list which facts are relevant and justify the survival of their proofs in (Dembo & Zeitouni, 2010) with upper LDP. Definition B.1. A rate function I is a lower semicontinuous mapping I : X → [0, ∞] on a metric space X , i.e. I -1 ([0, a]) is closed for all finite a. A good rate function is a rate function I such that I -1 ([0, a]) is compact for all finite a. The effective domain D I if I is I -1 ([0, ∞)). Definition B.2. A family of Borel probability measures {µ ϵ } on (X , B) satisfies upper large deviation principle (upper LDP) with rate function I if for all measurable subsets A of X , lim sup ϵ→0
A family of Borel probability measures µ ϵ on (X , B) satisfies weak upper large deviation principle (weak upper LDP) with rate function I if ( 13) holds for all compact subsets A.
For background, recall that {µ ϵ } is said to satisfy the large deviation principle with rate function I if in addition to (13) it also satisfies the lower bound Remark about the proofs. Theorem B.3 and Theorem B.4 are the upper bound directions of (Dembo & Zeitouni, 2010, Theorem 4.1.11 & 4.2.1). Their proofs are identical to those therein. For Theorem B.3, note that this direction only uses the equality (4.1.14), but not (4.1.12) and (4.1.13), in (Dembo & Zeitouni, 2010).
Definition B.5. For families {ν ϵ,m } and {ν ϵ } of probability measures on a metric space Y, where m ∈ N and ϵ > 0, we say {ν ϵ,m } are exponentially good approximations of {ν ϵ } if there exist probability spaces (Ω, B ϵ , P ϵ,m ) and two families of random variables y ϵ,m , y ϵ with joint distribution P ϵ and marginal distributions ν ϵ,m , ν ϵ such that for all δ > 0, the event dist(y ϵ,m , y ϵ ) > δ is B ϵ -measurable and
If in addition ν ϵ,m = ν ϵ is independent of m, we say { ν ϵ } and {ν ϵ } are exponentially equivalent. Remark about the proof. The proof is the same as that of (Dembo & Zeitouni, 2010, Theorem 4.2.16). For part (a), by Theorem 3.3 applied to the topological base consisting of all metric balls B δ (y) in Y, {ν ϵ,m } satisfies weak upper LDP with rate function
So it suffices to prove I(y) ≤ I * (y). This was done in the proof of (Dembo & Zeitouni, 2010, Theorem 4.2.16, part (a)) via the inequality
I m (z).
Hence
The proof of part (b) is verbatim as in (Dembo & Zeitouni, 2010).
Theorem B.7. Suppose a family of probability measures {µ ϵ } satisfies upper LDP with a good rate function I on a Hausdorff topological space X . And suppose a sequence of continuous maps {F m } from X to another Hausdorff topological space Y approximate a measurable maps F in the sense that for all a < ∞, lim sup
Finally, assume the families {µ ϵ •(F m ) -1 } are exponentially good approximations of another family of probability distributions {ν ϵ } on Y. Then {ν ϵ } satisfies upper LDP with good rate functions I ′ (y) := inf F -1 ({y}) I.
Remark about the proof. The theorem is the upper bound part of of (Dembo & Zeitouni, 2010, Theorem 4.2.23). The proof stay the same with (Dembo & Zeitouni, 2010, Theorems 4.2.1 & 4.2.16) replaced by their respective upper bounds direction, namely Theorem B.4 and Theorem B.6. B.2 UPPER LDP FOR DEGENERATE DIFFUSION WITH EXTRA CONTROL VARIABLE
In this part, we prove a variation of the upper bound direction in the large deviation principle proved in (Dembo & Zeitouni, 2010, Theorem 5.6.7). The notations in this section are self-contained and independent of those from other parts of this paper.
Throughout this section we will consider the following setting:
• b and σ are bounded, and h is bounded on [0, ϵ 0 ] × U × D for some ϵ 0 > 0. We will fix ϵ 0 and a common upper bound H for b, σ and h respectively on these domains.
Consider the following families of stochastic differential equations on (Y, Z) ∈ U × R l and ϵ > 0:
The main difference of our setting from that in (Dembo & Zeitouni, 2010) is the existence of the additional control variable Z ϵ t , whose evolution depends on ϵ in a less prescribed way. We will assume throughout this section, in addition to Assumption B.8, that: Assumption B.8. For all ϵ > 0 and initial values (y 0 , z 0 ) ∈ U × D, the solution (Y ϵ t , Z ϵ t ) to ( 16) and ( 17) starting at (y 0 , z 0 ) almost surely remains in U × D for all t > 0. Definition B.9. Given the functions b, σ, the upper bound H on |h|, and T > 0. The associated path space S T is defined as the family of triples (f, g, u)
Here C Lip H ([0, T ], D) is the subspace in C 0 ([0, T ], D) of functions g with Lipschitz constant bounded by H, i.e. that satisfy
And W 1,2 is the square integrable Sobolev space of first order differentiability.
Proof. As C 0 ([0.T ], D) is a metric space, it suffices to show any sequence g (k) in C Lip H ([0, T ], D) has a convergent subsequence with limit in C Lip H ([0, T ], D) Because D is a bounded domain, the g (k) 's are uniformly bounded. As they are also uniformly Lipschitz with Lipschitz constant bounded by H, by Arzelà-Ascoli Theorem we may assume g (k) converges in C 0 to some g ∈ C 0 ([0, T ], D). Then g would be H-Lipschitz continuous as well.
H ([0, T ], D) will be equipped with the C 0 topology without further notice. Definition B.11. Given a function f ∈ C 0 ([0, T ], U ), the corresponding energy functional is
By convention, Φ T (f ) = ∞ if S T is empty. Theorem B.12. Given a closed subset A of the metric space A ⊂ C 0 ([0, T ], U ) and an initial value y 0 , for the solution (Y ϵ t , Z ϵ t ) to ( 16) and ( 17) with initial value (y 0 , z 0 ), the following inequality holds:
In order to prove Theorem B.12, we need more notations to study the Y ϵ t while keeping the path Z ϵ t fixed. For this purpose, we define some distributions of (Z ϵ t , √ ϵB d t ) and Y ϵ t respectively. Definition B.13. Denote by µ ϵ (y0,z0),T the joint distribution of (Z ϵ t , 16), ( 17) with initial value (y 0 , z 0 ) at t = 0. Write λ ϵ for the distribution of For all initial values (y 0 , z 0 ) ∈ U × D, Y ϵ t , Z ϵ t are progressively measurable processes. In consequence,
Lemma B.15. The function
1 satisfies upper LDP with rate function I.
Proof. We first check that I is a rate function. That is, it is lower semicountinuous on
, and thus by definition I(g, u) = I 0 (u) in this case. It was known by Schilder's Theorem ( (Dembo & Zeitouni, 2010, Theorem 5.2.3)) that the function
is a good rate function, and in particular lower semicountinuous. Thus
Thus I is a good rate function and we want to show that it is good, i.e. I -1 ([0, a]) is compact for all finite a. Remark that
) and the second factor is compact as I 0 is a good rate function. Note that I 0 (u) = I(g, u). So it suffices to know that C Lip H ([0, 1], D) is a compact space in C 0 topology, which is the assertion of Lemma B.10.
Finally we need to show that (13) holds for {µ ϵ } and I. The same inequality holds for {λ ϵ } and I 0 , i.e. for all
In the last inequality, we used the fact that A 0 contains the projection of A and that I(g, u) = I 0 (u). This completes the proof.
For all (g, u)
In addition, given an integer m ∈ N, we also define Y ϵ,m (g,u),t as the solution on [0, 1], also with initial value y 0 , to the following stochastic differential equation
We emphasize that Y ϵ (g,u),t and Y ϵ,m (g,u),t are deterministic once the pair (g, u) are given and all randomness comes from µ ϵ (y0,z0),T . Lemma B.16. For all any δ > 0 and all initial values y 0 ∈ D,
Proof of Lemma B.16. Fix δ > 0. Let ∆ ϵ,m (g,u),t := Y ϵ,m (g,u),t -Y ϵ (g,u),t , for any ρ > 0, define the stopping time τ ϵ,m,ρ := min(inf{t :
τ ϵ,m,ρ depends on (g, u), but we skip it to simplify the notation.
The process ∆ ϵ,n (g,u),t satisfies the SDE
By the uniform Lipschitz continuity of b and σ, and the boundedness of g t ∈ D, there is a constant C such that for all t ≤ τ ϵ,m,ρ ,
By (Dembo & Zeitouni, 2010, Lemma 5.6.18), for all ϵ ∈ (0, 1), δ > 0,
where K is a constant independent of δ, ϵ, ρ, µ and m. Then
the lemma is proved if we show for all ρ > 0,
To prove this, recall that |b| and |σ| are bounded by a constant H, and
Therefore, for m > H ρ , sup
This guarantees (23) and proves the lemma.
Proof of Theorem B.12. First of all, notice that one can assume without loss of generality that T = 1 by rescaling the time interval [0, T ] to [0, 1]. To see this, notice that the rescaled Brownian motion
We will only deal with the [0, 1] interval below.
Define maps F m , F :
For F , the image f = F (g, u) instead satisfies f 0 = y 0 and
It is not hard to check by Lipschitz boundedness of b, σ, and the compactnes of
Moreover, ( 21) and ( 22) can be reformulated as Y ϵ,m (g,u),t = F m (g, u) and Y ϵ (g,u),t = F (g, u) respectively. ( 26)
Θ m is a function of t, and by the Lipschitz bounds on b and σ,
In other words, the families {µ ϵ (y0,z ϵ 0 ),1 • (F m ) -1 } are exponentially good approximations of the distribution of Y ϵ (g,u),t with (g, u) ∼ µ ϵ (y0,z ϵ 0 ),1 . Thus if we can prove: for all a < ∞,
then by Lemma B.7 and Lemma B.15, the distribution of Y ϵ (g,u),t with (g, u) ∼ µ ϵ (y0,z ϵ 0 ),1 satisfies upper LDP with good rate function y → inf F (g,u)=y I(g, u), which is exactly Φ 1 (y). Because for each different value of ϵ, z ϵ 0 is arbitrarily chosen in D and the distribution of 16), ( 17), this exactly yields the statement of the theorem.
holds, then for f m = F m (g, u) and f = F (g, u) given in ( 24), ( 25),
for some constant C 0 by the bound on the coefficients and Cauchy-Schwarz inequality. Write η m for the right hand side in (28). Then by Lipschitz continuity of b and σ, for some other constant C,
Thus by Gronwall's inequality, (∆ m t ) 2 ≤ 4C 2 (1 + a)e 4C 2 (1+a)t (η m ) 2 . The equality ( 27) follows by letting m → ∞, This completes the proof.
The following is a strengthen version of Theorem B.12. Theorem B.17. Given a closed subset A of the metric space A ⊂ C 0 ([0, 1], U ) and an initial value (y * , z * ) ∈ U × V , for solutions (Y ϵ t , Z ϵ t ) to ( 16) and ( 17), the following inequality holds: lim sup
Proof of Theorem B.17. As in the proof of Theorem B.12, we can assume T = 1.
By Theorem B.6, it suffices to prove that for any family of points y ϵ 0 → y * as ϵ → 0 and arbitrary z ϵ 0 ∈ D, the family of distribution {ν ϵ
, and
Moreover,
Remark that the coefficients α ϵ t , β ϵ t are progressively measurable processes with respect to the filter generated by the Brownian motion {B d t }. Moreover, by Lipschitz continuity of b, σ, h, for some constant
By applying (Dembo & Zeitouni, 2010, Lemma 5.6.18) with τ 1 = 1, we know that there is another constant C such that for all ρ > 0, δ > 0,
By letting ρ → 0 first and then ϵ → 0, it follows that lim sup ϵ→0 ϵ log P( sup
This shows {ν ϵ (y ϵ 0 ,z ϵ 0 ),1 } is exponentially equivalent to {ν ϵ (y * ,z ϵ 0 ),1 }, which suffices to conclude the proof.
Corollary B.18. Given a closed subset A of the metric space A ⊂ C 0 ([0, 1], U ) and a compact set K ⊆ U , for solutions (Y ϵ t , Z ϵ t ) to ( 16) and ( 17), the following inequality holds: lim sup ϵ→0 ϵ log sup
. By Theorem B.17, for all y ∈ K, there is a value ϵ y such that for all y 0 ∈ B ϵy (y) and 0 < ϵ < ϵ y ,
Cover K by finitely many balls of the form B ϵy i (y i ), then for all 0 < ϵ < min i ϵ yi ,
The proof is completed by letting M → inf f ∈A f0∈K Φ T (f ).
In this section, it will be assumed, in addition to Assumption B.8, that: Assumption B.19. There are a C 2 function L : U → [0, ∞) and a bounded open set V ⊂ U such that:
(1) ∇ b(y,z) L(y) ≤ 0 for all (y, z) ∈ V × D and the equality holds if and only if L(y) = 0;
(2) L is strictly positive on ∂V .
Write V q = L -1 ([0, q)) ∩ V and choose q 0 sufficiently small such that V q0 lies in the interior of V .
In particular, for all q ∈ [0, q 0 ], L| ∂Vq ≡ q. Definition B.20. Suppose 0 < q < Q ≤ q 0 . For a solution (Y ϵ t , Z ϵ t ) of ( 16), ( 17) with initial value in V Q × D, denote by τ ϵ q,Q the first time Y ϵ t hits V q ∪ ∂V Q , and by τ ϵ Q the first time Y ϵ t hits ∂V Q .
Our goal is to prove the following main theorem: Theorem B.21. Under Assumptions B.8 and B.19, for all 0 < q < Q < q 0 there exists I Q > 0 such that for all, lim ϵ→0 sup (y0,z0)∈Vq×D
The following lemma is an analogue to (Dembo & Zeitouni, 2010, Lemma 5.7.22) Lemma B.22. For all 0 < q < Q ′ < Q ≤ q 0 , the stopping time τ ϵ q,Q satisfies
Proof. Consider the solution Y 0 t to the deterministic flow
starting at y 0 . By Assumption B.19, L(Y 0 t ) is decreasing and must converge to 0 as t → 0, and
It would in turn follow that
For simplicity, write J ϵ t := (Y ϵ t , Z ϵ t ), (Y 0 t , z 0 ) . Let M < ∞ be a common upper bound on the C 0 and the Lipschitz norms of the maps b, σ and h over the domains ϵ ∈
By Gronwall's inequality,
Therefore, in order to make sup t∈[0, T ] J ϵ t ≥ δ, we must have
and thus
T must hold for at least one of the row vectors σ k of σ.
The process
By the Burkholder-Davis-Gundy inequality (see e.g. (Dembo & Zeitouni, 2010, Chapter E)),
for an absolute constant C. And thus by the Chebyshev's theorem
From the earlier discussion, after summing over all k's, we obtain that
We deduce ( 30) from ( 31) by letting ϵ → 0, which concludes the proof.
The following lemma is the analogue of (Dembo & Zeitouni, 2010, Lemma 5.7.23). Lemma B.23. For all δ, a > 0 and bounded set K ⊂ U , there exists a constant T 0 = T 0 (δ, a, K) > 0 such that lim sup ϵ→0 ϵ log sup
Proof. Without loss of generality, assume ϵ, δ ∈ [0, 1] with δ fixed and ϵ varying. Let the stopping time ζ ϵ be the first time such that
and thus they all are uniformly bounded by a constant M . For all
As in the proof of (Dembo & Zeitouni, 2010, Lemma 5.7.23), it suffices to consider each row vector σ k of σ. The stochastic process
t 0 σ k (Y ϵ s , Z ϵ s )dB 1 s is equivalent to B 1 τ ϵ k,t by the time change theorem (see (Dembo & Zeitouni, 2010, Chapter E.2)) where τ ϵ k,t = t 0 σ 2 k (Y ϵ s , Z ϵ s )ds. The function τ ϵ k,t is increasing in t and almost surely τ ϵ k,t ≤ M 2 t if T 0 ≤ ζ ϵ as the C 0 and the Lipschitz norms of b, σ, h are bounded by M before the stopping time ζ ϵ . By (Dembo & Zeitouni, 2010, Lemma 5.2.1),
Summing over different k's, we conclude from the two inequalities above that for all T 0 ∈ [0, δ 4M ]
It now suffices to take T 0 = min( δ 4M , δ 2 8d 2 M 2 a ). Definition B.24. For y 0 , y 1 ∈ U and T > 0, define an energy cost Ψ T (y 0 , y 1 ) by
The following lemma claims there is a minimum energy cost required to increase the loss function L between different levels. Lemma B.25. For all 0 < q < Q ≤ q 0 , inf
Moreover, there is constant T q,Q > 0 such that inf
Proof. Suppose for now y 0 , y 1 ∈ V Q \∂V q , and (f, g, u) ∈ S T with f 0 = y 0 , f T = y 1 . Then by (18), dL
Because q > 0, by Assumption B.19, as ∇ ⊤ L(y) b(y, z) = ∇ b(y,z) L(y) < 0 for all y ∈ V Q \V q and z ∈ D. In particular, this also shows ∇L(y) ̸ = 0 for all y ∈ V Q \V q . Since both V Q \V q and D are compact, There exists positive constant κ = κ(q, Q) > 0 and η = η(q, Q) > 0, such that
Integrating from 0 to T , we get
In order to show (32), note that if y 0 ∈ V q and y 1 ∈ ∂V Q , then L(y 1 ) -L(y 0 ) = Q -q > 0. By (34) and Cauchy-Schwarz inequality,
This provides a positive lower bound for Ψ T (y 0 , y 1 ) that is uniform for T > 0, y 0 ∈ V q and y 1 ∈ ∂V Q . This proves (32).
Published as a conference paper at ICLR 2024
We now prove (33). Note that for all y 0 , y 1 ∈ V Q \V q , L(y 1 ) -L(y 0 ) ≥ q -Q. By (34),
The last expression is uniformly positive for T ≥ T q,Q := 2(Q -q)κ -1 η -2 . Thus Ψ T (y 0 , y 1 ) is uniformly positive over the region given by T ≥ T q,Q , y 0 , y 1 ∈ V Q \∂V q . This proves (33).
Lemma B.26. For all 0 < q < Q ≤ q 0 and initial value (y 0 , z 0 ) ∈ V Q × D, the stopping time τ ϵ q,Q satisfies lim
and in consequence it suffices to show lim
Assume, for the sake of contradiction, that (36) is false, then for some M < ∞ and any all k ∈ N, there exists f k ∈ C 0 ([0, kT q,Q ], V Q \V q ) with Φ(f k ) ≤ M , where T q,Q is given by Lemma B.25. After breaking f k into k segments on subintervals of length T q,Q , it follows that there exists f * k ∈ C 0 ([0, T q,Q ], V Q \V q ) such that Φ(f * k ) ≤ M k . By taking limit in C 0 norm (which is permitted by Lemma B.10) and using the lower semicontinuity of the good rate function Φ, there exists f * ∈ C 0 ([0, T q,Q ], V Q \V q ) with Φ(f * ) = 0. This implies Ψ T (y 0 , y 1 ) = 0 and thus it contradicts to the inequality (33) of Lemma B.25. This completes the proof.
Denote by I q,Q > 0 the left hand side in (32). Lemma B.27. The solutions to ( 16) and ( 17) satisfy lim q→0 lim sup ϵ→0 ϵ log sup (y0,z0)∈V2q×D
Proof. Fix an arbitrarily small δ, and let I Q,δ := min(lim q→0 I q,Q -δ, 1 δ ). Note that the right hand side in (37) always exists because I q,Q is a decreasing function in q by construction. In particular, I 2q,Q ≥ I Q,δ when q is sufficiently small depending on Q and δ.
By Lemma B.26, there exists a large T * = T * (q, Q, δ) < ∞ such that lim sup ϵ→0 ϵ log sup (y0,z0)∈V2q×D
In addition, inf
and thus by Corollary B.18, lim sup ϵ→0 ϵ log sup (y0,z0)∈V2q×D
Note that the event {Y ϵ τ ϵ q,Q ∈ ∂V Q } is contained in the union of the events {τ ϵ q,Q > T * } and {sup t∈[0,T * ] L(Y ϵ t ) ≥ Q}. Therefore, we obtain by combining ( 38) and ( 39) that the inequality lim sup ϵ→0 ϵ log sup (y0,z0)∈V2q×D
holds for all sufficiently small q. The lemma then follows by letting δ → 0.
We are now ready to establish Theorem B.21.
Proof of Theorem B.21. Choose q < Q 2 to be sufficiently small. Define a sequence of stopping times
∂V 2q }. By Lemma B.22, all these stopping times are finite almost surely. Write Y m = Y ϵ τm , which is a Markov chain.
Recall that by Lemma B.25 I q,Q > 0 for all 0 < q < Q and is an decreasing function in q. Let I Q := 1 2 lim q→0 I q,Q > 0 and fix 0 < α < 1 4 I Q . By Lemma B.27, if we fix a sufficiently small q, then lim sup ϵ→0 ϵ log sup (y0,z0)∈V2q×D
By plugging in (Y ϵ θm , Z ϵ θm ) as the the value for (y, z), we deduce that there exists ϵ 0 > 0 such that for all 0 < ϵ < ϵ 0 and m ≥ 1, sup
On the other hand, assuming ϵ 0 is sufficiently small, applying Lemma B.23 with a = I Q + 2α, δ = 1 2 q and K = V Q yields that, for some fixed T 0 > 0 depending on q and Q and all ϵ ∈ (0,
For a given M , the event {τ ϵ Q ≤ M T 0 } is contained in the union of the events
Combining this fact and the inequalities (41), (42) yield sup (y0,z0)∈Vq×D
which tends to 0 as ϵ → 0. This completes the proof of Theorem B.21.
B.4 PROOF OF PROPOSITION 4.2
Recall that the movement of (2) stays in Γ # , i.e. |X t | ∈ [R -, R + ] and can be characterized as the new model ( 6), (5).
After applying a time change T = (ηλ)
we get the following system of equations on (X T , γT )
To deduce (44), we used the standard fact that for any a > 0, a 1 2 B d a -1 T and B d T are equivalent as Wiener processes.
as long as X t ∈ Γ # . As there are only finitely many basins, we may fix an index i without impact Proposition B.28. In addition, without loss of generality let us assume L = 0 on Γ i . For our purpose, it might be better to measure the distance to Γ i on U i #,p0 where p 0 > p 1 is sufficiently small and in particular U j #,p0 are disjoint for distinct j's. For q ≥ 0, we will write V i r,q = {x ∈ U i r,p0 , L(x) < q} and V i #,q = {x ∈ U i #,p0 , L(x) < q}. By Assumption 1.2.(ii), one may manipulate p 0 , q 0 , p 1 , q 1 (p 0 > p 1 , q 0 > q 1 ) such that
, and thus reformulate Proposition 4.2 as Proposition B.28. There exists c > 0 such that if q 0 > q 1 > 0 are fixed, but q 1 is sufficiently small compared to q 0 , then in the regime η
The convergence is uniform with respect to (y 0 , z 0 ).
Proof. In order to apply Theorem B.21 with domain V i 1,q0 and control domain D = [γ -, γ+ ], we first make the following remark.
Theorem B.21 is in the setting where the domain is an open neighborhood in R n , while our current V i q0 is a neighborhood in the sphere. This is not a problem because unless L is a constant function, Γ i 1 is a proper subset of the sphere S d-1 . And V i q is also a proper subset in S d-1 for small q. One can then change coordinates and identify V i q with a subset of the Euclidean space.
This converts the problem to the equations ( 16), ( 17) with the following dictionary: ϵ = (ηλ) 1 2 ; X T and γT play the roles of Y ϵ t , and Z ϵ t respectively; b(y, z) = -z -1 2 ∇(y); σ(y, z) = z -1 2 σ(y); and h(ϵ, y, z) = ϵ(-4z + 2 Tr Σ(y)).
It remains to check Assumptions B.8 and B.19. We start with the latter. The strictly positivity of L directly follows from the construction of L and the neighborhood V i q0 . The property (1) in Assumption B.19 holds because b is negatively proportional to the gradient ∇ of L with respect to the spherical coordinates.
Unfortunately Assumption B.8 doesn't automatically hold as trajectories may escape from V i 1,q0 . In order to adapt to this case, we smoothly modify the value of σ on V i 1,q0 so that it remains unchanged on V i 1,q1 and vanishes near ∂V i 1,q0 . Then near the boundary, the SDEs ( 16), ( 17) become deterministic. Because of Assumption B.19.(1), the trajectories do not escape from ∂V i 1,q0 . Moreover, we know that γt remains in D = [γ -, γ + ]. This verifies Assumption B.8 for the modified model.
We conclude by applying Theorem B.21 that, for some fixed I > 0, for all initial positions in V i 1,q1 × [γ -, γ+ ], the probability that a trajectory (X T , γT ) (with respect to the modified model) leaves
2 ) converges to 0 as ηλ → 0. The convergence is in addition uniform with respect to the initial position.
Since such modifications only take place outside V i 1,q1 × [γ -, γ+ ], the same statement also holds for the original model. As V i 1,q1 ⊂ V i 0,q0 , we obtain the statement of Proposition B.28 after reparamatrization of variables.
The results from §B.2, stated in the form of Proposition 4.2, guarantee that, after discarding an exponentially small subset of random incidences, the trajectories of (2) stays inside the basin that contains the initial position for exponentially long time O(e C(ηλ) -1 ). We now justify Proposition 4.3
We restart (2) from an initial point, still written as x 0 by abuse of notation, in some U i #,p1 . We now apply a uniform approximation theorem, which is a stronger version of (Li et al., 2022a, Theorem 4.6). We can prove this uniform approximation result because we can strengthen (Katzenberger, 1991, Theorem 6.3) to be a compactness theorem, uniformly with respect to the initial points of the SDE. To describe this result, let (Ω n , F n , {F n t } t≥0 , P) be a filtered probability space, Z n an R evalued cadlag {F n t }-semimartingale with Z n (0) = 0 and A n a real-valued cadlag {F n t }-adapted nondecreasing process with A n (0) = 0. Let σ n : U → M(d, e) be continuous with σ n → σ uniformly on compact subsets of U . Let X n be an R d -valued cadlag {F n t }-semimartingale satisfying, for all compact K ∈ U ,
for all t ≤ λ n (K) where λ n (K) = inf{t ≥ 0|X n (t-) / ∈} K or X n (t) / ∈ K is the stopping time of X n leaving K. (47)
We will present Assumption B.3, B.4 and Condition B.5, B.6, B.7 and B.8 from (Li et al., 2022a) in Appendix B.
The main difference of Theorem C.1 to (Katzenberger, 1991, Theorem 6.3) is that we allow the initial point X n (0) to vary within U .
Theorem C.2. Let the manifold Γ and its open neighborhood U satisfy Assumption 3.1 and 3.2. Let K ⊂ U be any compact set and x n,0 ∈ K be a sequence of initial points. Consider the SGD formulated in (46) where X ηn (0) ≡ x n,0 . Define Y ηn (t) = X ηn (t) -Φ(X ηn (0), A ηn (t)) + Φ(X ηn (0)) and µ ηn (K) = min{t ∈ N|Y ηn (t) / ∈ K}. Then the sequence {Y where {W (s)} s≥0 is the standard Brownian motion.
Proof. The proof of Theorem C.2 follows how (Li et al., 2022a, Theorem B.8) was proved by using (Li et al., 2022a, Lemma B.6) and the standard Katzenberger's theorem (Katzenberger, 1991, Theorem 6.3). One difference is that here not all trajectories stays inside one basin. However, we claim that the probability that trajectories escape the basin goes to zero when ηλ tends to zero. Once this claim is proved, Theorem C.2 is an immediate consequence of (Li et al., 2022a, Lemma B.6) and Theorem C.1.
To prove the claim, we adopt the same idea as in the proof of Theorem 4.2 in Appendix B.4. Although trajectories may escape from level set V i 1,q0 , we can smoothly modify the value of σ on the closure V i 1,q1 so that it remains unchanged on V i 1,q0 and vanishes near the boundary ∂V i 1,q0 . The SDEs become deterministic, and thus the trajectories of the modified model do not escape from the boundary ∂V i 1,q0 . Now, as ηλ tends to zero, by Theorem B.21 the probability of a trajectory of the modified model leaving ∂V i 1,q1 × [γ -, γ+ ] before a fixed T tends to 0. Since such modifications only take place outside ∂V i 1,q1 × [γ -, γ+ ], the same statement holds for the original model. This finishes the proof of the claim.
Proof of Proposition 4.3. The above uniform version of the Katzenberger's theorem guarantees that, starting from different initial points in the same compact neighborhood of the basin, the distribution of trajectories associated with (2) is still close to that of the Katzenberger's SDE (47). By Proposition 3.1, the latter is mixing towards a unique equilibrium ν i . Note that even though in Chapter 3, we have only proved it for one basin case, Theorem 4.1 shows that with a large probability, the trajectories do not escape from the basin. For those trajectories, they satisfy a modified SDE equation like before, so that all trajectories do not escape from this basin. At this moment, we can directly apply Proposition 3.1. It follows that within any polynomial time window under consideration, the distribution of trajectories associated with (2) are also mixing towards ν i . This proves Proposition 4. (Then Φ is C 2 on U by (Falconer, 1983).) Condition C.5. (Li et al., 2022a, Lemma B.2) The integrator sequence {A n } n≥1 is asymptotically continuous: sup t>0 |A n (t) -A n (t-)| ⇒ 0 where A n (t-) = lim s→t-A n (s) is the left limit of A n at t. Condition C.6. (Li et al., 2022a, Lemma B.3) The integrator sequence {A n } n≥1 increases infinitely fast: ∀ϵ > 0, inf t≥0 (A n (t + ϵ)) -A n (t)) ⇒ ∞.
Condition C.7. ((Katzenberger, 1991, Equation 5.1), (Li et al., 2022a, Lemma B.4)) For every T > 0, as n → ∞, it holds that sup 0<t≤T ∧λn(K)
∥∆Z n (t)∥ 2 ⇒ 0.
Condition C.8. ((Katzenberger, 1991, Condition 4.2), (Li et al., 2022a, Lemma B.5)) For each n ≥ 1, let Y n be a {F n t }-semimartingale with sample paths in D R d [0, ∞). Assume that for some δ > 0 allowing δ = ∞ and every n ≥ 1 there exist stopping times {τ m n |m ≥ 1} and a decomposition of Y n -J δ (Y n ) into a local martingale M n plus a finite variation process F n such that P[τ m n ≤ m] ≤ 1/m, {[M n ](t ∧ τ m n ) + T t∧τ m n (F n )} n≥1 is uniformly integrable for every t ≥ 0 and m ≥ 1, and lim It was shown in (Li et al., 2022a, Lemma B.6) that for SGD formulated in ( 46
Different connected components of Ω are not required to have the same dimension.