Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression

  • 2021-10-12 17:49:54
  • Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, Sham M. Kakade
  • 0

Abstract

Stochastic gradient descent (SGD) has been demonstrated to generalize well inmany deep learning applications. In practice, one often runs SGD with ageometrically decaying stepsize, i.e., a constant initial stepsize followed bymultiple geometric stepsize decay, and uses the last iterate as the output.This kind of SGD is known to be nearly minimax optimal for classicalfinite-dimensional linear regression problems (Ge et al., 2019), and provablyoutperforms SGD with polynomially decaying stepsize in terms of the statisticalminimax rates. However, a sharp analysis for the last iterate of SGD withdecaying step size in the overparameterized setting is still open. In thispaper, we provide problem-dependent analysis on the last iterate risk bounds ofSGD with decaying stepsize, for (overparameterized) linear regression problems.In particular, for SGD with geometrically decaying stepsize (or tailgeometrically decaying stepsize), we prove nearly matching upper and lowerbounds on the excess risk. Our results demonstrate the generalization abilityof SGD for a wide class of overparameterized problems, and can recover theminimax optimal results up to logarithmic factors in the classical regime.Moreover, we provide an excess risk lower bound for SGD with polynomiallydecaying stepsize and illustrate the advantage of geometrically decayingstepsize in an instance-wise manner, which complements the minimax ratecomparison made in previous work.

 

Quick Read (beta)

loading the full paper ...