Pith. sign in

REVIEW 2 major objections 4 minor 6 references

Adaptive step sizes stay stable because their variance saturates

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 02:42 UTC pith:ZQNPQL23

load-bearing objection Stability-index bound is a genuinely useful lens on why SPS/SPP ride out large step sizes; the NGN theorem-level claim is real overreach because (A2) fails for the nonsmooth losses the paper advertises. the 2 major comments →

arxiv 2602.09842 v2 pith:ZQNPQL23 submitted 2026-02-10 math.OC cs.LG

Step-Size Stability in Stochastic Optimization: A Theoretical Perspective

Fabian Schaipp , Robert M. Gower , Adrien Taylor This is my paper
classification math.OC cs.LG MSC 90C1590C25
keywords stochastic optimizationstability indexstep-size stabilityadaptive step sizePolyak step sizeGauss-Newton step sizestochastic proximal pointconvex optimization
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper argues that the step-size sensitivity of stochastic optimization methods is governed by a single per-step quantity called the stability index, which measures how much of the current loss is not explained by the model update. Plugging this index into the standard convex suboptimality bound shows that the variance term—the part that grows with the step size—is exactly an average of the stability index. For SGD, this term grows linearly with the step size, explaining why SGD becomes unstable for large learning rates. For SPS, NGN, and SPP, the paper proves that the stability index is pointwise no larger than SGD's and saturates as the step size grows, giving a theoretical reason for the empirically observed robustness of these adaptive methods. If correct, this explains learning-rate robustness without invoking interpolation or smoothness.

Core claim

The paper identifies a single per-step quantity, the stability index, and proves that it is the variance term in the suboptimality bound for model-based stochastic methods. For convex problems satisfying a model lower-bound condition, the bound is f̄_T − f(x*) ≤ D²/(2Σα_t) + (Σα_t E[δ_t])/(Σα_t). The scaling of E[δ_t] with the step size α_t therefore determines step-size sensitivity. For SGD, δ_t = (α_t/2)‖g_t‖² grows linearly in α_t. For SPS, NGN, and SPP, the paper derives explicit formulas (δ_SPS ≤ min{α_t‖g_t‖², f(x_t,s_t) − C_t}, δ_NGN = (γ_t/2)‖g_t‖² with γ_t converging to 2f(x_t,s_t)/‖g_t‖², δ_SPP ≤ min{(α_t/2)‖g_t‖², f(x_t,s_t) − inf_y f(y,s_t)}) showing that these stability indices

What carries the argument

The central object is the stability index, defined as the gap between the current loss and the regularized model value at the next iterate. Under the model lower-bound assumption it is non-negative. It enters the suboptimality bound as the variance term, so its scaling with the step size distinguishes methods: linear for SGD, saturating for SPS, NGN, and SPP. The derivations rely on specific model choices: the truncated model for SPS, the square-root model for NGN, and the exact model for SPP.

Load-bearing premise

The convergence theorems require the model lower-bound condition that the model never exceeds the true loss, which is automatic for SGD, SPS, and SPP but for NGN is a strong curvature inequality that holds only on bounded domains for exp-concave losses.

What would settle it

Check whether E[δ_t] for SPS or NGN can grow linearly with α_t on a convex problem where the respective bound says it should saturate; a single such example would disprove the saturation claim. Alternatively, construct a nonnegative convex loss on an unbounded domain where the NGN model violates the lower-bound condition; then the NGN convergence bound fails, exposing the limit of the theory.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • SPS and NGN have stability indices bounded by SGD's, so under the paper's assumptions they are provably at least as stable as SGD for large step sizes; as a by-product, the analysis gives the first convergence complexity for NGN in the convex nonsmooth setting.
  • The advantage of SPS is governed by the interpolation constant and the lower-bound estimation error; a poorly chosen lower bound can erase the advantage, but never makes SPS worse than SGD.
  • For SPP, the stability index is capped by suboptimality plus the interpolation constant, and the batch size affects stability through that constant, matching observed behaviour.
  • The theoretical bound qualitatively predicts the learning-rate range that gives good performance, even in nonconvex deep learning, where the assumptions are not satisfied, suggesting the stability index is a robust diagnostic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the stability index is as informative as claimed, it could be estimated online from the trajectory to detect unstable runs or adapt the step size; the paper leaves this as an open question.
  • The model-based framework suggests a direct route to analyse momentum or preconditioning methods like Adam: define the corresponding stability index and check whether it saturates; the paper explicitly does not cover them.
  • The NGN lower-bound condition is the main restriction: it can fail for generic nonnegative convex losses on unbounded domains, so the NGN convergence theorem likely needs an additional exp-concavity or boundedness assumption, even though the pointwise inequality remains valid.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper introduces a 'stability index' δ_t = f(x_t,s_t) − f_{x_t}(x_{t+1},s_t) − (1/2α_t)‖x_{t+1}−x_t‖² for model-based stochastic proximal updates (Eq. 3). Under convexity of the model and a lower-bound condition (A2), it shows in Lemma 2 and Theorems 3–4 that the expected suboptimality decomposes into a bias term D²/(2Σα_t) and a variance term (Σ α_t E[δ_t])/(Σ α_t). For SGD, SPS, NGN, and SPP it derives explicit expressions or bounds for δ_t (Lemma 5–7, Eq. 12), concluding that the adaptive methods have δ_t no larger than SGD and that δ_t grows sublinearly in α, whereas for SGD it grows linearly. Experiments on ResNet20/CIFAR10 and convex regression/logistic tasks compare actual training loss with the theoretical bound across a range of step sizes.

