Nesterov acceleration despite very noisy gradients

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.

We agree that a key point is that our method is a simple modification of NAG. We tried to highlight this in the abstract and will be happy to emphasize it more in the main text of a revised version of the paper.

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.

Thank you for this comment. We agree that our work should be regarded as a new analysis (and derivation) of the method of [Liu & Belkin, 2018]. In addition, the ideas behind the proof, in particular Lyapunov function arguments inspired by an analysis of the continuous dynamics, are fairly well-known in the optimization literature. We derived the method from our analysis of NAG independently and found the equivalence after the analysis was completed. The main novelty is a simple parametrization which simplifies the proofs of our main results (which are novel for this method).

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

Thank you for pointing out this literature, which we were previously not familiar with, and which we are planning to add to our literature review to include this work. Based upon our reading, this work is very extensive and covers the situations of online optimization and adaptivity with respect to the (additive) noise level $\sigma$ and the smoothness parameter $L$ (which may even be infinite for some results, assuming that the objective function is Lipschitz-continuous). The second case excludes for instance for strongly convex functions, since we have

$$f(x)\geq f(x^*) + \frac\mu2\|x-x^*\|^2,$$

i.e. the function grows quadratically at infinity. If the were Lipschitz-continuous, it could grow at most linearly. Many merely convex functions also grow faster than linearly at infinity.

Unbounded gradients particularly affect the multiplicative noise setting we consider: The multiplicative noise is our 'friend' close to the set of minimizers since it becomes small, but it is our 'enemy' at infinity since it becomes large and may send us in the wrong direction. In particular, we have no a priori bounds on the diameter of the trajectory or on the gradient estimates in $L^\infty$. The fact that we do not constrain the trajectory also allows us to formulate an result in the setting where the objective function does not have minimizers, in which case the optimizer trajectory has to diverge. It is not immediately apparent how the adaptive algorithms would fare in these situations as they have not been studied with multiplicatively scaling noise.

We agree that this is an important part of the literature and we will include a comparison to it in a revised version of the paper. Still, we believe that we contribute new results even in the convex case here.

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.

Again, we thank the reviewer for pointing out this work, which we were previously unaware of. Based upon our reading, the method in reference [V, Eq. (3.11)] is an optimal accelerated method in the plain convex (i.e. not strongly convex) case, which works even with a constraint (the convex set $Q$). Without further analysis, we do not know how this method will perform with multiplicative noise, but we believe that such an analysis will be too extensive to add to this paper and thus leave it to future work. We will certainly mention this work and its contribution to accelerated methods in the convex case in a revised version of the manuscript, however. We were also very intrigued by the method of similar triangles, which gives a nice way of deriving accelerated optimization methods for convex and strongly convex objectives that we were not aware of. However, we do not know how this method will generalize to the case of multiplicative noise without significant further analysis, which we again leave to future work. Of course, we will certainly mention the contributions of this paper in our revision.

We are grateful to the reviewer for their feedback and encouraging comments.

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 involving a prime.

We thank the reviewer for the good suggestion, and we agree that this would make the notation more consistent. We will be happy to replace $g_n$ with $g'_n$ for NAG and AGNES to make it clearer that those gradients are estimated at $x'_n$.

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.

We agree that the literature review being in the main body would help the readers put the current work in context of prior works. We will be happy use the additional content page that we would get, if accepted for publication, to move the literature review to the main body of the paper.

We are grateful to the reviewer for their helpful feedback.

The language requires proof-reading [...] and should be made more formal [...] To summarise, text is far from being publishable.

We understand that our presentation goes against the reviewer's stylistic preferences, and we are happy to integrate feedback into a revised version. To be sure, we would request more specific feedback about alterations the reviewer is suggesting. Since two other reviewers rated the presentation as '4: excellent', we are hesitant to consider changes without further clarification. We understand that this places additional strain on the reviewer's time, and we are very grateful for their service and the feedback they already provided.

text [...] exploits $x^*$ for convex functions which are not guaranteed to reach its inf

The existence of a minimizer $x^*$ is stated as part of the assumptions in Theorems 1 and 3. In fact, we study convex objective functions without minimizers in Theorem 7 (see also the paragraph above it). We are happy to rephrase the statement to emphasize this in a revised version.

If a minimizer does not exist, we do not expect that the algorithm would yield quantitative guarantees since even the 'heavy ball ODE' (deterministic, continuous time) can be arbitrarily slow due to Lemma 4.2 in [1] (see also lines 870-883 in Appendix F).

std-shadows are not added to some of the plots in stochastic experiments

The std-shadows are included in all experiments involving neural networks (albeit imperceptibly small in some plots compared to the oscillation of the trajectory which obscure them somewhat). They are not included in the plots for convex optimization since they made the plots less clear. Standard deviations were small and comparable for all methods considered. We did not find them to add much to the message: If $\mathbb E[f(x_n)] < \varepsilon$ for instance, then $f(x_n)< n\varepsilon$ with probability at least $1-1/n$ by Chebyshev's inequality, directly yielding bounds on $f(x_n)$ since $\mathbb E [f(x_n)] \to 0$ fairly quickly.

In theory, it does not make exhaustive literature review (arxiv:2307.01497 is ignored, for example

The literature review is in Appendix C. We would be very happy to move it to the main text in a revised version and dedicate the additional text page to it. In a large and complex field, the review is certainly not complete, but we provide more context with the literature there (see also the next point).

We were indeed unaware of arxiv:2307.01497 and we will be happy to add it to the literature review.

the only comparision of theoretical guarantees were given on Figure 1 with SGD)[...], competes with only SGD and NAG, i.e. the simplest methods,

