PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Analysis of STORM Under Different Geometries

Wei Jiang, Yibo Wang, Wenhao Yang, Rui Yan, Lijun Zhang, Zechao Li

arXiv:2610.01599v1math.OCcs.LG

TL;DR

Existing STORM guarantees rely on average smoothness and do not establish optimal rates for convex or strongly convex objectives without it. The paper analyzes the original STORM recursion across smoothness assumptions and objective geometries, using different parameter choices for its guarantees. STORM attains optimal stochastic orders for both averaged and last iterates in the convex and strongly convex settings.

  • Problem

    Existing STORM guarantees rely on average smoothness and do not establish optimal rates for convex or strongly convex objectives without it.

    Source: §1 · p. 1

  • Method

    The paper analyzes the original STORM recursion across smoothness assumptions and objective geometries, using different parameter choices for its guarantees.

    Source: §7 · p. 10

  • Results

    STORM attains optimal stochastic orders for both averaged and last iterates in the convex and strongly convex settings.

    Source: §7 · p. 10

  • Takeaways & Limitations

    The same STORM recursion supports guarantees across these settings with different hyperparameter choices, a single initial sample, and a constant number of gradient evaluations per iteration.

    Source: §7 · p. 10

    The guarantees are worst-case upper bounds, so a particular objective may converge faster in practice.

    Source: §6 · p. 9

Abstract

from arXiv · show

Stochastic recursive momentum (STORM) achieves fast convergence for nonconvex optimization via the variance reduction effect, but existing analyses rely on the strong average smoothness assumption. In this paper, we study the convergence of STORM for different objectives without average smoothness. We first revisit the results under average smoothness, obtaining the $O(T^{-1/3})$ bound for nonconvex objectives and the $O(\sigma^2/(\mu T))$ bound for last-iterate output under the $\mu$-Polyak--\L{}ojasiewicz~(PL) condition. Without average smoothness, we design an auxiliary sequence and compare the STORM update with it in the analysis. With the help of this sequence, we prove that STORM still attains an $O(T^{-1/4})$ rate for nonconvex objectives, which is optimal under standard smoothness. For convex and $\lambda$-strongly convex objectives, we further prove averaged and last-iterate bounds with optimal rates of $O(\sigma R/\sqrt T)$ and $O(\sigma^2/(\lambda T))$, respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.

1 INTRODUCTION

The paper asks whether STORM can retain strong convergence guarantees without average smoothness, and develops results for nonconvex, convex, and strongly convex objectives. It revisits guarantees under average smoothness, then establishes the paper’s main results under standard smoothness.

1 INTRODUCTION

  • STORM uses a recursive stochastic-gradient estimator, with η_t as the stepsize and a_{t+1} as the momentum parameter.The paper studies the original STORM framework, whose nonconvex rate under average smoothness improves on the standard SGD rate described in the introduction.Source: §1 · p. 1
  • Existing STORM analyses require average smoothness, leaving its standard-smoothness rate and optimal convex and strongly convex guarantees unresolved.The paper defines average smoothness through a bound on stochastic-gradient differences; it measures nonconvex convergence by expected gradient norm and other cases by expected function gap.Source: §1 · p. 1
  • Under average smoothness, STORM achieves O(T^-1/3) for nonconvex objectives and a last-iterate O(σ^2/(µT)) bound under the µ-PL condition.The analysis removes a logarithmic factor from the previous nonconvex bound, avoids a large initial batch, and uses a two-phase stepsize design for the PL result.Source: §1 · p. 2
  • Without average smoothness, STORM attains the O(T^-1/4) nonconvex rate and obtains weighted-mean and last-iterate guarantees for convex objectives.The nonconvex rate matches classical SGD and is optimal under standard smoothness; the supplied passage gives the convex bound only partially.Source: §1 · p. 2
  • O(σ^2/(λT)) is the weighted-mean and last-iterate bound for smooth λ-strongly convex objectives.The paper describes these bounds as optimal in iteration number under their corresponding settings.Source: §1 · p. 2

2 RELATED WORK

Prior variance-reduction methods use recursive stochastic-gradient estimators in nonconvex optimization, while STORM avoids periodic large-batch refreshes. Related STORM-based work also addresses convex and PL settings, often under additional assumptions or different procedures.

