Nesterov acceleration in benignly non-convex landscapes

We thank the reviewer for their service. Unfortunately, neither of their main claims and criticisms of our work is correct.

Aujol et al. (2022) make significantly stronger assumptions:

1. In the continuous time setting (Section 3), the authors assume that "$F:\mathbb R^n \to \mathbb R$ is a differentiable convex function admitting a unique minimizer $x^*$. Assume that $F$ is additionally quasi-strongly convex." (emphasis ours) All results in continuous time assume that $F$ has a unique minimizer. Our assumptions do not imply either convexity or uniqueness of minimizers, as also demonstrated by the examples in our Section 2.
2. In the discrete time setting (Section 4), they assume that $F$ is not just quasi-strongly convex, but in fact $\mu$-strongly convex. This, of course, does not imply any of the results proved in our work, where the focus is relaxing the assumptions on the objective function.
3. Aujol et al. do not consider the stochastic setting at all. A major part of our analysis is not considered in this work.

Needless to say, this setting is significantly simpler and needs none of the innovations in our proofs which address tangential movement along the set of minimizers.

These distinctions are not mere technicalities: In overparametrized machine learning, the minimizer is never unique, and deterministic optimization is rarely used. The claim that "all of the theoretical contributions presented by the authors already exist in the literature" is wildly inaccurate. At the very least, the reference cited by the reviewer does not support their claim. If there are other relevant works which we missed, we are grateful for further feedback.

• We understand the reviewers confusion about Nesterov’s method and heavy ball momentum. Yurii Nesterov has introduced several algorithms in optimization theory. The algorithm we analyze is, in the deterministic setting, a reparametrization of the one introduced in "A Method for Solving the Convex Programming Problem with Convergence Rate $O(1/k^2)$" in 1982 (up to a different choice of the factor which in Nesterov’s original work is denoted by $(a_k-1)/ a_{k+1}$, which is standard in the strongly convex setting). The equivalence between the time stepping scheme that we use and the standard version of Nesterov's method is proved in Appendix B of the work of Gupta et al. (2023) cited in our bibliography.

  The heavy ball discretization indeed looks very similar to this parametrization of Nesterov’s algorithm, but they are different. As noted by Sutskever et al. "On the importance of initialization and momentum in deep learning" (2013), the only difference between the two methods is the point at which the gradient is evaluated. While the heavy ball method uses gradients at $x_n$, Nesterov's method uses gradients evaluated at $x'_n = x_n + \rho v_n$. We make use of the latter in our work.

We will be very happy to engage in further discussion, but we maintain that the reviewer's characterization of our contribution and comparison with Convergence Rates of the Heavy Ball Method for Quasi-Strongly Convex Optimization by Aujol et al. is highly inaccurate.

Thank you for you effort for improving the paper. I mostly agree with your points from the general response:

• You work essentially extends the literature on convergence guarantees of heavy ball/nesterov for beningly convex functions. You present techniques to improve existing results such as the one of Aujol et al., and to manage non-isolated minima under geometric assumptions.

• The connection with deep learning is not central, and is mostly supported by the literature on overparameterized models (in particular in Cooper).

I'm still not satisfied with the current redaction. It really has to be improved:

• The introduction still need to be polished. I believe the main elements which have to be exposed there are: (i) your motivations in deep learning; which is mainly the connection with overparameterized models, and (ii) a clear literature review of convergence guarantees under weak convexity assumptions (nonuniquess of minimizers etc). But the reading I have of your current introduction looks like this:

• Accelerated methods in deep learning
• PL condition
• NTK
• Hessian eigen values
• Gradient method (with a reference to Cauchy)
• Nonsmooth optimization (with FISTA)
• Then, heavy ball in deep learning again
• KL inequality, with only one recent reference from 2023
• A small mention to time discretization but with no further explanation
• strong quasar convexity
• Implicit bias in deep learning
• Your contributions, with the first mention of "overparameterized models", and also this strange mention of the Hessian eigenvalues...

• Sometimes your language is overblown:

In general deep learning applications, the set of minimizers of the loss function is a (generally curved) manifold

"Deep learning applications" is wide... Can you claim this any model?

We have proved that first order momentum-based methods accelerate convergence in a much more general setting than convex optimization

