Gradient correlation is a key ingredient to accelerate SGD with momentum

Thank you for your feedback and careful reading of our paper. Please see below our detailed answers

• Although the almost sure convergence result provided in Theorem 4 deepens our understanding of the SNAG method, I believe that the major focus of this paper is still on how the gradient correlation can lead to a better SGC coefficient, which gives acceleration for SNAG. From this perspective, the result in Theorem 4 seems a bit disjoint from the other sections of the paper.

We thank the reviewer to share his interrogation about the relevance of Theorem 4. As the reviewer noticed, our paper main interest is the link between gradient correlation and the possibility of accelerating SGD with SNAG. In order to have a complete comparison between these two algorithms, we include almost sure convergence rates (Theorem 2-4) additionally to expectation rates (Theorem 1-3). Importantly, in the strongly convex case notice that, as explained in Remark 5, the SGC, linked with gradient correlation, appears in the rate of Theorem 4 so in this case the question of gradient correlation remains crucial.

• Although the RACOGA condition holds in general with a coefficient of $c \geq -\frac{1}{2}$, it does not seem to be easy to find a tight $c$ for the objectives, as evaluating this lower bound involves analyzing the pairwise inner product between gradients for all choices of the parameters in the parameter space. Furthermore, when approaches to $-\frac{1}{2}$, the SGC coefficient $\rho = \frac{N}{1+2c}$ approaches infinity, leading to a trivial condition.

We thank the reviewer for this relevant remark. As discussed in our Appendix H, it is not easy to find a tight RACOGA constant even in the relative simple case of linear regression, and it could be an interesting venue of research. Also, as the reviewer noticed, the case of RACOGA constant approaching $-\frac{1}{2}$ is indeed a critical case, that is exactly the case where SNAG will perform poorly. We propose a modification of Remark 6 in our revised version in order to emphasize this property.

• The experimental verification of the paper seems quite weird. It is noticed that, in the linear regression case, the gradient correlation involves both the inner product term and the $a_i^T a_j$, sign of the residual terms $x^T a_i - b_i$'s. In particular, different signs of the residual terms could lead to completely different lower bound on the gradient correlation. However, it seems that in the experimental design the paper considered only the correlation between the data. Moreover, it may contradict the claim of the paper that RACOGA helps acceleration since in Figure 1.(a) the green curve, with a smaller RACOGA coefficient, led to a faster convergence than the blue curve.

We thank the reviewer for this interesting remark. As the reviewer noticed, the sign of $a_i^T a_j$ is not necessarily the same than the sign of RACOGA. We aim to stress that in the particular case of linear regression, Equation 15 gives a strong link between the correlation and the correlation between gradients (RACOGA). For instance, if the data are uncorrelated, then the gradients are also uncorrelated. This is exactly the example detailed in Example 3.

Moreover, experimentally, on Figure 1-2, we show RACOGA values and not the data correlation. Then, on Figure 1, we see that the values of RACOGA are very different if the data are weakly correlated (Figure 1.a) or highly correlated (Figure 1.b). We proposed a revised version of Figure 1 with the same scale for RACOGA on both plots to stress this behaviour.

Finally, in Appendix H, we develop more deeply the link between RACOGA and the data correlation in some simple examples to get more intuition about this link.

• How is Theorem 2 different from the results in Vaswani et al, 2019 ? It would be nice if the paper could include a detailed comparison of the two results.

We thank the reviewer for his suggestion. We assumed that by "Theorem 2", the reviewer meant "Theorem 3", which is the SNAG result in expectation. The convergence result from [1] and Theorem 3 differ as we consider a version of the Algorithm that involves a fewer amount of parameters. For completeness, we added a Section C.3 in our revised version where we compare SNAG with the algorithm of [1].

Also, we want to emphasize that our main theoretical contributions are rather our almost sure convergence results (Theorem 4) and our gradient correlation analysis (Proposition 1-2, Theorem 5).

Dear Reviewer wrcq,

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

Thanks.

Area Chair

Thank you for your positive feedback and careful reading of our paper. Please see below our detailed answers

• Proof for theorem 4 heavily relies on an existing result (Sebbouh et al. 2021, theorem 9), which one could argue it weakens the theoretical contributions of this work.

We are not sure what the reviewer mean with this remark, as there is no Theorem 9 in [1]. If referring to the theorem 9 present in our paper, it is a result from [2], that is a classical tool to study almost sure convergence in stochastic optimization.

What we meant is that we use this result to derive the almost sure rates. And to be transparent we mentioned that before us, Sebbouh et al. 2021 almost sure results also heavily rely on these results (from [2]), although they are applied to different algorithms. Finally, note that the strongly convex result of our Theorem 4 does not relie on the result of Robbins and Siegmund (1971), although it needs less developed tools.