Variance reduction for nonconvex objectives

  • SPIDER uses successive stochastic-gradient differences but periodically refreshes its estimator with a large batch or full gradient; STORM instead adds a fresh-gradient difference at every step.The cited discussion states that SPIDER's complexity guarantees assume average smoothness.Source: §2 · p. 2
  • STORM's original nonconvex guarantee includes logarithmic factors; STORM+ requires bounded gradients and objective value, while Ada-STORM uses an O(T^1/3) initial batch.The discussion attributes the logarithm in the original bound to Cutkosky & Orabona (2019) and describes later variants by Levy et al. (2021) and Jiang et al. (2024).Source: §2 · p. 2

STORM-based methods for convex optimization

  • Zhang et al. (2020) combine STORM with Frank–Wolfe updates for convex objectives, requiring a bounded feasible set, samplewise smoothness, and bounded stochastic gradients.Dahan & Levy (2025) use STORM with anytime averaging in µ2-SGD, evaluating gradients at running averages of a separate projected sequence and also requiring samplewise smoothness and a bounded feasible set.Source: §2 · p. 3

Variance reduction under the µ-PL condition

  • PAGE's PL guarantee assumes average smoothness and uses a refresh batch dependent on target accuracy; STORM-based stage-wise SMVR also has PL complexity guarantees.RECOVER addresses compositional objectives, while the cited stage-wise SMVR result gives O((µε)^-1) when ε ≤ µ.Source: §2 · p. 3

3 ASSUMPTIONS

The paper assumes a differentiable objective with finite infimum and an unbiased stochastic oracle with bounded variance. Average smoothness, the PL condition, convexity, and strong convexity specify additional settings for individual results.

3 ASSUMPTIONS

  • Throughout, the objective is differentiable with finite infimum, and the stochastic oracle is unbiased with variance at most σ^2.The paper initializes at x0 and uses ∆0 = F(x0) − F*, R = ∥x0 − x*∥, and, when applicable, κ = L/λ.Source: §3 · p. 3
  • Average smoothness bounds the expected squared difference between stochastic gradients at x and y by L^2∥x − y∥^2.The paper also calls this mean-square smoothness and notes that it implies L-smoothness of F together with the oracle assumptions.Source: §3 · p. 3
  • Convexity and the µ-PL condition are separate setting assumptions, while λ-strong convexity implies the PL condition with µ = λ.The converse does not hold, so the PL setting is not restricted to strongly convex objectives.Source: §3 · p. 3

4 CONVERGENCE UNDER AVERAGE SMOOTHNESS

The section revisits STORM under average smoothness, first for nonconvex objectives and then for objectives satisfying the PL condition.

4.1 NONCONVEX OBJECTIVES

  • O(T^-1/3) convergence for nonconvex objectives removes the logarithmic factor in the prior STORM bound and avoids a large initial batch.The rate matches the lower bound for nonconvex objectives with average smoothness.Source: §4.1 · p. 4

4.2 OBJECTIVES SATISFYING THE PL CONDITION

  • O(σ²/(μT)) stochastic error is obtained for the last iterate under the PL condition.A two-phase schedule geometrically reduces initialization error, then decreases the stepsize without restarting or adding a nonconstant factor to the leading stochastic term.Source: §4.2 · pp. 4–5

5 CONVERGENCE WITHOUT AVERAGE SMOOTHNESS

Without average smoothness, the analysis handles STORM's inherited estimator error using auxiliary sequences. It establishes convergence guarantees for nonconvex, convex, and strongly convex objectives.

5 CONVERGENCE WITHOUT AVERAGE SMOOTHNESS

  • The analysis separates inherited estimator error from centered noise and compares STORM with an auxiliary sequence driven by that noise.The shared noise cancels in the trajectory difference, which is controlled by nonexpansiveness or, under strong convexity, contraction.Source: §5 · p. 5

5.1 NONCONVEX OBJECTIVES

  • O(T^-1/4) convergence for nonconvex objectives matches SGD and is optimal under standard smoothness.The analysis shifts the iterate by a multiple of the previous estimator error to remove inherited error from the auxiliary recursion.Source: §5.1 · p. 5

5.2 CONVEX OBJECTIVES

  • For convex objectives, STORM obtains optimal weighted-mean and last-iterate guarantees without average smoothness.The rates match SGD guarantees and the lower bound for convex objectives.Source: §5.2 · p. 7

5.3 STRONGLY CONVEX OBJECTIVES

  • O(σ²/(λT)) is the dominant last-iterate bound under strong convexity, without average smoothness.The companion-distance contraction supports the guarantee.Source: §5.3 · p. 8

6 NUMERICAL EXPERIMENTS

