The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning

Abstract

In this paper we aim to formally explain the phenomenon of fast convergence of SGD observed in modern machine learning. The key observation is that most modern learning architectures are over-parametrized and are trained to interpolate the data by driving the empirical loss (classification and regression) close to zero. While it is still unclear why these interpolated solutions perform well on test data, we show that these regimes allow for fast convergence of SGD, comparable in number of iterations to full gradient descent. For convex loss functions we obtain an exponential convergence bound for {\it mini-batch} SGD parallel to that for full gradient descent. We show that there is a critical batch size $m^{\ast }$ such that: (a) SGD iteration with mini-batch size $m\le m^{\ast }$ is nearly equivalent to $m$ iterations of mini-batch size $1$ (\emph{linear scaling regime}). (b) SGD iteration with mini-batch $m>m^{\ast }$ is nearly equivalent to a full gradient descent iteration (\emph{saturation regime}). Moreover, for the quadratic loss, we derive explicit expressions for the optimal mini-batch and step size and explicitly characterize the two regimes above. The critical mini-batch size can be viewed as the limit for effective mini-batch parallelization. It is also nearly independent of the data size, implying $O(n)$ acceleration over GD per unit of computation. We give experimental evidence on real data which closely follows our theoretical analyses. Finally, we show how our results fit in the recent developments in training deep neural networks and discuss connections to adaptive rates for SGD and variance reduction.

Cited by in corpus (64)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Prevalence of Neural Collapse during the terminal phase of deep learning training
• Local SGD Converges Fast and Communicates Little
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Measuring the Effects of Data Parallelism on Neural Network Training
• To understand deep learning we need to understand kernel learning
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• Batch Normalization Biases Residual Blocks Towards the Identity Function in Deep Networks
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Understanding and Mitigating the Tradeoff Between Robustness and Accuracy
• Accelerating SGD with momentum for over-parameterized learning
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• On the Computational Inefficiency of Large Batch Sizes for Stochastic Gradient Descent
• On the Origin of Implicit Regularization in Stochastic Gradient Descent
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• SGD: General Analysis and Improved Rates
• Multiplicative noise and heavy tails in stochastic optimization
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Bad Global Minima Exist and SGD Can Reach Them
• Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization
• On the Adaptivity of Stochastic Gradient-Based Optimization
• PCONV: The Missing but Desirable Sparsity in DNN Weight Pruning for Real-time Execution on Mobile Devices
• Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Communication-efficient distributed SGD with Sketching
• Stochastic Weight Averaging in Parallel: Large-Batch Training that Generalizes Well
• Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Logarithmic Pruning is All You Need
• Interpolating Predictors in High-Dimensional Factor Regression
• Stochastic Training is Not Necessary for Generalization
• Training Neural Networks for and by Interpolation
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• An Image Enhancing Pattern-based Sparsity for Real-time Inference on Mobile Devices
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
• Distributed Optimization for Over-Parameterized Learning
• Drawing Multiple Augmentation Samples Per Image During Training Efficiently Decreases Test Error
• Empirical Risk Minimization in the Interpolating Regime with Application to Neural Network Learning
• Inefficiency of K-FAC for Large Batch Size Training
• Explicit Regularization of Stochastic Gradient Methods through Duality
• Stochastic Reweighted Gradient Descent
• Which Minimizer Does My Neural Network Converge To?
• On Large-Cohort Training for Federated Learning
• Student Specialization in Deep ReLU Networks With Finite Width and Input Dimension
• On Riemannian Stochastic Approximation Schemes with Fixed Step-Size
• On the Last Iterate Convergence of Momentum Methods
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• How Data Augmentation affects Optimization for Linear Regression
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates
• Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
• Learning Curves for SGD on Structured Features
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Batch size-invariance for policy optimization
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs
• Comments on Leo Breiman's paper 'Statistical Modeling: The Two Cultures' (Statistical Science, 2001, 16(3), 199-231)