← Research

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

Antesh Upadhyay, Arda Fazla, Abolfazl Hashemi

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.

PDF ↗

Models

Loading
EVIDENCE / COMPARISON

Benchmarks

Explore every benchmark

Loading

These charts contain model-linked results. The charts above also include unlinked source profiles. Compare scores within each evaluation. Model quality, usage, transparency and system performance measure different things.

Install TensorTrace