Significance. If the theorem-level statements were fully established, the paper would provide a unified, quantitative explanation of the empirically observed learning-rate robustness of SPS, NGN, and SPP, going beyond pointwise or asymptotic analyses. The explicit δ formulas are correct: the algebra for δ_SPS, δ_NGN, and the SPP Moreau-envelope/Young bound checks out, and the PEPit verification for SPP is a useful worst-case sanity check. The pointwise inequalities δ_SPS, δ_NGN, δ_SPP ≤ δ_SGD are genuine and unconditional. The main weakness is that the convergence theorems for NGN require assumption (A2), which the square-root model does not satisfy for generic convex nonsmooth losses; the paper itself flags this in Section 4.3 but then drops the qualifier in the abstract, summary, and Section B.1. This makes the claimed 'first complexity for NGN in the convex non-smooth setting' unsupported as stated. The underlying stability-index comparison remains valuable, but the theorem-level claims need to be restricted to the (A2) setting.

major comments (2)
  1. [Section 4.3 / Section B.1 / Abstract] The theorem-level claims for NGN require (A2), which is not implied by convexity and nonnegativity. For the square-root model (10), (A2) is equivalent to f(y,s) ≥ f(x,s)+⟨g,y−x⟩+(1/(4f(x,s)))⟨y−x,g⟩² for all x,y,s,g. This fails even for f(x)=|x|: at x=1, g=1, y=0 the model gives f_x(0)=(1−1/2)²=1/4 > 0=f(0). Consequently Lemma 2's descent inequality (4), and hence Theorems 3–4, are not valid for NGN in the general convex nonsmooth setting. The paper acknowledges this in Section 4.3 ('less trivial', exp-concavity/bounded domain), but the Abstract, Summary 4.5, and Section B.1 claim 'provably always more stable' and a first convex non-smooth complexity for NGN without the qualifier. Please restrict the suboptimality claims to the (A2) setting and present the unconditional result as the pointwise bound δ_NGN ≤ δ_SGD.
  2. [Section B.1] The statement 'Using this bound in Theorems 3 and 4 we immediately arrive at a convergence result for SPS and NGN' is misleading for NGN. The bound (16) can be plugged into Theorems 3–4 only when those theorems apply, which requires (A2). Since (A2) fails for typical nonsmooth convex losses such as |x|, the derivation of (17) does not establish a convergence rate for NGN in the 'convex, non-smooth' setting claimed. The same caveat applies to Section 4.5's 'as a by-product ... first convergence analysis' for NGN. Either state the additional assumptions needed for (A2) explicitly in these sections or rephrase the claim as a conditional result.
minor comments (4)
  1. [Section 4.3 / Eq. (10)–(11)] The NGN model and update involve division by f(x,s) and become undefined when f(x,s)=0 and g=0 (e.g., at the minimizer of f=|x|). A convention or explicit restriction to strictly positive losses would make the statement of Lemma 6 fully rigorous.
  2. [Section 4.2] The display decomposing E[f(x_t)−C_t] is typeset ambiguously: the alignments after '=:σ²' and '=:ε_lb' make it unclear which term receives the label. Please define σ² and ε_lb with explicit equations.
  3. [Section 5.1] The distance bound D is set to 50 based on the observed final norm ∥x_T−x_1∥≈50.7, which is post hoc. Although Figs. 9 and 10 ablate this choice, the main text should state that D is not known a priori and that the qualitative conclusion is robust to the choice of D.
  4. [Conclusion] The phrase 'we prove that adaptive methods such as SPS or NGN are always more stable than SGD' should be qualified: the unconditional, proven statement concerns the one-step stability index δ_t, while the suboptimality comparison through Theorems 3–4 holds only under (A1)–(A2).

