Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate

Abstract

Stochastic Gradient Descent (SGD) is a central tool in machine learning. We prove that SGD converges to zero loss, even with a fixed (non-vanishing) learning rate - in the special case of homogeneous linear classifiers with smooth monotone loss functions, optimized on linearly separable data. Previous works assumed either a vanishing learning rate, iterate averaging, or loss assumptions that do not hold for monotone loss functions used for classification, such as the logistic loss. We prove our result on a fixed dataset, both for sampling with or without replacement. Furthermore, for logistic loss (and similar exponentially-tailed losses), we prove that with SGD the weight vector converges in direction to the $L_2$ max margin vector as $O(1/\log (t))$ for almost all separable datasets, and the loss converges as $O(1/t)$ - similarly to gradient descent. Lastly, we examine the case of a fixed learning rate proportional to the minibatch size. We prove that in this case, the asymptotic convergence rate of SGD (with replacement) does not depend on the minibatch size in terms of epochs, if the support vectors span the data. These results may suggest an explanation to similar behaviors observed in deep networks, when trained with SGD.

Fixed a typo (Eq. (4) - missing σ_{max}^2 term in the denominator)

Cited by in corpus (21)

• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• Gradient Descent Maximizes the Margin of Homogeneous Neural Networks
• Towards Understanding the Spectral Bias of Deep Learning
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Convergence of Gradient Descent on Separable Data
• Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• When Will Gradient Methods Converge to Max-margin Classifier under ReLU Models?
• A Unifying View on Implicit Bias in Training Linear Neural Networks
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Exploring Weight Importance and Hessian Bias in Model Pruning
• Implicit Gradient Regularization
• The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networks
• On the Power of Differentiable Learning versus PAC and SQ Learning
• Why to "grow" and "harvest" deep learning models?
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks
• Gradient Methods Never Overfit On Separable Data
• Directional Convergence Analysis under Spherically Symmetric Distribution