Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
Abstract
This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension d≥ N+1, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of N stepsizes in [0,1.5]N. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least Ω(1/√N), our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
Related
- Optimal Recursive Composition and Dyadic Phase Laws for Gradient Descent with Predetermined Stepsizes
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case
BibTeX
@misc{grimmer2026exact,
title = {{Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization}},
author = {Benjamin Grimmer and Qining Shen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42048},
eprint = {2610.42048},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42048},
}
RIS
TY - UNPB
TI - Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
AU - Benjamin Grimmer
AU - Qining Shen
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42048
UR - https://arxiv.org/abs/2610.42048
AB - This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension d≥ N+1, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of N stepsizes in [0,1.5]^N. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least Ω(1/√N), our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.
ER -