Circularity Check

0 steps flagged

Central δ-domination derivations are self-contained algebra; only minor self-citations and a posteriori experimental diagnostics. The NGN (A2) gap is a correctness limitation, not circularity.

full rationale

The paper's core derivation is not circular. The stability index δ_t is defined as the exact residual in the model-based proximal update, and Lemma 2's suboptimality bound follows from the external Asi & Duchi (2019a) Lemma 3.7 plus assumptions (A1)–(A2); Theorems 3–4 are algebraic rearrangements. The expressions δ_SGD = (α_t/2)||g_t||², δ_SPS = τ_t[1−τ_t/(2α_t)]||g_t||², δ_NGN = (γ_t/2)||g_t||², and the SPP upper bound are computed directly from the respective update rules, not assumed; the key inequalities δ_SPS, δ_NGN, δ_SPP ≤ δ_SGD follow from τ_t ≤ α_t and γ_t ≤ α_t. Thus the central 'adaptive methods are at least as stable as SGD' claim is derived, not postulated. The paper does cite its own prior work (Schaipp et al. 2023 Lem. 9; Schaipp et al. 2025 Thm. 9), but these are elementary algebraic facts or proof techniques, and the load-bearing one-step inequality is from an external source. The experimental comparison computes the bound from each run's own logged δ_t and sets D from ∥x_T−x_1∥, so it is a diagnostic consistency check rather than an independent prediction; the authors ablate D and the qualitative conclusion rests on the derived scaling. Finally, the paper itself flags in Section 4.3 that (A2) for the NGN square-root model is 'less trivial' and holds only under exp-concavity/bounded-domain conditions, while Section B.1 claims 'the first complexity for NGN in the convex non-smooth setting' without restating this qualifier. That is a correctness/assumption gap—it does not make the derivation circular—so I leave it out of the circularity score.

Axiom & Free-Parameter Ledger

1 free parameters · 6 axioms · 2 invented entities

The two-term bound structure of Theorems 3–4 requires only (A1)–(A2) plus per-sample convexity and standard stochastic averaging. These are satisfied by construction for SGD, SPS (given C_s ≤ inf f), and SPP; for NGN, (A2) is the fragile premise (exp-concavity / bounded domain), explicitly flagged in Sec. 4.3. One constant is fitted to the data being explained: D in the plotted bounds, disclosed and ablated (Fig. 9). No unexplained entities are postulated: the stability index is measurable from the run itself; the appendix's Lambert-W step size is new but clearly derived and outside the central claims.

free parameters (1)
  • D (initial distance-to-optimum bound) = 50 (CIFAR-10), 1 (linear regression), 100 (vowel), 50 (dna)
    Appears in the first term of the plotted bound Ω_T. Chosen as ‖x_T − x_1‖ ≈ 50.7 for the ResNet experiments, i.e., fitted to the trajectory actually run, not known a priori. Ablated in Fig. 9 (D ∈ [1,100]) with the qualitative conclusion surviving, so it does not drive the central claim.
axioms (6)
  • domain assumption (A1) each per-sample model y↦f_x(y,s) is convex
    Needed for Lemma 2 and Theorems 3–4; holds by construction for the SPS truncated model, the SPP exact model, and the NGN square-root model (Section 3, Section 4.3).
  • domain assumption (A2) f_x(x,s) = f(x,s) and f_x(y,s) ≤ f(y,s) for all y
    Load-bearing for Lemma 1 (δ_t ≥ 0) and for the U_1 step in Lemma 2. Automatic for SGD/SPS/SPP via convexity; for NGN it is equivalent to an α-exp-concavity-type inequality that holds only on a bounded domain — flagged by the authors as 'less trivial' (Section 4.3).
  • domain assumption f(·,s) is convex for every s
    Restricts the theory to convex problems; the non-convex experiments are explicitly acknowledged to fall outside the theorem's applicability (Section 4.5, Limitations).
  • domain assumption C_s ≤ inf_z f(z,s) for SPS (valid per-sample lower bound)
    Ensures the truncated model satisfies (A2) and that the update (8) is well-defined; experiments use C_t = 0 and C_t = −2, both valid lower bounds in the tested cases (Section 4.2, experiments V3).
  • domain assumption f(x,s) ≥ 0 for all x,s (for NGN)
    Required for the square-root model (10) and for the saturation γ_t → 2f/‖g‖²; standard for machine-learning losses (Section 4.3).
  • standard math Last-iterate bound structure of Defazio et al. (2023, Thm. 10)
    Theorem 4 follows that proof pattern identically, substituting α_t E[δ_t] for (1/2)η_t² E‖g_t‖² (Theorem 4 proof, Section 3).
