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

By Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Krishna Pillutla, Aaron Sidford. 2017

41 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Robust Aggregation for Federated Learning (2019, methodology): “We now analyze RFA where the local SGD updates are equipped with “tail-averaging” [44] so that w(t+1)i = (2/τ) ∑τ k=τ/2w (t) i,k is averaged over the latter half of the trajectory of iterates instead of line 8 of Algorithm 1.”
Parallelizing Stochastic Gradient Descent for Least Squares Regression: Mini-batching, Averaging, and Model Misspecification (2016, methodology): “Refer to Jain et al. (2017b) for more details.”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “…that present a non-asymptotic understanding of SGD for least squares regression, with the caveat being that these results crucially rely on iterate averaging with constant stepsize sequences (Bach and Moulines, 2013; D ´ efossez and Bach, 2015; Jain et al., 2016, 2017b,a; Neu and Rosasco, 2018).”