Gradient correlation is a key ingredient to accelerate SGD with momentum
Authors: Julien Hermant
Marien Renaud
Jean-François Aujol
Charles Dossal
Aude Rondepierre
Venue: ICLR 2025 Poster (2025)
Keywords: optimization
convex
nesterov momentum
sgd
neural network
Primary area: optimization
TL;DR: We prove that gradient correlation enables nesterov momentum to accelerate SGD for convex functions.

Abstract: Empirically, it has been observed that adding momentum to Stochastic Gradient Descent (SGD) accelerates the convergence of the algorithm.
However, the literature has been rather pessimistic, even in the case of convex functions, about the possibility of theoretically proving this observation.
We investigate the possibility of obtaining accelerated convergence of the Stochastic Nesterov Accelerated Gradient (SNAG), a momentum-based version of SGD, when minimizing a sum of functions in a convex setting. 
We demonstrate that the average correlation between gradients allows to verify the strong growth condition, which is the key ingredient to obtain acceleration with SNAG.
Numerical experiments, both in linear regression and deep neural network optimization, confirm in practice our theoretical results.

Published as a conference paper at ICLR 2025
GRADIENT CORRELATION IS A KEY INGREDIENT TO ACCELERATE SGD WITH MOMENTUM
Julien Hermant Marien Renaud', JJan--rannool Aujol', Charles Dossal,, Aude Rondepierre? Univ. Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251, F-33400 Talence, France 2. IMT, Univ. Toulouse, INSA Toulouse, Toulouse, France
ABSTRACT
Empirically, it has been observed that adding momentum to Stochastic Gradient Descent (SGD) accelerates the convergence of the algorithm. However, the lit- erature has been rather pessimistic, even in the case of convex functions, about the possibility of theoretically proving this observation. We investigate the pos- sibility of obtaining accelerated convergence of the Stochastic Nesterov Acceler- ated Gradient (SNAG), momentum-based version of SGD, when minimizing a convex setting. We demonstrate that the average correla-
sum of functions tion between gradients allows to verify the strong growth condition, which is the key ingredient to obtain acceleration with SNAG. Numerical experiments, both linear regression and deep neural network optimization, confirm in practice theoretical results.
INTRODUCTION
Supervised machine learning tasks can often be formulated the following optimization prob- lem (Hastic et al. 2009):
f min f(x), with f(x) = Σ f(() xEB4
(FS)
where for all i E (1,...,N) N). : Rd - R is associated to one data. As there is often no closed form solution to problem (FS), optimization algorithms are commonly used. Considering high di- mensional problems, first order algorithms such as gradient descent, namely algorithms that make use of the gradient information, are popular due their relative cheapness, e.g. compared second order methods which involve the computation of the Hessian matrix. In the case of problem (FS) the gradient itself may be computationally heavy obtaín when N is large, i.e. for large datasets. This the reason why, instead of the exact gradient, practitioners rather use average of subsampled set of several Vfs, resulting in algorithms such as Stochastic Gradient Descent (SGD) (Robbins & Monro 1951) ADAM algorithm (Kingma & Ba 2015). Although estimation of the gradient is used, SGD performs well in practice (Goyal et al.
2017 Schmidt et al. 2021 Renaud et al. 2024).
Interpolation One of the key points that explain the good performance of SGD is that large ma- chine learning models, such as over parameterized neural networks, are generically able to perfectly fit the learning data (Cooper) 2021 Allen-Zhu et al., 2019; Nakkiran al., 202T; Zhang et al.) 2021]. From an optimization point of view, this fitting phenomenon translates into an interpolation phenomenon (Assumption I].
Assumption (Interpolation). 3z arg min v1 S N, x² E arg
Strikingly, under this assumption, theoretical results show that SGD performs as well as determinis-
tic gradient descent (Ma al. 2018 Gower et al. 2019 202T).
Momentum algorithms: hopes and disappointments Within the convex optimization realm, it is well known that a first order momentum algorithm, named Nesterov Accelerated Gradient (NAG),
maalien.hermannn @ math borddcauuu.f

---

