# Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 13 Feb 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimization](https://mlsanity.com/paper/1905.05920/) (2019)
- [A unified variance-reduced accelerated gradient method for convex optimization](https://mlsanity.com/paper/1905.12412/) (2019)
- [Direct Acceleration of SAGA using Sampled Negative Momentum](https://mlsanity.com/paper/1806.11048/) (2018)

## Built on by (most cited first, 7 of 7)

- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2412.20017/) (2024)
- [Noise-Adaptive Layerwise Learning Rates: Accelerating Geometry-Aware Optimization for Deep Neural Network Training](https://mlsanity.com/paper/2510.14009/) (2025)
- [Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization](https://mlsanity.com/paper/2509.15399/) (2025)
- [A General Reduction for High-Probability Analysis with General Light-Tailed Distributions](https://mlsanity.com/paper/2403.02873/) (2024)
- [On the Convergence of Adam-Type Algorithm for Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2503.03908/) (2025)

## Abstract (arXiv)

The generalized smooth condition, (L0,L1)-smoothness, has triggered people's interest since it is more realistic in many optimization problems shown by both empirical and theoretical evidence. Two recent works established the O(ε-3) sample complexity to obtain an O(ε)-stationary point. However, both require a large batch size on the order of ploy(ε-1), which is not only computationally burdensome but also unsuitable for streaming applications. Additionally, these existing convergence bounds are established only for the expected rate, which is inadequate as they do not supply a useful performance guarantee on a single run. In this work, we solve the prior two problems simultaneously by revisiting a simple variant of the STORM algorithm. Specifically, under the (L0,L1)-smoothness and affine-type noises, we establish the first near-optimal O(log(1/(δε))ε-3) high-probability sample complexity where δ∈(0,1) is the failure probability. Besides, for the same algorithm, we also recover the optimal O(ε-3) sample complexity for the expected convergence with improved dependence on the problem-dependent parameter. More importantly, our convergence results only require a constant batch size in contrast to the previous works.