  Stochastic gradient descent (SGD) exhibits strong algorithmic regularization
effects in practice, which has been hypothesized to play an important role in
the generalization of modern machine learning approaches. In this work, we seek
to understand these issues in the simpler setting of linear regression
(including both underparameterized and overparameterized regimes), where our
goal is to make sharp instance-based comparisons of the implicit regularization
afforded by (unregularized) average SGD with the explicit regularization of
ridge regression. For a broad class of least squares problem instances (that
are natural in high-dimensional settings), we show: (1) for every problem
instance and for every ridge parameter, (unregularized) SGD, when provided with
logarithmically more samples than that provided to the ridge algorithm,
generalizes no worse than the ridge solution (provided SGD uses a tuned
constant stepsize); (2) conversely, there exist instances (in this wide problem
class) where optimally-tuned ridge regression requires quadratically more
samples than SGD in order to have the same generalization performance. Taken
together, our results show that, up to the logarithmic factors, the
generalization performance of SGD is always no worse than that of ridge
regression in a wide range of overparameterized problems, and, in fact, could
be much better for some problem instances. More generally, our results show how
algorithmic regularization has important consequences even in simpler
(overparameterized) convex settings.
