Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
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 Lb2Δ3ε−6 and LΔσ2ε−4 stochastic terms, where Δ is the initial objective gap and σ2+b2|x−x1|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 Lp-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
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
- Asymptotic Analysis of Gradient Mapping-type Stationarity Measure for the Sum of Nonconvex Nonsmooth Functions and Applications to Proximal Gradient-type Algorithms
- Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
- Norm-Cone Conjugation for Nonconvex Optimization: Scalar Duality and Exact Distance Penalization
- On the Regularization of Primal-Dual Dynamics in Time-Dependent Nonconvex Optimization
BibTeX
@misc{wu2026ordinary,
title = {{Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds}},
author = {Wei Biao Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30499},
eprint = {2609.30499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30499},
}
RIS
TY - UNPB
TI - Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds
AU - Wei Biao Wu
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2609.30499
UR - https://arxiv.org/abs/2609.30499
AB - 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Δ^3ε^−6 and LΔσ^2ε^−4 stochastic terms, where Δ is the initial objective gap and σ^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.
ER -