no. 14 · Friday 13 November 2026
Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise
Abstract
Stochastic optimization theory often assumes that gradient noise has uniformly bounded variance. However, this assumption can be inadequate even in simple settings; e.g., it does not hold for linear least squares regression. The Blum-Gladyshev ($\mathsf{BG}$-0) noise model instead allows the stochastic gradient variance to grow quadratically with the distance from the initialization and has recently been identified as the weakest known viable variance assumption. We study nonconvex stochastic optimization under $\mathsf{BG}$-0 noise and prove that normalized momentum converges with one stochastic gradient per iteration, reaching an $\varepsilon$-stationary point with the optimal $O(\varepsilon^{-6})$ complexity. We then show that, under mean-square smoothness, a variance-reduced normalized STORM method achieves the minimax optimal complexity of $O(\varepsilon^{-4})$. We further extend our analysis to the symmetric generalized smoothness framework, which captures objectives whose local curvature can scale with the gradient norm. To our knowledge, these are the first convergence guarantees for normalized methods in nonconvex stochastic optimization under $\mathsf{BG}$-0 noise without bounded domains.
- journal
- Neural Information Processing Systems, NeurIPS 2026
- fields
- Optimization and Control