The experiments isolate how objective geometry, average smoothness, and output choice relate to STORM’s convergence and prescribed schedules. They report behavior on four objectives with known minima and exact gradients.

Experimental setup

  • The experiments examine objective geometry, failure of average smoothness, and schedule behavior for averaged and last-iterate outputs rather than repeat broad benchmark evaluation.The setup uses objectives with known minima and exact gradients; parameters are chosen from analytical constants without tuning.Source: §6 · p. 8
  • For experiments without average smoothness, the stochastic oracle is unbiased, has variance σ^2 = 10, and has no finite average-smoothness constant.The study runs 256 independent trials.Source: §6 · p. 8

Nonconvex and PL objectives under average smoothness

  • Under average smoothness, the nonconvex result is roughly consistent with T^-2/3; on the PL problem, two-phase stepsizes do better at smaller budgets, while harmonic stepsizes do better at larger budgets.Figure 1 presents convergence on log–log scales.Source: §6 · p. 9, Figure 1 · p. 9

Nonconvex objectives without average smoothness

  • 85× more iterations reduces the squared-gradient criterion by about 9.1 for each tested correction coefficient without average smoothness.The observed reduction is close to the theoretical stochastic order T^-1/2; fixed-β curves and SGD are nearly indistinguishable at this scale.Source: §6 · p. 9, Figure 2 · p. 9

Averaged and last iterates without average smoothness

  • Without average smoothness, the uniform mean is slightly better than the last iterate at the largest tested convex budget, while both strongly convex curves follow T^-1 closely at larger budgets.Figure 2 presents convergence on log–log scales.Source: §6 · p. 9, Figure 2 · p. 9

7 CONCLUSION

The conclusion summarizes STORM’s guarantees across objective geometries and smoothness assumptions, using different parameters within the same recursion. The proof of Theorem 1 combines descent with an estimation-error bound to establish a nonconvex rate.

7 CONCLUSION

  • Under standard smoothness, STORM matches the nonconvex SGD rate and attains optimal stochastic orders for averaged and last iterates in convex and strongly convex settings.The guarantees use different parameter choices within the same STORM recursion, with one initial sample and a constant number of gradient evaluations per iteration.Source: §7 · pp. 9–10

A PROOF OF THEOREM 1

  • Theorem 1’s proof combines a descent inequality with a gradient-estimation-error bound, using η = 1/[2L(T + 2)^(1/3)] and a_t = (t + 2)^(-2/3).The resulting expected-norm rate follows from an O((LΔ_0 + σ^2)T^-2/3) second-moment bound.Source: A PROOF OF THEOREM 1 · pp. 11–13

B PROOF OF THEOREM 2

The proof of Theorem 2 uses a potential with a constant weight on estimator error and splits the updates into two phases. It carries the potential forward without restarting the STORM iterates.

B PROOF OF THEOREM 2

  • The proof uses a potential that gives the estimation error a constant weight.It bounds the initialization and noise contributions separately.Source: B PROOF OF THEOREM 2 · pp. 13–14
  • With m = floor(T/2), the proof applies one bound during the first m updates and a second schedule over the remaining n = T − m updates.The latter uses η_(m+j) = 2/[μ(s + j)].Source: B PROOF OF THEOREM 2 · p. 15
  • The remaining-update argument uses the potential at step m directly, without restarting x_m or d_m, and yields the stated final bound.The proof concludes by bounding Δ_T using V_T and the initial bound on V_0.Source: B PROOF OF THEOREM 2 · p. 15

C PROOF OF THEOREM 3

The proof of Theorem 3 handles the inherited estimator error by defining an auxiliary iterate for analysis, not for STORM’s implementation. A centered-noise descent argument then yields the convergence bound.

C PROOF OF THEOREM 3

  • The estimator error is decomposed into inherited error and a conditionally mean-zero increment, whose second moment is bounded by (1 + β)^2σ^2.The proof uses fresh-sample independence and the oracle variance bound.Source: C PROOF OF THEOREM 3 · p. 16
  • The analysis defines an auxiliary iterate so the inherited estimator error cancels from its update; STORM does not compute this sequence.The auxiliary sequence is compared with the actual iterate using standard smoothness.Source: C PROOF OF THEOREM 3 · pp. 16–17
  • Descent along the auxiliary sequence produces a bound whose parameter choice recovers the usual initialization and variance orders of nonconvex SGD.The descent inequality is summed over the iterations before choosing parameters.Source: C PROOF OF THEOREM 3 · pp. 17–18

D PROOF OF LEMMA 4

