Convergence of Gradient Descent on Separable Data

Abstract

We provide a detailed study on the implicit bias of gradient descent when optimizing loss functions with strictly monotone tails, such as the logistic loss, over separable datasets. We look at two basic questions: (a) what are the conditions on the tail of the loss function under which gradient descent converges in the direction of the $L_2$ maximum-margin separator? (b) how does the rate of margin convergence depend on the tail of the loss function and the choice of the step size? We show that for a large family of super-polynomial tailed losses, gradient descent iterates on linear networks of any depth converge in the direction of $L_2$ maximum-margin solution, while this does not hold for losses with heavier tails. Within this family, for simple linear models we show that the optimal rates with fixed step size is indeed obtained for the commonly used exponentially tailed losses such as logistic loss. However, with a fixed step size the optimal convergence rate is extremely slow as $1/\log (t)$, as also proved in Soudry et al. (2018). For linear models with exponential loss, we further prove that the convergence rate could be improved to $\log (t)/\sqrt{t}$ by using aggressive step sizes that compensates for the rapidly vanishing gradients. Numerical results suggest this method might be useful for deep networks.

arXiv commentAISTATS Camera ready version

References in corpus (8)

• Train longer, generalize better: closing the generalization gap in large batch training of neural networks
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Gradient descent aligns the layers of deep linear networks
• Risk and parameter convergence of logistic regression
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate
• Margins, Shrinkage, and Boosting
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?

Cited by in corpus (14)

• The Modern Mathematics of Deep Learning
• Risk and parameter convergence of logistic regression
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• Minnorm training: an algorithm for training over-parameterized deep neural networks
• The Implicit Bias of Depth: How Incremental Learning Drives Generalization
• On Dropout and Nuclear Norm Regularization
• To Each Optimizer a Norm, To Each Norm its Generalization
• On generalization bounds for deep networks based on loss surface implicit regularization
• Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods
• Implicit bias of deep linear networks in the large learning rate phase
• Dissecting Supervised Contrastive Learning
• Implicitly Maximizing Margins with the Hinge Loss