Nesterov acceleration despite very noisy gradients

Summary

The paper studies the accelerated gradient method of Nesterov’s (NAG) for smooth and (strongly-)convex problems under the multiplicative noise model when the variance of the stochastic gradients behave as $O(\sigma^2 \| \nabla f(x) \|^2)$. The authors identify that the NAG in its original momentum formulation could tolerate multiplicative noise for $\sigma \in [0,1)$. They propose a modified version which uses 2 step size sequences for the update and momentum steps, respectively, which are a constant factor apart from each other, and prove that their method achieves the optimal rates for any positive value of $\sigma$ for general convex and strongly convex problems.

Strengths

**Clarity and Presentation**\ The manuscript identifies the key contributions in terms of the algorithmic design and explains how/why the particular parameter choices are necessary for the convergence with optimal rates. **Strengths**\ The authors identify the limits of NAG and propose an easy but nice fix to remedy the limitations under multiplicative noise. They are inspired by the continuous time aspect of NAG, similar to [Even et al., 2021] and [Liu and Belkin., 2018] but their modified construction of the Lyapunov function accommodates the 2 step-size-formulation they have. Looking at the analysis for NAG and AGNES, one could see that the separation in the second term of the Lyapunov function, i.e., $\| b(n) ( x’_n – x_n ) + a(n) ( x’_n – x^* ) \|^2$, enables to handle the multiplicative noise and the 2 step size structure at the same time. This is a simple fix, but it proves to be useful. To my knowledge, this is the first work that successful studies the general convex and strongly-convex functions under multiplicative noise and proves optimal bounds. I find the results and the simplicity of the proposed method to be important.

Weaknesses

**Clarity and Presentation**\ I think it should be made clearer that the proposed method is as simple, modified version of NAG rather than a new framework as the only difference is using 2 step size sequences, which are only a multiplicative factor of $\frac{1}{1 + \sigma^2}$ apart from each other. **Weaknesses** The equivalence between [Liu & Belkin, 2018] makes me regards this work as a new analysis for an existing framework. They also have overlapping proof ideas with [Even at al., 2021] (use of continuous-time perspective, similar Lyapunov function constructions). Having that said, the authors seem to have identified correct modifications on the existing methodologies. I strongly suggest to include a dedicated section of comparison between the analysis techniques and explain their main strengths/contributions in accordance with the related work as it is not clear from the manuscript. The results for the general convex case is not too interesting in my opinion. The main reason is the existing work on adaptive methods, which essentially prove that $\sum_{i=1}^{n} a_i^2 \| \nabla f(x_i) \|^2 < O(LD^2) $, where $D$ is the diameter of bounded set of iterates. Please refer to [I - IV] for relevant results. I cannot say anything for sure before analyzing in details but looking at their proofs, it should be fairly possible for those methods to tolerate even to unknown values of $\sigma$ when $\mu = 0$. Note that most probably this would not be extended to strongly-convex problems. **References** [I] Levy, K.Y., Yurtsever, A., & Cevher, V. (2018). Online Adaptive Methods, Universality and Acceleration. ArXiv, abs/1809.02864. [II] Cutkosky, A.. (2019). Anytime Online-to-Batch, Optimism and Acceleration. *Proceedings of the 36th International Conference on Machine Learning*, in *Proceedings of Machine Learning Research* 97:1446-1454 Available from https://proceedings.mlr.press/v97/cutkosky19a.html. [III] Kavis, A., Levy, K.Y., Bach, F.R., & Cevher, V. (2019). UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization. Neural Information Processing Systems. [IV] Joulani, P., Raj, A., György, A., & Szepesvari, C. (2020). A simpler approach to accelerated optimization: iterative averaging meets optimism. International Conference on Machine Learning.

Questions

1. Could you please comment on other formulations of acceleration such as the optimal method in [V, Eq. (3.11)] and the method of similar triangles [VI]. Specifically, optimal method in [V] has a 2 step size formulation and it might already give the desired result for multiplicative noise. 2. In Figure 3, what happens to NAG when $\sigma = 0$? Please also include a case where $\sigma < 1$ to compare NAG and AGNES. 3. Could you elaborate on the contributions of your paper in terms of the theoretical analysis w.r.t. prior work? **References**\ [V] Nesterov, Y. (2005). Smooth minimization of non-smooth functions. Mathematical Programming, 103, 127-152. [VI] Gasnikov, A.V., Nesterov, Y.E. Universal Method for Stochastic Composite Optimization Problems. Comput. Math. and Math. Phys. 58, 48–64 (2018). https://doi.org/10.1134/S0965542518010050

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

I would suggest the authors to move the Appendix B.2 to the main text and discuss the equivalence to the prior work clearly.

Summary

