The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations
Authors: Waïss Azizian
Franck Iutzeler
Jerome Malick
Panayotis Mertikopoulos
Venue: ICML 2025 poster (2025)
Keywords: stochastic gradient descent
non-convex
large deviations
Primary area: optimization->stochastic
TL;DR: We characterize the time to global convergence of stochastic gradient descent on non-convex objectives.

Abstract: In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of large deviations theory and randomly perturbed dynamical systems, and we provide a tight characterization of the associated hitting times of SGD with matching upper and lower bounds. Our analysis reveals that the global convergence time of SGD is dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach a global minimizer, coupling in this way the geometry of the underlying loss landscape with the statistics of the noise entering the process. Finally, motivated by applications to the training of deep neural networks, we provide a series of refinements and extensions of our analysis to, among others, loss functions with no spurious local minima or ones with bounded depths.

The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations
Waiss Azizian' Franck Iutzeler?
Jérôme Malick
Panayotis Mertikopoulos
Abstract
where v 0s the method's step-size or learning rate- and 9n. = I...., is computationally stochas tic approximation of the gradient of f at Xn E R"
stochas-
In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynamical systems and large deviations theory, and we provide tight characterization of the global convergence time of SGD via matching upper and lower bounds. These bounds are dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach a global minimizer from a given initialization, coupling in this way the global geometry of the underlying loss land- scape with the statistics of the noise entering the process. Finally, motivated by applications to the training of deep neural networks, we also provide a series refinements and extensions of our anal- ysis for loss functions with shallow local minima.
The study of (SGD) goes back to the seminal work of Rob- bins Monro [74] and Kiefer & Wolfowitz [37], who in- troduced the method in the context of solving systems of nonlinear equations in the 1950's. Originally, the analysis of (SGD) involved a vanishing step-size 17 satisfying the "1.2 - I. 1.' summability conditions Σn nn2 < co = Σn 'n. and gave rise to the ODE method of stochastic approxi- mation. In this context, the first convergence results for (SGD) were obtained by Ljung [50, 51], Benaïm [8], and Bertsekas & Tsitsiklis [10], who established the almost sure convergence of the method in non-convex problems (with different regularity conditions for f). In conjunction with the above, parallel thread in the literature launched by Pe- mantle [70] and Brandière & Duflo [13] showed that (SGD) avoids saddle points with probability 1, so, barring degen- eracies, it only converges to local minimizers of f see also [2, 9, 28, 29, 35, 57, 58, 75) and references therein.
On the other hand, when (SGD) is run with constant step- size - the standard choice in data science and machine learn- ing - the situation is drastically different. The trajectories of (SGD) do not converge, but they instead wander around the problem's 's state space, spending most time near the critical points of f. This is quantified by "criticality bounds" of the form [ output with small gradient norm, in expectation with high probability [41]. As in the vanishing step-size regime, these results are supplemented by range of saddle-point avoid- ance results [24, 79] which, under certain conditions, imply that the output of (SGD) is approximately second-order optimal (and hence, in most cases, a near-minimizer).
Introduction
Much of the success of modern machine learning applica- tions hinges on solving non-convex problems of the form
mingert edd f(x)
(Opt)
O(vn), which certify an
where f: Rd + R is a smooth function on Rd. When d so large as to make gradient calculations computation- ally prohibitive, the go-to method for solving (Opt) is the stochastic gradient descent (SGD) algorithm
Xn+1 Xn -n
(SGD)
Nevertheless, all these results for (SGD) are, at best, guar- antees of local minimality, not global. When it comes to approximating the global minimum of f, we must tackle the following fundamental question:
Univ. Grenoble Alpes. CNRS, Inria, Grenoble INP, LJK, 38000 Grenoble, France. Institut de Mathématiques de Toulouse, Université de Toulouse, CNRS, UPS, 31062 Toulouse, France. Univ. Grenoble Alpes. CNRS, Inria. Grenoble INP, LIG, 38000 Grenoble, France. Correspondence to: Waiss Azizian <waiss.azizian www.euunnivreeeeeee
How much time does it take (SGD) to reach the vicinity of a global minimum of f?
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Of course, attaining the global minimum of a non-convex function is lofty goal, so, before examining the time re-

---

The Global Convergence Time of SGD in Non-Convex Landscapes
quired to achieve it, one must first assess the likelihood of getting there in the first place. In this regard, Azizian al. [5] recently showed that, in the long run, Xn is exponentially concentrated near the local minimizers of f. with the degree of concentration depending on the landscape of f and the noise entering the process. In practice, this means that (SGD) ultimately gets arbitrarily close to arg min f. but be- fore getting there, it may have spent an exponential amount of time away from arg min f. Consequently, any answer to the question of global convergence of (SGD) must incorpo- rate global information about the geometry of f. as well as the statistics of the stochastic gradients G..
cannot be adequately surveyed here. As we mentioned above, in the non-convex case, most of this literature con- cerns the criticality and saddle-point avoidance guarantees of the method, under different structural and regularity as- sumptions. For our purposes, the most relevant threads in the literature revolve around (i) treating X as a discrete-time Markov chain and examining its tails [26, 27, 69]; (i)) view- ing it as a discrete-time approximation of a stochastic dif- ferential equation (SDE) and employing tools like dynamic mean-field theory (DMFT) to study the resulting "diffusion approximation limit [59, 60. 77]; and/or (iii) focusing on the time it takes (SGD) to escape a spurious local minimum [7, 25, 30, 33, 61, 86]. Our analysis shares the same high- level goal as these general threads that is, understanding the global convergence properties of (SGD) in non-convex landscapes - but we are not aware of any comparable results. To streamline our presentation, provide more detailed account of this literature in Appendix A.
Our contributions. Our aim in this paper is to provide quantifiable predictions for the global convergence time of (SGD). Building on the approach of Azizian et al. [5], we examine this question through the lens of the Freidlin Wentzell (FW) theory of large deviations for ran- domly perturbed dynamical systems in continuous time [23], and we employ the subsampling theory of Kifer [38, 40] as a starting point to derive similar theory for the tiserete-time setting of (SGD). In so doing, we obtain tight characteri- zation for the global convergence time of (SGD) which can be expressed informally
The only thing we should highlight at this point is a range of phenomena that arise in the context of neural network training, where overparameterization and Gaussian initial- ization schemes can lead to global convergence [1, 19, 92]. Results of this kind typically require some specific structure the underlying neural network: a width scaling quadrati- cally with the data [65, 68] - or linearly for infinite-eppth networks [54] and/or initialization schemes that are at- tuned to the network's 's structure [49, 65]. By contrast, our work takes a more holistic viewpoint as we aim to obtain results for general non-convex landscapes, without making any structural assumptions about the problem's 's objective or the algorithm's 's initialization. To provide the necessary con- text, we survey the relevant literature overparameterized neural networks in Appendix A.
[x[r] = E(x)/1
where (i)= r denotes the number of iterations required to reach arg min of within a given accuracy; (it) x is the initial- ization of (SGD); and (iti) E(x) is an "energy function" that encodes the geometry of f and the statisties of the noise in (SGD) via a construct called the "transition graph" of f.
The precise form of the hitting time estimate (1) is described via matching upper and lower bounds in Section 4 (cf. Theo- rem I), Subsequently, in Section 5, we take an in-depth look at the impact of the loss landscape of ff on these bounds, and we link the energy Exx) to the depth of the function's 's spuri- ous, noo-global minima. The resulting expression provides crisp characterization of the global convergence time of (SGD) in terms of the geometry of f - andd, more precisely, the maximum relative depth of any spurious minimizers that the process encounters on its way to arg min f. The details of this construction rely on an intricate array of tools and techniques from the theory of large deviations and ran- domly perturbed dynamical systems, so they are difficult to describe here; for this reason, we begin by presenting simplified version of the apparatus required to state our results in Section 2.
2 A gentle start
Stating our results in their most general form requires some fairly involved technical apparatus, so we begin with warm- up section intended to introduce some basic concepts and develop intuition for the sequel. Specifically, our aim in this section is to give a high-level overview of our main results for a simple -vo-dimensional example which is easy to plot and visualize. We stress that the material in this section is presented an informal level; the rigorous treatment is deferred to Section 4.
With this in mind, the example of (Opt) that we will work with is a modified version of the well-known "three- humme- camel" test function, as detailed in Fig. 1. This is a multi- modal function with five critical points, indexed L1 through ps: two are saddles (p2 and p4), three are minimizers (P1, P3, and ps). and the global minimum is attained at Pi > (-2.573, 1.029). To keep things simple, we will fur- ther assume that (SGD) is run with stochastic gradients of
Related work, Owing to its importance, (SGD) and its variants have given rise to vast corpus of literature which
Formally, Azizian et al. [5] showed that, in the limit n - co, Xn follows approximate Boltzmann-Gibbe distribution with temperature equal to 77, and energy levels determined by f and the statistics On-
2

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Pr
Figure 1: Visualization of the three-hump camel test function f x2) / -442 /48 42xx /1442/22111622 166 /
/4
The figure to the left depicts the loss landscape of f with several (deterministic) gradient flow orhits superimposed for visual convenience. The figure in the middle highlights the 5 critical points of f (light blue for local minimizers, light red for saddle points): the red curves depict the stable manifolds the saddle points p2 and p4. and they partition space into three basins attraction, one per minimizer; the blue curves are gradient flow orbits that realize the edges of the transition graph of f. Finally, the figure to the right illustrates a trajectory of (SGD) starting near P3, and stopped when gets within 10-2 of Pt. the global minimum of color represents time, with darker hues indicating later iterations (SGD). The plotted trajectory gets to p1 only after first being trapped by p5-
the form 0n fxn)) where Zn is an i..dd sequence of Gaussian random vectors with covariance 1²1. Then, fixing an initialization x e- x E IR2, we will seek to estimate the global convergence time
An instructive way of interpreting this expression is fol- lows: if ((p)) S fp:). the transition of (SGD) from Pi to is "costless"; otherwise, if f(p)) > f(pi). the noise in (SGD) can still lead to an ascent from p; to pj. but the cost of such a transition is proportional to the potential difference f(p,) f(P),, and inversely proportional to the variance of the noise in (SGD).
T= in = 0, I. ||x, -P 6}
(2)
for some fixed error margin 5 > 0 (e.g., 8 = 10-2 in Fig. 1). The core of our analysis may then be summarized as follows:
In our example, this construction yields the path graph be- low (where, for visual clarity, the height of each node corre- sponds to its objective value):
With exponentially high probability, (SGD) spends most of its time near the critical points (and, in particular, its minimizers).
To leading order, the time that (SGD) takes to get to neighborhood of arg min ff is determined by the chain of critical points visited by xn, and by the average time required to transition from one to the next.
P4
P5
The technical scaffolding required to make this intuition precise is provided by weighted directed graph which quantifies the difficulty of (SGD) making a direct transition between two critical points of f. In the context of our example, this graph constructed as follows:
P1
The topology this graph captures the fact that the entire space is partitioned into the basins of attraction of Pt, P3 and p5. as shown in Fig. 1. Since #1 and ps separated by neighborhoods, there can be gradient flow orbits joining "non-successive" critical points e.g., P1 to pa leading to the path graph structure depicted above.
The nodes of the graph are the critical points Pa. i 1,.... of
Two nodes joined by edge if there exists solution orbit of the gradient flow ((t) = (x)((()) whose clo- sure connects said points.? Importantly, if Pj, we also have Pj ~ p; by default.
To proceed, we fix an initial condition x for (SGD), say, in the basin of attraction of ps. In this case, the most likely event that (SGD) will first be attracted to p3 on its way to the global minimum Pl, so, for simplicity, we just estimate the time it takes (SGD) to reach p1 from P3. However, this time cannot be determined only by the local geometry of f along the "direct" transition path ps ~ P2 ~ P1; with positive probability, (SGD) may first jump over p4 and be trapped in ps. In that case, the process will first have to escape from Ps. and then follow the "indirect" transition
The weight of an edge p; ~ Pj is given by the expression
Bij =
Formally, two distinct critical points Pi. Pj of are joined by edge if there exists solution orbit.c x()) of the gradient flow of f such that (pr. P,] = - x()).
3

---

