math.OCMay 23, 2025

Bias-Optimal Bounds for Stochastic Gradient Descent

Authors: Daniel Cortild, Lucas Ketels, Juan Peypouquet, Guillaume Garrigos

Organizations: University of Oxford, Mathematical Institute, Woodstock Road, OX2 6GG Oxford, United Kingdom · University of Groningen, Bernoulli Institute, Bernouilliborg, 9747AG Groningen, Netherlands · Université Paris Cité and Sorbonne Université, CNRS, Laboratoire de Probabilités, Statistique et Modélisation, F-75013 Paris, France

Abstract

The non-asymptotic analysis of Stochastic Gradient Descent (SGD) typically yields bounds that decompose into a bias term and a variance term. In this work, we focus on the bias component and study the extent to which SGD can match the optimal convergence behavior of deterministic gradient descent. Assuming only (strong) convexity and smoothness of the objective, we derive new bounds for the full range of constant step-sizes γL∈(0,2)γL \in (0,2). This includes critical and large step-size regimes that were previously unexplored without additional variance assumptions, in both the convex and strongly convex cases. Those bounds are bias-optimal, in the sense that the bias term coincides with the worst-case rate of gradient descent, for all non-critical step-sizes. For critical step-sizes, we show that no bounds can be obtained with an optimal bias term, but that this optimal bias can be approximated arbitrarily closely. As an immediate application, we provide new complexity bounds for the Stochastic Proximal algorithm, without the need of regularity assumptions.

Explore similar work

Sep 24, 2026

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

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/3T^{-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ε−6Lb_2Δ^3\varepsilon^{-6} and LΔσ2ε−4LΔσ^2\varepsilon^{-4} stochastic terms, where ΔΔ is the initial objective gap and σ2+b2∥x−x1∥2σ^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>2p>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-TT stationarity, and stochastic LpL^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.
Apr 17, 2026

Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

Analysis of Stochastic Gradient Descent (SGD) and its variants typically relies on the assumption of uniformly bounded variance, a condition that frequently fails in practical non-convex settings, such as neural network training, as well as in several elementary optimization settings. While several relaxations are explored in the literature, the Blum-Gladyshev (BG-0) condition, which permits the variance to grow quadratically with distance has recently been shown to be the weakest condition. However, the study of the oracle complexity of stochastic first-order non-convex optimization under BG-0 has remained underexplored. In this paper, we address this gap and establish information-theoretic lower bounds, proving that finding an εε-stationary point requires Ω(ε−6)Ω(ε^{-6}) stochastic BG-0 oracle queries for smooth functions and Ω(ε−4)Ω(ε^{-4}) queries under mean-square smoothness. These limits demonstrate an unavoidable degradation from classical bounded-variance complexities, i.e., Ω(ε−4)Ω(ε^{-4}) and Ω(ε−3)Ω(ε^{-3}) for smooth and mean-square smooth cases, respectively. To match these lower bounds, we consider Proximally Anchored STochastic Approximation (PASTA), a unified algorithmic framework that couples Halpern anchoring with Tikhonov regularization to dynamically mitigate the extra variance explosion term permitted by the BG-0 oracle. We prove that PASTA achieves minimax optimal complexities across numerous non-convex regimes, including standard smooth, mean-square smooth, weakly convex, star-convex, and Polyak-Lojasiewicz functions, entirely under an unbounded domain and unbounded stochastic gradients.
Nov 10, 2026

Improved last-iterate bounds for SGD with and without replacement

In this work, we study last-iterate convergence bounds for stochastic gradient descent (SGD) on convex and ββ-smooth loss functions and improve the bound from \cO((log⁡T)3/T)\cO((\log T)^3/T) to \cO((log⁡T)3/(Tlog⁡log⁡T))\cO((\log T)^3/(T\log\log T)) in the interpolation regime. The improvement comes from applying a horizon-dependent multiscale estimate of gradients to the comparison of trajectories. The bound applies to both sampling with replacement and sampling without replacement within one pass.