The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Overparametrized Learning
[edit]
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:33253334, 2018.
Abstract
In this paper we aim to formally explain the phenomenon of fast convergence of Stochastic Gradient Descent (SGD) observed in modern machine learning. The key observation is that most modern learning architectures are overparametrized 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 minibatch SGD parallel to that for full gradient descent. We show that there is a critical batch size $m^*$ such that: (a) SGD iteration with minibatch size $m\leq m^*$ is nearly equivalent to $m$ iterations of minibatch size $1$ (linear scaling regime). (b) SGD iteration with minibatch $m> m^*$ is nearly equivalent to a full gradient descent iteration (saturation regime). Moreover, for the quadratic loss, we derive explicit expressions for the optimal minibatch and step size and explicitly characterize the two regimes above. The critical minibatch size can be viewed as the limit for effective minibatch 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.
Related Material


