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

By Siyuan Ma, Raef Bassily, Mikhail Belkin. 2017

334 citations recorded by the source corpus.

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^*$ such that: (a) SGD iteration with mini-batch size $m\leq m^*$ is nearly equivalent to $m$ iterations of mini-batch size $1$ (\emph{linear scaling regime}). (b) SGD iteration with mini-batch $m> m^*$ 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.

Subfields: Artificial Intelligence, Computational Mechanics, 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

In Computational Mechanics

In Scaling & Learning Theory

Citations in the corpus

Measuring the Effects of Data Parallelism on Neural Network Training (2018, background): “Under assumptions including convexity, Ma et al. (2018) derive such a critical batch size, and argue that a batch size of one is optimal for minimizing the number of training epochs required to reach a given target error.”
Scaling Laws for Autoregressive Generative Modeling (2020, background): “This can be studied by identifying the critical batch size [MBB17, MKAT18] above which there are diminishing returns to further data parallelism.”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Modern machine learning models such as non-parametric regression or over-parametrized deep neural networks are highly expressive and can fit or interpolate the training dataset completely (Zhang et al., 2017; Ma et al., 2018).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, background): “Interpolation allows stochastic first-order methods to attain the convergence rates of their deterministic counterparts, without the need for explicit variance reduction (Vaswani et al., 2019a,b; Ma et al., 2018; Bassily et al., 2018).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “Indeed, recent works [5, 13, 33, 47, 52, 73, 83] have shown that when training over-parameterized models, classic SGD with a constant step-size and without VR can achieve the convergence rates of full-batch gradient descent.”
Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, background): “Thus, large inter-polating models can have low test risk and be easy to optimize at the same time, in particular with SGD [26].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “Our re-sults show that in overparametrized settings no drift effects occur and linear convergence can be achieved similar as to the centralized setting (Schmidt & Roux, 2013; Needell et al., 2016; Ma et al., 2018).”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, background): “Furthermore certain real-world data sets, it is well known that larger minibatches also lead to poor generalization and gradient saturation that lead to significant performance gaps between the ideal and practical speed up [12, 22, 41, 20].”
Local SGD Converges Fast and Communicates Little (2018, background): “Recent work in [11, 43] explores various limitations of this approach, as in general it is reported that performance degrades for too large mini-batch sizes [14, 19, 42].”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, methodology): “In particular, we make use of the fact that models such as non-parametric regression or overparameterized deep neural networks are expressive enough to fit or interpolate the training dataset completely [42, 22].”
SGD: General Analysis and Improved Rates (2019, methodology): “Thus our results are directly comparable to those developed in (Ma et al., 2018) and in (Vaswani et al.”
Does learning require memorization? a short tale about a long tail (2019, background): “has been suggested that interpolation is the result of computational benefits of optimization via SGD [33].”
On the Computational Inefficiency of Large Batch Sizes for Stochastic Gradient Descent (2018, background): “[21] showed theoretically that in convex, over-parameterized settings, the reduction in convergence time obtained by increasing the batch size decays dramatically to a near-constant level after a critical batch size that is independent of the dataset size.”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Exponential convergence of SGD for strongly convex losses in the interpolation setting has been established previously in [8].”
To understand deep learning we need to understand kernel learning (2018, background): “By a remarkably serendipitous coincidence, small mini-batch SGD can be shown to be exceptionally effective (nearly O(n) more effective than GD) for interpolated classifiers (Ma et al., 2017).”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “A line of research focused on analyzing gradient descent dynamics for (convolutional) neural networks with one or two unknown layers [Tian, 2017, Brutzkus and Globerson, 2017, Du et al., 2017a,b, Zhong et al., 2017, Li and Yuan, 2017, Ma et al., 2017, Brutzkus et al., 2017].”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “4).”
Batch Normalization Biases Residual Blocks Towards the Identity Function in Deep Networks (2020, background): “Intuitively, this transition occurs when we reach the maximum stable learning rate, above which training diverges [28].”