Stab-SGD: Noise-Adaptivity in Smooth Optimization with Stability Ratios
Authors: David A. R. Robin
Killian Bakong
Kevin Scaman
Venue: NeurIPS 2025 poster ()
Keywords: learning theory
noise-adaptive hyperparameters
schedule-free gradient descent
smooth last-iterate optimization
Primary area: theory
TL;DR: Estimating the stability of stochastic gradient estimates provably yields an efficient and horizon-free adaptive algorithm with noise-indepent hyperparameters.

Abstract: In the context of smooth stochastic optimization with first order methods, we introduce the stability ratio of gradient estimates, as a measure of local relative noise level, from zero for pure noise to one for negligible noise. We show that a schedule-free variant (Stab-SGD) of stochastic gradient descent obtained by just shrinking the learning rate by the stability ratio achieves real adaptivity to noise levels (i.e. without tuning hyperparameters to the gradient's variance), with all key properties of a good schedule-free algorithm: neither plateau nor explosion at intialization, and no saturation of the loss.
We believe this theoretical development reveals the importance of estimating the local stability ratio in the construction of well-behaved (last-iterate) schedule-free algorithms, particularly when hyperparameter-tuning budgets are a small fraction of the total budget since noise-adaptivity and cheaper horizon-free tuning are most crucial in this regime.

Stab-SGD: Noise-Adaptivity in Smooth Optimization with Stability Ratios
David A. R. Robin INRIA ENS Paris PSL Research University
Killian Bakong INRIA -ENS Paris PSL Research University
Kevin Scaman INRIA ENS Paris PSL Research University
Abstract
In the context of smooth stochastic optimization with first order methods, we introduce the stability ratio of gradient estimates, as a measure of local relative noise level, from zero for pure noise to for negligible noise. We show that schedule- free variant (Stab-SGD) of stochastic gradient descent obtained by just shrinking the learning rate by the stability ratio achieves real adaptivity to noise levels (i.e. without tuning hyperparameters to the gradient's 's variance), with all key properties of good schedule-free algorithm: neither plateau nor explosion intialization, and no saturation of the loss. We believe this theoretical development reveals the importance of estimating the local stability ratio in the construction of well-behaved (last-iterate) schedule- free algorithms, particularly when hyperparameter-tume budgets are a small fraction of the total budget, since adaativvatiiitty and cheaper horizon-fiee free tuning are most crucial in this regime.
We consider the standard Machine Learning setup, where the task of learning function f 129 - R* from samples (X 2 Y E y) ~ DD is decomposed into a parameterization F : 1Rd IR9 + R and loss function é: y I + R, with the aim minimize E[E(Y, f(=)) 2). A parameter yields a predicted function fa = F(O.-): Rd + R* whose quality evaluated according to C()) Ex.y [e(Y, ((,, X))] defining loss function L Rd -> TR to be minimized.
0 e Edd
Typical scenarios include least-squares regression E(u, v) = ||u - u/3 for y = R with functional optimum x r E
ær; and classification with cross-entropy Ely, u) u. + log E. exp(u,) uu)) for } [k.. The success of deep learning has taken this long past the historically well-studied linear case of d q x k, with impressive empirical performance lacking a strong theoretical support.
Using small batches of data to estimate gradients is one of the keys used to scale up such settings, leading to stochastic iterative algorithms. This randomness induces failures of constant-step gradient descents, which saturate and fail to minimize the loss past a threshold (e.g. Wilson and Martinez [2001]). This leads the of schedulers to shrink the learning rate over time. Setting it too low slows down optimization, and too high recovers saturated losses, thus even more hyperparameters are added to define schedulers of varying decay rates such as n nu t for [0, 1].
Related works. The elimination of such hyperparameters, by theory-backed choice of algorithm, has naturally been an active study of research. Such tentatives includes the carly "Adagrad" [Duchi et al., 2011] and "Adadelta" [Zeiler, 2012] adaptive algorithms, but also "AC-SA" [Lan, 2012, Sec 3.1] and its more recent variants such as "Schedule-free SGD" [Defazio et al., 2024]. One branch of this effort chose to model the loss L as Lipschitz, i.c. having bounded gradients, see for instance the "COCOB" [Orabona and Tommasi, 2017, Thm 1] and "D-Adapt" algorithms [Defazio and Mishchenko, 2023, Thm 3] with known Lipschitz constant. Despite the immediate incompatibility of the
with the lqaates objective, this modeling choice is supported by the ReLU non-linearity + m0 which is differentiable (and thus not smooth) the origin.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The Lipschitz-model, typically used with convexity of L in addition, does not produce guarantees for the last iterate, but for the average + +. 24 or ergodic average Σ. n.Fz// Σ. ?t of iterates [Garrigos and Gower, 2023, Thm 9.6 9. 9.12]. On the contrary, there is growing evidence that such aggregation not mandatory' (e.g. the same reference Orabona and Tommasi [2017. Algorithm 2] from the Lipschitz-model branch does not use averaging on neural network experiments), and possibly detrimental in non-convex cases [Zhou et al., 2020, Figure 4]. Other requirements such as bounded domain are also questionnable. A second branch of this research effort thus focuses on smooth model of the loss L, i.e. Lipschitz-continouss gradients, which yield good last-iterate predictions (see Garrigos and Gower [2023, Thm 4.3] for the deterministic case and Bach and Moulines [201] 1, Thm 4] for the stochastic case with power schedule). By continuous-diffceretaailll differentiability. these losses have gradients converging to near the global minimum which naturally leads to smaller steps, contrary to Lipschitz losses. This lack of averaging is also supported, outside the convex case using Jensen's 's inequality, by the lack of guarantees on the loss of the average iterate, even if the averaged loss is controlled.
Although this smooth model does not immediately fit the ReLU-based networks, experiments with smooth non-lincarities often match performance of ReLU networks [Clevert et al., 2016, Elfwing et al., 2018, Sitzmann et al., 2020]. Moreover, any continuously differentiable function is smooth on compact domains, which supports the idea that this model will also be a good description of training dynamics naturally constrained to compact set, e.g. by regularization.
Contributions. We introduce in Sec. I the stability ratio, as measure of gradient stochasticity, and as a shrinkage of SGD learning rates to obtain an algorithm adaptive to noise levels, formalized in Sec. 2. We show that this ratio is computable from samples and give an estimator. We prove in Sec. how this adaptively achieves the optimal last-iterate rates of SGD at various noise levels, without the need to tune the learning rate to the (unknown) noise level or training horizon. We validate these statements with experiments in convex and deep learning scenarios in Sec. 4.
1 Stability Ratio: ensuring (strict) expected loss decrease
In gradient descents with large amounts of noise, common practice is to shrink the step-size, backed by the standard intuition that lower learning rates are required to converge to low loss values. To quantify how much lower, define measure of "relative" or "normalized" noise level (between zero and one), inspired by classical smooth stochastic analysis. and show shrinking by this quantity achieved the desired adaptive result. For a random variable X Rd (not identically zero) with 0 < EE [I] x1 < +oc, we denote as "Stability Ratio" the quantity Stab (X) E [0, 1] defined by
E [ 12
Stab (X)
E E
Note, for μ [[X] * O, that V[x] = σ² implies Stab (X) 1/(1 02/11m]2), thus smaller variance leads to a stability ratio closer to 1. On the other hand, near-zero mean and non neglnggiii variance give stability ratios approaching zero: these the estimates causing instabilities in the loss. The lower the stability ratio of the gradient, the lower the step-size must be taken to avoid instability.
For an SGD sequence (0, E IRe), using u stochastic gradient estimates G R (.,,)) to compute 0.41 = 02 GT, the loss variation for a 3-smooth function is at most
3 [(0++1) L(O.) < -T (VL(0.) G.+1) + ?nd ||a+1122
When G (..)),) this is minimized at 7)- 1//8, as in classical smooth deterministic analysis. In the stochastic case, taking the expectation and minimizing immediately gives 1): Stab (G++1) /B. Moreover, 7) < Stab (G++1) / ensures that TBG., [E(0++1)) a decrease similar to that of gradient flow. Convergence is slowed down by a factor Stab (G.+1 that is equal to 1 in the deterministic regime, and small in the high variance regime (where [(..) and E [[G++1 [2]] > 1). In what follows, we refer to SGD with such adaptive step-sizes as Stab-SGD, and discuss how to estimate this stability ratio in practice in Sec. 2.2.
< -% / ((0,)) 2, and thus
0
'This claim is also supported for instance by the GPT3 training, which uses Adam without averaging [Brown al., 2020, Appendix p43], and the MuZero training. which uses a momentum version without averaging Schrittieeeer al. [2019] (sce Ancillary file "pseudocode.py" I.553).
formally, satisfying E Gr+1 | 0:] VL(0.)) with finite second moment IB[ ||Gr-1]| [., < +00.

---

1.1 Adaptivity to noise level of stability-adjusted learning rates
Two typical regimes of SGD are depicted in Figure 1.1, with quadratic problems and injected additive gaussian noise ~ (0, o for gradient estimates (varying oo), for a total variance of o² ozd.
1
L: L: R
x² = =1)xe(d E IR",
d = 250
(QSC)
1+
4: Z:ZER H 2
Σ 1<d
2
x = (2 xE(d) kE(l)] E ER, d = 25
(QWC)
Both losses are smooth with parameter 3 3= 1. Problem QSC has ((x") = 3.05, and is Mo -ntstnongly convex with A4 1/2500 4 10-3 On the other hand, Problem QWC has ||x00 x² 11 x 1.33, [(x²) R 0.5714, and is 141 stroongy convex with μr = 2-25 = 3 10-8, which is too small to play a quantitative role in experiments, hence it is likely better described by weakly-convex smooth theory.
(a) Problem QSC, low noise (o² = 10016.. d)
(h) Problem QWC, high noise (a² = d)
SGD: d 7/
SGD: 7): = t 1/2 Stab-SGD (Sec. 2.1)
10
Mcan excess loss
x 1-1
10-1
104
10-2
Mean excess loss
100
10-3 3
10-4
10
10-8
10-3
100
102 102
10 10t 10 10 10? 10
10
10
Iteration E N
10-20
SGD: np 1
SGD: 1j: = L 1/2
100
10t 10a 1 10 10st 10t 10 10s
y vott" txt-1/3 Stab-SGD (Sec. 2.1)
Iteration E N
Figure 1: Mean excess loss of SGD and variants. The hyperparameter of SGD (both constant and scheduled) is tuned by grid search at 10s iterations (vertical dashed line). Bounds of Sec. are presented with dotted lines. Details of all experimental protocols deferred Sec. 4.
In (near- jeaandeddeemiiitiic settings, large step sizes are necessary, and decreasing too much gives slow asymptotic convergence (see Fig. la). Fast-decreasing schedulers emulating these large (near- constant) learning rates need huge initial learning rates, causing initial explosions which are pro- hibitive in deep learning. On the contrary, in more noisy settings (see Fig. lb), shrinking the learning rate sufficiently is necessary, and constant learning rates trying to lower the saturation threshold will use much lower learning rates causing large initial plateaus. In both cases, the trajectory of Stab-SGD seems a more reasonable balance to strive for: no explosion, no initial plateau, no saturation.
(a) Constant 1/: Yju
(b) Schedule 7) 17u ---1//
(c) Schedule yp m t=
Mcan excess loss
10
10
10
log (7o)
10-1
10
10
5.0
10-2
10-2
10
4.0
10-3
10-3
10
3.0
-2.0
10
10-4
10
-1.5
10
10-6
10-5
-1.0
10"
102
10*
10 10a
10"
10a
10
10
10
10"
10a
10a
10 10a
0.5
Iteration t N
Iteration t E N
Iteration t E N
+0.0
Figure 2: Mean excess loss of various SGD schedulers on Problem QWC, 0² d. Horizon-dependent hyperparameters are still needed, with high sensitivity to perturbations of the noise-dependent ?)o-
The use of schedulers does not eliminate the need to tune the learning rate (see Fig. 2b) and selection of learning rate decrease speed is not trivial (compare with Fig. 2c). Typical prescriptions tuned to the target horizon I' N. e.g. with the constant but horizon-dependen rate 1); = Co-1 1-2
3

---

2 Stab-SGD: Stochastic Gradient Descent with stability-adapted step-sizes
We build our formal statements in the rigorous formalism of stochastic processes, motivated by the crucial part that the step-sizes 7/ must depend on the local stability ratio of gradient estimates, which itself is function of the iterates, therefore the step-sizes are random and must be handled carefully.
We take (2, P) to be a probability space, with a filtration (Fa) of A. A sequence random variables (NN) is said to be "adapted" to F if X; is F--easurable for all E N.
Intuition. The standard informal interpretation that F models the passage of time, and X is adapted to F if X; is "known" at time i E N. In our case, if the sequence of iterates (0,, is adapted to F, then any deterministic function Y .. of previous iterates is adapted to as well.
Definition (Stochastic Gradient Descent, with unbiased gradients and stochastic stepsizes).
A stochastic gradient descent of C R IR an F-adapted sequence of random variables (0,, E IR" )ne together with two F-adapted sequences (G, E IR JnEN and (7/ E R.) such that VL(00)
for all L E N, it holds 0.+1 02 7// Ge+1 and E [[G++1 [Fre
Definition 2 (Conditional Stability Ratio). The Stability Ratio of random variable X E R
conditionally on Fe is defined for any E N as: Stab (X Fi) = || R Fi
Fil1l [ F...
2.1 Stab-SGD: A noise-adaptive algorithm with stability oracles
The Stab-SGD iterates (0g E JEN of loss L C:R" - R are defined
lc+1 0, - TJ: G1+1
Tt Stab (G(+1 Fi)
for any adapted sequence (Gt), satisfying B [G++1 |Fr = ((,))) and V [[++1 [F)
< +00.
Note that Stab-SGD has a single hyperparameter 3 E R2, which must be set below the smoothness constant of C. There is no coise-hyperparamete and no horizon-hye hyperparameter, contrary to SGD bounds typically* using step-size пtt x o /-////// to give bounds at horizon T' E N under variance a². Stab-SGD is noise-adaptive algorithm (conditionally on access to stability ratios), in the sense that it depends on the realized noise level only through the stability ratio, which can be adaptively estimated every step. This single algorithm adaptively achieves all the convergence rates of Table 1.
Table 1: Convergence rate of Stab-SGD under affine variance V [Gu+1 a +
E [[((r++)] - L
Noise
Convex 3-smooth
μ-strongly convex 3-smooth
Non-convex 3-smooth
0 a²
O (T-1)
o (exp 1 Ita )T)
0 (T-1) o (T-1/2)
0² > 0 o (T-1/3)
O (T-1))
Rates in Table 1 are presented in expectation for the last iterate. In particular, the (TT-1/3) rate in the weakly-convex smooth setting matches Bach and Moulines [2011, Theorem 4] (conjectured to be the optimal horizon-firt last-iterate rate for SGD with schedule = To t and achieved for -2/3, see reference for details"). The weakly-convex case additionally assumes that there exists 8" Rd such that L(#*) L inf C, see Theorem I for the complete statement.
2.2 Estimations of Stability Ratio from samples
natural estimator for Stab (X) consists in replacing expectations with averages over n iid samples. Unfortunately, this estimator is strongly biased towards 1 when the number of samples is small. We thus propose another estimator using Jackknife resampling for the numerator [Quenouille, 1956].
WWitoout loss of generality, can assume that Gr+1 is identically zero by skipping such iterations.
*See Garrigos and Gower [2023, Thm 5.5) after canceling gradients with respect to step-size.
'A slighly altered di min(1/25 sjo/ vt) reaching improved rate (loo((T))VT)) But it does not reach the a = 0 or μ >> 0 fast rates without modifying m. Thus the question of getting improved rate for the bottom-left case while retaining adaptivity is left open.
shown to break this conjecture in Liu and Zhou [2023].

---

Definition 3. The Jackknife estimator of Stab (X) from iid samples (X, E R ke(m) is
1 Σ, j (X,, n n-
R
E
This can be computed by constructing the sequences (M; E Rd )iein and (Z, E Rd xe([n++]] from Mo R and Zo 0 e R. MM+1 M, + (X, M,)((i 1) compute the mean, and Z1+1 = Z, + (11x, - Zz) + 1) for the second moment, then Rn - M, Z,, ZZn This gives a numerically stable algorithm with (11) space complexity to estimate the stability ratio.
Lemma (Relative error of stability estimation). Ler (X; E ke(m) be iid random variables. Define Jn 1] Eigs Xi E R and Zn = > II 4 1 E R4,, then Ra clip (o. 11 E [0, 1].
Let E [x), and 0² = E [[|X 1112], and K = E X
[1 If R. Stab (X) # 0,
E
Rn - R. )²}
2
Ri-1
44 4x
n1 + R.,² exp (-5%)
72
Rr
In particular (when clipping to [0, 1J. R Stab (X) with high probability, so this estimator consistent. This lemma is direct consequence of Lemma A.9. Note that for isotropic multivariate normal random variables X E Rd, such as X ~ NO0 o² /), it holds K S 1 + 3/d (for any a). Thus the number of samples needed to estimate a stability ratio R. > 0 often order n x R, The kurtosis is used to quantify the number of samples needed to estimate the variance.
3 Convergence analysis
The tactic used for following proofs closely tracks the continuous-time analogue by integra- tion along gradient flows (i.c. [d((CC) 0,C -1 ((C)) < x(Co) - t] for any desingularizer Φ R + I., such as & log). This is done by leveraging the "sufficient decrease" inequality (obtained by construction of Stab-SGD) together with
[(+,) S - - the variance control assumption GG++1 Fi S a ((+)) + o², to obtain an "average sufficient decrease" inequality E [C[(0++]]
E [[((((+1)]
[c.) S - v
(E [V }). for well-chosen convex u²/(o" 2 + (1 + a)u) for this affine variance control.
and increasing function th, namely v
This result can be composed with any bound of the form E [[IVL( 2 & (E] L"), to bound the optimization gap A, = [[(,)] L as A, S Φ- (o(Ao) + 1/(23)), where + 1/(0 (u). Different assumptions, leading various
obtained by integration of ( choices of yield different convergence speeds, as integrated into the function Φ. In particular, local Kurdyka-Lojasiewwa inequalities | (C((() L)) for convex functionn şp immediately satisfy the previous condition in expectation (such as (xx) = 2μ for p-strong convexity).
3.1 Convergence statements with stability oracles
Assumption (Stab-SGr with stability oracle and fffiell-boundee variance).
This set of assumptions satisfied if there are constants 3 e E., a E R., and a E R. such that:
Rd + IR is differentiable and uniformly 3-smooth
(0l E Rdd G. Rd me Rt, )IEN is an SGD of L (Definition
EE V[G++1 F.J a (V) (0) o² (affinely bounded variance)
V N, T) = Stab (G++1 Fi) / (strong stability condition)
In such case, the sequence of random variables N - Rd are called Stab-SGD iterates.
'See Lemma A.10 appendix.
have empirical estimates variance close to true variance, while high kurtosis requires more samples for accurate estimation of variance. "See Beck [2014, Lemma 4.3 and Sec 4.7.3] for the classical deterministic analysis leveraging this condition.
VVariables with low kurtosis x := [| / [ 1 Stab (JIX
5

---

The following theorems are derived from Corollary A.1, Corollary A.2, and Proposition A.3. Theorem 1 (Weakly convex smooth rate). If L Rd IR is convex, uniformly B-smooth, and if there exists 6" E @ such that L = [()*), then for any Stab-SGD iterates 8 : - R satisfying Assumption I, and if
2 20
3Dg
2
(1 ax) a))
3 8
then E ((0r+1)] S L" E, where D = E |00 - 11 measures initial distance to optimum.
Theorem (Strongly convex smooth rate). If C 12d + R is uniformly 3-smooth and u-strongly
convex, then any Stab-SGD iterates 0: N + R2 satisfying Assumption 1, and if
a² + (1 + 0) 3 24
A
T 2
log /
then IE [ [C(O++)) 5-++5 where Ao E [(0))] L measures the initial optimization gap.
Theorem 3 (Non-convex rate). If C
Rd + R is uniformly B-smooth, for any Stab-SGD iterates
0: N IRd satisfying Assumption 1,
V,EN,
E
Σ
<1+
232
2
T
T
T
KT
where 4. = [[((0)]] L measures the optimization gap at initialization.
3.2 Inline Stability Estimation
To incorporate the estimation of the gradient's ' stability ratio in the algorithm at little overhead cost, we propose Algorithm with access to noisy gradients but without a stability oracle.
This algorithm uses three parame-
Input: Tp E R. To E Ri < 1, n, R [0,
ters to control estimation overhead:
(S, < (S, = 1 E 0, 1, To=1e TR.)
a sample overhead < E R (of order 10 to 100)
for E N do
if (k = 0) or (k 2 T) then
a time step x E R
n n [c/S] E
a time exponent 7 [0. 1]
(M,, 7o) + (0 R
for i [n] do
The most conservative configura- tion (7 = 0, K = 1) estimates the stability ratio at every step. How- ever, the stability ratio is expected to be relatively continuous, then looser configuration (y = 1) will perform only logarithmically many estimations with respect to the hori- zon, which is minimal overhead.
GR,i E Rd
(estimate of V[(xx)]
M f M, + (v: - M.)/(i+
Z++1 + Zz + (1|v 2))(i+1)
end
n
||M Zz
S 5
[Stab estimator]
n1 1
Zi
T + T + K 7
end
In looser configurations, incorrect ratios could yield temporary satu- rations (overestimation), tempo- end
mi Tk+1 f- F3. (No S) m)m,
G1 E Rd
[fresh estimate of v((xx)]
rary slowdowns (underestimation).
Algorithm 1: Inline Stab-SGD
While we can't t guarantee the quality of the looser configurations without additional assumptions such as continuity of noise variance, we observe empirically that loose options such (7 1, x 0.5) still display all key properties of Stab-SGD no intial plateau or explosion, and no saturation.
Note on overhead cost. For total of T gradients queried stability ratios above s. 0. at most a fraction c/(1 + c) E J0, [[ of queries are dedicated to stability estimation, where c E R can be controlled by tuning (e.g. set to e 1). If = then e log=)= is vanishing with T. If 7 0, then < ( & -1 For the exponent a. the movement's ss characteristic timescale is estimated using E. [[[] [F] < (I) V ((0,) I|2 + 2)11/2 (unrigorously) without expectations for a quick approximation, and smoothness as / (Vv(()))) 112 < 28(C(x) - Ct) with L for simplicity,
log(T))
[C((++))]1
||:+4:: 0el <
To mnIG+++41ll
$
[(0++R)
C +02/1/2
AsAt
K
A

---

If (0,)) & Co C//31/3, this bound is at most C1 At 1-33, so the unit-scale movements' characteristic time is at most At ~ (1/3./3 This quick calculation suggests that even in the worst case, 1/3 should remain safe option. Similarly, rate [())) S Co レー could use ς conjecture that such loose settings will be useable far outside this regime. Characterisation of precise noise-continuity hypotheses under which such choices are provably safe is left for future work.
safely, but we
Experiments
Methods." We perform experiments in two stages, first training for To NN (tuning horizon) iterations on a grid of hyperparameters (log Y/u from to +5 by increments of 0.5, a total
25 values). We then select the best hyperparameter (at Tu) and train with this value for T E N iterations. The fraction of the total budget spent on hyperparameter tuning is thus To (l: To + T), and the tuning overhead (excess cost of tuning relative to training) is & T./T. These quantities on large-scale experiments failing to take hyperparameter-tuninn costs into account, but there is common intuition that popular algorithms require massive fraction of budget allocated to tuning.
rarely reported
4.1 Comparisons with concurrent schedule-free algorithms
Cheap regime: low noise, strong convexity. Fig. presents loss as function of tuning horizon.
Vertical gaps within curves in- dicate the final gap in loss if less budget is spent on tuning.
Mean loss at T 10a
10
SGD: 1/: = 1/o
10 10-12
SGD: 1/0 / 1/2
The sensitivity of SGD vis-
10 14
Stab-SGD: =
ible the right (the noise-
10 16
Stab-SGD (tuned)
dominated regime). The long- horizon optimal learning cannot be selected well on short tuning horizons (which do not enter the noise regime), a property that is likely shared by deep learning settings.
Algorithm 1
10 18
D-Adapt: do 1
10a
10a
10a
107
"Schedule-free"
(0.003%)
(0.25%)
(25%)
(96%)
COCOB
+0.003%
+0.25%
+20%
+2500%
COCOB-backpre
Tuning horizon (fraction) +overhead
Figure Mis-tuning cost on Problem QSC, 0² = 10 16
10
SGD: T/: 10
Mean excess loss
10"
SGD: 1): -1.+ t-1/2
10-4
Stab-SGD: v 100
10-8 8
Algorithm 1: n 10"
D-Adapt (do = 200): G = 10
10 12
D-Adapt (d, 4): G = 10-5
10-16
"Schedule-free"" 7= 10
10-20
COCOB 10 0.5
109
10
102
10
104
105
106
10"
108
COCOB- (a 10²)
Iteration
Figure Evolution of the loss on Problem QSC, 0² 10 d. Tuning horizon as dashed line.
Figure 4 depicts the evolution of the loss over time for tuning horizon To 103. Algorithms designed for the noisy regime alone (such as COCOB and D-Adapt, which use iterate-averaging) fail take advantage of strong convexity, leaving them 8 orders of magnitude behind 10 iterations.
"The source code to reproduce experiments this section and the next is available online StS_b-SDDD.
attps://wwe htt::/.ggttut.. github.........
and ( 50. Iteration count is total number of gradients queried. Results overlap with Stab-SGD (with stability oracles), both tuned and pre-set to n) 8ー1 hardly visible. Results overlap with D-Adapt (both settings). Both COCOB and D- D-Adapt are average-iterate algorithms, the averaging slows down convergence in this regime, yielding very similar speeds.
Algorithm with (loose) 7
7

---

Expensive regime: smooth with high noise. Figure 5 presents mean loss as a function of tuning horizon for Problem QWC. Each training run at 10" iterations takes about one hour on our CPUs.
Slope indicates sensitivity of the hyperparameter to the tun- ing horizon. Algorithms with large slopes are only usable if essentially all budget is spent tuning the sensitive parameter.
10
102
SGD: 1NU
10
SGD: Yh 1/2
Mcan loss at
10
Stab-SGB (1 1)
Stab-SGD (tuned)
10
Algorithm 1
10-1
D-Adapt (da 22
At high noise with this train- ing horizon (10"), SGD only outperforms Stab-SGD if at least 71% of the total budget is spent on hyperparameter tun-
-
D-Adapt (do = 200)
10
"Schedule-free"
10
10
10
10?
COCOB
(0.003%) (0.25%)
(25%)
(96%)
ROCOB-backppe
+0.003%
+0.25%
+20%
+2500%
ing, i.c if an extra +250% of the training budget is spent tuning at To 10th horizon.
Tuning horizon (fraction) +overhead
Figure 5: Mis-tuning cost on Problem QWC, o² === d.
Algorithms previously well- pell-performing (such "Schedule-Free SGD") not good in this regime, sometimes even indistinguishable from equivalently-uue SGD, On the contrary, algorithms designed for this setting (e.g. COCOB) perform much better. This leaderboard reversal induces difficulty to choose the best algorithm with unknown noise level. Stab-SGD gives consistent performance both settings. The price of this adaptivity is apparent in both cases, but not necessarily prohibitive.
100
SGD: ") 10
Mean excess loss
10-1
SGD: 1/: 10 10-1.6, 1--1//1//
10
Stab-SGD: 1): =
Algorithm 1 (tuned): Wl 10
10-3
D-Adapt (d, 2):
10.
10
D-Adapt (do = 200): = 10
10-5
COCOB: L 10
100
10a
10a
103
10
10
106
107
1
COCOB- BackB-backprop (a 10²)
Iteration E N
"Schedule-free SG = -3.
Figure 6: Evolution of the loss Problem QWC, o² d. Tuning horizon dashed line.
Although asymptotic performance slightly suboptimal compared to other methods, and does not achieve the minimax optimal rate of averaging methods, the complete absence of noise- noise-depnndent tuning of the hyperparameter, and reasonable properties (no plateau, no explosion, no saturation) of the Stab-SGD trajectory make it interesting research direction for schedule-fis free settings aiming for those properties, particularly when the hyperparameter-ttnme tunnng cost taken into account.
The proof of last-iterate expected loss matching these observations also highlights the importance of the stability ratio of gradients in the development of smooth optimization with last-iterate guarantees, possibly better suited to the study of non-convex models such as neural networks.
We conjecture that it will be possible construct accelerated noise-adaptive algorithms which will be competitive not only on low tuming budgets, but also on high tuning budgets (right end of Figure 5) where Stab-SGD and its stability to suboptimal asymptotic rate. Nonetheless, works on accelerated stochastic algorithms typically use hyperparameters with convoluted dependence on noise parameters, see for instance Jain al. [2018, 8, Thm 1] with impressive speed but four noise- deseedeeenddntt hyperparameters for the case of quadratic problems alone. Therefore, we suspect that an accelerated noise-adane adaative horizon-free extension of StabSGD could be vastly more complicated algorithm than the ones presented here.
variant Algorithm are found be lacking, possibly due
Algorithm with (loose) 7 = 1, x = 1, and Ç = 50. Iteration count total numher of gradients queried. Resuult almost perfectly overlap with SGD, difference hardly visible

---

4.2 ResNet training experiments on CIFAR-10
Methods. We perform experiments on the CIFAR-10 10 image classification dataset [Krizhevsky, 2009] with the ResNet-56 architecture" 14 [He et al., 2015a, Sec 4.21. We compare with the aforementioned original ResNet publication, which uses learning rate 10-1 1 for 32k iterations, then 10 2 for the next 16k and 10-3 for the last 16k, totaling 64k iterations (thresholds depicted by dashed vertical lines). We use batches of size 128 sampled without replacement for each epoch (391 batches epoch). We restrict the hyperparameter search for log (7) to a grid from -3 to +1 by steps of 0.5, informed 10-4 for all runs.
by choices in the original reference. We use an Eg weight decay with
We run Algorithm with 10+1, with the configuration x = 10-1, evaluate the overhead of iterations is the number of corresponds the total number of gradients queried, including gradients used for stability estimation.
and Ç 100. To provide both curves: oracle where the number
of stability-stimmation, steps (effective iterations); and raw where iterations
10a
100
Test Accuracy (%)
10a
90
Train Loss
80
10-1
-104
70
0
6
10
12
10-3
Iteration
-104
0
2
8
10
12
Algorithm [oracle] - SGD [original]
Iteration
Algorithm
[raw]
Figure ResNet-56 on CIFAR-I0. Evolution of accuracy and loss, presented as medians and quartiles for error bars, for 20 seeds of Algorithm 1. Average runtime of 4h to 5h per seed GPU,
The results presented in Figure 7 show performance comparable between the oracle variant and SGD with tuned schedule. Without the need to tune scheduler, this algorithm has correctly used first large step-size then much lower, allowing it to break past the mid-traini mid-training plateau incurred by SGD (visible at 32k iterations). Nonetheless, the variance across seeds is significantly increased, and taking into account the cost of stability-ratio estimation (with the raw variant) we can estimate that it needs on the order of twice many iterations for similar performance this experiment. For context, the choice of scheduler must have been guided by experiments, say k E N runs thus the total cost comparison with noise-dependent scheduler tuning between T for the scheduled SGD, and 2 for Algorithm 1 (raw), which is in favor of the adaptive algorithm presented here as soon as k >> 2.
Although not competitive on such problems at this stage of development, Alg. remains a promising research direc- tion, since it maintains in this non-convex setting the desired properties: no initial explosion or plateau, and no saturation requiring large learning rate shrinkage. It reaches lower loss than SGD with 7) 10-1 (before first threshold) without tuning threshold (at 32k) or shrinking factor (x0.1).
10
Stability Ratio
10
10-2
10-3
Fig. shows evolution of the Stability Ratio along trajec- tories. Shrinkage behavior is consistent with the original: small variations up to 10a then decreasing by several orders of magnitude. The original tuned schedule shrinked learning rates at 32k and 48k. More details in Appendix C.2.
10-4
10a
103
10a
10a
Total iterations
Figure 8: Stability along trajectory
14 Note that the numbering refers to CiFAR-targeting architectures [He al., 2015a, See 4.2], contrary to the much larger ResNet-18 18 and ResNet-30 [He et al., 2015a, Sec 4.1]. which target ImageNet [Deng et al., 2009]. The number of tuning runs & N²' not given in the original reference, and left for the reader estimate.

---

104
Test Accuracy (%)
100
+ T
80
Train Loss
10a
60
- T = 10
40
-- T 10
100
20
+ T 10
I T 10a
10-3
10-2
10-1
10"
10a
10-2
10
T 10a
Base learning rate Yoo
Base learning rate
Figure 9: ResNet-56, loss and accuracy function of learning rate for SGD.
This is consistent with convex experiments, indicating that Stab-SGD enables selection of larger base learning rate, which is automatically adapted to the noise level. Indeed, with the initial Stability Ratio around 10-1, the effective learning rate of the first 10 iterations around 10", which is not far from the optimum observed for SGD over that period (see Fig. 9). The performance of the oracle variant (i.e. ignoring stabilit--estimale costs) showcases the competitive behavior that could be reachable for future works achieving cheaper stability estimations.
Conclusion. We introduced the Stability Ratio, a natural measure local relative noise of stochastic gradient estimates, yielding schedule-free variant of SGD achieving real adaptivity to the noise level. We presented new theoretical tools to analyze this stochastic-step algorithm convex, strongly convex and non-convex settings, with strong last-iterate guarantees in expectation, obtained by stochastic version of Bordyka-ELjasiewiie integration. We validated the adaptivity of this proposed algorithm with convex experiments showing that it outperforms algorithms not achieving the fast rate strongly convex problems (such as COCOB or D-Adapt, developped for less regular settings), and that remains in the competitive range without the need for noise-dependent tuning of hyperparameters.. We measured performance on ResNet networks for CIFAR- 10 which further strenghtened that when taking hyperparameter-tunigg budgets into account, this last-iterate noise-adaptive algorithm retains reasonable performance on non-convex deep learning problems. This shows that future algorithms leveraging this idea together with improved estimates of the stability ratio along a training trajectory will likely be able to outperform extensively-tune learning rate schedulers in deep learning scenarios.
Acknovledgements
This work was supported by the French government managed by the Agence Nationale de la Recherche (ANR) through France 2030 program with the reference ANR-23-PEIA-00S (REDEEM project). was also funded in part by the Groupe La Poste, sponsor of the Inria Foundation, framework of the FedMalin Inria Challenge.
10

---

References
Francis Bach and Eric Moulines. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In J. Shawe- Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Asso- ciates, Inc., 2011. URL https::/pproceeddinn neurinn #it1:000008830000acc33//0f0f0000 pdf.
neurips. www.ripscccpppprraaiiiee ppaapr_filese fiwes/ wwwps//pppppp//1/////
Amir Beck. Introduction to Nonlinear Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. doi: 11111///9977111999997991 URL https: //www//wwwwww/.t math. kent edu/
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Vosse, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jefffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. CoRR, abs/2005.14165, 2020. URL https:://// atapaaxxvvv........ www.aog.//a/oooooooooooo..oee. ab///00ss/00555 14165.
Djork-Are Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (clus). In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL //axivv.//////////a org/ abs /111/111111.11 11111.07220 07289.
Aaron Defazio and Konstantin Mishchenko. Learning- rate-frre learning by d-adaptation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 7449-7479. PMLR, 23-29 Jul 2023. URL btstps://proceeee
mlr, wwwps/vveeii /V0es///222////// dww./iiiaa.aaaceeeooooo
Aaron Defazio, Xingyu Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, and Ashok Cutkosky. The road less scheduled. In A. Globerson, L. Mackey, D. Bel- grave, A. Fan, U. Paquet, J. Tomezak, and Zhang, editors, Advances in Neu- ral Information Processing Systems, volume 37, pages 9974-10007. Curran Associates, Inc., 2024. URL https: stttp:://proceedinng newwddddnnnnnnnnnnn....e. neurips cccpapperfilliee files/lllppplle palle///pper/224///11e 08660113801100699440000000066660 cer.reeeeeeepeeeeeeeoeeeeeeeeeee pdf.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009, CVPR 2009. IEEE Conference on, pages 248-255 IEEE, 2009. URL https: ieee org/ abstract/ sestraatt/dccummt//228655
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ul):2121-211 2011.
Stefan Elfwing. Eiji Uchibe, and Kenji Doya. Sigmoid-weighted linear units for neural network func- tion approximation in reinforcement learning. Newral Networks, 107:3-11, 2018. ISSN 0893-6080. doi: https///dk..any///o.oooooeeeeeee scien attac///arriieee/1///99000000010
URL https: : / /wwww sciencedirectt com/ Special issue on deep reinforcement learning.
Xiequan Fan, Ion Grama, and Quansheng Liu. Exponential inequalities for martingales with applica- tions. Electronic Journal of Probability, 20(none): 22, 2015. doi: 10. 10.1214/EJP:20-34000 URL
https://doi. org/10 10. 1214/EJJ..... 349-
Guillaume Garrigos and Robert M Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv preprint 1xXiv:2301.11233 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2015a.

---

Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Sur- passing human-level performance on imagenet classification. In Proceedings of the 2015 IEEE International Conference on Computer Vision (ICCV), ICCV '15, page 1026-1034, USA, 2015b. IEEE Computer Society. ISBN 9781467383912. doi: 10. 2..1100C.22001..222. URL https: / /doii. org/10. 10. 1109/ ICCV 2015. 123.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Pranceth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 545-604. PMLR, 06-09 Jul 2018. URL hat.m1...mmmll.....m
ptttp::/pproceeding: .mw............................. wta.a/nn......ppes/155555.
Michael I. Jordan. Lecture notes: Stats 210b, lecture 3. In Berkeley Statistics Courses, 2007. URL https:// eecs. berkeler berkeley.edu/" pordan/ccuuses//22000 Stttcuuree/stat21___eettte
pdf.
Alex Krizhevsky, Learning multiple layers of features from tiny images. pages 32-33, 2009. URL htttps//wwwrd cs. toronto................ ceaiitt..ddu//// edu/ "adth/"krrzzLLariingg-.
2009--2099-T-01 pdf.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Program- ming, 133(1-2) 06 2012. ISSN 0025-5610. doi: 10.10077110007--00-0444444
Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. arXiv preprint arXiv:23/2.08531 2023.
Francesco Orabona and Tatiana Tommasi. Training deep networks without learning rates through coin betting. In Proceedings of the 31 International Conference on Neural Information Processing Systems, NIPS' 17, page 2157-2167, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
M. H. Quenouille. Notes on bias in estimation. Biometrika, 43:353-360. 1956.
J Schrittwesser, I Antonoglou, T Hubert, K Simonyan, L Sifre, S Schmitt, A Guez, E Lock- hart, D Hassabis, T Graepel, Lillicrap, and D Silver. Mastering atari, go, chess and shogi by planning with learned model. In Nature, 2019. doi: 10.1038/s41586-022 URL https: / arxxvv org/ abs/191111111// 08265. Nature link https: nawurewwwwwa...e.ee/aeeeaa.aeee. com/ articles/s41586- 020 000055860-0000000--------0- and Ancillary anc/pseudocode.p2 py.
00000-555000000005511 000000035----
Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Wetzstein. Implicit neural representations with periodic activation functions. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7462-7473, Curran Associates, Inc., 2020. URL https://proceeddnnin www.:eiiiiiinnnnnniineeeeee neurips.ec. cc/ paper_ files
1ttp:////1115330411110 18df 112c1 2el22233ecccb0333340000000000000
.dff.
A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
D.R. Wilson and T.R. Martinez. The need for small learning rates on large problems. In IJCNN 'O.. International Joint Conference Neural Networks. Proceedings (Cat. No.01CH37222), volume 1, pages 1 115-119 vol.1, 2001. doi: 10. 10110//CNN.2000.909 9399022. URI. https:t/s///xoo edu/papers/wiilson wwwp://ssso..........oo.m wic.nnn01.......m
byu.
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. CoRR, 2012. URL http:
//arxiv. org/ abbs/1212.500.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen P. Boyd, and Peter W. Glynn. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30( 1):7777666 2020. doi: 10.1137/17M1134999 URL https:// //apiii///xvv...//// org/ pd706..6.056
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Schedule-free and noise-adaptive results of Sec. 3 are present in the abstract, along with matching experiments, as claimed.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See end of Section 4.1
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
See Section 3, where Theorem 1, Theorem 2 and Theorem 3 use assumptions
Assumption
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 4, "methods" paragraph.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: Data is openly available, all instructions to reproduce experiments are provided.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //o////ooaeeeeeeeeeee
/nips wwtppcccc//caeeccccccccccccc C ssssonolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See Section 4, "methods" paragraphs, and appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Deep learning experiments feature error bars. Convex experiments with more replications do not display error bars because these would be imperceptibly small.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https : http///eerrrpppeeeeeeeeeeee cttpp////c/pcccccccccccceeeeeeee
Answer: [Yes]
Justification: Both theoretical contributions and experiments with publicly available and widely used data conform with the code cthics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Foundational and theoretical optimization research does not have specific positive or negative societal impacts beyond those of all the field of optimization.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Not applicable, no data models relased.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Section 4 for credits of publicly available assets.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were used in the making of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https:// /ttpa//:///eu.../eeeee cctpe//cecceeeeeecee/22555555 for what should or should not be described.
19

---

A Appendix
In all the appendix, R2 - Rdd ß-smooth function for some E R2, and (0, IRe) a stochastic gradient descent of (Definition 1) with gradient estimates (G++1 E "eE and step-sizes (7/ 2 IIE satisfying 0e+1 0, T/t G141 and E [G2+1 Fi VL(()), where F is
the time filtration.
When appropriate, the variable T E N denotes horizon, S = inf C is the infimum of the loss, and 8" Ied is global optimum L(0*) L when it assumed exist.
A.1 Rates with stability oracle
Lemma A.1 (Base reduction). If for all < T. it holds Nt 3-SStaa (G++1 Fi) (weak stability condition), then it holds
vt S T, E [[((0++)) Fil C(0.) "/t
[VV((0))
Proof. By B-smoothness of L, then simplifying conditional expectations,
1 [(0++1) - ((.)) V.((.)) G++1 + 3n2
2
1 2
E [(0++1) Fil < E [(0:) Th VL(0.) G4+1 +
G
F2
=2"
1
S (().) d VL(O.) E [ G [Ft]
E [[|G++1l8
Fb]
2
V
S ((0)) aL C + 3,8n Stab (Go+1 Fi)
< C()+) T. C/0)))1 27hh [[V2(
& ((e.)
1/t
|VC(0)]1
2
Lemma A.2. For all (a, a) E R22 the function to : R. + R4 is strictly increasing and convex.
u²
: σ² a1+
Proof. By continuity at zero and wiccediiffreentaablltyy of sb on RI, it suffices to check, for every E RT, that (u) > 0 (strict increase) and ( 2 0 (convexity). Write 1 and compute
dxb(w) 2u(o² 2 + cu) cu² 2uo² + cu²
>0 0
(02 + cu)²
(02 cu)²
Then the second derivative of vi is observed to be non-negative, which concludes the proof.
d'vb(u)= (2o² + 2cu + cu)² - (2uo² + cu²) 2e(a" + -cu)
(02 + cu)
(20² + 202 + cu) 2c(2uu² + cc?)
(02 cu)s
2 + 4402cu + 2c 2 - (40 / + 20²u²)
2 (02 + cu)3 20
(02 + cc)
Lemma A.3. For all (a, a) E RR, the function v u E R2 + nZ (a" - (1 ()) admits R,, it holds - (x) I =1+
inverse --1 ; R_ - Rt, and for all
20

---

Proof. By Lemma A.2, vé is strictly increasing and has (b()) - 0 when u + 0, and (2)) + too when u + oc, therefore & is bijective and admits an inverse, which is also strictly increasing.
Moreover, defining 2 = (1 + 0xx + ovT observe that
2²
(1+a)²² + +2(1+))
(b2) 0² (1+00) a)z
0² (1+))x+((+a)))
(1+a)IV
= 0² + (1+a) + (1 + aaooo 2x
Therefore S (2),, which implies ve (xx S z and concludes the proof.
Lemma A.4 (Key reduction).
If for all - T, it holds [[ Fi) S all cl))3( + a² (affinely bounded variance), and M 3- Stab (G++1 Fi) (strong stability condition), then it holds
1I S T, [[((0++1)] -B(0+)))BB((CO.))))
23 (B
where v : u - u² 1002 + (1 + o:) u) is convex and increasing function.
Proof. Starting from Lemma A.1, and using the affinely bounded variance asssumption to obtain
the inequality E [1] Fi I [ [G++1 Fr ]lle V[G++ [F, s (1 + a)) + o².
substituted in the stability ratio, we obtain
E (((00))) [i. ((0.) s - 1/t [V
|VCO1
< 23 02 (1
1
23 (IVC(())))
Therefore, taking expectations, and using convexity of e (Lemma A.2) as E[P(U)) 2 (E(U)).
-[[(0=))--B[000 2 1 (IVC(())
23 v (E [ICC()))
Lemma A.5 (KL stochastic integration).
If for all < T. it holds V G++1 Fil < al|V2((8)11 + o² (affinely bounded variance), and
3 Stab (G++1 Fi) (strong stability condition). and if it holds for some increasing function pp RR. R4 that EE [IVL 0.) 2 & (E [[(,)) - L)), then it holds
t
Vt ST B[C(0(+1) L -- (<([[[())] LT)
23
where & IR., + R is the function defined as ddb(w) = - (0² + +1 a) (())) ((u)=²
In particular, if 2 23 23 (#()) - (bAo)) for A = E [[(b)) - L", then E ((0r+1)] s L +
Proof. Starting from Lemma A.4. and using the last assumption since & is increasing.
1
1 2,3 (w p) (E [C(0,)] L*)
E [CC(0
[[((O)) -
2/3 v (IVC(())) <
Note that by definition ( = = 1 o (w). We will use this to simplify the above equation, but also to observe that d is increasing since (yb o sp) is increasing as a composition of increasing
16 uniquely defined only up constant, the bound invariant change of such additive constant
21

---

functions. Therefore, I is a convex function (since it has increasing derivative) which can be used as (g)) (xx) dd (z) (y z) further simplify
1
dΦ (E [()=)] - (B((((()))) 2
2
1
@ ( ( (*) Z 2/3
Observing that & is decreasing (since it has negative derivate), this implies
E [ [[((++1) - Φ-1 ① (B[[(6)) L* + 2/
Defining Ao = [[()) - L and injecting yields the final claim, by decrease of T.
2 28(((E)) - ( the previous equation
T
-L' -- E -
+ (An) +
S E
23
Lemma A.6 (Squared distance to optimum is submartingale). If L: IRd - IR is convex, and there exists 0* IRd such that L(0*) L", and if for all t S T, it holds qe S 3-1 Stab (G++1 Fi) (weak stability condition), then holds
1L ST
E [110, - 0-] S E
[110- - 01
Proof. Define the random variable Dr E R as D. = 10 11. Observe that expanding the square,
Di+11 - DJ- = 2m G1+1 (0.- - 0¹) + nr |G++1l/2
Thus taking conditional expectations and using the weak stability condition.
E [[D4+ Fi] D3- 22); VL((0)) (0, (0--0") + n | ((.) 113/ Stab (G+41 | Fi)
2mp V ((.))) (0, - 0-)) me
(..)
33
By convexity of L, the first term can be bounded with L ((0,) 2 -V((6)) - (0, (8)- and the second term can be bounded by 3-smoothness of as [(,) S 23((((,)) - C²*,, thus
E DD ]F:] - DJ < 27 (C* - [(O,)) + 21j;
- ()) 0
Hence E Di+1 Fi] S. DD and by induction E [1++1] < E [8] which concludes the proof.
Corollary A.1 (Convex smooth rate).
If Rd IR is convex and there exists 0" E Rd such that L(8*) = L", if all < T, it holds
?tt = Stab (G++1 F.) (strong stability condition), and V [G |F,1 $ L +
(affinely bounded variance), then it holds
ST - (00(00(()) L*)
t
23
C²0²
C
where Φb u + (1+
a) 2u
for C E [110g 0-11]] E R.+
3n3
- 1T implies E [(0++)) $ L* E, which is rate of (TT31/3) if with additive noise 0² > 0, and O(T-1)
Therefore, T2 2233 (1-
(1+
)) in the case d² 0.
Proof. Define E 100 0-1 and p: + u² //C In order to use Lemma A.5, let us show that E [[ > (E [(0)) L*)) +). By convexity of L and then by Cauchy-Schwart inequality.
((O.) L s VL(O.) (0: - 0*)
B[C(0) - -² s [ E [110, - 0*1
22

---

Using additionally Lemma A.6 to get E [10: 0- < 100 - 1- this concludes the first part of the proof, that E [ 2 ( [(()) -)
For the second part of the proof, apply Lemma A.5, with desingularizer obtained by integration
d o² + (1+
o² (1+
((u)²
0-2wa
C²0²
C
( uu3
+(1 + a) 2u
Bound inversion: the condition to obtain E [[((0++)] & L + with T as a function of s, i.e.
2 T 30380000 A) (1 3)
can be rewritten with as function of T, in the original statement of Corollary A.1, in the form
7
S Φ + (Au) + 23
with -C2o²/3 and b = (1 + a2//2 defining ((u) au 3 + bu This expression can be simplified at y = (Ao) +
T 28
with the intermediate variables p = 3y
6²
and g
24
using
279
+ (v) |
2
3
(22)
V
9
3y
b
(CVX-INV)
This expression of ET 2 (y) any easier use, hence our statement in the other Tg form. Corollary A.2 (Strongly-conve smooth rate).
If C is ptstonngly convex, and for all S. T, it holds V V[G41 |F] S a C< + o² (affinely bounded variance), and T)- 8 Stab (G++1 Fi) (strong stability condition), then holds
A1 S, [[((0++1)] f S Φ- (0(E|C(00) - L*) 23
/
0² 1 1+a
where 4b u+
log(u).
4n,2 u
2y
nn² - A))) (1 + a) log Ao/E). where A. = E [[C(0)) - L", this implies that E[ L- < E. This rate of O(T-1) with additive noise o² and a linear rate O(exp(-xII + +))) for K = p/3 8 in the noiseless multiplicative-nois case σ² = 0.
For 2
o²3
E
Proof. The proof straightforward application of Lemma A.5 with & H> 2pm which satisfies E [[] 2 ( [(6.) - L*1), 1), because by strong convexity of L, it holds for all a E Rd that [+))) (n([(x) L*). It remains to compute the desingularizer & by integration
0² + +1+ (1+()
o² + 2(1 + a))
dΦ(u)
p(u)²
41
o2 1 +
(u))
log(u)
4
2p
Proposition A.3 (Non-convex rate).
If for all t < T, it holds V V[G+ti F.] a al).)( + o² (affinely bounded variance), and
!) = B- Stab (G+41 Fi) (strong stability condition), then writing A [E[(()))] L*, it holds
1
28A0
23 23
E
Σ IIVC(0))
<1
+
T
T
23

---

Proof. Starting from Lemma A.4 (valid by strong stability condition and affinely bounded variance),
1
E B[
((0.) < 2,3 ( (IVL(00)))
where v : u + u+++ (o² (1+a) u) is convex increasing function. Thus, taking total expectations and summing iterates [T] telescope (a), and then using convexity of to bound (b),
23Au
|VC(0)13
E & (IVC(()))))
(4)
where A =
L is the expected initial optimization error. It remains to use the bound (x) (1 0:) x (Lemma A.3), obtain
| ((0))
2(1 +3++)
23
E
VC(0)1
T
T
We thus recover the classical deterministic and stochastic regimes in, respectively, O(1/T) and O(1/ VT) depending whether the additive variance term o² is positive equal to 0.
The same analysis would hold a more general setting in which Stab (G++1 FF) 2 o V(
and x: + <p(x) is a positive, increasing and convex function.
A.2
Estimation of stability ratio
Lemma A.7. Let B > O and (Xz)ie(m) be i.i.d. real random variables such that, for all [n].
holds E X; 0 and X S B almost surely. Then, for any >> 0, we have
ntt
P
Σ vE(x)
x; 2
S exp
(I)
[VIx)
where f(x) (1 /4 if and f(x) x otherwise. (In particular, Vz, f(x) S x)
Proof. Use Fan et al. [2015, Corollary 2.7] with U;-1 B, note that 1 8² [(v[x]/B²* C exactly matches the definition in the reference's notation, thus following the reference and simplifying constants C₁, we get for 2 = Σm= C = nB² f(V[X,)/ B2), that it holds
x
IP
Σ iE(m)
X 22
exp
20
The result follows using nt.
Lemma A.8. Let (Di)ie(n) be non-negative i.i.d. random variables with E [D < too and D2 Rt Then, for D3
E [ 2 E [1, holds
Σ D. < D/2 (E(m)
< <exp (-
n
8k
Proof. Let X; D D,. Observe that E.. [X,] O. and X; < almost surely. Additionally, by expanding the square, V[X.]
[D D2
Apply Lemma A.7 with B = D and f D/2 and use f(x) < 1 + x to simplify the denominator with D2 < 2 + VID.] = E [D.]. Therefore,
nD2
P
Σ iE(n]
D: < D/2
< exp
2E D2
exp
88
D
D2

---

Lemma A.9 (Relative error of stability estimation), Let (X; E )e(()) be iid random variables.
Define J a(n-1) Eips X, Xj E R. Z 1. E. E R4,, then S = oo E [0, 11.
Write μ = E [X] E Rd and 0² = X - 12 and k = E || / If R = || 1 #0. 0.
and n 2 a/ for a constant a 2 1, then
R
2
48 + 1(K 1) +
exp (-
n 8k
E
R
a
R²
At 3 (for centered gaussian) and neglecting the fast-decreasing second term, this is a relative squared error of 56/a, a, i.c. a relative error of order 7.48/ Va, which is below 1 as low as a = 100.
Proof. Let N || and D= E [[]]]]] be the numerator and denominator in N/D. Note
that E []] = N and E. [ D. Proceed then by case disjunction; if on one hand 7 $ D/2, then
|S R 1 1 (both are in [0, 1). while on the other hand 2 D/ 2 then
J N N
1
1
J N
N
2 D
ss - R <
Z R =
+
<
Z
7
D
Z
D
Z
J N
N 2 - DI
J
N|
Z - DI
2R
+
D/2
D (D/2)
N
D
Therefore joining both cases after taking squares,
S
R
N-N N
7 D
2
1
4
+ 1 D/2)
R
D
R²
Hence, after taking expectations and applying Lemma A.12 (numerator sample control) and Lemma A. (denominator variance), it holds for n 2 1 ++ a/R that
S
R
PIZ S D/2) +4 K-1 +
E
S
R
a
n
R2
Additionally, by Lemma A.8, P Z < 2/2) S exp (- 5/
where = E [|IX; [|]] /D2 K. Thus,
S
R
2
8
R(K
1 R22
E
S 4 a
+ 4
exp
R
a
8k
The result follows by using 2 1 and R < 1.
Lemma A.10 (Uncentered kurtosis of isotropic normal distribution). Let X E Rd be random variable with X N11,,²2), It holds E [||]]]] d and E. [|] [ E X 13 d-1
Proof. By expanding the sum,
E
Σ
X?
Σ
E x
= do²
2
E [ = E
x
Σ
E
[xx}]]
i
E
+
Σ
E
X3
= d. 0- + + - l)o*
The result follows by taking the quotient of both. Lemma A.11 (Kurtosis bound for the denominator).
Let (X, E Rd) )ej)) be iid random variables with E
[||||]| = Q. and Z = 1/2
Then
E 2
=
(
_ n
E [[I]]]]
E [1x11]]
E
and thus for K
(uncentered kurtosis of X), it holds P( - Q) > =Q) < n
E X
25

---

Proof of the expectation is just expansion of the square and linearity of expectation. The second proposition is Chebyshev's inequality.
Lemma A.12 (Numerator sample control).
Let (X; E R ke(m) be iid random variables with [[X] = nt, and J I[n-1] Eizs X; X3. If
+ 0 and if n 2 1 c c. E [[|X - -01l]] /llul then it holds
E
J
1
2
4
8
1
This is an immediate corollary of the following lemma.
Lemma A.13 (Variance bound for the Jackknife numerator).
Let (X; E )Eiin be iid random variables with E [ E Rd, and J n(n-1]
Eiees Xi X3.
Then holds E [] = 11 2. and
E
|
[|m]B1]] S
| - m1
8
E
|| -0112] -1111
n(n 1)
n
Proof.
J J-][J] nnn 1)
1
Σ (Xi X3- - -22)
1
Σ
Σ(xx: ((X; 11). (X; 11) + (X; xz)x -2
n(n (nn-)
1)
(F1
E(x: - 14) (X, (x3--1) + +(2( - -1)-
X; 14)
-2n(n - 1)1²
'mn-1 1)
Σ (X, - ()) (X, -M) +2 ( 1 1 - X₁ - 1 11) 1
nann - 1)
B
As sanity check, observe that E [ - E [J]] = 0 because E [A] = 0 and E [B| = 0.
We will use the (crude) bound E [|] - -1313 < 2E A
+ 2E
B2
Let us compute each.
x: (()Exx--))
2 )2
42 < 4 o2 112
E 1 4E
4E
Σ X, H
n2
n
On the other hand, by Lemma A. 14, E [Aa]
< 2E
||X -m13]]
/(n(n - 1)). Thus the conclusion,
E || 111 2
J - 11 21 < 2E [ A2 + 2 B2 <
X 101
||
n(n
1)
26

---

109
VJJERA
10a
100
Measurements
Upper-bound
10-4
10a
10
103
10a
10
10
107
10a
7 N
Figure 10: Empirical measurements of E [ - E [J,, 11 as function of (mean and 5-sigma confidence interval for the mean, 10 samples) vs Lemma A.13 upper-bound. for isotropic gaussians in dimension d = 10 with noise op 10 per coordinate, thus o² doğ = 10 and || d.
Lemma A.14 (Variance of the squared-mean U-statistic).
Let (C₁+ E IR se(n)) be iid random variables with E [[;]] and E [|C]]]]] 0² R4. Define [A < 20
11 Eits C Cg. Then
/eff/nnnn (n - 1)).
This is the usual analysis of variance of U-statistic by intersection disjunction, see for instance the lecture notes Jordan [2007] for Berkeley's 's Stat 210B, or the more conventional reference Asymptotic Statistics [Vaart, 1998]. An empirical verification and tightness evaluation performed in Figure 11.
Proof. Starting from the definition of A
A
ΣΣ (C- Ci) i#j K
n² (n 1)2
Proceed by case disjuction:
if (i (k, 2, then E [[ C2)(C, =)]= Gi 0.
if #(i,5) n ()) 2, then E [C. CC = 0,) and by Cauchy- Schwarz inequality, it holds [CC
S [
C3] S
if #(i.)) (k. 17) = 1, then without loss of generality i = k and j * 1. Therefore
E [[ CC C,) E [(CC C)))))) C, = E (C, C) E [C, = 0
It remains take expectations and count the number of size-2 intersections.
2
[A < n 1)2
Σ 20
n(
itj
10
R+
E
10
A2
10a
Measurements Upper-bound
E
1
10a
10a
103
10
105
106
n neN
Figure 1I: Empirical measurements of A22 as a function of n (mean and 5-sigma confidence interval for the mean, 500 samples) versus upper-bound used in Lemma A.14, for isotropic gaussians in dimension d = 10 with noise do = 100 per coordinate, thus | = o² = d = 10
27

---

B Influence of learning rate parameters (77-scan) on Problem QWC
We present results of all algorithms on Problem QWC at various noise levels, for all learning rate parameters tried in experimental protocol. Flatter lines indicate less sensibility to the hyperparameter, aligned minima indicate ability to tune on short horizons. The smooth standard limit step 3 1 is displayed as vertical dotted line, for all algorithms with smooth claims.
B.1 SGD with constant, scheduled, or stability-adjusted learning rates
(a) SGD: ?
7l
(b) SGD: 1/: 1/b 1/2
(c) Stab-SGD
log10 mean excess loss
+0
+0
-14
-1
10a
-2
-2
10a
-3
-3
-3
10a
10a
-5
-5
-5
10
10
10-4
10-1
10-3
10
10a
10-5
10-2
10
10
10
Base step-size To
Base step-size To
Base step-size no
10
Figure 12: Problem QWC with additive gaussian noise of variance x² d. Excess loss versus base learning rate To E Ri and training time E N.
(a) SGD: 71 170
(b) SGD -t 1/2
(c) Stab-SGD
log10 mean excess loss
+0
+0
-2
-2
-2
10'
-- 10a
-4
-4
10
-6
-6
-6
10a
10
-8
-8
-8
10-7
10-4
10
10-3
10-1
10a
10-5
10
10
10
Base step-size Y7u
Base step-size yo
Base step-size Y/u
10"
Figure 13: Problem QWC with additive gaussian noise of variance o² 10-4 d. Excess loss versus base learning rate yo E Rt and training time T' N.
(a) SGD: 77
(b) SGD: 1/8
TJo
112
(c) Stab-SGD
1o mean excess loss
+0
+0
T
-4
-4
-4
10
-8
-8
-8
10
-12
-12
-12
10
- 10a
-16
-16
-16
10a
-20
-2
-20
10-7
1
10
10
10-1
102
10
10 10-2
10
10
Base step-size п00
Base step-size
Base step-size Tlo
107
Figure 14: Problem QWC with additive gaussian noise of variance o² 10-16 d. Excess loss versus base learning rate Too E R and training time T E N.
28

---

Fig. 12, Fig. 13 and Fig. 14 show evolution of the mean excess loss as function of the base learning rate Vi (before applying any scheduler) and the total training time T E N (a.k.a. "horizon"). The dependence of the optimal base learning rate on the horizon 7 is visible for both SGD with constant learning rate and with 1122 schedule. Additionally, these optimal base learning rates are seen shift between the two figures, when the noise levels vary. particular, this means that the learning rate of mini-batch SGD must be re-tuned if the batch size (i.e. noise level) is altered.
Consistently with other experiments, the optimal learning rates for long horizons (T 2 10") are associated with a long plateau at initialization. This implies that models tuned for long horizons are essentially unusable mid-training (no better than initialization), thus it meaningless an "optimal trajectory". or a horizon- horizon-independent "optimal learning rate"; on the contrary, the horizon plays central role in evaluating the quality of the model. This effect is much less pronounced with Stab-SGD, with little to no movement around the prescribed rate 70 = 3 = 10 across noise levels.
consider
B.2 D-Adapt
We repeat the experiment at multiple noise levels with the D-adapt algorithm, Defazio and Mishchenko [2023, Algorithm 2J. We run the experiment with the hyperparameters D 2 and = 200 separately, and sweep all "learning rates" G-1 for each case.
(a) 0² = d
(b) 0² = -10
(c) 0² 10 d
logın mean excess loss
+0
+0
+0
T
-4
10
-8
10
-12
10a
-4
-16
10
105
-8
-20
10
10
3
10
10
7
10
3
10
10-7
10-3
10a
10
Parameter G-1
Parameter G-1
Parameter G-!
10
Figure 15: Performance of D-adapt algorithm, for = Problem QWC at various noise levels.
(a) 0²
(b) 0² 10 ..
(c) 0² = 10-16.
1o mean excess loss
+0
+0
T
-4
10
0000
-8
10a
-12
10
-4
-16
10
10
-8
-20
10
10
101
10-7
10
10a
10-7
10-3
10a
10
Parameter G-1
Parameter G
Parameter G-1
107
Figure 16: Performance of D-adapt algorithm, for 20000, on Problem QWC at various noise levels.
B.3 "Schedule-free SGD"
We repeat the experiments with the "Schedule-free SGD" algorithm from "The Road Less Scheduled", as it is described the main text: Defazio et [2024, Sec. 2, Eq 3-5], i.e. with hyperparameters 3 0.9 and z-step schedule c 1/(t 1) prescribed in Sec. 2 $2.
29

---

(a) 0
0² 10-4... .d
(c) o² 10010
10g10 mean excess loss
+0
-4
10a
-8
102
12
10a
-4
-16
10
-8
-20
10
10-?
10
10
10-7
10
10
10
10
10
10
Step-size y
Step-size ?
Step-size 7
10
Figure 17: Performance of the "Schedule-free SGD" algorithm, on Problem QWC at various noise levels. We observe saturation at all noise levels, this is inconsistent with the idea that this algorithm can be used instead of scheduler for SGD.
To contrast this with the theoretical predictions in the reference, note that Defazio et al. [2024, Thm only gives convergence (in the Lipschitz model) with the horizon-dependen hyperparameter 7 DT The smooth result Defazio et al. [2024, Appendix Corollary
a time-varying parameter 3r, such as 3 = 1/(5((+1)) (obtained by injecting the bounds on Wi and a, of Corollary into their definition in Thm 5), to guarantee speed ((D2B/T' Do /T), and uses an "optimistic online learning algorithm" for the one given in appendix Sec D. uses a vanishing learning rate.
B.4 COCOB Coin-betting approach
We perform the experiments with the Continuous Coin-Bettiin algorithm (COCOB) Orabona and Tommasi [2017, Algorithm 1], designed for the setting of convex online learning with Lipschitz losses and almost surely bounded gradients. Although this experiment uses smooth losses with gaussian noise (unbounded with finite variance), the performance of both this algorithm and its "Backprop" version more adapted to the non-convex setting remain competitive.
(a) 0²
(b) 0² = 1004..
(c) 0² = 10-16
16
10g10 mean excess loss
+0
T
10a
-8
10a
-4
-12
10a
-16
10a
10a
-8
-20
10-7
10
10
10-7
10
10
10
10-3
10
10
Parameter L
Parameter L-1
Parameter I,
10
Figure 18: Performance of the "COCOB" algorithm, Problem QWC various noise levels. The algorithm uses hyperparameter (L,), E RÇ. which we set identically for all directions for this experiment, this being the only reasonable choice without canonical basis.
As observed in Fig. 18, the alignement of the optimal hyperparameter across training horizons is excellent, despite the mismatch settings (Lipsehitz objective in the theory, versus quadratic loss in the experiment, which is uniformly 1-smooth but not Lipschitz on the entire domain). The value of the limit learning rate however is perhaps not so intuitive, since is no longer directly linked to 8-1
Fig. 19 shows the results of COCOB-Backprrgg Orabona and Tommasi [2017, Algorithm 2].
30

---

(a) 0
(b) 0² 10 .
(c) o² 10011
log10 mean excess loss
T
10
-8
10
Loof Boo00000
00g o
-12
10a
10
-4
-16
10
-8
-20
10
10
10
10
10
10
10
10
10a
10
10
Parameter a
Parameter a
Parameter a
Figure 19: Performance of the "COCOB- "aCCk--Bakpprpp algorithm. on Problem QWC at various noise levels. The vertical line depicts the default value (a 10+2) suggested to make this algorithm completely "parameter-free" (in sense that has no parameters to tune).
The sensitivity the hyperparameter is essentially non-existant except near the initialization. The performance does not quite match that of SGD. For instance at x² = 10 10-16 16 d. SGD (both constant- step and 1 scheduled reach 10 17 after 107 iterations (cf. Figure 14), while COCOB- -aakk-pppppopppp reaches only 10-15 The observation of such gap on single problem does allow general conclusions on the behavior of the algorithm (usually evaluated only in worst-case performance) but remains marginally informative. The gap in performance was apparent Problem QSC.
C ResNet Training Experiments
Methods (additional details), Consistently with original experimental protocol al. [2015a, Section 3.4), we use the initialization taken from He et al. [2015b], also known as "Kaiming" initialization. This explains in particular the large initial loss, due to large values in the last layer at initialization under such scheme. Since the number of samples is not perfectly divisible by the batch size, our last batch in each epoch is smaller, we do not use a multiplicative correction for this altered size. We present in the following pictures results over 20 random seeds. Since in those twenty essentially failed to train (loss nearly stalled at initial value), we present median and quartiles for error bars instead of means, which are less sensitive to large but rare values.
C.1 Loss and accuracy across multiple runs (full scale)
103
Algorithm [oracle]
10a
Algorithm [raw]
SGD [original]
10
Train Loss
100
10-1
10
10
0
2
3
5
6
8
9
10
11
12
Iteration
.104
Figure 20: median (and quartiles as error bars) of the training loss as function of iterations.
31

---

100
Algorithm 1 [oracle]
90
Algorithm I [raw]
SGD loriginal]
Test Accuracy (%)
80
70
60
50
40
30
20
10
6
10
12
Iteration
-104
Figure 21: Median (and quartiles as error bars) of the test accuracy as a function of iterations.
C.2 Stability ratio along trajectory, and kurtosis estimations
Fig. 22 shows the Stability Ratio and estimated kurtosis of gradients along the trajectory. Except for one run with very high kurtosis (> 40), all observed values are below 10 for most of the trajectory, leading to error of 44 4x s 84 (Lemma which is below our choice of Ç 100.
Stability ratio
Kurtosis
10
10a
Kurtosis estimation
Stability Ratio
10 10-1
10
10
10-3
10
10 10-4
10a
103
10
105
10a
103
10
10a
Total iterations
Total iterations
Figure 22: Stability ratio and kurtosis along trajectory (10 random seeds).
32


Reviews:
[{"review_id": "CsCvTSBltB", "reviewer": "Reviewer_2Qgz", "summary": "This paper proposes a new optimization algorithm in the smooth, stochastic setting which adapts to the noise distribution of the gradient estimates using the notion of the ``stability ratio,\" avoiding the need for setting the learning rate as a hyperparameter. For a random variable $X$, the stability ratio is defined as $Stab(X) = \\frac{||\\mathbb{E}[X]||^2}{\\mathbb{E}[||X||^2]}$. Given this definition, they propose the Stab-SGD method which employs the update $\\theta_{t+1} = \\theta_t - \\frac{1}{\\beta} Stab(G_t) G_t$ where $G_t$ is the stochastic gradient estimate and the objective is $\\beta$-smooth. Given oracle access to the stability ratio, they derive convergence rates for convex, strongly convex, and non-convex settings. They then propose an estimator for this stability ratio given i.i.d. samples and analyze its error. For this estimator, they propose an algorithm for implementing Stab-SGD on real data. They compare its performance relative to other learning-rate-free algorithms on synthetic quadratic loss functions and also perform a comparison to SGD for training a neural network on CIFAR-10.", "questions": "1. Is there any convergence analysis for the practical variant?\n\n2. Is there a setting where Stab-SGD provably or empirically beats other methods convincingly?\n\n3. Can the authors compare the convergence rates in Table 1 to other methods which operate under similar assumptions?", "limitations": "The authors mention some limitations but do not discuss the practicality of the stability oracle access assumption or the downside of the additional hyperparameters introduced to estimate the stability ratio in real data settings without this oracle access.", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe Stab-SGD successfully removes the dependence on a learning rate hyperparameter when given access to a stability oracle and only requires setting a hyperparameter relating to the smoothness of the objective. Further, the effective learning rate adapts to the noise of the gradient estimates, avoiding the need for an explicit learning rate scheduler. The theoretical convergence analysis given the stability oracle seems correct and the results are clearly presented. \n\nWeaknesses:\n\nThe Stab-SGD method is primarily motivated as a way to eliminate additional hyperparameters such as the learning rate and learning rate schedule in a way that adapts to the gradient noise. In the theoretical setting, even given access to the stability oracle, the Stab-SGD method still requires knowledge of the smoothness parameter. Further, the practical variant that estimates the stability ratio from gradient queries requires many additional hyperparameters which set the initial learning rate, frequency of stability estimates, and number of gradient queries per stability estimate. Thus, the Stab-SGD method ultimately still requires setting many hyperparameters, which is contradictory to its original motivation.\n\nThe theoretical contributions focus on the setting where there is oracle access to the stability ratio of the stochastic gradients. This assumption is unrealistic and there is no convergence analysis of the proposed practical method which estimates the ratio from gradient queries. They provide error bounds for the finite sample stability estimate, but the impact of this error on the convergence is not analyzed.\n\nLastly, Stab-SGD does not seem to improve upon other schedule-free methods or SGD in either of the synthetic data or CIFAR-10 experiments, so the practical significance appears limited.", "was_revised": true, "final_justification": "As I wrote in the discussion, I have the following concerns.\n\nFirstly, there is a large gap between the algorithm for which this paper derived convergence rates (using the stability ratio) and Algorithm 1. If the stability ratio is updated in every iteration, the new theoretical statement the authors proposed in response to my comments (convergence rates with high probability if the stability ratio is approximated well enough) together with the approximation result in Lemma 1 is a step in the right direction. However, we are not able to verify the details of the proposed statement and the corresponding proof. \n\nMoreover, the general form of Algorithm 1 does introduce new hyperparameters, which is counterproductive to the overall aim of the work.\n\nThe use and analysis of stochastic step-sizes itself is not a novelty or a major technical difficulty. It is standard practice e.g. in Reinforcement Learning. \n\nEven taken into account the comments the authors regarding hyerparameter training budget, I still believe the numerical experiments are not convincing especially compared to the author parameter-free algorithms. \n\nTherefore, I believe the paper has two main contributions:\n\n1. It starts a discussion on noise-adaptive learning rates.\n2. It presents an algorithm (when having access to the stability ratio) that adaptively chooses a constant learning rate for situations with asymptotically degenerate noise and a decaying learning rate for situations with noise.\n\nI think this is a strong idea, but I am hesitant to recommend acceptance due to the limitations of the work.", "rebuttal": "Thank you for time reviewing this submission.\nAs you noted, the purpose of this modification to the SGD algorithm is the\n*adaptivity to noise* with *last-iterate guarantees*.\nThere was (until the work presented here) no guarantee that such a strong property was even possible.\nThis is why general practice in deep learning is to tune both a learning rate (related to the smoothness),\nand a schedule (to account for higher noise requiring smaller steps).\n\nTherefore, we still require knowledge of the smoothness parameter, because that is not the parameter\nwe aim to gain adaptivity on, we are focusing on the noise parameter.\nWe also do not claim that the presented practical algorithm (Alg 1) doesn't have any hyperparameters,\nor that should\nimmediately be used in place of other optimizers in production.\n\nOur theoretical contributions demonstrate that *is indeed* possible to achieve adaptivity to noise\nwith last-iterate algorithms. This is a model much closer to what is sought in practical implementations\nthan the typical average-iterate guarantees used in parameter-free algorithms.\nIn order to push the research on adaptivity in this direction, we believe it is important\nto publish these developments, which will constitute the building blocks of a theory of last-iterate\nalgorithms with good adaptive properties and fewer parameters.\n\nThis new type of guarantee is desirable because noise is present in deep learning and last-iterate algorithms are the standard. Furthermore, we demonstrate feasibility of these guarantees by highlighting the central notion of stability ratios.\nWe show that this variant (with stability oracles) provably outperforms other algorithms in the adaptive setting.\nFor a concrete example, consider a strongly convex objective with unknown noise level.\nIf the learning rate is chosen regardless of noise as $\\eta_0 t^{- \\alpha}$, then\n$\\alpha = 0$ will yield bad performance on strictly positive noise (saturation) and $\\alpha=1/2$\nwill yield bad performance on null noise (stalled due to learning rates too small), while\nStab-SGD is a unique algorithm achieving both of the rates described in Table 1,\nit is therefore an *adaptive* algorithm outperforming a *tuned* alternative in which\n$\\alpha$ has to be tuned on each new problem depending on whether there is noise or not.\nTo highlight why this distinction between noisy and noiseless is non-trivial,\nconsider a large neural network at initialization with large batch sizes.\nInitially, all gradients will tend to point in the same direction, thus the setting is essentially\nnoiseless and one should choose the largest non-exploding step-size (characteristic of deterministic settings).\nHowever as training\nprogresses the noise will become more apparent, and thus the setting will become essentially noisy, with\na step-size required to decrease. Because we cannot predict the threshold at which this switch will occur,\nwe must perform expensive experiments with various decrease-horizons. An ideal noise-adaptive\nalgorithm would eliminate the need for this expensive tuning, which is why we believe this to be a fruitful\nresearch direction, hence the proof of concept of a noise-adaptive last-iterate algorithm presented here.\n\nWe do not claim that the stability oracle is \"realistic\" in any way, rather we use it as a stepping\nstone for this new adaptive setting, by showing how *any (present or future) stability-estimator*\ncan be used to construct an adaptive algorithm.\n\nThis new kind of guarantee with stochastic step-sizes (because $\\eta_{t+1}$ depends on $X_t$ which is random)\nposes new technical challenges. We show how to overcome some of them, going up to convergence bounds\nin expectation, by leveraging new analysis techniques (KL integrations).\nHowever, the analysis of the practical variant (Alg 1) will pose even more new technical challenges,\nessentially because stability-estimation errors could \"compound\" in non-trivial ways,\nwhich is not something easily handled with the\nusual tools of convergence bounds in expectation, and will likely require the introduction of new tools.\nThis is in our opinion all the more reason to share our progress on the technical challenges that\nwe have already solved, so that others may build upon it to construct new analyses and better estimators,\nto get us closer to production-ready adaptive algorithms and guarantees closest to existing practice."}, {"review_id": "552LxfHkxw", "reviewer": "Reviewer_SUNZ", "summary": "The authors propose a quantity called “noise stability ratio” that helps them design a noise-adaptive version of SGD, Stab-SGD, that is highly robust to noise without tuning the learning rate. The noise stability ratio ranges from 0 to 1, where it is closer to 0 when the noise is high and 1 otherwise.\nAn efficient estimator for the noise stability ratio is provided as well, and the experiments show robust performance on synthetic problems emphasizing noise, strong convexity, and smoothness.\nSpecifically, Stab-SGD simultaneously performs well on strongly convex problem with low noise and smooth problems with high noise.\nExperiments on ResNet-56 on CIFAR-10 show promising results as well.\nThe authors complement their algorithm with a last-iterate, horizon-free convergence analysis.", "questions": "- Figure 1 shows that Stab-SGD shows good balance, but so is the sqrt(1/t) schedule.\nIn Figure 2, the authors mention high sensitivity to initial leaning rate, but I don’t see that for the sqrt(1/t) schedule.\nCould the authors clarify this point?\n\n- The stability ratios in Figure 22 highly varied trajectories with a downward trend. The downward trend might seems understandable as the noise becomes more significant near the optimum, but why is it highly varied in the middle? I think it would be interesting if the authors can provide an explanation.\n\n- Does Stab-SGD work with momentum?\n\n- line 66: what is “not identically null”?", "limitations": "None.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nThe authors show that Stab-SGD shows “no plateau, no explosion, no saturation”, which is difficult to achieve on the the two extreme ends of problems considered (QSC and QWC) without hyperparameter tuning.\n\nThe first paragraph in Sec 4 is interesting and I agree with it. It is often good to report those hyperparameter tuning budget, particularly for papers proposing a new optimization algorithm.\n\nFigures 3 to 6 are very informative about how parameter/schedule-free algorithms compare on two regimes: strong convexity + low noise vs. smooth + high noise. Stab-SGD does show robust and stable performance on both problems with $\\\\eta = 1. This is one of the strong points of this paper. (The experiments also interestingly reinforce COCOB-backprop’s position as a powerful parameter-free algorithm, especially Figure 19).\n\nThe authors provide last-iterate convergence results using a general theoretical framework and provide rates for smooth, strongly convex, and non-convex problems. I have only skimmed the proof due to time constraints. I’m not very familiar with some of the proof techniques used here, e.g., the KŁ stochastic integration lemma, but I understand that it generalizes the PŁ condition. I will review the proof in more detail later and make any amendments as necessary.\n\nThe usage of Jackknife estimator is an interesting contribution in this context. It is an efficient way to estimate the noise stability ratio.\n\n\n**Weaknesses**\n\nI think one of the weak points of this paper is the clarity of writing.\nFor example, the intro, while very informative, could do with smaller sentences and clearer phrasing and style. For example, an open paranthesis that extends from line 40 to line 46 is not easy to digest. Another example is the last sentence in line 48, which is not written in a natural way. The sentence “lack of [X] is supported by lack of [Y]” is difficult to digest since “lack of” is a negation, and the filler sentences make it even more difficult to parse (reminding me a little bit of Bertrand Russell’s writing).\n\nRegarding the last paragraph in Sec 3, starting at line 186: this paragraph tries to justify the practical design of the estimation overhead control parameters. However, this control introduces three extra parameters that might not be as intuitive to the user as, say, momentum. Also, trying to choose $\\\\kappa$ and $\\\\alpha$ has an ironic parallel to choosing $\\\\eta_0$ and $\\\\alpha$ in $\\\\eta_0 t^{-\\\\alpha}$, especially given the fact that $\\\\eta_0 t^{-1/2}$ performs very well on both the QSC and QWC problems. The authors might argue that their parameters do not require careful tuning and can be adapted in a short horizon.\nThis is true, as can be seen from the experiments, but so are the parameters of $\\\\eta_0 t^{-\\\\alpha}$, as $\\\\alpha$ is usually one of 0, -1/2, or -1, and $\\\\eta_0$ is then relatively easy to tune in the short horizon. This can also be seen in the experiments. In practice, we simply choose the largest $\\\\eta_0$ that doesn’t blow up. The experiments in Appendix B also support this argument (except Figure 14 maybe).\n\nIn addition to the above, the edge cases of the control parameters that the authors—perhaps correctly—describe as harmless and easy to tune might not necessarly be so in real-world problems, unless the authors can demonstrate that to be the case on a wide range of problems. The introduced parameters do remind me of the warmup and exponent hyperparameters in the “schedule-free” algorithm by Defazio et al., which they tout as a minor warmup trick (but they did show competitive performances across a much wider range of real-world tasks, albeit with some learning rate tuning).\n\nPerformance on CIFAR-10 is not very promising in my opinion. It seems to require more gradient calls in order to achieve similar performance to SGD. I was hoping for the algorithm to give at least similar performances to SGD in the longer run, if not better. The algorithm also shows a sudden drop in test accuracy at some point after 2x10^4 steps and very high variance in Figure 21.\n\nline 824, the authors mention the following: \"this means that the 824 learning rate of mini-batch SGD must be re-tuned if the batch size (i.e. noise level) is altered.\"\nThis is not necessarily true. The noise introduced from mini-batching is very different from Gaussian noise. I cannot exactly recall the paper, but the learning rate can be set to be linearly proportional the batch size (or its square root). In general, some rules of thumb in practice are quite effective, so the need for full grid tuning is definitely not necessary for ERM problems.\n\nUnfortunately, the authors did not share the code for the experiments.\n\n**Minor**\n- In line 139, is J_n the same as the numerator of the equation in Definition 3? If so, the notation should be consistent.\n- I believe Sec 1 should be intro.\n- Last paragraph in Sec 3: “caracteristic”, “caracteristisation” -> “characteristic” and “characteristisation”.\n- Lines 144-145: What is $\\\\zeta$? And line 153: What is $\\\\alpha$? If these are the control parameters, then they should be defined before they are introduced.\n- Lines 144-145: Also, could you please clarify what you mean by the last sentence?", "was_revised": true, "final_justification": "This direction of research deserves more attention, as the authors have mentioned. I believe this work is an interesting contribution, regardless of the immediate practicality of the proposed algorithm in production-grade models. It will allow other researchers and practiioners to build on it and design better noise-adaptable algorithms. I disagree with the reviewers that say that estimating the stability ratio is inefficient or that an oracle for this quantity is a strong theoretical assumption. The authors provided an efficient estimator of this quantity, and using more gradient oracle calls per step to estimate some quantity can sometimes be better than using them directly for descent (one example from the top of my head is AdaHessian).", "rebuttal": "Thank you for your time reviewing this submission.\nWe will heavily edit all introductory paragraphs to shorten sentences and improve clarity.\nWe have also noted your various editing comments, and fixed the misspellings and lacking\ncontext on the jacknife numerator $J_n$, sample overhead $\\zeta$ and multiplicative noise level $\\alpha$.\nL145 now reads: \"The kurtosis $\\kappa = \\mathbb{E}[\\lVert X \\rVert^4] / \\mathbb{E}[\\lVert X \\rVert^2]^2 = 1 /\\operatorname{Stab}(\\lVert X \\rVert^2)$ is a property of a random variable quantifying the number of samples\nneeded to estimate the variance. Variables with low kurtosis have empirical estimates of the variance close\nto their true variance, whereas variables of high kurtosis require many more samples for accurate estimations\nof their variance\". The \"$G$ not identically null\" assumption has been reworded to \"$\\mathbb{E}[\\lVert G \\rVert^2] > 0$\", which is simply there to avoid a variable $G$ almost surely equal to zero, which would have undefined stability.\n\nContrary to your first intuition, we believe the results on CIFAR-10 to be promising, for the following\nreason.\nAs you have noted, typical practice in early step-size tuning is simply to pick the largest\nparameter which does not blow up, which is a behavior typical of deterministic scenarios (or negligible noise).\nThis choice is supported by Figure 14 (low noise $\\sigma_0^2 = 10^{-16}$) for the first $10^5$ iterations.\nHowever, as you have also noted two paragraphs down, neural networks also encounter at a later point\na noisy regime, where dividing a batch size by four requires halving the learning rate.\nThis noise-dependent intuition is supported by the fact that using $b \\in \\mathbb{N}$ samples of\nvariance $\\sigma^2$ leads to a batch-average of variance $\\sigma^2 / b$, therefore the prescripted\nhorizon-dependent learning rate $\\eta_t = C \\sigma^{-1} T^{-1/2}$ scales like $b^{1/2}$.\nAs an aside, note that this is not supported by Fig 12-13, where SGD at $10^5$ iterations has optimal\nlearning rate going from $10^{-4}$ to $10^{-3}$ (one order of magnitude) despite a variance $\\sigma^2$ divided\nby $10^4$ (two orders of magnitudes in standard deviation $\\sigma$), so this is really a rule of thumb\nnot an analytical optimum, valid in some restricted settings and requiring more theory in others.\nThe transition between these two noiseless and noisy regimes happens at $T=10^1$ in Fig 13, but at $T=10^5$\nin Fig 14 with lower noise. In neural networks, it may mean that the first 100 epochs are essentially noiseless,\nbut that after that the noisy learning-rate adjustment must be performed.\nIdentifying the threshold at which this switch occurs, and adjusting the learning rate of the later part,\nwill surely require several training runs, say $k \\in \\mathbb{N}$ (with the intuition that $k \\approx 10$).\nOn Fig 7, without any late-horizon finetuning requiring full retrains, Alg 1 reaches the same (and even better)\ntraining loss in $12 \\cdot 10^{4}$ iterations than SGD *with a scheduler* did in $6 \\cdot 10^4$ iterations.\nThis means that using this algorithm would have given better results as long as $k > 2$.\nBecause we do not believe this scheduler was identified using less than two training runs,\nthis means that when accounting properly for *all* training and tuning costs, and not just the single\nrun presented, a noise-adaptive algorithm would have given better results at equal budget.\nIt is not necessary for Stab-SGD to outperform SGD on a single isolated and already-tuned training run,\nthe value of such adaptive algorithms would be in curbing the total training cost, by requiring less tuning.\n\nNote that this intuition also gives a hopeful answer to the question of new hyperparameters introduced in\nAlg 1 to estimate the stability ratio. Compared to using $\\eta_0 t^\\alpha$ with three full runs $\\alpha \\in \\{0, -1/2, -1\\}$ (and presumably many more to tune $\\eta_0$ separately in each case), if the parameters of Alg 1\ncan be roughly guessed with a rule of thumb (e.g. 10\\% of budget allocated to stability estimation),\nthen the adaptive algorithm will outperform a tuned version with equal tuning budget.\nWe agree that the introduction of these hyperparameters in Alg 1 is unfortunate, and would not be satisfactory\nfor a production-grade deployment. However, we believe that they will serve as a useful hint\nto experienced practitioners to improve upon this first proposition and eventually match Stab-SGD performance\nwith little to no new hyperparameter tuning. Thus the benefits of introducing these hyperparamters in this\nsubmission outweigh the slight unease caused by the similarity to scheduling parameters, because the\nlower sensitivity to stability-estimating parameters will make it easier to erase their presence, be it\nby good rules of thumb or by future parameter-free alternatives.\n\nRegarding your questions,\nwe leave the question of noise-adaptive last-iterate algorithms with momentum as an open problem for the moment.\nThe major difficulty in extending this analysis to momentum will likely be the handling of the interaction\nbetween past gradient samples and current gradient, because there is not only noise in past gradients, but\nalso a difference between past and current gradients that is unknown and controlled only by the smoothness.\nWe also leave the question of the non-monotone stability ratio open for the time being,\nwe provide this data mostly to disprove the quick intuition of a constant noise and strictly decreasing\ngradient magnitude, justifying more studies of stability estimation along trajectories.\nThe sensitivity of the power schedule $\\eta_t = \\eta_0 t^{-1/2}$ to hyperparameter choice is best\nseen on Fig 2b, where although the same asymptotic rate is achieved (the same slope), the values\nattained at $10^8$ iterations depend on the particular choice of hyperparameter, and several are\nno better than SGD tuned at horizon $10^7$."}, {"review_id": "OUuGKQVTjY", "reviewer": "Reviewer_hYFS", "summary": "This paper proposes modulating step sizes with a measure of signal-to-noise of the gradient.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "This paper has an interesting ideas. I like the comparison against various other methods in the last-iterate analysis setting. The use of online estimates of the stability ratio seems sensible, particularly the jackknife estimate. \n\n- The stability ratio appears to be a signal-to-noise estimate. Some discussion of this would be helpful. Is there existing literature using SNR estimates to correct the step size? I did some quick googling and found the following two papers, which are related but not an exact overlap:\nhttps://openreview.net/forum?id=TKXMPtCniG&noteId=utYnKNrXWv\nhttps://www.sciencedirect.com/science/article/abs/pii/S0167865524002629\n\n- I appreciate the large set of methods compared against in the experiment section, it's good to see a comprehensive algorithmic comparison.\n- Line 39 \"On the contrary, there is growing evidence that such aggregation is unnecessary\": I wouldn't really agree with this statement. The Schedule-Free algorithm that is shown to work very well in this papers experiment section actually does use averaging, together with an additional layer of momentum that fixes the poor performance of standard Polyak averaging. The theory of \"Optimal Linear Decay Learning Rate Schedules\" (Defazio et. al. 2023) is a good counter-point though, showing that in some cases averaging can be replaced with linear decay schedules without sacrificing convergence rate guarantees. Perhaps this statement could be expanded and qualified?\n- The experiments suggest that estimating the stability ratio well is difficult particularly as you approach the optimum. I think this is the main limitation of this line of work. \n- I don't understand the D-Adapt results, doesn't it set D automatically, so what are the indicated D values in the legend?\n- Theory results are clear and well-stated, and placed within context.", "was_revised": true, "final_justification": "Based on other reviews and rebuttals, I standby my assessment.", "rebuttal": "Thank you for your time reviewing this submission.\nIndeed, the stability ratio is directly related to a signal-to-noise ratio, but remains well defined\nand finite when the noise vanishes, which eases all statements of convergence.\nThe idea of reweighting learning rates using noise estimations seems intuitive, but underdeveloped\nin the community, possibly because getting a provably-good reweighting comes with many theoretical challenges.\nPreviously,\nSchaul \\& Zhang \\& LeCun (2012) \"No more pesky learning rates\" proposed\nto use hessian estimates reweighted by a coordinate-specific noise estimation,\nbut the algorithm did not gain traction in the following decade, and the original\nwork proposes no convergence analysis.\nThe first reference (Guo-Qing, Jinlong , Zixiang, Lin, Wei [2023])\nuses a signal-to-noise ratio $\\lVert \\mu_i \\rVert_2^2 / \\sigma_i^2$,\nnormalized and capped to sum to one, so it is not a variation of the total learning rate\nbut a relative variation of learning rates in each dimension,\nwith the aim of getting better generalization. Since it is also essentially undefined as $\\sigma$ approaches zero,\nand proposes no theoretical guarantees of any kind,\nwe consider it unrelated to the topic of noise-adaptivity in optimization.\nThe second reference (Min, Shupeng, Taihao, Huai, Xiaoyin [2024]) tackles the issue of generalization\nerror in image deblurring, where the candidate image is seeked with low cross-correlation with the\nblur-induced noise, which is also a topic we consider far removed from the optimization guarantees seeked here.\nHowever these two works stress the idea that noise-related automatic adaptations of the learning rate\nare intuitive ideas that would be supported by the machine learning community if they came\nwith trustworthy adaptive algorithms.\n\nTo clarify our problematic sentence regarding \"unnecessariness\" of aggregation, we do not claim that averaging method never give good performance,\nbut rather than many non-averaging methods give good results. In that sense, averaging is clearly\nnot mandatory, and non-averaging methods have become the de-facto standard in deep learning.\nThis claim is supported for instance by the GPT3 training, which uses Adam without averaging\n[Brown et al, 2020, Appendix B p43], and the\nMuZero training, which uses a momentum version without averaging [Schrittwieser et al, 2019, Ancillary file \"pseudocode.py\", L553], presumably identical to its predecessors AlphaGo and AlphaGoZero.\nIf networks of that scale and impact work without requiring iterate averaging, then the theory of machine\nlearning should try to cover these algorithms, to better explain and predict their performance.\n\nWe have changed the notation of the hyperparameter in $D$-adapt from $D$ to $d_0$ for clarity,\nit is the same hyperparameter used in the original reference, which functions as a \"guess\" of the\ntrue distance $D$. The purpose of $D$-adapt is to reduce sensitivity of the algorithm to the precise\nchoice of this guess, hence the \"adaptivity\" when this sensitivity vanishes.\n\nReferences:\n- Brown, Mann, Ryder, Subbiah, Kaplan, Dhariwal, Neelakantan, Shyam, Sastry, Askell, Agarwal, Herbert-Voss, Krueger,Henighan, Child, Ramesh, Ziegler, Wu,  Winter, Hesse,  Chen, Sigler, Litwin, Gray, Chess, Clark, Berner, McCandlish, Radford, Sutskever, Amodei (NeurIPS 2020) - \"Language models are few-shot learners\"\n\n- Schrittwieser, Antonoglou, Hubert, Simonyan, Sifre, Schmitt, Guez, Lockhart, Hassabis, Graepel, Lillicrap,  Silver (2019) - \"Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model\", Ancillary material \"pseudocode.py\" (https://arxiv.org/src/1911.08265v2/anc/pseudocode.py)"}, {"review_id": "O3akV5w5PO", "reviewer": "Reviewer_aGBz", "summary": "This work considers hyperparameter-free stochastic optimization for smooth loss functions. The authors propose to use the signal-to-noise ratio for the gradient oracle to derive an appropriate adaptive learning rate that ensures a decay in the loss function in expectation. Under the assumption that the so-called stability ratio is known at each point, the authors give convergence rates for $\\beta$-smooth loss functions that are convex, strongly convex and non-convex, respectively.  The derived rates are comparable to those found for SGD with decaying learning rate schedules. Numerical experiments are presented that compare the performance of the proposed variant of SGD to other schedule-free algorithms.", "questions": "- In the convex setting, the convergence rate derived in this work matches the rate given in Bach and Moulines (2011). In line 124, the authors claim that this rate is conjectured to be the optimal horizon-free last-iterate rate for SGD with schedule $\\eta_t=\\eta_0 t^\\kappa$. However,  Theorem~3.1 in Liu,Zhou (2024), Revisiting the last-iterate Convergence of Stochastic Gradient Methods, appears to improve this rate to $O(\\log(T)/\\sqrt T)$.  Could the authors clarify their statement?\n- I am wondering why the bounds in Theorem 1 and Theorem 2 are presented in a different way compared to the bounds in Theorem 3. As far as I understand, since the learning rate does not depend on the time horizon, it would be possible to give an upper bound for the optimality gap in terms of the current iteration number $T$, as it has been done in Theorem 3.\n- It would be interesting to analyze how using the same gradient estimates for both the learning rate and the descent direction would change the dynamics of Stab-SGD. Can the convergence results be recovered in these settings with dependencies between the learning rate and the gradient estimate?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThe paper is written in a clear and concise way. Adapting the learning rate to the noise intensity is a nice idea which allows to present a framework for convergence of SGD without using a decaying learning rate schedule. In fact, the proposed learning rates adapt to the asymptotic noise regime. For vanishing noise at the minimum the learning rate does not vanish in the limit, allowing Stab-SGD to achieve linear convergence. For non-vanishing noise the stability ratio and, thus, the learning rate converges to $0$, recovering the $O(T^{-1})$ convergence rates for SGD with decaying learning rate schedule. \\\n\t\n**Weaknesses:**\nThe stability ratio is a theoretical object and has to be approximated in practice using Monte Carlo simulations, requiring more gradient oracle queries. It is not clear how the estimation of the stability ratio and the convergence of the Stab-SGD algorithm interact, since the theoretical guarantees are presented under the assumption that the exact stability ratio is used for the learning rates. Moreover, it seems inefficient to generate estimates of the gradient for adapting the learning rate and then sample new, independent gradient estimates for determining the descent direction. The numerical experiments are not convincing, so that the contribution of this work is rather theoretical than practical.\n\n\nSome minor remarks are listed below: \n- Line 75: It should be assumed that $G$ is unbiased.\n- Lemma A.6: Convexity of $\\mathcal L$ should be stated as an assumption in the lemma. \n- Corollary A.1: The definition of $\\Delta_0$ should be recalled.", "was_revised": true, "final_justification": "Overall, I agree with reviewer 2Qgz in his main criticism. Firstly, there is a large gap between the algorithm for which this paper derived convergence rates (using the stability ratio) and Algorithm 1.\n\nIf the stability ratio is updated in every iteration, the new theoretical statement the authors proposed in response to my comments (convergence rates with high probability if the stability ratio is approximated well enough) together with the approximation result in Lemma 1 is a step in the right direction. However, we are not able to verify the details of the proposed statement and the corresponding proof. \n\nMoreover, the general form of Algorithm 1 does introduce new hyperparameters, which is counterproductive to the overall aim of the work. \n\nThe use and analysis of stochastic step-sizes itself is not a novelty or a major technical difficulty. It is standard practice e.g. in Reinforcement Learning. \n\nEven taken into account the comments of reviewer SUNZ and the authors regarding hyerparameter training budget, I still believe the numerical experiments are not convincing especially compared to the author parameter-free algorithms. \n\nTherefore, I believe the paper has two main contributions:\n- It starts a discussion on noise-adaptive learning rates.\n- It presents an algorithm (when having access to the stability ratio) that adaptively chooses a constant learning rate for situations with asymptotically degenerate noise and a decaying learning rate for situations with noise.\n\nI think this is a strong idea, but I am hesitant to recommend acceptance due to the limitations of the work. Therefore, I am keeping my score.", "rebuttal": "Thank you for your time reviewing this submission and for the excellent reference that we had missed.\nWe have updated the corresponding literature review to reflect the new state of non-adaptive last-iterate\nrates. Indeed, by using not just the power scheduler $\\eta_t = \\eta_0 t^\\alpha$ but instead\na capped $\\eta_t = \\min(1/\\beta, \\eta_0 t^\\alpha)$, the authors break past the conjectured $T^{-1/3}$ rate.\nUnfortunately, the two rates presented in the weakly and strongly convex case do not use directly coinciding\nstep-sizes, so there is little hope of re-using the analysis tools presented in this adaptive case.\nTherefore, the task of adaptively matching their improved $\\log(T) / \\sqrt{T}$ last-iterate rate\nwhile maintaining fast convergence on strongly convex problems will remain an open problem for the time being.\n\nAs you have noted, the new theoretical framework we present allows handling stochastic step-sizes\n(because $\\eta_{t+1}$ depends on $X_t$ which is random), but leaves unanswered the question of\ninteractions between the ratio estimation and choice of direction.\nFor the practical variant (Alg 1) we have chosen to discard gradient samples used for the stability estimation,\nprecisely to minimize this interaction, we thus do not consider this an inefficiency but a safety measure.\nThis could be improved by future works, for instance by demonstrating (by a new analysis) that the interaction\nbetween these two components can be controlled.\nWe believe that the new techniques presented here to handle the stochastic step-size in a noise-adaptive manner\nwill be a strong building block for future theories tackling these interactions, justifying the publication\nof these proof techniques and the possibility of noise-adaptivity that they demonstrate.\nNote as well that if the stability estimation is seldom updated, then the effect of discarding these samples\nfor the choice of descent direction is negligible.\n\nWe have updated the appendix to reflect both versions $T \\leq f(\\varepsilon)$ and $\\varepsilon \\leq g(T)$\nfor theorems 1, 2, and 3. As you observed, they are strictly equivalent, and choosing one or the other is only a matter\nof whether one prefers using the simple function $f(u) = a u^{-3} + b u^{-1}$\nor the less easily-expressed $f^{-1}$ function in the bound.\nWe have also fixed the missing clarifications on unbiased-ness, use of $\\Delta$ and convexity rightfully noted."}]

Author rebuttal:

Meta-review: This paper proposes using the stability ratio of the stochastic gradient to adaptively adjust the stepsize in SGD to the noise level. Assuming access to a stability oracle, the authors derive last-iterate convergence guarantees for weakly convex and strongly smooth convex problems with horizon-independent stepsizes, as well as best-iterate rates for the non-convex smooth setting. They also introduce a practical variant, Stab-SGD with the Jackknife estimator, though no theoretical analysis is provided for this version.

The reviewers were divided after extensive exchanges with the authors and among themselves:

- **Reviewers hYFS and SUNZ** expressed strong support for the paper.
- **Reviewers 2Qgz and aGBz** recommended rejection, primarily due to the gap between the theoretical results and the practical implementation.

Despite this gap, I find the central idea novel and of significant interest to the community. Moreover, the demonstration of last-iterate, schedule-free convergence in stochastic settings represents a non-trivial and meaningful contribution. While the practical variant lacks theoretical backing, the idealized version of Stab-SGD comes with strong guarantees, and the authors convincingly explain how it can be approximated in practice, supported by promising empirical evidence.
Decision: Accept (poster)