Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum Mechanism
Authors: Tehila Dahan
Kfir Yehuda Levy
Venue: ICLR 2025 Poster (2025)
Keywords: online convex optimization
stochastic convex optimization
Primary area: optimization
TL;DR: Stochastic convex optimization methods that allows easy tuning similarly to (noiseless) Gradient Descent

Abstract: Optimization methods are crucial to the success of machine learning, with Stochastic Gradient Descent (SGD) serving as a foundational algorithm for training models. However, SGD is often sensitive to the choice of the learning rate, which necessitates extensive hyperparameter tuning. In this work, we introduce a new variant of SGD that brings enhanced stability in two key aspects. First, our method allows the use of the same fixed learning rate to attain optimal convergence rates regardless of the noise magnitude, eliminating the need to adjust learning rates between noiseless and noisy settings. Second, our approach achieves these optimal rates over a wide range of learning rates, significantly reducing sensitivity compared to standard SGD, which requires precise learning rate selection.
Our key innovation is a novel gradient estimator based on a double-momentum mechanism that combines two recent momentum-based techniques. Utilizing this estimator, we design both standard and accelerated algorithms that are robust to the choice of learning rate. Specifically, our methods attain optimal convergence rates in both noiseless and noisy stochastic convex optimization scenarios without the need for learning rate decay or fine-tuning. We also prove that our approach maintains optimal performance across a wide spectrum of learning rates, underscoring its stability and practicality.  Empirical studies further validate the robustness and enhanced stability of our approach.

Published as a conference paper at ICLR 2025
Do STOCHASTIC, FEEL NOISELESS: STABLE STOCHAS- TIC OPTIMIZATION VIA A DOUBLE MOMENTUM MECH- ANISM
Tehila Dahan
Kfir Y. Levy
ECE Department
ECE Department
Technion
Technion
Haifa, Israel
Haifa, Isracl
t. d.daaancammpss ctt.smppuustecchioooo. technion.
ac.
k KFlryleevyttecchion..ca.
ABSTRACT
Optimization methods are crucial to the success of machine learning, with Stochas- Gradient Descent (SGD) serving as foundational algorithm for training models. However, SGD is often sensitive to the choice of the learning rate, which necessi- tates extensive hyperparameter tuning. In this work, we introduce a new variant SGD that brings enhanced stability in two key aspects. First, method allows the use the same fixed learning rate to attain optimal convergence rates regardless of the noise magnitude, eliminating the need to adjust learning rates between noiseless and noisy settings. Second, our approach achieves these optimal rates over wide range of learning rates, significantly reducing sensitivity compared to standard SGD, which requires precise learning rate selection. Our key innova- tion is novel gradient estimator based on double-momentum mechanism that combines two recent momentum-basee techniques. Utilizing this estimator, we design both standard and accelerated algorithms that are robust the choice of learning rate. Specifically, noiseless and noisy stochastic convex optimization scenarios without the need for learning rate decay or fine-tuning, We also prove that our approach maintains optimal performance across a wide spectrum of learning rates, underscoring its stability and practicality. Empirical studies further validate the robustness and enhanced stability our approach.
methods attain optimal convergence rates in both
INTRODUCTION
Stochastic Convex Optimization (SCO) is fundamental framework that captures several classical Machine Learning (ML) problems, such as linear regression, logistic regression, and SVMs (Support Vector Machines), amongst others. In the past decades, SCO has been extensively explored and highly influenced the field of ML: it popularized the use of Stochastic Gradient Descent (SGD) as the standard workhorse for training ML models; see e.g. Shalev-Shwarts
al. (2007); Welling Teh (201 I); Mairal et al. (2009); Recht et al. (201 (); as well as has lead to the design of sophisticated SGD variants that play a central role in training modern large scale models (Duchi et al., 2011: 1; Kingma Ba, 2015).
One practical difficulty in applying SGD-type methods is the need to tune its learning rate among other hyperparameters, and is well known that the performance of such algorithms crucially relies on the right choice of the learning rate. Adaptive SGD variants, such as AdaGrad and Adam (Duchi et al., 2011; Kingma & Ba, 2015; Levy et al., 2018: Kavis al., 2019; Jacobsen & Cutkosky, 2022) have been designed to alleviate this issue by adjusting the learning rate during training. However, despite reducing the need for hyperparameter tuning, adaptive methods can introduce additional complexity and may not always lead to better generalization performance. In many applications, practitioners still prefer to employ standard SGD because it often results in better test error and improved generalization compared to adaptive methods (Wu et al., 2016; Ruder, 2016). Thus, designing SGD variants that are robust to the choice of learning rate, while retaining the simplicity and generalization benefits of standard SGD, be extremely beneficial in practice.

---

Published as a conference paper at ICLR 2025
To address these challenges, we propose new approach that retains the simplicity and generalization benefits of standard SGD while significantly enhancing its robustness to learning rate selection. Moreover, since our method focuses stabilizing the gradient estimation rather than adapting the learning rate, it is orthogonal to adaptive techniques and could potentially be combined with them to yield even better performance.
Focusing on the SCO Setting: In this paper focus on the prevalent SCO setting where the objective (expected loss) is an Expectation Over Smooth losses (SCO-EOS); this applies c.g. to linear and logistic regression problems (though not to SVMs). In this case, it is well known that SGD requires a careful tuning of the learning rate to obtain the optimal performance. For example, in the noiseless case, SGD (or GD in this case) should employ a learning rate of nf the smoothness parameter of the objective. Nevertheless, if we apply this 7) Offiime in the noisy setting, the guarantees of SGD become vacuous. To obtain the optimal SGD guarantees,
1/L where L is
should roughly decrease the learning rate by factor of T where T is the total number of SGD iterates (and samples), and o is the variance of the noise in the gradient estimates. This illustrates the sensitivity of SGD to the choice of 1), a challenge that also affects stochastic accelerated methods such as those in Lan (2012); Hu et al. (2009); Xiao (2010).
Contributions. We introduce a novel gradient estimator for SCO-EOS problems that uses a single sample per-iterate, and shows that its square error, ||=:||², shrinks with the number of updates as ||oll x 1/t, where t is the iterate. This, in contrast to the standard SGD estimator where usually | = Variance, = O(1). Our new estimator blends two recent mechanisms that are related to the notion of momentum: Anytime Averaging, which is due to Cutkosky (2019); and corrected momentum technique (Cutkosky & Orabona, 2019). We therefore denote our estimator by ju² which stands for Momentum².
As described below, our new estimator enables "Do Stochastic (optimization), while feeling Noiseless", i.c. it allows us to use similar machinery as GD employs in the noiseless case. Specifically, (i) we can use the exact same fixed learning rate as used in GD, irrespective of the noise; (ii) enables us to use the norm of the gradient estimates as a stopping criteria, which is common practice for GD (Beck, 2014). Finally, (iii) enables us to design new SGD variants which are extremely robust to the choice of the learning rate, significantly reducing sensitivity compared to standard SGD,
Concretely, we design an SGD variant called 1²-SGD, as well as an accelerated version called 2² ExtraSGD, that employs our new estimator and demonstrates their stability with respect to the choice of the learning rates 17. We demonstrate the following,
For S Upon using the exact same learning rate of 1) Offline 1/8LT' (where T is the total number of iterates/data- (ierates/data-samples)).. j.2-SD enjoys convergence rate of OLLTT) in the noiseless case, and rate of OL//T + + in the noisy case. Moreover, in the noisy case, 1z²DSGD enjoys the same convergence rate of the optimal SGD O + a / /T), for wide range of learning rate choices i.e. 7) E myn max) with the ratio y/max/ /1jx/// min as (ō/L)VT.
For n1² ExtraSGD : Upon using the exact same learning rate of 17 of = 1/2T. n₂² ExtraSGD enjoys an optimal convergence rate of (T./T²2) in the noiseless case, and an optimal rate of (L/T² + a /TT) in the noisy case. Moreover, in the noisy case, μ²² ExtraaCO enjoys the same optimal convergence of ( + +a/V/)/ for an extremely wide range of learning rate choices i.e. 1) E [ng 1 n),,, with the ratio 77m min = (ō/ GL)/33/2 The optimal rates mentioned above are also tight for SCO-EOS problems, see e.g. Thm. 16.7 in Cutkosky (2022a).
These ratios are substantially larger than the corresponding ratio for standard SGD, where the optimal convergence is achieved only when my /y, x O(1). This establishes the substantial improvement in stability of our approach compared to standard SGD (see Appendix A for a detailed discussion).
We empirically demonstrate the improved stability and performance of our methods over various basclines, confirming both the theoretical and practical advantages of our approach.
On the technical side, it is important to note that individually, each of the momentum techniques that we combine is unable to ensure the stability properties that we are able to ensure for their appropriate combination, i.e. for -SDD and for μ1² Ext EaSGD Morcover, accelerated version μ²² ExxraSGG, requires a careful and delicate blend of several techniques in the right interweaved manner, which leads to concise yet delicate analysis.
2

---