• I appreciate that the authors made an effort to compare RACOGA with gradient diversity and gradient confusion and agree with the authors that they are not identical, but they do look quite similar.

We are glad the reviewer appreciate our attempt to relate our work with the literature. It is absolutely true that RACOGA and gradient diversity [3] are strongly related (Equation 39), although they correspond to different viewpoints. RACOGA is a direct measure of the gradient correlation. The gradient confusion [4] assumption is a less closed assumption, as it only measures anti correlation.

• It would be nice to have a table that summarizes results from theorem 1-4 (perhaps including results from the literature) so that readers don’t have to go back and forth to compare them.

We thank the reviewer for this suggestion. In order to make the comparison between SGD and SNAG under different conditions more clear we add a table in Section 3 (Table 1).

• Authors have remark 5 to explain the results from theorem 4 which does help me to understand it. I wonder if there is any intuition about why ρK plays a different role in convex vs strongly convex cases. Also, for the strongly convex case, it seems we need less noisy data for SNAG to beat SGD , because we want to be small. Am I understanding this correctly ? For continuous strongly convex function, there is a unique minimizer, meaning it won’t stuck in some local minimizers. How does this fit into this theory ?

This is a very interesting question, that involves deep optimization concepts. The different role of $\rho_K$ regarding the convexity or strongly convex functions stems from the different nature of momentum in these two cases.

We believe a good intuition can be gained from the continuous variants of SNAG [5,6]. In the strongly convex case, best convergences are achieved choosing momentum to be constant. In our case, the momentum depends on the SGC constant $\rho_K$ making the role of $\rho_K$ crucial. However, in the convex case, as this class of functions include very flat functions (e.g $x \to x^{12}$), best convergences are achieved with increasing momentum. In this case, the SGC constant factor is asymptotically negligible. As you noticed, we want $\rho_K$ in the SGC to be small in both cases. In the convex case, the finite-time speed up depends on SGC constant $\rho_K$. However, the asymptotic speed-up does not depend on $\rho_K$. In the case of strongly convex $f$, both finite-time and asymptotic speed-up depend on $\rho_K$.

Convex functions do not have local minimizers (as mentioned just after Definition 2). In our study, note we that do not assume that the $f_i$ are convex, we only assume that $\frac{1}{N}\sum_{i=1}^N f_i$ is convex/strongly-convex. Therefore some $f_i$ could have many minimizers and not be convex.

[1] Sebbouh and Gower and Defazio, Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball, 2021.

[2] Robbins and Siegmund A convergence theorem for non negative almost supermartingales and some applications, Optimizing methods in statistics, pages 233-257, 1971.

[3] Yin et al. Gradient diversity: a key ingredient for scalable distributed learning, 2018.

[4] Sankararaman et al. The impact of neural network overparameterization on gradient confusion and stochastic gradient descent. 2020

[5] Su, Boyd, Candès A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights 2016

[6] Siegel Accelerated First-Order Methods: Differential Equations and Lyapunov Functions 2019

• The theorem 4 statement suggests that the authors recover a rate almost surely, but in the current presentation, it is unclear what precisely is meant. Even for $O(n^{-2})$: Is there a random variable C such that $f(x_n)-f^\ast \leq C/n^2$ simultaneously for all $n$ (and almost surely in probability), or does the random constant depend on $n$ ? And, what is meant by $o(n^{-2})$? For a machine learning venue, they should state a non-asymptotic quantitative bound. Almost sure convergence is a notion of convergence which is not induced by a metric on a space of random variables. As such, there is no immediate way of making sense of the notion that $f(x_n)$ and f$(x^\ast)$ are $o(n^{-2})$-close in a specific sense. More explanation is needed. The same concern applies to Theorem 2.

We thank the reviewer to point out to us that the notion of almost sure convergence has not been formally defined in our work. Almost sure convergence rate are standard in stochastic gradient algorithm analysis (see Theorem 8 in [2], Theorem 2-3 in [3], Corollary 5 in [4], Theorem 1-2-3 in [5] or Convex Convergence Theorem, page 156 in [6]), so we do not recall the definition of this notion. More formally, if $\Omega$ is the set of realization of the noise, we say that $f(x_n) - f^\ast \overset{a.s.}{=} o\left( \frac{1}{n^2} \right)$ if and only if $\exists A \subset \Omega$, such that $\mathbb{P}(A) = 1$ and $\forall \omega \in A$, $\forall \epsilon > 0$, $\exists n_0 \in \mathbb{N}$, such that $\forall n \ge n_0$, $|f(x_n(\omega)) - f^\ast| \le \frac{\epsilon}{n^2}$. In order to make it clearer in the revised version of paper, we recall this definition in the beginning of section 3.