This paper presents a new accelerated gradient method for smooth (possibly strongly) convex functions. It is assumed that the available gradients are noisy, where the noise level is proportional to the norm of the gradient. The authors show that Nesterov's accelerated gradient method (NAG) will converge in this setting when the constant of proportionality for the noise level is less than 1, but will diverge otherwise. To remedy this, the authors present the Accelerated Gradient descent with Noisy EStimators (AGNES) scheme. AGNES employs an additional parameter $\alpha$ in the momentum step, and show that if $\eta = \alpha$ (where $\eta$ is the step size for NAG), then NAG is equivalent to AGNES. Theoretical guarantees are presented to show that AGNES converges in the convex case, and at a better rate in the strongly convex case. Due to the noise in the gradients, the theoretical results hold in expectation, and the authors also show almost sure convergence in Corollary 5. Numerical experiments are also presented to support their findings.

Strengths

Writing. The paper was well written and presented. Clear motivation for the new algorithm was given, as well as a comparison with other results in the literature to put this work in context. I enjoyed reading it. Contribution. Problems where one encounters noisy gradients are abundant in the literature, so new algorithms for such tasks are welcome. The algorithm is conceptually simple, with few parameters to tune, and theoretical results guarantee convergence. Numerical experiments. The algorithm is supported by numerical experiments, which show the practical behavior of AGNES, and support the findings of the paper.

Weaknesses

Personally, I would have preferred if the authors had used different notation. For example, in (1), there are two sequences of points, $\{x_n\}$ and $\{x_n'\}$. But then, the authors use the notation $g_n = g(x_n',\omega_n)$, i.e., the gradient estimate does not have a prime, but it is associated with the sequence $x_n'$ involving a prime. I found it a bit jarring to read. To be honest, it probably would be even better to have used different letters to denote the two sequences, rather than a prime. I know it is hard to write in this style where a lot of important information needs to be put off until the appendix. However, in this case, it might have been an idea to have included the Literature Review (Appendix C) in the main body of the paper, and then taken out some of the length in the numerical experiments section (and put it in the appendix) to balance it out to 9 pages. Both of these are personal preferences for the authors to take note of (I am not asking them to do anything here).

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A

Summary

This paper proposes an accelerated gradient method which is applicable in stochastic convex optimisation with unbiased but highly noised estimator. The method is analysed in a continuous-time convergence framework. Special attention is paid to the application of the method in machine learning, corresponding numerical experiments were carried out which confirm the advantage of the proposed method over some other ones, including classical Nesterov's accelerated method.

Strengths

The proposed method is indeed a good alternative to a classical NAG method when some simple problem statements are considered, which is the case in the problems chosen for practical evaluation. The analysis in continuous-time fashion seems unnecessary here, yet convenient to proof the results shortly and clearly. Most of minor technical details are clarified in appendices.

Weaknesses

The language requires proof-reading, at least with an automated tool, and should be made more formal. The same recommendation is regarding the mathematical expressions: text takes several liberties here and there, i.e. uses not introduced notions without purpose, applies same-called functions to differently typed arguments, exploits x* for convex functions which are not guaranteed to reach its inf, etc. which makes an impression of that of informal draft, that I believe can be altered, taking into account that no significant details remain unclarified after reading the appendices. Similarly for numerical experiments: std-shadows are not added to some of the plots in stochastic experiments, axes are not labelled, etc. Besides, text contains many remarks on physical meaning, or on qualitative comparison of the proposed method with classical ones, which are so unclear that contribute nothing to understanding, but shift focus from the factual results. To summarise, text is far from being publishable.

Questions

Contribution of the paper is not clear. Since we expect that paper contributes either to theory or to practice, I try to find if it does. In theory, it does not make exhaustive literature review (arxiv:2307.01497 is ignored, for example; the only comparision of theoretical guarantees were given on Figure 1 with SGD) which is expectable when yet another accelerated method is proposed, competes with only SGD and NAG, i.e. the simplest methods, does not consider any structured optimisation settings and does not provide some generalizable analysis with any new techniques, but only uses some known tools to show the noise-robustness in the simplest setting, again without comparing their results with the literature on optimisation with state-dependent noise. In practice, it looks better when comparison is carried out on not-toy examples like image classification, but achieved improvement does not look significant in comparison to Adam, and its advantage is still confirmed by few simple problems, which does not convince a practitioner that method worth utilisation. Thus, this method does not seem helpful to the community, at least through its presentation in this text.

Rating

3

Confidence

4

Soundness

3

Presentation

1

Contribution

2

Limitations

The limitations are clear from reading.

Summary

This paper introduces and studies AGNES (Accelerated Gradient Descent with Noisy Estimators), a generalization of Nesterov's accelerated gradient (NAG) descent algorithm. First they show that NAG's guarantees break in the high noise regime. Then they prove that AGNES can accelerate gradient descent at any noise scale in smooth convex and strongly convex minimization tasks. The paper also provides empirical evidence arguing AGNES's improved performance over existing methods in various settings such as ImageNet.

Strengths

The strongest aspect of their paper is theoretical result. The fact that they only require two parameters will make it easier to apply to practical applications and also it leads to lesser space usage then Vaswani et al.

Weaknesses

The optimizer comparison is done on small datasets and even then not done well since the authors either do not sweep over hyperaprameters such as learning rate or sweep with a large factor such as 10. This reduces the certainty of the claim that AGNES outperforms NAG in the high noise regime for deep learning.

