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

DOI10.4230/LIPIcs.FSTTCS.2017.2zbMath1496.62140arXiv1710.09430MaRDI QIDQ5136291

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

Publication date: 25 November 2020

Full work available at URL: https://arxiv.org/abs/1710.09430

zbMATH Keywords

least squares regressionstochastic gradient descentminimax optimality

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Quadratic programming (90C20) Stochastic programming (90C15) Stochastic approximation (62L20)

Related Items (1)

On the regularization effect of stochastic gradient descent applied to least-squares

Cites Work

• Unnamed Item
• Unnamed Item
• Nonparametric stochastic approximation with large step-sizes
• Stochastic approximation methods for constrained and unconstrained systems
• Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression
• Acceleration of Stochastic Approximation by Averaging

This page was built for publication: A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)