We are emphasizing the advantages of acceleration in Figure 1, which are shared with other methods such as ACDM and CNM. We present those methods alongside AGNES in Figure 3. We would be happy to replace the label AGNES in Figure 1 by 'AGNES, ACDM'. We conjecture that the same holds for CNM, but the full result is not available in the literature.

without comparing their results with the literature on optimisation with state-dependent noise

We would be happy to expand the discussion of the results of Vaswani et. al. and Even et. al. in a revised manuscript and to include the reference suggested above.

achieved improvement does not look significant in comparison to Adam

We consider this work a (non-trivial) first step at designing algorithms which combine momentum and adaptivity in a more principled way. The simplicity of the algorithm, e.g. compared to ACDM, is an important part of this. Even in our fairly simple examples, it can be seen that for more stochastic gradient estimates (smaller batch or larger model), AGNES is more stable in its performance compared to Adam. A similar trend would be expected when looking at very diverse datasets (although we do not test this hypothesis here).

[1] Siegel, Wojtowytsch: A qualitative difference between gradient flows of convex functions in finite- and infinite-dimensional Hilbert spaces, arXiv:2310.17610 [math.OC]

We are grateful to the reviewer for their helpful feedback and will be happy to incorporate it in a revised version.

This should be highlighted more since currently the paper is written as presenting a new algorithm rather than presenting a better analysis.

We agree with the point that the novelty of our work lies in the analysis of this algorithm, which is a reparametrization of Liu and Belkin (2018)'s algorithm. We will emphasize this more clearly in the revision and further place our work in the broader context of similar accelerated algorithms. We derived AGNES as a modification of NAG independently in a parametrization particularly suited to proving acceleration in this setting and only realized the equivalence after. We maintain that the 'AGNES' version of the scheme is particularly suited to geometric interpretation and analysis, which is why we retained it.

This reduces the certainty of the claim that AGNES outperforms NAG in the high noise regime for deep learning... Could the authors either add more sweeps over hyperparameters or add these limitations to the empirical claims (such as in Contribution 5)?

The work is primarily theoretical and we are happy to acknowledge the limitations of our experimental section.

To address the question at least on one realistic example, we ran additional experiments testing a much wider range of hyperparameters for NAG for the task of training ResNet34 on classifying images from CIFAR-10. The plots along with the complete details of the experiment are included in the pdf attached to the global rebuttal. The results indicate that AGNES outperforms NAG with little fine-tuning of the hyperparameters.

Details of the experiment: We trained ResNet34 on CIFAR-10 with a batch size of 50 for 40 epochs using NAG with learning rate in {$8\cdot 10^{-5}, 10^{-4}, 2\cdot 10^{-4}, 5\cdot 10^{-4}, 8\cdot 10^{-4}, 10^{-3}, 2\cdot 10^{-3}, 5\cdot 10^{-3}, 8\cdot 10^{-3}, 10^{-2}, 2\cdot 10^{-2}, 5\cdot 10^{-2}, 8\cdot 10^{-2}, 10^{-1}, 2 \cdot 10^{-1}, 5\cdot 10^{-1}$} and momentum value in {$0.2, 0.5, 0.8, 0.9, 0.99$}. These 80 combinations of hyperparameters for NAG were compared against AGNES with the default hyperparameters suggested $\alpha = 10^{-3}$ (learning rate), $\eta = 10^{-2}$ (correction step), and $\rho = 0.99$ (momentum) as well as AGNES with a slightly smaller learning rate $5\cdot 10^{-4}$ (with the other two hyperparameters being the same). AGNES consistently achieved a lower training loss as well as a better test accuracy faster than any combination of NAG hyperparameters tested. The same random seed was used each time to ensure a fair comparison between the optimizers. Overall, AGNES remained more stable and while other versions of NAG occasionally achieved a higher classification accuracy in certain epochs, a moving time average of AGNES outperformed every version of NAG (results not plotted due to space constraints, but will be included in the revised manuscript).

We thank the reviewer for their helpful feedback and comments.

Does this imply that AGNES is essentially the same as MaSS or other previously suggested algorithms? Please clarify this point.

AGNES is equivalent to MaSS after a reparametrization (shown in Appendix B.2). We derived the algorithm from NAG independently in a way which made the proofs geometrically transparent and allowed us to draw a clear parallel between Theorems 1 and 2 for NAG and Theorems 3 and 4 for AGNES. After the analysis was completed, we realized the equivalence, but decided to work with the version which, in our opinion, allows for a simpler geometric interpretation and more transparent proofs. The results we obtain for AGNES had not been obtained for this time stepping scheme in either parametrization. We will update the introduction of the article to more prominently reflect our contributions and avoid any confusion about the novelty of the scheme.

Are Theorems 1 and 2 new theoretical results or just induced by prior works?

To the best of our knowledge, Theorems 1 and 2 are new results that we did not find elsewhere in the literature.

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.

We are grateful to the reviewer for making us aware of this reference, which we will be happy to include in our discussion of continuous-time dynamics.

Could the convergence result in Theorem 3 and 4 extend to the expectation of gradient norm?

Yes, since L-smooth functions satisfy the inequality $\|\nabla f(x) \|^2 \leq 2L (f(x) - \inf f)$ (see line 616 in Appendix E for context), Theorems 3 and 4 automatically lead to a bound on $\mathbb E[\|\nabla f(x) \|^2]$ in both convex as well as strongly convex cases. A bound on $\mathbb E[\|\nabla f(x) \|]$ can then be obtained using Jensen's inequality, i.e. $\mathbb E[\|\nabla f(x) \|]^2 \leq \mathbb E[\|\nabla f(x) \|^2]$. We would be happy to add a remark about this in the final version of the article.