Nesterov acceleration in benignly non-convex landscapes

Authors: Kanan Gupta, Stephan Wojtowytsch
Primary area: optimization
Keywords: nonconvex optimization, stochastic optimization, stochastic acceleration, smooth convex optimization, deep learning, accelerated gradient descent

Abstract:
While momentum-based optimization algorithms are commonly used in the notoriously non-convex optimization problems of deep learning, their analysis has historically been restricted to the convex and strongly convex setting. In this article, we partially close this gap between theory and practice and demonstrate that virtually identical guarantees can be obtained in optimization problems with a 'benign' non-convexity. We show that these weaker geometric assumptions are well justified in overparametrized deep learning, at least locally. Variations of this result are obtained for a continuous time model of Nesterov's accelerated gradient descent algorithm (NAG), the classical discrete time version of NAG, and versions of NAG with stochastic gradient estimates with purely additive noise and with noise that exhibits both additive and multiplicative scaling.

Decision: accept (spotlight)
Reviewer scores: 8, 8, 5, 6

Reviews and discussion:
<thread>
creation date:
1729761796157

thread_type:
official_review

<thread_object>
creator: reviewer_cdrw

<content>
summary:
Motivated by nonconvexity of deep learning objectives, this paper studies the  heavy ball method under relaxed convexity assumptions. The continuous time, discrete time and stochastic algorithms are investigated. Some toy experiments are presented to illustrate how the convexity assumptions hold in practice.


------- AFTER REBUTTAL -------


**I raise my score to 6. The author(s) present interesting and sufficiently new contributions, but the paper needs strong revisions in terms of presentation and redaction.**

strengths:
Benign convexity of machine learning problems is an interesting direction in order to understand why gradient methods may converge well in practice.

weaknesses:
The author(s) confuse the assumptions used in the related work by Aujol et al., titled "Convergence Rates of the Heavy Ball Method for Quasi-Strongly Convex Optimization," published in SIAM Journal on Optimization in 2022.

In the introduction, the authors claim that "strong quasar-convexity" is used in Aujol et al. (2022). This condition appears to be stronger than the one used by the authors, referred to as Assumption 4, which the authors now describe as "strong convexity with respect to the closest minimizer."

**However, Aujol et al. (2022) already use Assumption 4.** Their assumption is not quasar-convexity, as mistakenly stated in the introduction, but rather strong convexity with respect to the projection onto the minimizing set, which corresponds to the closest minimizer (see equation (4) in Aujol et al., 2022). As a result, **all of the theoretical contributions presented by the authors already exist in the literature**. For example, Theorem 7 replicates the convergence rates from [Theorem 1, Aujol et al., 2022].

Furthermore, the authors conflate Nesterov's acceleration with the heavy ball method throughout the paper, although they are two distinct algorithms. **The paper focuses on the heavy ball method, not Nesterov's acceleration.**

questions:
I suggest the authors to better compare their work with the related works.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730492749745

thread_type:
official_review

<thread_object>
creator: reviewer_4krh

<content>
summary:
The paper presents convergence analysis of Nesterov Acceleration for nonconvex functions. Some (geometric) assumptions weaker than PL inequality are employed to derive convergence results for NAG.

strengths:
There are some works have been reviewed in the literature, both from the line of momentum algorithms, and the geometry of deep neural networks. The paper is well-organized.

weaknesses:
1. 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. However, the paper under review focuses more on Nesterov acceleration, while mentioning motivation from deep learning without any references. Could the author carefully provide sufficient references to support this motivation?

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

