Convergence Analysis of STORM Under Different Geometries

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

math.OCOct 1, 2026

Convergence Analysis of STORM Under Different Geometries

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

Organizations: School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

Abstract

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(σ^2/(μT))$ bound for last-iterate output under the $μ$ -Polyak--Ł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 $λ$ -strongly convex objectives, we further prove averaged and last-iterate bounds with optimal rates of $O(σR/\sqrt T)$ and $O(σ^2/(λT))$ , respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.

Figures & tables

Objective	Assumption	Output	Convergence rate
Nonconvex	AS	Uniform random	$T^{-1/3}$
Nonconvex	$-$	Uniform random	$T^{-1/4}$
$\mu$ -PL	AS	Last iterate	$\sigma^{2}/(\mu T)$
Convex	$-$	Weighted mean; last iterate	$\sigma R/\sqrt{T}$
$\lambda$ -strongly convex	$-$	Weighted mean; last iterate	$\sigma^{2}/(\lambda T)$

Table 1: Convergence of STORM under different settings. All rows assume an

L

-smooth objective and an unbiased oracle with variance at most

\sigma^{2}

. AS denotes average smoothness. The nonconvex rows measure the expected gradient norm, while the other rows measure the expected function gap. Only the dominant term is presented.

Figure 1: Convergence under average smoothness (log–log scales).

Figure 2: Convergence without average smoothness (log–log scales).

Explore similar work

Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise
May 14, 2026Antesh Upadhyay, Arda Fazla, Abolfazl HashemiStochastic Convex Optimization Stochastic Gradient Descent
School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.
Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum
Jun 18, 2024Haoyuan Cai, Sulaiman A. Alghunaim, Ali H. SayedStochastic Convex Optimization Convex Optimization
Ecole Polytechnique Fédérale de Lausanne, Switzerland · Kuwait University, Kuwait
Stochastic Non-Smooth Convex Optimization with Unbounded Gradients
May 15, 2026Dmitry KovalevStochastic Convex Optimization Lipschitz Continuity
Yandex Research

May 14, 2026, cs.LGJ/K move · Enter open · S save

Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise

Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi

School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

Stochastic Convex Optimization Stochastic Gradient Descent Convex Optimization Smoothness Nonconvex Variance+3

Open paper AskPDF arXiv

We study nonconvex stochastic optimization under the Blum-Gladyshev (

\mathsf{BG}

-0) noise model, where the stochastic gradient variance grows quadratically with the distance from the initialization. We consider this problem under both standard smoothness and the symmetric generalized-smoothness framework, which captures objectives whose local curvature can scale with the gradient norm. We prove that normalized stochastic gradient descent with momentum, using only one stochastic gradient per iteration, converges under

\mathsf{BG}

-0 noise with oracle complexity

O(\varepsilon^{-6})

. This rate holds both for standard smoothness and for

α

-symmetric generalized smoothness, showing that generalized smoothness is rate-neutral for normalized momentum in this setting. We then study a variance-reduced normalized STORM method. Under mean-square smoothness and sharp initialization, the method achieves the minimax optimal

O(\varepsilon^{-4})

complexity, matching the lower bound. Under expected

α

-symmetric generalized smoothness, the STORM recursion couples gradient-dependent smoothness with distance-dependent noise, leading to complexity

O(\varepsilon^{-(4+α)})

for

α\in(0,1)

and

O(\varepsilon^{-5})

for

α=1

. When the distance-growth parameter in the noise model vanishes, our guarantees recover the standard bounded-variance rates:

O(\varepsilon^{-4})

for momentum,

O(\varepsilon^{-3})

for variance reduction, and

O(\varepsilon^{-2})

in the deterministic case. To our knowledge, these are the first convergence guarantees for normalized methods in non-convex stochastic optimization under

\mathsf{BG}

-0 noise without bounded domains, increasing batch sizes, or explicit anchoring, covering both standard and generalized smoothness regimes.

Abstract

Explore similar work

Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise

Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum

Stochastic Non-Smooth Convex Optimization with Unbounded Gradients