For practical usage, non-asymptotic quantitative bounds are in fact more useful. This is the reason why Theorem 2 and 4 are together with Theorem 1 and 3 that provide finite time quantitative bounds in expectation. However, we are not aware of finite time convergence rates, asymptotic being the standard results in almost sure convergence studies, as it can be seen in above references. As the reviewer mentioned, even the task to define such a convergence is tough.

Finally, we are not sure to understand this part of the reviewer remark : "Almost sure convergence is a notion of convergence which is not induced by a metric on a space of random variables.". Do our clarifications about the almost surely rate definition solve this concern ?

• The title of the paper is "Gradient correlation is needed to accelerate SGD with momentum", which makes it sound like gradient correlation is a necessary condition (i.e. if it is not satisfied then SGD with momentum does not converge at an accelerated rate). But I did not see a result proving that in the paper. The results actually claim that it is a sufficient condition. The title does not accurately reflect the main results.

We thank the reviewer to point out to us that our title might be confusing. In fact, our theoretical results show that positive gradient correlation, i.e. RACOGA verified for c > 0, ensures accelerated convergence rate for SNAG. Note that we look empirically at the reverse implication. On Figure 1)a), we highlighted that the uncorrelated data, i.e. RACOGA not verified for c > 0, leads to SGD being faster than SNAG.

In order to suppress any logical ambiguities, we have decided to reformulate our title into : "Gradient correlation is a key ingredient to accelerate SGD with momentum"

Thank you for your positive feedback and careful reading of our paper. Please see below our detailed answers.

• Line 70: "However, even the question of the possibility to accelerate with SNAG in the convex setting is not solved yet." This is either unclear or inaccurate or both. There are several works which address the convergence of accelerated methods in the stochastic setting, both under SGC and with classical Robbins-Monro bounds, at least for smooth objectives. For a rigorous statement, the authors should specify the geometric assumptions, smoothness assumptions, and assumptions on the gradient oracle. Since the authors are aware of previous works on acceleration in convex optimization under SGC noise, it is unclear what meaning is intended.

We thank the reviewer to stress that this sentence might be confusing. In this paragraph of the introduction, we aim to stress the interest of studying the convex setting. The detailed explanation about existing works has been stated in the previous paragraphs of the introduction "Stochastic Nesterov Accelerated Gradient(SNAG)" and "What keeps us hopeful".

We propose to reformulate this sentence as : "However, even in the convex setting,here is still work to do concerning the possibility of accelerating SGD with SNAG. For example, up to our knowledge, characterizing convex smooth functions that satisfy SGC has not been addressed yet.".

• More concerningly, the next sentence says "Finally, note that our core results (Propositions 1-2) do not assume convexity, and thus they could be used in nonconvex settings." Juxtaposed with the previous sentence, it gives the reader the impression that the authors have addressed the question of acceleration for non-convex functions, which is not true. It is true that the conditions PosCorr and RACOGA studied in Propositions 1 and 2 imply SGC even for non-convex functions. But SGC/PosCorr/RACOGA alone is not sufficient for any of the accelerated convergence results provided here or in previous works, some form of convexity is still required. The current phrasing is misleading since, again, it conflates conditions on the noise in the gradient estimates and on the geometry of the objective function, which are in general independent. If there is a relation in the setting the authors consider, they need to explain and emphasize this. I do not see the implication

We thank the reviewer to point out that this formulation might be misinterpreted. Our work does not solve the question of acceleration for non convex functions and we do not claim in our work to do so. We meant to say that further works, e.g. considering SGC in non convex setting, could also use RACOGA. Indeed, the essence of this definition and the properties we derive in Propositions 1 and 2 do not stem from convexity. We propose to reformulate this sentence as : "Finally, note that our core results about gradient correlation (Propositions 1-2) do not assume convexity, and thus could be used in future works beyond the convex setting.".

• The authors claim one of their main contributions is "new almost sure convergence results (Theorem 4)". However, almost sure convergence is already covered by corollary 5 in Gupta et al. "Achieving acceleration despite very noisy gradients" arXiv :2302.05515. That paper studies a stochastic version of NAG under a condition similar to SGC. The authors should highlight the differences in their results.

We indeed missed the recent result of [1], where the authors indeed give an almost sure convergence result. However note that if they show that $f(x_n) \to f(x^\ast)$ almost surely, they do not provide any convergence rates, as we do in our Theorem 4. We cite this work in our revision and add the sentence "Almost sure convergence has already been addressed in [1] without convergence rates." in the beginning of section 3.3.

Thanks for your response. I appreciate that the authors are receptive to feedback and have made a good effort to incorporate the feedback into their revision. I still have some doubts about the comparison between SGD and SNAG under different conditions. But now with the addition of remark 4 and appendix F, the authors are at least being more transparent about the nature of the comparison. It is interesting to see that without SGC, only a non-accelerated rate can be proved for SNAG. If the authors have the space for it, they can consider moving the discussion in Remark 9 to the main body of the article (this is only a suggestion and does not affect my recommendation for the paper).