This sentence is too general while your work focuses on particular notions of weak convexity, and a specific landscape geometry.

with many geometric features motivated by realistic loss landscapes in deep learning

This is overblown. As you admit in your general comment, some works on overparameterized neural networks may motivate the use of such geometric features but the word "realistic" seems too much to me.

• I would have preferred more insights into the proof techniques in the main paper. You mention that the main difficulty lies in controlling the "tangential motion" (I don't even know what it is precisely) but you do not explain how this is achieved or how it connects with the assumptions. I believe your proof techniques could contribute to the ML/optimization community from a theoretical perspective (more than your deep learning illustrations). However, the current presentation makes them difficult to access.

Overall, the paper contains new contributions for the convergence theory. Thus I raise my score to 6 but I urge the authors to work on the redaction for the future version.

To the best of my knowledge, both from theoretical and practical perspectives, the momentum methods commonly used in deep learning are based on the Polyak Heavy-ball method, not Nesterov acceleration. […] Could the author carefully provide sufficient references to support this motivation?

Theoretical guarantees for heavy ball momentum are very weak compared to Nesterov momentum, even in the setting of convex optimization. Popular machine learning libraries like PyTorch and TensorFlow include easy options to to use either Nesterov or heavy ball momentum in their SGD optimizer. In On the importance of initialization and momentum in deep learning (ICML 2013), Sutskever et al. study both heavy ball and Nesterov momentum and highlight situations where latter is more effective than the former. Other works suggest that using Nesterov momentum with adaptive optimizers may indeed lead to superior performance (e.g. Dozat: Incorporating Nesterov Momentum into Adam (2016), Xie et al: Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models (2024)).

We take a broad view of the role of optimization theory for machine learning, where we consider not only the currently dominant paradigm, but also emerging techniques which may evolve into dominant narratives in the future.

The main contributions of the paper in comparison with related references is unclear. Could you state them more explicitly, discuss them in greater detail?

We will be happy to expand the literature review in a revised version. The main novelty of our analysis is the extension to a setting where minimizers are not unique and where movement tangential to the set of minimizers has to be carefully considered (as is the case in overparametrized deep learning).

For example, a unified convergence analysis for momentum algorithms has already been considered in Josz et al.

We are grateful to the reviewers for pointing us towards this reference. We will include in in the literature review in a revised version of the article. To us, the main differences between the articles are:

• We make more restrictive geometric assumptions, but obtain a stronger result (see also the next point).

• We include an analysis of a broad stochastic setting with state-dependent noise. Stochastic variations of the analysis are listed as future directions in the work of Josz et al.

Recent works, such as Josz et al. mentioned above, require only the KL inequality, which holds for a significantly larger class of functions encountered frequently.

Josz et al. prove convergence to a local minimizer under certain mild regularity conditions. We make stronger geometric assumptions and obtain stronger quantitative guarantees on the speed of convergence. In particular, we obtain an ‘accelerated’ rate of convergence. As Yue et al. (2023, details in bibliography) prove, no such guarantee can be found under weaker assumptions such as the PL condition.

If the continuous-time analysis can be directly applied to derive results for discrete time, its inclusion is entirely appropriate.

The proofs in discrete time are more technical variations of proofs in continuous time. We include them to provide geometric intuition and illustrate the important ideas in a simpler setting. Using continuous time differential equations to gain insight into the behavior of and develop methods of analysis for discrete time algorithms is well-established and has led to tremendous progress following e.g. the highly influential work of Su et al. A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights (NeurIPS 2014, JMLR 2016).

Additionally, the results obtained in continuous time are stronger in terms of the geometry. In the current work, we decided to extend the results towards the stochastic direction rather than full geometric generality. Nevertheless, we believe that the continuous time analysis illustrates other directions in which our results can presumably be extended in future work.

The numerical experiments are too simple

The goal of the current work is to propose an appropriate setting for the analysis of certain momentum-based optimization algorithms that are already being used in deep learning sucessfully, albeit without convergence guarantees. We do not propose any new algorithms but provide theoretical guarantees for existing ones with significantly weaker assumptions. Numerical experiments would mostly recreate well-known results and were not deemed a priority. This is particularly true for Nesterov’s algorithm, which has been used for neural network training for over a decade.

In the AGNES setting, admittedly, numerical studies are scarcer, and the image classification experiments of Gupta et al. do not match theoretical assumptions precisely. We would be happy to include further experiments in different settings where MSE loss is common, such as regression or the training of neural PDE solvers.

Dear Reviewer 4krH,

The author discussion phase will be ending soon. The authors have provided detailed responses. Could you please reply to the authors with whether they have addressed your concern and whether you will keep or modify your assessment on this submission?

Thanks.

We thank the reviewer for their kind and helpful feedback.

the paper does not seem to have many novel technical contributions compared with existing works on ODE modeling of optimization algorithms

There are parts of the article where new ideas are required for the ODE section (Lemma 1, and in the proof of the global convergence result of Lemma 8), but we agree that the main innovation is based on novel geometric insight, not the technical tools used for the analysis. The proofs in discrete time (Theorems 11, 13, 14 and 15) also build on top of existing proof ideas, but are more challenging. They require a much more careful analysis of terms because we need to handle the tangential and normal components of the velocity and the gradients separately.

We thank the reviewer for their kind and helpful feedback.

I'm not sure to what degree the proof of Theorem 7 requires novel techniques.

The proof of Theorem 7 combines two main points:

• The trajectory of $x(t)$ remains in a good neighborhood of minimizers. This is achieved by energy estimates.
• A modified total energy is decreasing. This mimics existing proofs using Lyapunov functions, but requires greater care since a 'base point' in the construction of the Lyapunov function is moving. Lemma 1 is needed to address this.

As such, the proof of Theorem 7 does not require the development of novel tools so much as new geometric insight to combine known arguments. The proofs of Theorems 11, 13, 14 and 15 (i.e. in the discrete time setting ) are more challenging. They require a much more careful analysis of terms because we need to handle the tangential and normal components of the velocity and the gradients separately.

Do you believe that similar ideas could be used for non-smooth objectives in future work

The reviewer raises an interesting question. We require control of the Lipschitz constant of the gradient in two places:

1. To bound the error in a gradient descent step. For non-smooth convex optimization, it is in places possible to circumvent this control at the cost of slower rates of convergence or without deterioration by selecting a partially implicit time stepping scheme (like FISTA, which treats part of the gradient implicitly). Intuitively, we see no obstructions to mimicking either one.

2. To track how the objective function $f$ changes in the momentum step. Here, only a lower bound on the eigenvalues of $D^2 f$ is required, and an assumption of the nature that $f(x) + \frac {\epsilon}2 \|x\|^2$ is convex may be sufficient here. We do not believe that a geometric assumption of this form can be removed entirely, but smoothness may not be needed.

For a neural network with a single hidden layer $f_{(a,W)} (x) = \sum_{i=1}^n a_i\sigma(w_i^Tx)$ and the loss function $L(a, W) = | f_{(a,W)}(x) - y|^2$ with a single given data/label pair $(x,y)$, we find that $\nabla_{W} L = 2 (f_{(a,W)}(x) - y) \nabla_W f_{(a,W)}(x)$ and $D^2_W L = 2 (f_{(a,W)}(x) - y) D^2_W f_{(a,W)}(x) + 2 \nabla_W f_{(a,W)}(x) \otimes \nabla_W f_{(a,W)}(x)$.

The second term in the sum is a non-negative semi-definite symmetric rank one tensor and therefore unproblematic. Since $f$ is non-linear in $W$, the Hessian $D^2_Wf$ is non-zero (a measure, if $\sigma$ is ReLU), and in general, the first term may be indefinite. If we choose $y$ adversarially, we can guarantee that $D^2L$ has a large negative eigenvalue even for smooth activation. If $\sigma$ is ReLU, then $D^2_Wf$ is singular with respect to Lebesgue measure, so intuitively there will be an 'infinitely large negative eigenvalue' whenever $f(x)-y$ has the wrong sign, even in a neighborhood of the set of global minimizers.

Whether $L$ can be controlled locally in a sufficient manner, possibly under additional geometric assumptions, is an interesting question even in the shallow case, but beyond the scope of this work. We strongly believe that the results are relevant in a more general setting than we can guarantee at this point, and we believe that charting the borders of their validity is an exciting topic for future research.