Questions

1. As the authors mentioned their algorithm is equivalent to a reparameterization of previous algorithms such as that in Liu and Belkin and also I believe the one in https://arxiv.org/abs/1803.05591. This should be highlighted more since currently the paper is written as presenting a new algorithm rather than presenting a better analysis. 2. Could the authors either add more sweeps over hyperparameters or add these limitations to the empirical claims (such as in Contribution 5)? I would be happy to increase my rating if the authors could answer the above queries. [Addressed]

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

Yes.

Summary

This paper introduces ``Accelerated Gradient Descent with Noisy Estimators" (AGNES), a variant of Nesterov's accelerated gradient descent (NAG), and proves that AGNES achieves an accelerated convergence rate regardless of the noise level relative to the gradient in both convex and strongly convex cases. Additionally, experimental results validate the effectiveness of AGNES.

Strengths

It is impressive that a simple modification of NAG results in a robust theoretical convergence in stochastic settings. The theoretical analysis, including continuous analysis, seems consistent, and the experimental studies are detailed, particularly in the context of deep learning

Weaknesses

I wonder if AGNES is truly novel. In lines 34 to 36, the authors state, ``In this work, we demonstrate that it is possible to achieve the same theoretical guarantees as Vaswani et al. [2019] with a simpler scheme, which can be considered as a reparametrized version of Liu and Belkin [2018]’s Momentum-Added Stochastic Solver (MaSS) method''. Does this imply that AGNES is essentially the same as MaSS or other previously suggested algorithms? Please clarify this point.

Questions

Are Theorem 1 and 2 new theoretical results or just induced by prior works? I recommend to cite `Continuous-Time Analysis of AGM via Conservation Laws in Dilated Coordinate Systems. J. J. Suh, G. Roh, and E. K. Ryu' as the reference of continuous analysis of NAG type algorithm. Could the convergence result in Theorem 3 and 4 extend to the expectation of gradient norm? The fifth line of the caption in Figure 6 needs spacing.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes, the authors addressed the limitations.

Reponse to Authors.

Thank you for the additional experiments. I am assuming that the authors will add limitations re "happy to acknowledge the limitations of our experimental section" in the final version. I will increase my score.

Official Comment by Reviewer e67y

Thank you for your responses. **Convex case and adaptive methods**\ Let me try to explain what I had in mind with more details. First, I do not suggest such methods are better suited for this problem; I can see how their analysis techniques are suitable for handling multiplicative noise. In the proof of adaptive methods, one cannot guarantee descent each iteration unless the method is equipped with linesearch. Therefore, the main strategy is to prove that cumulative error of not knowing the true Lipschitz constant will be bounded by a constant that is guided by the initial step size, Lipschitz constant and the initial distance/bounded domain radius. At the end of the day, the effort of bounding this cumulative error is equivalent to showing that the adaptive step-size has a strictly positive limit and it is lower bounded by a large enough value. The step size is of the form: $$ \gamma_t = \frac{\gamma}{\sqrt{ \beta + \sum_{k=1}^{t} \alpha_k^2 \|\| \nabla f(\bar x_k) \|\|^2 }} $$ where $\gamma$ and $\beta$ are some initialization parameters, $\alpha_k$ is the averaging parameter that grows in the order of $O(k)$ and $\bar x_k$ is the weighted average of the sequence(s) generated by the algorithm with respect to the weights $\alpha_k$. Note that this step size is non-increasing and assume for simplicity that $\eta_t$ incorporates the knowledge of $L$ and $\mu$. Then, one could show that, under **unbounded** gradients, the step-size has a strictly positive limit, and the algorithm should converge at a rate of $O(1/T^2)$. This translates to showing that $\beta + \sum_{k=1}^{t} \alpha_k^2 \|\| \nabla f(\bar x_k) \|\|^2 \leq O(1)$. Multiplicative noise gives us a way to move from the noise vector to the full gradients. In its presence, the analysis will have an additional term of the form $\sigma^2 \sum_{t=1}^{T} \|\| \nabla f(x_t) \|\|^2$. The main upside is that this summation is in terms of the full gradient, but missing the scaling parameter which could be added to the expression by upper bounding it. Then, we will have two summation terms of the same form; one has a multiplicative constant that depends on $L$ (the original error term) and the other has the variance term $\sigma^2$. The proof needs additional steps to verify this logic, but I believe it is not too complicated. My point is not to downplay the results presented in this paper, but I would like to propose that there are multiple techniques that have the potential to achieve the accelerated rates under multiplicative variance. As I mentioned, this technique is not valid when we are aiming for a linear rate. Indeed, [Levy, 2017] has a result for (non-accelerated) adaptive methods for smooth and strongly convex problems. When the algorithm knows $L$ and $\mu$, it is possible to achieve (non-accelerated) linear rate, however, there is a multiplicative factor $T$, which also appears in the linear rate exponent. **References:** Levy, K. Y. Online to Offline Conversions, Universality and Adaptive Minibatch Sizes. NeurIPS 2017.