arXiv:2605.15314 · v2

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

超越有界方差：Blum-Gladyshev 噪声下非凸优化的方差缩减归一化方法

首次提交 2026-05-15 02:27

版本更新 2026-11-13 02:07

雷达观测 2026-11-13 14:15

摘要

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.

期刊信息：Neural Information Processing Systems, NeurIPS 2026