invented entities (2)
  • The stability index δ_t (Eq. 3) independent evidence
    purpose: A per-step quantity that controls the α-dependence of the suboptimality bound of any model-based method
    Not a physical entity but a defined observable: it is directly measurable from the trajectory (per-step loss and gradient norm), and its scaling in α is the paper's falsifiable handle, tracked in all experiments.
  • Lambert-W adaptive step size γ_t = (f_t/‖g_t‖²) W_0(α_t‖g_t‖²/f_t) (Eq. 22) independent evidence
    purpose: New step-size rule derived from the log→linearize→exp generalization of the NGN model
    Proposed in Appendix D with preliminary experiments showing stability; well-defined and testable, but outside the central claims and not investigated further.

pith-pipeline@v1.3.0-alltime-deepseek · 19390 in / 33954 out tokens · 322576 ms · 2026-08-03T02:42:04.994333+00:00 · methodology

0 comments
read the original abstract

We present a theoretical analysis of stochastic optimization methods in terms of their sensitivity with respect to the step size. We identify a key quantity that, for each method, describes how the performance degrades as the step size becomes too large. For convex problems, we show that this quantity directly impacts the suboptimality bound of the method. Most importantly, our analysis provides direct theoretical evidence that adaptive step-size methods, such as SPS or NGN, are more robust than SGD. This allows us to quantify the advantage of these adaptive methods beyond empirical evaluation. Finally, we show through experiments that our theoretical bound qualitatively mirrors the actual performance as a function of the step size, even for non-convex problems.

Figures

Figures reproduced from arXiv: 2602.09842 by Adrien Taylor, Fabian Schaipp, Robert M. Gower.

