The Implicit Bias of Gradient Descent on Separable Data
By Daniel Soudry, Elad Hoffer, Suriya Gunasekar, Nati Srebro. 2017
1,145 citations recorded by the source corpus.
We examine gradient descent on unregularized logistic regression problems, with homogeneous linear predictors on linearly separable datasets. We show the predictor converges to the direction of the max-margin (hard margin SVM) solution. The result also generalizes to other monotone decreasing loss functions with an infimum at infinity, to multi-class problems, and to training a weight layer in a deep network in a certain restricted setting. Furthermore, we show this convergence is very slow, and only logarithmic in the convergence of the loss itself. This can help explain the benefit of continuing to optimize the logistic or cross-entropy loss even after the training error is zero and the training loss is extremely small, and, as we show, even if the validation loss increases. Our methodology can also aid in understanding implicit regularization n more complex models and with other optimization methods.
Subfields: Artificial Intelligence, Optimization & Training, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Percy Liang
- Sergey Levine
- Quoc V. Le
- Ruslan Salakhutdinov
- Mohit Bansal
- Jianfeng Gao
- Dacheng Tao
In Optimization & Training
- Yuanzhi Li
- Jason D. Lee
- Tengyu Ma
- Zeyuan Allen-Zhu
- Simon Lacoste-Julien
- Sebastian U. Stich
- Simon Shaolei Du
- Martin Jaggi
In Scaling & Learning Theory
Citations in the corpus
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “This is important when using loss functions such as the logistic loss for which the infimum is achieved at infinity (Soudry et al., 2018).”
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “For linearly separable datasets, [55, 27, 14, 32, 33] show that first-order methods find solutions that generalize well without an explicit regularization for logistic regression.”
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Recent studies are on SGD for different tasks, such as logistic regression [27] and matrix factorization [11, 19, 16].”
- Error Feedback Fixes SignSGD and other Gradient Compression Schemes (2019, methodology): “We borrow following definition from Stich et al. [2018]. Assumption A (Compressor).”
- An Empirical Study of Example Forgetting during Deep Neural Network Learning (2018, background): “This goes along the support vector interpretation provided by Soudry et al. (2017).”
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…established that first-order methods can automatically find minimum-norm/maximum-margin solutions that fit the data in the settings of logistic regression, deep linear networks, and symmetric matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018a,b; Ji & Telgarsky, 2018; Li et al., 2018b).”
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Assumption 3.1 has been widely made in the studies of training binary classifiers (Soudry et al., 2017; Nacson et al., 2018; Ji and Telgarsky, 2018).”
- Does learning require memorization? a short tale about a long tail (2019, methodology): “Note that algorithms with this property are easy to implement efficiently via SGD on the cross-entropy loss [SHNGS18] and also via simple regularization of the Perceptron algorithm [SSS05].”
- Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks (2019, background): “There are also several recent works on implicit regularization of gradient descent that establish convergence to some idealized solution under particular choices of learning rate [27, 36, 1, 7, 26].”
- On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Furthermore, the distance to minimizer can be infinite in many important settings, including optimization via logistic loss [12] or inverse problems over Hilbert spaces, as in kernel methods [9].”
- Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “The result in Soudry et al. [2017] holds for any loss function `(u, y) that is strictly monotone in uy with specific tail behavior, name the tightly exponential tail, which is satisfied by popular classification losses like logistic and exponential loss.”
- On the Spectral Bias of Neural Networks (2018, background): “Our work more directly follows the line of research on implicit regularization in neural networks trained by gradient descent (Neyshabur et al., 2014; Soudry et al., 2017; Poggio et al., 2018; Neyshabur et al., 2017).”