A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
This work provides a theoretical foundation for SGD's optimality in least squares, which is incremental as it simplifies existing proofs.
The paper tackled the problem of proving the statistical minimax optimality of stochastic gradient descent (SGD) for least squares, achieving a simplified proof by analyzing SGD as a stochastic process and characterizing its stationary covariance matrix.
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.