Precise limits on consistent convergence speed for noisy gradient descent
The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
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
- •For machine learning engineers: Set rigorous performance expectations for iterative optimization when tuning SGD parameters under noisy conditions.
- •For statistical signal processors: Identify fundamental convergence limits when applying stochastic gradient algorithms to smooth convex problems with Gaussian noise.
A theory result. No direct application yet.