Figure 1
Figure 1. Figure 1: Illustration of theory for f(x, st) = ln(1 + exp(−x)) + max{x − 2, 0} and xt = −3. (Left) Next-iterate loss as a function of step size α. (Right) Stability index δt as a function of α. Vertical line marks best SGD step size. For large α, stable loss values coincide with benign (≈ sub-linear) increase of δt . various settings (Bertsekas, 2011; Boyd & Ryu, 2014; Patrascu & Necoara, 2017; Asi & Duchi, 2019a; … view at source ↗
Figure 2
Figure 2. Figure 2: (Left) Stability with respect to learning-rate α under different scalings of ∆t . (Right) Values of Λ(α) (blue) computed with PEPit, for different Lipschitz constants G. We plot the upper bound fs(x) − inf fs for the worst-case instance in (green), and the corresponding δ SGD = 1 2 αG2 (grey). 4.1 Linear Model (SGD) If fx(y, s) = f(x, s) + ⟨g, y − x⟩ for some g ∈ ∂f(x, s), then (A1) is always satisfied and… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of the stability index δt for SGD (left) and NGN (right), for the function from [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: ResNet20 on CIFAR10: Actual training loss (solid lines) and value of the bound Ω last T , Theorem 4 (dashed) with D = 50. After T = 20 epochs, SPS and NGN are more stable than SGD for large α and achieve a smaller loss. This behavior is (qualitatively) reflected in the bound. (Right) Warmup allows SGD to use a larger learning rate. Again, this is reflected in the bound Ωlast T . (1) (without warmup): const… view at source ↗
Figure 5
Figure 5. Figure 5: (Left) δt explodes for SGD (without warmup) in the first iterations when α is large. (Right) When using warmup over 100 steps, the increase of δt is slowed down. 5.2 Convex Regression Tasks We also run a set of convex tasks, where the assumptions of the theory are satisfied. First, for ridge regression on synthetic data, we compare SGD, SPP and SPS; we omit NGN here for the sake of clarity of presentation.… view at source ↗
Figure 6
Figure 6. Figure 6: Linear regression: (Left) Actual training loss (solid lines) and value of the bound Ωlast T , Theorem 4 (dashed) with D = 1. (Right) The values of δt quickly explode for SGD, whereas for SPP and SPS they remain bounded when α becomes large. 10−3 10−2 10−1 100 101 102 Base learning rate α 10−2 10−1 100 101 102 103 SPS SGD SPP f(xT ) − f? (train) Bound ΩT (a) Variant (V1) 10−3 10−2 10−1 100 101 102 Base lear… view at source ↗
Figure 7
Figure 7. Figure 7: Variations for the linear regression problem. [PITH_FULL_IMAGE:figures/full_fig_p015_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Logistic regression on vowel dataset. 6 Conclusion We have presented a theoretical analysis for step-size stability of several stochastic opti￾mization methods. Within our framework, we prove that adaptive methods such as SPS or NGN are always more stable than SGD. An open question is how tracking the stability index δt could be leveraged in practice, for example to terminate unstable runs early. Another d… view at source ↗
Figure 9
Figure 9. Figure 9: ResNet20 on CIFAR010: Bound ΩT from Theorem 4 for multiple values of D ∈ [100 , 102 ]. The advantage of SPS and NGN over SGD for large α is reflected in the bound independent of the value of D. 10−2 10−1 100 101 102 Base learning rate α 10−1 100 101 102 NGN SPS SGD Train loss f(xT ) Bound ΩT (a) without warmup 10−2 10−1 100 101 102 Base learning rate α 10−1 100 101 102 NGN SPS SGD Train loss f(xT ) Bound Ω… view at source ↗
Figure 10
Figure 10. Figure 10: ResNet20 on CIFAR10: Same as [PITH_FULL_IMAGE:figures/full_fig_p028_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: ResNet20 on CIFAR10: Same as [PITH_FULL_IMAGE:figures/full_fig_p029_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Same as [PITH_FULL_IMAGE:figures/full_fig_p029_12.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

6 extracted references · 3 linked inside Pith

  1. [1]

    Hilal Asi and John C. Duchi. Stochastic (approximate) proximal point methods: con- vergence, optimality, and adaptivity.SIAM Journal on Optimization, 29(3):2257–2290, 2019a.[Cited on pages 3, 4, 5, 6, and 7] Hilal Asi and John C. Duchi. The importance of better models in stochastic optimization. Proceedings of the National Academy of Sciences of the Unite...

    Pith/arXiv arXiv 2017

  2. [9]

    Since Ψt =f(x t, st)−δ SPS t we have from the above thatδ SPS t =τ t[1− τt 2αt ]∥gt∥2

    it holds xt+1 =x t −τ tgt with Ψt =f(x t, st)−τ t∥gt∥2 + τ 2 t 2αt ∥gt∥2 =f(x t, st)−τ t[1− τt 2αt ]∥gt∥2. Since Ψt =f(x t, st)−δ SPS t we have from the above thatδ SPS t =τ t[1− τt 2αt ]∥gt∥2. Given that the functionτ7→τ(1− τ 2α ) is maximized at ˆτ=α, we conclude thatδ SPS t ≤ αt 2 ∥gt∥2 =δ SGD t (assuming bothδ t would be measured at the same iteratex ...

    2024

  3. [28]

    Tyrrell Rockafellar

    Princeton University Press, Princeton, N.J., 1970.[Cited on page 2] R. Tyrrell Rockafellar. Monotone operators and the proximal point algorithm.SIAM Journal on Control and Optimization, 14(5):877–898, 1976.[Cited on page 4] Fabian Schaipp, Robert M. Gower, and Michael Ulbrich. A stochastic proximal Polyak step size.Transactions on Machine Learning Researc...

    arXiv 1970

  4. [1983]

    [Cited on page 2] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions.SIAM Journal on Optimization, 29(1):207–239, 2019.[Cited on pages 3, 4, 5, and 24] Aaron Defazio and Konstantin Mishchenko. Learning-rate-free learning by D-adaptation. InInternational Conference on Machine Learning, volume 202, pp. 7449–7479,

    2019

  5. [2023]

    Optimal linear decay learning rate schedules and further refinements

    [Cited on page 4] 17 Aaron Defazio, Ashok Cutkosky, Harsh Mehta, and Konstantin Mishchenko. Optimal linear decay learning rate schedules and further refinements. arXiv:2310.07831,

    Pith/arXiv arXiv

  6. [2024]

    [Cited on page 1] Guillaume Garrigos and Robert M. Gower. Handbook of convergence theorems for (stochastic) gradient methods. arXiv:2301.11235, 2024.[Cited on page 24] Baptiste Goujaud, C´ eline Moucer, Fran¸ cois Glineur, Julien M. Hendrickx, Adrien B. Taylor, and Aymeric Dieuleveut. PEPit: computer-assisted worst-case analyses of first- order optimizati...

    Pith/arXiv arXiv 2024