Title: 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.