3. The paper lacks a thorough literature review. For example, a unified convergence analysis for momentum algorithms has already been considered in Josz et al. (https://epubs.siam.org/doi/abs/10.1137/23M1545720?journalCode=sjope8). Could the authors please address this paper carefully and consider the references therein to better position their contribution within the literature on Nesterov acceleration? 

4. The assumptions in Section 2.1 seem too strong, as they imply the PL inequality. 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.

5. What is the connection between your continuous-time and discrete-time analyses? While the discrete-time analysis is of primary interest, the purpose of including the continuous-time analysis is unclear, aside from serving as additional motivation. If the continuous-time analysis can be directly applied to derive results for discrete time, its inclusion is entirely appropriate. However, if it is independent of the discrete-time analysis, I do not think it should be included unless carefully justified.

6. The numerical experiments are too simple. Could you include additional experiments on practical classes of nonconvex functions, such as those commonly found in deep learning?

questions:
See weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730741878529

thread_type:
official_review

<thread_object>
creator: reviewer_jpmm

<content>
summary:
This paper studies the convergence rate of momentum-based optimization methods under more general conditions than (strong) convexity. Motivated by existing works, the authors assume a localized version of strong convexity that allows for multiple local minimizers. The authors provide examples of such objective functions and also show empirically that the assumption is reasonable in deep learning applications. By considering a continuous-time ODE, the authors characterize the behavior of momentum-based method and prove accelerated rate compared with standard GD. The setting of stochastic optimization is also considered as an extension.

strengths:
1. Overall I think this is a nice paper with interesting contributions to the optimization community. I like the writing style of this paper, especially for the concise introduction and discussions of relevant works.

2. This paper justifies the superiority of momentum methods under weaker assumptions than strong convexity. Moreover, the assumptions made in this paper are supported by empirical evidence.

weaknesses:
While I do not check all the proofs, the paper does not seem to have many novel technical contributions compared with existing works on ODE modeling of optimization algorithms. I'm not sure if this should be considered as a weakness, since the results themselves are interesting.

questions:
I do not have any questions for this work.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730835632049

thread_type:
official_review

<thread_object>
creator: reviewer_jze8

<content>
summary:
This paper presents an analysis of NAG that proves accelerated convergence rates in some non-convex scenarios, using assumptions on the loss function inspired by overparameterized deep learning. The authors analyze continuous time with deterministic gradients, discrete time with deterministic gradients, and discrete time with stochastic gradients (and multiplicative noise), showing accelerated convergence rate (better dependence on condition number) compared to gradient descent/gradient flow.

strengths:
1. The paper is very clearly written. Previous work is totally explained and the authors are very straightforward when describing their novel contribution (Lines 42-51 and Lines 106-107).
2. The convergence rates are a clear improvement upon previous work, which either achieves similar rates with stronger assumptions or achieves a non-accelerated rate for gradient flow under a similar setting as this work (aiming condition).
3. The authors are straightforward about the limitations of their work, which I appreciate. In Lines 253-260, they mention that their global assumption on the loss geometry can only be guaranteed locally. Still, it seems that the assumptions are weaker than previous works (e.g. quasar convexity), so I think that this is acceptable.

I want to mention to other reviewers/AC that I am not too familiar with this particular line of work, so I am slightly less confident about the technical contribution of this submission. However, according to my best judgement, the contribution seems worthy of publication.

weaknesses:
1. The assumptions are inspired by overparameterized deep learning, but are unlikely to be completely accurate. This authors already comment on one instance of this (Lines 253-260). Another instance is the requirement that the objective is $C^1$-smooth (Line 114), which is not satisfied by non-smooth activation functions. Still, the assumptions are weaker than previous work, and I believe these gaps are very non-trivial to address. This is a minor weakness compared to the strengths of the paper.

questions:
1. I'm not sure to what degree the proof of Theorem 7 requires novel techniques. The authors mention (Line 324) that their overall proof strategy is common, and the contribution comes from their Lemma 1. I am not too familiar with this line of work, so it is hard for me to judge the novelty and non-triviality of Lemma 1. Can you elaborate on the technical contribution of Lemma 1?
2. Do you believe that similar ideas could be used for non-smooth objectives in future work? For example, the objective function for training a ReLU network with squared loss is almost everywhere continuously differentiable, instead of continuously differentiable (as required by your assumption #1). Could this gap be addressed with the kind of techniques used in this paper, or might this setting require entirely an entirely different approach?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732944224304

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank all reviewers for their helpful feedback and for actively engaging in the author discussion period.

All reviewers agree that there are novel contributions in our work. Their main criticism is that we did not explain clearly enough what these contributions are in the original submission, and did not outline clearly enough differences from the existing literature. We address these criticisms in a revised submission (changes marked in blue in the document). We would also like to highlight that we made compare our assumptions and other notions like quasar-convexity, strong convexity, and the PL condition in Lemma 24 in Appendix C.

Additionally, some reviewers note that we do not support our geometric modelling choices with extensive numerical experiments. In response, we hold that

1. Our assumptions are well-motivated from theoretical predictions, and a similar framework has been studied e.g. by Rebjock and Boumal (2023). The simulations are merely meant as an illustrative proof of concept and should not be considered an integral part of this work. Our theoretical contributions stand on their own.

2. It is well-known that the minimizers of objective functions in over-parametrized learning are non-isolated, and that Hessian eigenvalues may be negative, even close to global minimizers. Our analysis is the first to address objective functions with non-isolated minimizers in a meaningful way for momentum-based optimization. We also give a precise quantification of the impact of the magnitude of negative eigenvalues by the parameter $\varepsilon>0$.

	Whether or not the simulations suggest that this is a fully realistic setting for optimization in deep learning, we claim that it is undebatably a significant step towards a realistic model. We conjecture that it remains simplified, but that it captures important features much more precisely than previous assumptions.

3. Finally, we are the first to analyze the impact of negative eigenvalues of the Hessian for accelerated rates in the context of *stochastic* optimization. Namely, we show that these are generally *not* the limiting factor on achieving fast convergence if the gradient oracle is reasonably noisy (in a precise way).

Our links to deep learning are heuristic, but not novel — indeed, it can be argued that the study of accelerated first order methods is largely motivated by the fact that these methods are highly popular in deep learning. The main contribution of our work is not on establishing such a connection, but on extending guarantees in optimization theory to a setting which we merely argue to be *closer* to deep learning than previous work in this direction. To emphasize that, we have also renamed Section 2.3 to "Connection to Deep Learning" in order to avoid giving the impression that we are claiming to offer new applications of these already existing methods.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates momentum-based optimization algorithms, such as Nesterov's accelerated gradient descent (NAG), under relaxed convexity assumptions inspired by the non-convexity of deep learning objectives. The analysis encompasses continuous-time models with deterministic gradients, discrete-time models with both deterministic and stochastic gradients, and cases where the noise exhibits additive and multiplicative scaling. These findings bridge the gap between theory and practice by extending momentum-based optimization guarantees to optimization problems with benign non-convexity.

The convergence rates achieved in this paper are an improvement over previous work, either matching rates under weaker assumptions or outperforming non-accelerated rates in similar settings. This paper justifies the superiority of momentum methods under relaxed convexity assumptions, which are supported by empirical evidence, and explores the intriguing concept of benign convexity to explain the practical effectiveness. These contributions represent a valuable addition to the optimization community.

The paper has several weaknesses, though many are minor compared to its strengths. The assumptions made may not fully reflect practical scenarios inspired by overparameterized deep learning. For instance, the requirement of smoothness excludes non-smooth activation functions, and the assumptions in Section 2.1 are criticized as overly strong, implying the PL inequality, whereas weaker conditions like the KL inequality are more broadly applicable. Additionally, the focus on Nesterov acceleration is questioned by one reviewer, as momentum methods commonly used in deep learning are often based on the heavy-ball method, and the paper lacks sufficient references to support its motivations. Also, the relationship between the continuous-time and discrete-time analyses is unclear, raising questions about the necessity of including the former unless its connection to the latter is better established.