Published as a conference paper at ICLR 2025
outperforms the gradient descent in term of convergence speed Nesterov 1983 2018) A natu- ral concern thus whether, assuming interpolation and convexity. a stochastic version of NAG, Stochastic Nesterov Accelerated Gradient (SNAG), can be faster than SGD. Unfortunately, exist- ing works has expressed skepticism about the possibility of acceleration via momentum algorithms, even assuming interpolation (Assumption D. Devolder al. (2014); (Aujol & Dossal (015) indicate that momentum algorithms are very sensitive to errors on the gradient, due to error accumulation. Also, the choice of parameters that offers acceleration in the deterministic case can make SNAG diverge KKdammi et al. 22018; Assran & Rabbat 2020); Ganesh et al. (003)).
What keeps us hopeful Firstly, the case of linear regression, depending on the data, SNAG can accelerate over SGD (Jain et al., 2018 Liu & Belkin] 2020) Varre & Flammarion] 2022). Unfor- tunately the methods used in those works are hardly generalizable outside of the linear regression case. On the other hand, in convex setting, Vaswani al. (2019) show that under assumption over the gradient noise, named the Strong Growth Condition (SGC), SNAG can stabilized, and it could accelerate over SGD. However, it is not clear which functions satisfy this assumption, and in which cases acceleration occurs.
On the convexity assumption For many machine learning models, such neural networks, the associated loss function is not convex (Li et al., 2018).
However, even in the convex setting, there still work to do concerning the possibility of acceler- ating SGD with SNAG. For example, up to our knowledge, characterizing convex smooth functions that satisfy SGC has not been addressed yet.
Finally, note that our core results about gradient correlation (Propositions vexity, and thus could be used in future works beyond the convex setting.
12 do not assume con-
Can SNAG accelerate over SGD in convex setting
Contributions (i) We give new characterization of the Strong Growth Condition SGC constant by using the correlation between gradients, quantified by RACOGA (Propositions 12 and we exploit this link to study the efficiency of SNAG. (ii) Using our framework, we study the theoretical impact of batch size on the algorithm performance, depending on the correlation between gradients (Theorem 55). (iii) We complete convergence results of Vaswani et al. (2019); Gupta et al. (2023) with new almost sure convergence rates (Theorem 4 (iv) We provide numerical experiments that show that RACOGA is key ingredient to have good performances of SNAG compared to SGD.
2 BACKGROUND
For a function f: dRd + R. continuously differentiable, we introduce the following definitions.
Definition 1. Let L > 0. f IRd + R is L-smooth V is L-Lipschitz.
Definition I Timplies that Vx, y E Rd, f(x) S f(v) + (V)()) y) 11 Nesterov 2018
and it ensures that the curvature the function f is upper-bounded by
Definition 2. f Rdd + IR is j-strongly convex if there exists p. > 0 such that: Va, y E Rdd f(x) >
f(y) (Vf(v), x y) + 1 yll². f. Id - convex if it verifies this property with μ
Definition implies that the curvature of the function f lower-bounded by / 0. Convex functions are very convenient for optimization and widely studied (Nesterov) 2018 Beck 2017
For instance, a critical point of convex function is the global minimum this function.
Assumption 2 (smoothness). Each fr in (FS) is L,-smooth. We note L(k) == max K E Lg where C (1....,N), Card( B) = K and we note Immax = L(1) max Li-- 1515N
Assumption implies that f is L-smooth with L < for the convergence results for SGD (Theorems
N ΣN L, S L(k) I Lmazz and will be used
2

---

Published as a conference paper at ICLR 2025
The stochastic gradient descent (Algorithm D is widely used despite its simplicity. It can be viewed as a gradient descent where the exact gradient is replaced by a batch estimator
SGD
<<(x)
M v((x). K
(1)
REB
where batch of indices of size K sampled uniformly in { (1,..., N) Card( K). Note that V (x) a random variable depending on K, and æ.
Algorithm 1 Stochastic Gradient Descent (SGD)
Algorithm 2 Stochastic Nesterov Accelerated Gradient (SNAG)
1: input: Zu E IR, > 0
1: input: = E Rd > 0. 8 E [0, 1],
2: for 0, ........ Bie do
(an)nEN E |0, 1], (Ba E R
En+11 =In sVV(kn))
2: for = 0,1,..... Tlit do
4: end for
3: yn = Un + (1 +1--nn)
5: output: Fna
4: In-1 = Un (V))
5: Zn+1 = Ban + (1 - 8)1yn 1m (x(yn)
6: end for
7: output: Fru
SNAG The Nesterov accelerated gradient algorithm (Algorithm in Appendix B.1 allows to achieve faster convergence than gradient descent when considering L-smooth functions that are convex or strongly convex, see Nesterov [1983] 2018). Intuitively, a momentum mechanism accel- erates the gradient descent. As proposed in Nesterov (2012). stochastic version of the Nesterov Note that there exists several
accelerated gradient algorithm can be developed, see Algorithm 2
ways to write (see Appendix B.2
Strong Growth Condition To our knowledge, this assumption was introduced in Polyak 1987). and further used Cevher & Vu (2019) as relaxation of the maximal strong growth condition
Tseng 1998 Solodov 1998).
Definition 3. The function f. with gradient estimator V (Equation 7v. is said to verify the Strong Growth Condition if there exists pk 2 such that
Vr E IRd, E [ S SK Vfxx)
(SGC)
PK quantifies the amount of noise: the larger PK. the higher the noise. In some sense, the strong growth condition allows to replace the norm of the stochastic gradient by the norm of the exact gradient, up degrading constant Pg. We will see in Section 3 that it allows recover similar convergence results as for the deterministic case.
Example 1. Vaswani el al. (2019) show that if the function f strongly convex and verifies As- sumptions and then f verifies the strong growth condition with Pk 1.x)
Remark 1. The SGG implies interpolation (Assumption ! each fi is convex, see Remark 77 in Appendix [I.3] However in the following results (Theorems [14) as we will only assume that the sum of fs is convex, SSGC will not enforce interpolation. It will imply instead that minimizers of are critical points of all fe.
Remark 2. Considering linear regression, one can choose functions such that the SGC is verified only for arbitrary large values of PK (see Appendix D.I). Worse, if we discard the convexity as- sumption. then one can construct examples such that PK does not exist (see Appendix D.2 Finding classes of functions such that the SGC is verified for an interesting PK is thus not an obvious task.
3 CONVERGENCE SPEED OF SNAG AND COMPARISON WITH SGD
In this section, we present convergence results for SNAG (Algorithm 2 under the Strong Growth Condition (SGC). Before doing so, introduce convergence results for SGD (Algorithm) in order

---

Published as a conference paper at ICLR 2025
Algorithm
Assumption over j
Convergence
SGD
convex
E, solution
O
Lixi
Thm
strongly convex
E, solution
o
Luxi
log (
Thm
"
convex
a.s.,
) Thm 2
strongly convex
a.s.,
4.
)m)
Thm
SNAG
Convex
E, solution
PK V
1 Thm
Strongly Convex
E, solution
o pk v
log (1)
Thm 3
Convex
a.s., c.r
( Thm 4
Strongly
a.s., C.r
I + 51)² Thm
Table Summary all the convergence results presented in Section 3 Results stated c-solution
refer to convergence results of the form of Equation (2). c.r. stands for convergence rate. These
results are stated as an upper bound of the form f((nn) - f" = O (1hn), where th is a sequence decreasing to O.
to compare the performance of these two algorithms. All the results introduced in this section are summarized in [
For >> O, we say that algorithm (rn)a reaches e-precision at rank Vs R if
Vn 2 [f(x)) S
We denote by Ω the set of realization of the noise. We say that an algorithm {zn Jn converges almost surely with rate negligible compared an E I denoted by fzz)) f 0.2 o (an). if and only 33 C Ω such that ((A) = 1 and Vu E A, Ve > 0, Eng E N. such that Vn 2 no.
[f(x((w)) - f*1 S Ea,
(3)
3.1 CONVERGENCE RESULTS FOR SGD
First, we state convergence results of SGD (Algorithm 1. in expectation and almost surely. The two following theorems are variations of Gower et al. (2019) and Gower et al. (2021) (results in expectation) and Sebbouh et al. (2021) (result almost surely). The difference that our setting does not assume the convexity of each f. in (FS), but rather only the convexity of the sum.
Theorem 1. Under Assumptions and 2 SGD (Algorithm) guarantees to reach an E-precision at the following iterations:
If f convex, 2T
> 2 ((K))
100 - x²1 Taxi
(4)
If f j-strongly convex,
> 2 L(K)
log ( -M
(5)
P
MEE
For the convex case, the bound is of the order O [(k) while for the strongly convex case the key
factor is L(x) that may be very large for ill conditioned problems. These results very similar to J those obtained in deterministic setting, Appendix B.1
Additionally, almost sure convergence gives guarantees that apply to a single run of SGD.
Theorem 2. Under Assumptions and 2 SGD (Algorithm [ guarantees, in the sense of (3) the
following asymptotic results.

---

Published as a conference paper at ICLR 2025
If is convex, 2hexey"
( 11
(TTn)
0.8.
If p-strongly convex, s Tuxy
f(xn) f - o o + +
for all > O, where ==
___ To = zo and In+1 ntI In + n-1 Tn. L(x)'
Note that in the convex case, there need of averaging the trajectory along iterations. Proofs of Theorem and Theorem are Appendix E.1
3.2 CONVERGENCE IN EXPECTATION FOR SNAG
We now state the convergence speed of SNAG in expectation under the Strong Growth Condition SGC and we compare with the convergence speed of SGD.
Theorem 3. Assume f is L-smooth, and that VK verifies the SGC for PK 1. Then the SNAG (Algoritim 2 allows to reach an E-precision (2) at the following iterations: If f convex,
1 Lpx: Tn
1 n+
3 1, an
LPk
2
2+
2 PK
2L 2D0 z¹1l.
(8)
If is p-strongly convex,
Lpx Tn 11
PxVul, 8 ==1
PN On
14
n 2 PK V log [1m))
(9)
Theorem is variation Vaswani et al. 2019 Gupta al. (2023). see Appendix Indeed, our proof (Appendix(G) leads to the same convergence result as Vaswani et al. (2019), although resulting in a slightly simpler formulation of the algorithm, as we do not have intermediate sequences of parameters, see Appendix C Note that only use the L-smoothness of and the SGC instead of Assumptions because SGC allows us to make weaker assumptions.
Theorem indicates that the performance degrades linearly with PK. For the special case PK 1, bounds of Theorem 3 are the same as the deterministic case (see Appendix [.I).
Remark 3. According to Theorem and Theorem 7 SNAG (Algorithm is faster than SGD (Al- gorithm 7 when PK is small enough, more precisely when
2L eT. I xx11= if convex.
. PK <
PK 2
i p-strongly convex, ignoring the differences between logarithm terms. uL
If f is convex and the required precision E small enough, SNAG is faster than SGD. is not neces- sarily the case if f is p-strongly convex, the dependence disappears. In particular, the bound pK < Lan. offered by strong convexity (see Example 1y does not guarantee acceleration.
Remark 4. In our comparison, we neither considered convergence result SGD (Algorithm that assumes the SGG nor considered result for SNAG (Algorithm) 2 that does not assume SGC In both cases, doing would lead to misleading comparisons, see summary in Remark
3.3 ALMOST SURE CONVERGENCE FOR SNAG
We provide new asymptotic almost sure convergence results for SNAG (Algorithm 2 Almost sure convergence has already been addressed in Gupta et al. (2023) without convergence rates.
5

---

Published as a conference paper at ICLR 2025
Theorem 4. Assume is L-smooth. and that Vx verifies the SGC for pK 1. Then SNAG
(Algorithm 2 guarantees, in the sense of (3), the following, asymptotic jasypoing.syymmpooti results:
n² If convex, LxL On 1++1 B 1, On
f(xn) f
(10)
n?
If f is p-strongly convex,
Px Tn =1 px vpL 8 =
V L.
On =0=
PK
f(x)) f a.s. o ol1g+ + =
(11)
for all e' > O, where = PX VE.
See proofs in Appendix These bounds are asymptotically better than the finite time bounds, with of ( compared to O (Theorem 3 for instance in the convex setting. A similar asymptotic
speedup phenomenon happens in the deterministic setting (Attouch & Peypouquet 2016).
Remark 5. Theorem 4 states that in the convex case, the parameter рK has negligible impact on the asymptotic convergence, and thus SNAG always asymptotically outperforms SGD. For the strongly convex case, we need to ensure that pk / have SNAG faster than SGD,
The possibility of acceleration of SNAG over SGD highly depending on the |SGC constant PK- We need to investigate for fine characterization of pæ to ensure acceleration in realistic contexts.
CHARACTERIZING CONVERGENCE WITH STRONG GROWTH CONDITION AND GRADIENT CORRELATION
Although general bounds on the constant Px are difficult to obtain (see Remark Example shows that the characterization of the SGC constant given in Example can be improved.
Example (Motivating example). Consider the function f(x) = (e1, x)2² 4 (e2, x)) with O < < L and E1, eg standard basis vectors. This function satisfies Assumption Assumption with Lmuax = L, and it is I "sttrongly convex. Following Example ! f satisfies the SGC with
P1 = 2 which can be arbitrary large. However, by developing || f we get that the SGC is
actually verified pt = - 2
Example 2 motivates to seek for new, eventually tighter, characterizations of the SGC constant.
4.1 AVERAGE POSITIVE CORRELATION CONDITION
In this section, we show how we can exploit the finite sum structure of f to exhibit condition that, verified, allows for a new computation of pk-
Proposition Considering batches of size K, we have
K |V/()| N [IVx()))
N - K
Σ V((x))
(12)
N2 N-1 KEKGEN
Proposition is proved in Appendix H.1 Without any assumption on f. Proposition [ splits the norm of f into two terms. One relies on the gradient estimator, while the other one involves the average correlation of gradients. From Proposition] 1 we deduce the following consequence.
Corollary 1. Considering batches of size K, f satisfies the SGC with Pk = N if its gradients are, on average, positively correlated, i.e. if have
VE Rd.
Σ (V)(()), ())))) 2 O. ISKINN
(PosCorr)

---

Published as a conference paper at ICLR 2025
Using CosCon Corollary SarollaryDensuree that verifies SSC for constant PK only depending on N and the batch size K, and not on geometrical parameters of f, e.g. μ or L.
Example 3. Assume fi(x) (( wi)), for some & R I that are non necessarily convex, and some orthogonal basis fwite We have Vf((r) = = ((x ui)) Then, condition PosCorr is verified, and f satisfies the SGC with pk -.. Note that the upper-bound pk S #
L(K1 given
in Example can be arbitrary large independently of N and K (see Example 2 meaning that eventually K L(K) Thus, the new upper-bound for PK (Corollary can be much tighter, resulting in improved convergence bounds for SNAG (Theorem
In some cases, condition PosCor could be too restrictive (see Appendix DT In the following section, we show how to ensure the SGC with relaxed version of PosCont named RACOGA
4.2 RACOGA RELAXING THE PosCoRs CONDITION
We introduce a new condition named RACOGA which is related, but not the same as two other conditions named gradient diversity (Yin et al. (018) and gradient confusion (Sankararaman et al., 2020j. We discuss these different conditions Appendix
Definition 4. We say that f verifies the Relaxed Averaged COrrelated Gradient Assumption (RACOGA) if there exists c E R such that the following inequality holds:
Ve ER Eisioien (V V(z(a))
2c,
(RACOGA)
Σ [/(=))]
where X E E (I, IVA(( = 0}.
RACOGA is a generalisation of the condition PosCor which allows to quantify anti correlation (c < 0) or correlation (c 0) between gradients.
Proposition 2. Assume RACOGA holds with > - Then, considering batch of size 1, f verifies
the SGC with P1 I+22
N
Proposition 2 proved Appendix H.2 Note that RACOGA is always verified with - and we have N-1 (Appendix H.5
2
Remark 6. Proposition 2 creates a direct link between RACOGA and SGC indicates that the more correlation between gradients there is, the lower is the SGC constant, which results in im- proved convergence bounds for SNAG, see Theorems 3 Importantly if the gradients are too anti correlated. Proposition could only be verified with arbitrary close to resulting in bound for P1 increasing to +
2
Remark 7. It is well known thut considering high dimensional vectors drawn uniformly the unit sphere, they will be pairwise quasi orthogonal with high probability (Milman & Schechtman 1986). Sankararaman et al. (2020) show theoretically and empirically that considering neural networks with data drawn uniformly on the unit sphere, under some assumptions, linked to over parameter- ization, each scalar product (V (I),, fzz())) is not too negative. In this case, RACOGA is thus verified for a c that is at worst close to zero.
4.3 THE STRONG GROWTH CONDITION WITH BATCH SIZE 1 DETERMINES HOW THE PERFORMANCE SCALES WITH BATCH SIZE
In this section, we build over Proposition 2 which only covers batches of size 1, to take into account bigger batches.
Lemma 1. Assume that for batches of size 1. f verifies the SGC with constant P1. Then, for batches size K, f verifies the strong growth condition with constant PK where
PK S K(N 13 (pi(N - K) + (K 1)N)
(13)
Lemma D is proved in Appendix H3 It shows that the SGC is verified for batches of size 1, is verified for any size of batch K and can compute estimation of px.

---

Published as a conference paper at ICLR 2025
Strikingly, Lemma 1 allows to study the effect of increasing batch size K on the number of f evaluations we need to reach a e-solution. We only consider the convex case, as the same reasoning and results hold for strongly convex functions.
Theorem 5. Assume f is convex and I-smooth, and that V, verifies the SGC with P1 2 1. Then, SNAG (Algorithm 2 with batch size K allows to reach an e-precision this amount of V fr evaluations:
2L Io
AK.PL
x²1,
(14)
where Ak = - pI *x=
|ro x"1 is the number of V f: evaluations needed reach E-precision when using batches of size according Theorem
-= and PIV V
21 =
Compared to the theorems of section Theorem gives bound on the number of V have evaluate, not the number of iterations of the algorithm, see the proof in Appendix H.4
Theorem 5 indicates that using batches of size K, we need ÅK times the number of V.f that is needed when using batches of size to reach an e-precision. Note also that it assumes the knowledge of P1. that can be determined using (ACOGAA see Proposition| 2
Remark From Theorem we distinguish regimes, among which the orthogonality of gradients is critical state.
1. P1 =N. This is notably true when the gradients are orthogonal. Αк for any value of K, and the number of V evaluations is exactly the same independently of batch size.
2. P1 < N. The gradients are in average positively correlated, i.e. RACOGA is verified with > ÂK > 1, and increasing batch size leads to an increasing amount of f evaluations. So, increasing batch size will make parallelization sublinearily efficient, phenomenon known as performance saturation, see MeeMa et al. (0118; Liu & Belkin (220))
3. P1 N. The gradients are in average negatively correlated, i.e.
RACOGA is verified with
C << 0. Δк < 1 and larger batches leads to a decreasing amount of J evaluations.
Theorem and Remark [ state that, considering convergence speed, replacing the exact gradient by stochastic approximation is not necessarily cheaper, of number of V fs we evaluate.
5 NUMERICAL EXPERIMENTS
Our theory indicates that the correlation between gradients, evaluated through RACOGA is needed to have SNAG (Algorithm outperforming SGD (Algorithm[]) We provide numerical experiments to validate this statement by running SNAG to optimize classic machine learning models such as linear regression (Section [5. or classification neural network (Section 5.2). We also compare its performance with its deterministic version NAG (Algorithm
7). together with GD (Algorithm 6 com J- He rmant /oome/o um Stochastic
Our code is available at
RACOGA in practice We introduced the MACCGAA as an inequality that holds over all the space. However, in practice, one only needs to consider the RACOGA] values along the optimization path. So this quantity will be computed only along this path.
Performance metrics Our interest will be how the algorithms make the training loss function decrease. In order to make fair comparison between algorithms, our z-axis is the number of V evaluations, not fia, the number of iterations of the algorithms.
5.1 LINEAR REGRESSION
For dataset (as; N Rdd x R., solve linear regression formulated Problem LR
8

---

Published as a conference paper at ICLR 2025
1 E N
f(x)
M
(ai 4) b,)².
(LR)
We consider the overparameterized case, i.e. d> N. Note that the linear regression problem is con- vCx and smooth, so we are in the theoretical setting of this paper. Moreover, we can directly compute the parameters involved in the algorithms except for parameter À that replaces the unknown pK constant in the case of SNAG, see details in Appendix A.1
An interesting characteristic of linear regression is that as f(())) ((a5, - be]as, we have (V V(}()) ((u;, x) bi)( - bj) (ais (s)
(15)
gradient conrelation
data correlation
The pairwise correlation between the gradients depends explicitly on the pairwise correlation inside the data. Therefore, we expect the correlation inside data to impact on the RACOGA values, and thus on the performance of stochastic algorithms such as SNAG (Algorithm 2
To validate this intuition experimentally, we build two different datasets with 1000. The first set of ) is generated uniformly onto the d-dimensional sphere, such that the data are fewly correlated. The second one is generated by a Gaussian mixture law with ten modes, which induces correlation inside data. In both cases, the {b:] are generated by a Gaussian law.
100 and d
SNAS U.5N
29
SNAG 0.25M SNAG 1.00
SNAG A 11.5N
login
logif
GD
GD
NAG
NAG
SNAG = 0.5%
5WG A 2
1:N0
SYAG A
SNAGA=
0
1000
-0.5
1000
05
Gradient evaluations
RACOGA
Gradient evaluations
RACOGA
(a) Low correlation within data
(b) High correlation within data
Figure 1: Illustration of the convergence speed of GD (Algorithm 6). SGD (Algorithm I batch size 1), NAG (Algorithm 7 and SÑAG (Algorithm batch size 1) on linear regression prob- lem, together with an histogram distribution of RACOGA values along the iterations of SNAG. Stochastic algorithms results are averaged over ten runs. On the left, data are generated by a law that make them fewly correlated, while on the right the data are generated by gaussian mixture, leading to higher correlation. The parameter replaces the unknown LSGCCcontan see Appendix A. Note that the data correlation results in better performance of SNAG, whereas uncorrelated data lead to smaller RACOGA values, reducing the benefit of using SNAG.
the algorithm.
SGD SNAG Comparing right parts of Figure la and Figure 1b we observe that the lack of correlation inside data leads to smaller values of RACOGA In the case of Figure Ta these lower Figure RACOGA values coincide with SGD being faster than SNAG. On the other hand we that the presence of correlation inside the data makes the optimization path crosses areas with higher RACOGA| values, allowing SNAG to be faster than SGD. These experimental results support our theoretical findings.
Deterministic vs stochastic Strikingly, one can also observe that the lack of correlation results in poor performance of all the stochastic algorithms, especially compared to NAG (Figure Tap. Con- versely, presence of correlation results the opposite phenomenon (Figure [ These observations are consistent with our theoretical findings of Section 4.3 which indicate that is some cases, stochas- tic algorithms are not necessarily cheaper to use than their deterministic counterparts in term of f.f evaluations.
Role of À the case of SNAG (Algorithm the PK constant, that do not know. We thus replace pK by parameter X. The higher the
2).
the choice of parameters from Theorem involves

---

Published as a conference paper at ICLR 2025
RACOGA are, the smaller PK is, and the smaller À can be chosen which results to more aggressive steps of the algorithm, as 1. See details in Appendix A.1
LX
5.2 NEURAL NETWORKS
In this second experiment, aim test if the crucial role of correlation inside data observed for linear regression (Section 5.1) extend to more general models.
For dataset {a;, by J network model with the cross-entropy loss. Importantly, this problem is not convex, so we are not anymore in the setting of our theoretical results.
Rdd IR, we consider classification problem tackled with neural
We use the SNAG version implemented in Pytorch (Algorithm 3 that is equivalent to Algorithm 2 Appendix B.2
As for the linear regression problem, we use two different datasets. The first one, CIFARIO (Krizhevsky & Hinton| 2009). is composed of images and serves as the correlated dataset. The second one, generated onto the d-dimensional sphere with 2 different labels according to which hemisphere belongs each data (see details in Appendix A.2), serves the uncorrelated dataset. For the CIFARTI 10 experiment, we use Convolutional Neural Network CCNN,LeCuus et al. (1998) and for the sphere experiment we use Multi Layer Perceptron (MLP, Rumelhart al. 1986))
0.75
2.4
SG.
SGID
GD
GD
logifi
SGD
SNAG
SNAG
NMS
3911
12,3
3911
48.3
Gradient evaluations
RACOGA
Gradient evaluations
RACOGA
(a) SPHERE MLP
(b) CIFARIO CNN
Figure Illustration of the convergence speed of GD (Algorithm 6 SGD (Algorithm 1 batch
size 64), NAG (Algorithm 3 full batch) and SNAG (Algorithm 3 batch size 64) averaged over 10 different initializations, together with an histogram distribution of RACOGA values taken along the optimization path, averaged over 10 different initialisations, where the z-axis scale is logarithmic.
On the left, we use MLP to classify data sampled from law such that they are fewly correlated. On the right we use CNN to classify CIFAR10 images. Note that contrarily to Figure [I the presence of correlation within data no longer influence the RACOGA values, that remains high in both cases, resulting in better performances of SNAG.
Strikingly, appears on Figures 2a and anddadndbbbb that the correlation inside data has no longer direct impact on the RACOGA values along the iterations path. In each case the RACORGA values high, which results is SNAG outperforming other algorithms. In particular, both deterministic algorithms are significantly less efficient.
These experiments indicate that neural networks offer high RACOGA values, that SNAG can take advantage of to converge faster.
CONCLUSION
In this paper, we introduced RACOGA to help to understand in which case the Stochastic Nes- terov Accelerated Gradient algorithm (SNAG) allows to outperform the Stochastic Gradient Descent (SGD) for convex or strongly convex functions, as it happens for the deterministic counterparts of these algorithms. We demonstrate theoretically and empirically that large RACOGA values al- lows to accelerate SGD with momentum. RACOGA may be the, up to now. missing ingredient to understand the acceleration possibilities offered by SNAG in this setting, outside the linear regression problems.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the ANR project PEPR PDE-AI, and the French Direction Générale de I' Armement. Experiments presented in this paper were carried out using the PIaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Universite de Bordeaux, Bordeaux INP and Conseil Regional d' d'Aquitaine (see our knowlegde the works about gradient diversity and gradient confusion, and Eve Descomps for her help for figure design.
We thank Bilel Bensaid to bringing to
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International conference on machine learning, pp. 242-252. PMLR, 2019.
Mahmoud Assran and Michael Rabbat. On the convergence of nesterov's accelerated gradient method in stochastic settings. In Proceedings of the 37th International Conference Machine Learning. ICML 20. JMLR.org. 2020.
Hedy Attouch and Juan Peypouquet. The rate of convergence of nesterov's accelerated forward- backward method is actually faster than 1/k²2. SIAM Journal Optimization, 26(3):1824-1885 2016.
Jean-François Aujol, Charles Dossal, and Aude Rondepierre. FISTA is an automatic geometrically optimized algorithm for strongly convex functions. Mathematical Programming, pp. 1-43, 2023.
Jean-François Aujol, Charles Dossal, Hippolyte Labarrière, and Aude Rondepierre. Heavy Ball
momentum for non-strongly convex optimization. arXiv preprint arXiv:2403.0644 2024.
Jean-François Aujol and Charles Dossal. Stability of over-relaxations for the -bakwadd algorithm, application to FISTA. SIAM Journal on Optimization, 25(4):2408-2444 2015.
Rishab Balasubramanian, Rupashree Dey, and Kunal Rathore. Contrastive learning for ood object detection, 2022. URL httpt:ttt////attttt org/ abs/ 2208. 06083
Amir Beck. First-order methods in optimization. SIAM, 2017.
Volkan Cevher and Bang Cong Vu. On the linear convergence of the stochastic gradient method with constant step-size. Optimization Letters, 1375:11177-1177, 2019.
Tarin Clanuwat, Mikel Bober- Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, 2018.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 international joint conference on neural networks (ICNN), pp-
2921-2926. IEEE, 2017.
Yaim Cooper. Global minima of overparameterized neural networks. SIAM Journal on Mathematics of Data Science, 3(2):676-691, 2021.
Aaron Defazio. On the curved geometry of accelerated optimization. Advances in Neural Informa- tion Processing Systems, 32, 2019.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146:37-75, 2014.
Swetha Ganesh, Rohan Deb, Gugan Thoppe, and Amarjit Budhiraja. Does momentum help in stochastic optimization? a sample complexity analysis. In Uncertainty in Artificial Intelligence, pp. 602-612. PMLR, 2023.
Yuan Gao, Anton Rodomanov, and Sebastian U Stich. Non-convex stochastic composite optimiza- tion with polyak momentum. arXiv preprint arXiv:2403.02967, 2024.
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint arXiv:2301. 2023.

---

Published as a conference paper at ICLR 2025
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. International Conference on Artificial Intelli- gence and Statistics, pp. 1313-1323. PMLR, 2021.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International conference on machine learning, pp. 5200-5209. PMLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv:1706.0060 2017.
Kanan Gupta, Jonathan Siegel, and Stephan Wojtowytsch. Achieving acceleration despite very noisy gradients. arXiv preprini arXiv:2302.055 2023.
David Harrison and Daniel L Rubinfeld. Hedonic housing prices and the demand for clean air. Journal of Environmental Economics and Management, 5(1):81-102, 1978. doi: 10.1016/
(195-0696(8))90000
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, 2009. ISBN 9780387848846. URL htttts::////oooo// httpb/oooss.oogg.....e.eoooooooe httpa/oooo.../ooooooooeoooooooa.
Julien Hermant, Jean-François Aujol, Charles Dossal, and Aude Rondepierre. Study of the be- haviour of nesterov accelerated gradient in a non convex setting: the strongly quasar convex case. arXiv preprint arXiv:2405. 19809, 2024.
Oliver Hinder, Aaron Sidford, and Nimit Sohoni. Near-optimal methods for minimizing star-convex functions and beyond. In Conference on learning theory, pp. 1894-1938. PMLR, 2020.
Geoffrey Hinton. Neural networks for machine learning. Coursera Lecture 6e, 2012. Available at https:// /tt::://wwww... http://wwwco.urrre..e wtt.://ere.eereeeeeeeeeereraaaaa
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerat- ing stochastic gradient descent for least squares regression. In Conference On Learning Theory, pp. 345-604 PMLR, 2018.
Rahul Kidambi, Praneeth Netrapalli, Prateek Jain, and Sham Kakade. On the insufficiency of isting momentum schemes for stochastic optimization. In 2018 Information Theory and Applica- tions Workshop (ITA), pp. 1-9. IEEE, 2018.
Donghwan Kim and Jeffrey A Fessler. Optimized first-order methods for smooth convex minimiza- tion. Mathematical programming, 159781-107, 2016.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to 1998.
document recognition. Proceedings of the IEEE,
Jongmin Lee, Chanwoo Park, and Ernest Ryu. A geometric structure of acceleration and its role in making gradients small fast. Advances in Neural Information Processing Systems, 34:1 1999- 12012, 2021.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. Advances neural information processing systems, 31, 2018.
Chaoyue Liu and Mikhail Belkin. Accelerating sgd with momentum for over verrpaaameeterzed learn- ing. In International Conference Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2025
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec- tiveness of sgd in modern per-parametrized learning. In International Conference on Machine PMLR, 2018.
Learning. pp.
Vitali D Milman and Gideon Schechtman. Asymptotic theory of finite dimensional normed spaces: Isoperimetric inequalities in riemannian manifolds, volume 1200. Springer Science & Business Media, 1986.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12):124003, 2021.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175:69-107 2019.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interssiencce, 1983.
Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1/k²). Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Compu- lational Mathematics and Mathemutical Physics, 4(5):1-17, 1964. ISSN 0041-5553.
Boris T Polyak. Introduction to optimization. 1987.
Marien Renaud, Jean Prost. Arthur Leclaire, and Nicolas Papadakis. Plug-and-pla image restora- tion with stochastic denoising regularization. In Forty-first International Conference on Machine Learning, 2024.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathe- matical Statistics, 22(3):400- - 407, 1951. doi: 10.121 4/111///////177729/00
Herbert Robbins and David Siegmund. A convergence theorem for non negative almost supermartin- gales and some applications. In Jagdish S. Rustagi (ed.), Optimizing Methods in Statistics, pp. 233-257. Academic Press, 1971. ISBN 778-0-12-6045500
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors, volume 323. Nature Publishing Group, 1986.
Karthik Abinav Sankararaman. Soham De. Zheng Xu, W Ronny Huang, and Tom Goldstein. The impact of neural network overparameterrizaton on gradient confusion and stochastic gradient de- scent. International conference on machine learning, pp. 1469-84779 PMLR, 2020.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprini arXiv: 1.11.188..33 66700, 2013.
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley- benchmarking deep learning optimizers. International Conference on Machine Learning, pp. 9367-9376. PMLR, 2021.
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochas- tic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pp. 3935-3971. PMLR, 2021.
Bin Shi, Simon S Du Michael Jordan, and Weijie J Su. Understanding the acceleration phc- nomenon via high-resolution differential equations. Mathematical Programming, pp. 1-70, 2022.
Mikhail Solodov. Incremental gradient algorithms with stepsizes bounded away from zero. Com- putational Optimization and Applications, 1 11:23-35, 1998.
13

---

Published as a conference paper at ICLR 2025
Weijie Su, Stephen Boyd, and Emmanuel J. Candès. A differential equation for modeling nesterov accelerated gradient method: theory and insights. Journal of Machine Learning Research, 17 (153):1-43, 2016.
Paul Tseng. An incremental gradient (-projection) method with momentum term and adaptive step- size rule. SIAM Journal on Optimization, 8(2):566-531, 1998.
Aditya Varre and Nicolas Flammarion. Accelerated sgd for non-strongly-conver least squares. In Conference on Learning Theory, pp. 2062-206200022 2126. PMLR, 2022.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. The 22nd international conference on artificial intelligence and statistics, pp.
PMLR, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. Gradient diversity: a key ingredient for scalable distributed learning. In International Conference Artificial Intelligence and Statistics, pp. 1998 2007. PMLR, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Zeyuan Allen Zhu and Lorenzo Orecchia. Linear coupling: An ultimate unification of gradient and mirror descent. In Christos H. Papadimitriou (ed.). 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LiPles, pp. 3:1-3:22, 2017. 2017.
SUPPLEMENTARY MATERIAL
These supplements contain additional details the numerical experiments, proofs of theoret- ical results, and some additional insights. In Supplement A we present additional details about numerical experiments and supplementary experiments. In Supplement B an optimization back- ground is provided for completeness. In Supplement C we present and comment related works. In Supplement D we provide simple examples of functions that do not verify SSG] or verify for a large constant. In Supplement E we provide convergence proofs for SGD (Algorithm IT. In Supplement
|F we introduce new convergence results for SNAG (Algorithm 2 without assuming that the holds.. In Supplement G we present convergence proof for SNAG (Algorithm 2 In Supplement[[] we provide the proof of the results presented Section 4 Finally in Supplement we give deeper explanations concerning the link between RACOGA and algorithms considered in this paper when applied to the problem of linear regression.
REPRODUCTIBILITY STATEMENT
Source code used in our experiments can be found in supplementary material. It contains README.md file that explains step by step how to run the algorithm and replicate the results of the paper. We detail our datasets, network architectures and parameter choices in Section A.2 The- oretical results presented the paper are proved in the appendices.
IMPACT STATEMENT
The present paper, from optimization point of view, aims to strengthen our understanding of the theory of machine learning. A good comprehension of the tools that are broadly used is important in order to quantify their impacts the world. Moreover, considering environmental impact, it is crucial to understamd the process that makes learning more efficient, especially accelerate current optimization algorithms, without necessarily using huge models.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL EXPERIMENTS AND DETAILS
This section presents additional details on the experiments for the sake of reproducibility. We also provide additional experiments for deeper analysis.
A.1 LINEAR REGRESSION
Algorithms and parameters For the problem stants. Indeed, f is L-smooth with L = N Amax
LR we can explicitly compute geometrical con- (Ei= a,a""). and each fi is L.-smooth with I = Amax (ata?) In the overparametrized case i.e. N < d, f is not μ-strongly con- vex. However, up to a restriction to the vectorial subspace V spanned by aN,). flv is -strongly -strongly convex. Therefore our experiments, in order to run GD, SGD and NAG (respectively Algorithms 6 1 and 7)
( Ammin (Ei- a:a?)
we chose the parameters respectively accord- ing to Theorem 6) | and In the case of SNAG (Algorithm ( in order to apply Theorem 3 we also need to know the [SC] constant Pk. where K' is the selected batch size. However this constant is hard to compute. The knowledge of [RAAACAA allAoo iterates would be sufficient, but we do not SNAG with this choice of parameters
know this path before launching the algorithm. Thus,
1 8= VULA
1 p AV L a=
1 I+
LA 7=
(16)
1+
where A > 1. In order to achieve better performance, provided that the iterates higher RACOGA] values, À can be chosen more aggressively, i.e. X smaller, as on Figure [b] De- creasing the À parameter leads to more aggressive, less safe algorithm, because it will increase 8 and in Equation (16). Taking a glance at Algorithm P we see that results in making larger gradient steps. Recall that larger gradients steps allows the trajectory to move faster, and eventually to converge faster, but steps that are too big will make the algorithm diverge.
areas with
BVG
log(4
loa
35.0 30
8
00.5
Gradient evaluations
RACOGA
Gradient evaluations
RACOGA
(a) Isotropic data
(b) Correlation within data
Figure 3: Illustration of the convergence speed of GD (Algorithm 6 NAG (Algorithm 7p. SGD (Algorithm [ and SNAG (Algorithm (2) with varying batch sizes K, applied to a linear regression problem, together with an histogram distribution RACOGA values along the iterations of SNAG. The stochastic algorithms results are average on ten runs. On the left, data are generated by a law such that they are fewly correlated, while on the right the data are generated by a gaussian mixture, such that some of the data are highly correlated. Note that the presence of correlation in data results in decrease of performance for SNAG (Algorithm 2 when increasing too much the batch size, whereas uncorrelated data results in an improvement of performance when increasing batch size.
we observed that contrarily to data generated uniformly onto the sphere, the presence of correlation inside data coincides with high RACOGA values and good performance of SNAG (Algorithm Z with batch size compared to other algorithms. Now in the same experimental setting, we study the impact of varying batch size. According to Remark 8 in the case of correlated data, we should observe a decrease the performance up to a certain batch size. On Figure 3b) we observe this phenomenon. We see that 10, and keeping the same performance. If performing parallelization, this results in 10 times faster computations. However, when increasing batch size from 10 to 25, lose performance, inducing
Batch size influence In Section 5.1
multiply the batch size by factor
15

---

Published as a conference paper at ICLR 2025
Algorithm 3 Stochastic Nesterov Accelerated Gradient Machine learning version (SNAG ML)
1: input: zo: by E IRd, 8 > 0, p E [0, 1]. (BA)DEN R
2: for = 0, 1,..... ..... Thit do
3: bn < pbn-1 + VK((nn11
4: I'n < Inn-
Vx (T(-11 + pbn))
5: end for
6: output: Fna
10
GD
2.5
SNAG À 0.25N
SGD
SNAG À =0.5N
NAG
SNAG À 1.ON
SNAG 0.25N
SNAG À 0.5N
log(n
SNAG À = 1.ON
2
0.0
0 Gradient evaluations 10
-0.5 0
80
RACOGA
Figure 4: Illustration of the convergence speed of GD (Algorithm NAG (Algorithm 7p. SGD (Algorithm[I I and SNAG (Algorithm 2 for the linear regression problem with the Boston dataset. The parameters of SNAG are choosen accordingly to Equation 16 Some RACOGA) values are high, while other also close the worst anti-correlation case 3.2 Note that SNAG appears to converge faster than the other algorithms when choosing small enough.
paralellization will not results in 2.5 times faster computation. This phenomenon often referred to as performance saturation, see Ma et al.] (2018); ; Liu & Belkin (2020). On Figure Bal we observe that conversely, increasing batch size improve the performance. Figure is thus consistent with our theoretical findings, see Remark
Under-parametterizaionn with realistic dataset The Boston dataset (Harrison & Rubinfeld 1978) concerns house pricing in the Boston area. This dataset can be used for linear regression, where we aim to predict house prices using 13 variables such as tax rates. There are 200 data, so 200 and d = 13, which means we are in under-parameteriized regime. In this case, we can hardly expect SGC to hold, as the noise of the gradient has no reason to be zero at the minimizers of f. On Figure 4 tackle the linear regression problem this dataset, and we observe that despite the under-paree parammttrraetti setting, SNAG (Algorithm 2 appears to outperform GD (Algorithm (6) NAG (Algorithm 7 and SGD (Algorithm D. RACOGA values be either very large (e.g. for aggressive, i.e. small A), but also close to 7 which corresponds to high anti-correlation In this under-parameterized regime, the role of RACOGAJ is less clear. possible explanation of the good performance of SNAG could be the variance reduction effect of momentum, see Gao et al. 20244).
A.2 NEURAL NETWORKS
For dataset (at, b E Rdd x R. we want to solve a classification problem formulated as Prob-
lem C
1 N
f(x) = N
Σ f((x): = N
CROSS(2;; b;);;
(C)
1=1
16

---

Published as a conference paper at ICLR 2025
Where CROSSO) is cross entropy loss, it is implemented in Pytorch with the function nn. CrossEntropyLoss)).
Classification problem In Section 5.2 considered two classification problems. The first one involves the classic CIFARIO dataset (Krizhevsky & Hinton 2009). that contains 60000 color im- ages (dimension 32 32) with 10 different labels. See Figure 5a to see data visualisation of the dataset, taken from Balasubramanian et al. (2022). This datasel serves as our correlated dataset. For the second classification problem, we generated data drawn uniformly onto the d-dimensional sphere, where d is the same dimension as the image of CIFARIO, i.e. 32 = 3072. We created different labels depending on the positivity of the first coordinate of each data, which remains to associate different label depending on which hemisphere belong each data, see Figure 5b for 3d visualisation. This dataset is named SPHERE.
75-
-25
-90
label 1
-19
-100
-35
(a) CIFARIO data vizualisation
Sphere classification problem
Figure 5: Illustration of the two classification problems we consider in Section 5.2 On the left part, wee see 2D vizualisation of CIFARIO data set, proposed by Balasubramanian et al. (2022). On the right, we illustrate SPHERE dataset the 3d-sphere, where each hemisphere correspond to different label.
Network architecture For the classification problem involving the CIFARIO dataset, we use Convolutionnal Neural Network (CNN, (CNN,LeCunn et al. (1998). For the classification problem involv- ing the spherical data, we use Multi Layer Perceptron (MLP, Rumelhart et al. (T986)). CNN are efficient architecture when comes to image classification, at is exploit local information of the images. However, this architecture makes less sense for our classification problem the sphere. This model indeed performed poorly in our experiment, and so our choice of a MLP architecture. We detail the architectures on Figure
Algorithms and parameters We ran the experiments using the Pytorch library. We used the Pytorch implementation to run the optimization algorithms, through the function torch. optD... This function contains a nesterov = True argument, which allows to run Algorithm 3 Note that this indeed formulation the Nesterov algorithm, see Appendix [.22] The detailed parameters used to run the experiment, determined by grid search, are displayed on Figure 2 are presented on Table together with the final test accuracy, averaged over 10 initialisations.
Single run and RACOGA along iterations As complement, we display on Figure 7 slightly different view Figure 2 On the left part of Figure Figure 7 we display the typical behaviour of one single run of optimization algorithms, namely without averaging for several initialisations. As we can expect, we observe a higher variability, although the general behaviour remains similar. On the right part of Figure 7a 7b] we displayed the evolution of RACOGA values along the iterations, instead of the histogram distribution Figure which does not keep any temporal infor- mation. For correlated data, we observe that RACOGA values decrease when iterations converge.
17

---

Published as a conference paper at ICLR 2025
Inout Layer [3072]
Input
32x52x3
Hidden Layer
Output Layer (2)
Output
Asia128
Rctx128
Convolution
Activation: ReLU
Activation: Linear
18010432
pooling
Adaptive average pooling
Activation: ReLU
Fully connected linear
S2x52e30
(a) MLP 401,730 parameters
(b) CNN 98,730 parameters
Figure 6: Scheme of the architecture of the MI. and the CNN used in our experiments.
MLP (SPHERE)
CNN (CIFARIO)
Accuracy test (%)
p
Accuracy test %)
GD
49.72
17.54
SGD
0.3
80.6
0.3
65.40
NAG
0.9
50.02
0.7
17.07
SNAG
0.1
0.9
88.73
0.05
0.9
70.88
Table Parameters (the learning rate and the momentum p) used to run the experiments presented in Section 5.2 together with the final accuracy test in percent averaged over 10 different initial-
izations. For precise formulation of the algorithms, see Algorithm 6 (GD), Algorithm [ (SGD),
Algorithm (NAG) and Algorithm 3 (SNAG).
This phenomenon can be interpreted as the convergence of the iterations to minimum with low curvature which is related to low RACOGA value (see Appendix [ for more details).
W aMM Wmmm
AAC
2011
3011
Gradient eva luations
RACOGA
Gradient evalustions
RACOGA
(a) SPHERE-MLP
(b) CIFARIO-CNN
Figure 7: Illustration of the convergence speed on run GD (Algorithm batch size N ). SGD (Algorithm[[ batch size 64), NAG (Algorithm 7 and SNAG (Algorithm batch size 64), together with display the RACOGA values taken along the path, averaged over different initializations. On the left, the right we use CNN, and the dataset used is CIFAR1O.
MLP, and data generated by isotropic law and fewly correlated. On
(Algorithm 4 and ADAM (Kingma & Ba 2015) (Algorithm 5) are popular algorithms when it comes to optimize neural net- works. RMSprop similar to gradient descent, at the difference that, grossly, it divides component- wise the gradient by average of the squared norm of the past gradients. There exists variant of R.Sprop that incorporates momentum. Adam combines both techniques of RMSprop and momen- tum, plus other mechanisms such bias corrections.
Comparison with ADAM and RMSprop RMSprop (Hinton 2012)
On Figure 3 compared to Figure 2 we add the training convergence curve and RACOGA values of RMSprop and ADAM. On the CIFAR10 dataset, both algorithms do not converge faster than
18

---

Published as a conference paper at ICLR 2025
Algorithm 4 Root Mean Square Propagation (RMSprop)
Input: a, B, > 0, 2o Rd
2: for = 0, -14
do
3: In Vx(
4: Un+1 f0
g)
5: In+1 In (n++ite
6: end for
Algorithm Adaptive Moment Estimation (ADAM)
1: Input: a, 32, > O, initial parameters 2g Rd ma Ug = 0
2: for π = O...., Mie do
3: In. (x(xn)
4: Mn+1 Bimn + (1 9m
5: Bn+1 = 320n + (1 32)9
6: Mn+1 1-8.-1
7:
En+1 1-82
8: En+1 In Ma+t1
9: end for
SNAG, and share similar RACOGA values. Interestingly for the SPHERE dataset, both algorithms are significantly faster than others. We observe that all the algorithms are, at the begining of the optimization process, stuck in a tray. SNAG steps out of this tray faster than SGD, and R.Mpprop and ADAM step out it even faster. One may think that the normalization by the average of squared gradients induces larger stepsize and boost the convergence speed, as in this tray the gradient values are low. The average test accuracy at the end of the training for ADAM (Algorithm (5 is 73% for MLP, 69.12% for CNN. The average test accuracy at the end of the training for R.Spprop (Algorithm 4h is 94.02% for MIP, 67.3 .7.31% % for CNN.
2.4
SCD
SAC
logiA
ADAH
Gradient evaluations
RACOGA
Gradient evaluations
RACOGA
(a) SPHERE
(b) CIFAR10
Figure 8: Illustration the convergence speed of GD (Algorithm 6 SGD (Algorithm batch size
64), NAG (Algorithm 3 full batch) and SNAG (Algorithm 3 batch size 64), ADAM (Algorithm 5) and RMSprop (Algorithm 4 averaged over 10 different initializations, together with an histogram distribution RACOGA values taken along the optimization path, averaged over 10 different ini- tialisations. On the left. we use a MLP to classify fewly correlated data sampled from an isotropic law. On the right we use a CNN classify CIFAR10 images. Note that ADAM and RMSprop are both better than other algorithms for the SPHERE experiment, they are not faster than SNAG in the CIFAR experiment.
Computation time Using the Python library time, the computation time needed to choose the best parameters for our two models (CNN for CIFARIO and MLP for SPHERE) have been saved. More- over, the computational time needed to generate Figures D and g is added to computational budget. We saved the computation time needed to train the models and to compute the IRACOGA] values, 10 times per algorithms (due to the 10 initializations) and for both networks. Note that for
19

---

Published as a conference paper at ICLR 2025
the stochastic algorithms, RACOGA was computed only every 100 iterations, because of the heavy computation time it demands. The experiments for the linear regression problem take less than one minute of computation. Experiments with SNAG, NAG, SGD and GD took approximately 4 hours. Additional experiments with ADAM and RMSprop took approximately 8 hours. Note that ADAM requires to tune hyperparameters with the grid search, making this step significantly longer. The total computation time needed for all these experiments is approximately 12 hours of computation on GPU NVIDIA A10 Tensor Core.
Additional datasets results ues for SGD (Algorithm I and SNAG (Algorithm 3) on various datasets, including hand written numbers (MNIST), pictures of clothes (FashionMNIIS NIST T Xiao al. (2017)) and Kuzushiji characters (KMNIST Clanuwat et al. (2018)) and hand-written characters (EMNIST Cohen et al. 2017)). The used learning rate for SGD and KMNIST. The learning rate of SNAG is 0.05 for MNIST and EMNIST and & 0.1 for Fashion MNIST and KMNIST. The momentum of SNAG (Algorithm 3 p 0.8 for MNIST and MNShi and 0.9 for KMNIST and EMNIST. These quantities have been chosen after grid search find the parameters that maximize the test accuracy of the learned model. There were 3 epochs for the training.
On Figure 9 present the convergence
and RACOGA val-
0.1 for MNIST and EMNIST and 0.25 for MNSST
Note that the RACOGA values are large for all these training paths. Moreover, in all these scenarios, we observe that the convergence of SNAG is faster than the convergence of SGD, although it is less clear for KMNIST. These additional experimental validations support our theoretical results.
SNAG
05-
SNAG
login
log
Gradient
RACOGA
Gradient
RACOGA
MNIST
(b) FashionMNIST
SGD
SGD
looii
logtn
2500
13.4
200
2500
13.4
200
Gradient evaluations
RACOGA
Gradient evalustions
RACOGA
(c) KMNIST
(d) EMNIST
Figure 9: Illustration of the convergence speed of SGD (Algorithm and SNAG (Algorithm batch size 64), averaged over 10 different initializations, together with an histogram distribution of RACOGA values taken along one optimization path. We use CNN described on Figure 6b only changing the input layer with the dimension of images x 28 x 28. Note that SNAG is faster than SGD, although is less clear for KMNIST, and the RACOGA values are large for all these datasets.
A.3 LOGISTIC REGRESSION
On Figure 10 we present the convergence curves and RACOGA values for SGD (Algorithm [ and SNAG (Algorithm 3 images extracted from CIFARIO. Images of CIFAR10 have 10 classes and are of dimension 3, 072, so the logistic regression has 30, 730 parameters. In order to observe the convergence curves under-parametrrized regime, the optimization all the CIFAR10
20

---

Published as a conference paper at ICLR 2025
dataset (60, 000 images). To analyse the over- wer-parametrized regime, the optimization
subset of 10, 000 images from CIFARIO. The learning rate SNAG is 0.2 and the momentum p 0.7. The learning rate for SGD is 1.0. These parameters have been chosen after grid search to find the parameters that maximize the test accuracy of the learned model. There were epochs for the training.
Note that for logistic regression the RACOGA values are positive but small (compared to the deep learning experiments). Therefore, do not observe any acceleration of SNAG over SGD.
SGD
SG0
14
SNAG
3B
login
logit
2500
0
Gradient eve eveluations
RACOGA
Gradient evalustions
RACOGA
(a) Under-parametrriedd (60, 000 data)
(b) weer-paameetrized (10, 000 data)
Figure 10: Illustration of the convergence speed of SGD (Algorithm I and SNAG (Algorithm batch size 64), averaged over 10 different initializations, together with an histogram distribution of RACOGAA taken along one optimization path. We run a logistic regression (30, 730 param- eters) images extracted from CIFAR10. Note that SNAG and SGD have the same speed, which may be caused by the non convexity of the problem, or by the fact that the RACOGA values might be not large enough to observe an acceleration of SNAG.
B BACKGROUND: CONVEX OPTIMIZATION AND THE NESTEROV ALGORITHM
In this section, we give the reader some optimization background for completeness of paper. First, we expose known results related to the convergence of the deterministic counterparts of SGD and SNAG, and then we exhibit different forms of the Nesterov algorithm that can be found in the literature.
B. PERFORMANCE OF GD AND NAG
We present the speed of convergence of GD (Algorithm 6) and NAG (A AIgorithm 7). lowing theorems well known results demonstrated by Nesterov (1983 2018
The two fol-
Algorithm 6 Gradient Descent (GD)
1: input: vi Rdd
2: for 0, 1, ...., Al do
3: Fn-11 = In -VV (xx,)
4: end for
5: output: Vnn.
Theorem 6. Let ff Bd + R be L-smooth, fEEN be generated by Algorithm 6 with stepsize t. Let v. IN the smallest integer such that Vn Ve, f(x,) f" Se.
1. If. f is convex, have
L [i0
x=
V. <
(17)
2. If J is j-strongly convex, we have
21

---

Published as a conference paper at ICLR 2025
Algorithm 7 Nesterov Accelerated Gradient (NAG)
1: input: 20: 20 E R2d 8 > 0. 8 [0, 1], (an)nEN [0. 1JA, (NADDEN R
2: for = 0,1,..... Thit do
3: In <- Rn +
0p)22
4: 2n+1 Yn vVf(Hn)
5: En+1 + Bān + (1 8)yn - T/ (1(m)
6: end for
7: output: Znzza
L 1
f(xo)
Ve log
(18)
The result for convex f can be found in Garrigos Gower (023))
Theorem 7. Let f Rd RR be L-smooth, (nnJ be generated by Algorithm 7 with stepsize
8 E. Let V. E the smallest integer such that vn 2 Ve, f(xa) - -f" S
1. I is convex, choosing an
n-1 n+I
3 = 1, I
nt1 2
we have
2
20 xz
V S 2T.
(19)
VE
2. If f j--strongly convex, choosing on 1 =1=
V T/
vet. we have
L V
2(5(3o)-
Ve S
log
(20)
By comparing the convergence speed for convex functions given by Theorems and NAG is faster than GD as long as the desire precision is small enough. As L 2 μ. considering μt --strongly convex functions NAG is always at least good as GD. In practice, in particular for ill-conditioned problems, we can have & L. In theses cases, NAG is significant improvement over GD.
Optimality of NAG Note that NAG (Algorithm 7 not only outperforms GD (Algorithm 6 also offers bounds that are optimal among first order algorithms when minimizing strongly or non strongly convex functions, in the sense that it is possible find examples of functions within these classes such that these bounds are achieved up to a constant (Nemirovskij & Yudin 1983).
B.2 THE DIFFERENT FORMS OF NESTEROV ALGORITIM
There exists several ways of writing Nesterov momentum algorithm, that can be linked together (see e.g. Defazio (2019) for 6 different forms in the strongly convex case). Different research fields are used to their own typical formulation.
this section, we present formulations that can be found in the optimization and machine learning communities. Within the optimization community NAG (Algorithm 77) (Zhu & Orecchia [0177: Hinder et al.) (2020) or NAG 2S (Algorithm (9) (Su et al.) 2016 Aujol et al. 2023 2024) are often used. The machine learning community rather used to the formulation of NAG ML. (Algorithm 8). fact, this last algorithm is the version implemented in Pytorch with the function prrch.pptim.SDD) with the argument nesterov True, up the condition that T = 0.
The links between the several forms have been studied previously (Defazio, 2019 Lee al. 202 As our results are related to the three points version of NAG (A (Algorithm 7). we state now results that allow generate the same optimisation scheme than Algorithm 7 with Algorithms 8 9
Proposition 3 (Hermant et al. ). ). Consider (In)eN and (UN)EN generated by NAG (Algo-
rithm 7. The same sequences are generated by Algorithm with choice of parameters
an On 18n-15 bn = 0x,)
7n-1
an-13n-1 -1)
Og 1 ap-1
(21)
an-1
22

---

Published as a conference paper at ICLR 2025
Algorithm 8 Nesterov Accelerated Gradient Machine Learning version (NAG ML)
1: input: zo: by E IRd, 8 > 0, p E [0, 1], r E IR, (Mn)NEN E R
2: for = 0, 1, ..... Thit 1 do
3: bn f- pbn-1++ +1 f
4: Zn f- In-1
(V (In-1) + pbn)
5: end for
6: output: 2razs
Algorithm Nesterov Accelerated Gradient Two Sequences version (NAG 2S)
1: input: 2g E IRd > 0, (an)nEN [0, 1| (bA)REN E (0, 1JN
2: for 0, 1........ Die do
3: V/ <- In + (In In In-1) 1) + bn (In vn-1)
4: #n+1 f yn (V))
5: end for
6: output: Z4z
Note that Algorithm have constant parameters in the Pytorch implementation. The link between Algorithm 7 and Algorithm can be deduced from Defazio (019) in the case when 1 for Algo- rithm g We demonstrate a generalisation of this result for F and we present it in Proposition 4
Proposition Consider (Un)eeN generated by Algorithm Algorithm
7 The sequence (Rn)neN generated by
8 is the same as (yn)neN with choices of parameters
p a8, s(1 + a(3 - 1)) - (1-a)) a)
(22)
aBs
Proof. Our strategy is to write both algorithms in a one point form algorithm to compare the param- eters.
(i) Algorithm 8 By the line 4 of Algorithm g
we have the relation
Fn In
by
(23)
ps
P
Now replace the b, and - in line of Algorithm
thereby
Vf(xn-1) = Inn In-1
V((an)2) + (1 (1)-))V((.-.).
(24)
ps P
ps
p
We multiply both sides by -ps, and rearrange
= In-1 + p(En-1 xn-2) sV Ps -
ps
(25)
In + p(=n-1 2n - [V - ps (V - vf(xn-2)) + Tps f
(26)
Interestingly, we recognize with the three first terms on the right hand side Polyak's Heavy Ball HB equation (Polyak] 1964)
In In-1 + p( 2n-2) (x
(HB)
The ps (V 2 term is often referred as gradient correction term Shi al. 2022 and is characteristic of the difference between Polyak's 's Heavy Ball and Nesterov's algorithm. damping term, and is often needed obtain the tightest convergence results (Kim & Fessler 2016)), also to achieve accelerated convergence outside of the deterministic convex realm (Hermant al. 2024).
The last +7ps V (x is considered
(ii) Algorithm 7 We set that Vn E N, on = a E [0, 1]. and f/ = 1 > 0. First, combining lines 3 and have:
4 of Algorithm
Yn a.E, (1 a)zn = a(yn-1 sVf (1 a)
(27)
23

---

Published as a conference paper at ICLR 2025
Hence:
Zn yn 0Yn-1 + as 1(3n-1)
(28)
1-a a
Now we inject this expression in line 5 of the Algorithm
Un+1 ayn + a f(m)) Un O + as ass (VV
0yn-1
-8ym -V (29)
1
a
Then, multiply both sides by 1 and rearrange to get
Un+1 at (y + Byn Boy aB +(1 - (1 - 3) - v)))
(30)
(31)
By simplifying and regrouping terms, we get
Un+1 = yn + o:3(yn 1m- (VI(U)) - a.3 (V/(vn) - vS((n-1))
vVf(Un) a3sV ((y,) asV (1))) a))V yn + (3 Vn-1) vV (y)) aßs (Vf(yn) - vf(mn-1)) +s(1+a(8 1)) - (1 a)m) V f(nn).
(32)
(33)
By comparing, Equation 26 and Equation 33
we can identify the different parameters
p o.
(34)
Tps s(1 a(3 1)) -ann
(35)
So, we have the correspondence
p aB
(36)
s(1 + (3 1)) (1 a)n aßs
T
(37)
Extension to Stochastic Nesterov algorithms Proposition and Proposition 4 can be extended to the stochastic versions NAG (Algorithm 77 NAG ML (Algorithm g and NAG 2S (Algorithm 9
where the f terms are replaced by Vk. The same correspondence between parameters these algorithms holds.
C RELATED WORKS
C.I GRADIENT CORRELATION CONDITIONS
In this paper, introduce assumptions related the average correlations of the gradients of the functions that form the sum in problem (FS), namely
Vx E Rd
(V)()), VL((O)) 2 O.
(PosCorr)
ISKIEN
EISKISN (i(r)) Vz)())
Ve E R. Z
2 -c
(RACOGA)
where X fr Rd (1. (I....,N} NJ. [x))l 0}. PosCor is special case of RACOGA with the choice c = O. The key role correlation between gradients has been already observed in previous works, through related but different assumptions.
24

---

Published as a conference paper at ICLR 2025
Gradient diversity Yin et al. 2018) following ratio
Gradient diversity is defined at point R as the
Vf(())
Ax))
(GradDiv)
i= [x()]
This quantity is closely related to the SGC condition. Indeed, for batch size 1, we clearly have
Σ [+(())
S N sup
(38)
ZER4
Thus, assuming SuPxER* ((x) < +oc, f verifies SGC with < N sup A(x). The authors show that increasing batch size less efficient with ratio depending on the values that NA)()) takes along the optimization path. The smaller these quantities (high correlation), the smaller this ratio. Conversely, the higher it is (low or anti correlation), the higher the ratio is, inducing large gain with parallelization of large batches. GradDiv is another measure to quantify gradient correlation. Indeed by developing the squared norm, we have the relation
-1 Eisicien (V((()). V((()))
(39)
E V((c))
However, RACOGA appears naturally in our study of the SGC and is a direct measure of the correlation between gradients.
Gradient confusion (Sankararaman ef al., 2020) f has gradient confusion v 2 at a point R
[f) 2 (1......7.
(GradConf)
The authors show that for some classes of functions and considering SGD, satisfying this assumption allows to reduce the size of the neighbourhood of stationary point towards which the algorithm converges. Also, they study theoretically and empirically how the gradient confusion behaves when considering neural networks. They show that practices that improve the learning, such as increasing width, batch normalization and skip connections, induce a lower gradient confusion at the end of the training, i.e. [GraCConf is verified with small r). In other words, well tuned neural networks avoid anti-correlation between gradients. However, compared to (oRACCOGA) GradConf asks for a uniform bound over the correlation of each pair of gradients, which can be much more restrictive.
C.2 LINEAR REGRESSION ACCELERATION RESULTS
We mentioned in the introduction of this paper that there exists positive results concerning the pos- sibility of acceleration considering the linear regression problem (Jain et al.) 2018 Liu & Belkin 2020 Varre & Flammarion] 2022). However, setting is bit different. Indeed, we consider the finite sum setting, while they consider the following problem
H ( x) 6)3
min P(x), P(x) == (a
(40)
SER
They assume that they have access to a stochastic first order oracle, that returns the quantity
P(x) = ((a, b)u
(41)
where (a, 6) ~ D. Noting H B(a, (aa") they denote R²2 and v the smallest positive constants such that
E ||aa| R2 H. (( (at.)--laaali Ilaa
RH.
(42)
Finally, they note μ the smallest eigenvalue of H which is assumed to be invertible. and x.
n2a In
this setting, there is interpolation if there exists xx Idd such that almost surely, b = (x .). Under noting The the algorithm iterations, the convergence speed of GD (Algorithm
Assumption [
of the order O Pit while momentum style algorithms allow to have O(e v convergence (Jain et al.] 2018: Liu Belkin 2020). The acceleration is data dependant. In particular, fixing the distribution be uniform over the orthonormal basis (ei,-..,ea), one have ň and there
25

---

Published as a conference paper at ICLR 2025
no acceleration. Our results (Example 3 acceleration result, to the case of convex functions with orthogonal gradients. However, the ideas behind those results and ours different, and Ä is not correlation measure. According to Jain et al. (2018), & measure the number of a, we need to sample such that the empirical covariance is close to the Hessian matrix, H.
Theorem 5 extend outside linear regression this non-
C.3 SGC RELATED CONVERGENCE RESULTS
The linear convergence of SGD under variation of SGC, for smooth convex and strongly convex functions, has been addressed in (Schmidt & Roux 2013). Later, convergence of SNAG type algo- rithms under strong growth condition, for functions that are convex strongly convex, also attracted interest. In this section, we discuss how these works relate to Theorems
Vaswani et al. (2019) As mentioned in Section the bounds of Theorem 3 were already achieved by /aaswani al. 2019). It was achieved with a quite unusual formulation of the SNAG algorithm, which is equivalent, to the following one
Algorithm 10 /Vaswani al. 2019)
1: input: To = 2g E Rd > 0, B E [0, 1]. (an)EEN E [0, 1P, (DM)EN E R In(.) stochastic approximation of (-) at iteration
2: for = 0, 1, ................................ A4e do
3: In u + an.)
4: #n++1 = yn sgn (yn)
5: 2n+11 82n + 8)yn "/n 8gn
6: end for
7: output: Tna
For L-smooth, and such that SGC is verified with constant p. the bounds of Theorem are verified considering SNAG /Vaswani et al. 2019) with the following parameters:
If f p-strongly convex:
us
VI
Bn =1
bat1
Vusp'
(n+1)/2'
ps
In b,b 18
an+1
(1+1)/2
On
3n 22
a
PL
us
If convex:
1
+
0z
4
ant1 /sp
2
In8
On
7n8 + a2
pL
In the strongly convex case, intermediate sequences of parameters (ax) and (bw.) appear. In the convex case, the sequence (7x) is defined with a recursive formula. Our different proof of Theorem does not make these features appear.
Gupta al. 2023
Another line of research leads to similar expectation result to ours, using AGNES (Algorithm [.), and so with a different proof. The authors of Gupta et al.) (2023) also get almost convergence, nevertheless without convergence rates contrarily to Theorem
26

---

Published as a conference paper at ICLR 2025
Algorithm 11 Accelerated Gradient descent with Noisy EStimators (AGNES), al. (2023)
input:f (objective/loss function), 2o (initial point), 10 (learning rate), 1j 10 (cor-
rection step size), = 0.99 (momentumm) N (number of iterations)
2: no +-
3: for 0, 0.1..... N do
4: In. -- Vof(an) (gradient estimator)
5: Un+1 t p(vn 9n.)
6: #n+1 t In + atn+11 - 119n.
7: end for
8: 9N + -VN((IN)
9: EN t- IN 79N
10: output: NN
D SOME EXAMPLES WITH CRITICAL STRONG GROWTH CONDITION CONSTANT
In this section, we show that even for some simple examples, the SGC constant can be very large or not existing, justifying that finding interesting characterizations of it is challenging problem.
D.I LARGE P1 WITH LINEAR REGRESSION
We consider the function
1 1.1 f(x) 2 (e1, + (a, x)
2
=f((()) f=())))
where ei (1, =1,e). We have Vf((z) (e1, and ff((x) (a, Assume
To = (-g. A). We have
vf(20) -1, (1,0) e _ -11
1
(43)
8 2 11,1 2 )=).
(44)
Thus obtain
22 [Vf(2))]1
1 1).2).
7 (111))2+ ((1 +)2
(45)
whereas
2 e2
E[| v (2x) =
(1 ブ |1 + ="))
(46)
8
2
Simply note that with the choice 1, we have Thus
|
(ro
A 18.
while E[| V
=2 +
o(e2)
( (z
(47)
So the strong growth condition can be arbitrarily large as & vanishes.
D.2 NON CONVEX FUNCTIONS SUCH THAT P1 DOES NOT EXIST
We consider:
f(x) + ((()))
where x = (2) R f1(x) ](1 tanh(x2)) f2(x) [ax + tanh(x2)) We have:
(z: (x1 tanh(x2), (m - tanh (22)) tanh?(2z)))
(48)
fz(x)) (x1 + tanh(xz), (mn tanh(2>)) -tanh3
(49)
27

---

Published as a conference paper at ICLR 2025
Consider the line y (0, yo), you E R. We have:
V (v) (- tanh(yo), tanh(3)) tanh (36))) tan))(y)))
(50)
V f2( (tanh(yo), tanh(yo) tanh (vo)).
(51)
Then:
V - 2 (V) V/2(v)) - (0, tanh(y0) - (anh(yo)
(0,
(52)
Ivol +
However, we have Vf( - (-1.0) and V12(1) - (1, 0) as you - +00. Thus, for any P1 0, the SGCCiiittion is not verified when considering the whole space R??
E CONVERGENCE OF SGD
In this section, we prove convergence results of SGD (Algorithm D stated in Section 3 namely
Theorem and Theorem 2 Also, Subsection E.2 we present a convergence result for SGD under SGC and we justify that it is not a relevant result in order to compare the convergence speed of SGD and SNAG (Algorithm 2
PROOFS OF THEOREM AND THEOREM
We can deduce Theorem Theorem by respectively adapting the proof from Garrigos & Gower (2023) and Sebbouh et al. (202T). We can not directly apply their original results because their setting is slightly different: in problem (FS) their convexity assumption holds for each fú while in our case it solely holds over the whole sum. In both expectation and almost sure cases, the core
Lemma 6.7 in Carrigos & Gower 2023). and Lemma 1.3 Sebbouh et al, (202T). These two lemmas do not hold in our setting. We will use instead the following result.
Lemma is to bound E || x (>:))? which bounds the variance of the estimator.
Lemma 2. Under assumptions
we have
E [[Vx(>)1P] < ([()) 1*).
(53)
Proof. Let x Rdd Consider fixed batch B with |B| K. We note fB(œ) 1 Eien
ffb(z) = 3 ELEB Vf((.). We first show that fB is Eien In -mooth.
Ya,y Rd, [[V - vfa(i)ll
[V Vf((i)l
(54)
K
EB
<
Li|lx
yl1
(55)
K
BEB
Eien B Li
yll-
(56)
K
The first inequality uses triangular inequality, the second inequality uses the assumption that each fi is L.-mootth i.e. [[V]; ((((i) < La|l= - y/|- Now, is well known that if In is Eie
smooth, fixing xx E arg min I we have [[)/((>)]| < 2 Enng Li (fn(x) fn(x") )), see Nesterov
K 20088 page 30. We upper bound this quantity uniformly in the constants L; over all the batches.
EiEB Li K
(fe(z) f=(x*) (L())(f(()) fx((*).
(57)
where [uk)= == max =' (
EieBy Lx). Now, we get back to the random variable V (.), we take the expectation over all the batches of size K, and get
E [[Vx(()]]]] < 2L
Σ
K (filz) - min fi)
(58)
LEB
28

---

Published as a conference paper at ICLR 2025
Note that E such that x" E arg min f. for all I N, which implies
LiEB f((x)) f(x). By interpolation (Assumption 1b.
there exists x" arg min
E
min fr =
Σ f((=") f(x))=)=--))))))) f. LEB
(59)
K
K
IEB
Proof of Theorem 1 Now to prove Theorem 1 note that the same proof as for Theorem 6.8 and Theorem 6.12 from Garrigos & Gower (2023) holds, replacing their Lemma 6.7 by our Lemma 2 setting in their prool 0 0 (Assumption D and replacing their 2C, by L(K). allowing in our case
to take stepsize S x instead of their I in the convex case, and L(K)
instead of their
22, in the strongly convex case. Note that for the convex case, the e-precision is actually reach with the sequence Fn := En Ti. i.c. we get number of iterations such that E [f(T,) [*] S
Proof of Theorem For the case of a convex function, the almost sure result from Sebbouh et al. (202T) follows from a decrease in expectation. by our Lemma As for the result in expectation, Lemma 2 allows us to choose S L The rest of the proof follows as theirs, as no supplementary assumption is needed in the interpolated case (Assumption D. For the case of strongly convex functions, we apply the same proof as for Proposition fixing En = || x 1² where xt E arg min f with 8 LiRi"
obtained our case replacing their Lemma 1.3
E.2 CONVERGENCE OF SGD WITH STRONG GROWTH CONDITION
Theorem D states a convergence result for SGD (Algorithm I without making use of the strong growth condition. It is however possible, done in Gupta al. (2023). In Thcorem g we give very similar result.
Theorem 8. Assume f is L-smooth, and that Vx verifies the SGC for Pk 2 1. Then SGD (Algo-
rithm with stepsize s Px
1 allows to reach an e-precision at the following iterations
n 2 pK |1:0- - x=1 (f convex).
(60)
n 2 PK log 2 (25(z0)
L
(ʃ p-strongly convex).
(61)
Proof. These results be obtained by adapting Theorem 3.4 and Theorem 3.6 from Garrigos & Gower (003). Indeed, the two equations from their Lemma 2.28 can be adapted to our case in the
following way, Vx E Rdd
E B[r(x f (x(x) f(0) S (1 PKSL
[f
(62)
Then, proceeds fixing s = Px from their Corollaries 3.5 and 3.8.
their proof just replacing the condition < L by S 1
pxt. The conclusion
It is straightforward to compare these bounds with those of Theorem This comparison indicates that the bounds of SNAG always outperform the bounds of SGD. The only exception that could occur is in the convex case if || x=" < 1, i.e. if we start close from the minimum. Making such conclusions would be misleading. Indeed in some cases, the characterization of Theo- rem & is suboptimal compared to the one of Theorem
[ Consider the strongly convex bounds: we
L log 2 f(mo) -f"
(Theorem & with 4 Lmax log f(z))=")
then compare PK ş
(Theorem Now,
the question is:
How do compare pie L. with Temax?
29

---

Published as a conference paper at ICLR 2025
We recall the example of Section D.I that is
1,1 f(x)
1
2 (e,, x) x/²² f + (a, x))
(63)
= (c(
where = -1,0), a = -1,E), > 0. We already computed the gradient, that is
1 vf(z)
1 (e1. 2)) 61 + (a, x) a.
(64)
One check that the Hessian matrix is
2 8 v²)(x) - E E²)
(65)
The L-smoothness constant the larger eigenvalue, that (55 + + +2 1 ols).
Moreover, L(1) = Lmax 1 + e². Now, we saw Section D.I that Pk at least of the order O (2). Thereby, for small values of E, we have L > L()), inducing the bound of Theorem is significantly suboptimal. Therefore, Theorem is more relevant than Theorem 8 to compare SGD and SNAG convergence speeds.
F CONVERGENCE OF SNAG WITHOUT STRONG GROWTH CONDITION
In this Section, we derive finite time convergence result in expectation for SNAG (Algorithm 2 without assuming SGC. In this case, for Theorems 22
the bound over the noise is derived from
the geometrical properties of the functions.
Lemma 3. Assume f is such that assumptions
2 hold.
If f is p-strongly convex, have
E
22(((K) - -(((()))
(66)
If ff is convex, we have
E
- Vx(=))]] s -
(f))) f*).
(67)
We prove Lemma 3 in Appendix
R.3 We note L the smoothness constant of f. Under assump-
tion 2 we have T. 1/ EN
La (())-
Theorem 9. Under Assumptions 7 and 2 SNAG (Algorithm 2 with batch size K guarantees to reach an e-precision (2) at the following iterations:
If f convex, 8n 2L nt1 On
- Th 1 Lixs
3 1,
4kix1
1100 x x=112.
(68)
If f is p-strongly convex, s (TTx) = B 11 (Tqk)-W) w) 11 (I) a
14 1 (L(K)
2 JaRg log ((f(2a))("))
(69)
In this Section, denote F, the o-algebra generated by the + 1 first iterates {zr)n generated by SNAG (Algorithm 2), f.e. F,, = a ( R.)) Also, we note E,,[-] the conditional expectation with respect to F,..
30

---

Published as a conference paper at ICLR 2025
Comparison with the bounds of Theorem I on SGD (Algorithm))
1
f convex. In this case, the bound for SGD of Theorem 1 is
2 2 [(K)
100
x" 2=1
This bound for SGD always better than the bound of SNAG from Theorem 9 However this comparison would be mislcading, Theorems 3 show that in the convex case, if aiming for a small enough precision E, SNAG's bound can always be smaller than the one of SGD.
f strongly convex. In this case, the bound for SGD of Theorem is
n 2 Tu log
2 f(2z)) -f*
The bound on SNAG from Theorem is better if L0g I 3. In realistic setting, L(x > 1. n In particular if f is quadratic strongly convex, to ensure that the bound of SNAG is better, we need to ensure that Amas
< 4 where Amax and Xuii are respectively the highest and the lowest eigenvalues of the Hessian matrix of f.
Awin 3
Using Assumptions T2 to study the convergence of SNAG almost always leads worst bound than SGD independently of the value of L(K), which is misleading. 'his is because, in this case, we have to take safer parameters for SNAG. For example in the convex case, 8, - in order to ensure convergence, compared to the Theorem using SGC (Theorem 3 where 8n
> O. This means that this is the [SGC characterization of the noise that allows to stabilize SNAG and which tells us how to chose parameters such that the convergence of the order O (n ²) Our results of Section 4 indicate that what is behind, in the finite sum setting, is the question of measuring the correlation between gradients, that is encapsulated within the SGC
Comparison with Theorem 3 Compared to Theorem that makes use of SGG in Theorem 9
we had to choose more conservative parameters in order to ensure convergence, leading to similar convergence bound as for SGD (Algorithm D. The comparison of the bounds of Theorems 3 are
similar the ones of Remark 3
Remark 9. In Remark 3 compare SGD and SNAG under different assumptions, in the sense that we assume that the SGCSSGChho holds when studying convergence of SNAG, but not not SGD. In Section E.2 see that using SGC to study SGD leads convergence bounds that are always worse than for SNAG, which is misleading. In this Section, with Theorem 9 we show that not using SGC when studying SNAG leads to an opposite phenomenon, with bounds for SGD that better than for SNAG, which is also misleading. Indeed, in particular, as seen in Remark 3 in the convex case, using SGC to study SNAG allows to have acceleration over SGD in finite-fime, as long as we for small enough E e-precision. Also, in our experiments, e.g. on Figures 2 we see that both cases are possible, namely SGD outperforming SNAG or SNAG outperforming SGD.
almost always
F.1 PROOF OF THEOREM 9 CONVEX CASE
We first recall the SNAG algorithm (Algorithm with step-size 8n and B 1
In Un (1 an)zn
Øn+1 Yn 5n V Vx(up (((yn)
(SNAG)
2n+1 Zn 17 Vx (yrs)
with (-))) defined in 1
1
1
1/2 V x (y.))1 + nm(x" .n, vx(Um)
2 2n
2
2 2| xx
x=12
(70)
||2m
x= x01
1/2
| x (1x))11 + mnfo" - yn. Vxc (yn))
(71)
2
+ 7/1
On
(In - Mn. {((y))
(72)
On
31

---

Published as a conference paper at ICLR 2025
Taking the expectation, using, under the assumption 8n 1. Lemma 4 we have
En
2n41 x=1 - 25ل1 x=11²+ 7m (x Un. (f(n))
(73)
(In yn vf(yn)) + Nh En [f(ym) - f(xn+1)] + En [V [x(wn)1 On
+ 17p
On
Sp
(74)
Using convexity of f on both scalar products, we get
Enn
|n+1 - x=11²=
nh
(f(In+1) - 5r) S 2 1 2²113= + on
an (f(xn) ((f(n)) fvn)) (75)
8n
an
The
+
m/
(s(yn)- - 1²) + En |[][(u)) - x
(76)
8n
In order to bound En | /IV5())) vx(2x)11
we use Lemma 3
En
Za41 - x 11+
nh (f( -
14)
S
2 Zm
x=1
+ 11
On (f(#n) - -r)
8n
On
+
the
On
In + 2 L(k) ((()))-F )-)-
8n
On
(77)
We set
The C
-- (n + 1)
an
C n. L(k)
Oa
Sn L(k)
On
for some positive constants C and a. We want to have a to be the highest possible, while having the factor behind (f(,) - f*) non-positive. We have
n C L(K)
Can (n+ 1)
(n + 1)2 + 1n 1
(78)
[(()
8n
And then
On
C n2
an
1 C n2
(79)
O'n
L(K)
an
Tn L(K)
On
C
na
(80)
1-an
V
LiKY (n + 1)
We plug the above equations the factor behind (f(y)) -r)
1/
17
O'
-m + 2n
C.
(n + 1)a
L(k)) na
C
(81)
Sn
an
L(k)
Csn
(n + 11 + 2nn + 1)a0
(82)
V L(K)
C.
LiKi
(n+1)o- 10=-"=-n= 1 -
(n +
(83)
L(K)
C
+2s, (() (1)))
(84)
Now, we note sn
C. (x+1)a
Then, we have
1 On
on + 21)
C L(K)
(n + 1)aa n nn
C (n -
V
11+
8p On
+
(i
(85)
32

---

Published as a conference paper at ICLR 2025
We have to ensure that the positive term not of larger order than the negative ones. We have (n + 1) n zo ana=!. So, to have that this term is controlled, we need to have
2( 1) aa 3 2 2( - (3
(86)
The second constraint implies S 8. As want to be maximal, we set =B.
The first
constraint implies a + 3 S 2, we get a = 3 = 1. Plugging these values into Equation (85)
C (I-Voo C
1/1
On - 17 + 2m L(k)
C
11
+ +2L 0.
1/n
= 0 = L(K)
(87)
Sn 1 an
=1+ (T)))
(88)
C
CiL(K)
(89)
(1)
Cylay (1) is maximized at C1 = 2L(K) 1 = C =
We choose C1 such that C is maximal, and
8.
So we have
8n ()) n 1 Th (L(
(90)
and On
Note that as L(K) 2 L. this choice of sn satisfies the constraint Sp t. needed to apply Lemma With these choices of parameters, taking expectation
Tuxyy nt 3. so On n42
T-on
on Equation we have
E
2 znt1
- -f)) x²1 2²11²+ + (n + 1) (f(n+1) 8L(K)
< E
2 1m
x²1²²
n 8L(
(f(zn) - f(xx))
(91)
By induction, we get
[n+1 - x² 111 (n + 11
1 =-1100 - x²1
(f(xx+1) - -f) SE
[ 11 x²113]
(92)
SL(X)
Now, as 11 - x²112 + (a+1)
(f(In+1) -f)) 2
(n+1) (f f(xn+1) - ff),, we get
8lag
8L(K)
4L (L((K)
E [( - (n + In - x x11
(93)
We see that, compared the case where assumed SGC where had decrease of the order O (n 2n) the decrease here is of the order O (n-1). In term of s solution, it leads to
4L(K) |20 x²1
(94)
F.2 PROOF OF THEOREM 9 STRONGLY CONVEX CASE
We use the following Lyapunov function.
En = f(za) - fr + 11 x=1
/ 2
(95)
Proceeding to the same computations as in the proof of Theorem arrive to Equation (148), namely
3 in the strongly convex case,
E, E., 1| 3E,, + E, -f - -f²) (1 B)ll,, =x11
(96)
2 5191 - 38) ( 1 1lum - 1nl1
+ H Enn
| (v.))1))
2
a,87//
(E (x(um)
In an) - pn(Enn (V((2))) x²)
1
33

---

Published as a conference paper at ICLR 2025
Recall En V (un))
= Vf(n). By Lemma 4 and Lemma we respectively have
En (Vm)))
En (((())) - f( + 2 [VV V [x(n))13
(97)
8n
and
E
[V))) V S ((( (ff((m)) - f-).
(98)
So, by combining the two previous equations, we have
En [IVx(UN)1)]
- 2 Bn ((f())) ) - f(zn+1)))))) ((L())
- (f((m) - f*)
(99)
Now, we inject this in (96), also using strong convexity.
En En+il S BE, + En (x - - 33-3(ff (f(2m) - -²) + 11 71 - 3)11yn - x²11 (100)
+ 1 E,, (J(a) - [(xn+t)] + 2pur) - (J - -³)
2 ((1 - -3)
H
a T-a)
11yn z.112 aBTp (f(y) ) [(xx)) (1)(s(())) -8)
a
1 11 x=1
2
Collecting terms and removing the 11yn~ xx|l² term, get
E, [E S Bn + (1 (1-
En [f( - +3+ "a "n²
1-a 1) (f(Øn) ff)
wmp -1)
(101)
11 B - um)luu 11 + mm
("6 "1
a
a - -1 2n ([(( - 12) (f(ym) f*)
We fix = 2 and a I. mn
which cancels En [f(en+1) - fr1 and the f(xn) - f terms. With
these choices, we want
1-a 1 1 2m(L(x) 11) B 1 2n(( 14) =0
ag
(102)
pm
pm
=1 - B = pm1(1 2n(L<r)) - -1))
(103)
We want to maximize the right quantity with respect n). It is maximized for r allao-aa)> and in this case:
- 1)) = 8 1= 1m(11 - -4)
4 (T<KK) - 11) (1 (1-
1 2 -1- 8 (I((K) 11)
1 1
(104)
Also with that choice of 17 rn (, we have 1 1 ---mm (Tere -w) 4 [(()))))
< 0,
which ensures that we can control the 1/y/- x= term. Thus, with the choice of parameters
8 16 (TeK) 1122
B 8=1
8 (LIK) w)'
= 4 (T(K) u)) a
[LRK)- 2)
(105)
have
412
En En+1] S
#
En 16 (LIK) 11)
1l - x²12
(106)
(L(x) - 1)
Ignoring norm term, taking expectation and by induction
E [Ex] <
E [Eo]
(107)
(LIK) - 14)
34

---

Published as a conference paper at ICLR 2025
Finally, we just bound Eg, by strong convexity
Eo f(xo) f + #
200-=211==2100 - -f);
(108)
as we assumed 20 = 20. Thus, we get
Bff(2z) --
((x))
(109)
We obtain a bound in term of solution following the same reasoning as for the proof of Theorem the strongly convex case, and obtain jfathat such solution achieved
n 8 L(K)
H log
(2 f*)
(110)
F.3 ADDITIONAL LEMMA
In this section, we prove Lemma Then, we introduce and prove Lemma
First, we recall the statement of Lemma 3
Lemma. Assume f is such that assumptions 7 1-2 hold.
If f is p-strongly convex, we have
E
-
-
(111)
If f is convex, we have
- {x(=>1]] -
= (((x))((0)- -f()
(112)
Proof. We have the elementary relation:
E [V) - V (z))) = E [ - [V)))
(113)
If f is u-strongly convex, it satisfies the Polyak-Lojasiewing inequality (Necoara et al.
2019
namely
|> > -x(f())-f")
(114)
The convex case can be obtained by letting - O. In this case, we only have [V 2 conclude, we apply Lemma and we get the result.
0. To
Lemma 4. Assuming f is L-smooth and sn t, iterates of SNAG give:
En
[ < En [(f(ym) - f(xn+1))] + 2IE,,
V -
(115)
Proof. Using smoothness, we get
f(xn+1) S f(yn) (VF(a))) Un) + |in+1 vnll
(116)
2
Lo
f(xnt1) S(yn)) sn, (V)(u)) vx(un) +
V ((()))1
(117)
2
We have
(Vf(y)). (K,)) = (Vf())) (x(un), (v.))) + + =-I[V[(m,)
(118)
V (y. 2 (V)())) (u)),, (y,)))
(119)
Note that taking conditional expectation with respect F... the scalar product in equation equa- tion 119 gets cancelled. Inserting (119) in (117) and taking conditional expectation, we have
E, [f(xn+1)] < En [f + s. En
[VV(())) - vx(v.))1
(120)
En 8n (1 Lsn
[[Vx(1))11]
(121)
2
E, | (uw))l
< E, [f(w) - f(xn+1)] + 2E, VV(()) Vx (x()))1
(122)
Sp
Where used in the second inequality that 8n,
> 2, provided that 8, < +
35

---

Published as a conference paper at ICLR 2025
G CONVERGENCE OF SNAG WITH STRONG GROWTH CONDITION
and G.2 we provide for completeness a proof of Thhorrm 3 that a similar result to the one from Vaswani al. (2019). Our proof is slightly simpler formulation of the algorithm. In Sections G.3 and G.4| we extend these results proving new almost sure convergences (Theorem that are asymptotically better that the results expectation.
In Sections G.
In this Section G we denote Fn the o-algebra generated by the n + 1 first iterates {ay /== gener- ated by SNAG (Algorithm (). i.e. Fr, OZz......... Zn). Also, we will note En the conditional expectation with respect to Fn.
First, we present technical result (Lemma 5) that will be useful our proofs.
Lemma 5. Assume f is L-smooth, and that VK verifies the SGC for PK 2 1. If yn and In+1 are generated by SNAG (Algorithm 2) then with
Lpk
Vf Bm f(ant1)l
(123)
where E, stands for the conditional expectation with respect to Fr.
Proof. By L-smoothness, we have
f(n+11 S f(yn) + (Vf(y)), 2n+1 -va) L
In+1 - yn y211
(124)
Ls²
[(yn) - s ((V(())) (x(un)) + (V((()))1
(125)
2
By taking conditional expectation,
L.2
E, [f( f(v,)) - -/sss>/VVVir V/(w))1 +
E,
(126)
2
Then, by strong growth condition (SGC), we have
Bn [f(++1) - f(ym)] S (LKK
LpK 3 - | f(mn)11
(127)
To maximize the decrease, we choose
I,pK leading to
En [f(x=+1) - f(yn))
2Lpx (2)))
(128)
G.1 CONVEX-EXPECTARE
In this section, we prove statement ( Theorem B which the convergence rate of SNAG algo- rithm for convex function.
We first recall the SNAG algorithm (Algorithm)
2 with a fixed step-size s and 3 = 1
V/ Jn + (1 an)
In+1 Yn s V k (3n) 2n+1 Zn 17 V (yn))
(SNAG)
11. with <.(-) defined in
1
1/2
2 2nt1
x 1²
2 1| x=1
112
V x (yx)))
2 + nm(x" .n, Vx
(129)
||2n
xt 112
1/2
| (1x))11 + mnfo" Un. Vx (yn))
(130)
2
+ 7/1
On
(In - Mn. vx(un))
(131)
On
36

---

Published as a conference paper at ICLR 2025
After taking conditional expectation with respect to Fr, by the convexity of f. SGC and Lemma we have
5
Bm [11=+11 - x011 - an x²1 The (S(n) - [(x))( + Th 1 On
On (f(an) (1n)) (132)
+ L In En (1(m) - ([n+1)]
(133)
We can reformulate as
En [Lppnn (f(+))) - f*) | x²113] S 17n
On (f(In) f²) 21l - x=11
1
anp
(134)
Lp
'7n 1 0n
On
(f(2m) - f*).
(135)
We define parameters as
Lpk = L (n+
C
Th
On
C
L
n
(136)
an
with C' 2 0.
This parameter setting implics '7n = yC Lpx
(n + 1).
Thus, we have
VC
Lp 111 1/1
On
_ (2n
(n + 1n+1) 50
(137)
an
Lpx
n n+1 + VC <
(138)
DK 2n + I
As we have, for all n E N,
S
n+1 1n+1
S 1, at best we can set VC
With this choice, we have
2
2px"
C
4pp
Thn
Lpk
1+1
2
and
C 2 m
1 n²
(139)
Ob
2
+1
This implies that an
n+1
With this choice of parameter, we have
2+
En
(n 1)2 4LPx
(f(#n+1) fr) 11llnt1 1aat1-=211' s
n²
-f)
-
1
11
x²1
4LPx
(140)
Finally, we get the convergence rate
2LP
(n 1)2 ||:00 xx x=112
(141)
To conclude:
2 n²
2L
|20
x x²1 S
2 V
PK I150 - =x"1l S n
(142)
G.2 STRONGLY CONVEX EXPECTATION
In this section, we prove statement 9 of Theorem
3 Let us remind the algorithm
V/ Tn + (1 - an)an
Fn-1 Un 8 v x (ym)
(SNAG)
2nt1 B2n + (1 B)yn Tm V (yn)
with v-(-) defined in (1. We introduce the following Lyapunov energy:
E, = =((x)) - 4*+ + / ||z, - x: 21 2
(143)
37

---

Published as a conference paper at ICLR 2025
We compute:
E En = f(Tat1) - f (1a) + 2 [1 - x=122 14 2112n x=1
(144)
2
We start considering the right term
A 2
| - x²11 - 1| - x2
= 11 + +1 (1- 3) 17 (Bn)) - -x111--1222 -1 x²11
= (52 1)]l - 12
+ (1 - -1-3)211u4 -x
1
+28(2n -x", x1" 3) = - 2(1 3)m( (Vn), yn -x")
by construction of Algorithm 2 We now control the first scalar product: using the definition of Algorithm
we have 2n Yn I (Un xn),, therefore
(zn xx, (1 (y x²) - (VV((M)))
(yn x², {1 (y)n x²) -/V K (Un))
(Un In, (1 - () x²) xVn))
(1 B)1ly/ x² 112 7ynn x², (x(U))) 1-a 7yyn Ini (x(vn)
+ (1 - 8y - In. Un x²)
Now, applying the relation 2(a, b) = ||a + b11 we get
||a|| -1b112 to -ya -xx and a
1-a - (ynn In),
1 ( a
(yn - nn. 10 x²) = 5 2| x x²112-
118b - -xa11 - 11 x=13, (145)
a
2
1 -a a
so that
(Zn x², , (1- (1-1)) -x")
V (2m))
1 - 3 ||2n x²11 11? + 11ym x1
(1
11 - xnll?
1,y, x,, vx(xx))))
1 1-
T/yr - In. <(()))
and
An = -(1 - -x"11 11 + (1- (1))), - =1112 + 17² 12" 1//1 (1((v((()))) (Vm))l?
BB(1 - B) ( a
2
a.3 ( k (ya), Un - xnn)
ll xnll²
1 1-a
1 a
- 2n x< (Jn), Un - xx)).
Reinjecting A, in the expression of En+1 - En and by definition of En, we get
Ent1
Fm -1 B) Fm + (xx++1 - -5- - 33-3(pm (f()) 1d) + 10 331lyn - 111
2
+ トリ V x (1m))1
11 -
(-a)
11./n x 11?
(146)
I a
ann ( (Jn). Un znn) wurn V x (yn), Un - xx")
(147)
We take the conditional expectation with respect to Fn:
En [E++]] BE,, + E, (x - f 3 (f(x)) - f*)
11 (1- B)1l,, x01
(148)
2
2
PEn +
|| (1.)))
- #1 3111 (3) -
11.m. xnl1
2
2
a,3mm
EEn
(v((H)))
33n In) - unmen V ((())
.3/ - =x))
(149)
1
38

---

Published as a conference paper at ICLR 2025
Using strong convexity of f, the strong growth condition (SGC), and then Lemma 5 we have:
En [En+]] - EE + Enn (f(+++1) f 3 (f(xn) fr) + (1
B)1lyn x=12
En (f())) - [x 13 3( (3) (
2
pI En
2
1 1-a
1/
I. 11?
(150)
aBmmp (f(y)) ((xr)) pm((((n)) - - 2 !1
1/n x²11?
(151)
2
( amp
1-a -1) ) (f(xn)= - 1*)
< Bn + +(1 (1- (1-ploppe?)) En (1(++1) + 3
p (1 - 3 - (an)) 18n - x 1²11 + 10n [.pk')
aB -1 (f(yn) -8) (152)
2
We make the following choices: =
Valpx"
1
3 = pm =
V L
F and
1-a
a
PK V 1/2 +
a
As we have:
V
Px
Lpkn
a3
= PK
PK
T (1
PK V
P
1- 0,
(153)
1-a
these choices cancel all the terms. Thus we have:
a+1
En [Ea+1] 2
1
En E [[E++1] 5 1
Eo-
(154)
PK
PK T.
Now, note that Fg = ((x) f" + 2/2 |F - =11 S 2(f((()) - ff*), because f is ju-strongly convex.
We deduce the following convergence rate:
(1 1---V + (f(zn) -*).
[[((aa)
(155)
PK
sufficient condition on the number n of iterations needed to achieve precision E is then naturally given by
2 (1
VWV L
11 (m (f(zo) - (f) Sc
(156)
PK
By taking the log, we get
(2(((z)) - 5.
ni log
1
log
(157)
PK L
Or equivalently
11
((f(zo) - -r)
n z log 1
V
log
(158)
E |log (1 x)] 2 x for any (0, 1), we observe that
PK
Using the inequality:
1
(2(((0)))
L
(2([(z)) 8*)
log 1
log
PK
log P
(159)
PK
L
E
Hence sufficient condition on the number of iterations reach given precision is
n M PK / [h log
(2(((x))-("))
n log ( VH)
log (2(((xo))5))
B(f(
1
(160)
39

---

Published as a conference paper at ICLR 2025
G.3 CONVEX ALMOST SURE
In this section we extend statement ( of Theorem to get a new almost sure convergence rate.
Proposition Assume f L-smooth, convex, and that VK K verifies the SGC for PK 2 1. Then SAlgorrrr 2 with parameter setting Lx 3 = 1, On 4+ a sequence fonnne such that
1
n² 1n+1 generates
f(xn) a.s.
(161)
n
This result asymptotically better than the result in expectation of Theorem 3 This asymptotic speedup happens similarly considering the deterministic version of the algorithm (Attouch & Pey- pouquet, 2016).
Following the scheme of the proof of Theorem 3.1 in Sebbouh et al. (202I). the Theorem 10 is the
key result of our proof.
Theorem 10 (Robbins & Siegmund (1971)). Let Vn, Ans B, and on positive sequences, adapted some filtration Fn. Assume the following inequality is verified for all n E N:
(197))
E[Vn+1l Fr] S Vnn ann) An -B.
(162)
Then, on the set (Ei20a a < +00, Eiv0 Ar < +oo}. Vn converges almost surely to a random variable Vos, and we also have Σ Bi < +oG.
Note that the choice of parameters stated in Proposition 5 are less agressive (multiplied by factor 1 compared to the results in expectation (Theorem
Proof. We start back from Equation 134 that we recall
E,,
-
+ kn41 - x²1]]] S Th On
an (f(xn) - 1*) + + - =12
(163)
+
1/1
:nn
On
(f(ym) f*).
an
(164)
We set
Lpk n = L
C (n (n+1)²,
Th an
On
C n
(165)
L
with C' 0.
In this proof, compared the one of Theorem we do not want to cancel the last term but exploit it. More precisely, we are looking forward to the following inequality
Lp Th Th
an
S
73n
(166)
an
2
Hence:
C
(2n + 1) Tn 1 VVC
n + 1 2pk
(n 11+1)
+ VC
(167)
I
2 Lpk
2n + n +
C 5
(168)
16p
With the choice C' =
16p3 the last inequality is verified. Then, we get the following parameters
1 n #1
On
n²
Tn
(169)
PK L 4 1- On
4
40

---

Published as a conference paper at ICLR 2025
a²
The latter induces O₂
m+1
Thus, we have
4+
nn + 1)2
1
n²
1
En
(f(Int1)
-f)+
2n+1 x²1
(f(In) f*) + 11 x² x=1
16LpX
16Lpx
2
th
(f(yn) -)
2
We can now apply Theorem 10 with
V, = n²
1
16Lp (f -fm + 21120 x x²11?
2
A =- O,
Bn = ?h 2
(S(J)) - -5²),
an = O.
So we have almost surely
Bn, = 8
E ()f(v))) - < t00,
(170)
220
n20
which implies that
Σ (n + ()([()))) (³) < +00.
-
(171)
n20
By the definition of Algorithm
1 in the convex setting), we have
Zn
On (#n-1 zn-1) (1
(172)
Moreover, we have
yn = (1 On (vin - 2nn.
(173)
By combining Equation 172) and Equation
(73).
we get
2
[ 2 ant1)²
On
|| Un 112 + (1 ant1) =))31/ (Vm,)l?
1 On
(174)
+ + an+1)²
)
an
(m - s)(nn Un. x
(175)
1 an
By taking the expectation with respect to Fn. and using (m ss² n/ for n large enough, we have
(1-n an
2
E, Pm][110411 Va+i [12] < (1 an+1)² )
||0, -vall2
(176)
an
(1 (1-aa41)2 V (um))l91 2(1 ax+1) )²
On
(nn =S( Un. vf(y))) (177)
1- an
Using the convexity of f, have (xn Un. v((yn)) s f(xa) f(ya). Thanks to SGC and
Lemma we have
2
Em Em || Vn+1 1n++113]
(1 1| S
0n+1)²
On
|| ynll2
(178)
Om
+ 2(1 ax+1) 2 T/e Lp En Emln()n)) - -f(xntz)
(179)
+ 2(1 ax+1) ) an
(mm - ()(( - -((w))).
(180)
1- On
41

---

Published as a conference paper at ICLR 2025
We divide the previous inequality by (1 an+1)2
|[ Un+1ll
11?
2
Bn
On
|| - ynll2++ 2n f(nnt1)]
(181)
(1 an+1)
1 - an
+ 2
On
(1/n
s)({((n)) -((u))
(182)
an
Thus
Fn+1 Dnt1 12
2
En
On
|| ynll? + +21 Lpp f(xn+1))
(183)
(1 ax+1)
1
an
+
O'
(1/n
()((( - -f*)
(184)
On
On
(m -) (f(yn) f²)
+
2
(185)
On
By the parameter setting (Equation
169 and the step-size 8 PxT.
we have
1 2n + 1
1 n²
2 Lp' 1 On
(nh 8) 16 Lpk
Lpx 4n+1 (n)..
(186)
By setting Cn : 2 Lp I-an (Nma 21n(1n -)) (S(y)) - S*), Equation (171) and Equation 186
gives that almost surely
Σ Cv < +00.
(187)
By defining An := I-an formed into
and the parameter setting (Equation 169)). Equation 183
can be trans-
1
(n + 1)2
E,, | 1 |1 Mh++ 2
(((n+1)- [*
(188)
8
Lpk
1 n
n
S -nn)2
ynl 2|2
(f(xr) -r)
2Lpx (n + (f(rm) - -5² Cn
(189)
8
Lpp
1 n²
n²
< 12 ynl + 8 Lpk
(f(x)) -f²)
2Lpx (n + (f(Øn) -f) + On
(190)
-22nn 1) yn 12
(191)
Recalling En Cn too, then use Theorem
10 with
n²
Vn = 12 - -yxlll 2
(f(In) f
8 L
An Cn.
n
B, 2Lp (n + (f(zn)
f*) - +2\n 1)]lzn ynl12.
ān =.
Note that An 1-a,,
1, 2A, - 2 An 2 0 and B,, is positive. So, we have that lim Vn = Voo exists almost surely, and En Bn < too almost surely. However, we have Ann n
1
An B. 2 (T + +1) (f(x.) - f*) + م Un 112.
(192)
Moreover, we can compute by the parameter setting (Equation
169
n²
PK + n² n n+1
Ann²
4+
1 n²
n²
n+1
n+1
(193)
(L
4
Lpk 2
8LP
42

---

Published as a conference paper at ICLR 2025
As Px
+4n+4 PK n +2n+1
1, we have [xpk(
A,n²
n² 87,p"'
and thus
n+1
Bn 2 Vn-
(194)
We can deduce from the previous inequality
1
V.
Σ BB= =
Br
By,
Vn
(195)
An
An
n²
n²0
n00
n:0
#+1
As BB Bn < oo almost surely, we have almost surely. Then, almost surely
Σn
P
<
+00 almost surely, and necessarily V/ =
1 n²
(f(xm) - 1*) 4 0.
(196)
8 T
Finally, we get the result of Proposition
5
f(xx) l = 0 n
(197)
G.4 STRONGLY CONVEX ALMOST SURE
Similarly to Section G.3 we extend statement S of Theorem 3 to get new, asymptotically better, almost sure convergence result.
Proposition 6. Assume is L-smooth, p-strongly convex, and that V k verifies the SGC for pk 2 1. with parameter setting
Then SNAG (Algorithm 2
L 1 PK T. and
1+ ++ / V
77
A8 VpT. generates a sequence (In)nEN such that for all E > 0, we have
(xx) - -s" a.s. o(1 + E)"),
-
(198)
I| - x x²11 o.s. ((g + E)²)
(199)
where q : 1==1- 1
VT.
PK
Proof.
We use the following Lyapunov function
E, = f(xn) - 1 1|, - x x²112
(200)
We set q 10
1 PK V L. We fix r' > 0. By the Markov inequality and Equation 154
we get
P(E 2 (q (q+ -
E[E.] (g ''+
S q + E'
9
(201)
We sum 0
Σ n20
P (En 2 (q+ E0 S
Σ n20
< +00.
(202)
q a e
Setting A, := [E,= 2 (g+ Eo we have by the Borel Cantelli Lemma that IP (lim sup A..) = 0,
which implies P (lim inf A 1, where A% is the complementary of A,, In other words, as
AC = fEn < (q- }. then for almost every w E Ω (N) N such that for all n 2 No)w),
we have
En(w) < (q + E')"Fo Fo.
(203)
Thus, we have
En (w)
q 44 n
Eg
(204)
(g 25/)mi
q + 2
n
43

---

Published as a conference paper at ICLR 2025
The right term is independent of w, so almost surely, we have 2²"
En + +
Now fix 2s' and get
En - -00++()))))
(205)
and thus the result by definition of Ein.
H PROOFS OF SECTION
In this section, we will prove our results that establish a link between the strong growth condition SGC and the average correlation between gradients, by exploiting the finite sum structure (FS)
H.1 PROOF OF PROPOSITION 1
In order to demonstrate Proposition ! we first establish Lemma 6
Lemma 6. Let {a,) ;= be a sequence of vectors in B. and K E N. We define B(K {B c {1..... N B) = K}. Then, we have
N
N
N K Σ
ag 2
Σ
ΣΣ iEB
0
+2
(as,
(206)
K
N
K
BE
1SiCJEN
Proof. We fix (ii....,.s.
E B(K,N), We have
N
Σ ail
a
Σ
a.l1
(207)
i=1
if (
N
N
a:l
||
+11
Σ
ail 2
Σ (oi,
(208)
i=1
iet
N
N
0: 2 +
Σ
1|i:12 +
Σ
(a; -2
-
Σ
(a:,az)
1=1
id
(
(i ifj
i=1
j$ (1
(209)
We sum over all the possible B (in.... E B(K Note that [B(K, = each term in Equation (209) first
We split
N
Σ
aill
as
1|
(210)
K
BEB(K,N)
i=1
The sum of the second term of Equation 220 is
Σ
Σ
|| =
Σ
||a.12
(211)
BEB(K,N) TE (
BEBIN K,N) aad
N
1a,11
(212)
N - K
N
K
||a.11
(213)
N
N
N K
N
N
K
Σ
all1
Σ
(a. az)
(214)
K
N
$
44

---

Published as a conference paper at ICLR 2025
The second equality comes from how many times the index is picked by the sum. We thus count the number of set ffi.....,n- compute the cardinal of the set {fi, (1.,.,...... ................................ in k- 1
E "I, such that é belongs to this set. This amounts to N...), This set
has the same size as B(N K 1, 1), which is (w-K-1)
The sum of the third term of Equation (209 is
Σ
Σ
(a))
E BEB(N KN EJE boc
E
(ai,
(215)
BEB(K.N)
(9)
(F
N
N -
Σ
(a4.
ag)
(216)
N
K -
N (N K
K) K
N Σ
(ai,aj)
(217)
N(N 1)
+-=11
Here, the second equality comes from the fact that we compute the size of the set (...j,,....,,.--- 2,, {I,..., NVMi..)) which is of the same size B(N K 2, 2). which is (N-K-2).
Finally, we compute the sum of the fourth term of Equation 209 using Equation 213
N
Σ
Σ
(0..0,)
ats
aj
(218)
BEB(K,N) NN t=1 (
BEB(K, JE (f
N
N
N
K
ais
(219)
K
N
j=1
N
N
K
0:
1|.
(220)
K
Now that we have computed the sum of each terms in Equation 209
we have
E1
ail
N
N
as 2
+
N
K
Σ>
N
ag
N
az)
K
K
N
BEB(K,N) (E(
i=1
1 1
(221)
N
(N K)(N K 1)
N Σ
(N)
N
K
N
+
(a a²) - 2
a1l1
(222)
K
N(N -1)
K
N
1-=1
i=1
N
(1
N- K
N
NN) N K
N
N
ag
-
Σ
(a;aa))
(223)
K
N
K
N
N -
N
K
N
N
K
N
2
N N - Σ (ai,a))-
(224)
K
N
K
By rearranging the terms, we obtain the desired result
DI E
N
N
K
N
a
all
Σ
(225)
K K
N
BEB(K,N) iE(EL
$
45

---

Published as a conference paper at ICLR 2025
The proof the Proposition
is simply an application of Lemma 6 with a; N ff()). We obtain
[V[()| = INN i=1
Σ
f(())
(226)
N 1
Σ E BEB(K,N)
Σ
VA(=))
N N K 1 N
Σ
K (N)
N
N +J=
[fj
(227)
KI MERK
N K 1
N
Σ
vf(())|+
(f(()).fff))
N K BEB(K,N) (1
K
N
N
(228)
K
N
K
N V
(229)
N
N
K E N [
2 N K
Σ (Vf(2),, Vf(()). ISKjSN
(230)
N2
H.2 PROOF OF PROPOSITION 2
In this part, we demonstrate Proposition 2 The result is a direct consequence of the RACOGA condition. Indeed, considering batch of size 1, by Proposition we have Vz Rd
[v)(2)] =
1 E N
[
2
Σ
Vf((z)
(231)
N2 ISKjIN
Now recall the RACOGA condition
Va E Rdd (VA(() vf((a)
2 c.
(RACOGA)
We injeet Equation 231 to get
N + N2
1
2
E
||
(x)
(((())
(232)
N
E
[+)
+ E
| [2)
(233)
N
1
(1+
E [+
(234)
N
N From Equation 234 that holds Vo E Rd, we deduce that satisfy SGC with S
I426
H.3 PROOF OF LEMMA D
In this part, we demonstrate Lemma Assume that for batches of size 1, f verifies a P1 SGC i.e.
Vz Rd V {
(235)
By Proposition we have
[f =
K N [IVx(T)]P]
+
N K
Σ (V)(()), (f)(2).
(236)
N N -1
IgieiEN
46

---

Published as a conference paper at ICLR 2025
Moreover, by developing the squared norm of V of (x) and rearranging, get
Σ
(V(()) = |/(+)|
1 2N
[V(+))]?
(237)
N
ISKCISN
hence, by reinjecting (37 into 236
1 N K N
N
N K
B
[
|V](t)]
NK [V
(238)
-
N
N - K 1N-K K
N- 1 |[V(())1
(239)
K(N-1) (N(K 1) + (N (V)))
(240)
using the SGC assumption for batches of size 1.
Finally we deduce Lemma the SGC is verified for every size of batch K 2 1 and we have
PK S K(N (PI(N - K) + 1)N).
(241)
Remark 10. Lemma 7 offers indirect way to demonstrate Corollary | Indeed, the result of Proposition 7 foor the special case of batches of size 1 is easily computed, as we have
[V](2))
1 Σ IVA N
2 N
E
(VI((),, Vfz(2))
(242)
ISiSiNN
Thus, when PosCorr is verified, with batches size I verifies SGC with constant P1 N. By applying Lemma with P1 = N, we get that for batches of size K, verifies SGC) with constant
N PK K(N-1) (N(N K) (K 1)N)
1
(243)
K
For the clarity of our presentation, choose present Proposition 7 before Lemma can be seen as a corollary of this result.
even if
One can obtain reciprocal result of Lemma
Proposition 7. Assume that for batches of size K, f verifies the SGC with constant Pk. Then, for batches of size 1, f verifies the SGC with a constant P1 which satisfies
Kpk(N - - (K - 1)
P <
(244)
N K
Proof. From Equality 238
we have
1 N K N
[+(()) + K-1 --1 N
E |
KN N Σ
K N [Vf())1
(245)
Using the SGC obtain
1 N K1 N [+(()) <
Σ K N IN
PK
K-1
K N - [+
(246)
So, the SGC is verified with batches of size and 244 is proved.
47

---

Published as a conference paper at ICLR 2025
Remark 11. Proposition 7 indicates that satisfying the SSCC for batches of size K implies interpo- lation (Assumption]] 7 if each fi is convex. Indeed, Proposition 7 induces that the She is verified for batches of size 1 with some p1 1, i.e.
Vx R
(247)
Interpolation is then direct consequence of evaluating Inequality (247 at some x² arg min f. Indeed. implies that each minimizer of f is critical point of each fo. Convexity of the fa allow to conclude.
H.4 PROOF OF THEOREM 5
Recall that we assume f is convex, L-smooth, and that Vi verify SGC for p1 2 1. We know that SNAG with good choice of parameters (see Theorem 3 guarantees to reach e-precision (2) if
In this section, we demonstrate Theorem 5
2L ro - x"1|.
n 2 PK
(248)
Note that by Lemma 1 we know that Pk. the SGC constant associated V K, exists, and that
PK S K(N 1) 1) (pI(N - + (K)
(249)
So, in particular, we are ensured to reach an e-precision if
2 1
2L K(N 1) (0I(NV K) + (K - -1)N) V
10 x"1l
(250)
- N N N K
2L
100
x²1l
(251)
Now, to translate the result in term of number of f,, evaluated, note that each iteration requires to evaluate K different fi, because consider batches of size K. Finally, the number of V to evaluate is
2L ro x²1
AKPI
(252)
H.5 BOUND ON RACOGA
In this section, we bound the ratio EISTSIEN A (1 dition.
EN [ that is involved in the RACOGA
Proposition 8. Let E XX We have
Eisieren (V)((),, Vz)())
N
<
(253)
E |V
where X = fa E Rd Vi (I...., NJ. VV = 03.
Proof. The upper-bound relies on the inequality (a, b) S ||la|| + 11 for a, be Rd.
Σ (VH())
1
Σ
(1V+<)))+++<<
(254)
ISKGNN
ISi<JSN
N
2
(255)
2
48

---

Published as a conference paper at ICLR 2025
||]|1 ||b|], for a, E RR, we could get lower-bound. This lower-bound is not tight when considering a sum of two or more scalar products. This is because the critical equality case occurs when opposite to each other. Interestingly, Proposition provides a way to get a tighter lower-bound.
Using (a, 2 -
b. However considering at least 3 vectors, they cannot be respectively
By contradiction, assume there exists Ie RR such that
Eiskojen (V)( ((z(as))
1
(256)
E (x+=))
with & >> 0. Using Proposition 1 with batches of size 1, we have
N
[f(x))]
(=(a))) + N
E (V.i(ze), Vfz(z)))
(257)
N
ISKGIS
N (+((=)))1
N
+
Σ (=))()
(258)
N
2
N
2x [VA(==]||
<
(259)
N
We thus arrive at a contradiction, as [V(())) 2 is non negative. As a consequence, (256 cannot hold. Thus, at worst we have for all I E 1
1 E EiSisJen (Vi((),, Vf}())
(260)
2
Σ [
So, Proposition iis proved.
RACOGA VALUES IN LINEAR REGRESSION
In this section, give deeper insights considering RACOGA values in the case of the linear gression problem. Moreover, we investigate, in this linear regression context, the link between RACOGAI and the curvature.
We have {a;, bi bi where each (ai, b;) E Idd x IR, and we want to minimize f, with
N
1 N N
f(x)
= N
fl(z)
Σ (la, -..22.
(LR)
As mentioned Section 5.I in this case the correlation between gradients directly linked to the correlation between data
= ((a;, x)) b;)( - by) (a,, ag)
(261)
gradient comelation
data comrlation
In particular uncorrelated data, i.e. (ag, a.) 0, will induce uncorrelated gradients, i.e. Va Rdd (V)r,), (z)()) = this case, RACOGA is verified for 0. In this section, we will see that outside this special case of orthogonal data, the characterization of RACOGA values is challenging problem.
1.1 TWO FUNCTIONS IN TWO DIMENSIONS
We study in this subsection the simplified case with d N 2 and bi b2 0. i.e. two functions defined on IR_ such that 0 is their unique minimizer. Formally the function we consider is the following
f(x) =
1 2
(a1, xx2
1
(0)
(2f)
2
49

---

Published as a conference paper at ICLR 2025
In this special case, we look the gradient correlation, with same sign of the RACOGA values,
((x) = (z), Vf2(=)) = (a1, (a2, (a1,a2).
(262)
If (a1, .2) # 0. A(x) is not identically equal zero. Without loss of generality, for the following reasoning we can assume (a1, 02) 0. Choose ag Kº such that (a1, xo) ) > and (a2, zo) * O. The function
(a1,2) 2) has kernel aT. the orthogonal of d1- Moving along this kernel, ie. considering x = mo + k, k E at. 01 and 02 are not colinear, one can make the sealar product (a2, .) be positive or negative while (a1,4) > 0 as remains equal (0), Therefore necessarily, if (a1, 02) * 0 and and d2 are not colinear, we have ming A(r) < 0. So, (a1, (2) + O, the minimum of the RACOGA values the space necessarily negative.
0.1
RACOGA
Vectors a.
-0.1
Illustration of the RACOGA values for problem 20). along a circle around the solution. On the left part, and ag are orthogonal, inducing RACOGAÍis constant equal to zero. On the right part, a1 and 02 are slightly correlated, inducing positive and negative RACOGA] values. Note that the non positive RACOGA areas exactly contain the points æ E Rd such that (0), .) (az, z) S 0.
Figure 11:
Figure I illustrates this behaviour. We observe that orthogonality of a1 and d2 creates non positive and non negative areas RACOGA values.
According to Theorem gorithm 2). The example of this section indicates that we can not hope to obtain theoretical results that would ensure high RACOGA] values for any linear regression problem, and thus good perfor- mance of SNAG. In the next section we see that, nevertheless, we can expect the RACOGA values to be positive over most of the space.
positive RACOGA values indicate bad performance of SNAG (Al-
1.2 RACOGA IS IIIGII OVER MOST OF THE SPACE
In Section I.I we considered a 2-dimensional example with 2-functions. Increasing dimension and adding functions, the problem of characterizing RACOGA] values becomes harder. In the case of independent data, it is possible to give theoretical result considering the RACOGA values in expectation over the data.
Proposition Let [(x) = I (0(x,, b;)2 where {a,, bi E TRP I are i.i.d. and Rdd R IR is differentiable. We have
(fxl)) N(N
E
2 |B((((z,11) - (1) 0.
(263)
ISiCJEN
In particular if (x, ai) (x, as) and a ~ *N(m by N(m,,, of) with 01 1 by, we have
N(N 1) [Tx + mm a moml 2 0.
Σ (V)()), v(((a))
(264)
ISKSJN
In both cases, the expectation taken with respect the data {as, by N 1
50

---

Published as a conference paper at ICLR 2025
Proposition Catoosttionnniniie Iiddicates that when having large amount of data, expect the RACOGA values to be positive over large part of the space. The proof of Proposition is deferred in Appendix 1.4
To confirm this statement empirically, for fixed dataset {a,, b. values on a sphere whose center is a minimizer the function. Note that by the linearity of the gradient, the [ values taken on this sphere are invariant by homothety. We set the bias, i.e. the (b. } at zero. This forces zero to be minimizer, without loss of generality. The function we consider is the following
compute the RACOGA
[(x)
ai, x)
(265)
N
20
0
-0.05
0
RACOGA
0.15
0
RACOGA
4
(a) Uncorrelated data
(b) Correlated data
Figure 12: Histogram distribution of the RACOGA values for points sampled uniformly sphere centered on minimizer. the left plot, the data are fewly correlated and the RACOGA] values mostly positive. On the right plot there is correlation inside data, and all RACOGA values are positive. Note that the IRACOGA values are significantly higher on the right plot, because of the higher data correlation.
run this experiment the case where {a: 1.V drawn uniformly onto the sphere, inducing low correlation inside data, and also in the case it is drawn following gaussian mixture law, inducing higher correlation inside data. We d 1000, N 100. It is the same problem as for Figure I except that here we set the bias to zero. We sample 10000 points on the sphere. In both cases, RACOGA is almost only non negative. More, all the RACOGA values are positive on Figure 12b i.e. for the correlated dataset. Note that the observations we made in Section 5.1 are consistent: correlated data induce
On Figure 12
values (Figure 12b whereas with uncorrelated data the TAAOOAAAvallll values smaller (Figure 12ap.
However, one should not conclude from Figure 12b that RACOGA values are positive everywhere, as there could be non positive RACOGA value areas that are small that our sampled points never fall in. Even more, we should not conclude from the fact that the eventual areas of non positive RACOGA values small that the optimisation algorithms never cross them. We show in the following section that, actually, these small non positive Pesitive/RAOGGA value areas exist and attract the optimization algorithms, and that stochasticity prevents the algorithm get stuck inside.
value
51

---

Published as a conference paper at ICLR 2025
1.3 THE CURVATURE PROBLEM: FIRST ORDER ALGORITHMS ARE ATTRACTED BY LOW RACOGA VALUE AREAS
In Section T.2 we showed that in the case d > N where N is small, can Sxpect|AACOK values to be high over most of the space. This statement is reinforced in the presence of correlation inside data (Figure 12b].
However, if d is high, even though we sample a large amount of points to evaluate RACOGA values, could miss non positive RACOGA] value areas if these areas are too small. On Figure [ see that these areas indeed exist. Moreover, although they are tiny with respect to the whole space (Section[..2) deterministic algorithms, namely GD (Algorithm and NAG (Algorithm / dive into these areas and stayed trapped inside. Strikingly, SNAG behaves differently and it manages not to get stuck in the same area.
0.1
2.6
GD
SNAG 0.25N
0.5N
SNAG À 1ON
RACOGA
RACOGA
00
SNAG 0.5N
-0.2
SNAG 1NN
SNAG 15N
-0.3
Gradient evaluations 900
Gradient evaluations 900
(a) Spherical data
(b) Gaussian mixture data
Figure 13: Illustration of RACOGA values taken along iterations of GD (Algorithm 6 NAG (AI- gorithm 7 and SNAG (Algorithm)) 2 batch size for the linear regression problem. On the left plot, the data are fewly correlated while on the right plot there is correlation inside data. Note that while deterministic algorithms, iee. GD and NAG, dive and stay negative RACOGA value area, the stochasticity of SNAG enables it to not to be trapped in the same zone.
In the remaining of this section, we give an explanation of the behaviour observed on Figure
First order algorithms fall in low curvature area In the case of linear regression, which amounts to minimizing a quadratic function, it is well known that first order algorithms, namely algorithms that only gradient information, converge faster in the direction of high curvature, i.e. directions such that the Hessian matrix has a high eigenvalue, We illustrate this phenomenon on Figure [14] where we plot the first iterations of GD (Algorithm(6) and NAG (Algorithm 7 applied to the function
g(x)
Ar -
(266)
where = ( 9 << -0000<<
The algorithms GD and NAG dive and stay in a low curvature zone. However, note that the stochasticity of SNAG makes it unstable enough to not follow the exact same path.
The RACOGA CRACOGACCrvaart Curvature link In this paragraph, we connect our observations about curvature and RACOGA values. Intuitively, for point z E Rd such that RACOGA is small, iee. gradients average anti correlated, the gradients will compensate each other. Thus,
expect that around this point, the gradient will have low values. Considering linear regression, this induce that non positive RACOGA areas tend to produce low curvature areas. We illustrate this phenomenon
52

---

Published as a conference paper at ICLR 2025
127
SNAG NAG
GD
Curvature
7
Figure 14: Illustration of the iterations of the trajectories of GD (Algorithm 6). NAG (Algorithm 7 and SNAG (Algorithm 2 applied the function (266). We also display the curvature of the function, which we define at x E R T direction of smallest curvature, and then move following this direction. Note also that the instability of SNAG enables itself to follow less strictly this smallest curvature ravine.
Az Note that the deterministic algorithms GD and NAG dive in the
on Figure 15
where we consider problem Actually if a and 02 have the same norm, the lowest RACOGA direction coincides exactly with the lowest curvature direction. As we mentioned in the previous paragraph that deterministic algorithms dive and stay in low curvature zone, they actually dive and stay in low RACOGA areas. The instability provided by stochasticity allows SNAG not to get stuck inside these low RACOGA areas.
0.1
0.2
CURVATURE
CURVATURE
RACOGA
RACOGA
Curvature
7
7
RACOGA
Vectors a a2
-0.1
0.0
Figure 15: Comparison of the RACOGA and curvature values for problem 2f along circle around the solution. On the left plot, a₁ and ag have the same norm, which is not the case the right plot. Note that the low curvature zone are close to the non positive RACOGA areas, and are exactly the same when dn and d2 have same norm.
53

---

Published as a conference paper at ICLR 2025
1.4 PROOF OF PROPOSITION
Proof of Equation (263)
We consider the least square problem defined by
1 f(z) = N (z)
-b)) 6:)²
(267)
with & 12 IP- IR differentiable and {az, 6,); random variables drawn i.idd
By the independence of the variable, we have for i + j
(IV = (E[V (IV) (=)]I
(268)
(269)
[[[[(((r 01) - a)) 2 0
(270)
Finally, we sum over N to get Equation (263
Proof of Equation 264
First, we compute for (a ,.... (())) E Rd and E R
E[((a, x) b)a} (E)
( Ela ..... E
1 Bl) (271)
We have a ~ N(m, I), b ~ ((m,, of with a IL b. So we can deduce that [( )2 = F + m.
and ((a(1) = Ti.j + m.my. Thereby, we have for fixed x E TRdd
Bi(( x)- - -b)a] = (E
EE
a - E[a
(272)
Σ Ela ( E[
fala (1) x - Ela E(bl
(273)
Ti + mimmat - mmm.,...........................
aai Σ
mamaa - m.mm)
(274)
Ti 11 .... Σ Tajan) (m...... ma) Σ maa mm(mm,....,a. ma)
(275)
Tw + (m" T x m2)m
(276)
From the previous computation and Equation 263 we deduce Equation (64
54


Reviews:
[{"review_id": "ouMrCaLzSC", "reviewer": "Reviewer_b9ZL", "summary": "This paper studies the possibility of obtaining accelerated convergence of the Stochastic Nesterov Accelerated Gradient (SNAG) method. The authors provide a clear proof that the average correlation between gradients allows to verify the strong growth condition, which is essential for achieving accelerated convergence in convex optimization settings. Furthermore, the paper includes comprehensive numerical experiments in both linear regression and deep neural network optimization, empirically validating the theoretical findings. The experimental results are clear and concise. These contributions advance the understanding of momentum-based stochastic optimization techniques and demonstrate the practical effectiveness of SNAG in enhancing convergence rates.", "questions": "* 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?\n* 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?\n* How robust is SNAG's performance to variations in RACOGA across different types of datasets and optimization problems?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Originality:\n- Proposes the hypothesis that Stochastic Nesterov Accelerated Gradient (SNAG) can accelerate over Stochastic Gradient Descent (SGD) and proves that this hypothesis is valid when SNAG is under a Strong Growth Condition. \n- Provides new asymptotic almost sure convergence results for SNAG. \n- Gives the new characterization of the SGC constant by using the correlation between gradients.\n- Introduces a new condition named Relaxed Averaged COrrelated Gradient Assumption (RACOGA).\n2. Quality and clarity:\n- Clearly shows when $f$ is convex and $\\mu$-strongly convex, it shows the possibility of acceleration of SNAG over SGD is highly dependent on the SGC constant $\\rho_K$, where $\\rho_K < \\sqrt{\\frac{L^2_{(K)}}{\\mu L}}$.\n- Provides clear and explicit steps for proofs.\n- The numerical results are readable and show a clear difference in convergence speed among different algorithms.\n3. Significance:\n- People can get faster and better results by applying the condition proposed in this paper.", "weaknesses": "* 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.\n* 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.\n* The colors in the right graph for Figure 1(a) are similar, author can use more contrasting colors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M1Di5xluhG", "reviewer": "Reviewer_zYBC", "summary": "The paper studies stochastic versions of Nesterov's accelerated gradient descent (NAG). These algorithms have been previously shown to converge at the same accelerated rates as NAG when the stochastic gradient estimates satisfy the so-called strong growth condition (SGC). Specifically for functions satisfying a finite sum structure, this paper finds a sufficient condition (RACOGA) in terms of gradient correlation that implies the strong growth condition, consequently implying that SNAG converges at an accelerated rate in those settings. Numerical experiments are provided to verify the implications of the RACOGA condition on accelerated convergence of stochastic algorithms.", "questions": "1. Was the Algorithm 2, in its given form, first introduced by Nesterov (2012) \"Efficiency of coordinate descent methods on huge-scale optimization problems.\"? If yes, the authors should cite that paper. I appreciate Proposition 4 in the appendix showing that the more common two parameter NAG algorithm (Algorithm 8, with $\\tau=0$) can be obtained as a special case of this algorithm with a reparametrization.\n\n2. Proposition 2 suggests that RACOGA holding with $c>-0.5$ is sufficient to verify the SGC. But in Figure 1(a), SNAG does not accelerate over SGD despite the RACOGA values being greater than -0.12. Is there an explanation for this apparent discrepancy?\n\n3. Just to confirm, in the experiments, were GD and NAG used with the full batch gradient at each step (e.g. were all of 50k images used for the CIFAR-10 experiment at each training step)? If yes, this might be worth specifying explicitly since most of the times in machine learning experiments, NAG refers to Algorithm 8, even when it is used with mini-batch gradients.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Previous works have shown that stochastic versions of NAG converge at the same accelerated rates when the gradient estimates satisfy the strong growth condition (SGC). While they provide heuristics that suggest that SGC is a reasonable assumption in the context of overparametrized deep learning, it is not always clear when the condition is actually satisfied. This work addresses that gap in the literature. The authors show that for functions of the form $f=\\sum_{i=1}^N f_i$, positive gradient correlation (i.e. $\\langle f_i, f_j\\rangle \\geq 0$ for all $i,j$) is sufficient to guarantee the strong growth condition for the gradients. This result also gives a bound for the strong growth parameter ($\\rho$) in terms of the batch size, which is important for choosing optimal parameters for the SNAG algorithms. The main contribution of the paper is a gradient correlation condition (RACOGA) which implies SGC for functions with a finite sum structure. This further implies that SNAG converges at an accelerated rate in those settings. I think this is a useful contribution and a step in the direction of better understanding why momentum-based stochastic gradient algorithms perform well in practice. The authors provide numerical experiments to back their claims, which I found interesting and insightful as well.", "weaknesses": "1. Line 70: \"However, even the question of the possibility to accelerate with SNAG in the convex setting is not solved yet.\"\nThis 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.\n\n2. 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.\n\n3. 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.\n\n4. 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(x^*) \\leq C/n^2$ simultaneously for all $n$ (and almost surely in probability), or does the random constant $C$ 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^*)$ are $o(n^{-2})$-close in a specific sense. More explanation is needed. The same concern applies to Theorem 2.\n\n5. 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.\n\n6. $L_{(K)}$ acts as an \"effective\" Lipschitz-continuity parameter of the gradient, depending on the batch size $K$. The results for SGD (Theorems 1 and 2) are provided in terms of $L_{(K)}$ without assuming SGC but the results for SNAG (Theorems 3 and 4) are provided in terms of the SGC parameter $\\rho_K$. Then these two results, derived under different conditions, are compared to conclude that SNAG does not accelerate over SGD unless $\\rho_k<\\frac{L_{(K)}}{\\sqrt{L}}\\cdot C$ (where $C$ is a constant that differs in the convex and strongly convex cases). This seems like an unfair and misleading comparison to me. Both, $L_{(K)}$ and $\\rho_K$, measure the stochasticity of the gradient estimates but in different ways. The authors demonstrate in Appendix E.2 an example where $L_{(K)}$ is a tighter estimate of the effective Lipschitz constant than $L\\rho_k$. That does show that if the smoothness parameter $L_i$ of each summand $f_i$ is known, then using $L_{(K)}$ would allow us to choose a larger step-size for SGD than the one provided by $1/L\\rho_k$. However, a fair comparison between SGD and SNAG can only be made if the same assumptions and information are used to calculate the step size, but there are no convergence results available for SNAG that directly make use of $L_{(K)}$. This feels like comparing apples and oranges. If the authors want to argue that you can use a larger step size for SGD than for SNAG, they should justify why Nesterov would blow up with that step size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2hOuHduR0J", "reviewer": "Reviewer_Dovy", "summary": "The authors study the convergence of SGD with momentum--Stochastic Nesterov Accelerated Gradient (SNAG) and obtained an improved rate compared to vanilla SGD. More precisely, they consider the strong growth condition that, intuitively, quantifies the amount of noise. Using this definition, they are able to achieve e.g. $o(\\frac{1}{n^2})$ convergence rate (SGD has $o(\\frac{1}{n})$) for convex functions. For certain objective functions, the authors propose a way to compute the strong growth condition and a new condition RACOGA. In addition, the authors have numerical experiments to verify their results.", "questions": "1. 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. \n\n2. 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 $\\rho_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 $\\rho_k$ 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-organized and easy to read. The material in the supplement serves as a good complement to the main paper. Experimental results are presented in a clear way with nice plots and great details.\n\n2. The main result is indeed very interesting to the community and gives some insight into a long-standing question. The theoretical contribution mainly comes from Theorem 4 which provides an almost surely convergence for SNAG showing a speed-up compared to SGD. \n\n3. By proposing a new characterization of SGC, the authors improved the assumption so that it only depends on the size of the dataset and batch size. Using this, the authors proposed a new condition--RACOGA. \n\n4. The authors also discuss the relation between batch size and gradient correlations which brings interesting insights into when to use stochastic and non-stochastic versions of these algorithms.", "weaknesses": "1. 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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2D7vwmIjV3", "reviewer": "Reviewer_wrcq", "summary": "This paper studies the acceleration of Stochastic Nesterov's Accelerated Gradient (SNAG) method over the SGD algorithm. In particular, the study is based on Vaswani et al, 2019, in which the acceleration is first proved based on the Strong Growth Condition (SGC) of the stocastic gradient. This paper extends the previous paper by showing an accelerated almost sure convergence result for SNAG, and develops condition that lead to a better SGC coefficient. Based on this condition, they show how the SGC coefficient changes as the batch size increases. The paper also verifies the condition using experiments.", "questions": "1. 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.\n\n2. In Example 3, the paper demonstrates the benefits of PosCorr condition over the traditional way of verifying the SGC condition by showing that $\\rho_K\\leq \\frac{N}{K}$. Why is $\\frac{N}{K} \\leq \\frac{L_{(K)}}{\\mu}$, so that it could be considered an improvement?\n\n3. What is $\\lambda$ in Figure 1?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper provides an extension of the original convergence theorem in Vaswani et al, 2019 in the almost sure convergence form, leading to a more comprehensive understanding of the SNAG algorithm.\n\n2. The paper's result covers both convex and strongly convex case. In particular, both the PosCorr and the RACOGA condition can lead to the SGC without assuming the strong convexity.\n\n3. Centered around the SGC, the paper develops conditions that implies the SGC, which allows the paper to investigate the relationship between the batch size and the SGC coefficient.", "weaknesses": "1. 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.\n\n2. 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 $c$ approaches to $-\\frac{1}{2}$, the SGC coefficient $\\rho = \\frac{N}{1 + 2c}$ approaches infinity, leading to a trivial condition.\n\n3. 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 $\\mathbf{a}_i^\\top \\mathbf{a}_j$, sign of the residual terms $\\mathbf{x} ^\\top\\mathbf{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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)