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

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

    Apr 17, 2026Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1Stochastic OptimizationOracle Complexity

  2. Improved last-iterate bounds for SGD with and without replacement

    Nov 10, 2026Yimin Zhong, Jiaxin ZhouLast-Iterate ConvergenceStochastic Optimization Convergence