Abstract
Traditional analyses for non-convex stochastic optimization problems characterize convergence bounds in expectation, which is inadequate as it does not supply a useful performance guarantee on a single run. Motivated by its importance, an emerging line of literature has recently studied the high-probability convergence behavior of several algorithms, including the classic stochastic gradient descent (SGD). However, no high-probability results are established for optimization algorithms with variance reduction, which is known to accelerate the convergence process and has been the de facto algorithmic technique for stochastic optimization at large. To close this important gap, we introduce a new variance-reduced algorithm for non-convex stochastic optimization, which we call Generalized SignSTORM. We show that with probability at least $1-\delta$, our algorithm converges at the rate of $O(\log(dT/\delta)/T^{1/3})$ after $T$ iterations where $d$ is the problem dimension. This convergence guarantee matches the existing lower bound up to a log factor, and to our best knowledge, is the first high-probability minimax (near-)optimal result. Finally, we demonstrate the effectiveness of our algorithm through numerical experiments.
Introduction
In the field of stochastic optimization, the gold standard for theoretical guarantees has traditionally been convergence "in expectation." While this provides a useful average-case analysis, it offers no certainty for a single execution of an algorithm—a critical limitation for practitioners in high-stakes environments. High-probability bounds, which guarantee that an algorithm will succeed with probability at least $1-\delta$, provide the necessary reliability for real-world deployment.
While high-probability results have recently been established for Stochastic Gradient Descent (SGD), a significant gap remained for variance-reduced methods. Variance reduction is essential for accelerating convergence in large-scale stochastic optimization, yet its high-probability behavior remained poorly understood, particularly under non-standard smoothness conditions. This paper addresses this gap by establishing the first near-optimal high-probability convergence rates for variance-reduced algorithms, specifically focusing on the Normalized STORM (STochastic Optimization with Recursive Momentum) framework.
The Challenge of Generalized Smoothness
Most optimization analyses assume $L$-smoothness, where the gradient's rate of change is globally bounded. However, modern deep learning and distributionally robust optimization (DRO) often exhibit $(L_0, L_1)$-smoothness. In this regime, the function's smoothness can grow with the norm of the gradient, allowing for potentially unbounded gradient growth.
This generalized smoothness presents two major hurdles:
- Reliability: Standard concentration tools fail when gradients are not globally bounded, making high-probability analysis significantly more complex.
- Efficiency: Previous methods for $(L_0, L_1)$-smooth functions often required massive, accuracy-dependent batch sizes (on the order of $1/\epsilon$), which are computationally expensive and impractical for streaming data.
The Normalized STORM Algorithm
The authors analyze Normalized STORM, a single-loop algorithm that integrates momentum-based variance reduction. Unlike complex double-loop structures (such as SPIDER), Normalized STORM is simpler to implement and better suited for streaming applications where only one sample is available at a time.
To prove high-probability bounds in this challenging setting, the authors introduce several technical innovations:
- Dimension-Free Concentration: Utilizing Hilbert-space martingale concentration inequalities, the authors derive bounds that do not depend on the problem's dimensionality.
- Recursive Induction Argument: A novel inductive proof strategy is used to "tame" the potential gradient growth inherent in $(L_0, L_1)$-smoothness, ensuring the algorithm's stability throughout the optimization process.
- Affine-Type Noise: The analysis accounts for a general noise model where variance can grow with the true gradient, providing a more realistic representation of modern optimization landscapes.
Key Insights and Theoretical Results
The paper's primary result is that Normalized STORM achieves an $\epsilon$-stationary point with a sample complexity of $O(\frac{\log(1/\delta\epsilon)}{\epsilon^3})$. This translates to a convergence rate of $O(\log(dT/\delta)/T^{1/3})$ after $T$ iterations.
Constant Batch Sizes
A standout finding is that massive batches are not required to handle generalized smoothness. The authors demonstrate that constant batch sizes (even a batch size of 1) are sufficient to achieve optimal convergence rates, significantly reducing the computational burden compared to previous state-of-the-art methods.
Near-Optimality and Adaptivity
The achieved rate of $\tilde{O}(T^{-1/3})$ matches the known theoretical lower bounds for non-convex stochastic optimization, proving the method is minimax near-optimal. Furthermore, the bounds are adaptive; if the problem is standard $L$-smooth ($L_1=0$) or deterministic, the formulas automatically collapse to the known optimal rates for those simpler cases. Interestingly, the authors also show that in certain regimes, stochastic optimization under generalized smoothness can achieve an expected convergence rate of $O(T^{-1/2})$, matching deterministic efficiency.
Conclusion
This work establishes the first high-probability, near-optimal convergence guarantees for variance-reduced stochastic optimization under generalized smoothness. By proving that these results are attainable with a simple, single-loop algorithm and constant batch sizes, the authors bridge the gap between theoretical optimality and practical engineering requirements. Future work may explore parameter-free versions of the algorithm that do not require prior knowledge of smoothness and noise constants, as well as techniques to remove the remaining logarithmic factor in the convergence bound.
Summary updated