Stochastic Gradient Descent (SGD) with small mini-batch is a key component in modern large-scale machine learning. However, its efficiency has not been easy to analyze as most theoretical results require adaptive rates and show convergence rates far slower than that for gradient descent, making computational comparisons difficult. In this paper we aim to clarify the issue of fast SGD convergence. The key observation is that most modern 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, these regimes allow for very fast convergence of SGD, comparable in the number of iterations to gradient descent. Specifically, consider the setting with quadratic objective function, or near a minimum, where the quadratic term is dominant. We show that: (1) Mini-batch size $1$ with constant step size is optimal in terms of computations to achieve a given error. (2) There is a critical mini-batch size such that: (a. linear scaling) SGD iteration with mini-batch size $m$ smaller than the critical size is nearly equivalent to $m$ iterations of mini-batch size $1$. (b. saturation) SGD iteration with mini-batch larger than the critical size is nearly equivalent to a gradient descent step. 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, with the results closely following our theoretical analyses. Finally, we show how the interpolation perspective and our results fit with recent developments in training deep neural networks and discuss connections to adaptive rates for SGD and variance reduction.

本文旨在正式解释当代机器学习中观察到的SGD快速收敛现象。我们重点观察现代学习架构是过参数化的，并且被训练用于通过将经验损失（分类和回归）驱动到接近零的插值数据。我们表明，这些插值方案允许SGD快速收敛，与全梯度下降迭代次数相当。对于凸损失函数，我们获得了与全梯度下降相似的“迷你批次”SGD的指数收敛界限。关键的迷你批次大小可以视为有效迷你批次并行化的限制，并且几乎独立于数据大小。

插值的威力：理解SGD在现代超参模型学习中的有效性