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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 46 references that are in the map.
- First posted on arXiv 14 May 2026.

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

- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms](https://mlsanity.com/paper/1810.10690/) (2018)
- [Accelerated stochastic approximation with state-dependent noise](https://mlsanity.com/paper/2307.01497/) (2023)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)

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

- [Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds](https://mlsanity.com/paper/2609.30499/) (2026)
- [Why Does Adaptive Batching Help LLM Pretraining? A Perspective from Unbounded Variance](https://mlsanity.com/paper/2610.02355/) (2026)

## Abstract (arXiv)

We study nonconvex stochastic optimization under the Blum-Gladyshev (mathsfBG-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 mathsfBG-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 α∈(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 mathsfBG-0 noise without bounded domains, increasing batch sizes, or explicit anchoring, covering both standard and generalized smoothness regimes.