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

**Authors:** Siyuan Ma, Raef Bassily, Mikhail Belkin  
**arXiv:** [1712.06559](https://arxiv.org/abs/1712.06559)  
**Date:** 2017-12-18  
**Summary page:** https://www.summarizepaper.com/en/paper/1712.06559v1/

## Key points

- The paper explores the efficiency and convergence properties of Stochastic Gradient Descent (SGD) with small mini-batches in large-scale machine learning.
- Most modern architectures are over-parametrized and trained to interpolate the data, driving the empirical loss close to zero.
- Interpolated solutions enable very fast convergence of SGD, comparable to gradient descent in terms of iterations.
- Mini-batch size 1 with a constant step size is optimal in terms of computations required to achieve a given error.
- There exists a critical mini-batch size that determines the behavior of SGD iterations: smaller sizes are nearly equivalent to multiple iterations with mini-batch size 1, while larger sizes are nearly equivalent to gradient descent steps.
- The critical mini-batch size is independent of data size and implies an acceleration over gradient descent per unit computation complexity by O(n).
- Experimental evidence on real data supports the theoretical analyses.
- The results have implications for training deep neural networks and connections to adaptive rates for SGD and variance reduction techniques.

## Summary

The paper titled "The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning" by Siyuan Ma, Raef Bassily, and Mikhail Belkin explores the efficiency and convergence properties of Stochastic Gradient Descent (SGD) with small mini-batches in large-scale machine learning. While SGD is widely used in practice, its theoretical analysis has been challenging due to the requirement of adaptive rates and slower convergence rates compared to gradient descent. The authors aim to clarify the issue of fast SGD convergence by observing that most modern architectures are over-parametrized and trained to interpolate the data, driving the empirical loss close to zero. Although it remains unclear why these interpolated solutions perform well on test data, they enable very fast convergence of SGD, comparable in terms of iterations to gradient descent. The paper focuses on the setting with a quadratic objective function or near a minimum where the quadratic term dominates. The authors make two key findings: 1. Mini-batch size 1 with a constant step size is optimal in terms of computations required to achieve a given error; 2. There exists a critical mini-batch size that determines the behavior of SGD iterations - For mini-batch sizes smaller than the critical size (linear scaling), an iteration with mini-batch size m is nearly equivalent to m iterations with mini-batch size 1; for mini-batch sizes larger than the critical size (saturation), an iteration with a larger mini-batch is nearly equivalent to a gradient descent step. The critical mini-batch size can be seen as the limit for effective mini-batch parallelization and is almost independent of the data size. This implies an acceleration over gradient descent per unit computation complexity by O(n). To support their theoretical analyses, experimental evidence on real data is provided which closely aligns with their findings. Finally, the paper discusses how these results fit into recent developments in training deep neural networks and their connections to adaptive rates for SGD and variance reduction techniques. In summary, this paper sheds light on the efficiency of SGD with small mini-batches in modern over-parametrized learning; it highlights the role of interpolation in achieving fast convergence and provides theoretical insights supported by experimental evidence. The findings have implications for training deep neural networks and offer potential avenues for further research in adaptive rates for SGD and variance reduction.