Published as a conference paper at ICLR 2025
Related Work: The Gradient Descent (GD) algorithm and its stochastic counterpart SGD (Robbins & Monro, 1951) are comerstones of ML and Optimization. Their adoption in various fields has lead to the development of numerous elegant and useful variants (Duchi et al., 2011; Kingma & Ba, 2015; Ge et al., 2015). Curiously, many SGD variants that serve in practical training of non-convex learning models; were originally designed under the framework of SCO.
As we mention in the introduction, the performance of SGD crucially relies on the choice of the learning rate. There is plethora of work on designing methods that implicitly and optimally adapt the learning rate throughout the learning process (Duchi et al., 2011; Kingma & Ba, 2015; Kavis al., 2019; Antonakopoulos et al., 2022; Jacobsen Cutkosky, 2022: Ivgi al., 2023; Defazio & Mishchenko, 2023); and such methods are widely adopted among practitioners. Nevertheless, in several practical scenarios, standard (non-adaptive) SGD has proven to yields better generalization compared to adaptive variants, albeit still necessitating to find an appropriate learning rate (see e.g. Giladi et al. (2019)).
Momentum (Polyak, 1964) is another widely used practical technique (Sutskever et al., 2013), and it interestingly related to the accelerated method Nesterov (Nesterov, 1983) - seminal approach that enables to obtain faster convergence rates compared to GD for smooth and convex objectives. While Nesterov's 's accelerated method is fragile to noise, Lan (2012); Hu et al. (2009); Xiao (2010) have designed stochastic accelerated variants that enable obtain convergence rate that interpolates between the fast rate in the noiseless case and between the standard SGD rate in the noisy case (depending on the noise magnitude).
Our work builds on two recent mechanisms related to the notion of momentum: (i) An Anytime averaging mechanism Cutkosky (2019) which relies on averaging the query points of the gradient oracle. And (ii) corrected momentum technique Cutkosky & Orabona (2019) which relies on averaging the gradients themselves throughout the learning process (while introducing correction). is interesting to note that the Anytime mechanism has proven to be extremely useful in designing adaptive and accelerated methods (Cutkosky, 2019; Kavis al., 2019; Antonakopoulos et al., 2022). The corrected momentum mechanism has mainly found use in designing optimal and adaptive algorithms for stochastic non-convex problems (Cutkosky & Orabona, 2019; Levy et al., 2021).
2 SETTING
Consider stochastic optimization problems with convex objective S K. + R that satisfies,
f(x) (x;
(1)
where KC C IR is a compact convex set, and D is an unknown distribution from which we may draw i..d. samples { D}. We consider first order optimization methods that iteratively employ such samples in order to generate sequence of query points and eventually output a solution Foutput E X. Our goal to approximately minimize ʃ(.), so our performance measure the expected excess loss,
ExcessLoss := (Z]((tooptt))) min f(x),
=eK
where the expectation is w.r.t. the randomization of the samples.
More concretely, at every iteration t such methods maintain a query point x E Rd which is computed based on the past query points and past samples {2I,..., -t-1 Then, the next query point #++1 is computed based on H, and on a gradient estimate Sr that is derived by drawing a fresh sample 2, D independently of past samples, and computing, 9t- == V ( Note that this derivative is w.r.t. II The independence between samples implies that gr is an unbiased estimate of f.();;) in the following sense, Elg, 22, = fz.) It is often comfortable to think of the computation of Dt (I 21) as a (noisy) Gradient Oracle that upon receiving query point 2, E K. outputs vector 9r E IRd, which is an unbiased estimate of (x())).
Assumptions. We will make the following assumptions, Bounded Diameter: There exists D > such: max,, | - yll S S.
Bounded variance: There exists 0 such,
[ - vf(+)| oo² Yr E.
(2)
3

---

Published as a conference paper at ICLR 2025
Expectation smooth functions: There exists L such Vz, E K. Support(D):
[[V V/(n=)) =)ll s L|| - -yl
This implies that the expected loss f()) is L smooth. Bounded Smoothness Variance. The above assumption implies that there exists o E [0, L2] such,
E [[(V{(z;=) vf())) (VI(w: vf()) ofl yl1 Vx, K.
(4)
Clearly, in the deterministic setting where f( f(x) V2 Support(D). we have or In App. B, we show how Eq. (3) implies Eq. (4).
Notation: The notation f 2) relates to gradients with respect x, i.e., V = Vz. We use || to denote the Euclidean norm. Given a sequence {Ve) we denote 3o == Σr= y,- For a positive
integer N we denote [N] [1.....N], We also let Hy R + K. denote the orthogonal projection onto K., i.e. (x) arg min lly Ve Rd We shall also denote σ² 32D 20
3 MOMENTUM MECHANISMS
Here, we provide background regarding two mechanisms that related to the notion of momentum. Curiously, these approaches are related to averaging of different elements of the learning algorithm. Our approach presented in Sec. 4 builds on combination of these aforementioned mechanisms.
3.1
MECHANISM I: ANYTIME-GD
This first mechanism is related averaging the query points for the noisy gradient oracle. While in standard SGD query the gradients at the iterates that we compute, in Anytime-SGD (Cutkosky, 2019), we query the gradients at weighted averages of the iterates that we compute.
More concretely, the Anytime-SGD algorithm (Cutkosky, 2019; Kavis et al., 2019) that we describe in Equations (5) and (6), employs a learning rate v > and a sequence of non-negative weights {az J.. The algorithm maintains two sequences {w; Jts {xr Je. At initialization ø1 W1. and,
W++1 wt n749t Vt E [T] where 9r vz(zz)))
(5)
where 24 ~ D. Then Anytime-SGi updates,
Ond +
01+1
T++1
W[+1
(6)
014+1
01441
The above implies that the x; 's are weighted averages of the wy's, i.e. that r1+1
en 11 Er=1 W-W+
Thus, every iterate, the gradient gi is queried at xe which is weighted average of past iterates, and then W is updated similarly to GD with a weight a on the gradient 9t-
Curiously, it was shown in Wang al. (2021) (see Sec. 4.5.1), that very similar algorithm to Anytime-GD. can be related to the classical Heavy-Ball method (Polyak, 1964), and the latter incorporates momentum in its iterates. Cutkosky (2019) has shown that Anytime-SGD obtains the same convergence rates as SGD for convex loss functions (both smooth and non-smooth). And this technique was found be extremely useful in designing universal accelerated methods (Cutkosky, 2019; Kavis et al., 2019).
The next theorem is crucial analyzing Anytime-SGD and actually applies more broadly,
Theorem 3.1 (Rephrased from Theorem 1 in Cutkosky (2019)). Let K. ++ be a convex function with a minimum w" E arg min (w). Also let {a, 2 0}, and {w; E Kh,, {x, E K),, such that {a+} is an {at}e weighted average of (we)t. t. i.e. such that Iı wr, and for any Z It-1 0nit1 E1t1 W,W,, Then the following holds for any 2 1: an: (f(x)) - f(w*)) E
a, Vf(x)) Ei
(w, -
The above theorem holds for any sequence (w: E Kh,,, and as private case holds for the Anytime- GD algorithm. Thus the above Theorem relates the excess loss of given algorithm that computes the sequences {w, E K)+, {ar JC}, its weighted regret, R, Σt a ff(x)) (w, w²)
4

---

Published as a conference paper at ICLR 2025
3.2 MECHANISM II: RECURSIVE CORRECTED AVERAGING
This second mechanism is related to averaging the gradient estimates that we compute throughout training. which is common and erucial technique in practical applications. While straightforward averaging might incur bias into the gradient estimates, it was suggested in Cutkosky & Orabona (2019) to add a bias correction mechanism named STORM (STochastic Recursive Momentum), And it was shown that this mechanism leads to a powerful variance reduction effect.
Concretely, STORM maintains an estimate de which a corrected weighted average of past stochas- tic gradients, and then it performs an SGD-style update step,
W+++1 = W² r/d.-
The corrected momentum estimates are updated as follows,
d₂ = [w,; z,) + (1 - (c) V[(
(8)
for some Be [0, 1]. The above implies that Ejd,] = EVf Nevertheless, in general Ejd,/un [uy] * f(()), so de is conditionally biased (in contrast to standard SGD estimates). Moreover, the choice of the same sample oN in the two terms of the above expression is crucial for the variance reduction effect.
4 OUR APPROACH: DOUBLE MOMENTUM MECHANISM
Our approach is combine together the two momentum mechanisms that we describe above. Our algorithm is therefore named SSG (Momentum 2 -Stochastic Gradient Descent), and we describe Alg. Intuitively, each of these Momentum (averaging) techniques stabilizes the algorithm. and their combination leads to a method that is almost as stable as offline GD. Note that the right combination of these techniques crucial to obtaining our results, which cannot be achieved by employing only one of these technique without the other.
We first describe algorithm and then present our main result in Theorem 4.1, showing that the error of the gradient estimates of our approach shrinks as we progress. Suggesting that we may use the norm of the gradient estimate as a stopping criteria which is common practice in GD (Beck, 2014). Another benefit is demonstrated in Thm. 4.2,is that 22G obtains the same convergence rate as standard SGD, for a very wide range of learning rates (in contrast to SGD).
Next we elaborate on the ingredients of Alg. 1:
Update rule: Note that for generality we allow a broad family of update rules in Eq. (10) of Alg. 1. The only constraint the update rule is that its iterates {wt ) always belong to K. Later, will specifically analyze the natural SGD-style update rule,
Wt+1 [lx(w; na,de).
Momentum Computation: From Eq. (12) in Alg. we can see that the momentum de is updated similarly to the STORM update in Eq. (8), albeit with two main differences: (i) first we incorporate importance weights farhe into STORM and recursively update the weighted momentum a,d,- More importantly (ii) we query the noisy gradients at the averages x, rather than in the iterates themselves, and the averages (Eq. (11)) are computed in the spirit of Anytime-SGD These can be seen the computation J++1 and ÿt which query the gradients at the averages rather than the iterates. Thus, as promised our algorithms combines two different momentum mechanisms.
Next, we present our main result, which shows that Alg. yields estimates with a very small error. The only limitation the update rule in Eq. (10) is that its iterates {we) always belong to K. Theorem 4.1. Let f K + R. and assume that K. is convex with diameter D, and that the assumption in Equations (2) hold. Then invoking Alg. I with {a, = + 1h and {3, = 1/a,), ensures, Elle,1 12 == E, V f(2,))1 < 8² /t,
here 4 : (zz)), and x2 = 32D + 20 * In App. D.I we provide high-prob. bounds.
So according to the above theorem, the overall error of d, compared to the exact gradient V fx;) shrinks progress. Conversely, in standard SGD (as well as in Anytime-SGDD the expected square error is fixed, namely Elgg. (( < O
Based Thm. 4.1, 1, we may analyze Alg. 1 with the specific SGD-type update rule presented in Eq. (9).
5

---

Published as a conference paper at ICLR 2025
Algorithm P2D
Input: #lterations T. initialization æ1, > O, weights far)., Corrected Momentum weights { Initialize: set W1 21, draw 21 D and set dj =V 21)
for t 1,..., T do
Iterate Update:
Use an update rule to compute W1+1 E K.
(10)
Query Update (AnytimeSGiD style):
Tt+1 01:4+1
Ond
Tt. +
0++1
Wx+1
(11)
01+++1
Update Corrected Momentum (STORM stte):
draw 2e+1 ~ D, compute g++1 == Vf( 2++1, and 01 == (f(riize1)) and update,
d,41 9.+1 + (1 (c+ 9.)
(12)
end for output: 2T
Theorem 4.2 (p²-SGD SGD Guarantees). Let f. F + R be a convex function, and assume that w E arg wex f(w) is also its global minimun in Rd. Also, let us make the same assumptions as in Thm. 4. I. Then invoking Alg. I with {a, =t+ =t+1] and (3e = 1/04)tt. and using the SGID-type update rule (9) with learning rate n S 1/8LT inside Eq. (10) of Alg. I guarantees.
B(f(rT) f(w")))))))))))))))))))) EAT S 00
D2
+ +na²² + 4Dō
1/T²
VT
where A, = f(x)) f(w"), and 0² = 32D 07. 20
Stability of PDDSGD The above lemma shows that SSD obtains the optimal SGD convergence rates for both offline (noiseless) and noisy case with the same choice of fixed learning rate 17 Offfine SLT' which does not depend on the noise 5. This in contrast to SGD, which require either reducing the offline learning rate by factor of ovT; using sophisticated adaptive learning rates (Duchi et al., 2011; Levy et al., 2018).
1
Moreover, letting Noiay 1/(8T. + 2T3/2 than it can be seen that in the noisy case our approach enables to employ learning rates in an extremely wide range of iyNNoay, , Offline]; and still obtain the same optimal SGD convergence rate. Indeed note that, 1y Offtine /1/ Noiey = 10/L)T1/2
Note that in Theorem 4.2 we assume that the global minimum of f(.) belongs to K.. In the next section we present n Ext raGDD an accelerated version of 1 -SGD, that does not require this assumption, and enables to obtain accelerated convergence rates as well as better stability.
Comment:
4.1 EXTENSIONS
Unitormly Small Error. We have shown that upon using single sample per-iteration, our approach enables to yields gradient estimates dj 's with a shrinking square error of (11/t). Nevertheless, if we like to incorporate early stopping, it is desirable to have uniformly small error of 0 across all iterates. In the appendix we show that this is possible, and only comes at the price of a logarithmic increase in the overall sample complexity. The idea is to incorporate decaying batch-size into our approach: at round f we suggest to use a batch-size b, x T/t. Thus, along T rounds we use a total of
EL by O(T log T') samples. This modification allows uniformly small square error of (1/TT)
across all iterates.
Accurate Estimates of General Operators. We have shown that approach enables yield O(1/t) estimates for gradient estimates of the query point (re)ee This can be similarly generalized to yielding (11/t) estimates for other operators. For example, if we like to estimate the Hessian ((x))) and we assume Lipschitz continuous Hessians and bounded variance analogously to Eq. (2), then we can maintain good Hessian estimates in the spirit of Eq. (12)
Unweighted Variant of R-GD. It is natural to ask whether
employ the more standard

---

Published as a conference paper at ICLR 2025
uniform weights far Nejj.. within SGD. Going along very similar lines to proof for Thm. 4.2, we show that this indeed can be done while using x 1/L T, and yields similar bounds, albeit suffering logarithmic factors in
4.2 NECESSITY OF BOTH MECHANISMS
Here discuss the importance of combining both Anytime and STORM mechanisms to obtaining the shrinking error property (see Thm. 4.1) of j²-SGD, which is a key to our other results. Concretely, the Anytime mechanism (without STORM appearing in Equations (5) (6), is employing gradient estimates of the form 9r == V (x)) and it is therefore immediate that error of these gradient estimates ||e, Amytime 1| = 19: (xx,)) 1 is O(1), which is similar to standard SGD. Conversely, the STORM mechanisms (without Anytime) appearing in Equations (7) (8) maintains estimates dg The STORM update rule yields variance reduction, which depends the distance between consecutive query points i.e. ||,0, - we-1ll?, which will in turn depend on the learning rate (as in the original STORM paper). This couples between the variance reduction mechanism and the learning rate, and therefore fails to achieve robustness to the learning rate (for example: using a fixed learning rate within the standard STORM approach will fail to converge). Thus, the combination of these techniques is crucial towards obtaining the shrinking error substantiated in Thm. 4,1, which independent of the learning rate, and therefore allows obtain stability as we substantiate in Theorems 4.2 and 5.2.
4.3 PROOF SKETCH OF THM. 4.1
Proof. First note that the x2 always belong K., since they are weighted averages of {w,, E K'''s. Our first step is to bound the difference between consecutive queries. The definition of ze implies: 01:11( 21-1) ar(w; - xz) yielding.
|| -t- ||2 = (as/ana-1) 1)² |w,, - xz 111 S (16/a4-1)D2
(13)
where we used 0g = +++ 1 implying ar/ /1/an=111 S 4/0x-1 for any 2 2, we also used I|w, -rell < D. Notation: Prior to going on with the proof we shall require some notation. We will denote St = fæ(z), and recall the following notation from Alg. 1: 9t == Vf 2x) :9:-1 == Vf(Ia-1.2)) We will also denote, Et == de- - Dt
Recalling Eq. (12), and combining it with the above definition of e, enables to derive the following.
Qt 0ttt = 3,ar(g - g.) + (1 Ban + 0: at a1-16--))
where denote Z, := (g): 9t) (g) 1 It- Now, using an 1+ 1, and 3r = 11/(++1) then it can be shown that ar3r = l,and a; (1 Bi) a: - 1 = a-1 Moreover, (1 3;) _ 2--1 1. Plugging these above yields,
ar-1
06-1
Ocfi = 04--1 74 + 04 16t-1 + (gt - gt) = M₁ + 14-1--11
(14)
where for any >> 1 we denote M; at-1 Z + (g: 9r), well M1
91 -T. Unrolling the above equation yields an explicit expression for any E [T]: a = Σ M,
Notice that the sequence {Mr h is martingale difference sequence with respect to the natural filtration {Fi), induced by the history of the samples up to time t; which implies,
E||aaee/11== =
Σ M
Σ
12
< Σ
1 21 + Σ
Elige gt ge
(15)
T=1
r=1
Using Eq. (4) together with Eq. (13) allows to bound, E E| 7, 1
El 9t) - -0r-1 -t-1) 1|1 <
of [x fz-1ll² < 160 D2/02_, and we may also bound Ellge Ft 112 S 0². Plugging it above
back into Eq. (15) and summing establishes the theorem.
ACCELERATED VERSION: 1r2 EXTRASGD
Here we present an accelerated version that makes use of a double momentum mechanism as we do for S²DD Our approach relies on an algorithmic template named ExtraGradient (Korpelevich,
7

---

Published as a conference paper at ICLR 2025
1976; Nemirovski, 2004; Juditsky al., 2011). The latter technique has already been combined with the Anytime-Sa SGD mechanism in Cutkosky (2019); Kavis et al. (2019), showing that it leads to acceleration. Here, further blend appropriate STORM Mechanism, leading to new method that we name n²² - ExtraSGD. Our main result is presented in Thm. 5.2.
On the technical side, accelerated version requires careful and delicate blend of several techniques in the right interweaved manner, which leads to a concise yet delicate analysis.
The extragradient technique is related to an algorithmic template named Optimistic Online GD (Optimistic OGD) (Rakhlin & Sridharan, 2013). In this algorithm
Optimistic OGD, Extragradient and UnixGrad:
receive sequence of (possibly arbitrary) loss vectors {d, E R "<([T]] in an online manner. And our goal is to compute sequence of iterates (or decision points) {we E K) where X is given convex set. Note that we may pick Wi only based on past information {d1,...,44- d.-1) And our goal is ensure low weighted regret for any w K. where the latter defined as,
RT(W)= = Σ o,ds (wi w²)
t=1
and {az 0} is sequence of predefined weights. In the optimistic setting we assume that we may access a sequence of "hint vectors" {dl E Rd), and that prior to picking w, we may also access {di...., dej. Rakhlin & Sridharan (2013) have shown that if the hints are useful, in the sense that d, ss de, then one can reduce the regret by properly incorporating the hints. Thus, in Optimisti-OGD we maintain two sequences: a decision point sequence {wi and an auxiliary sequence {yr J. updated as follows,
Optimistic OGD:
1 2m
1 11 1e-2
& Us arg min ande + Wt: arg min Crdq w ||-- 1111
(16)
vek.
2n
was shown in Rakhlin Sridharan (2013); Kavis et al. (2019) that the above algorithm enjoys the following regret bound for any w E K.,
Theorem 5.1 (See e.g. the proof of Thm. in Kavis et al. (2019)). Let n > O, {ax, 2 Oher and K. be convex set with bounded diameter D. Then Optimistic-OGi ensures the following for any W E K.
Σand (we - w)
T
4D2
allld - ddl1? 2
n
2 1=1
T
Σ
T ww 1122
2n
The Extragradient algorithm (Nemirovski, 2004) aims to minimize a convex function f IC + R. To do so, it applies the Optimistic-OGD template with the following choices of loss and hint vectors: de (y)--),. and d; :- f((w)). The UnixGrad algorithm (Kavis et al., 2019), can be seen as an Anytime version of Extragradient, where again we aim to minimize convex function f IC ト RR In the spirit of Anytime- GD, UnixGrad maintains two sequences of weighted averages {1r, 3e based on (we, he
01
Ft-1
Vt-1
Ft.
01: Ft-1 +
Ot
(17)
01d
Q1:
ar
Then, based on the above averages UnixGrad sets the loss and hint vectors as follows: d, = (+t). and de == ffxt). Note that the above averaging rule implies that the x, 's are weighted averages of the wo 's, i.. F2 01. Σ W, The latter enables to utilize the Anytime guarantees of Thm. 3.
There also exist stochastic versions of the above approaches where may only query noisy gradients.
Our Approach. We suggest to employ the Optimistic-OGD template together with STORM mechanism on top of the Anytime mechanism employed by UnixGrad. Specifically, we maintain the same weighted averages as in Eq. (17), and define momentum estimates as follows:
At round draw fresh sample 2, ~ D. and compute
- = [ 2)) Ò: = (f(G))) 9: = V V (x)
(18)
Based on the above compute the (corrected momentum) loss and hint vectors as follows,
ayd; a.g: + (1 Be)ar(de-1 -1-1) & onde orgi + (1 (e)o Ōc-1) (19)
8

---

Published as a conference paper at ICLR 2025
Algorithm 2 n² ExtraSGD
Input: #lterations T. initialization Vo. 1j > O, weights (ar)., Corrected Momentum weights {Br}
Initialize: set zn = 0, and é = yo, draw 21 ~ and set dg = 90 = di = 21)
for t I,..., do
Compute: wy arg min ande 27 I|w - y--1 Update: zt. weK
1 - +
aL Wt antt
an
Compute: = V (1)) & Update: dj 9t + (1 - (e) 1 91-1)
Compute: Y/ arg min ord, by 11 & Update: t yEλ.
abd astl M/ anit
01:411
Draw a fresh sample 2++1 D and compute, g. = v f((322+11 91+1 Vf($2+1,244)
Update: de41 = 94+1 + (1 B(+1)(ds 3t) end for oulput: 27
And then update according Optimistic OGD in Eq. (16). Notice that the update rule for azd, is the exact same update that we use in Alg. I; additionally as we have already commented, the o; sequence in Eq. (17) is an {a+): J weighted average of the {w;} sequence. Therefore, if pick a₁ = t + and B = 1/as, then we can invoke Thm. 4.1 implying that,
E 2 == Elid - ff(x)) 02/t, where x² := :2D + 2
The poeudo-code in Alg. depicts our 21² Ext r aSG algorithm with the appropriate computational order. It can be seen that it combines Optimistic-OGii updates (Eq. (16)), together with appropriate Anytime averaging (Eq. (17)), and together with STORM updates for de, de (Eq. (19)).
We are now ready to state the guarantees of μ ExtraSGD
Theorem 5.2 (12 ExtraSGD ). Let f K. - R be a convex function and K. a convex set with diameter D, and denote w* E arg we fw) Then under the assumption in Equations (2)), invoking Alg, 2 with {a= = t+ 1 and {3, = 1/0r]t. and 1) S 1/2L guarantees,
1/12 +
D2
ēD
E(f(xT) f(w")) EÅT S
As can be seen in Alg. 2, the appropriate 4² accelerated version requires a careful and delicate blend of the aforementioned techniques in the right interweaved manner.
Stability of 212 ExtraSGD The above lemma shows that /ي² ExtraSGD obtains the optimal rates for both offline (noiseless) and noisy cases with the same choice of fixed learning rate o7 Offliee = 1/2L. This contrasts existing accelerated methods, which require either to reduce the offline learning rate by factor of T (Xiao, 2010); or to employ sophisticated adaptive learning rates (Cutkosky, 2019; Kavis al., 2019). Moreover, letting 17 /Naisy := 1/(2L 0T then it can be seen that in the noisy case, our approach enables to employ learning rates in an extremely wide range of Noisy, Offline]; [,,Noisy,,
and still obtain the same optimal convergence rate of O (LD² / + @D/VT). Indeed note that, the ratio 17 Offline Noiny (ō/L)r8/2, Moreover. conversely to Thm. 4.2, which requires w" arg wik fww to be also the global minimum of f()): Thm. 5.2 does not require this assumption.
EXPERIMENTS
We begin by evaluating our proposed SGD algorithm in a conver setting, where model weights were projected onto a unit ball after each gradient update. The evaluation is conducted on the MNIST dataset (LeCun et al., 2010), using a logistic regression model. We compare our approach with the parameters suggested by our theoretical framework (a: t, 3 = }) against several baseline optimizers. This includes each individual component of the SSD Any TnyTeme-SGre SGD all tested with the same parameter settings. As illustrated in Figure the 2²D algorithm consistently demonstrates superior stability across a wide range of learning rates. Notably,
SrrnthmmSTTRMMM and

---

Published as a conference paper at ICLR 2025
while the AnyTime-SOh SGD algorithm maintains strong stability broad spectrum of learning rates, STORM encounters difficulties at higher rates. By combining both methods, μr SSD achieves greater stability and performance, outperforming each approach individually. Additionally, when considering a more typical range of learning rates for this setup (see Figure 1b), SDDSGD may not always achieve the absolute best result compared the other algorithms. Nevertheless, consistently achieves high performance and robustness across broader range of learning rates, significantly reducing the need for an extensive search to find a segh-perfrrmig learning rate. On top of that, by leveraging the momentum parameters grounded in our theoretical framework, SCG further eliminates the need for hyperparameter tuning a process that can be highly computationally expensive.
b Over Typical Range Learning Figure 1: MNIST: Test Accuracy Over Different Learning Rates in Convex Setting better).
Wide Range caning
Deep Learning Variant. We demonstrate the effectiveness of our approach in non-comee settings using 2-layer convolutional network on the MNIST dataset and ResNet-18 on the CIFAR- 10 dataset (Krizhevsky et al., 2014). First, we reformulate the AnyTime update, originally defined as into a mathematically equivalent momentum-base based approach: 01d
It = 7/244 + (1 -/)
where 7t- =
ans For non-convex models, decaying momentum parameters in the iteration number can be overly aggressive; thus, we propose heuristic approach using fixed momentum parameters to improve adaptability. Note that, by setting or = Ca where C' >> 0 is constant, we derive
C C.T. making it fixed for all time steps 2 1.
We show that using fixed momentum parameters (7+- = 0.1, 8, = 0.9) in the non-convex setting ensures high stability and strong performance (i) across wide range of learning rates and (fi) over random seeds, as shown in Figure 2 and in App. H.3. Consistent results were observed on
both MNIST and CIFAR-10, detailed in App. H.3. These findings highlight the robustness and adaptability of our method, making it a reliable choice for optimizing non-convex models.
a CIFAR Wide Runge
b CIFAR 10: Overa Typical Search Range.
C MNIST: Over Typical Search
Figure 2: Test Accuracy Over Range of Learning Rates in Non-Convex Setups (1 is better).
All experiments were conducted using the PyTorch framework. The convex experiments were run on an Apple M2 chip, while the non-convex experiments were executed on NVIDIA A30 GPU. The results were averaged over three different random seeds. For additional details, refer to Appendix H and our GitHub repository."
7 CONCLUSION
By carefully blending two recent momentum techniques, designed new shrinking-ens gradient estimate for the SCO-EOS setting. Based on it, we presented two algorithms that rely on SGD and Extragradient templates and showed their significant stability w.r.t. the choice of the learning rate, thus enabling a much more robust training. In the future, it will be interesting to further explore the applicability of our non-convex heuristic for huge-scale models, which require much more computational resources. Moreover, it will be interesting to understand whether we can design an algorithm for non-convex problems, with similar theoretical properties our approach.
Phttps://0g http://gttttt thub. com. com/daham dahann /mddgd
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
This research was partially supported by Israel PBC-VATAT, by the Technion Artificial Intelligent Hub (Tech.AI) and by the Israel Science Foundation (grant No. 3109/24).
REFERENCES
Kimon Antonakopoulos, Dong Quan Vu, Volkan Cevher, Kfir Levy, and Panayotis Mertikopoulos. Undergrad: A universal black-box optimization method with almost dimension-free convergence rate guarantees. In International Conference on Machine Learning, pp. 772-795. PMLR, 2022.
Amir Beck. Introduction to nonlinear optimization: Theory, algorithms, and applications with
MATLAB. SIAM, 2014.
Ashok Cutkosky. Anytime online-to-batch optimism and acceleration. In International Conference on Machine Learning, pp. 1446-1454. PMLR, 2019.
Ashok Cutkosky. Lecture notes for ec525: Optimization for machine learning. EC525: Optimization for Machine Learning, 2022a.
Ashok Cutkosky. Lecture notes for ec525: Optimization for machine learning. EC525: Optimization for Machine Learning, 2022b.
Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Aaron Defazio and Konstantin Mishchenko. Learning-rate-Fin frre---reeeeee learning by D-adaptation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 7449-7479. PMLR, 23-29 Jul 2023. URL https: pttpppeecceennseeeeeee www.mmrr......
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points- stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference Learning Theory, pp. 797-842, 2015.
Niv Giladi, Mor Shpigel Nacson, Elad Hoffer, and Daniel Soudry. At stability's edge: How to adjust hyperparameters preserve minima selection in asynchronous training of neural networks? In International Conference on Learning Representations, 2019.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):1577325, 2016.
Chonghai Hu, Weike Pan, and James T Kwok. Accelerated gradient methods for stochastic optimiza- tion and online learning. In Advances in Neural Information Processing Systems, pp. 781-789, 2009.
Maor Ivgi, Oliver Hinder, and Yair Carmon. Dog is sgd's best friend: A parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference Machine Learning (ICML), 2023.
Andrew Jacobsen and Ashok Cutkosky. Parameter-free mirror descent. arXiv preprint arXiv:2203.00444, 2022.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: a universal, adaptive algorithm with optimal guarantees for constrained optimization. Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 6260-6269, 2019.
11

---

Published as a conference paper at ICLR 2025
Diederik P. Kingma and Jimmy Ba. Adam: A 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. URL http: //arxiv. org/ abs / 112...6 6980.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. online: http://www. cs. toronio. edu/krizciifar himl, 55(5), 2014.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1-2):35--37, 2012.
Yann LeCun, Corinna Cortes, Chris Burges, et al. Mnist handwritten digit database, 2010.
Kfir Yehuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In NeurlPS, 2018.
Kfir Yehuda Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. In NeurlPS, 2021.
Julien Mairal, Francis Bach, Jean Ponce, and Guillermo Sapiro. Online dictionary learning for sparse coding. In Andrea Pohoreckyj Danyluk, Léon Bottou, and Michael L. Littman (eds.), Proceedings of the 26th Annual International Conference on Machine Learning, ICML 2009, Montreal, Quebec, Canada, June 14-18, 2009, volume 382 of ACM International Conference Proceeding Series, pp. 689-696. ACM, 2009, doi: 10.11455/553374.15544.. URL https: 1553463.
//doi. wtl..oorg/...11e11 1ttee//1.1111115522
Stanislav Minsker. On some extensions of bernstein's 's inequality for self-adjoint operators. Statistics
& Probability Letters, 127:11 1-1199 2017.
Arkadi Nemirovski. Prox-method with rate of convergence O(L/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-coneave saddle point problems. SIAM Journal on Optimization, 15(1):229-255 2004.
Yurii Nesterov. method of solving a convex programming problem with convergence rate (11/k²). In Soviet Mathematics Doklady, volume 27, pp. 372-376, 1983.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning. and games with predictable sequences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013.
Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu. Hogwild: lock-free ap- proach to parallelizing stochastic gradient descent. In John Shawe-Taylor, Richard S. Zemel, Peter L. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger (eds.), Advances in Neu- ral Information Processing Systems 24: 25th Annual Conference Neural Information Pro- cessing Systems 2011. Proceedings of meeting held 12-14 December 2011, Granada, Spain, neurips. htcpppper/2011/aaeee Abstract html.
pp. 693-701, 2011. URL htwptttp://proceeeeeeeee 218a0aefdl di www.:eew6666ccccc. htt.eeaaaa..aaeeeeeeeeeeeeeeeeee
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint 17X14:1609.04447, 2016.
Shai Shalev-Shwarte Yoram Singer, and Nathan Srebro. Pegasos: Primal estimated sub aub-gradient solver for svm. In Proceedings of the 24th international conference on Machine learning, pp. 807-814, 2007.
12

---

Published as a conference paper at ICLR 2025
Ila Sutskever, James Martens, George Dahl, and Geoftrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning. pp. 1139-1147 PMLR. 2013.
Jun-Kun Wang, Jacob Abernethy, and Kfir Y Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. arXiv preprini arXiv:2111. 2021.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-I1), pp. 681-688. Citeseer, 2011.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine translation sys- tem: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609.08144, 2016.
Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11(Oct):2543 2596, 2010.
13

---

Published as a conference paper at ICLR 2025
A STABILITY W.R.T. CHOICE OF LEARNING RATE
Here we formally explain what we mean when we relate to the stability of algorithm A w.r.t. choice of the learning rate 7)-
Given SCO algorithm A. For a given choice of 0 S 17 S 9j. then the algorithm A ensures,
usually present its generalization bounds as follows:
Excess-Loss - (n)
where R: R_ + R4 is the convergence rate function of the learning rate v,. And this description applies to all the methods that we mention in our paper.
In this case define the optimal learning follows,
min Ra(1).
And we define the range of order optimal learning rates of A to be:
Range (n [0, (a) 2RA(1"))
In words, this set is comprised all learning rates that achieve the optimal convergence rate up to multiplicative factor of 2
Usually, the set Range A is line segment in R4,, and we can therefore write Range = mp y And further denote,
r = 17 max min
Thus, higher ratios imply improved stability of A w.r.t. choice of the learning rate 1). Next, we compare the stability for the methods that we mention our paper, for the SCO-EOS setting that we describe in Sec. 2. And substantiate the improved stability of p. SGD and of μ² Extra over standard SGD and accelcrated stochastic SGD.
1 it Stability of Standard SGD: For standard SGD it is well known that for the choice r E (0, 27. enjoys convergence rate of,
D
RSCD(1) n/ + 1j02
D Thus, in the typical case where o/T S 21 (i.e. when the noise is not negligible) we have 17" 2Do and (T") = /T" And it can therefore be validated that,
D
ovT
ratioScD S 15.
Conversely, (fi) in the typical case where ovT Z have 1/" validate again that,
1 In this case we can 22
ratioseD < 15.
This substantiates that for standard SGD we have stability ratio of ratiosGD 0(1).
Stability of Accelerated Stochastic SGD: There are several variants of accelerated stochastic SGD, For such algorithms, and for learning rate choice of E (0, 21 such methods enjoy convergence rate (See e.g. Theorem 2 in Lan (2012)),
D
RAred--SDD
2T
1/T2
Thus, similarly to our analysis of standard SGD, it can be validated that for such methods we have, ratio A SGD ~ O(1).
Thhe choice of is rather arbitrary, and we similarly choose any factor sufficiently greater than
14

---

Published as a conference paper at ICLR 2025
Stability of p²=SGD: As establish in Theorem 4.2 our 4² s²- approach ensures that for the choice of 77 E (0, | it enjoys a convergence rate of,
D 17T
4D vT
-
+ 2nj²²
Thus, in this case we have 11" /27T'
D and R,22- ())")
2v2Da 4D
And it can therefore
/T
be validated that in this case have n ~ 37
D
and 17m
ST7 and therefore,
ra SGD
VT
LD
Stability of n²² ExtraSGD: As we establish in Theorem 5.2 our nr² Ext raSGD approach ensures that for the choice 17 E (0, 2L. it enjoys convergence rate of.
D
ēD
R n2² ExDraSGD (1) = 1/2 +
VT
Thus, in this case we have '7*
27. and R - raSD (1)²)
2LD
72 + aD
And it can therefore
VT
be validated that in this case we have my = #T3/2 and max 2L. and therefore,
ā T3/2
ratio EXtroSGD
LD
B EXPLAINING THE BOUNDED SMOOTHNESS VARIANCE ASSUMPTION
Here we show that Eq. (3) implies that Eq. (4) holds for some of E [0, L...
Fixing x, y K., then Eq. (3) implies that for any = Support(D) (D) there exists Lu,,y [0, L. such that,
ff(;;;) Vf(n 1² L 2 || y11
Similarly there exists Le. E [0, L] such that,
ff(x) V+( 12 v1
And clearly in the deterministic case we have Liz = Li V= Support(D). Therefore,
(V((((((;)) Vf(()) - (Vf(y;z) 2 = E 2) Vf(;;; >)1 [V - ff()))l
E 2 12 || y/1 = (, || vl1
where we have used E [<Vf(x;;) v)(r=))) = (v)(x) - (v())) and we denote of (.. y) :=
E(L2.g= - y. This notation implies that oî {z, y} E [0, L"). and clearly of y) = 0 in the deterministic case for all x, y E IC. Thus, if we denote,
of
sup of (2, yeek
Then of [0, T.2] satisfies Eq. (4) and is equal to 0 in the deterministic (noiseless) case.
C PROOF OF THM. 4.1
Proof of 4.1. First note that the x; 's always belong to K,, since they are weighted averages of the {w) E KCy''s s. Next we bound the difference between consecutive queries. By definition,
012-1(2; - It-1) = ar(we 2z),
Implying.
||00 12- 2 (as/01:-1)) 11 22l12 & (16/P) (16/a²_))
(20)
15

---

Published as a conference paper at ICLR 2025
where have used or ++1 implying 01/01.0-1 S 4/t t for any 2 2, we also used ( wzll D which holds since We, 24, E K. finally we use a;-1 =
Notation: Prior to going with the proof we shall require faz)), and recall the following notation form Alg. 1: 9t := V Va 24) : = Vf(xt-1; 2t).
notation. We will denote
and we will also denote, Pt
(xx) and
C = de Jt.
Now, recalling Eq. (12),
a,dy 0.9. + (1 B.)an.(d.- It-1)
Combining the above with the definition of ez yields the following recursive relation,
Ox == ande 0gfi
cve(ge 9t) + (1 [c)ar(de-1 01-1)
Braxe (gtt - gr) + (1 (.)a((dr= - gt- + gt 9t)
Bga Ît) (1 31)a ( -1 + 9: 9t) + (1 B:)aa(dd- -
(s - 9r) + (1 3.)c((( - 9t) - (ūt-1 - gt- (n-1)) + (1 - Be) - 9t-
Ot a4 04-10-1
(g 9c) + (1 3,)a Ze + Be) a1-1
where we denoted Z, = (g: - T1) - (ğ.-1 1 - 1). Now, using = =t+1, and Br = =1((++1) then it can be shown that 0z29; = 1,and aj - B,) = a₁ 1 = 0--1- Moreover, (1 - --1) aa a-
Using these relations in the equation above gives,
Oxt 04-1 Ze + 16 (gt 9t) Mr 04-16t-1
(21)
where for any > we denote M; := at- Zr + (gt - 9t), as well as M1 91 -1- Unrolling the above equation yields explicit expression for any E [T].
M,
(22)
Now, notice that the sequence {M.) is is martingale difference sequence with respect to the natural filtration {Frh induced by the history of the samples up to time t. Indeed,
E[M E[(g: 9:) au- E[Z,|F,-1] El(g: 3t) at (1z = 0.
Thus, using Lemma C.1 below gives,
E|
Σ M
E 1 Σ E 110 12 (g: -2))l2
<
0 El |2/11 + Σ E Elgg: - 12
<
Σ
a Ell - gr) -
- 1112 +2 22 0²
T=1
=2 2
0 El (V] - -f{() - (V | 21
[((
2
Σ
ai 2 11 - -t 111 2102
Tm1
<32D of
+ 2t0²
1=1 (32D2o7, + +20
= 02.1.
(23)
16

---

Published as a conference paper at ICLR 2025
here the first inequality uses ||a + bl1 2||a||2 2 2| which holds for any a, b E IR the second inequality uses the bounded variance assumption; the third inequality uses Eq. (4), and the last inequality uses Eq. (20).
Dividing the above inequality by af = (t + 1)² the lemma follows,
E d2 Vf(x)]| = E| El / < (2)((11)+
+
Lemma C.1. Let {Me} martingale difference sequence with respect to a filtrationn {Fih,, then the following holds for any t,
E
M
Σ
E |M++1
r=1
C.I PROOF OF LEMMA C.I
Proof of Lemma C.I. We shall prove the lemma by induction over t. The base case where 1 clearly holds.
Now for induction step let assume that the equality holds for 2 and lets prove it holds for 1. Indeed,
2++
E
M,
=
E
M
+
M,
r=1
2
1
E
M,
E Mc+1 11 1 2E
Σ
My
Me+1
r=1
++1
E B|MM 2
+ 2E
Σ Mr
-M++ile Fe
E || + 2E
Σ Mr
E [M
E
||M +0
+0
E |M
where the third line follows from the induction hypothesis, as well as from the law of total expectations; the fourth lines follows since {M, 14 are measurable w.r. F, and the fifth line follows since Thus, we have established induction step and therefore the lemma holds. O
E E[M&+1|Je [F]]
D EXTENSIONS
Here provide several extensions and additions to Theorem 4.1.
In Sec. D.I provide high-probability bounds for ||c]||2.
In Sec. D.2 we show how obtain E||c.|2 < O(1/T) at the price of additional Olog T) factor in the total sample complexity (i.e. we show that this requires a total of O(T log T) samples rather than OTT) samples).
Our extension to more standard variant of SGD, which employs uniform weights and learning rate of n) log T appears in Sec. G
17

---

Published as a conference paper at ICLR 2025
D.1 HIGH PROBABILITY BOUNDS
To obtain high probability bounds we shall require another assumption, that the stochastic gradients in K are bounded, i.e. that the exist G 0 such [
=) G, Vo E K, Support(D), We
are now ready to show that w.p. 2 1 - then for all I E [T] we have,
U
||e||1 s
log( (T/6) +
max
log(T/6)
12
where we denote Umax 8LD 22.
Recall that in the proof of Theorem 4.1 we show the following in Eq. (22),
ag Σ M, == M1 T=1
(24)
104-9:0 9t). as well as M1 91 I1, where we denoted Ze := (g: gt (gt-1 1t- Thus M, is martingale difference sequence w.r.t. the natural filtration induced by the upcoming samples. And M, also bounded w.p. since,
where M, == 0t Zz (ge-
|| = || 21 (gt 9:)l
< 1 + [1( g:)ll
< | (gt 9(-1) || + ( 9c-1))l + l1( 9:)l
Lag-1 1| 1 + Lau-1 100 x2-1/l 10-1l++2 +
S -La -4D/ 1 + 2G
SLD + 2G
U Umax
where we have used the smoothness of the v)(;,) as well as Eq. (20). We also denote Umax = 8LD + 2G.
Finally, similarly to the proof Theorem 1 we can show that,
E M. 2= =
where E denotes conditional expectation conditioned over history of the samples (randomizations) up until and including round
Now, since the {Mr J+ is martingale sequence w.r.t. the natural filtration induced by optimization process, and since it bounded, with bounded conditional second moments, then we can use Cor. 4.1 in Minsker (2017) to show that w.p. 2 1 - 5 the for all E [T] we have,
| < 0 (ō²t 1og(( + U2 U log(T/6))
where the T inside the logarithm comes from using the union bound.
Thus, based on the above and on Eq. (24), we immediately conclude that, w.p. 2 1 - then for all t [T] we have,
1 Mreel s
82 (
U2 max log(TT/)) log(T/0)
de ||
at
where we used ag f. This concludes the proof.
D.2 UNIFORMLY SMALL ERROR BOUNDS
Here we show that upon increasing the sample complexity by a factor of log T, enables to obtain a uniformly small bound of E|| d² /T, Vt [T].
To do do, we will employ a batch-size size b, = [T/t] at round
Actaully Cor 4.1 in Minsker (2017) is a Corollary of Thm. 3.1 therein, which applies to sum of independent matrices. Nevertheless, Minsker (2017) which applies to this martingale difference case.
obtain corollary for the Martingale difference case for vectors from Thm. 3.2 in
18

---

Published as a conference paper at ICLR 2025
Total # Samples. The total number of samples that along all rounds is therefore E (T To. Thus the sample complexity only increases by log T factor.
Error Analysis. Upon using batch-size by the variance of our estimator in round decreases by factor of by. Thus, along the exact same lines as in Eq. (23) we can show the following.
0²
t
E El ?
T
Recalling 04 and dividing by of yields,
Ø²
E elll 2
T
which establishes the uniformly small error.
E PROOF OF THM. 4.2
Proof of Thm. 4.2. The proof is a direct combination of Thm. 4. together with the standard regret bound of OGD (Online Gradient Descent), which in turn enables to utilize the Anytime guarantees of Thm. 3.1.
Part 1: Regret Bound. Standard regret analysis of the update rule in Eq. (9) implies the following for any / (see e.g. (Hazan et al., 2016), as well as Theorem 15.1 in (Cutkosky, 2022b)).
D
a,d, (w--wi w²)
"
a 1d111
(25)
2n
Part 2: Anytime Guarantees. Since the ae 's are weighted averages of the w, 's we may invoke Thm. 3.1, which ensures for any E [T].
a1
- f(w")) S Σ ar Vs(x)) (w, w²),
where we denote A, = fxx) f(w").
Part Combining Guarantees. Combining the above Anytime guarantees together with the bound
in Eq. (25) yields,
a1 A S Σ at Vs(()) (w, - -w")
T=1
d (w, w²) + Σ ar (f((() dz) (w, w*)
D
"
+
0,67 (w, - w²)
2n
2
D2
+
"
a
V
(x+
+ + + Σ
||a,c||| -1/u, w'll
2n
2
r=1
D2
+
V
( || + Σ
| 2 D
|+tr||
2n
D2
+ 2
Σ
a
2 A, + Σ
| + D
||,,
2n
7=1
T=1
T=1
D
+ 4nL
a1.r A, + 1
af 12 ||| 1 + D
|a,c|l1
(26)
2n
1=1
19

---

Published as a conference paper at ICLR 2025
where the first incquality follows from Sauchy-Schwarttz the second inequality holds since 1 w"'l S D, as well as from using ||a + b1]2 I a| + 2||b]] which holds for any a, E R", the third inequality follows by the self bounding property for smooth functions (see Lemma E.1 below) f(w") = 2,,,; and the fourth inequality follows due to of 2011 which holds since a, -
implying that VIV II( < (f((((+))
Lemma E.1. (See e.g. (Levy et al., 2018; Cutkosky, 2019)) Let F Rd + R be an L-smooth funccitoonniion with global minimum x², then for any x Rd have,
[V) < 2L(((x) -FF()))F(u")),
Next, we will take expectation over Eq. (26), yielding.
D2
4
01. EA, + Σ 0 B|||eT1 2++1 Σ Blaa,e711
21
1>2
+ 1
01 EA, +1 11 Σ 0 E|c/c] + DDD
E
21
D2
T
Σ
01 OI.TA EA, + Σ
0 0 11 +
V
/2 62 /2/
2n
T=1
T=1
1=1
D2
4
Σ
01 EA, + no²
Σ
a, + Dō
Va
2n
T=1
T=1
T=1
D2
T Σ
T
T
4nL
01 EA, + 110
+ Dō
Va,
29
1=1
r=1
D2
4mL
Σ
a1.T + 01 EA, + +noaar
+2D7T8/2
21
D2
1
a1 EA, + no 2D713/2
(27)
27
2T
where the second lines is due to Jensen's 's inequality implying that EX S VEX for any random
variable X: the third line follows from E|| S 5² /av, which holds by Thm. 4.1; the fifth line holds
since < T'; the sixth line follows since Di= Voz S 2/3/2 and the last line follows since we pick 1 S 1/8LT'
To obtain the final bound we will apply the lemma below to Eq. (27),
Lemma F.2. Let {Ae)ErT be sequence of non-negative elements and B R, and assume that for any 1 T,
T
A S
B
A
2T
t=1
Then the following bound holds,
AT < 2B
Taking A₁ t EI:EA, and B + D2
a1 + 3/2 provides the following explicit bound, 2n + n
D2 + 2 air + 3/2
EAT <
Dividing by our and recalling 01.77 = (T22 gives,
D
4D
- (((TT)
EdT 5
+ 2no² +
1/T"2
VT
which concludes the proof.
20

---

Published as a conference paper at ICLR 2025
E.1 PROOF OF LEMMA E.2
Proof of Lemma E.2. Summing the inequality At < + 2T Ei A, over gives,
1
Aur STB+T
ALT = TB + AIT 27
Re-ordering we obtain,
ALT 2TB. Plugging this back to the original inequality and taking t = T gives,
AT $ B
AITr S 2B.
2T
which concludes the proof.
F PROOF OF THM. 5.2
Proof of Thmm. 5.2. The proof decomposes according the techniques that n²² Ext raSDD ploys.
Part I: Anytime Guarantees. Since the 's are far)e weighted averages of the (w;)z 's
invoke Thm. 3.1 which implies,
T
I and (wi - -w") - Σ
T
(1r((((F)) - f(w")) < vf(z)) (wi w²)
Σ
ase (wr w²)
1=1
1=1
(28)
where we have denote 6. == de fz())
Part II: Optimistic OGD Guarantees. Since the update rule for {we, Mr satisfies the Optimistic- OGD template w.r.t the sequences of loss and hint vectors {dl, de we can apply Lemma 5.1 to bound the weighted regret in Eq. (28) as follows,
()T(( - ((ww))
40
1
T
T
+
a ld, - del12
|wm
11-1
ar4 (w, w*)
"
2
27
t=1
t=1
4D
af 11g
-cell
Σ
||w 1111
||00 |aaccll|
w'll
"
2n
t=1
4D
"
0
[
( =1]11
We
Vt 1| + D
oosel
2n
4D2
L
T Σ
1 T
T ||we Dイ- 1| + D Σ
2 1r - +e 2
Σ
|| ansell
2
2nj
1=1
tml
402
2
T
at
||1,
V/. 1/-111"
11
T || -1-11l1 + Σ 2n t=1
1
aacell
11
2
01:t
1=1
t=1
4D
1,1
|wa
11-1
|w 1t-
2 +
D
|lacell
11
2
2n
4D
+
||aeell
(29)
where the first line uses Eq. (28) together with Thm. 5.1; the second line uses de d 9: g. which follows by Eq. (19); and the third line follows by the definitions of gr, Ôt. as well as from l|w, w²1 < D, which holds since W., w E K; the fourth line follows by assumption in Eq. (3);
21

---

Published as a conference paper at ICLR 2025
the fifth line holds since 2t- 2, (au/a14)(m) ye-1) which holds due to Eq. (17); the sixth line holds since aj (a1:)) < 4, vt 2 1; and the last line follows since 2T,L² 1/(2n) S which holds since assume Part III: n² Guarantees. Notice that our definitions for wi, Tt, og, 3, and de satisfy the exact same conditions of Thm. 4.1, This immediately implies that Elfe, 11? I 8² /t, vt. Using this, and taking the expectation of Eq. (29) yields,
1/2L.
4D
T
4D² S
T
B(T())) - f(w"))
+
D
E
arall
D
E a
1
"
t=1
t=1
4D2
4D²
Dō
a a S
2T Dē
(30)
1
where the second inequality uses Jensen's Inequality: EX I EXX which holds for any random
variable X; the last inequality follows from a < 2t, implying that Σ v /a//t s 2T3/2
Dividing the above equation by 01:r and recalling that 01.7 ( concludes the proof.
G EXTENSION OF SSGD TO UNIFORM WEIGHTS AND 7, x log
Here we show that we can obtain the same guarantees as in Thm. 4.2, when using the following more standard choices of ag = 1, and 7) x 1/Llog T inside Alg. I; albeit suffering log T factors in the convergence rate.
The next theorem, which is variant of Thm. 4.1, shows that even upon choosing uniform weights we get E/|ez|1 < <0
Theorem G.1. Let f I. + R, and assume that is convex with diameter D, and that the assumption in Equations (2), hold. Then invoking Alg. I with {ar = 1}e and {.e 1/1}, ensures,
E|e, 12 == Elid, f(2)))1 < 80 where G == de (xxz), and 82 32D 20..
Next we provide proof sketch. The exact proof follows same lines as the proof of Thm. 4.1.
Proof Sketch of Thmm. G.I. First note that the x, 's always belong to K, since they are weighted averages of (w,, E K)''s. Our first step is to bound the difference between consecutive queries. The definition of 2, implies,
012-1(0; IT-1) ar(we xz),
yielding,
1 D2
1x 112 (01//0a-) 1)² lwue 1x.1? < (1 1)2
(31)
where we have used a; 1 and 01:111 t 1; we also used ||w xzll < D which holds since
We, 2t E K.
Notation: Prior going with the proof we shall require some notation. We will denote V (xzz), and recall the following notation from Alg. 1: = V ff 2x) : == (f)
We will also denote, Ez de g.
Now, recalling Eq. (12), using a, = 1, and combining it with the above definition of e, enables to derive the following recursive relation.
et Be(g: g.) (1 -3.42 + (1 (1-Bi)et--) Bc)e
1
t t-1
t 1-1
= (g: 3i) + 2,
Et-1,
t
t
where we denote Z; (gi equation by / gives,
d1) (ğ) 1 91-1), and used Br 1/t. Now, multiplying the above
te = (g: - g.) + (t - 1)2, + (t 1)4-1
Mi + (t 1)4-11
22

---

Published as a conference paper at ICLR 2025
where for any t denote M, 1) + (ge 9t), well M1 91 91. Unrolling the above equation yields an explicit expression for any E [T]:
te
M, == M
Noticing that the sequence (M, J is is martingale difference sequence with respect to the natural filtration {Fi) induced by the history of the samples up to time t; enables to bound as follows,
te
1|
Σ
Mr
E M 11
Bll 1)2, + (g) - g:))
r=1
T=1
2 2 Σ
- 1) 11 + 2
Eligr - 9ell2
r=1
==1
$ 2 Σ (t - B)) g:) (őt 91-1)11 +2 >>> o².
(32)
r=1
7=1
Now, using Eq. (4) together with Eq. (31) allows to bound,
Bli gc) (ύ--1 1t - o 21-1 of 1)2.
Plugging the above back into Eq. (32) and summing establishes the theorem.
SSGD with y log Based on the above theorem we are now ready to state the guarantees version of yu -SGD that employs standard choices of a₁ = and v x 1/L.
Theorem G.2 (u²-SGD Guarantees). Let f Rd + R be convex function, and assume that "" E arg min (w) is also its global minimum in TR... Also, let us make the same assumptions as Thm. 4.1. Then invoking Alg. with {a, = }}; and {3, = 1/t),. t. and using the SGD-type update
rule (9) with a learning rate 7) S [6L(1+logT] inside Eq. (10) of Alg. I guarantees,
D2
62
4D7
B(((ET) - f(ww)(( EAT < 5
27
1/T
VT
where A, = f(x) - [(w",, and 0² = 32D2 + 20
And note that this demonstrates the same stability this 2²DSGD variant, similarly to the stability of the variant that we discuss in the main text and in Thm. 4.2.
Next we provide a proof.
Proof of Thm. G.2. The proof is a direct combination of Thm. G.1 together with the standard regret bound OGD (Online Gradient Descent), which in enables utilize the Anytime guarantees of Thm. 3.1.
Part 1: Regret Bound. Standard regret analysis of the update rule in Eq. (9) implies the following for any / (Hazan et al., 2016),
D
Σ o,d+ (w, w²) w") 2n
(33)
Part 2: Anytime Guarantees. Since the I ry's are weighted averages of the wy's may invoke
Thm. 3.1, which ensures for any E (T].
= (f) f(w))) < Σ a, =
vf(x,) ( (w, - -w").
T=1
where we denote A, == f(xx) f(w²).
23

---

Published as a conference paper at ICLR 2025
Part 3: Combining Guarantees. Combining the above Anytime guarantees together with the bound in Eq. (33) yields,
A S
Σ at Vf((+) (w, w²)
arl7
(wT w²) + Σ
ar(VS(()) dr) -ww+ w*)
T=1
7=1
D
+
1
a 1/122111
a,c, (w, - w*)
27
2 ==1
1=1
D²
+ "
a
V f (I+) + c+? + Σ
||,G|l| 1|0, - w'll
27
2
r=1
D2
+
a
| (I+))) || + Σ
a || 112 + +D Σ
a,erll
2n
1=1
7=1
==1
D2
+ 2mL
az + Σ
|+1 + +DY
|a,c=ll
2n
==1
T=1
D2
+
I.
Σ T=1
A + Σ | + D Σ ||l||.
(34)
2m
T=1
where the first inequality follows from Cauchy-Schwartz: the second inequality holds since || wI || S. D. as well as from using ||a + b11² - 2||a||2 + 2/|6 which holds for any a, b Rd the third inequality follows by the self bounding property for smooth functions (see Lemma E, implying that [++](=))|?? < (x())= f(w")) == 2LA,; and the fourth inequality follows due to a,- 1.
Next, we will take expectation over Eq. (34), yielding,
D2
EE = 01:
+ 4nI.
EA, +1
Σ
E||cT|| 112 +
D
>
E||cT|
2n
1=1
D2
+
4nL
Σ
EA, +1) Σ Elle,11 +
v /|
2n
7=1
T=1
T=1
D2
+
4
EA, +1| Σ / D
102/T
2n
1=1
T=1
1=1
D2
+
4nT. Σ
EA, + +n0²
1/T + Dā Σ 11/T Σ
27
7=1
7=1
T=1
D2
+ 4nL
EA, + +ooo + logtt) + +2DVEE
2n
7=1
<
D²
+
1
ΣEA, + no log 1) + +Dävt, (35)
2n
4(1 + log T)
1=1
where the second lines is due to Jensen's 's inequality implying that EX S VEX for any random variable X: the third line follows from E| < g2/l which holds by Thm. G.I. We also used Σ 1/VF < 2/t as well as Σ 1/T < log t. Lastly, we use our choice for n,
To obtain the final bound we will apply Lemma G.3 below to Eq. (35).
Lemma G.3. Let > and (Atheer be sequence of non-negative elements and {B, Rher a monotonically increasing sequence of non non-negative elements, and assume that for any t < T,
T
LA < B, +
1
Σ t=1
A
4(1 + log T)
24

---

Published as a conference paper at ICLR 2025
Then the following bound holds Vt [T].
A 5 2B./t.
Taking A, f- EA,, and B,
D³a + nz² (1 + logt) -Dā / provides the following explicit bound,
2nj
B(f(xr)- f(w")) EAr 00 (
D2
4Dō
2m
n/
T
VT
which concludes the proof.
G.1 PROOF LEMMA G.3
Proof. We shall prove the lemma by induction. For the base case we have,
A1 S B1 4(1 + log T) A1 - B1 4 A1
This directly implies that A < /B1/3 & 2B,, which establishes the base case.
For the induction step, lets assume that the lemma holds for for any т S t, and show that it also holds for + 1. Indeed, using the induction assumption we obtain,
(t + 11+41 S Bit1 +
A4t1+
17
4(1 + log
1
2B,
Bi+1 + A4+1 +
4(1 + +lg 7)
==1
2Be+1
$ BB4t + A4+1+ +
4(1 + log T*
==1
2B
< Bit1 + - Act1 + 4(1 + log T
==1
S + A4t1 Bi+1
where we have used the monotonicity of the B, sequence, well the fact that for any have Σt= + Since / then / 1 2 3 + 1). Using this together with the non-negativity of A directly implies that,
+ logt < 1+ log T. Re-ordering the above implies 1-- 1) S Be+1-
3B 3B++1/2 2B
A41 S
1+1-1 S 3
which establishes the induction step; and in turn the induction proof.
25

---

Published as a conference paper at ICLR 2025
H EXPERIMENTS
H.1 TECHNICAL DETAILS
We compared the following optimization algorithms range of fixed learning rates*:
-SGD.
Momentum-baste based SGD with μ 0.9 and 0.9 (see PyTorch docs. 9).
Standard SGD,
STORM.
Anytime-SGD.
We evaluated our approach the following datasets:
CIFAR-10 Dataset. The CIFAR-IO dataset (Krizhevsky et al., 2014) consists of 60,000 color images across ten classes with resolution of 32x32 pixels.
MNIST-10 Dataset. The MNIST dataset (LeCun et al., 2010) comprises 70,000 grayscale images of handwritten digits (0-9) with resolution of 28x28 pixels.
H.2 CONVEX SETTING
In this experiment, address logistic regression problem the MNIST dataset. Both the training and testing phases employed mini-batches of size 64, with one full pass (epoch) over the dataset.
Also, the model weights constrained within unit ball, limiting the solution space compact convex set:
KC = {w E Id |0l S 1}.
where I denotes the model weights.
At each iteration, the weights are projected back into the unit ball using the projection function (w)) ensuring that the norm of w remains bounded.
The following algorithms were evaluated with their respective parameter settings: SSG with at and B, 1/t, STORM with 3r = 1/1, and Anytime-SGD with az = I.
H.2.1
TEST ACCURACY ACROSS LEARNING RATES
Accuracy
m2/2ag
arryiine, syd
Test Accumicy
0.5
mymy My
Text Accunsty
Test Accurasy
Taxk Actmney
Taxi Assumiy
0.5
Ma1
Beraaion Number
Number
Heration Number
Number
Number
Figure 3: Test Accuracy at Learning Rate = 10 (f is better).
*Note that comparing fixed learning rates across different optimizers is consistent with our theoretical findings, which demonstrate optimal convergence for asp) = O(t/7) = ((1).
26

---

Published as a conference paper at ICLR 2025
Accuracy
mag2
momeer
viorm
aryyline agd
Teet Acarrny
Test Accunsty
Test Accursty
Toxl Ausuraty
Teat Ansunicy
0.4
Text
0.2
Puagae
Figure 4: Test Accuracy at Learning Rate = (f is better).
Test Accuraty
mmg2
alorm
aryyiite
Tesl Accumioy
0.8
Test Actunsoy
Test Accurscy
Text Azunnry
TAe Assumeyy
0.4
al
40
20
20
40
20
20
40
40
Beration
Iteration Number
Iteradion Number
Bleration Number
Henation Number
Deeatt Number
Figure 5: Test Accuracy at Learning Rate = 0.1 (1 is better).
Test Accuracy
mu2zgd
momantum
5gd
storm
anytmme sgd
Test Actumety
0..00
Text Apdcurni
Tonal Acsuiratyy
Text Acturncy
lst Aocurasy
Tos Accurast
0.50
0.75
20
20
40
40
Bot Blom
lluralion Number
Nltratio Number
Detution Number
Uenulion Numbon
Hlsrulion Number
Figure 6: Test Accuracy at Learning Rate 0.01 (1 is better).
Tast Accuracy
mu2sgd
Test Accuminz
0.8
Text Accunsoy
Test Accurasy
Teal Accunnty
Text Acsumny
0.4
0.2
40
20
40
40
Batalion
Neet eliin Num but
Berraiio Number
Barrllian Numbor
lanalion Narbow
Dataloo Number
Figure Test Accuracy at Learning Rate = 0.001 (f better).
Test Accuracy
mu2sgd
momenbum
5gd
storm
anytime, 5gd
Teet Accurayy
0.5
Toot Accuuraryy
Test Accurasy
Accurnty
Armunny
40
20
20
40
20
40
beration
Iteration Number
lteration Number
Iteration Number
Heration Number
Ioorat on Number
Figure 8: Test Accuracy Learning Rate 0.0001 (t is better).
27

---

Published as a conference paper at ICLR 2025
H.2.2 TEST Loss ACROSS LEARNING RATES
Teet Loss
mu22gg
momentum
anylime_app
M M
Teat Losa
lest Loss
Test Loos
Teal Loos
Test
Test
40
20
40
43
20
40
40
20
Ileration
Iooraii Numbar
Beration Number
Ilratiin Number
Iteaatoon Number
Beeation Number
Figure 9: Test Loss at Learning Rate 10 (1 better).
Teat Loss
m222sgd
momentum
sgd
storm
anytime_apt
Teat Losa
Loss
Test Loss
Teat Loos
20 Number
40
20
20
Boration Number
Number
Iteration Number
Neration Number
Figure 10: Test Loss at Learning Rate 1 (1 is better).
muZ2gg
momentum
agd
anytimo sgd
Teot Losa
Tod Loss
Ted Leos
940ggg
Mate
20
20
Iteration
Beraton Number
Beratio Number
Iteration Number
Ileraton Number
Nerrtion Number
Figure 11: Test Loss at Learning Rate 0.1 (4 is better).
muZagd
anylime
1.4
1.2
Tex LOoo
Toot Lova
Teol Loos
20
20
40
20
40
40
20
20
40
Iteratio
heration Number
heration Number
Iteratin Number
heration Number
Iteration Number
Figure 12: Test Loss at Learning Rate 0.01 (4 better).
Tost Loss
muZagd
momanium
atorm
anytime agd
2.0
Texl Lones
Teot Loos
Teol Loos
1.5
Tesd
20
20
40
40
20
20
Iteration
Ieration Number
Peration Number
Iterotio Number
Ieration Number
Iteration Numbor
Figure 13: Test Loss at Learning Rate 0.001 (4 is better).
28

---

Published as a conference paper at ICLR 2025
2.4
ruu2agd
momer
agd
anyline agd
Tael Look
Toal Loca
Teal LooD
2.0
1.8
Ileration
Ierrtion Number
Number
Itoration Number
Icration Number
Iteration Number
Figure 14: Test Loss at Learning Rate = 0.0001 (4 is better).
H.3 NON-CONVEX SETTING
C-FAR-10 Experiment. We trained ResNet-18 for 25 epochs using mini-batches of size 32. Training included RandomCrop (32x32, padding=2, p=0.5) and RandomHorizomallFii (p=0.5) for data augmentation.
MNIST-10 Experiment. We trained a two-layer CNN with ReI.U activations, max pooling, and two fully connected layers. Batch normalization was applied to the first fully connected layer. The model was trained using mini-batcher size 64 single pass over the dataset.
The following algorithms were evaluated with their respective fixed parameter settings: 5DGD with "/ = 0.1 and B. 0.9, STORM with 3, = 0.9, and Anytime-SGD with 7t. 0.1. These fixed parameter choices help mitigate the sensitivity of small momentum parameters in non-convex deep learning models, which arises from two key factors:
Relevance of Historical Weights: non-convex optimization, heavily relying on past weights (e.g., " 1/t) can hinder progress, as old weights may lose relevance or misguide optimization through saddle points and local minima.
Numerical Stability: In high- -egaparaeeter models or large datasets (where t grows large), very small momentum parameters can introduce numerical instability, compromising optimization effectiveness and reliability.
lest Accuracy
mu/2gd
momenttum
<plimiee
momoruum
Teat Actirsiy
dlom
Toat Accunacy
Text Accunnry
wallmm rgr
Number
5gd
stom
anytime_cog sgd
Teet Actisty
Toal Actomnay
Test Accunry
0.4
10
20
15
Epech
Epoch
Epoch Mumber
Figure 15: CIFAR-10: Test Accuracy Over Epochs at Learning Rate 10 (1 better).
29

---

Published as a conference paper at ICLR 2025
lest Accuracy
mu2egd
momeent.m
Teet Teet
op0 mizer muZegi
Tool Acturney
Test Acnunay
0.8
spd
anylimeespp gg0
Beration Number
Benation Number
arytme_rgg agd
Test Nctueery
Toal Actunaty
Teat Acnunnry
0.0
Iteration
Iinnation Number
Benation Number
Figure 16: MNIST: Test Accuracy Over Iterations at Learning Rate=10 (f is better).
1.0
0.8
0.6
0.4
momennum
0.2
storm
anytime._sg _sdd
mu2agd
10
10
10'
Figure 17: MNIST: Test Accuracy LRs from 0.0001 to 10 (1 is better).
30

---

Published as a conference paper at ICLR 2025
H.3.1 CIFAR-10: 10: TEST ACCURACY ACROSS LEARNING RATES
Test Acouracy
mu22spd
momentuum
anylime_sp2
0.6
Tost Auconacy
Test Acsuracy
Teat Auturacy
0.0
0.4
0.0
20
10
20
10
20
92
20
20
10
20
Epoch
Epach Number
Epach Number
Epoch Number
Epoch Number
Epoch Number
Figure 18: Test Accuracy at Learning Rate 10 (f is better).
Test Acturaay
mu2sgd
momentum
sgd
storm
anylime_agf
Accurscy
Accuresy
Trel Aucomaryy
Toot Accuur Accuracy
Teal Aucunacc
69.55
0.4
10
20
Epoch
Epoch
Epoch Number
Epoch Number
Epoch Number
Epoch Number
Figure 19: Test Accuracy at Learning Rate (f is better).
Tast Acouracy
muZagg
momenium
spd
anylime agd
0.8
Pocuracy
Twol Aacuraayy
Text Accuraty
Texl Acourayy
20
Number
Eposh Number
Epoch Number
Epoch Number
Number
Figure 20: Test Accuracy at Learning Rate = 0.1 (1 is better).
Tast
muZagd
anylime
0.8
Twxi Accuraty
Tedi Accuraty
Tool Accunity
0.7
0.8
10
20
10
20
10
20
20
Epoch
Epoch Number
Epoch Number
Epoch Number
Epoch Number
Epoch Number
Figure 21: Test Accuracy at Learning Rate 0.01 (f better).
Tast Acouracy
muZagd
momanium
atomm
anytime. agd
0.8
Accuracy
Texl Acsuracy
Test Acouraay
Accuraty
0.7
0.6
0.5
20
10
20
Epoch
Spoch Number
Epoch Number
Epoch Number
Epoch Number
Epoch Number
Figure 22: Test Accuracy at Learning Rate 0.001 (t is better).
31

---

Published as a conference paper at ICLR 2025
Moy
muu2agd
moneer Bum
agd
enylime age
Test Teet/ccuurryy
Text Accuraoy
Text Auco RwOy
Test Accu Accuraayy
69.5
Test Accu
0.4
0.3
Number
Number
Number
Epoch Number
Numbor
Figure 23: Test Accuracy at Learning Rate = 0.0001 ( is better).
H.3.2
CIFAR-10 10: TEST LOSS ACROSS LEARNING RATES
Loss
mu2agd
mome
sgd
anyline agd
15
Teot Lose
Ted Lass
Tool Loss
Test
ecDagg
10 Epoch
Epoch Number
Number
Number
Epoch Number
Number
Figure 24: Test Loss at Learning Rate 10 (L. is better) 6
Test Loss
mu2spd
momentum
spd
storm
anylime 5gd
1.5
Tenl Lows
Test LoGR
1.0
Tood
Epoch
Epoch
Epoch Number
Epoch
Figure 25: Test Loss at Learning Rate () is better).
muZagd
momentur
spd
anyline sgd
1.5
Teel Looo
Teot Loca
1.0
Teol
0.5
.uchpp
oeder
20
Number
Eppcc Number
Number
Epoch Number
Number
Figure 26: Test Loss at Learning Rate = 0.1 (L is better).
"I Loss values clipped at maximum of 20 for better visualization.
32

---

Published as a conference paper at ICLR 2025
Loss
mu2sgd
mommeniam
egd
wrylime agd
1.20
Teed Loos
ledt Lass
Toot Loss
Teet
0.90
Epoch Number
Number
Number
Number
Figure 27: Test Loss at Learning Rate 0.01 (4 is better).
1.90
muu2add
monee
spd
anyline agd
Tael Look
Tool Losa
Tool
0.75
0.50
Number
Number
Number
Epoch Number
Numbar
Figure 28: Test Loss at Learning Rate = 0.001 (L is better).
Loos
mu2sgd
momentum
spd
storm
anytime _gd
Twell Loos
Teai Losa
Tool Lowe
1.50
1.25
Pi
oepore
Epoch
Epuch Number
Epuch Number
Epoch Number
Figure 29: Test Loss at Learning Rate = 0.0001 (1 is better).
H.3.3 MNIST: TEST ACCURACY ACROSS LEARNING RATES
Test Acouracy
mu2sgd
momentum
ssdd
storm
anylime _sd
Text fecurascy
Accurseyy
Texl Aucunary
Text Ascursey
Teal Ancumary
20
20
20
40
40
20
20
llrration
Ver Veralion Numben
Derafion Number
leeralion Number
Deraion Number
Beration Number
Figure 30: Test Accuracy at Learning Rate 10 (f is better).
Tast Acouracy
muZagg
momanium
storm
anytime agd
1.0
Aocuracy
Texi Acsuracy
Test Accuraay
Text Accuraty
0.0
0.6
20
20
40
20
20
Iteration
Neration Number
Peration Number
Itorotin Number
beration Number
Iteration Numbor
Figure 31: Test Accuracy at Learning Rate (1 is better).
33

---

Published as a conference paper at ICLR 2025
Text Accuraty
muZagd
momeentam
egd
storm
anyliime agd
1.0
Tee Acco (aaa
Toct ACC.CCC-PRO oro
Toxt Accu aaaayaaay
0.0
Test Acc.cccusn
0.0
10:
tal
20
Iteration Number
Boration Number
Iteration Number
Itoration Number
Number
Figure 32: Test Accuracy at Learning Rate = 0.1 (f is better).
Test Accuuracy
muu2agd
moneettum
agd
storm
anyline agd
1.0
Text Accurary
Texl Auc ewOy
Test Accu Bacyurayy
Texl Accu eaty
0.8
09.55
0.4
20
Iooation Number
Ieration Number
Itoratio Number
beration Number
Iteration Number
Figure 33: Test Accuracy at Learning Rate = 0.01 (f is better).
Test Acouracy
mu22gd
momentum
sgd
storm
anylime sggd
0.8
Teet Accuraor
Tool Ascannery
Toat Accunscy
Teal Aucuresc
0.8
0.2
20
Number
leeraiion Number
Number
Number
Figure 34: Test Accuracy at Learning Rate = 0.001 (f is better).
Tast Acouracy
mu2zad
momenbum
spd
stom
anylimee sgd
0.8
Tex: Focuracy
Tool Auctnay
Texl Accuracy
Toxl Accurity
0.4
Iteration
Number
Number
Ierootnn Number
Number
Number
Figure 35: Test Accuracy at Learning Rate 0.0001 ( is better).
H.3.4 MNIST: TEST LOSS ACROSS LEARNING RATES
Test Logs
mu2agd
momentum
sgd
storm
anylime agd
30
Test Loss
Text Loce
Tasd Lovss
Test Loos
Tood LOSS
20
40
20
20
20
40
20
Boration
Iterabon Number
Iteration Number
Herrtion Number
Mlrrtion Number
Iteration Number
Figure 36: Test Loss at Learning Rate 10 (4 is better).
34

---

Published as a conference paper at ICLR 2025
muu2gdd
momerila Bum
agd
enyline agd
2.0
1.5
Tael Looo
Tool Loca
LooD
1.0
0.0
20
Number
Ieration Number
Itoration Number
Ioration Number
Iteration Number
Figure 37: Test Loss at Learning Rate = () is better).
momantum
Teol Lobe
root LOGS
Toot LoGS
0.6
0.0
20
40
20
40
20 Iteratio Number
20
20 Iteration Number
20
40
tereton
Iteration Number
Iteration Number
Ieeraiin Number
Figure 38: Test Loss Learning Rate 0.1 (4 better).
Test Loss
mu2sgd
momentum
ssdd
storm
anylime__s2
2.0
Text Loon
Test LooR
Text
Text
20
20
20
40
40
20
20
lleratton
Veraation Number
Derafion Number
lleration Number
leration Number
Deration Number
Figure 39; Test Loss at Learning Rate 0.01 (J is better).
Losg
mu22gd
momentum
agd
storm
anylime agd
2.0
Twel Looa
Toal Loca
1.5
Text
Tool
1.0
Neration Number
Eoration Number
Iteration Number
boration Numbar
Itaration Number
Figure 40: Test Loss at Learning Rate = 0.001 (1 is better).
muZagd
anyline agd
Teal LOOK
Tool Losa
Teel Loos
Toot
1D Aec
21
20
40
20
40
20
40
40
20
20
Iteration
heration Number
Ioration Number
Itcrotio Number
boration Number
Itcoation Number
Figure 41: Test Loss at Learning Rate 0.0001 (4 is better).
35


Reviews:
[{"review_id": "F8xSzU98OU", "reviewer": "Reviewer_8uRS", "summary": "This paper presents two methods for stochastic optimization that achieve similar guarantees as standard gradient descent and accelerated gradient descent while being robust to the choice of learning rate involved.", "questions": "1. Have the authors tested out the proposed algorithms (or their adaptive gradient variants) on problems that appropriately reflect problems/setups that are of realistic practical interest? For instance, training transformer based architectures on standard pre-training tasks?\n2. Can the authors clarify how this algorithm's guarantees look like with (a) strong convexity, (b) non-convex but say with a PL style condition?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a well written paper that presents two interesting algorithms with strong theoretical guarantees. The algorithms definitely appear novel to my knowledge but I do not know of the latest developments in this area.", "weaknesses": "The empirical section seems to be fairly underbaked in my opinion.", "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": "bUL4eyVt8K", "reviewer": "Reviewer_p8j2", "summary": "The paper introduces the $\\mu^2$ (Momentum$^2$) gradient estimator, designed to manage gradient noise in stochastic optimization, particularly in convex and smooth loss scenarios using single-sample batch sizes. This estimator integrates two momentum techniques:\n\n1. **Anytime Averaging**, which averages the query points for the gradient oracle.\n2. **STORM**, a corrected momentum method that averages gradient estimates with bias correction.\n\nBy combining these techniques, $\\mu^2$ achieves a progressively shrinking square error of the gradient estimates ($\\|\\epsilon_t\\|^2 \\propto 1/t$), contrasting with the fixed gradient error in standard stochastic optimization ($\\|\\epsilon_t\\|^2 = O(1)$). This property enables the use of a fixed step-size for convergence, removing the necessity of step-size decay in stochastic settings. Additionally, $\\mu^2$ allows the norm of the gradient estimate to serve as a stopping criterion.\n\nThe paper implements $\\mu^2$ in two algorithms:\n\n1. **$\\mu^2$-SGD**: This combines $\\mu^2$ with SGD. Although $\\mu^2$ could work with other first-order methods, the authors focus on SGD to derive theoretical guarantees. Theorem 4.2 shows that $\\mu^2$-SGD achieves optimal convergence rates for noiseless ($O(L/T)$) and noisy ($O(L/T + \\tilde{\\sigma}/\\sqrt{T})$) settings using a fixed learning rate $\\eta_{\\text{Offline}} = 1/8LT$. Remarkably, this rate does not need to change between noiseless and noisy conditions.\n\n2. **$\\mu^2$-ExtraSGD**: This accelerated variant of $\\mu^2$-SGD uses the ExtraGradient framework to achieve optimal convergence rates of $O(L/T^2)$ (noiseless) and $O(L/T^2 + \\tilde{\\sigma}/\\sqrt{T})$ (noisy) with a fixed learning rate $\\eta_{\\text{Offline}} = 1/2L$.\n\nExperiments on MNIST and CIFAR-10 datasets, using convex (logistic regression) and non-convex (deep learning) models, demonstrate $\\mu^2$-SGD's stability and performance over a range of learning rates compared to various baseline optimizers, including SGD, Polyak momentum, and individual applications of Anytime Averaging and STORM.", "questions": "I am curious to know about your choice of  single sample per iterate setting. I understand that this choice might be more convenient to work in theory, but could you still carry the same theory using batch size b?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-organized, with clear explanations of each momentum component and its integration into $\\mu^2$. A convergence guarantee for stochastic optimization with a fixed step-size addresses a significant challenge in optimization.\n\n- The theoretical results are rigorously supported. Extending Theorem 4.2 to the accelerated version in Theorem 5.1 provides a pleasing completeness to the theory. In the former, the learning rate has a dependency on $T$, which prevents it from achieving the accelerated rate. This dependency is eliminated by introduction of the $\\mu^2$-ExtraSGD.\n\n- The theoretical results carry over nicely in the convex experiment, logistic regression on MNIST. $\\mu^2$SGD consistently achieves the best performance across a very wide range of learning rates ($10^{-3}$ to $10^3$). Unfortunately, I am unable to tell where each method lies in the last plot in Figure 1 ($10^{-4}$).", "weaknesses": "- My main critique of this paper goes back to its main promise: with $\\mu^2$SGD, convergence using a fixed step-size is achievable in a stochastic setting. However, although the step-size is fixed, varying momentum parameters, $\\alpha$ and $\\beta$, are required to prove convergence in Theorem 4.2. The decreasing step-size nature necessary for convergence in a stochastic setting seems to be delegated to the momentum parameter here. That being said, I appreciate the theoretical results and the simplicity of the schedule for $\\alpha$. This same schedule was also used in the experiments, and it seems to work well.\n- There is no experiment on $\\mu^2$-ExtraSGD. Observing the accelerated rate in experiments could have potentially highlighted the strength of this method. I would also be curious to see how this acceleration performs compared to the Nesterov accelerated method. \n- Although the paper shows $\\mu^2$’s stability across learning rates, there is little analysis on how sensitive the algorithm might be to momentum parameter choices, especially in non-convex settings where fixed parameters are used.", "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": "wYZmDXEPqQ", "reviewer": "Reviewer_eNgP", "summary": "Combining two existing methods, the authors propose an accelerated SGD mechanism that is stable w.r.t. learning rate. The authors provide rigorous justifications for their claims and supporting experiments.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. By combining two existing methods--Anytime-SGD (Cutkosky, 2019) and STORM (STochastic Recursive Momentum) (Cutkosky & Orabona, 2019), the authors propose $\\mu^2$-SGD.\n\n2. The authors show the error term is upper bounded by $\\frac{1}{t}$ with $\\mu^2$-SGD. Moreover, they obtain an upper bound for the excess loss that gives a noise independent optimal learning rate, which results in a wider range of optimal choice for learning rate compared to SGD. \n\n3. By adding Optimistic-OGD, the authors propse an accelerated version of $\\mu^2$-SGD--$\\mu^2$-ExtraSGD. The optimal learning rate in this case is constant in time so the optimal rate can be obtained without doing time-varying learning rate. \n\n4. The authors have experiments in both convex and non-convex setting to verify their results. Experiments show $\\mu^2$-SGD and $\\mu^2$-ExtraSGD are stable w.r.t different learning rates while other methods don't. Experiments are done thoroughly with details given in the appendix.", "weaknesses": "1. The main contribution of this work--$\\mu^2$-SGD and $\\mu^2$-ExtraSGD--comes by combining two existing works. The proofs for main theorems are quite traditional. One could argue this lacks novelty, although I personally found the results interesting.\n\n2. In the numerical experiments (non-convex setting), It seems $\\mu^2$-SGD and $\\mu^2$-ExtraSGD only make a difference when the learning rate is far away from normal choices. More precisely, Figure 2 shows all methods are quite similar for $\\eta\\leq1$. $\\mu^2$-SGD and $\\mu^2$-ExtraSGD are better only when $\\eta >1$, which is not a typical choice for learning rate anyway. I am not sure how learning rate stability is appreciated by the community. \n\n3. By allowing a wider range of learning rates, one could argue that with this method, we don’t need to tune the learning rate anymore, like we could set it to be 1. However, $\\mu^2$-SGD and $\\mu^2$-ExtraSGD are not hyperparameter free, i.e. they introduce weights $\\alpha_t$ and Corrected Momentum weights $\\beta_t$, which are chosen to be $t$ and $\\frac{1}{t}$ in the experiments. I wish the authors could give more insights into this topic. If the cost of reducing one hyperparameter is introducing two hyperparameters, I am not sure it’s worth it. \n\n4. The experiments are done for different learning rates, but I found the plots were hard to read when the accuracies/losses got too close. Presenting results with an additional table could help in these cases.", "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": "s2uTe0IUqN", "reviewer": "Reviewer_pANq", "summary": "This paper proposes a novel gradient estimator for stochastic convex optimization, combining momentum-based techniques. Using this estimator, the authors develop robust SGD-style algorithms that achieve optimal convergence rates in both noiseless and noisy settings, maintaining stable performance over a wide range of learning rates.", "questions": "1.\tCould the author provide more comparisons between the proposed algorithm and parameter-free algorithms?\n2.\tCould the author include additional experiments on the impact of noise on the algorithm?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Considering algorithms that work in both noisy and noise-free conditions helps improve the robustness of the algorithm.", "weaknesses": "1.\tThe structure of this paper makes it difficult to follow, especially in terms of understanding the novelty of the algorithms.\n2.\tThe experimental results presented do not convincingly demonstrate the superiority of the proposed algorithm. The choice of learning rates between 10 and 1000 is unconventional and the hyperparameter settings for STORM are not clearly defined. Furthermore, the generalization benefits mentioned by the author in line 52 has no experimental support.\n3.\tThe novelty of this paper appears to be limited. For example, STORM was originally designed for a non-convex setting, and one of the main contributions of this paper seems to be the redesign of STORM's parameters for a convex setting.\n4.\tMany fully parameter-free algorithms[1,2] have appeared recently, which do not require knowledge of the smoothing constant $L$ and can achieve the same convergence rate. In contrast, this paper still relies on smoothing constants to determine the learning rate. Under fully parameter-free conditions, even a wide range of learning rate options appears to lose its significance.\n\n[1] Khaled A, Jin C. Tuning-Free Stochastic Optimization[J]. arXiv preprint arXiv:2402.07793, 2024.\n[2] Ivgi M, Hinder O, Carmon Y. Dog is sgd’s best friend: A parameter-free dynamic step size schedule[C]//International Conference on Machine Learning. PMLR, 2023: 14465-14499.", "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)