Timezone: »

 
Poster
The Benefits of Implicit Regularization from SGD in Least Squares Problems
Difan Zou · Jingfeng Wu · Vladimir Braverman · Quanquan Gu · Dean Foster · Sham Kakade

Thu Dec 09 04:30 PM -- 06:00 PM (PST) @
in Poster Session 7 »

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 \emph{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 \emph{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.

Keywords: Optimization · Machine Learning

Author Information

Difan Zou (University of California, Los Angeles)
Jingfeng Wu (Johns Hopkins University)
Vladimir Braverman (Johns Hopkins University)
Quanquan Gu (UCLA)
Dean Foster (Amazon.com (NYC))
Sham Kakade (Harvard University & Microsoft Research)

More from the Same Authors