The Global Convergence Time of Stochastic Gradient Descent in Non-Convex Landscapes: Sharp Estimates via Large Deviations

Thank you for your time, input, and positive evaluation! We reply to your remarks and questions below:

• 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.

• 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.

• 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.

  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.

• 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.

• 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.

We 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.

Kind regards,

The authors

Dear reviewer,

Thank 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.

• 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.

  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.

  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.

• 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.

  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.

• 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.

• 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.

We thank you again for your time, and we look forward to an open-minded discussion during the rebuttal phase.

Kind regards,

The authors

Dear reviewer,

Thank you for your time, input, positive evaluation and appreciation! We reply to your remarks and questions below:

• 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."

• 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.

  To lay the groundwork, we prepared a flowchart of the logical structure of the proof in the anonymized link here. In short, the main steps are as follows:

  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.
  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.
  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.
  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.

• 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.

• 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.

We thank you again for your time and positive evaluation! Please let us know if any of the above points is not sufficiently clear.

Kind regards,

The authors

Dear reviewer,

Thank 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.

• 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.

• 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).

• 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.

• 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 (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.

  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.

  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.

• 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.

• Statement of Theorem 1. Are you referring to the attracting strength? This is defined in (1), L242.

• 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.

• 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.

• On $\sigma_{\infty}$: Yes, this was supposed to be $\underline{\sigma}$, thanks!

Looking forward to a fruitful discussion! Regards,

The authors