arXiv：cs.LG· Wei Biao Wu·· 6 小时前AI 评分33
普通非凸 SGD 在距离相关矩下的有限时域稳定性与 Nagaev 界
Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
AI 导读
研究在距离相关条件矩下普通单样本随机梯度下降的收敛性，仅用二阶矩即证明期望平均梯度平方达到 T^{-1/3} 稳定性，显式复杂度推论匹配已知光滑 Blum-Gladyshev (BG-0) 下界。对 p>2 情形，通过可预测局部化与 Hilbert 空间 Fuk-Nagaev 不等式给出高概率界，分离对数方差与多项式稀有冲击贡献，局部化半径由递推导出，无需有界迭代、裁剪、归一化、动量或增大批量。
正文
Abstract:Uniform noise-moment bounds exclude stochastic gradients whose variability increases with the iterate. We study ordinary, single-sample stochastic gradient descent for smooth, lower-bounded, possibly nonconvex objectives under distance-dependent conditional moments. Under second moments alone, a direct descent--displacement argument yields $T^{-1/3}$ expected average squared-gradient stationarity with a horizon-dependent stepsize. An explicit oracle-complexity corollary matches the known smooth Blum--Gladyshev (BG-0) lower bound, including the $Lb_2\Delta^3\varepsilon^{-6}$ and $L\Delta\sigma^2\varepsilon^{-4}$ stochastic terms, where $\Delta$ is the initial objective gap and $\sigma^2+b_2\|x-x_1\|^2$ bounds the variance. Thus unchanged SGD attains the minimax stochastic complexity in this second-moment class. For $p>2$, predictable localization and a Hilbert-space Fuk--Nagaev inequality yield a high-probability bound separating logarithmic variance and polynomial rare-shock contributions. The localization radius is derived from the recursion: no bounded-iterate assumption, clipping, normalization, momentum, or increasing batch size is needed. We also give increasing-confidence rates, an objective-gap-growth refinement recovering root-$T$ stationarity, and stochastic $L^p$-Lipschitz examples. The broad BG-0 optimality statement is distinguished from the smaller mean-square-smooth class, in which additional oracle structure permits faster algorithms.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| MSC classes: | Primary 62L20, Secondary 60E15, 60G42, 90C15, 90C26 |
| Cite as: | arXiv:2609.30499 [stat.ML] |
| (or arXiv:2609.30499v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2609.30499 arXiv-issued DOI via DataCite |
Submission history
From: Wei Biao Wu [view email]
[v1]
Thu, 24 Sep 2026 19:37:07 UTC (28 KB)
[v2]
Wed, 7 Oct 2026 03:17:45 UTC (37 KB)
来源：arXiv：cs.LG · arxiv.org