Fetching the paper…

Reading the bibliography…

Gradient Methods Never Overfit On Separable Data · Around

2020

Gradient Methods Never Overfit On Separable Data

Shamir, Ohad

Original
PDF
Post on X

Understand

A line of recent works established that when training linear predictors over separable data, using gradient methods and exponentially-tailed losses, the predictors asymptotically converge in direction to the max-margin predictor.

As a consequence, the predictors asymptotically do not overfit.
However, this does not address the question of whether overfitting might occur non-asymptotically, after some bounded number of iterations.
In this paper, we formally show that standard gradient methods (in particular, gradient flow, gradient descent and stochastic gradient descent) never overfit on separable data: If we run these methods for $T$ iterations on a dataset of size $m$, both the empirical risk and the generalization error decrease at an essentially optimal rate of $\tilde{\mathcal{O}}(1/\gamma^2 T)$ up till $T\approx m$, at which point the generalization error remains fixed at an essentially optimal level of $\tilde{\mathcal{O}}(1/\gamma^2 m)$ regardless of how large $T$ is.

Built on

A refined primal-dual analysis of the implicit bias
Original
Ziwei Ji and Matus Telgarsky · 1906
Earlier work this paper cites.
Simplified pac-bayesian margin bounds
David McAllester · 2003
Earlier work this paper cites.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Earlier work this paper cites.

Similar

Characterizing implicit bias in terms of optimization geometry
Suriya Gunasekar · 2018
Cited alongside, same era.
Implicit bias of gradient descent on linear convolutional networks
Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro · 2018
Cited alongside, same era.
Lectures on convex optimization , volume 137
Yurii Nesterov · 2018
Cited alongside, same era.
Gradient descent aligns the layers of deep linear networks
Ziwei Ji and Matus Telgarsky
Cited in the paper.
Risk and parameter convergence of logistic regression
Original
Ziwei Ji and Matus Telgarsky
Cited in the paper.
Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks
Ziwei Ji and Matus Telgarsky
Cited in the paper.
Convergence of gradient descent on separable data
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry
Cited in the paper.
Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry
Cited in the paper.

Then

The implicit bias of gradient descent on separable data
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro · 2018
Later among the works it cites.
Gradient descent follows the regularization path for general losses
Miroslav Dudik, Ziwei Ji, Robert Schapire, and Matus Telgarsky · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…