arXiv:2605.15314cs.LGmath.OC2026-05

提出新型优化方法,在噪声随距离增长时仍能高效收敛。

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

论文配图:Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise
图 1 · 摘自论文原文
  • 使用单次采样梯度的归一化动量法,适应非凸优化中的距离相关噪声。
  • 在理想条件下达到最优 $O(ε^{-4})$ 复杂度,优于传统方法。
  • 适用于标准光滑和广义光滑场景,无需固定域或增大批量。

研究在 Blum-Gladyshev(BG-0)噪声模型下的非凸随机优化问题,其中随机梯度方差随离初始化距离的平方增长。在标准光滑性和对称广义光滑性框架下,证明仅需每次迭代一个随机梯度的归一化 SGD 动量方法,可在 BG-0 噪声下实现 $O(ε^{-6})$ 的预言机复杂度。该速率在标准光滑与 $α$-对称广义光滑情形下均成立,表明广义光滑性在此设定中不影响收敛率。进一步研究了方差缩减的归一化 STORM 方法:在均方光滑性和尖锐初始化下,达到最小极大最优 $O(ε^{-4})$ 复杂度,匹配下界;在期望 $α$-对称广义光滑性下,递推式耦合梯度相关光滑性与距离相关噪声,导致复杂度为 $O(ε^{-(4+α)})$($α∈(0,1)$)和 $O(ε^{-5})$($α=1$)。当噪声的距增长参数为零时,结果退化为标准有界方差情形:动量法 $O(ε^{-4})$,方差缩减法 $O(ε^{-3})$,确定性情形 $O(ε^{-2})$。据我们所知,这是首个在无界域、不增大批量、无需显式锚定的前提下,对归一化方法在非凸随机优化中于 BG-0 噪声下的收敛保证,涵盖标准与广义光滑性设定。

原文摘要 · Abstract (English)

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

非凸优化随机梯度噪声建模收敛分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。