Exact uniform convergence limits for stochastic gradient descent rates
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
Machine Learning
Summary
This paper looks at how the accuracy of a common optimization method called stochastic gradient descent (SGD) improves over time when applied to smooth and convex problems. The authors find that while the error rate gets very close to a certain mathematical limit involving logarithms and square roots, it never actually reaches it. They also discover precise conditions under which a specific rate can be guaranteed for all time steps with high probability. Importantly, their results apply even in simple one-dimensional cases with noise, showing that the limits they identify are fundamental.
stochastic gradient descentsmooth convex optimizationtime-uniform convergenceconvergence rateprobability boundsnoise assumptionsoptimization scheduleconvex objectiveGaussian noise
Authors
Ruijie Li, Kang Chen, Tianyu Wang
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 $\sqrt{\log n / n}$ but never reaches it. More specifically, we prove that for every positive, eventually nondecreasing sequence $h$ satisfying $h(n) = o(\sqrt{n})$, a bound of order $h(n)/\sqrt{n}$, holding simultaneously for all $n$ with probability at least $1-α$ and uniformly over the problem class, is achievable if and only if \[ \sum_{j = 1}^{\infty} \frac{1}{h(2^j)^2} < \infty. \] 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.