The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Abstract
We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to √(log n / n) but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence h satisfying h(n) = o(√n), a bound of order h(n)/√n, holding simultaneously for all n with probability at least 1−α and uniformly over the problem class, is achievable if and only if ∑j = 1∞ 1/h(2j)2 < ∞. The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
Related
- Differential Privacy of Gradient Descent on Perturbed Objectives
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- Convergence rate of stochastic gradient descent under Łojasiewicz type condition and polynomially controlled noise
- Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization
- Continuous Delayed-Memory Stochastic Gradient Descent and Continuous-Time Reinforcement Learning from History of Astrophysical Time Series Studies
BibTeX
@misc{li2026exact,
title = {{The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives}},
author = {Ruijie Li and Kang Chen and Tianyu Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08537},
eprint = {2609.08537},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08537},
}
RIS
TY - UNPB
TI - The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
AU - Ruijie Li
AU - Kang Chen
AU - Tianyu Wang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08537
UR - https://arxiv.org/abs/2609.08537
AB - We study the time-uniform convergence of the raw iterate of standard stochastic gradient descent (SGD) for unconstrained smooth convex objectives. We prove that, under standard noise assumptions, the time-uniform convergence rate gets arbitrarily close to √(log n / n) but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence h satisfying h(n) = o(√n), a bound of order h(n)/√n, holding simultaneously for all n with probability at least 1−α and uniformly over the problem class, is achievable if and only if ∑_j = 1^∞ 1/h(2^j)^2 < ∞. The constructive sufficiency result follows from a dyadic horizon-free schedule together with an additive conditional-restart inequality. The necessity counterpart applies to every deterministic nonnegative schedule and holds even for a one-dimensional analytic smooth convex objective with Gaussian noise.
ER -