The proof establishes nonexpansiveness of the gradient update for smooth convex objectives, then extends the argument to strongly convex objectives by removing a quadratic term. It also derives function-gap inequalities using smoothness alone.

Contraction under strong convexity

  • The gradient map is nonexpansive for η ≤ 1/L, as the gradient-difference inner product bound makes the squared distance between updated points no larger than before.The proof uses ⟨∇F(x) − ∇F(y), x − y⟩ ≥ ||∇F(x) − ∇F(y)||^2/L.Source: D PROOF OF LEMMA 4 · p. 18
  • For L > λ, subtracting λ||z||^2/2 yields a convex function H with an upper quadratic model of coefficient L − λ, allowing the nonexpansiveness argument to apply.When L = λ, H is affine and the gradient-difference relation holds with equality.Source: D PROOF OF LEMMA 4 · p. 18

Comparison of function gaps

  • The two function-gap inequalities follow from the smoothness upper model and require smoothness only.The proof applies the upper model at a gradient step, rearranges, then uses Young’s inequality.Source: D PROOF OF LEMMA 4 · pp. 18–19

E PROOF OF LEMMA 5

The proof controls STORM through an auxiliary companion sequence, then develops shared one-step bounds, rounded schedule blocks, and guarantees for means and the last iterate.

E PROOF OF LEMMA 5

  • STORM’s estimation error satisfies e_t=βe_{t−1}+ν_t with conditionally centered innovations; subtracting the companion update cancels their shared innovation, and under strong convexity E||x_t−y_t||²≤3β²σ²/λ².Source: E PROOF OF LEMMA 5 · p. 19

F.1 A SHARED ONE-STEP INEQUALITY

  • For an adapted companion recursion with conditionally centered noise and ηt ≤ 1/(2L), the shared one-step inequality bounds both distance and expected function error.The proof uses conditional centering, smoothness, and convexity to control the terms in the distance expansion.Source: §F.1 · p. 20

F.2 ROUNDED-BLOCK GEOMETRY FOR ARBITRARY INTEGER HORIZONS

  • The rounded blocks cover arbitrary integer horizons while keeping adjacent block lengths within constant factors.The construction ensures K ∈ {2M − 1, 2M}, K/n ≤ 2, and |Bi| ≤ 3|Bi+1|.Source: §F.2 · p. 20

G.1 GENERAL STEPSIZE-WEIGHTED AND CONSTANT-STEP MEANS

  • Summing the one-step bound with stepsize weights controls the stepsize-weighted mean, and constant stepsizes make that output the uniform mean.The weights ηt/ΛT are positive and sum to one; the corollary specializes to ηt = η.Source: §G.1 · p. 21

G.2 THE COMPANION’S LAST-ITERATE BOUND

  • The last-iterate analysis compares consecutive schedule blocks and propagates their mean-error bounds to the terminal singleton block.The same block estimates also bound the full uniform mean; the geometric coefficients avoid a factor proportional to the number of blocks.Source: §G.2 · pp. 22–23

G.3 PROOF OF THE CONVEX THEOREM

The proofs transfer companion-sequence guarantees to STORM outputs for convex and strongly convex objectives, using weighted averaging and block comparisons. The block argument supports the last-iterate guarantee under smoothness without sample smoothness or globally bounded stochastic gradients.

G.3 PROOF OF THE CONVEX THEOREM

  • The convex-theorem proof establishes a common bound for the last iterate, uniform mean, and stepsize-weighted mean.The weighted-mean bound is no larger than the common bound for the other two outputs.Source: §G.3 · p. 24

H.1 THE LINEARLY WEIGHTED MEAN

  • The linearly weighted mean guarantee also applies to an independent random output J with probability proportional to t + s.The weighted average of expected STORM function gaps equals E[F(xJ) − F*].Source: §H.1 · p. 25

H.2 A BLOCK COMPARISON FOR AN SGD COMPANION

  • The SGD-companion block comparison relates an earlier block’s expected function errors to the next block under the stated direction-moment bound.Rounded block lengths and the schedule’s changing stepsizes are used to bound the adjacent-block comparison.Source: §H.2 · pp. 26–27

H.3 PROOF OF THE LAST-ITERATE THEOREM

  • For the last-iterate theorem, the companion’s trajectory segment is controlled using smoothness alone, without sample smoothness or globally bounded stochastic gradients.The proof uses a reference function value in the first half and a block comparison to transfer the companion guarantee to STORM’s last iterate.Source: §H.3 · pp. 29–30

Related papers

Loading 2610.01599v1…