A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)

Abstract

This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The finite rate optimality characterization captures the constant factors and addresses model mis-specification.

Lemma 1 has been updated in v2

Cited by in corpus (8)

• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• On the Double Descent of Random Features Models Trained with SGD
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression