Precise limits on consistent convergence speed for noisy gradient descent

The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives

Machine Learning

Summary

This paper studies how quickly a common method called stochastic gradient descent (SGD) can reliably find good solutions when trying to minimize smooth convex functions, even when there is randomness or noise involved. The authors show that the best possible speed for consistent accuracy over time is very close to, but slightly slower than, a certain mathematical rate involving the square root of log n divided by n. They also describe exactly when such a speed can be achieved using specific schedules for running SGD and explain why other schedules cannot do better, even in very simple cases. This result sharpens our fundamental understanding of the limits of how fast SGD can reliably work under noise.

What this means in practice

A theory result. No direct application yet.

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.