The Global Convergence Time of SGD in Non-Convex Landscapes
0.0067
0,0019
0.0011
0,0008
In words, the exponent E(pilps) of (4) scales with the largest value gap that Xn may need clear in order to reach arg min f. In the specific example of Fig. 1, we have f(3)) > f(ps), so f(p)) f(ps) f(p2) f(ps). and hence
Theory
10*
Data
10*
10'
Convergncc Time (log
10a
10
E(pilps) =[[((p))
(6)
10*
This is precisely the obstacle that (SGD) must clear gets trapped by ps. hence our intuition (cf. Fig. 1).
10a
10a
All this may sound paradoxical at first: (4) shows that the global convergence time of (SGD) is not driven by the "shortest", least costly chain of transitions leading to arg min f. but by the "longest", most costly one. In this sense, E(p1 P3) directly encodes all non-local information of f that ends up affecting the global convergence time of (SGD), so it can be seen as an explicit measure of the "hardness" of the non-convex landscape under study: in particular, a slight increase this gap would end up having an exponential impacr on the global convergence time of (SGD), indicating the difficulty of learning even in this sim- ple example
10a
Step-size (inverse scale)
Figure 2: Statistical analysis of the number of iterations required for (SGD) to reach the global minimum of the three-hump camel function Fig. 1. For each value of 1/. we performed 500 runs of (SGD) initialized near p3 with Gaussian noise (or = 50), and we recorded the number of iterations required to reach the vicinity of #1 (within = 10-2). The resulting boxplots are displayed in log-inverse scale, with a point density overlay to illustrate the full empirical distribution of for every 7I. As per (4). we see that E[r] scales exponentially with 1/1.. To measure the goodness-of- fit, the dashed blue "Data" line represents linear regression fit for our data, while the solid red "Theory" line a linear fit with slope given by (4). The two fits have R² values of 0.99 and 0.97 respectively, indicating strong agreement between theory and experiment.
We find this characterization quite appealing because it al- lows us to quantify the features of (Opt) that make it harder or easier as a global problem. We will revisit this question several times in the sequel.
path ps ~ P4 ~ P3 P2 ~ ~ Pt. As a result, the mean global convergence time of (SGD) is not affected solely by the obstacles that lie the most "direct" path from the initialization to the global minimum of f, but also by the traps that the process can fall into along every other "indirect" path as well.
3 Problem setup and blanket assumptions
In this section, we begin our formal treatment of the global convergence time of (SGD). As a first step, we present below our standing assumptions for (Opt) and (SFO): these assumptions are not the weakest possible ones, but they lead to a more streamlined presentation; for a more general treatment, cf. Section 5 and Appendix B.
With all this in mind, when instantiated to the example at hand, the general analysis of Section 4 yields the following expression for the mean convergence time of (SGD):
Assumptions on the objective. To begin, we assume throughout that Rd is equipped with the Euclidean inner (4)
[x] exp (2(((2))) ((ps))
product and norm, denoted by (..)) and |I-Il respectively, We then make the following standing assumptions for f: Assumption 1.
11022
This expression shows that the global convergence time of (SGD) scales exponentially with the inverse of the step-size and the variance of the noise, and it is dominated by the objective value gap that X, must clear if it is trapped by ps- We verify experimentally the accuracy of this derivation in Fig. 2, where we measure r over several runs of (SGD) for different values of 17.
The objective function f: Rd - of (Opt) is -m-soo and satisfies the conditions below:
(a) Coercivity: lim fxx co.
(b) Gradient norm coereivity: || co.
(c) Lipschitz smoothness: the gradient of f is B-Lisschitz continuous, i.e.,
To provide some more context for all this, the precise pression for the coefficient of 1/n in (4) which we denote as Ep1lpp) in Section 4 - is obtained by aggregating the graph weights Bij according to the formula
[VV V s B|]x' -xll for x, Rd
(d) Critical set regularity: The critical set crit f = (x Idd vf(x) 0
E(pilp3) = B32+ + B54 min B14, B54) 2 max (p()) f(p)). f(ps)) (5)
of f consists of a finite number of closed, disjoint, smoothly connected components C,, i = 1,..., Nent-
02

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Remark. By "smoothly connected", we mean here that any two points in such component be joined by a smooth path contained therein. In the sequel, we will refer to these components simply as the critical components of f, and we will say that C; is a (locally) minimizing component of f if C = arg xe44 f(x) for some neighborhood U of C, $
the growth bound
||Z(x; 00.
sup
1 + ||>||
X,0
(c) Sub- Sab-Gaussian tails: The tails of Z are bounded as
log L e ((x
$ 2 ||ll
1
(8)
The requirements of Assumption 1 are fairly mild and quite standard in the literature. In more detail, Assumption I(a) simply ensures that arg min f is nonempty otherwise, the question of global convergence may be meaningless. Sim- ilarly, Assumption I(b) is a stabilization condition aiming to exclude functions with specious, near-critical behavior at infinity - such as f(x) log(1 I x²). Finally, terms of regularity, Assumption (cc) is the go-to hypothesis for the analysis of gradient methods, while Assumption (cd) rules out problems with pathological critical sets (such as Warsaw sine curves, Cantor staircase functions, etc.).²
for some and for all p E Rd.
Assumption 2(a) is standard in the field it ensures that the oracle G(x; w) provides unbiased gradient estimates; as for the ancillary covariance requirement, it serves to differenti- ate (SGD) from deterministic versions of gradient descent that are run with perfect gradients. Assumption 2(b) is a reg- ularity requirement imposing a mild limit on the growth of the noise as ||x|| - co, while Assumption 2(c) is a widely used bound on the tails of the noise. Importantly, even though Assumption 2(c) is less general than finite variance assumptions which allow for fat-tailed error distributions, it provides much finer control on the process and leads to a much cleaner presentation. We only note here that it can be relaxed further by allowing the variance parameter o² di- verge to infinity as ||x|| - co, in way similar to Langevin sampling under dissipativity [21, 43, 52, 53, 73]; this case is of particular interest for certain deep learning models, and we treat it in detail in Appendix B.
Assumptions on the gradient input. Our second set of assumptions concerns the stochastic gradients In that enter (SGD). Here we will assume that the optimizer has access stochastic first-order oracle (SFO), that is, a black-box mechanism which returns stochastic approximation of the gradient V (x) of f at the queried point x Rd. Formally, an SFO is random vector of the form
= ())
(SFO)
An illustrative use case. We close this section with an example intended illustrate the range of validity of our assumptions for (SGD). In particular, we will focus on the regularized empirical risk minimization (ERM) problem
where:
(a) The random seed w is drawn from a compact subset f of R" based on some probability measure P.
(b) The error term Z(x; w) captures all sources of random- ness and uncertainty in (SFO).
1 f(x) = -/4 N Σ (x:EE) +
A =11=11
(ERM,)
With all this in place, we will assume that (SGD) is run with stochastic gradients of the form
where ((x:g) is the loss of model against input & (e.g.. logistic or Savage loss), the data points E,, i = I,....N, comprise the problem's training set, and d > 0 is a regular- ization parameter. For example, this setup could correspond to a linear model with non-convex losses [21, 52], a neural network with smooth activations and normalization layers [46], etc. Accordingly, if we estimate the gradient of by sampling a random minibatch E (EI...., of training data (typically a small, fixed number thereof), the corre- sponding gradient oracle becomes
Ôn = G(Xn;
(SG)
where G is an SFO for f and wn, S2, n 0, l...., is sequence of i.i.d. random seeds as above. This well- established model accounts for all standard implementa- tions of (SGD), from minibatch sampling to noisy gradient descent and Langevin-type methods. The only extra assump- tions that we will make are as follows:
Assumption 2. The error term Z: Rd x xQ - Rd of (SFO) has the following properties:
G(x;
1 [w|
Σ v((x;)) gEw
(a) Propernsss: E[Z(x;w)) = 0 and cov (ov(Z(x; w)) > 0 for all x Idd.
Under standard assumptions for 6 e.g., twice continuously differentiable, Lipschitz continuous and smooth, cf. [57] and references therein - Parts (a)-(c of Assumption I are satisfied automatically. The resulting error term Z(x; w) is casily seen to be uniformly bounded, so Parts (a)-(c) of Assumption 2 are likewise verified [80, Exercise 2.4].
(b) Smooth growth: Z(x; w) is -m-smooth and satisfies
This last requirement be replaced by positing for example that f is semi-algehraic, cf. [5, 15, 76].
5

---

The Global Convergence Time of SGD in Non-Convex Landscapes
4
Analysis and results
Elements of large deviations theory. Moving forward, the first ingredient required to state our results is the Hamilto- nian of G, defined here as
We are now in a position to state our main results for the global convergence time of (SGD) under the blanket as- sumptions presented in the previous section. Our strategy to achieve this mirrors the general scheme outlined in Sec- tion 2: First, at high level, once (SGD) has reached neighborhood of a critical component of f (and, especially, a locally minimizing component), it will be trapped for some time in its vicinity. To escape this near-critical region, (SGD) may have to climb the loss surface of f, and this can only happen if (SGD) takes a sufficient number of steps "against" the gradient flow 1= (x) of f. Thus, to un- derstand the global convergence time of (SGD), we need to quantify these "rare events", namely to characterize (i) how much time (SGD) spends near given critical component; (it) how likely it is to transition from one such component to another; and (iii) what are the possible chains of transitions leading to the global minimum of f-
Ha(x, p) == log Eulepp((<pp ((x)))))))))))))
(13)
for all x E Rd and all p R Up to the sign in the exponent, HG p) is simply the cumulant- -eenraatngg function of the gradient oracle G at x, so it encodes all the statisties of (SGD) at Dually, the Lagrangian of G is given by the convex conjugate of Ha p) with respect to p, that is,
Co(x, = (x. 0) = mmx ((v, p) Ha p)}. (14)
PeR
The importance of the Lagrangian (14) lies in that it provides "pointwise" large deviation principle (LDP) of the form
1 P Σ G(x;wn) E B 11 K=0
expl -n inf Ca(x. .)) neB
(15)
To do this, we employ an approach inspired by the large deviations theory of Freidlin& & Wentzell [23] and Kifer [38, 40] for randomly perturbed dynamical systems on compact manifolds in continuous time. In the rest of this section, we only detail the elements of our approach that are needed to state our results in self-containee manner, and we defer the reader to the paper's 's appendix for the proofs (see also Appendix B.1 for outline of the proof).
for every Borel s Rd. In view of this LDP, the long-run aggregate statistics of the sum S, Σn= G(x; wx) are fully determined by LG [16]; however, even though the iterates In = x 1 2 G(xx:())) of (SGD) are likewise defined as a sum of SFO queries, obtaining "trajectory- I.DP for Xn is far more involved.
To address this challenge, the seminal idea of Freidlin & Wentzell [23] was to treat the entire trajectory Xn. n 0, l.... of (SGD) as a point in some infinite-dimensionall space of curves, and to derive large deviation principle for (SGD) directly in that space. To that end, drawing inspira- tion from the Lagrangian formulation of classical mechan- ics, the (normalized) action of LG along a continuous curve y: [0, - Rd is defined as
Generalities. To fix notation, we will assume in the sequel that (SGD) is initialized at some fixed xo e x E Rd, and we will write P3 and Ey (or sometimes Px,, and Ex,,) for the law of the process starting at Xo = x and the induced expectation respectively. Then, given a target tolerance objective will be to estimate the time required for (SGD) to get within ō of arg min f, that is, the hitting time
O, our main
Sr171= = S.' Lo(x(1))(1) di
T inf (n E N dist(xn. 5 6)
(10)
(16)
where, for notational brevity, we write
with the convention Sy[r] = co if y is not absolutely con- tinuous. In a certain sense - which we make precise in Appendix B.4 - the quantity Sr[y] is a "measure of likeli- hood" for the curve y, with lower values indicating higher likelihoods. This is the so-called "least action principle" of large deviations [23, 40], which we leverage below to char- acterize the most and least- likely transitions of (SGD).
arg f
(1I)
for the minimum set of f (which could itself consist of
several connected components). Throughout what follows, we will refer to as the global convergence time of (SGD), and our aim will be to characterize [,[r] as a function of the algorithm's 's initial state xo < x E Rdd
For future use, we also define here the attracting strength of Q as the maximal value of the product 2R2, where a and R are such that, for any x E Rd with dist(x, Q) S R.
The transition graph of (SGD). To achieve this character- ization, we start by associating a certain transition cost to each pair of critical components C, C2 of f. We will then use these costs quantify how likely it is to observe given chain of transitions terminating at the global minimum of f.
(vf(x)x-x')) x²) 2 xx12
(12)
with xx E Q denoting projection of x onto Q. In this way, (12) can be seen as a "setwise" second-order optimality condition for the global minimum of f. Intuitively, the large the attracting strength of Q, the sharper it is.
To begin, following Freidlin & Wentzell [23], the quasi- potential between two points pointsx,,x' E Rd is defined as
B(x,x)= = (nr[l] : Cx(x,' C(x,x')))TT Q,TEN) (17)
6

---

The Global Convergence Time of SGD in Non-Convex Landscapes
where xx,,;; 2) denotes the set of all continuous curves y: [0, [] - Rd with y(0) x, y(7) =x', and y(n) Q for all n = T-I." By construction, Bxx,x') is simply the cost of the "least action" path joining x to x' in time T and not hitting& 2 before that time. As such, the induced setwise cost is given by
as larget nodes, and all other nodes in V \ Q as non-target nodes. We then define transition forest for 2 to be directed acyclic subgraph T of G such that (i) target nodes have no outgoing edges; and (ii) every non-target node of T has precisely one outgoing edge. 6 In particular, this means that there exists a unique path from every non-target node E V Q to some target node j E O. The energy of Q is then defined to be the minimal cost over such forests, viz.
B(C, = inf(
E K.).
(18)
i.e. as the action of the "least costly" transition from some point in KC to some point in K'' which does not go through Q in the meantime. In this way, focusing on the critical components of f. we obtain the matrix of transition costs
E
Σ Bij TEG(C) UIJETT
min
(20)
where G(Q) denotes the set of all transition forests toward Q on G. In this way, the energy of Q represents the minimum aggregate cost of getting to Q, and it can be seen as an overall measure of how "easy" it is to reach Q.
Bij= = B(C, C2) for all j. = I...., Nerit (19)
which compactly characterizes the "ease" with which Xn may jump from C2 to Cy.
To account for the initialization of (SGD), we will need to perform a "pruning" construction, whereby we will system- atically delete different edges of 9 and record the impact of this deletion on the energy of 2. Formally, given starting node p V Q, we let = |V| - IQ] denote the number of "residual nodes") j e V that are neither starting (j # p) nor targets (j & Q). A pruning of from Q is then defined to be a directed acyclic subgraph S of G such that
We are now in a position to construct the transition graph of (SGD), generalizing the introductory example of Section 2. Formally, this is a weighted directed graph G = G(V.E.B) with the following primitives:
1. A set of vertices V indexed by i = I,..., Morit that is, one vertex per critical component of f. [To lighten nota- tion, we will not distinguish between the index and the component C₁ that it labels.]
1. S has r edges, at most one per non-target node j E V/ Q.
2. Target nodes have outgoing edges.
2. A set of directed edges E {(i.)) i.j I,..., ..at j. Bij < co). In words, i j if and only if the (direct) transition cost from C, to Cj is finite.
3. There is no path from to Q.
The energy required to prine p from Q is then defined as the minimal such cost, viz.
3. Finally, to each edge j) E E we associate the weight Bij-
E(p + 2
min SeL(pH ((.))ES
Σ Bij
(21)
To further streamline our presentation and ensure that the minimum set f can be reached from any initialization of (SGD), we will make the following assumption for G: Assumption 3. Bij- < for all i, j I...., Nemit
where G(p f Q) denotes the set of all prunings of p from Q in G. Then, to complete the picture, we define the energy of Q relative p E V Q as
This assumption is purely technical and holds automatically if there is "sufficient noise" in the process; for a detailed discussion, we refer the reader to Appendix C.4.
E(Q1p) E(2) - -E(p t Q)
(22)
= min TEG(g) (iJETT
Σ Bij
min SEG(p))) (i.)es
Σ Bij
Transition forests, energy levels, and prunings. We now have in our arsenal most of the elements required to quantify the difficulty of reaching Q = arg min f from an initial state x E Rdd As in the warmup setting of Section 2, we begin by describing the relevant walks of (SGD) on the associated transition graph g.
Finally, for given initialization x E Rd. we set
E(Q1x) = max [E(@)P) - (((())))(ssp)11.. PEVio
(23)
$In our case, the target nodes are simply the globally minimiz- ing components of f- To streamline notation, Q will he viewed interchangeably as a set points in Rd or as set of nodes V. 'Equivaeenlly, a transition forest for Q can be seen span- ning union of disjoint in-trees, each converging a target node. 'When Q is a singleton (i.c., arg min ff is connected), a transi- tion forest for Q is spanning in-tree, so our definition generalizes and extends that of Azizian et al. [5].
Given that we are interested in chains of transitions termi- nating at the target set Q, we will refer to all nodes in Q
We should note here that the curves that go the definition (17) of are only required to avoid Q at integer times. This is because, while a continuous curve may reach Q at non non-integer times, we only need to exclude integer times because we are only interested in the discrete-time process X,, not its continuous-time interpolations. We discuss this detail in Appendices B.4 and C.
'Equivalenly,, pruning of p from Q can be seen a spanning union of disjoint rooted in-trees, each rooted at some target node, except the one containing the starting node p, which is rooted a non-targer node.
7

---

The Global Convergence Time of SGD in Non-Convex Landscapes
i.e. [x) is the highest energy of Q relative to starting nodes p V1, Q that can be reached from x, modulo the cost of the initial transition x ~ p. This quantity measures the difficulty of reaching Q from x, and it plays a central role in our estimates of the global convergence time of (SGD).
This theorem is proved in Appendix D.4 as special case of the more general Theorems D.5 and D.6, and it shows that, conditioned on high probability event, the global convergence time of (SGD) starting at E R" is determined by the energy E p)) of Q relative to the minimizing component E V that attracts x under the gradient flow of f Intuitively, Theorem shows that all initial points in the basin of p will move to a small neighborhood of p with overwhelmingly high probability and, because this transition takes relatively little time, the global convergence time from to the global minimum is approximately equal to the convergence time from to Q. In the next section, we quantify the precise way that E(QIp) p) depends on the geometry of the problem's 's loss landscape.
The global convergence time of (SGD), We are finally in position state main estimate for the global conver- gence time of (SGD).
Theorem 1. Suppose that Assumptions 1-3 hold and (SGD) is initialized at x E Rd. Then, given a tolerance level & > 0, and small enough 5. 17 > O, we have
-6) [E(Q)x)
[E(11x)+6
exp
s B.[T] S exp
17
provided that the attracting strength of Q is large enough for the left inequality (lower bound).
5 Influence of the loss landscape
In this section, we explain how the energy E( of (22), which controls the global convergence time, depends on the noise, the depths of the spurious minima and their relative positions with respect to each other. We sketch the key elements and we refer to Appendix E for the full details.
This theorem provides matching upper and lower bounds for the global convergence time of (SGD) starting at x E Rd, and we prove it in Appendices B-D as a special case of the more general Theorems D.2 and D.3.9 Importantly, the sandwich bounds for scale exponentially with the inverse of the step-size 17 and show that the global convergence time of (SGD) is characterized by the pruned energy E Q x). In this sense, E(2) xx) characterizes the hardness of the non- convex optimization landscape for (SGD) and captures the fact that the hardness of global convergence stems from the presence of spurious local minima (that is, locally minimiz- ing components that are not globally minimizing). Indeed, as we show in Appendix D.6, the energy [([[x) [x) of Q relative to vanishes for all x if and only if there are no spurious minima, in which case T becomes subexponential.
The first step is to derive upper and lower bounds on the transition costs B.j. From Assumption 2(c), we have lower-bound on Biy for any i, : we have Bij 2 B,j where
Bij == inf sup 21000)))00))) y(0) E C.. y(T) E CJ T.y [
(24)
This means that the transition cost is at least equal to the maximal upward jump in the objective function that cannot be avoided when going from C, to Cj. To obtain the upper- bound, we need an extra assumption on the noise.
Moreover, when the initialization x E Rd belongs to the basin of specific minimizing component p. 10 Theorem can be restated in sharper manner that involves directly E(Q p) the energy of Q relative to p, instead of x (cf. (22)).
Extra noise assumption. While we only assumed a bound on the magnitude of the gradient noise (Assumption 2(c)), we now require in addition bound on the "minimal level of noise", through the following assumption. Assumption 4. The Lagrangian of G is bounded as
Theorem 2. Suppose that Assumptions 1-3 hold. Then, given a tolerance & > 0 and an initialization x E Rd that belongs to the basin of attraction of the (minimizing) com- ponent p V, there exist & > O and an event II with P. (H) -amn such that, for small enough 6, 11 > O,
LG(x, || ffx))
Vu ||o|| s fx)
20
we have
for all x in some large enough compact set.
exp E(Q1p)-
<EITT| S exp
[(() + + 7
This assumption is satisfied by general types of noise (in- cluding finite-sum models) given a lower-bound on the vari- ance of Z(x; w) and condition on the support; see Ap- pendix E. In particular, if Z(x; w) follows a (truncated) Gaussian distribution with a variance o², then Assump- tion 4 is satisfied with x² = (1 -1-38 =) where s depends
provided that the attracting strength of Q is large enough for the left inequality (lower bound).
9We should note here that the requirement on the attracting strength for the lower bound is purely technical: for more details, see the proof sketch Appendix B.
Importantly, this situation is generie: under standard assump- tions, the set of points that do not belong to such basin has measure zero
10 dispel any ambiguity, we mean here hasin of attraction for the gradient flow of f.
8

---

The Global Convergence Time of SGD in Non-Convex Landscapes
on the truncation level. In that case, the constant 2² of Assumption 2(c) can be taken as -² (1 x) (see Ap- pendix E.I). Note then that the ratio Ø² /²/0²r is close to 1, which will matter in the next theorem.
the formula of (5). In this case, the convergence time de- pends exponentially on the depths of the minima. However, different noise models would lead to qualitatively differ- ent results: Gaussian noise with variance scaling linearly with the objective value [61] would lead to a polynomial dependence on the depths of the minima. Our framework in Appendix E encompasses this case.
Transition between basins. With Assumption 4, we obtain quantitative upper-bounds on the transition costs between two neighboring components. More precisely, if C; and C are such that their basins of attraction intersect, then the cost of transitioning from C₁ to Cj is bounded by
Importantly, in the context of neural network training, our results offer way connect geometric properties of the loss landscape to sharp estimates of the convergence time of (SGD). Indeed, under certain conditions, neural networks have no spurious local minima [62, 64), in which case Theo- rem guarantees subexponential convergence to the global minimum of f. More to the point, even when spurious min- ima of bounded depth are present [66]. Theorems and provide way to translate these depth bounds directly into convergence time estimates for (SGD).
2 fi) Bij S
(25)
σ²
where fi, is the minimum of f over that intersection and fi is the value of f on G,
With these bounds. we recover immediately the example of Section 2. When the closure of the basin of C intersects Cj itself, fú, is simply the value of f on Cj and (25) simplifies to the same expression as in (3). The equality in (3) is thus obtained by combining (24) and (25) in the Gaussian case.
6 Concluding remarks
Our aim was to characterize the global convergence time of (SGD) in non-convex landscapes. Our characterization involves a pair of matching lower and upper bounds which captures the delicate interplay between (a) the geometry of the loss landscape of the problem's 's objective function; (b) the statistical profile of the stochastic first-order oracle that provides gradient input to (SGD); and (c) the hardest set of obstacles that separate the algorithm's 's initialization from the function's 's global minimum. In this sense, the character- istic exponent of our global convergence time estimate can be seen as a measure of the hardness of the non-convex min- imization problem at hand and, importantly, vanishes (resp. nearly vanishes) if the function admits no spurious local minima (resp. sufficiently shallow local minima), indi- cating transition to subexponential convergence times.
Graph structure. From the bounds of Bij. we can get bounds on E(QI p) as follows. We restrict the transition graph of Section 4 to neighboring components: we consider g' with vertices V and edges j ~ k if the closures of the basins of Cj and Cn intersect. Given path Pj= j ~ ji Jm in G' that ends in 2, we define its cost as
cost(P))
max max max(finnJess
Sin Sin
This cost involves the values of the objective function along the path from j to Q and captures the maximum depth of a minima encountered on the path: indeed, fin-Jn-1 - fj, represents the jump in the loss function when going from C, to C,a. while fin - fy represents the total jump when going from Cj to Cjnes
A concrete take-away of our analysis and results is that the global convergence time of (SGD) scales exponentially in (a) the inverse of the step-size: (b) the variance of the noise; and (c) the depth of any spurious minima of f. Among oth- ers, this has explicit ramifications for (overparameterrzze) neural nets: in order to escape the exponential regime, the depth of spurious minimizers must scale logarithmically in the dimension of the problem which, in turn, indicates the depth (or width, depending on the model) that a neural net must have in order to reach a state with near-zero empirical loss in subexponential time.
Result and discussion. With the above quantities, we can establish that the energy E(Q p), that governs the global convergence time of Theorem 2, is bounded as follows.
Theorem 3. Under Assumptions for p VV Q
2cost(P)) a²
1- -
E(Q1p) s max min j:B pj Sr Pj
(26)
for some r > 0 that depends on the graph structure G'.
From broader theoretical perspective, our results also pro- vide a flexible analysis template to tackle a wide range of stochastic -adeedttbbsed algorithms, such as Adam, os- cillatory step-size schedules, etc., as well as the study of interpolation and its influence on the global convergence landscape of (SGD). We defer these investigations to the future.
This means that E Q p) is bounded by the maximum depth of the minimizers that SGD must go through in order to reach Q This involves all the paths in G' that start at a component close to p. as measured by B,y
Consider, for instance, the example of Section 2: the bound of Theorem 3 is attained for ps- ~ p3 ~ P1 and we recover

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Acknowledgments
Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Hcidelberg, 1999.
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA-000) the "Investisse- ments d' avenir" program (ANR--1-IDEX--O
[9]
Benaim, M. and Hirsch. M. W. Dynamics of Morse- Smale urn processes. Ergodic Theory and Dynamical Systems, 15 16):100510030, December 1995.
the LabEx PERSYVAL A 11-1111-BBBX-005--011 and project SPICE (G7H-IRG24E90). PM is also a member of the Archimedes Research Unit/Athena Research Center, and was partially supported by project MIS 5154714 of the National Recov- ery and Resilience Plan Greece 2.0 funded by the European
[10] Bertsekas, D. P. and Tsitsiklis, N. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization,
10(3):277-422, 2000.
[11] Blanc. G., Gupta, N., Valiant, G., and Valiant, P. Implicit reg- ularization for deep neural networks driven by an Ornstein- Uhlenbeck like process. In Conference on learning theory, Pp. 483-513. PMLR, 2020.
Union under the NextGenerationEU Program. This work was granted access to the HPC resources of IDRIS under the allocation AD011015865 made by GENCL The authors would like to thank the anonymous reviewers for their con- structive feedback and suggestions that helped improve the quality of this work.
[12] Borkar, V. Stochastic Approximation: A Dynamical Sys- tems Viewpoint. Cambridge University Press and Hindustan Book Agency, 2008.
[13] Brandière, O. and Duñlo, M. Les algorithmes stochastiques contournent-ils les pièges ? Annules de I'Institut Henri Poincaré, Probabilités et Statistiques, 32())395-433 1996.
[14] Christof. C. and Kowalczyk. J. On the Omnipresence of Spurious Local Minima in Certain Neural Network Training Problems. Constr Apprex. June 2023, ISSN 1432-0940. doi: 10. 0/1//000065-002-99666-
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
[15] Coste, M. An introduction to o-minimal geometry. November 1999.
[16] Dembo, A. and Zeitouni, O. Large Deviations Techniques and Applications. Springer-Verlag Berlin, 1998.
[17] Dieuleveut, A., Durmus, A., and Bach, F. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3), 2020.
References
[1] Allen-Zhu, Z., Li, Y., and Song, 7. A convergence theory for deep learning via over-parameterriztion. In International conference on machine learning, pp. 242-252. PMIR, 2019. [2] Antonakopoulos, K., Mertikopoulos, P., Piliouras, G., and Wang, X. AdaGrad avoids saddle points. In ICML '22: Pro- ceedings of the 39th International Conference Machine Learning, 2022.
[18] Douc, R., Moulines, E.,, Priouret, P., and Soulier, P. Markor Chains. Springer Series in Operations Research and Financial Engincering. Springer International Publishing, Cham, 2018.
[19] Du S., Lee. J., Li, H., Wang. L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675- 1685. PMLR, 2019.
[3] Arjevani. and Field, M. Annihilation of spurious minima in two-layer relu networks. Advances in Neural Information Processing Systems, 35:37510-3755
[20]
Dupuis, P. and Ellis, R. S. Weak Convergence Approach to the Theory of Large Deviations. Wiley Series in Probability and Statistics. Wiley, New York, 1997. ISBN 978-0-471- 07672-8.
2022.
[4] Azizan, N., Lale, S., and Hassibi, B. Stochastic Mirror De- scent on Overparameterized Nonlinear Models. IEEE Trans. Neural Netw. Learning Syst. 33(12):777-7727 December 2022. ISSN 2162-237X, 2162-2388 2021 021.7807480.
[21] Erdogdu, M. A., Mackey, L. W. and Shamir, O. Global non- convex optimization with discretized diffusions. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
doi: 109.1NS/
[22] Freidlin, M. and Wentzell, A. D. Random Perturbations of Dynamical Systems. Springer, edition, 1998.
[5] Azizian, W., lutzeler, F., Malick, J., and Mertikopoulos, P. What is the long-run distribution of stochastic gradient de- scent? A large deviations analysis. In ICML '24: Proceed- ings of the st International Conference on Machine Learn- ing. 2024.
[23] Freidlin, M. and Wentzell, A. D. Random Perturbations of Dynamical Systems. Springer, 3 edition, 2012.
[24] Ge, R., Huang, F., Jin, C., and Yuan, Y. Escaping from saddle points Online stochastic gradient for tensor decompasition. COLT 11: Proceedings of the 28th Annual Conference on Learning Theory, 2015.
[6] Bajovic, D., Jakovetic, D., and Kar, S. Large deviations rates for stochastic gradient descent with strongly convex fune- tions. International Conference on Artificial Intelligence and Statistics, pp. 10095-10111. PMLR, 2023.
[25] Gesd, G. D., Lelièvre, T., Peutrec, D. L., and Nectoux, B. Sharp asymptotics of the first exit point density, Annals of PDE, 5:1-174, 2019.
[7] Baudel, M., Guyader, A., and Lelièvre. T. On the hill re- lation and the mean reaction time for metastable processes. Stockastic Processes and their Applications, 155:393-436, 2023.
[26] Gurbuzbalaban, M., Simsekli, U., and Zhu, L. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning (ICML), pp. 9964-3975. PMLR, 2021.
[8] Benaïm, M. Dynamics of stochastic approximation algo- rithms. In Azéma, J., Emery, M., Ledoux, M., and Yor, M.
[27] Hodgkinson, L. and Mahoney, M. Multiplicative noise and heavy tails in stochastic optimization. In International
(eds.), Séminaire de Probabilités XXXIII, volume 1709 of
10

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Conference on Machine Learning (ICML), pp. 4262-4274.
Foundations. Journal of Machine Learning Research, 20(40):
PMLR, 2021.
1-47, 2019.
[28] Hsieh, Y.PP., Mertikopoulos, P., and Cevher, V. The limits of min max optimization algorithms: Convergence to spurious non-critical sets. In ICML '11 Proceedings of the 38th International Conference on Machine Learning. 2021.
[46] Li, Z. Lyu, K., and Arora, S. Reconciling modern deep learning with traditional optimization analyses: The intrinsic learning rate. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 14544-14555, 2020.
[29] Hsieh, Y.-P.. Karimi, M. R., Krause, A., and Mertikopoulos,
[47] Li, Z., Wang. T., and Arora, S. What happens after SGD reaches zero loss?-a mathematical framework. In Inter- national Conference on Learning Representations (ICLR),
P. Riemannian stochastic optimization methods avoid strict saddle points, In NeurIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023.
2021.
[48] Li, Z., Wang. T., and Yu, D. Fast mixing of stochastic gradient descent with normalization and weight decay. In Ad- vances in Neural Information Processing Systems (NeurIPS), volume 35, pp. 9233 9248, 2022.
[30] Hu, W., Li, C. J., Li, L., and Liu, J.-G. On the diffusion approximation of nonconvex stochastic gradient descent. An- nals of Mathematical Sciences and Applications, 4(1):3 32, 2019.
[49] Liu, C., Drusvyatskiy, D., Belkin, M.. Davis, D., and Ma, Y-A. Aiming towards the minimizers: Fast convergence of SGD for overparametrized problems, June 2023.
[31] Hult, H., Lindhe, A., Nyquist, P., and Wu, G.-J. A weak convergence approach to large deviations for stochastic ap- proximations. 2023.
[50] Ljung. L. Analysis of recursive stochastic algorithms. IEEE Transactions on Automatic Control, 22(4):551-577 August
[32] Islamov, R., Ajroldi, N., Orvicto, A., and I Lucchi, A. Loss landscape characterization of neural networks without over- parametrization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: // /openreview net/ fto///rrrdddd// "arrummmdddh03355ttXXX
1977.
[51] Ljung. L. Strong convergence of a stochastic approximation algorithm. Annals of Statistics, 6(3).680 696, 1978.
[52] Lu, Y., Balasubramanian, K., Volgushev, S., and Erdogdu, M. A. An analysis of constant step size sgd in the non-convex regime: Asymptotic normality and bias. In Advances Neu- ral Information Processing Systems (NeurIPS), volume 34, 2021.
[33] Jastrzehski,, S., Kenton, Z., Arpit, D., Ballas, N., Fischer, A., Bengio, Y. and Storkey, A. Three factors influencing minima in sgd. arXiv preprint ar
2017.
[34] Jordan, R., Kinderlehrer, D., and Otto, F. The variational formulation of the Fokker-Planck equation. SIAM Journal on Mathematical Analysis, 177,, January 1998.
[53] Lytras, I. and Mertikopoulos, P. Tamed Langevin sampling under weaker conditions. bettps//arxiv..oo www. ab4/2405. 17693, 2024.
[35] Karimi, M. R., Hsieh, Y.-P., Mertikopoulos, P., and Krause, A. The dynamics of Riemannian Robbins-Monre Monro algorithuss. In COLT '22: Proceedings of the 35th Annual Conference on Learning Theory, 2022.
[54] Marion, P., Wu, Y.-H., Sander, M. F.,, and Biau, G. Im- plicit regularization deep residual networks towards neural ODEs. In The Tweifih International Conference on Learn- ing Representations, 2024, URL https// btttps///opene httpes///ppeeeeie.eeomm nnt//
[36] Kawaguchi, K. Deep learning without poor local minima. In NIPS 16: Proceedings of the 30th International Conference Neural Information Processing Systems, 2016.
torum?dd-AbGGwpppoa
[55] Mertikopoulos, P. and Staudigl. M. On the convergence of gradient-like flows with noisy gradient input. SIAM Journal on Optimization, 28(1) 28(1):163-19)) January 2018.
[37] Kiefer, J. and Wolfowitz, J. Stochastic estimation of the max- imum of a regression function. The Annals of Mathematical Statistics, 236646662-466, 1952.
[56] Mertikopoulos, P. and Staudigl. M. Stochastic mirror descent dynamics and their convergence in monotone variational in- equalities. Journal of Optimization Theory and Applications, 1 179(3):3388867 December 2018.
[38] Kifer, Y. Random Perturbations of Dynamical Systems.
Birkhäuser, Boston, MA, 1988
[39] Kifer, Y. Random Perturbations of Dynamical Systems. Birkhäuser Boston, Boston, MA, 1988
[57] Mertikopoulos, P., Hallak. N., Kavis, A., and Cevher, V. On the almost sure convergence of stochastic gradient descent in non-convex problems. In NewrlPS '20: Proceedings of the 34th International Conference Neural Information Processing Systems, 2020.
[40] Kifer, Y. A discrete-time version of the Frrizell-Freidlin theory. Annals of Probubility, 1864):1676-162, October 1990.
[41] Lan, G. First-order and Stochastic Optimization Methods for Machine Learning. Springer, 2020.
[58] Mertikopoulos, P., Hsieh, Y.P.., and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Programming, 203:559-660 609, January 2024.
a
[42] Li, D., Ding, T., and Sun, On the benefit of width for neural networks: Disappearance of basins. SIAM Journal on Optimization, 32(3): 1728-17.88 2022.
[59] Mignacco, F. and Urbani, P. The effective noise of stochastic gradient descent. Journal of Statisticul Mechanics: Theory and Experiment, 2022(8):0834005 2022.
[43] Li. L. and Wang. Y. A sharp uniform-in-time enror estimate for Stochastic Gradient Langevin Dynamics. arXiv preprint arXiv:2207.00 000000099044 2022.
[60] Mignacco, F., Krzakala, F., Urbani, P., and Zdeborová, L. Dynamical mean- field theory for stochastic gradient descent gaussian mixture classification. In Advonces in Neural Information Processing Systems (NeuriPS), volume 33, pp- 9540-9550, 2020.
[44] Li, Q. Tai, C., and Weinan, F. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning (ICML), pp. 2101-2110. PMLR, 2017.
[61] Mori, T., Ziyin, I.., Liu, K., and Ueda, M. Power-law es- cape rate of sgd. In International Conference on Machine Learning (ICMLJ, pp. 15999-15975.. PMIR, 2022.
[45] Li, Q., Tai, C.,, and F, W. Stochastic Modified Equations and Dynamics of Stuchastic Gradient Algorithms I: Mathematical

---

The Global Convergence Time of SGD in Non-Convex Landscapes
[62] Nguyen, Q. and Hein, M. The loss surface of deep and wide neural networks. In International conference on machine learning, pp. 2603-2612. PMLR, 2017.
[79] Vlaski, S. and Sayed, A. H. Second-order guarantces of stochastic gradient descent in non-convex optimization. https://arxiv. httpaaawwww...aaaaaeeeeeeoooeeee wwwgaa// htbbs//99..0023, 2019.
[63] Nguyen, Q. and Hein, M. Optimization landscape and expres- sivity of deep cnns. In International conference on machine learning, pp. 3730-3739. PMIR, 2018.
[80] Wainwright, M. J. High-dimensional statistics: A non-
asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[64] Nguyen, Q. Mukkamala, M. C., and Hein, M. On the loss landscape of class of deep neural networks with no bad local valleys. In International Conference on Learning Repre- sentations, 2019. URL https// / wowerevveeweeeeeeeeeeeeeeoe net/forum? id AB:Q
[81]
Wang. X., Oh, S., and Rhec, C.-H. Eliminating sharp minima from SGD with truncated heavy-tailed noise. In International Conference Learning Representations, 2022. URL https:
/ //apenreviww
[82] Wang, Y. and Wang, Z. Three-stage evolution and fast equi- librium for sgd with non-degerate critical points. In Interna- tional Conference on Machine Learning (ICML), pp. 23092- 23113. PMLR, 2022.
[65] Nguyen, Q. N. and Mondelli, M. Global convergence of deep networks with one wide layer followed by pyramidal topol-
ogy. Advances in Neural Information Processing Systems, 11:199 2020.
[83] Wang, Y., Lacotte, J., and Pilanci, M. The hidden convex op- timization landscape of regularized two-layer reI.U networks: an exact characterization of optimal solutions. In Interna- tional Conference on Learning Representutions, 2022. URL attps://openreeeee wttpenrvviewwnne/eeeee wtwpt//foommddd--eeeeee http://rmmmddd2/1122EEE--
[66] Nguyen, Q. N., Bréchet, P., and Mondelli, M. When are solutions connected in deep networks? Advances in Neural Information Processing Systems.
0122096622966 2021.
[67] Nguyen, T. H., Simsekli, U., Gurbuzbalaban, M., and
RICHARD, G. First Exit Time Analysis of Stochastic Gra- dient Descent Under Heavy-Tailed Gradient Noise. In Ad- vances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[84] Weinan, E., Ma, C., Wang. Q. and Wu, L. Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections. ArXiv, April 2019.
[85] Wojtowytsch, S. Stochastic gradient descent with noise of machine learning type part i: Discrete time analysis. Journal of Nonlinear Science, 33(3):45, 2023,
[68] Oymak, S. and Soltanolkotabi, M. Toward moderate overpa- rameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105 105, 2020.
[86]
Xie, Z., Sato, I., and Sugiyama, M. diffusion theory for deep learning dynamics: Stochastic gradient descent expo- nentially favors flat minima. In International Conference on Learning Representations (ICLR), 2020.
[69] Pavasovic, K. L., Durmus, A., and Simsekli, U. Approxi- mate heavy tails in offline (multi-pass) stochastic gradient descent. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2023.
[87] Yang. J., Hu, W., and Li, C. J. On the fast convergence of random perturbations of the gradient flow. Asymptotic Analysis, 122((-4):371 1-333311111111333 2021.
[70] Pemantle, R. Nonconvergence to unstable points in urn models and stochastic aproximations, Annals of Probabilit, 18(2):698-71 712,, April 1990.
[88] Zhang. H., Yu, D., Yi. M., Chen, W., and Liu, T.-Y. Stabilize deep resnet with sharp scaling factorr T. Machine Learning, 1 111(9):359-3392, 2022.
[71] Petzka, H. and Sminchisescu. C. Non-attracting Regions of Local Minima in Deep and Wide Neural Networks. Journal of Machine Learning Research, 22(143): 2021. ISSN 1533-7928.
[89] Zhou, Z., Mertikopoulos, P., Bambos, N., Boyd, S. P.,, and Glynn, P. W. Stochastic mirror descent for variationally coherent optimization problems. In NIPS '17 Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
[72] Pollaci, S. Spurious valleys and clustering behavior of neural networks. In International Conference on Machine Learning, pp. 28079-28099. PMLR, 2023.
[90] Zhou, Z., Mertikopoolos, P., Bambos, N., Boyd, S. P., and Glymn, P. W. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal Optimiza- tion, (0(1))687-766 2020.
[73] Raginsky, M., Rakhlin, A., and Telgarsky, M. Non- convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory (COLT), pp. 1674 1703. PMLR, 2017.
[91] Zou, D. and Gu, Q. An improved analysis of training over- parameterized deep neural networks. Advances in neural information processing systems, 32, 2019.
[74] Robbins, H. and Monro, S. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407, 1951.
[92] Zou, D., Cao. Y., Zhou, D., and Gu. Q. Gradient descent optimizes over-parametterized deep relu networks. Muchine learning. 109:467-499 4922, 2020.
[75] Staib, M., Reddi, S., Kale, S., Kumar, S., and Sra, S. Escap- ing saddle points with adaptive gradient methods. In ICMI. 19: Proceedings of the 36th International Conference on Machine Learning, 2019.
[93] Zou, D., Long, P. M., and Gu, Q. On the global conver- gence of training deep linear resnets. In International Con- ference on Learning Representations, 2020. URL https: //openreview ///pparreieevnne//oountttt--- http:/oouum//dd-toxuRRROOO
[76] Van Den Dries, L. and Miller, C. Geometric categories and
O o-minimal structures. Duke Math. J., 84(2), August 1996.
[77] Veiga, R., Remizova, A., and Macris, N. Stochastic gradient flow dynamics of test risk and its exact solution for weak features. arXiv preprint arXiv:2402.076:: 0766666666666. 2024.
[78] Venturi, L.,, Bandeira, A. S., and Bruna, J. Spurious valleys in one hiddeidde-llayrr neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1-34, 2019.
12

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Appendices
A Related work
15
(SGD) as discrete-time Markov chain
15
A.2 The diffusion approximation
15
A.3 Exit times for (SGD)
15
A.4 Overparameterized neural networks
15
A.5 LDP for stochastic algorithms
16
B Large deviation analysis of SGD
17
B.1 Outline proof
17
B.2 Setup and assumptions
17
B.3 Hamiltonian and Lagrangian
20
B.4 A large deviation principle for SGD
21
B.5 Return to critical points
22
B.6 Attractors
22
B.7 Convergence and stability
22
Transitions
24
C.I Setup
24
C.2 Induced chain
24
C.3 Estimates of the transition probabilities
25
C.4 Accelerated induced chain
28
C.5 Initial transition
30
C.6 Transition time
32
D Finite-Time Analysis
35
D.1 Markov Chains on finite state spaces
35
D.2 Hitting time of the accelerated process
35
D.3 Hitting time of SGD
39
D.4
Basin-dependent convergence result
45
D.5 Full transition costs
49
D.6 Link to topological properties of the loss landscape
50
E Potential-based Bounds
52
E.1 Noise assumptions
52
E.2 Potentials and path reversal
54
E,3 Graph representation
56
F Numerical validation
61
13

---

The Global Convergence Time of SGD in Non-Convex Landscapes
G
Auxiliary results
63
G.1 Truncated Gaussian distribution
63
14

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Related work
A.1 (SGD) discrete-time Markov chain
In a relatively recent thread in the literature, Dieuleveut et al. [17] and Lu et al. [52] undertook study of (SGD) discrete-time Markov chain. This allowed Dieuleveut et al. [17], Lu et al. [52] to derive conditions under which (SGD) is (geometrically) ergodic and, in this way, to quantify the distance to the minimizer under global growth conditions. Building further on this perspective, Gurbuzbalaban et al. [26], Hodgkinson & Mahoney [27] and Pavasovic et al. [69] showed that, under general conditions, the asymptotic distribution of the iterates of (SGD) is heavy-tailed; As such, these results concern the probability of observing the iterates of (SGD) at very large distances from the origin. This is in contrast with our work, which focuses on the time it takes (SGD) reach a global minimizer. These two types of results are orthogonal and complementary to each other.
A.2 The diffusion approximation
A classical thread in the literature- and the foundation of Langevin sampling methods revolves around gradient flows perturbed by Brownian noise in continuous time; in this case, it is possible to get en explicit expression for the invariant measure of the resulting stochastic differential equation (SDE) [34], or estimate it in more difficult, constrained cases [8, 12. 55, 56, 89. 90]. Owing to our understanding of gradient-based SDEs, an important thread in the literature concerns the so-called SDE approximation of (SGD), as pioneered by Li et al. [44, 45]. Applications of this SDE approximation include the study of the dynamics of (SGD) close to manifolds of minimizers [11, 47] or Yang et al. [87] which quantifies the global convergence of the diffusion approximation of (SGD) when the function has no spurious local minima. When the objective function is scale-invariant [46], we can obtain further results: Wang & Wang [82] describes the convergence of the SDE approximation to its asymptotic regime, while Li et al. [47, 48] also quantify the convergence (SGD) initialized close to minimizers.
Another line of work leverages DMFT to study the behavior of the diffusion approximation of (SGD) [59, 60, 77J. The DMFT, or prath-integral" approach, comes from statistical physics and bears a close resemblance to the Freidlin-Wentzell theory of large deviations for SDEs. All these results are either local or concern the asymptotic behaviour of the continuous- time approximation of (SGD). They do not provide information of the global convergence time of the actual discrete-time (SGD), since the approximation guarantees fail to hold on large enough time intervals.
A.3 Exit times for (SGD)
In our work, we study how long takes for (SGD) to reach global minimizer. There vast literature that instead seeks understand how long it takes for (SGD) to exit local minimum. For this, these works study either the diffusion approximation [7, 25, 30, 33, 61, 86] or heavy-tail versions of this diffusion [67, 81]. Interestingly, some of these works use elements of the continuous-time -rentein theory [22], which is also the point of departure of our paper.
Note that studying exit times it not enough to characterize the convergence time of (SGD) to a global minimizer. In fact, a simple way to see this is given by our introductory example in Section 2. Indeed, in this case, the escape time of p3 scales exponentially in fp2) f(3)) (the depth of p3) while the escape time of ps would scale exponentially in f - f(ps). However, the global convergence time of (SGD) as determined by (4) is greater than either of these two exponentials: indeed, our result takes into account that, when in the vicinity of pa. (SGD) could transition to ps instead of #1 an arbitrary number of times. Hence, characterizing escape times is not enough to describe the global convergence time of (SGD) in general.
A.4 Overparameterizze neural networks
The pioneering work of [1, 19, 92] show convergence for neural networks: overparameterization and Gaussian initialization enable convergence to global minimum. Among the many subsequent works, let mention [4, 84, 88, 91, 93]. In particular, with N denoting the number of training datapoints, this type of results require either O(i2)-width with Gaussian initialization [65, 68] or O -WNitwidth under additional structure: infinite depth [54] or specific initialization [49, 65]. Our work addresses a different question as it provides a convergence analysis on general non-convex functions, regardless of the structure of the objective or the initialization.
fruitful line of works studies the geometric properties of the loss landscapes of neural networks, and in particular whether they contain spurious local minima [36). Nguyen & Hein [62], Nguyen al. [64] show that there are spurious local
15

---

The Global Convergence Time of SGD in Non-Convex Landscapes
minima, "bad valley", if the architecture possesses hidden layer with width least N. There are many refinements: e.g. leveraging the structure of the data [78], considering regularization [83], convolutional neural networks [63] other variations of the architecture [3, 71, 72, 83J. Moreover, Li et al. [42] shows that this requirement is tight for one-hidden layer neural networks, in some settings. When the sizes of the hidden layers are smaller than N, the loss landscape does generally have spurious local minima [14]. Interestingly, in this case, the depth of these spurious can be explicitly bounded [66] and made arbitrarily small with hidden layers of size only vN.
Another fundamental property of overparameterized neural networks is that they can perfectly fit the training data and therefore, the noise of (SGD) vanishes at the global minimum. In this setting, under sufficient noise assumption everywhere else, Wojtowytsch [85], shows that (SGD) reaches neighborhood of global minimizer almost surely, gets trapped in this neighborhood and then converges to the global minimizer with provided asymptotic rate. Our work can be seen as precise estimation of the time to reach the neighborhood of the global minimizer.
Also motivated by the interpolation phenomenon, Islamov et al. [32] introduces the so-called a - B condition and shows a global convergence of (SGD) under this condition. Though this condition is much weaker than convexity, only ensures that the function value the iterates becomes less than the max of the values over all critical points. In contrast, our work characterizes the time convergence global minimizer for any non-convex landscape.
A.5
LDP for stochastic algorithms
Our mathematical development use large deviation results for stochastic processes; see e.g., the monographs of Dupuis & Ellis [20], Freidlin & Wentzell [22]. More precisely, rely the large deviation result [5, Cor. C.2), which is an application of the theory of Freidlin & Wentzell [22]. Let us also mention two recent works large deviations in optimization settings: [6] that studies (SGD) with vanishing step-size strongly convex functions and Hult et al. [31] that considers general stochastic approximation algorithms.
16

---

The Global Convergence Time of SGD in Non-Convex Landscapes
B
Large deviation analysis of SGD
B.1 Outline of proof
Before reviewing notations and assumptions, we provide an overview of the proof of our main results Theorems 1 and 2.
Our framework is built on large deviation principle for SGD (Appendix B.4): it yields precise estimations of the probability that SGD approximately follows an arbitrary continuous- cimiiuuouu-tmeeeeeoo path. In particular, this LDP concerns the accelerated (subsampled) SGD process x n = 0, I...., defined as
X XnLi/nl
(B.1)
We rely on the LDP from [5]that we restate in Appendix B.4. Note that this LDP is obtained consequence of [22, Chap. 7] by comparing the process (x))m20 to its continuous-timg time linear interpolation (X(r)) defined by
(r) = X, + t- m1 (Xne1 - xn))
(B.2)
for all A = 0, I, and all r E [nn,, (n+ 1)nl. This is why the action function (16) is defined in terms of continuous time.
Our framework also builds on two other key results from [5]. First, we need Lemma B.3 restated in Appendix B.5 that provides a control on the return time of SGD to a neighborhood of the set of critical points. In particular, it shows that the distribution of this return time is roughly sub-exponential. Second, we require the careful analysis done in [5ht exploits the structure of the set of critical points to obtain regularity properties on (16) locally, see Appendix B.6.
In Appendix C, we study the transitions of SGD, more precisely the sequence of (B.1), between connected components of critical points. In short, we characterize the probability that the iterates of (B.1) transition from one component of critical points to another as well as the time it takes to do so. It is because of this new requirement compared to [5]that we have to refine their estimates. For this, we introduce an induced Markov chain (zn) (Definition 8) that lives on the set of critical components and captures the essential global convergence properties.
With the transition probabilities and times in hand, the system can now be analyzed as a finite state space Markov chain whose states are the components of the set of critical points. Leveraging the tools of Freidlin & Wentzell [22], restated in Appendix D.I, we obtain a characterization of the global convergence time of (B.1) the set of critical points in Appendix D.2.
The only thing left to do is to translate the results obtained for the subsampled process of (B.1) 1) back to the original process of SGD (Appendix D.3). The upper-bound is immediate but the lower-bound needs some care. This is where the attracting strength defined in Section comes into play: if the attracting strength is large enough, we can show that when SGD reaches neighborhood of a global minimum, it will remain there enough time for the next iterate of the subsampled process of (B.1) to still be in that neighborhood. This in turn allows us show the global convergence times of SGD and the subsampled sequence roughly coincide, concluding the proof of Theorem 1.
Appendix D.4 is then dedicated to obtaining Theorem 2 while Appendix D.6 establishes the link between the presence of spurious local minima and a non-zero energy.
The results of Section 5 are then obtained in Appendix E. For convenience, the main dependencies between sections of the appendix are summarized in Fig,
B.2 Setup and assumptions
Before we begin our proof, we introduce here notations and we revisit and discuss our standing assumptions. In particular, to extend the range of our results, we provide in the rest of this appendix a weaker version of the blanket assumptions of Section 3 which will be in force throughout the appendix.
We equip Rd with the canonical inner product (.--) and the associated Euclidean norm ||.|]. We denote by (x,,)) (resp. Bxx, r)) the open (resp. closed) ball of radius r centered xt.
We also also define, for any A C Rd.
Us(A) = (x E Rd d(x, A) < <t..
(B.3)
17

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Prerequisite Results
B.4 Return
finite spaces
Analysis Of Transtions
Setup, C.2 Induced Chain, C.3 Estmatess of the trensitin probsbilties
C.6 Transition time
C.5 Initial transiiion
C.4 Accelerated induced chain
Finte- Time Anausis
D.2 Hitting time the accelerated
D.3 Hitling time SGD
Basin dependent convergence result
Interpretations And Appications
E.1 Noise assumptions
E.2 Potentials and path reversal
D.5 Full transition costs
E.3 Graph representation
D.6 Link topological properties the loss landscape
Figure 3: Structure of the proof: arrows represent the main logical implications between the main parts of the proof. The group "Prerequisite results" gathers the tools from the literature that rely on, mostly either from [4, 20, 21J. Our key technical contributions that lead to Thm. 1-2 are "Analysis Of Transitions" and "Finite Time Analysis". The results of $5 come from "Interpretation and Applications".
For any 7' > O, we denote by C((O,]) C([0,7], Rd) the set of continuous functions from [0, 7] to Rd
18

---

The Global Convergence Time of SGD in Non-Convex Landscapes
We begin with our assumptions for the objective function f. which are weaker version of Assumption Assumption 5. The objective function f: IRd - R satisfies the following conditions:
(a) Coercivity: f(x) as ||x|| co.
b Smoothness: f is C² --ddifferentiable and gradient is B-Lipschitz continuous, namely
[V vs(()l & B||x'' -x
for all x, e R
(B.4)
Assumption (Critical set regularity). The critical set
crit(f) = (XER" Vf(x) =
(B.5)
of f consists of a finite number of (compact) connected components. Moreover, each of these components connected by piecewise absolutely continuous paths, i.e., for any x' KC there exists E C((O, I], such that yo = x, Y1 = and such that it is piecewise absolutely continuous, i.e., y differentiable almost everywhere and there exists 0 to < 11 IN I such that y integrable on every closed interval of (bn, (n+1) for ......N
Note that, since connected components of closed set are closed, Assumption 5 automatically ensure that the connected components of crit( f) are compact.
Unlike in Assumption 1, we do not require the connected components of crit f to be smoothly connected but only piecewise absolutely continuous.
Remark B.I. The path-connectedness requirement of Assumption 6 is satisfied whenever the connected components of crit( f) are isolated critical points, smooth manifolds, or finite unions of closed manifolds. More generally, Assumption 6 satisfied whenever is definable in which case crit is also definable, each component be connected by piecewise smooth paths [15, 76]. The relaxation provided by Assumption 6 represents the "minimal" set of hypotheses that are required for our analysis to go through.
Moving forward, to align our notation with standard conventions in large deviations theory, it will be more convenient to work with (w): instead of Z(x; w) in our proofs. To make this clear, restate below Assumption 2 in terms of the noise process
uxx, w) w)
(B.6)
We also take the chance to relax the definition of the variance proxy of u, which requires the new assumption Assumption 8. Assumption 7. The error term Rd x Q Rd satisfies the following properties:
(a) Properness: B[u[x, ()) 0 and cov(u(x, w)) > 0 for all e Rd.
(b) Smooth growth: u(x, w)) C'ddifferentiabee and satisfies the growth condition
| w0
sup x,6
<00
(B.7)
1 |x||
(c) Sub- Gaussian tails: There is ::: R - (0,+00 continuous, with inf gd o 0. such that u(x, w)) satisfies
log E (o.(xx..)))) S 2
(f(((())
1|p for all E Rd
(B.8)
Assumption 8. The signal-to-noise ratio of G is bounded as
lim inf [()(1 [xil =00 fxx
16 16
(B.9)
Furthermore, (.(() =(t?) too and,
rof(() is bounded above and below infinity for s E [0,2], i.e. [x|
02 o f(x)
oā f(x)
0 lim inf
and
lim sup [
< 400.
(B.10)
x +400
||*||
|||||>
19

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Remark B.2. The key distinction between Assumption 2 and Assumptions 7-8 stems from their differing requirements for the variance proxy oh of the noise in (SGD). Since is coercive, allowing o depend f(x) enables consider noise processes whose variance may grow unbounded as ||x||| - specifically choose express this dependence through f(x) rather than directly through x as it substantially simplifies both our proofs and calculations. A version of Assumption adapted to this generalized setting will be stated as Assumption 11 in Appendix E.1.
We now introduce the notation for the target set Q. In the main text, choose Q to be the set of global minima of f but this needs not be the case in general. In the rest of the appendix, Q will union of connected components of crit( f)
Definition 1 (Choice of the components of interest). Denote by QI...., N the connected components of crit( that form the target set.
Denote by Kl,...,KK Kx the remaining connected components of crit( and denote by
(CI... CN.)) (KI, KR. .I...., 2Numn
(B.11)
their union with Nert K + Nuarg.
Since the connected components of crit(f) (f) are pairwise disjoint by definition, their compactness implies that there exists o > 0 such that Us (C;), for = l,..., Nait are pairwise disjoint.
In this framework, the iterates of (SGD), started at x Rd, are defined by the following recursion:
X Rd
(B.12)
Xn+1 = - V f(xx) + qun,
where un u (Xn, (e))
where (20))20 sequence of random variables in RT We will denote by Px the law of the sequence (wn)m20 when the initial point is x and by Ex the expectation with respect Px.
Assumptions 5 and 7 imply the following growth condition, that we assume holds with the same constant for the sake of simplicity. There is M > 0 such that, for all x e Rd, E Q
|V S M(1+ ||x|) and (1(x,c0)) s M(1 + I[xI)).
(B.13)
B.3 Hamiltonian and Lagrangian
Following the notation of [5], introduce the cumulant generating functions of the noise u(x, w)) and of the drift (x) u(x,w), that we denote by H. H to avoid confusion. We also define their convex conjugates, E, L.
Definition 2 (Hamiltonian and Lagrangian). Define, for E Rd, DE Rd.
F((x, n) log Elexp( (1,
(B.14a)
H(x, u) -(V](xx)) + H((x 8)
(B.14b)
E(x, v) -+((x,))(())
(B. (B.14c)
L(x. -(xx)))((o)) C(x,
(B.
C is thus equal to the Lagrangian L.(.,).
We restate [5, Lem. B.1] that provides basic properties of the Hamiltonian and Lagrangian functions. Lemma B.1 (Properties H and L, [5, Lem. B.1]).
1. H is C² and H(x,) :) is convex for any x Rd.
L(x,-) -) is convex for any x E Rd, lower semi-continuous (L.s.c.) on Rd x Rd.
For any x IR, D Rd, H(x, v) < 2M + [|x])]] and dom C(x, -) c B 2M ||xl)). For any x Rd, v E Rd, [(x, u) 2 and _(x, u) = - v= V=
The following lemma provides a lower bound on the Lagrangian and an immediate consequence of the Gaussian tails assumption ((c)).
20

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Lemma B.2 ([5, Lem. D.5)). For any Rd, Rd
| ((x.0)
(B.15)
20 f(x)
B.4 A large deviation principle for SGD
In this section, we present and restate the large deviation principles established in [5]for SGD. Note that their proof is itself an application of the general theory of Freidlin & Wentzell [22]. From the sequences (Xn)a>0 and (Wn) we define another discrete sequence: a subsampled or, accelerated, sequence
x = mm(1/
(B.16)
From the Lagrangian defined in (B.14d), we define, on C((0. 71, R the normalized action functional S0,7 by
St,r(y) Sh' L(y:, vr) dt if absolutely continuous
(B.17)
+00
otherwise
following Freidlin & Wentzell [22, Chap. 3.2), as manner to quantify how "probable" a trajectory is.
For some O, we will first equip (Rd)N N with the distance
dist (5,
max |I Gnll
(B.18)
0s*EN-1
Now, for N 2 0. = (Eo. EI-1) E Rd let us define the normalized discrete action functional
An = Σ plEn- En-1)
(B.19)
where the cost moving from one iteration the next is defined for any x,x Rd from the previous continuous normalized action functional (ef. (B.17)) with horizon
p(xxx') = inf(So, y y C(10, 1J, Yo =x,1 =x²
(B.20)
We now present the large deviation principle on the discrete accelerated sequence (x DoSHEN-I = (Knir=)00s In the following result, the functional 17 'AN is thus the action functional in (Rd)* N of the process (x DSSSNN-- uniformly with respect to the starting point xp in any compact set K. Rd as - 0. Proposition B.1. Fix N O.
For any > 0, the set
(s) (g RdN :50 K. ss}
(B.21)
is compact and An is L.s.c. RaN
For any 6, 0. K. Rd compact, there exists no > 0 such that, for any n (0. for any xo E K. s N,
& r(xo] (s), we have that
Ax) + E
Pso (dist,, (x 6) 2 exp
(B.22a)
Pao distt, (x",I(xx) p(xn) (s)) 6) exp
5-8
(B.22b)
17
21

---

The Global Convergence Time of SGD in Non-Convex Landscapes
B.5 Return to eritical points
In this section, we restate a key result from [5]: the lemma below provides control on the return time a neighborhood of the set of critical points. In particular, it shows that the distribution of this return time is roughly sub-exponential.
Definition (Stopping times for the accelerated process). For any set R we define the hitting and exit times of A:
A inf x A),
(B.23a)
0 7 in 2 0: x $ A)
(B. (B.23b)
Lemma B.3 ([5, Lem. D.21]). Consider crit(f) c c X Rd with U open set and X compact set. Then, there is
some 1/0. C0 a, b > O such that,
atH
Vn no. an E X,
E
e
e
+b
(B.24)
B.6 Attractors
We again build on the work of [5] which took inspiration from the framework of Kifer [39]. We first need to define the gradient flow of f.
Definition 4. Define, for x E Rd, the flow O of f started at x, i.e.,
Ox(x) =
(B.25)
6, = -V
(B.26)
and let F(x) be the value of this flow at time 1, i.c.,
F(x) = O))
(B.27)
We first list some basic properties. Lemma B.4 (Properties the flow [5, Lem. D.1]). O is well-defined and continuous both time and space, and, for any T y C([O,T) T), Rd) such that yo x,
So.(ly) =0 = Y/ 00(xx) for all [0.7].
(B.28)
The following lemma translates this for
Lemma B.5 (Properties F,[5, Lem. D.2]). F is well-defined and continous and, for any x.x e Rd.
p(x,x') = - x' x'(xx..
(B.29)
The next two lemmas are key regularity results on the connected components of the critical set.
Lemma B.6 ([5, Lem. D.8]). For any C c crit(f) connected component of the critical set, there is > 0 such that, for any 0 1<rs $ ro.
W,(C) {xER' p(x.C) <,, p(C.x) <r)
(B.30)
open and contains C.
Lemma B.7 ([5, Lem. D.9I). Let c crit(f) be a connected component of the critical set. Then, for any 6 > 0, there is some 2 such that, for any x, E C, there is E E D,NN) such that Eo = x, EN- = z, AN(E) E and maKogneN d(E,. C) 8.
B.7
Convergence and stability
Lemma B.8 ([5, Lem. D.28]). For any E X,, there exists E {1...., Nerih such that
lim d(O, (x), C.) = 0. 1-2000
(B.31)
22

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Definition 5. A connected component of the critical points C crit( is said to be asymptotically stable if there exists U/ neighborhood of C such that, for any U, (x) converges C, i.e.,
lim d(OO ()), =0
(B.32)
The notions of minimizing component and asymptotic stability equivalent in context. Definition 6. C connected component of f) is minimizing if there exists U neighborhood of C such that
arg min f(x) =C
(B.33)
xell
Note that since crit(f) is closed, C is closed well connected component of a closed Lemma B.9 ([5, Lem. D.29]). For any C c crit(f) connected component of the set of critical points, minimizing if and only if is asymptotically stable.
23

---

The Global Convergence Time of SGD in Non-Convex Landscapes
C
Transitions
In this section, we study the transitions of the accelerated sequence of SGD iterates between the different sets of critical points. As in [5], we build on the work Kifer [39] and Freidlin & Wentzell [22]. More precisely, Appendices C.1-C.5 consists in refining the framework of [5] to be able obtain precise time estimates on the transitions between the different sets of critical points. Such results provided in Appendix C.6.
C.1 Setup
We adapt our context Kifer [39, Lem. 5.4] and simplify using ideas from Freidlin & Wentzell [22, Chap, 6]. Definition 7 (Freidlin & Wentzell [22, Chap. 6.$2]). For i {I. (I.....K), K).
(I....,Neride Nerit. 6 0,
B inf (N 22 (M), Eo E G, EN-1 E Cj. En Uc, for all I....,,.-
B inf AN(E) N2 E D, to e Us(C), EN-1 (o(C,), En UG for all I...., -2
(C.1)
tti.j
While B is the usual definition from Freidlin & Wentzell [22, Chap. 6,82], BY, is variant that will prove helpful. Let us now first list a few immediate properties.
Lemma C.1. For e (I..... K}. jE (1....,No, Neru), B is non-decreasing and, for any > 0, B s Br.j-
Note that the fact that B is non-decreasing in 5 implies that the limit lim Bi, exists.
We now exploit the regularity around the K,, to obtain an alternate expression for Bij as the limit of Bi, as - 0.
Lemma C.2. For i e {l, (l...., K). j E N.....,Nrr). the following equality holds:
Bij lim B 8-0
(C.2)
Proof. By Lemma C.I, we have
B S B
(C.3)
and therefore
lim B s Bij 8-0
(C.4)
remains show the reverse inequality.
Take 0. Apply Lemma B.6 to C;: at the potential cost of reducing e, we get that We (C, is open neighborhood of C,
Take 8 > 0 small enough so that (C,) c 2c does not intersect with any other C₁, I #
Now, take any N 2 1 and & (N) such that &o E (C,),, EN-I E Us(C,)) En & Ussi, C, for all n I....,N- 2.
By the choice of ö, Eo cannot be Uli,, Cj and Eo is inside (C,),) so that there exists x E C; such that p(x, Eu) E. Similarly, there exists x' C2 such that p(ÊN-1,x') Eo,Eo.E E.-I,,,,)))))) that satisfies 5o Ci IN Cj and in Utii,j Ci for all I,...,N 2. Furthermore, ANI2(() (E) + 28 and thus Bi.j (E 28. Passing to the infimum over such paths & yields
g. Now consider the path { D, + 2) defined {
Bi, S B 28.
(C.5)
which concludes the proof.
C.2 Induced chain
We now define an important object: the law of the (accelerated) iterated at the first time they reach some set V (typically a neighborhood of the critical set). Due to our interest in the finite-time dynamics, we slightly deviate from the classical
definitions of Douc et al. [18, Chap. 3.4] and Kifer [39, Prop. 5.3] to follow more closely the one of Freidlin & Wentzell [22, Chap. 6.$2].
24

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Definition 8. Consider V,, i l..... Nei disjoint neighborhoods of C₁ and denote by V U Vi their union. We define recursively the sequences of stopping times (n2))20 and (z) nz0 by
For ı! = 0,
0
(C.6)
0 0.
(C.7)
For n 2 0, if x
is in Vi, then
f/
inf(k
2 In xx # Vi,)
if if
Vin for some in s.t. Ci E Kx),
o- n+1 T
TM
(C.8)
otherwise.
in 2 o² n+1 : 1x E V}
(C.9)
n+1
We denote by Zn = x probability i... the law of z started zo x.
O, l.... the induced Markov chain and by Qy(x, -) the corresponding Markov transition
A few remarks are in order (zn)nzo:
E V for all n 2 1.
If the chain reaches a neighborhood of Qi....,QN... stays there forever.
C.3 Estimates of the transition probabilities
Lemma C.3. For any & > 0, O, for any small enough neighhorhoods Vi of C2, i 1,...,,,, there some no > such that for all (l..... K), j (l..... N..ith x Vi 0 17 1j0.
B.
exp
if B < t00,
(y( S
(C.10)
exp
otherwise.
Proof. Following the alternative definition of the Bi,y's Lemma C.2, choose 5 > 0 small enough so that both Us (Ci),
I..... Nerit are pairwise disjoints and the following holds for all i, E Nait):
Br.j
if B +00, otherwise
B
(C.11)
A
Require then that V; be contained Ug (C2) for all I...., Note that the V are pairwise disjoint by construction.
Given neighborhoods V;, i 1, 1,..., Nan. by compactness of crit(f), there exists 8' 0 such that 8' 2. U28 (C₂) is contained in V, for all i = I,... Nemt
Fix j E fl....,,Ne Nerth and consider & D, such that εo e (V) c Us(C),, EN-1 E (V)( c Uc(C,) and En e Ug (Rd Unii, Vi) for all = 1,...,N-- N-2. By the choice of 8', En cannot be Unii, Us (C, for any = 1...., N-2.
By construction of & we thus have that
AN(E) 2 B
Bi.j A
if Bi, < +00, otherwise.
(C.12)
where the last inequality follows from (C.11).
Fix x E V. Let us now bound the probability
(x Vj) = P,
21 E VV
(C.13)
25

---

The Global Convergence Time of SGD in Non-Convex Landscapes
and start with the case where B +00, We have, for any N O,
Px x Ev) s Px P., E V4, T2 N + +Px +Px 2 N).
(C.14)
We first bound the second probability using Lemma B.3 applied U V;- Take N such that ao(a N) nob s - Bi. Then, by Markov's inequality and Lemma B.3, it holds that for all 17 S 170
p. P.(TT' 2 N) s Px
0
"
an
exp
2 exp
17
anla
N)
S exp
b
-Bi.J
$ exp
(C.15)
We now bound the term P, x 13
V,. z <N|
for this choice of N.
For this, we show that x" E V with 7 implies that
distw (x", (x",rt
p(x) (Bi, 20)) > 8' 2
(C.16)
Indeed, on the eventx", Vi with z N. there is some N' s N such that Tú 1. If disty (x", (2", (Br, 28) o/2 T3 did not hold, this would mean that there exists & (R") such that distyr (x",g) < 50 and, AN-(f) s B - 2E. In particular, E would also satisfy E E (V,)),) & E (Rd V) for all n 1....,'' N' 2 and, as consequence, É E D, (N'). This would be thus in direct contradiction of (C.12).
Therefore, we have that
T < < S Px distw distn(x",TT (x",Th" (Bi. - 26)) > )
Ps 2 2
VV,
Bi.j 38
$ exp
(C.17)
11
by Proposition B.1.
Combining this bound with (C.15) yields
Bi.j - 36
-Bi.j eexp
Px E V,) exp
(C.18)
17
17
which concludes the proof when Bi, < +00.
Let us now examine the case where Bi, = +00. Again, we have, for any N 2 O.
P 2 E EV
Px V/, T < N/ + P Px 2
(C.19)
We first bound the second probability using Lemma B.3 applied to ld - V. Take N such that an(a - N) + nob S -A. Then, by Markov's 's inequality and Lemma B.3, holds that for all 1 s 770
P. (T 2 N) s IP.
on
exp
2 exp
17
17
an(a - NN) b
$ exp
17
26

---

The Global Convergence Time of SGD in Non-Convex Landscapes
-A 7
s exp
(C.20)
We now bound the term P, x2 v, z3 <N for this choice of
13
For this, we show that x" E Vj with 73 implies that
disty (x", (17,
(x) 1 (A (ad-s)) 8'
(C.21)
V with r < N, there is some N' s N such that 7' = N' - If dist (x" [,"I," (A 8) d' did not hold, this would mean that there exists & E (Rd) such that dist < 8', En = and, Av 1 A - 8. In particular, & would also satisfy Ex E (V))), En e Ug (R \ V) for all n = I....,N' 2 and, as a consequence, EE (N'). This would be thus in direct contradiction of (C.12).
Indeed, the event x 23
Therefore, have that
Px disty (x", (.7 (A 8)) > "
Px 2
Vn.
+ <N
2
exp
(C.22)
by Proposition B.I.
Combining this bound with (C.20) yields
A
-A
Px(x E V,) s exp
+ exp
(C.23)
11
11
which concludes the proof.
Lemma C.4. For any & > 0.for any neighborhoods Vi of C, i = I,..., Now small enough, there exists > 0 such that for i KI,...,K,, j (1....,Nemhl, x E Vj, 0 < < 170.
BB, 8 7 Qv(x, V2) 2 exp
(C.24)
17
Note that this result is trivially valid if B, t00.
Proof. For any (i, E (I...., K} x (1...., Nent. there exists Nr.j 2 1, g/v E (N(N,,)) such that e.d e C₁, dbj NN E Cj. J.J En & Ulan Cj for all n = I...., N., 2 and ANi,, (gl.)) s Bi, +
Define jt, min dieh Unvi. C)
Ny. 2) and minnjjr jt.j By construction, it holds that 8 0.
Without loss of generality, at the potential cost of reducing &, we can assume that Lemma B.6 can be applied to every C, i = 1....,K K with - & and denote by W; the corresponding neighborhoods of C,. Require that V; be contained in W; n (8)2((C) for all = I..... K. Now, given such V; neighborhoods of C, i= I,..,,,,,NNi by compactness, there exists 0 < 8' s 6/2 such that 24g. (C,) is contained in Vi for all l...., ..rit.
Apply Lemma B.7 C,, i 1,...,k K with <- min(s, 8' /2) and denote by N; the bound on the length of paths obtained.
We are now ready to prove the result. Fix (i,j) E (1....,k K} x (1...., Nait) and consider x e V,. Since V; c W;, there exists E KG; such that p(x, z) < E.
By Lemma B.7, there exists n < N. E (n) such that to 2. EN-1 = 50.d .Ex (K)))())) for all & I...., 2 and An(F) <.
27

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Considering the concatenation
dij == (x.E..1........ 2n 1... (N.-11)
(C.25)
which is path of length n Ni,+ made x E V, then exactly n points in (K;) then Nr., 2 in I² (V) and dij NN Kj. Moreover, by construction, AN+N,, Bi. + 38. Therefore, if
Ni +1 (x 82/2
(C.26)
with x0 = =, then xx are in Mg V; and, since 8' s 6/2, x" 242 , ......." N+N.,-1
are not in MV))(VV) and therefore
not in V. Moreover, x" An would be in (2 c Vj.
Thus, all the paths x satisfying (C.26) with x correspond exactly one transition the induced chain (zn), from to Vj-
Therefore, using the definition of Qy, we have that
Qv(x. P, (1 8212)
Bi, + 48
exp
(C.27)
17
by Proposition B.I.
C.4 Accelerated induced chain
We will take the following convention, for any (1...., N. 0:
B B = Bj,; 0.
(C.28)
Recall that Qy is the transition probabilities of the induced chain (zn)n20 defined in Definition 8. In other words Qy V/) is the probability that the sequence of (B.16) starting from x at time O enters Vj before any other V for # j. Moreover, K still denotes the number of connected components of the critical set of f that are not part of the global minimum, see Definition 1 in Appendix B.2.
Definition 9, Given the induced chain (2n)m20, we define the accelerated induced chain (z n)ma0 as follows:
Znk
(C.29)
We denote by QK,, the transition probabilities of the accelerated induced chain which corresponds the K th power of Qy: it 12 for any E V.. i (1, ..r.i.) and any measurable set A c Rd
(x, A) / s 11xx E A} (v dzi) Qy(z), (t..:a/ddd.......xx..ddd... Qu(2x-1,dzk).
(C.30)
We now define transition costs for the accelerated induced chain, which correspond the ones introduced in the main text (19)
in Section 4. Definition 10 (Inspired by Freidlin & Wentzell [22, Chap. 6.$21). For E (I...., K). j .ih...,,erally 8 0.
B1, inf AN(E): N 1,g D,(N). &o C, EN-1 Cj. En U
C for all I..... -
(C.31)
Lemma C.5. For any (i.j) E (I.....
(1....,) Nevat.
Bi. = min
Binia in i, in-1 = j.4 (I...., for
2,
(C.32)
min
Biai :0 = (I..... ()... KI.....III.
K-1].
(C.33)
12This equation is sometimes referred to as the Chapman- Chapman-Kolmogonn Kolmogorov equation.
28

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. We focus proving the first equality for Bi.f; the proof for Br,, follows similarly. Let denote by RHS(i,)) the right-hand side:
2=2
J) == min
Bliial 10 =1, in j. i (l...... K} for -or/=1 lo... 2. 21
(C.34)
We will prove that B,,, = R..(...)..
(2): Let us show that Bi. 2 J). Fix & > O. There a path E (N) with &o e Ci EN-1 E Cj that avoids Usi.,,lak Ct so that, by definition of Bi, (Definition 10),
Bi, 2 AN (E) -
(C.35)
Let S n < < ... < nn < be the times when É belongs to some C with s K. Define io = i, iN j and for S < N", let be such that Em, Ci. Then, by definition of Bi (Definition 7),
(5
B Bi
(C.36)
k=0
Combining (C.35) and (C.36) and taking yields
N' 11
B 2
Bic.kel
(C.37)
k=0
2 R) E
(C.38)
since this sequence (ix) (o satisfies io i, iN' j and ix E (l.....K) for s k < N
(<): Let us show that Bi,, s RHS(i,)) j). Take > 0 and let (ix) be sequence achieving the minimum in RHS(i,) j) up to E, i.e.
Big S RHS((.) +
(C.39)
Take 8 > small enough such that (C),
Neit are pairwise disjoint.
For each O u k < N', by definition of Bic. (Definition 7), there exists oū (0, and path gk <D,(NN) such that: (i)
Ek Ci., (ii) et - Ci (ii) gh & Utzic C for all = II.....N 2, and (iv) AN, (E+) Bi + E/NN
By Lemma B.7, for each s & < - 1, there exists ş+ E (Nx) such that: (i) 50 ge -1-1 (ii) EK NN-1 = ek+1 (iii)
5h E (o and therefore Ek & Ultinn Ci for all n 1,...,,, Ñ₂ 2, and (iv) AN, (E+) S E/N'
Concatenating the paths 20. NN yields path / that: (i) starts in C, (ii) ends in Cj. (iii) avoids Utii,j, Ct. and (iv) has total cost at most Σ B + 36. Therefore, by definition of B, (Definition 10),
N' BI.
Big 38
k=0
RHS(i, j) + 4
(C.40)
The second equality in each case follows from the fact that optimal paths between different components can be chosen without cycles (since all costs are non-negative). and therefore their length can be bounded by the number of components K.
Lemma C.6 (Upper bound on accelerated induced chain transition probability). For any & > for any small enough neighborhoods Vi of C, I,..., Nerit there some 1j0 > O such that for all i (1...., K))....,,,. j (l..... Noith V,
<1 1) 170-
Bid exp
B < 400,
QK (xxx V))
11
(C.41)
exp
otherwise.
29

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. Fix (l..... KJ, je Neith By Lemma C.5, we have that
K-1 Σ
B min
Bisinn 10 =i ix i. (I..... K} for lo..= -I....,,-11
(C.42)
First, let us consider the case where Br < +00, Take & > 0 and let (it)= be sequence achieving the minimum in (C.42) up to &, i.e.
K
Bu.i B t
(C.43)
By definition of the accelerated induced chain (Definition 9), have that for any x e V/,
E E ""S QT dxa+1) Qv(x.. Vj),
e vx,
(C.44)
1 (1
k=D
where we define Xo X. Therefore, combining (C.44) with Lemma C.3 and (C.43), we obtain that for any x Vi.
K-1
B Bix
(xv Vi) <
Σ
exp
n
i Boonk--E
[l...
R=0
Bi.j 28
$ K-1 exp
(C.45)
11
For the case where Bi, +oo, by the same reasoning but using the alternative bound from Lemma C.3, we get
A 1
Q* vx. k- expl
(C.46)
Taking small enough so that K- z exp(s/n) for all r) no. the result follows from (C.45) and (C.46).
Lemma C.7 (Lower bound on accelerated induced chain transition probability). For any 0, for any small enough neighborhoods Vi of C, i = I...., Nerit. there is some > 0 such that for all i E (l...., K}, j E (I...., Noi) E V,
0 < 170-
Bi.j
(x Vj) 2 exp
(C.47)
17
The proof of Lemma C.7 is very similar to the proof of Lemma C.6 and is therefore omitted.
We end this section by restating result from [5]that provides sufficient conditions for Bi, to be finite for any (f,
(1...., K) x .......ert)..
Lemma C.8 ([5, Lem. D.12]). Consider x,x' Rd and assume that there exists T E N, y e C (IO,T), Rd) such that C, for all n I...., T and, for every [O,T], Vf(y)) is in the interior of the closed convex hull of the support of u( w), i.e.,
Yo x, yr xx' Yn & Ula.j.
Vf(y)) E int conv supp w).
(C.48)
Then, B(x,x') < +00.
C.5 Initial transition
Definition 11 (Inspired by Freidlin Wentzell [22, Chap. 6.821). For j E (I...., Nait. 8 0, x Rd.
BI, = inf AN N 1, D.(N), & Ex, EN- Cj. &n & U for all n
N - I....,N
(C.49)
[ti.j
B2,- = inf AN(E): N 12 (N))) Eo= = ÊN- Ua(C,), &n Uc for all 1,..., N-
(C.50)
toi.j
30

---

The Global Convergence Time of SGD in Non-Convex Landscapes
The proof of the following lemmas very similar the ones of Lemmas C.2-C.4 and therefore omitted. Lemma C.9. For any j (I...., Northh ó O, Rd
xx lim B 6-0
(C.51)
Lemma C.10. For any 0, x Rd, for any neighborhoods Vi Cf i l,..., Nect small enough, there exists no > 0 such that for all ......,Noil ) 0 < < 7/0.
B..j E 17
()x 2 exp
(C.52)
1
Lemma C.11. For any 0, A> 0, E Rd, for any small enough neighborhoods V: of C. i .,...,,......................... Now there is some 770 > O such that for all j
0 < < 170.
Bed
exp
if Bx. t00,
Qy(x.
(C.53)
exp
otherwise..
Following the same methodology for transitions between critical components, establish similar results for transitions starting from arbitrary initial state.
Definition 12 (Inspired by Freidlin & Wentzell [22, Chap. 6,$2)). For e R (I...., Neath 6 0,
Bx. = inf AN(E) N N 1.g D,(N), &n =x, EN- Cj. En &
U C for all n I Isjls*
(C.54)
This definition mirrors the one of Definition 10, adapting it to account for an arbitrary initial state rather than starting from critical component. We then establish the following decomposition result, analogous Lemma C.5.
Lemma C.12. For any Rd. j (l....,Noot)
Bx,j min
Bx.i +
Bisin 1n-1 (1...,,.,
22
(C.55)
EMP
min
Bx,
+
Busin :1x j. 4 (I...., KJ forr l..ol=,,.,,,.---....... KI.....II
(C.56)
The proof follows the same arguments as Lemma C.5, replacing the initial component with the given initial state.
These structural results allow us establish bounds on the transition probabilities from an arbitrary initial state, paralleling those of Lemmas C.6 and C.7.
Lemma C.13 (Upper bound accelerated induced chain initial transition probability). For any E Rd, for any O. A > O, for any small enough neighborhoods V; C, i l,..., Neri there is some > O such that for all j E (1...., Nanth
0 < 11 < 170-
exp
B
Bf < +00
(C.57)
exp
otherwise.
Lemma C.14 (Lower bound accelerated induced chain initial transition probability). For any Rd, for any for any small enough neighborhoods V; of C, i l...., Nerit there is some 170 0 such that for all j (1...., Neri).
0 < 17 < 170-
B 8
Q (x 2 exp
(C.58)
1
The proofs of these last two lemmas follow very closely those of Lemmas C.6 and C.7. with the main modification being the treatment of the initial state instead of an initial component. The key arguments involving the Chapman-Kolmogon Kolmogorov equation and the handling of the intermediate transitions remain essentially unchanged.
31

---

The Global Convergence Time of SGD in Non-Convex Landscapes
C.6
Transition time
Let us begin with preliminary escape result.
Lemma C.15. Given C a connected components of Keeas for any > O, for ny > small enough and a small enough neighborhood of C, holds that, for any V,
E
Ex
[o0] exp
(C.59)
Proof. Fix & > 1. By Lemma B.6, (C( is an open neighborhood of C. Since C' is closed, Wc(C) \ C not empty and open. Therefore, there exists X3 E (c(C) \ C and 5 > 0 such that ( 6) c Wc(C) \ C. By construction, there exists X2 E C such that x3), < &.
Let us now apply Lemma B.7 to obtain that there exists 2 such that, for any x1 C, there exists n & N. (N(N) such that Eo = x1, EN- X2, (E) E.
Require then that V be contained in (c(C) Bxx3, 6/2) which is open neighborhood of C.
Take X E V. Since V is in particular contained in W,(C), there exists E C such that (xx,x1) < 8. By our application of Lemma B.7 above, there exists n s N. E (n) such that Eu = x1, En-1 = X2, An(E) < 8. Now consider the path [ E D, (n + 2) defined by
E1. .n..,x))).....1
(C.60)
which satisfies
Ant p(x,x)) (n( + x(x2,x)) 38.
(C.61)
If a trajectory of SGD x with x²0- satisfies distm+2(x", < 6/2, then x x44 is inside [8xx,, 6/2) and therefore not in V.
Hence, we have, for > 0 small enough,
Px < N+3) 2 P.(or) < +)
2 Ps (x) 5/2)
A4+ +
exp
"
48
exp
(C.62)
where we invoked Proposition B.1 and used (C.61).
For any x V, for n 2 2. the (weak) Markov property yields that
Ps Px nNNN +2) Ex 1(0 >
NN+2 N.a
110 2 ....... .,,
.)...EE, m
[160 N N+2] [+2]]... 2
$ 22 - exp
48 "
(C.63)
with (C.62).
We can now finally estimate the expectation of o/ for V,
Ex [
Σ n=1
P, (a y n)
(o > n(N + 1) +k)
k=0
$ (N+ Σ P. > n(N+1) 1))
H=0
32

---

The Global Convergence Time of SGD in Non-Convex Landscapes
48
$ (N +
Σ
exp
17
48 (N+ + 2) exp
-
(C.64)
17
where we used (C.63).
Finally, taking 0 small enough so that N 1 expl ( yields that
58 17
Ex - exp
(C.65)
which concludes the proof.
Lemma C.16. For any Xo Rd compact, for any & > O, for any small enough neighhorhoods V of i l...., Neit there is some no > 0 such for all < < 170. for any x E No \ Non Vi
1 E se
(C.66)
Proof. Let begin with the LHS inequality. There are two cases: either belongs to U V; or not. Ifx belongs to UK Vi.
f
then by definition of " 2 and therefore r" 2 1. If x does not belong to U Vi, then of = 0 but necessarily Tj 2 1.
Hence, all cases, ! 2 so that the LHS inequality holds.
We now turn to the RHS inequality. As before, we will separate the proof into two cases: either belongs to U V or not.
If x belongs to some Vi for some E (1...., K} then, by Lemma C.15, we have that
= Eo se
(C.67)
In particular, o, is finite almost surely. Therefore, the strong Markov property implies that
E,IT"] =E,0o] E, "
IT31l-
(C.68)
Applying Lemma B.3 with U < Nua Vi and Rd - No. and using Jensen's 's inequality, obtain that
bmo c.
E [T
(C.69)
ao
Plugging this bound into (C.68) and using (C.67) yields
ExIT"I s +c.
(C.70)
which concludes the proof of this case.
Finally, if x does not belong to UK V, then one only needs to apply Lemma B.3 as above to obtain the result.
Corollary C.1. For any No C Rd compact, for any N 1, for any & 0, for any small enough neighborhoods V; of i= I,.... Noi. there is some no such that for all 0 π 77. for any x Xo Neu
(=K+1 Vi
1 E 2 < :
(C.71)
Proof. The lower bound follows directly from the definition of N since T 2 for & 2 I by construction.
For the upper bound, first note that we can write T" as a telescoping sum:
N-1
(C.72)
k=0
33

---

The Global Convergence Time of SGD in Non-Convex Landscapes
with the convention that o 0.. Therefore,
N-1 E
E R+1 - -x
(C.73)
By the strong Markov property applied at time o for each term, we have
ExIT R+1 T
Ex
E [T]]]]
$ se
(C.74)
where the inequality follows from Lemma C.16 since x², belongs to U V; by definition of r for all k 2 (and for k 0, apply Lemma C.16 directly the initial point Summing over k from 0 to N yields
Ex |x - Ne
$
(C.75)
for y small enough.
34

---

The Global Convergence Time of SGD in Non-Convex Landscapes
D Finite-Te Time Analysis
D.1 Markov Chains finite state spaces
In this subsection, we introduce the necessary notation and then restate key lemma from Freidlin & Wentzell [22, Chap. 6.$3].
Consider finite set V and Q & V. Denote by r == card V Q.
Given p (V) x + [0. I], we define the probability of a with edges (V) 2 a
x(g.p) == 1 p(i j).
(D.1)
i-jey
graph consisting of arrows j- with j e
V/ Q e j+ # k is called a Q-graph on if
(i) Every vertex in V has exactly one outgoing arrow.
There are no cycles, or, equivalently, from every vertex in V \ Q there is a directed path to a vertex in Q.
The set of Q-graphs is denoted by G(Q).
We denote by G(i b/r Q) the set of graphs with exactly card(V) V Q) edges from V Q to V, no cycles and no path from i to Q. Note that, cquivalently, this set is made of all Q-graphs from which a single edge from the path from to Q has been removed.
Lemma D.1 (Freidlin & Wentzell [22, Chap. 6,$3,Lem. 3.4)). Consider a Markov Chain on state space Uiev X; with X E V disjoint and non-emply, with transition probabilities that satisfy: for E V Q j with # j.
e a=' Pij P(x,X) apij
(D.2)
for some a 2 1, Pij > O. Fori E VA Q, the expected time to reach Q when starting at denoted by m (x) satisfies: for all X E X
3x4 EgcG(H-2) x(g.7) S mx(x) s 3x4r E Ege (9.P))
(D.3)
Eyeg (g.
Σgeg 9.
D.2 Hitting time of the accelerated process
We will instantiate the lemmas of the previous section Appendix D.I with V= (I...., Neit, Q= (K+ I,...,Neail Nea) and X; Vi for i (I,....Nenii We have r Neri K. Note that the notation @ is line with the notation the main text where we denote by both the set of indices {K 1....,Nenii and the of union of the corresponding components UjEe C = =
Now 2 = arg min f.
Define by TO Te v, the hitting time of ee Vi for the accelerated SGD process. We also consider the induced chain (In)n0 on Non Vi defined Definition as well as its accelerated version defined Definition 9 and denote by 7h the hitting time of USeQ V, for this accelerated induced chain. These two hitting times are related by the following lemma, which is key consequence of Lemma C.16.
Lemma D.2. For any for any small enough neighborhoods V, of i I...., ..ri there is some no such for all 7 < n7. for any UNo V,
Ex ExITK| Ex(T"! s Ex 1 x xen
(D.4)
Proof. First, if x belongs to UNN Vi = Ujeo Vj, then = and pi 0 so the statement holds trivially.
0
We now consider the case where x belongs UK V; Since Ci.... Cx are compact, we can require that U 1/ be relatively compact. We can apply Corollary C.1 to the accelerated process to obtain that with X, - c V, for any
small enough neighborhoods V; of C,, 1,..., Nani there some > 0 such for all 0 < < 7p. for any x U New Vi. we have,
E=
S E, ExIT sed
(D.5)
35

---

The Global Convergence Time of SGD in Non-Convex Landscapes
We now have that, by Definition 8,
1 = E
Σ
1 Tn
Uvi
( (n+1)
Tax)
jEQ
00
=
Σ x
1xx
Uvi
((+1)K Tix)
JEQ
00
E
1
U
E [<]]
(D.6)
2
jEQ
where we used the strong Markov property in the last equality, since r is always finite almost surely by (D.5).
Combining (D.6) with (D.5), we obtain the bound:
Ex |T Σ
1xx" & E
Uv
1 s >
Ex
1
Uvi JEQ
Xe
=
xe
(D.7)
==0
JEQ
n=0
which yields the result.
Assumption 9. For any E (1...., K) j E (1...., Nent.
B +00.
(D.8)
From now we will assume that Assumption 9 holds.
Definition 13. Fori V Q, define the following quantities:
E(i / Q) == min
Σ k-llg
BR.1 : ge g(
(D.9)
E(Q) == min
Σ
Be, g E 0(
(D.10)
k k-llgg
( = E(Q) - E(i Q)
(D.11)
Note that Assumption 9 ensures that all these quantities are finite.
Lemma D.3. For any V 2. for any & 0, for V1 Vi.... VN.a neighborhoods of CI..., CNus small enough, there no O such that for all 0 n7 no. for any E Vi
RIQ10= 4
EiQinee
S Ex
S
(D.12)
Proof. Fix i V Q. We will apply Lemma D.1 to the accelerated induced chain.
Let us first verify the assumptions of these lemmas. By Lemmas C.6 and C.7, for any & > 0, for small enough neighborhoods
Vi of C, Nertt there exists 770 > such that for all E (l...., K}. j E (1...., Nent.. E V,, 0 < r7 < 170:
Bi.j
vx Vj) s exp
(D.13)
11
Bi.j
(xx (xv Vj) 2 exp
(D.14)
17 17
Note that Assumption ensures that both Bı, and Br,, are finite.
We define, for any V j. E V with i j:
Bi.j Pij == exp
Bi.i
and, Pij = exp
(D.15)
17
17
36

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Let us verify the conditions of Lemma D.I with e By (D.13) and (D.14), for all e V Q. j e V with i * j.x Vj:
apij vxx Vi) s apij
(D.16)
Now we can apply Lemma D.1 to obtain that for E V;:
3x4 ElQin
S Ex a 3x4' EieIa
(D.17)
Recalling that a = e the bounds (D.17) become:
9
S Ex s
(D.18)
which concludes the proof since & > 0 was arbitrary.
Definition 14. Let us now define, for x E Rd,
x(QIx) (E(Q) Bxx)
(D.19)
iEVI
with the convention that these quantities are zero if Usee Vi or equal to the quantities defined in Definition 13 if
X E U i=] Vi
Note that these quantities defined in Definition 14 are non-negative and finite by Assumption 9.
Lemma D.4. For any Xo Rd, for any O, for Vi...., VNea neighborhoods of CI....,.rr CNow small enough, there is 170 O such that for all 0 < 170.
-(
E(Qlxg)
se
(D.20)
Proof. If xo U Vi, then Lemma D.3 applies and yiclds the result. if xo U V, then the result holds trivially. Let us now consider the general case where x Rd Nen V; and let us first prove the upper bound, the lower bound follows similarly.
By Lemma D.3 and Lemma C.13: for small enough neighborhoods V of C,, i I...., Nerit there exists 770 such that for all 0 17 17.. (1,..., K), x' Vi, both
E(Q +
B exp
(D.21)
1
and,
B
@ (x0. Vi) exp
(D.22)
n
hold.
Using the strong Markov property at time N (which is finite almost surely by Corollary C.I), we have:
Ner
mi|
Exo
Exo
(1+
E
[
1
" xh
1=1
Nut
Xp
y
1
x2
+
Σ
0x
1 " e vi
i=]
k=
E(Q1)
B Bxo,i + 28
< 1+
(D.23)
17
37

---

The Global Convergence Time of SGD in Non-Convex Landscapes
where we used (D.21) and (D.22) in the last inequality. Bounding the sum follows
K
i)
Bx + 26
0 maxie (I..... K) (E(Q)i) xxo, 2x)
1
Σ
exp
$ (K + 1) exp
i=1
E( xo) 2e
(K + 1) exp
(D.24)
"
yields the upper bound.
The lower bound follows similarly using Lemma C.14 and the lower bound from Lemma D.3.
Theorem D.1. For any Xo E R for any 0, for Vi...., VN.. neighborhoods of Ci...., CNow small enough, there is 7Jn O such that for all 0 < f/o
F(2) my)=
k(21s))+
Exo
4 T
Se
(D.25)
Proof. The result follows directly by combining Lemmas D.2 and D.4.
Specifically, by Lemma D.4, for any 0, for small enough neighborhoods Vi of C₁ == I..... there exists > 0 such that for all 0 < < ijo:
e(@lxmle
(D.26)
Then by Lemma D.2, potentially reducing n7.. have:
Exp s ExO S Exo ( x e
(D.27)
Combining these inequalities and using the fact that & > was arbitrary concludes the proof.
The following lemma, though looking at first weaker than Theorem D.I, will be useful later due to its uniformity in the initial condition in neighborhoods the components.
Lemma D.5. Under Assumption 9, for any i E V for any 0. for Vi, VN... neighborhoods Cl, CN... small
enough, there is no 0 such that for all 0 < 170. for any x Vi
EIQlD=e 4
EIQIN
S Ex
7 2
Se
(D.28)
Proof. The result follows directly by combining Lemmas D.2 and D.3.
Specifically, by Lemma D.3, for any 0, for small enough neighborhoods V; of C., I,..., Nurts there exists 170 such that for all 0 17 17o, for any V/:
KI 10
KCO i4
E
(D.29)
Then by Lemma D.2, potentially reducing no. we have:
E s EX(T") E xe
(D.30)
Combining these inequalities and using the fact that & > was arbitrary concludes the proof.
Another technical lemma that will be useful later is the following.
Lemma D.6. For any xg Rd, for any 8 O, for Vi...., VNu neighborhoods of CI....,CN, small enough, there 770 O such that for all O n7.
-(0
(D.31)
Proof. This result follows directly from Lemma D.4 and the fact that Fo S 7K
38

---

The Global Convergence Time of SGD in Non-Convex Landscapes
D.3 Hitting time of SGD
Leveraging the bounds on the hitting time of the accelerated process, can now derive bounds on the hitting time of SGD, Denote by the hitting time of V -ee Vj for the SGD sequence:
t == = inf n 20:00 E UV
(D.32)
SEQ
It corresponds to the hitting time of SGD defined in the main text (10) in the simpler case where each Vj is of the form V, Uc](C) for j E Q. We now state our first main results on the actual SGD sequence (B.12). The theorem below is a corollary of Theorem D.1 which concerned the subsampled process (B.16).
Theorem D.2. For any E RR for any O, for VI..... VN.W neighborhoods of CI.... CI....,CN.... CNen small enough, there is 770 > O such that for all 0 < < 170.
Exp [r] S E(Q
(D.33)
Proof. This result follows from Theorem D.I and the fact that, by construction,
7 '7.
(D.34)
with 1 s t for small enough
Corollary D.1. For any E R for any A 0, for Vi..... VN neighborhoods of C,, CNon small enough, there is 770 > O such that for all 0 < < 170.
E(Q + +4
Px
exp
S
(D.35)
"
Proof. By Markov's inequality and Theorem D.2, for any xo E Rd for VI...., Vn.. neighborhoods of CI...., Cr.. small
enough, there exists n70 such that for all 0 < 170:
E(Q xo) A
E
Px T2 exp
(D.36)
1
exp
E(Q xx)+A
E(Q xx)+A/2
exp
exp(-A/2n).
(D.37)
exp
"
Let us now focus on the lower-bound which requires more care. We will require the following additional assumption: Assumption 10. Assume that there exist μ 0, o2 +00, R > 0, such that,
1. clli 22), j= I,.... Nung are pairwise disjoint.
2. for all j I,...,N.a Nurg, E clldR( u(x, w) is a - -sub-Gausiian
Vp Rd, log E (p.u(x.0)))
(D.38)
Mung. 3. for all j = I......ug.. E
(Q)), there exists x' E proje, (x) a projection of on 2, such that:
(Vf(x),x-x)) 4 |x - x
(D.39)
2
39

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Note that, Assumption 2 and compactness of crit(f), such a F always exists since take
Nor
Jhe = sup ox(l())) :x U clUR(
(D.40)
j=l
In particular, if oi is constant, then one can simply take oa = o2. Lemma D.7. Under Assumption 10, for any E Q there exists mo > 0 such that for all 0 < < 176. for any xo E Rd satisfying d(xo. 2,) s 12"
R we have, for SGD started at No:
RR²
Xxm (Vn 2 d(xn 21) S R) 2921 exp
(D.41)
11520 2017
Proof. Let denote by K. == (Qj) Given Xo K, we define the projected SGD sequence
po xo
(D.42)
Pu+1 E projx((r f nu,) where u, = u(Pn:
By Assumption 10, for any n 2 0, there exists Yn E projo (Pn) such that:
4 llpn ynll?
(V Pn ynd 2
(D.43)
Define the martingale sequence (Mn)no0 by:
11 n (uL. Pk yk)
M, == E (1-))))
(D.44)
We recursively compute the moment generating function of M,; for a 2 0, n 2 0, by the tower property conditional expectation and Assumption 10:
a T
(1 um) 2 a 0
(1 - un) 20 2²0²
E Ma
s exp
exp
...exp
2
2
x² R²
- (1 - p(7) 2(m+l)
exp
2
(1 117)2
a² R²T2
S exp
(D.45)
2μr
provided that 17 is small enough so that μn 1. Note that we used that the iterates of (D.42) are at distance at most R from 2 by construction.
Since (e*M)),.. is convex function of the martingale sequence (Mn)n20- it is a sub sub- martingalt We can apply Doob's maximal inequality the non-negative sub-martingale (Mn)2o to obtain that for any 0,
P sup Mn 2 A W
< P
sup
aMa 2 aad
InSN-1
a R²R²=²
$ exp
a
(D.46)
2nm
where used (D.45) in the last inequality. Optimizing the right-hand side of (D.46) with respect to a and setting a we obtain:
R
2
P sup
Mn 2 A
exp
(D.47)
inN--1
2R
40

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Taking A A/1 and N +oo, obtain that, by monotone continuity of probability measures, for any A 0:
sup, M, 2 4 & exp
MA
sup nz0
(D.48)
R
Denote by G sup xuerex,.eall-V//6 + u(x, the bound on the gradient and on the noise K,, which is finite by Assumptions 5 and 7.
Let us now derive recursive inequality for the distance to Qy. For any iterate n 2 0, by non-expansiveness of the projection, we have:
d' (pr+1. 21) S Ilppnl yn
s llpn- - -nV + njtn yo 21?
|l yull2 + V/ (Pn)) 4n,'l
- (v Pn yn) + 217 Pn yn)
z (1 pr)ll ynll 2 of26 G² 207(uns pn 9nd
(D.49)
where we used (D.43) in the last inequality. Iterating this inequality and using that d(pn. 22) = |lpn - ynll. we obtain:
( 2,) (1 " d (xo. 2, + G2 (11 (1-m))
+ 2n
Σ
um) --1-111 11 Pi yi)
(uii
1=0
=(1 - pr) d² (xp. 23) + 122 G2 (1- un)
+ 22
lm
s (1 um) d (xo. 21) + 2n6
2n
(D.50)
Using that d(xo, 2,) fr by assumption, requiring that 7 > be small enough so that (D.48), we obtain that for any 2 0, with probability at least expl
2n0
R² in & and taking
#
RR²
1152
R²
d ( 22)
(D.51)
In addition, take 17 > small enough so that G/ S R. this implies that if e Rd so that d(x, 22) then Txx(() + na(x, w)) K. Combining this remark with (D.51), can show recursively that the sequences (xn)m20 and yielding the desired result.
2.
2
(Pn)220 coincide with probability at least - exp 1152
RR²
Define by To the hitting time of Ujeq V by the induced chain (In)az (see Definition 8).
Lemma D.8. Define
Bus max min Bi,
(D.52)
For any xn E Rd. for Vi...., VN.. neighborhoods Cf ...... CN.. small enough, there 170 > O such that for all < n < for any 2 0,
7jo
PA > s 11-e" Bu R
(D.53)
Note that Assumption ensures that B.g is finite.

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. Fix some xo Rd. By definition of B.,, for any vertex V 2, there exists j + such that:
B S Bo 1.
(D.54)
Fix - 1. By Lemma C.4, for small enough neighborhoods V; of C₁ i= .,..., Nerit there exists no > 0 such that for all i ieD V\ e. 0 < njo:
Qy x, Uv/ SEQ
2 max Qy Vj) jCl
minje Bi.j &
2 exp
17
17
Boo0
2 exp
(D.55)
Therefore, for any by the strong Markov property, have:
Pxp (To n) = Exp
1 n 13 [zn Vnj
jeQ
Exo
1(T0
1tzn & 13 Z
jel
expl
P1o (Te n- 1),
(D.56)
where we used the (D.55) in the last inequality. Iterating (D.56), we obtain the desired result.
Theorem D.3. Fix Xg E Rd. Under Assumption 10 and assuming that,
μR² > Ba xx)).x))
(D.57)
11520
for any & > for Vi...., VN.. neighborhoods Cf....., CNa small enough, there is 170 > such that for all 0 < <
E(S1x0)
Exo [T] 2e
(D.58)
Remark D.I. Note that the condition (D.57) is implied by the stronger condition
RR²
B
(D.59)
11527
In particular, Be does depend f nor the noise distribution the interior of the basins of attraction of Q Q Indeed, by definition, B. is equal to
B. max min Bi,; + +, j
(D.60)
and, for E V/ J. E Q, thanks to Lemma B.6, we have that
Bij= inf Sy(y) e C((.,T)) C((0)))))))))))))))))))))))))))) yo e C,, yr Attr(C,), Yn UC.
(D.61)
kEV
since for any E Attr(C;), the gradient flow started at converges to Cj and has zero action cost (Lemma B.4).
Hence, this condition assumption will be satisfied for functions with sufficiently sharp profile near QI...., QNi.. and a given profile away from
42

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. Let first begin by invoking Lemma D.6: for Vi...., VN... neighborhoods of C₁, ....... CN... small enough, there is 170 0 such that for all 1 rjo.
E(Qlx))
[Tol-
(D.62)
Also require that, for all j Q. V, c I d (x, 2,) 12
with R as in Assumption 10.
If x e Uje vj, then the result is trivial so let us assume that & Uje Vj.
Let us denote by
H (vn 2 0, d(xn+r. 21) S R with X E vi}
(D.63)
the event that, after SGD hits Uke V/x at V,. it stays in V, forever. Note that Theorem D.2 ensures that is finite almost surely. By the strong Markov property, we thus obtain from Lemma D.7 that
RR²
Pxp (H) 2 1 exp exp
(D.64)
11520 20
Let us now start from Exy [o] where To is the hitting time of Ujeo Vj by the induced chain (zn)n20 (see Definition 8), for which we have a lower-bound from Lemma D.6. We write
Exg [o)
E., lio 1H] E., (o [c
(D.65)
We begin with the first term of the RHS of (D.65). With the notations from Definition 8, let us consider k 2 0 such that
T Ln "J < s T "J (which possible since these hitting times are finite almost surely and r > 0). But, on
event H. 2x+1
x 11 = =x must be in Vy. This means that, on H. To k 1. Moreover, T kL,> so that, on H
2-1
Te [
(D.66)
and,
Exo To 1x]
Exn
(D.67)
Let us now focus on the second term of the RHS of (D.65). By Fubini's theorem for non-negative integrands, we can rewrite the expectation as:
+00
Exg To 1 [c] = Exn
1lfe 1) 1 di
+00
Pxo Te 1, 1.HC)ap dr.
(D.68)
Let us now split the integral into two parts. For T O. we have:
Ex, To [cc = S Pro Fo > t, H. dr+ J
+00
Px Pro [e t, i, di
$ L/' P Pn((FF)d di+ ff 400
(T f)di.
(D.69)
By (D.64), the first term of the RHS of (D.69) is upper-bounded as:
S Pxo HC dt S T Texp
UR²
(D.70)
11520 22
By (D.57), take 8 > 0 small enough so that
RR²
B - F(Q xx) 36.
(D.71)
1
43

---

The Global Convergence Time of SGD in Non-Convex Landscapes
and define
HR
E(Q (x)) 28
T == exp
(D.72)
11520 10
1
(D.70) now becomes:
J.
T
Pxn HC dt
R(21 m2)
(D.73)
By Lemma D.8, the second term of the RHS of (D.69) can be upper- bounded as: upper-bounded
+00
Pxo (Te > r)dt s
+00
(1 (1-e-
Bi
"
dt
exple e "
$ JT
dt
Boo T
exp
(D.74)
where we used 1 x S e for any x E Rn the last inequality. Injecting the definition of T (D.72), this bound becomes
B
HR² +
E(21xxp) BBx 26
Po, (Te > r)dt s exp
exp
11
11520r301
10
BB
(
S exp
exp
(D.75)
17
where we used (D.71) in the last inequality. With 17 > 0 small enough, we finally obtain
Px (To 1)dt s
(D.76)
Combining (D.73) and (D.76) in (D.69), we obtain:
E(Qlx))-2e
Exp To [c] s
+ +1,
(D.77)
and, combining (D.67) and (D.77) above in (D.65), we get:
E(Q1xo) 22
Exp [o] s E
+
11
(D.78)
Plugging in (D.62) yields:
-(01%))-
7
F(D
1-2
< E
mg
[
+
1
+ e
(D.79)
which yields the desired result by taking 7) > small enough.
Let us state variant of Theorem D.3 that will be useful later.
Lemma D.9. Fix (1....,Nori) Under Assumption 10 and assuming that,
μR²
1152 > Boo E(Q1i)
(D.80)
for any > for Vi...., VN... neighborhoods of CI....,,Cr CN small enough, there is > 0 such that for all 0 < < 1jo- x E V/:
BIQln-e
E [
(D.81)
The only difference with Theorem D.3 that the result is uniform over the initial state in V; instead of being specific to a given initial point. Its proof is identical to the proof Theorem D.3: it simply uses Lemma D.5 to obtain the necessary variant of Lemma D.6 and then follows the same steps. is therefore omitted.
44

---

The Global Convergence Time of SGD in Non-Convex Landscapes
D.4 Basin-dependent convergence result
Let us recall the potential function from [5]. Definition 15 (Potential, [5, Def. 4)). Define, for E Rd
(x) 20 f(x)
(D.82)
where de: Rd R is a twice continuously differentiable primitive of 1/0
Lemma D.10. For any y e C(10, ()), / [0, we have
(~(r(1)) - -U>(Y(0)) s Sor((y).
(D.83)
Proof. We have that, with &s defined Definition 15, by Young's 's inequality,
Uno(y)) - U (v0) 2 ('' (ts, V (y(s))
ds
o s(ys)
11
Jo ' [V)(()))1
ds [" (ts, vf(y))
ds
oà f(ys) ds
J0 203 f(y))
20 f(ys)
llys + +f(ys))l
ds
20 f(ys)
(t)
(D.84)
where we used Lemma B.2 the last inequality.
Lemma D.11. Uso is coercive i.e., Une +o0 as ||x|| t00.
Proof. By Assumption 8, (s) = o(s as - oo and therefore a primitive of 1/0 must be coercive. By coercivity of (Assumption 5), Uso 2ar is also coercive.
Lemma D.12. For any Rd compaet, for any e 0, the set
(r(1) : [0, y C(10, T]), N. yo e K. S,, s sc
(D.85)
is included in the set
E Rd (x) c sup sup
(D.86)
which is compact.
Proof. Consider such a path C() with T E N. By Lemma D.10, we have, for any E [0,7].
Un)r(()) - (ro)(()) s Sp,r(y) cc.
(D.87)
Hence the set from (D.85) is included in
E Rd Us)(x) c sup Uso
(D.88)
Now, by Lemma D.11, the set of (D.88) is compact, that the set of (D.85) is bounded.
The following lemma is slight refinement of [5, Lem. D.33]. For any C crit(f) connected component of the set of critical points, we define its basin of attraction as the set of points from which the gradient flow converges to C:
Att((C) = E Rd lim (x), =
(D.89)
1-0000
45

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Lemma D.13. For any C erit()) connected component which is minimizing, for ö O small enough, for 8' small enough,
[0.6]
B(Ux(()), R (Ma(C)) > 0.
(D.90)
Moreover, (C) can be assumed to be contained in At.
Proof. Since C is minimizing, there exists 60 > 0 such that, for any x E Us, (C) \ fx) > fc where fc is the value of f on C. Moreover, by Lemma B.9, taking > small enough also ensures that Mo (C) C Attr(C).
Take 5 3 66. U (C) and == min { ao (x) aro (fc) : R d(x, 6/2]. By the continuity of Use and the fact that ao is (strictly) increasing, have that A O.
Finally, take 6' E [0, 6/2) small enough so that, for any E (C), f(x) a (Sc) A/2. To conclude the proof of this lemma, we now show that (C), Rd (Ms(C)) > O. Consider some 7 > 0 and y E C([O, 7], (T,R%) R2) such that E U (C),
yr E Rd \ (C). By continuity of and d(: C), there exists / E [0, such that d(7,, C) = 6/2. By Lemma D.10, we have that
A s Uw(()) aod(fc
Uwo(y)) Ur((r) (r) ac)(fc)
A s Si,r(y) 2
(D.91)
Since this is valid for any y, obtain that B(Us (C), Rd (Ub(C)) A/2> 0.
We now proceed to the key result of this section.
Lemma D.14. For any crit(f) connected component which is minimizing, for any x Attr( C),,
B(x, Rd Attr(C)) 0.
(D.92)
Proof. First, let us invoke Lemma D.13 to obtain some 0 < 6' < such that
B(Ux Rd (M > 0.
(D.93)
and Uo (C) c ACtr(CC..
Then, by Lemma D.12 and continuity of f and o2, the set
(o' (o2((()))) : [0. y e C([O.T)), 7 N, ro ===xx S,, 1}
(D.94)
is bounded by some finite constant +00)
With (x))roo the gradient flow starting from x (Definition 4), by definition of Attr(C), there exists S > 0 such that
@s(x) E (C)
(D.95)
Now, consider some 7 NN and y C((O.T]) such that yo =x, Yr E Rd Att(CC) and Sr(y) s
We now define
g: = I1y - (x)
(D.96)
In particular, y must be differentiable almost everywhere and have
(5. 0,,) - (x(x))
= V((x)) Ox(x)) + (9) + -
s plly; - (x)) +11 +v(()) + I1x
2x)x)
(B+ B+
1
=
91 + 11 v
(D.97)
2
2
46

---

The Global Convergence Time of SGD in Non-Convex Landscapes
where in the last inequality we used the smoothness of (Assumption 5) and Young's inequality. Rewriting (D.97), we have
d
e (e-(Bt))) 9.) s ---(--)) 211i + vf(r))
dr
2 11, + VV(x))1
(D.98)
so that integrating yields, for any r [O.T],
Ir S elott)r
S/' 11's ff(ss) ds
(D.99)
2
where used that (x(x) yo- Furthermore, introducing a, we have
11's Vf(x)l ds Ir lBt!!!!r S'
o2(f(x))
s ae (0- Sn,(1). (n,
(D.100)
by Lemma B.2.
Hence, we have that, for any E [0,7],
1l, - 0,(x11 s 2ae (B+h)) (1
(D.101)
Therefore, if consider y such that, in addition, Sr(r) S
-101
822
we have that, for min
2a
8'
0, s
(D.102)
2
We now distinguish two cases:
If = S..... S s T, then (D.102) combined with (D.95) yields that ys (C). But yr must be in Rd Attr(C) and so in Rd (Cs(C), so that one must have
Ar BlMs (C), Att((C))
(D.103)
I = i.e., s S, we extend the path y to & E C((O, such that y: = y; for E [0, 7] and yr: = O, (x) for [T. -ia o
In particular, Ss(4) = Sy(y)= < yield that
2a x
8
so that the same computations leading to (D.102) can be applied to & to 4
8' llvs - Os(x)l 2
(D.104)
This means that 6s E Ugg((C) which is included in Attr(C). This is contradiction since this means that yr is in Attr(C). Therefore, this case cannot happen.
Therefore, we have shown that, for any y E C((O, T)) such that yo = x and yr E Rdd Attr(CC) holds that
(
8'2
(u(cc))
Sr(y) 2 min
T. BB ((( (
(D.105)
2a
which is positive by (D.93).
We are now ready to prove the main result of this section.
47

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Theorem D.4. Consider Xo Rd that belongs Attr(Ca) for some (I...., Nenut such that C₁ is minimizing. Then, for any O, for V1,... Voo neighhorhoods of Ia....,Conn small enough, there no event H and positive constant A such that for all O < 1l 170-
xx (H) 1-e 1
(D.106)
and,
EIQlI-c
Elel0re
S Exn
To 11 e
(D.107)
Proof.
First, Lemma D.14 ensures that (xx, Rd Attr(Ci)) O so that, for any jE V # it holds B(x,, Cj) > 0. Define
A min B(xo, Cÿ) 0. jeV
(D.108)
Let us now apply Lemma C.11 to obtain that, for any small enough neighborhoods V; of C,, i l...., Neit there is some 770 > 0 such that for all j E ........ettt).. 0 < 170.
Qv(x, Vj) s +
(D.109)
Now define the event I/ as
H = x E Vi
(D.110)
with the notation of Definition (D.109) then ensures that
PA, (H) 2 1 11-e" 1
(D.111)
provided that is small enough so that e Nent $ 1. if E Q, the result is immediate. In the following, we assume that i $ Q.
Let us now invoke Lemma D.5 to obtain that, at the potential cost of requiring smaller Vi...., VN... neighborhoods of CI...., CN... or of reducing 7o. it holds that, for any 0 17 170, Xg.
EIQInEr 1
EIQIN
E
(D.112)
To conclude the proof, write, by the strong Markov property,
Ex0 H
=
E
H
km
P..
H))
Ex, H
E. "
:2
"
Px (H)
EIQin12e
Exp [m]e
Px, (H)
1002e
=
(D.113)
where we used (D.112) in the last inequality and taking n small enough so that $ 2 2. We have thus shown the RHS of the inequality the statement, and the LHS obtained by the same argument.
Similarly how Theorem D.2 was obtained from Theorem D.I, we immediately obtain the following corollary.
48

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Theorem D.5. Consider Xo Rd that belongs Attr(C() for some (I....,.au such that C₁ is minimizing. Then, for any for V1,... V Voo neighhorhoods of Ct....,Con .Nen small enough, there no event H and positive constant A such that for all O < nl 170.
P (H) - AAn A
(D.114)
and,
Exp 7 H] s
(D.115)
We now turn our attention to the lower-bound counterpart of Theorem D.5. Theorem D.6. Consider E Rd that belongs to Attr(C,) for some E (l....,,o such that Cj is minimizing. Under Assumption 10 and assuming that,
RR² > B - E(2
(D.116)
11527
for any for Vi...., VNew neighborhoods of .f,....,Co CNa small enough, there is 170 > 0, an event H and positive constant A such that for all O < 1 < 170.
PP xp H) 2 1 - A/n
(D.117)
and.
EiR10-c
Ex [T] 2
(D.118)
Theorem D.6 is obtained by combining Lemma D.9 with Lemma D.14 in the same way as Theorem D.4 obtained from Lemma D.5.
D.5
Full transition costs
Definition 16. We define, for j Nonth
Ci, == inf (N)( N 1, D,N), &o E C, EN-1 E =inf(Sr(r) T N.ye e D,(T), e C,, yr E Cj).
(D.119)
With the same arguments as Lemma C.2, we can show the alternate expression for Ci.j.
Lemma D.15. For any j E Neruh it holds that
C.. lim CT,²*
(D.120)
where
C = inf inf(AA(E) : 2 1,5 D,), so EN- = =in((Sr(r) 7 E N. y (T),), yo E (c())) yT E(b(C))
EN-I
(D.121)
We also relate Cr, in terms Br.j- Lemma D.16. For any e (1.....A K}, E (l...., Nerit, it holds that
Cr, S B
(D.122)
and, Ci.j < Bi then there must exist Q such that B S Ci.j < Bi.j.
This lemma is direct consequence of the definitions of Ci, (Definition 16) and Br, (Definition 10) and is therefore omitted. Lemma D.17. For any i E (In)..,Ner)),
Ck.ig G( o)
E(Q s mins
Σ k-
CK.: : ((2) min
Σ
(D.123)
k k-
49

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. By Definition 13, have that Let us begin by lower- bourdin the second term. By Lemma D.16, holds that
E(Q) E(2) E(i f Q)
(D.124)
E(i t 2) min
Buy :ei:ge (
k-1co
min
Σ k-leg
CR. ge 0(1+
(D.125)
Now, let us turn our attention to the first term: by Lemma D.16, we have that
( min
Σ k-ley
B Ph.igen g(((
min
Σ k-ley
Cu. : (gr:))((2))
(D.126)
But, for any G(Q) which reaches that minimum, all its edges k - / must be such Вa = CR, by Lemma D.16 (otherwise we would replace it by an edge to Q with lower cost). Therefore, we must also have that
B&.1 : g {
min
CK. : g E 9(0) 2 ming k-llg
Σ
Σ k k-llgg
(D.127)
which shows that
E(
min
Σ k-Teg
Cai g
(D.128)
This concludes the proof.
Finally, let restate result from [5]that will be relevant in the following.
Lemma D.18 ([5, Lem. D.31)). IfC; is not asymptotically stable, then there exists V such that Bt.j O and such that C2 asymptotically stable.
D.6 Link to topological properties of the loss landscape
The goal of this section prove the following result. Proposition D.1. The following properties are equivalent:
(i) For all E Rd, E(Q)x) = 0.
(ii) For all i (1....,K), K), E(Q1))= =0
(ii) For all (I....,),, K4 is not locally minimizing.
Proof. Items (i) and (ii) are equivalent by definition of E(21x) (Definition 14). We thus focus on the equivalence of (ii) and (iii).
First, let us consider the case where there is some i (1....,K K} such that K,, is locally minimizing. By Lemma D.13, there exists 5 > 0 small enough such that
B(C,, Rd (KG)) > 0.
(D.129)
As consequence, for any j # Br,, > 0. Consider g G(V) such that
E(Q)= Σ B
(D.130)
k k-oteg
50

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Consider the graph o' obtained by removing the edge in graph that exits This edge must have positive cost and therefore
Σ
BR.1 >
E
BR. 2 E(i Q)
(D.131)
k-leg
k-ley
Combining (D.130) and (D.131), obtain that E(210) 0
Let us now turn to the case where there is n (l...., K) such that K2 is locally minimizing. Take any i E (l....,K) We bound ()) with Lemma D.17:
E( & min
CK. : g (( min k-leg
Σ
Ck.:: g k-leg
Σ
(D.132)
Take any 9 E G( f Q). By Lemma D.18, there exists j E V such that Bi, = 0 and K, is asymptotically stable. By assumption, j must thus belong Q. Consider g' ((Q) obtained by adding the edge - j to y. (D.132) then yields that E () = 0.
51

---

The Global Convergence Time of SGD in Non-Convex Landscapes
E Potential-based Bounds
E.1 Noise assumptions
Assumption 11 introduces key requirements the noise behavior through bounds on H and 2 around the gradient V (xx).. Intuitively, the bound on H. controls how large the noise can be (upper bound), while the bound on & ensures the noise maintains sufficient variance in all directions (lower bound) around the gradient. We then present two ways to satisfy these requirements:
Gaussian noise. The first approach, detailed in Lemma E.2, considers the case when the noise follows a truncated Gaussian distribution. This is standard Gaussian with variance (f)x),, but restricted to stay within a ball of radius R(f(x).
Support and covariance conditions. Lemma E. provides a more general approach with two main requirements:
support condition ensuring the noise can be large enough any direction around V Vx(x) with some positive probability
A lower bound on the covariance matrix of the noise
This second approach is more flexible as allows for Gausian noise distributions. A key example discrete noise distributions, where u(x, ()) takes values finite set. The support condition then requires that some points in the support sufficiently far from V fx) in every direction.
Assumption 11. For some Rd, there exist J. 0.22 (0, +00) continuous functions such that, for all that
X, it holds
2
{((()))
Vp E Rd s.t. |||l| F(((x)
H)xxp)s
||a112
Vu Rd s.t. I|e vf(x)l S [[v(()]] Σ(x,0)
(E.1)
2f²(f(x))
Remark E.1. Assumption 11 is generalized and detailed version of Assumption 4. Indeed, our blanket assumptions the noise Assumption 7 already imply upper-bound on (xx, p) with x² 03. for any x, p Rd. Assumption 11 allows for refined results when a tighter upper-bound on H(x, p) is available for restricted set of x and p.
Note that, in general, will have /² 2 hence the notation.
Lemma E.1. Assume for some X Rd relatively compact. there exists 0 such that,
b = (((((,)))))) VV(())) a IV xx x X s 0.
(E.2)
there exists z²: R + (0, +00) continuous function such that, for all x E X, it holds that
cov uxx, w) > (
(E.3)
Then, for any x E X, u E Rd such that ||I - vf())l & [x) I, holds that
_(x, o) s max(1 (1, log b-1 ||o|12
(F.4)
ac {²(((x)))
where 0 is a constant small enough such that
e X. E BOO,c), ||Hess, H((x, cov cov (((x))
{((())
(E.5)
for the matrix norm ussociated with the Euclidean norm.
Note that e always exists by the relative compactness of and the fact that
Hess, H((x 0) = cov u(x, w)
(E.6)
52

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. The first part of the proof consists in showing that, for x X, p Rd it holds that
H p) & ((((x)) min(c, I|el)
(E.7 7)
Let us first consider the case where ||pl| Since both M((x, 0) and V, Oxx E(u(x, O, have that
1 H(x, p)
2 L Hessp H(xx1p)p)dd
1 [( (p.covu(x..)))dtt - ((6))))1)))
2
(f())))1
(E.8)
where we successively used Cauchy-Schwarz inequality, (E.5) and (E.3). (E.8) readily yields (E.7) when ||pll s c.
Let us now consider the case where ||p|| c. By concavity the function sc/llll on R, and Jensen's 's inequality, we have that
|Pll H. x,c
H(x, p) 2
Ipll P Ipll (f())
TPT
((((()))
(E.9)
4
where we used (E.8) in the last inequality. This concludes the proof of (E.7).
The second step this proof now consists in showing that, for x E X, E Rd such that ||u vf(()l < [V] holds that
arg (p. Fl(x, = arg min (f((x, b) c B log b
(E.10)
PER
peRd
x E X, p Rd, we can lower-bound H(xx, p) using (E.2):
A(x, p) log H[exp((p.x<xx,o)))
<p. fx)x)) - Vf(x))
|I I 1(( ((xx)))) -(xxx)))-((())
P
a (++11((())))
(p. Vx((x) log E
Ipll
(p. (x()) (1pl((aaaa))))) || [[) log
(E.11)
As consequence, for Rd such that ||c v [x)]] = ||V we obtain that
H((x,)) - (p.0) z (p. fx)) n) + [I ||V][x)I)))))) log
2 ||p||a log b,
(E.12)
where used Sauuchy-Shhwaz inequality and the condition
In particular, (E. implies that + Hl(x, p) (p.b) is coercive on Rd and therefore arg min minpere (F((x, p) (p, 1)) is well-defined.
Remarking that Fx(x, 0) - -0 O, we can now conclude that arg min
(F((x, p) (p,u)} must be included in
log b-
{p Rd [|p]|a log s 0) = B 0.
(E.13)
a
which completes the proof of 10).
53

---

The Global Convergence Time of SGD in Non-Convex Landscapes
To conclude the proof of this lemma, (E.10) to obtain that, for X, u IR such that ||e vS(0)l |VV
C(x.0) sup
{p. 1) H(xx ())
peR-
log b-
= sup (p.u) -H(x, p) B
s sup (p.o) (²(((x)) min(c, ||p|DIll
log b-
e 0.
(E.14)
4
where we used (E.7) in the last inequality.
B 0, log.b! it holds that
Now, we note that, for any p
(x)) min(c, IPID
if
4
if c
log
(((()))
min
ac log b-1
(E.15)
Plugging (E.15) into (E.14), we obtain that
[(x,v) sup (p, 1) min
1, ac
(f(x))l
P B 0,
log b
log b
((()))1
sup (p. 1) min
1, ac log b-1
p Rd
max 1, log b-1
||u|12
(E.16)
ac
{2(((x))
which concludes the proof of this lemma.
The following lemma is an immediate consequence of Lemma G.1.
Lemma E.2. Consider & Assume that u(x, w) follows Gaussian distribution (O, (f()))) conditioned on being in BO, R Rx)(x) for all x e Rd and some continuous function 0², R (0, +co). Assume that 8 fx)]] R(f(x) for all x E Rd and that inf Rif(x)) and (f))))
of()) 2 O(log 1/E). Then Assumption 11 holds with X Rd, (f(xx) (1+ =)) for all Rd.
E.2 Potentials and path reversal
Let us now define the potentials associated the variance functions 2² and x² introduced in Assumption 11. Definition 17. G ... g² + (0, +00) continuous functions, we define the potentials U.U R - R as
U(x) = (x)) where ã F:: RR - R is primitive of 1/0²
(E.17)
U(x) (x))
where a R is primitive of 1/7
(E.18)
We begin by adapting [5, Lem EE.1] the current setting.
Lemma E.3. Consider y e C[[O,T)). Then, there exists y C((O, ST) reparametrization of y such that, for any e [0.S],
| = ||V (Y
(E.19)
and, under Assumption 11,
11, + +
Sr(y)
ds. 2 (f(7))
(E.20)
54

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Proof. By the proof Freidlin & Wentzell [22, Chap. 4, Lem. 3.1J, there exists (s) change of time such that, with 7s = Yr(s))
1|, = (V
We have that
Sr(y) S/" -/-"'
((G))) ds,
(E.21)
so it suffices bound 7,)..7,) from below: by definition, have
L(5s. (i(s)) 2 sup (p. (i(s)) v)(()) H(F..p) ||pll 2/
(((()))
2 sup (p.( v(())) {(((7s))
||||| :1ell= - 2//))(7))1
(E.22)
2
((
by Assumption 11. Applying Lemma G.2 with almost all s,
(((s)))17,,1 vf(()) and 1 (i(s)) -1 exactly yields, for
((((s))
/
((Tss 2 (i(s))- sup
2 || -llll = (((()))
(i(s)) 11 V
(E.23)
27 (F(+))
since (p.7, VS())) )((((+)) 2
||| reaches it maximum at p- (
whose norm satisfies I|e"|l s
((6)
An important consequence of Assumption is that the action cost of going from x to x' can be related to the action cost of going from x' to x. This formalized in Lemma E.4.
Lemma E.4. For any O, x, E Rd, y E C((O,T)) such that yo = x and yr = x', under Assumption 11, if is contained X, holds that,
Sr z inf o²((xx) (0xx
(E.24)
xex (f(xx)
Proof. Let us first invoke Lemma E.3: there exists ý E S[) a reparametrization of y such that, for any / E [0.
| = |V
(E.25)
and,
Sr(y) 2 /00 S + V ds
(T(())
((((x)
17 + Vf
inf xxX (((())
(E.26)
20 (7x))
It now suffices to lower-bound the integral the RHS of (E.26). We have
L0 1Ý. +V-II ds=
1 [ +V ds+ I 2 vf(7s)) o²(f(7.)) ds.
(E.27)
(f(3)
20
By definition of U (Definition 17) the second integral is equal to
[ 2 vs(7s)
ds = S S ((((T.))
vU(A)) ds
55

---

The Global Convergence Time of SGD in Non-Convex Landscapes
-x(x) U(x)
(E.28)
For the first integral in (E.27), define the path (45))et(..5) by 4ss = =s--s. We have that
Jo 1- + V
S 11+s ([(ss) ds
ds
(f7()
J
20 f0²))
E( + C.ars++V/((Npp V((,)))) ds
= Ss(
2 B(x,x')
(E.29)
where used Assumption 11 in the first inequality with - Φ. ((xs whose norm satisfies the condition of Assumption 11 by (E.25). Plugging (E.29) and (E.29) into (E.27) and then into (E.26) yields the desired result.
E.3
Graph representation
Let us reuse the notation of Appendix D. In Appendix D, we consider graphs over the set of vertices V = (1..... Nert) and the set of edges (V') \ Q) x V where Q = .......,.rg)..
Let us consider set of particular edges & (V Q) x V such that
{= Q) () j. cl Aur(C)) ncl Att((C) * 0).
(E.30)
Note that by Lemma B.8, we have that Attr E ..rit) is partition of Rd Therefore, (V. still satisfies that, from every i E V there is path that leads to Q.
Lemma E.5. For any i j E &, let us define
Xi.j
arg min xxel And Aur(C,)
f(x).
(E.31)
Then, under Assumption 11, if X is large enough so that it contains the bounded set
x X Rd f(x) S
max ieVio.eVV.ie
f(xI,)) +1
(E.32)
for any i j E E, holds that
C. S -US,)
(E.33)
Proof. Note that the coercivity of f (Assumption 5) ensure that xi,j is well-defined and the set of (E.32) is bounded.
Take i E V v, j. We first consider the case where fx(xi)) # 0. Fix > 0.
By Lemma D.15, we have that there exists 6 > such that, for any 6 E (0,
Ct, C. +
(E.34)
At the potential cost of reducing dn O, assume that, for any E B( 6o/2), it holds that
E [V]() s b and J% (x))) 2c.
(E.35)
for some 0 < $ b and c > 0. Moreover, by continuity of and U, also assume that óg is small enough so that, for any x E (B(xi,j. 6n/2), it holds that
U(x) s U(xI,) +
(E.36)
and,
f(x) f(xi,) +1
(F.37)
56

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Finally, also assume that 60 is small enough such that, for any (o(C), it holds that
U(x) 2 U(,)) -.
(E.38)
Fix (0,60) 60) such that < E. Now, since XI,J E cl Attr((C) n el Attr(C)), there exist x, e Attr(Ci) n ((x,,)6//2) and N Attr(C,) n [x 6/2). By construction, the gradient flows started x; and x, converge respectively C, and Cj. Hence, there exists
integer such that (x-a/2(xi) (C( and ax/) Us(C,) for all ō/a.
Let now estimates the action costs of the paths (07-0/2-((4)) definition of the flow, the whole path (0r-a/2-((xx)))000000- is contained in (E.32) and therefore in X. Therefore, by Assumption 11, we have that
and (0, (ee))), By (E.37) and
T-a/2
S1-0/2(00-0/1-(xx)))
((0r:-.:--660)))1/0000-----111 di
a/22
[10r-..2--(t)3777/0rr...222-1 dt T-af2 41V5(0)--//2((:;))1 (f((0r--/)-- dr.
(E.39)
where we used Assumption 11 in the last inequality. Rewriting this integral we obtain,
T-a/2 2r di
01-a:2(00-0/2-000) &
o(f(OTTa//-1xx))))
T-af2
(N dt
J0
U(xi) - =((0-a/2(xi))
U(x.i) U(C,) +
(E.40)
by (E.36) and (E.38).
For the path (0, (x))))))110 since is a trajectory of the gradient flow, we have that
St (0- (x.)x)) =0.
(E.41)
Finally, let consider the path (y))ejo.)) defined by 7, = + a r(x, - x;). We have ý, = ax x;) so that lhrrll s 6/a a s [[V)()))l by (E.35). Moreover, (E.37) ensures that y, e X for all E [0.
Therefore, by Assumption 11, we have that
1" C(y, V1) dt
S.(r)
0-² Zlyn vf(r)t)) di
11 + +f(r)l?
dr
3
2 (f(x))
b)+
2c
5(a + b)2
2ac
s(a + b)2
(E.42)
2ac
57

---

The Global Convergence Time of SGD in Non-Convex Landscapes
Putting the three paths (0r-a/2-. re)) (7))) and (0, (e)(x))) together, we obtain path that goes from (c(C;) to (C)) in integer time 27 and whose action cost is upper-hounded by
8(a + b)
((x,)) - -CC, + 2
(E.43)
2
Combined with (E.34), this yields
E(a + b)²
Ci. s ( UC,)) + 38
(E.44)
2
which yields the result.
Let us now briefly discuss the where (x(xii)) In this case, Xi,j belongs some C,, / E V. To adapt the proof above, it suffices to require that X, and x close enough to x1, that they belong (&(Ci) (give by Lemma B.6) and to use Lemma B.7 to build path from x; to xj with cost at most
We provide iterated version of Lemma E.5 that will be convenient in the following.
Corollary E.1. For any e V\ Q. j V, define
Ci. min
(xinnddnn) U(C =. JN =. Jn In+ E
(E.45)
Then, under the same assumptions as Lemma E.S, it holds that
Cij S Ci.j
(E.46)
Let us now specify how big enough we will need the set from Assumption 11 be. Lemma E.6. Define
C.. == max C., + +00.
(E.47)
i.jevi
Then, if X is large enough so that it contains the bounded set
x XERR: U+(xx) S
sup ieVie.ee
U(x) Coo..
(E.48)
then, for any j.j E VVQ. it holds that Ci,j is equal to inf(Sr(y) y C((0,7)), T N, yo C., Cj. (x(1) : [0,7]] c xx..
(E.49)
Proof. Note that Coo is finite by Assumption 9. The rest of the result is then direct consequence of Lemma D.12.
We can now combine Lemma E.4 with Lemma E.6 to obtain the following result.
Lemma E.7. Under Assumption 11, if X large enough so that it satisfies the requirement of Lemma E.6, then for any
i.j V Q i j, holds that
Cja- C.j AC + +1 (1- UU).
(E.50)
where A [0, satisfies
cf((x))
sup
(E.51)
F(f(x)
xxX
Proof. Lemma E.6 allows us to consider only paths that are contained in X to compute Ci,j- Taking the infimum over such paths in Lemma E,4 yields:
C₁2 2 (1 (C, (U,- - -U))
(E.52)
Rearranging the terms, we obtain the result.
58

---

The Global Convergence Time of SGD in Non-Convex Landscapes
To simplify the notation for the following lemma, let define, for i V/
ULJ ((4,)) and U(C))
(F.53)
Lemma E.8. Assume that Assumption 11 holds with satisfying the assumptions of Lemmas E.5 and E.6.
For any in E V Q g G(io 2), there exists E VV such that there is path from in in g and there is of E G such that the cost difference between g and g'
Σ k-llg
CL.I
Σ
Cx.1
(E.54)
k-lEy
is upper-bounded by
(Ujr.int - -Ujo U ji-J01 - -Ui) 2A(Neri 2 2 +1suup U
min
max p=
max
x
i= 1p E 2 / V Q J1 jun jun E 10.............
(B.55)
where A E [0, satisfies
2 sup 1 cf((x)) xxX {f(())
(E.56)
Proof. By definition of (io - Q) (Appendix D.1), there exists i \ Q. j V, j such that if were add the edge i j to g. it would be Q-graph. In other words, is not in g and there paths from io - i and Q in g.
Now, take consider path that goes from i to j with only edges from E: jo i, jp and ji V. ji ji+1 E E,
1=0, -=
Define 2 to be the smallest integer such that there is path from j& to Q in g. Such a exists since there is path from since there no path from to Q in g. particular, there is no path from jk-1 to Q in g. From the definition of the graphs G(io Q), this implies either there a path from to jk-1 in g or path from fk-1
j to Q in g. and
g.
If there is path from to jk-1 in g. then consider the graph g' G( obtained by adding the edge jk-1 jk g. Since jA-1- ju is in E, by Lemma E.5, the cost of adding that edge is bounded as
Cie-i-ia Ju-r-i - jk-1
(E.57)
in which case (E.55) immediately satisfied.
there is path from jx-1 to í in g. then we consider the graph g' E G(Q) obtained by reversing the path from jk-1 to in g and adding the edge jk-1 - jkk Let us denote by mo = jk-1, mg = and my E V Q, my - m441 E g. = O...., the path from jR-1 By Lemmas E.5 and E.7 the cost of reversing that path and adding the edge jR-1 jk upper-bounded by
C GmL-1. .i
+ Che-I.Ja Cm..mia
AC mC (1- A)) - -Uma))
U JU-Ii. Jn-
1=0
ACmin.m () +U jn-ije UK--1-
(E.58)
Now, Corollary E. ensures that the sum Σ9-1 ACmun.m is upper-bounded by 2Nart 2 supx U so we obtain that the RHS of (E.58) upper-hounded by
2N 2A sup U + U je-1.jk U; + 2A sup U,
(E.59)
which concludes the proof.
59

---

The Global Convergence Time of SGD in Non-Convex Landscapes
To obtain the main result, we will require the following lemma.
Lemma E.9. Under Assumption 11, if X large enough so that it satisfies the assumptions of Lemma E.6, then for any
i.j V ii + j, holds that For any i E V 2 jeV, j. holds that
Cij 2 C.
y - C((O. (T), T T, yo E y7 c
inf
-
(E.60)
s<t
Proof. This lemma follows the same proof as Lemma D.10 with the additional use of Lemma E.6 to be able to leverage Assumption 11.
We are now finally ready to prove the main result.
Theorem E.1. Assume that Assumption 11 holds with X satisfying the assumptions of Lemmas E.5 and E.6.
For any to E VV Q. define
min
Σ
Cr. g G(io t 2)
(F.61)
k-Ileg
there exists i E V. Q such that Cio,i $ such that E(Q io) is upper-bounded by
max (Un.ie - J U Ju.Ju1 - -U,) + 2A(Neri 1) sup U:
min
max 1=0....p--
x
jin1 jun E o,... O jo = i, E 1-
(E.62)
where A E [0, 1] satisfies
A 2 sup 1 g2(((x)
(E.63)
x 7(((x)
Proof. By Lemma D.16, io) is upper-bounded
E(Q 1o) min
Σ ge ((O)
min
Σ
Cu. G(io + 9)
(E.64)
k-leg
1-yley
By Corollary E.1, we have that
C g G(io fo 2) s min
min
Σ
Σ k-leg
fo 2) =r.
(E.65)
leg
Hence, take g arg min (in Cx.:g g G(Q 2 and it must satisfy
Σ CR. k k-Teg
(E.66)
Apply Lemma F.8 to obtain that there exists E V \ Q such that there a path from in to in g and there is g' G such that the cost difference between g and g' bounded by (E.62). Combined with (E.64), this yields that E(Q 1)) upper-bounded by (E.62).
Finally, denote by jo io. jp i and V 2, ji jo1 E g. / .... O...., that
the path from in to i in (F.66) ensures
2
Σ
Cinii 2 Ci..
(E.67)
1m0
which, combined with Lemma E.9, implies that C2 S r.
60

---

The Global Convergence Time of SGD in Non-Convex Landscapes
0.0067
0.0255
0.0016
0.0011
0.0009
0.0007
0,0006
0.000S
Theory
10a
Data
10
Converguoe Time (log scale)
107
105
10a
101
102
102
10
10a
Step-size scale)
(a) Loss landscape and hitting time statisties for the Styblinski Tang function (F.la).
0.0067
0.0022
0.0013
0.0009
0.0007
0.0006
0.0005
200
Theory
10a
Data
10*
Convergence Time (log scale)
107
105
10a
10
1100
102
102
2
10
10a
Step-size (inverse (inversee scale)
(b) Loss landscape and hitting time statistics for the Himmelblau function (F.Ib).
Figure 4: Visualization and hitting time statistics for the Styblinski Taansskk--Tanggga (top) and Himmelblau functions (bottom). In both cases, the loss landscape superimposed on the stable and unstable manifolds of the function's 's critical points, which define the edges of its transition graph (the arrows indicate the direction of the gradient flow, and hence the transitions which come cost).
F Numerical validation
In this last appendix, we provide some more numerical experiments as validation of the estimates provided by Theorems I and 2. For concreteness, we consider the following multimodal test functions:
(a) The Styblinski-Tang function:
1 d f(M,,)))
(xf (xt i=1
16x7 + 5x,))
(F.la)
(b) The Himmelblau function:
x(x,,))) xx + +
(F.1b)
For the Styblinski- Tang function, treat the 2-dimensional case in order facilitate comparisons with the other examples, and for ease of visualization.
In Fig. 4, we plot the landscape of f for each of the above cases, as well as the runtime statistics of (SGD) in each case. As in Fig. 2, we considered different values of the algorithm's 's learning rate and for each value of we performed 500 runs of (SGD) with Gaussian noise (a = 50). Then, for each "particle" of (SGD), we recorded the number of iterations required to reach the vicinity of P1 (within 10-2) from the same, fixed initialization. The resulting boxplots are displayed in Fig. 4 in log-inverse scale, with point density overlay to illustrate the full empirical distribution of z for every 17.
61

---

The Global Convergence Time of SGD in Non-Convex Landscapes
In both cases, plotted the theoretical prediction of Theorem 1 (labeled "Theory"), against linear regression plot of the observed runtime data (labeled "Data"). 13 For the Styblinski-TTang function, observe situation similar to the three-hump-camel example of Fig. 2: Both theory and experiment indicate that the global convergence time of (SGD) scales exponentially in the inverse of the algorithm's 's step-size 1). and there is excellent agreement between theory and experiment (R² = 0.973 and R² 0.989 respectively). By contrast, in the Himmelblau case, runtimes are significantly slower, and the slope the theoretical estimator is O: This is because the Himmelblau function does not have any spurious minima, so r enters the subexponential regime; this is confirmed by the fact that the algorithm's runtime several orders of magnitude smaller, with strong agreeemnt between our theoretical estimate and the numerically measured values (R² 0.913 and R² 0.976 respectively).
In more detail, we plotted a linear fit with slope given by Theorem
62

---

The Global Convergence Time of SGD in Non-Convex Landscapes
G
Auxiliary results
G.1 Truncated Gaussian distribution
Let restate two technical lemmas from [5]on which rely. The first one provides bounds the Hamiltonian and Lagrangian of a truncated Gaussian distribution.
Lemma G.1 ([5, Lem. F.2)). Consider X -N, multivariate Gaussian distribution with σ² > O. For R 0, define the truncated Gaussian random variable (I.v.) XR by conditioning X to the ball B(0, R). Define
H((p) = log E e(p.Xx)
(G.1)
E(p) = (p).
(G.2)
and
R²
E R) = e 16 2d+3 (d
(G.3)
and assume that R 0 satisfies
40 (d + 3) log + log d 1).
(G.4)
Then, for any p E Rd such that ||l||
R
Rd such that ||o|| s R. it holds that
2
r 1bll sH((p)
o 1|ll
1-EE(O? R))
| E(o?, R))
(G.5)
2
|1011 sC(()= s |1 2o² R)
||1|12
- 11-2E(02, R)
(G.6)
20
20
We will also require the following technical lemma. Lemma G.2 ([5, Lem. F.3]). Consider u, w E Rd such that 0 < ||l||| s uR for some R. H > O. Define,
f(u) sup peRd-
{p.u) H
2 11p11
(G.7)
then, with d
aʃ 15(2 + ss(u w)
(G.8)
63


Reviews:
[{"review_id": "QbaAWRELsy", "reviewer": "Reviewer_jzu6", "summary": "This article analyzes global convergence of SGD on non-convex optimization from the large deviation theory in probability. The question of how long does it take SGD to reach the vicinity of a global minimum of a loss f is studied. A tight theoretical estimation about this time is obtained under suitable assumptions. The contribution of the article is based on non-trivial technical contents. The results rely on the geometry of the loss function, SGD noise and its initialization. It gives an interesting picture of SGD for practitioners.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time and input. We reply to your questions and remarks below, and we will of course update our paper accordingly at the first revision opportunity.\n\n- **The notion of the quasi-potential.** This concept plays a central role in the theory of large deviations as developed by Freidlin and Wentzell, see e.g., Chapters 4.2 and 4.3 of [21]. We agree that this definition is not standard in the ML literature: it is for this reason that we devoted pages 4-5 to build up to it, and we would be happy to expand on this in our revision.\n- **Continuous curves hitting Q in non-integer times.** This is a great point, thanks for bringing it up! Indeed, the curves that go in the definition (16) of the quasi-potential are only required to avoid Q at integer times. This is not a mistake: while it is possible for a continuous curve to enter Q at non-integer times, we only need to exclude integer times because we are only interested in the hitting time of the discrete-time process, not its continuous-time interpolations. There is, of course, a lot of technical work that is required to justify this, starting with the large-deviations principle in Appendix B.3 as well the analysis of transitions between critical points in Appendix C (where the peculiar curves you mention are introduced).\n- **The attracting strength.** This notion is only required for the statement of our lower bounds in Thms 1 & 2. The reason is highly technical, and we explain it in detail in Appendices D.3 and D.4.\n- **Numerical verification.** We took advantage of the rebuttal period to perform a series of numerical experiments on some standard global optimization benchmarks, which show an exceedingly good fit between theory and practice, see [here](https://tinyurl.com/2k5ay5c6) (anonymous link). More broadly, we agree that it may be difficult to perform a numerical validation campaign in full generality but, at the same time, this is what we believe is the power of our theory: our results do not provide an upper or lower bound of the convergence time of SGD, but a tight characterization thereof in terms of the features of the problem and the parameters of the method, in cases where nothing can be said otherwise.\n\n  In terms of practical insights, our results already show that the global convergence time scales as exp(1/variance/η) in terms of the method's step-size and the variance of the noise, which is a concrete take-away for practitioners. Moreover, in Section 5, we describe the precise way in which the energy increases as spurious local minima get deeper, which dovetails with results on loss landscapes of neural networks showing that these depths vanish as the number of parameters grows. Thus, even without reaching the overparametrization regime, increasing the number of parameters intrinsically improves the optimization process.\n\n  Overall, we see our framework as a first step towards understanding modern step-size selections strategies, such as periodic schedules or adaptive algorithms, which cannot be otherwised approached theoretically.\n- **Uniformity of notation with [4] (Azizian et al.).** It is true that our choice of notation and terminology in pp. 4-6 follows [4] which, in turn, roughly follows the textbook of Freidlin & Wentzell [21]. This is by design: The setup required for the large deviations machinery is highly non-standard in the ML and optimization literatures, so we wanted to carefully introduce everything. The similarity in notation with [4] was intended to provide an anchor that would make it easier for the reader to connect and compare our setup with [4], which assumptions and definitions are similar, which aren't, and so forth. We made this choice consciously, even at the expense of presenting a more detailed proof sketch and overview of the technical trajectory leading to our results, because we felt that providing a simple pointer to [4] would make for a non-self-contained presentation that would be very difficult to follow. We did not enter a detailed point-by-point \"compare-and-contrast\" discussion for each assumption and definition in our paper because the focus of our paper and that of [4] is completely different (long-run distribution versus global convergence time), but if you think this would be warranted, we would be happy to provide more details.\n- **Statement of Theorem 1.** Are you referring to the attracting strength? This is defined in (1), L242.\n- **Compactness of Ω.** This is a purely technical assumption facilitating the treatment of the noise - it is standard for minibatch noise and/or inverse transform sampling.\n- **The definition of Q.** Throughout the main, $\\mathcal{Q} = \\arg\\min f$, as per (10). Eq. (16) and Thm 1 refer to that with the caveat that, to lighten notation, we are identifying nodes of the graph with Q itself.\n- **On $\\sigma_{\\infty}$:** Yes, this was supposed to be $\\underline{\\sigma}$, thanks!\n\n---\nLooking forward to a fruitful discussion! Regards,\n\nThe authors", "claims_and_evidence": "The main theorem (theorem 1) gives a tight bound of the stopping time tau, when the choice of the set Q is large. I am not able to check the proof as I do not understand the key concept “quasi-potential” which seems not to be standard in the literature. \n\nIt seems me that it might also contain some flaw in its definition (eq. 16). Are you sure that the B(x,x’) which takes account only the curves gamma on [0,T], will not go through the set Q over [0,T]? It is not so clear from the definition as in C_T(x,x’,Q), only the points at time n=1..T_1 are restricted to be outside Q. But gamma is a continuous curve, so it might hit the Q at some other time.", "methods_and_evaluation_criteria": "In eq. 11, the attracting strength is introduced, but it seems not have been used in the article. Could the authors clarify this?", "theoretical_claims": "I did not have time to check the proof.", "experimental_designs_or_analyses": "Na", "relation_to_broader_scientific_literature": "Na", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The theoretical results seem to be very hard to verify numerically since the first-hitting time tau can not be computed without knowing the global optima. Therefore it is unclear how the insights could be transferred to practical training using SGD. It would be good to discuss this aspect in the article.", "other_comments_or_suggestions": "The current article has a large overlap (page 4-6) with the contents in Azizian+2024. It would better to reduce the overlapped part to focus on the main contributions.\n\nRegarding theorem 1, it would be better to make the statement more precise, by citing properly the needed conditions in appendix. \n\nIt is not so clear why the random seed omega in Section 3 (a) line 173, needs to be a compact subset. Could the authors clarify this?\n\n\n[Azizian+2024]WHAT IS THE LONG-RUN DISTRIBUTION OF STOCHASTIC GRADIENT DESCENT? A LARGE DEVIATIONS ANALYSIS. WAÏSS AZIZIANc,∗, FRANCK IUTZELER♯, JÉRÔME MALICK∗, AND PANAYOTIS MERTIKOPOULOS⋄", "questions_for_authors": "The definition of the Q in eq. 16 is not so clear. Is it the same as the Q in Theorem 1? Or it is defined in eq. 10?\nWhat is the sigma_inf below eq. 7? Is it bar(sigma)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0aLDs8hqWC", "reviewer": "Reviewer_U6wN", "summary": "This paper answers a hard question in the optimization theory: how long it takes for the SGD to reach the global minimum of a general non-convex loss function. The answer is given in Theorem 1 and Theorem 2: the expected time is exponentially proportional to $E[Q]/\\eta$. Later, the author characterizes $E[Q]$, which describes the attracting strength determined by many factors.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, input, positive evaluation and appreciation! We reply to your remarks and questions below:\n- **On the beginning of Section 4.** Yes, we designed this part as a ramp-up to the technical apparatus required to state our results. As you mentionned, this is just a \"gentle start [...] for understanding the main result of this paper.\"\n- **On the inclusion of a proof sketch.** We hesitated to go into a lengthier presentation of the technical trajectory leading to our results because of space constraints. We will be happy to take advantage of the first revision opportunity to include a sketch.\n\n  To lay the groundwork, we prepared a flowchart of the logical structure of the proof in the anonymized link [here](https://tinyurl.com/mb4r9udc). In short, the main steps are as follows:\n  1. Our framework is built on a a LDP for SGD (B.3): it yields precise estimations of the probability that SGD approximately follows an arbitrary continuous-time path.\n  2. In particular, it allows us (App. C) to conduct a precise study of the transitions of SGD between critical points: we carefully estimate both the transition probabilities and the transition times.\n  3. We then construct an induced chain that lives only the set of critical points and show that it captures the global convergence of properties. We may therefore restrict our focus to this induced chain which is a finite state space Markov chain.\n  4. Subsequently, in Appendix D, we leverage quantitaive results for finite state space Markov of such chains to obtain global convergence bounds for the induced chain that we then translate back to SGD. This last step is trickier for the case of lower-bound and we remedy that difficulty by exploiting the attracting strength assumptions.\n\n- **On infinite numbers of critical components.** Formally, yes, the number of critical components is required to be finite (though, of course, the number of critical points could be uncountable). Note however, that functions like $\\sin x$ are ruled out by the gradient coercivity assumption. In fact, even though it is possible to construct examples with an infinite number of critical components that  satisfy all other assumptions, these examples are highly pathological, and thus not central to the considerations of our paper.\n\n- **On the role of $p$ in Theorem 2.**  In a way, yes. Theorem 2 essentially states that all initial points in the basin of $p$ will move to a small neighborhood of $p$ with overwhelmingly high probability. Because this transition takes relatively little time, the global convergence time from $x$ to the global minimum is approximately equal to the convergence time from $p$. This reduction in turn allows us to obtain the more detailed bounds of Section 5.\n\n---\nWe thank you again for your time and positive evaluation! Please let us know if any of the above points is not sufficiently clear.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "All claims made in this submission are well supported by clear justification and convincing evidence.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I checked \"An illustrative use case.\" to see if Assumption 1 will be satisfied. These claims should be correct.\n\nI also checked other parts of the main paper, but I cannot simply conclude if these results are correct or not. These parts are beyond my mathematical knowledge; I will tend to believe these theoretical proofs are correct, as the results make sense by my guess.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The results and developed mathematical tools presented in this paper is completely new. Though it has some overlappings with Ref. [4] on using the large deviation theory, this paper goes further and resolves an important but challenging problem in the optimization theory: how long the SGD takes to reach the global minimum. Unlike other finite-time analysis (they only consider the convergence to the stationary point, or make additional assumptions), this submission only requires sufficiently mild assumptions and presents much stronger conclusion. \n\n[4] Azizian, W., Iutzeler, F., Malick, J., and Mertikopoulos, P.\nWhat is the long-run distribution of stochastic gradient descent? A large deviations analysis. In ICML ’24: Proceedings of the 41st International Conference on Machine Learning, 2024.", "essential_references_not_discussed": "All essential references have been covered.", "other_strengths_and_weaknesses": "Other strengths: This paper is well-written and well-organized. The gentle start is very helpful for understanding the main result of this paper.", "other_comments_or_suggestions": "I may suggest the author to submit work similar to this submission to top-tier journals instead of conferences.", "questions_for_authors": "I have to admit that I didn't fully understand the whole picture of the proof. Even worse: I cannot tell if it is because the author didn't make this part clear or it is because I lack sufficient backgrounds in understanding the proof. If possible, I may hope the author could clarify several points:\n\n1. The beginning part of Section 4 Analysis and results (more explicitly, everything before Theorem 1) seems to be some introduction and definitions of mathematical notations. They don't describe how to prove Theorem 1. Do I understand it correctly? \n\n2. From my perspective, even if I know how these notations are defined, it is still hard to understand how the bounds in Theorem 1 are obtained. There is a large gap between knowing the proof technique and knowing how to prove it. Therefore, I may expect the author to include a brief proof sketch.\n\n3. Does this work assume the number of critical sets is finite? On page 6, the vertices have the maximum number $N_{\\text{all}}$. Is it possible to have infinite critical sets, e.g. $f(x) = \\sin x$? \n\n4. How should I understand Theorem 2? Does it simply take $x$ as a specific point $p$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HV0CG4KyxP", "reviewer": "Reviewer_WEdV", "summary": "This paper investigates the time required for SGD to attain the global minimum of a general, non-convex loss function. The authors approach this problem using large deviations theory and randomly perturbed dynamical systems and offer a exact characterization of SGD's hitting times with matching upper and lower bounds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your input and your assessment that \"the idea of analyzing the hitting time on the set of minimizers is novel\". We reply to your questions and remarks below, and we will of course integrate this discussion in the paper at the first revision opportunity.\n\n- **Practrical relevance of the energy.**  First, we should emphasize that, unlike standard results on the convergence rate of SGD to criticality, our result is not an upper bound but a characterization, valid up to a prescribed tolerance level. In particular, the energy describes exactly which features of the loss landscape and the statistics of the noise end up affecting the convergence time of SGD, and in what way.\n\n  In terms of concrete take-aways, the results of Section 4 and the \"deep-dive\" of Section 5 show that the convergence time of SGD is exponential in a) the inverse of the step-size; b) the variance of the noise; and c) the depth of any spurious minima of $f$. Among others, this has explicit ramifications for (overparameterized) neural nets: in order to escape the exponential regime, the depth of spurious minimizers must scale logarithmically in the dimension of the problem; in turn, by known structural bounds on the loss surfaces of neural nets (such as the works we mention in at the end of section 5 and the works of Ben-Arous and co-authors), it is possible to estimate precisely the depth (or width, depending on the model) of a neural net required to attain the \"shallow spurious minima\" regime, which in turn would guarantee subexponential global convergence times.\n\n  Finally, from a broader theoretical perspective, we believe that the value of our results for the ML community goes beyond the explicit energy characterization of the global convergence time of SGD. Our analysis provides a toolbox for the analysis of a wide range of stochastic gradient-based algorithms, and is, in a sense, the first step through the door to obtain similar results for, say, SGD with oscillatory learning rate schedules, Adam, etc.\n\n- **Explicit computation of the energy.** We provide a series of explicit expressions and approximations for the energy in Section 5 (this is how we derived the concrete expression in Section 2). It is true that the current version of Section 5 is somewhat \"crammed\", but we would be happy to take advantage of the extra page to extend and enrich it at the first revision opportunity.\n\n  Incidentally, to showcase the tightness of our analysis, we used the rebuttal period to perform a series of numerical experiments on some standard global optimization benchmarks, which show an exceedingly good fit between theory and practice, see anonymized link [here](https://tinyurl.com/2k5ay5c6).\n\n- **Comparison to existing bounds.** We are not aware of any bounds in the literature (upper or lower) providing even an estimate regarding the global convergence time of SGD in bona fide non-convex objectives. Reviewer U6wN echoes this, as they state that \"the results and developed mathematical tools presented in this paper is completely new\". Do you have a specific reference in mind? If so, we would be happy to discuss and position it accordingly.\n\n- **Implications from lower bounds.** The example provided in Section 2 already provides such an implication: even though the \"obstacle gap\" $f(p_2) - f(p_5)$ is not encountered on the shortest path toward the global minimum of $f$, it is what controls the speed and efficiency of learning in this case. Thus, a slight increase this gap would end up having an exponential impact on the global convergence time of SGD, indicating the difficult of learning even in this simple example.\n\n---\nWe thank you again for your time, and we look forward to an open-minded discussion during the rebuttal phase.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "Yes. This is a theoretical paper and all of its claims are proved.", "methods_and_evaluation_criteria": "N.A", "theoretical_claims": "No. I focused on reading the main text.", "experimental_designs_or_analyses": "No. I focused on reading the main text.", "relation_to_broader_scientific_literature": "This paper characterizes the performance of SGD on general non-convex functions, a widely studied setting. The analysis relies on treating the training process as a dynamical system, a commonly used approach. However, to the best of my knowledge, the idea of analyzing the \"hitting time\" on the set of minimizers is novel.", "essential_references_not_discussed": "See weeknesses.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written, clear, and conceptually sound.\n2. The idea of interpreting the convergence rate of SGD as the hitting time of a dynamical system reaching the set of global minimizers is both novel and interesting.\n\nWeaknesses and Suggestions for Improvement:\n\nMy primary concern lies with the main result of the paper. The characterization of SGD's convergence time is based on the notion of energy, which quantifies the difficulty of reaching the minimizer set from the initialization. However, it is unclear whether bounding convergence by energy provides meaningful insights or practical improvements in understanding SGD's behavior.\n\nCan the authors address the following points:\n\nPractical Relevance of Energy – Are there cases where the energy can be explicitly computed and shown to be useful for improving training? Any theoretical or empirical exploration of this aspect would be valuable.\n\nComparison to Existing Bounds – Are there scenarios where your bound leads to an improvement over known convergence bounds for SGD? Providing such cases would clarify the significance of the result.\n\nImplications for Lower Bounds – In the context of lower bounds, can you identify cases where your analysis proves that learning is inherently difficult? Establishing such results would strengthen the theoretical contribution.\n\nAddressing these points would help clarify the practical and theoretical impact of your results.", "other_comments_or_suggestions": "See weaknesses.", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wSXJyakq30", "reviewer": "Reviewer_Qj72", "summary": "The paper studies the global convergence time of stochastic gradient descent (SGD) in non-convex optimisation landscapes. By employing tools of large deviation theory and randomly perturbed dynamical systems, the authors provide upper and lower bounds on the global convergence time. These bounds are dominated by the most costly paths (in the sense of an energy function depending on the global geometry of the landscape and on the initialisation of the algorithm) the algorithm might take in the loss landscape.\n\n\n**Update after rebuttal**\n\nI thank the authors for the detailed response. I consider the paper a solid and relevant contribution, so I recommend its acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time, input, and positive evaluation! We reply to your remarks and questions below:\n\n- **Use of other benchmarks.** Sure thing! We took advantage of the rebuttal period to run numerical experiments on three standard non-convex benchmarks: the three-humped camel benchmark (already mentioned in the paper), Styblinski-Tang, and the Himmelblau example that you suggested. In all examples, we computed the various energy barriers exactly, and our experiments showed an exceedingly good fit between theory and practice, cf. the anonymized link [here](https://tinyurl.com/2k5ay5c6).\n\n- **The precise meaning of \"small enough\".** We mean here that there exists some constant, positive $\\eta_0$, depending on $\\varepsilon$ and the characteristics of SGD via $f$ and $Z$, such that the statement of the theorem is valid for all $\\eta ≤ \\eta_0$. Our proofs yield an explicit constructive estimate for $\\eta_0$, which means that one could, in principle, exhibit the explicit dependence of \"small enough\" on $\\epsilon$ and and $f, Z$. However, the resulting expression is the composition of several intermediate expressions, bounds and estimates, making it rather unwieldy to present (especially as it depends on certain quantities that are introduced and analyzed in the appendix). For this reason, we did not include a more precise description in the main part of the paper; nonetheless, it is worth noting that our simulations show an excellent fit between theory and practice for standard step-size parameter ranges (between 10E-2 and 10E-4). We will make sure to take advantage of the extra page to explain this at the first revision opportunity.\n \n- **Escape times and Mori et al (2022).**  Excellent question, thanks for giving us the opportunity to discuss this. In fact, a simple way to see that escape times are not enough to obtain the global convergence time of SGD is already given by our introductory example in Section 3. Indeed, in this case, the escape time of $p_3$ would scale exponentially in $f(p_2) - f(p_3)$ (the depth of $p_3$) while the escape time of $p_5$ would scale exponentially in $f(p_4)  - f(p_5)$. However, the global convergence time of SGD as determined by (4) is greater than either of these two exponentials: indeed, our result takes into account that, when in the vicinity of $p_3$, SGD could transition to $p_5$ instead of $p_1$ an arbitrary number of times. Hence, characterizing escape times is not enough to describe the global convergence time of SGD in general.\n\n  Finally, regarding on the modelling of the noise by [Mori et al. 2022]: under their noise model, our general framework of assumptions 7-8 and 11 allow us to obtain analogues of Thm.3 that depend on logarithmic barriers instead of linear barriers.\n\n- **On Assumption 2(c).** In our generic bounds (Thm. 1-2), the global convergence time depends on the dependence of the noise with $x$ because the computation of the energy involves the Hamiltation $\\mathcal{H}_G(x, \\omega)$, which fully characterizes how the noise distribution depends on $x$. It is true that, in Section 5, for simplicity, we consider bounds which are relevant when $\\underline{\\sigma} \\approx \\bar{\\sigma}$, i.e. when the magnitude of the noise is roughly constant. That being said, as mentionned above, our framework of Section 5 encompasses the noise model of [Mori et al. 2022] for Gaussian noise with variance $\\sigma^2(f(x)) \\propto f(x)$, we will make this clear in the revision.\n \n- **On Assumption 4.** Indeed, if one considers Assumptions 7-8 instead of Assumption 2(c), Assumption 4 becomes (E.1) in Assumption 11 in Section E.11, where $\\underline{\\sigma}$ now depends on $f(x)$. We will provide a reference to this assumption in Appendix B.1 for clarity.\n\n---\nWe thank you again for your constructive input and positive evaluation, and we look forward to any other comments you may have during the rebuttal phase.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "Although I have not checked the proofs in details, the claims are made based on well-established methods in the literature. Additionally, the authors provide a qualitative verification of their results using the three-hump camel function. Perhaps other benchmark functions like the Himmelblau function could be used to further validate the results", "methods_and_evaluation_criteria": "The authors make use of large deviation theory and randomly perturbed dynamical systems to provide bounds on the global convergence time of SGD. These methods have become popular within the machine learning community to study the convergence of stochastic optimisation algorithms and are well-suited for the problem at hand. The authors also provide a qualitative verification of their results using the three-hump camel function.", "theoretical_claims": "I have not checked the proofs in detail.", "experimental_designs_or_analyses": "Since the result is a bound on the global convergence time, there is not a direct experimental way to validate the result. Nevertheless, the authors provide a qualitative verification using the three-hump camel function. In Fig. 1, it is clear that the algorithm spends most of the time around critical points, which is consistent with the main result of the paper.", "relation_to_broader_scientific_literature": "The paper is well-positioned within the broader scientific literature. The authors provide a comprehensive review of the related work, citing not only closely related papers but also works that are more tangentially related.", "essential_references_not_discussed": "The related literature is well-cited.", "other_strengths_and_weaknesses": "Strengths:\n\n1) The paper is well-written and discusses the results in a clear and concise manner.\n2) It addresses an important problem in the field of optimisation and machine learning and uses well-established methods to provide bounds on the global convergence time of SGD.\n\nWeaknesses:\n\n1) See questions for authors below.", "other_comments_or_suggestions": "I have not found any typos in the paper.", "questions_for_authors": "1)  Both Theorems 1 and 2 are valid under the conditions that the learning rate $\\eta$ should be \"small enough\". What exactly do the authors mean by that? I believe this information is given in the appendices, which, unfortunately, I could not go through. In any case, why not precisely state in the main text how small the learning rate should be?\n\n2) In Appendix A3, the diffusion approximation studying escaping from minima of [Mori et al. 2022] is cited. Assuming the system takes more time to escape from minima than from saddle points, I would expect somehow the global convergence time to be dominated by the time to escape from minima ([Mori et al. 2022] claims one should consider a log exponential barrier between minima and saddle instead of a linear barrier). Could the authors please comment on this? Clarifying if they see any connection between their work and the results of [Mori et al. 2022] would be very interesting.\n    \n3) Assumption 2(c) provides a bound that does not depend on $x$. Nevertheless, in Assumptions 7-8, the authors relax this assumption, letting the bound depend on $f(x)$. So, the general picture related to the global convergence time does not crucially depend on the dependence of the noise with $x$? I ask because one of the big challenges in studying the effects of noise in SGD throughout the optimisation dynamics is how to deal with the dependence of the noise on the current iterate. \n\n4) Does Assumption 4 change if one considers Assumptions 7-8 instead of Assumptions 2(c)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper analyzes the time required for the global convergence of SGD under general non-convex functions. The main result provides a bound on the hitting time, indicating the time needed to reach the set of minima. The proof techniques rely on large deviation theory and the dynamical system theory of random perturbations. While many components are relatively standard, the proofs are generally well-written and easy to follow.

The reviewers raised several questions regarding presentation and clarity, but no critical technical flaws were identified. Although the novelty of the proof techniques remains somewhat unclear, the overall explanations are careful and have been evaluated positively by the reviewers on average. Furthermore, the authors' responses were clear and facilitated good communication throughout the review process.
Decision: Accept (poster)