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

@InProceedings{pmlr-v80-ma18a,
  title = 	 {The Power of Interpolation: Understanding the Effectiveness of {SGD} in Modern Over-parametrized Learning},
  author =       {Ma, Siyuan and Bassily, Raef and Belkin, Mikhail},
  booktitle = 	 {Proceedings of the 35th International Conference on Machine Learning},
  pages = 	 {3325--3334},
  year = 	 {2018},
  editor = 	 {Dy, Jennifer and Krause, Andreas},
  volume = 	 {80},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {10--15 Jul},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v80/ma18a/ma18a.pdf},
  url = 	 {https://proceedings.mlr.press/v80/ma18a.html},
  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 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