Nevertheless, I think that the overall contributions of the paper are interesting and useful enough. Most of my concerns were about the presentation, which have been addressed by the authors. I am happy to increase my score.

• How robust is SNAG's performance to variations in RACOGA across different types of datasets and optimization problems?

Again, it is a very interesting and open question. Identifying variations of RACOGA's behaviour across different datasets and optimization problems could help create link between model properties and appropriate optimizers. In all our experiments, both in linear regression (two datasets) and in deep learning classification (two datasets), we observe that large values of RACOGA allow to accelerate SGD with SNAG. Moreover, in the convex setting (linear regression), we show an example where low values of RACOGA lead to SGD being not accelerated with momentum. In our revised version, we added Figure 8 in Appendix A, where we plot the RACOGA values and convergence curves of SGD and SNAG for other classification datasets (MNIST, FashionMNIST, KMNIST, EMNIST), trained with a CNN. RACOGA values remain high for all datasets.

[1] Carmon et al., Lower Bounds for Finding Stationary Points I, 2019.

[2] Hinder et al., Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond, 2023.

[3] Arjevani et al., Lower Bounds for Non-Convex Stochastic Optimization, 2022.

[4] Sankararaman et al. The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent, 2020.

Thank you for your positive feedback and careful reading of our paper. Please see below our detailed answers.

• The text and formulas are a bit dense; the author can add a table to compare the convergence speed of SGD and SNAG under different conditions.

We thank the reviewer for this suggestion. In order to make the comparison between SGD and SNAG under different conditions clearer we have added a table at the beginning of Section 3 (Table 1).

• The graphs look good. However, that would be better if the author gave more detail about the explanation for the graph, for example, what the "small values" of RACOGA mean on the graph.

We are glad that you appreciate our graphs. We also thank the reviewer for his suggestion to bring more clarity to our paper. We propose a new revised version where we add some details. First, we introduce the parameter $\lambda$ (Figure 1) in the main text. Then, we display a revised version of the histogram of RACOGA values (same scale in both sub-figures) in order to show that we mean "small values of RACOGA" in Figure 1a compared to the correlated case (Figure 1b).

• The colors in the right graph for Figure 1(a) are similar, author can use more contrasting colors.

We thank the reviewer for his feedback about Figure 1. In the revised version, we propose a new set of colors in order to make this figure clearer.

• While RACOGA has been demonstrated to facilitate the acceleration of SNAG over SGD in convex and strongly convex functions, how does RACOGA perform in non-convex optimization scenarios, such as those commonly found in deep neural network training? Can RACOGA be effectively applied to these more complex models, or are there additional considerations needed to achieve similar acceleration benefits?

We thank the reviewer for this question. Indeed, it is crucial to derive from this work future theoretical results that could be applied to realistic machine learning optimization tasks.

First, the possibility to achieve acceleration relies heavily on geometrical assumptions of the function. Even in a deterministic setting, gradient descent is optimal in some cases, as for instance in the case of $L$-smooth functions [1].

It is therefore critical to find relevant geometrical properties that may relax convexity, and that allow to demonstrate an acceleration of SNAG over SGD. It is known that for some classes of non convex functions such as quasar convex functions [2] or functions with Lipschitz gradient and Lipschitz Hessian [3], momentum type algorithms allow to theoretically achieve faster convergence in a deterministic setting.

Finally, we study in this work deep learning classification trainings (Figure 2), which is a non-convex optimization problem, in order to get intuition of the possibility to extend RACOGA tools to this non-convex setting. We observe in Figure 2, that large RACOGA leads to faster convergence of SNAG over SGD. This suggests empirically that RACOGA could be useful even in this non-convex setting. We leave for future works the extension of our theoretical results in this non-convex setting with the appropriate geometrical properties.

• The paper highlights that large RACOGA values enable the acceleration of SGD with momentum. However, what practical methods or criteria can be used to identify or achieve large RACOGA values in real-world applications ?

It is a very interesting and open question. As mentioned in our Remark 7, the authors of [4] show that when considering neural networks, some mechanisms such as increasing the width of the layers allows to increase the gradient confusion, a quantity which is related to RACOGA.

However, the question of designing mechanisms that may exhibit positive correlation, quantified with RACOGA, is difficult (we discuss the linear case in our Appendix H), and it is still an open question as far as we know.

In this work, we introduce RACOGA as a theoretical tool to understand the possibility of accelerating SGD with SNAG, but more works need to be done to make it a truly practical tool.

Finally, note that it appears with our experiments in Figure 2 show that classical neural network architectures such as MLP or CNN lead to high RACOGA values. This suggests that these architectures naturally produce high RACOGA values.

Dear Reviewer b9ZL,

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

Thanks.

Area Chair