Last Iterate Risk Bounds of SGD with Decaying Stepsize for
  Overparameterized Linear Regression
  Stochastic gradient descent (SGD) has been demonstrated to generalize well in
many deep learning applications. In practice, one often runs SGD with a
geometrically decaying stepsize, i.e., a constant initial stepsize followed by
multiple geometric stepsize decay, and uses the last iterate as the output.
This kind of SGD is known to be nearly minimax optimal for classical
finite-dimensional linear regression problems (Ge et al., 2019), and provably
outperforms SGD with polynomially decaying stepsize in terms of the statistical
minimax rates. However, a sharp analysis for the last iterate of SGD with
decaying step size in the overparameterized setting is still open. In this
paper, we provide problem-dependent analysis on the last iterate risk bounds of
SGD with decaying stepsize, for (overparameterized) linear regression problems.
In particular, for SGD with geometrically decaying stepsize (or tail
geometrically decaying stepsize), we prove nearly matching upper and lower
bounds on the excess risk. Our results demonstrate the generalization ability
of SGD for a wide class of overparameterized problems, and can recover the
minimax optimal results up to logarithmic factors in the classical regime.
Moreover, we provide an excess risk lower bound for SGD with polynomially
decaying stepsize and illustrate the advantage of geometrically decaying
stepsize in an instance-wise manner, which complements the minimax rate
comparison made in previous work.
