> Details

Jain, Prateek [Author]; Kakade, Sham M. [Author]; Kidambi, Rahul [Author]; Netrapalli, Praneeth [Author]; Pillutla, Venkata Krishna [Author]; Sidford, Aaron [Author] ; Prateek Jain and Sham M. Kakade and Rahul Kidambi and Praneeth Netrapalli and Venkata Krishna Pillutla and Aaron Sidford [Contributor]

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

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
  • Contributor: Jain, Prateek [Author]; Kakade, Sham M. [Author]; Kidambi, Rahul [Author]; Netrapalli, Praneeth [Author]; Pillutla, Venkata Krishna [Author]; Sidford, Aaron [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.FSTTCS.2017.2
  • Keywords: Least Squares Regression ; Minimax Optimality ; Stochastic Gradient Descent
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access