Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds

arXiv:2609.30499v1 Announce Type: cross 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_2Delta^3arepsilon^{-6} and LDeltasigma^2arepsilon^{-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.

Related

• In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
• New Bounds for the Last Iterate of the Stochastic subGradient Method
• Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

Source: arXiv cs.LG | 2026-09-28