# Convergence Analysis of STORM Under Different Geometries

arXiv: https://arxiv.org/abs/2610.01599 · HTML: https://mlsanity.com/paper/2610.01599/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 15 references that are in the map.
- First posted on arXiv 1 Oct 2026.

## Builds on (most cited first, 12 of 12)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions](https://mlsanity.com/paper/2406.01959/) (2024)

## Abstract (arXiv)

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--Lojasiewicz~(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/√ T) and O(σ2/(λ T)), respectively. All the obtained results use the same STORM recursion with different hyperparameter choices.