# Training Neural Networks for and by Interpolation

arXiv: https://arxiv.org/abs/1906.05661 · HTML: https://mlsanity.com/paper/1906.05661/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2019.

## Built on by (most cited first, 30 of 45)

- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [MoMo: Momentum Models for Adaptive Learning Rates](https://mlsanity.com/paper/2305.07583/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize](https://mlsanity.com/paper/2110.15412/) (2021)
- [Stochastic Polyak Stepsize with a Moving Target](https://mlsanity.com/paper/2106.11851/) (2021)
- [Cutting Some Slack for SGD with Adaptive Polyak Stepsizes](https://mlsanity.com/paper/2202.12328/) (2022)
- [Variational Inference with Gaussian Score Matching](https://mlsanity.com/paper/2307.07849/) (2023)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [A Stochastic Proximal Polyak Step Size](https://mlsanity.com/paper/2301.04935/) (2023)
- [Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models](https://mlsanity.com/paper/2306.12747/) (2023)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance](https://mlsanity.com/paper/2406.04142/) (2024)
- [UORA: Uniform Orthogonal Reinitialization Adaptation in Parameter-Efficient Fine-Tuning of Large Models](https://mlsanity.com/paper/2505.20154/) (2025)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (2024)
- [Function Value Learning: Adaptive Learning Rates Based on the Polyak Stepsize and Function Splitting in ERM](https://mlsanity.com/paper/2307.14528/) (2023)
- [Stepping on the Edge: Curvature Aware Learning Rate Tuners](https://mlsanity.com/paper/2407.06183/) (2024)
- [Adaptive Learning Rates for Faster Stochastic Gradient Methods](https://mlsanity.com/paper/2208.05287/) (2022)
- [Stochastic Gradient Descent with Preconditioned Polyak Step-size](https://mlsanity.com/paper/2310.02093/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [SRRM: Semantic Region Relation Model for Indoor Scene Recognition](https://mlsanity.com/paper/2305.08540/) (2023)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [MetaOptimize: A Framework for Optimizing Step Sizes and Other Meta-parameters](https://mlsanity.com/paper/2402.02342/) (2024)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [On the Interplay Between Stepsize Tuning and Progressive Sharpening](https://mlsanity.com/paper/2312.00209/) (2023)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [Parameter-free Clipped Gradient Descent Meets Polyak](https://mlsanity.com/paper/2405.15010/) (2024)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [Empirically explaining SGD from a line search perspective](https://mlsanity.com/paper/2103.17132/) (2021)
- [Comment on Stochastic Polyak Step-Size: Performance of ALI-G](https://mlsanity.com/paper/2105.10011/) (2021)

## Abstract (arXiv)

In modern supervised learning, many deep neural networks are able to interpolate the data: the empirical loss can be driven to near zero on all samples simultaneously. In this work, we explicitly exploit this interpolation property for the design of a new optimization algorithm for deep learning, which we term Adaptive Learning-rates for Interpolation with Gradients (ALI-G). ALI-G retains the two main advantages of Stochastic Gradient Descent (SGD), which are (i) a low computational cost per iteration and (ii) good generalization performance in practice. At each iteration, ALI-G exploits the interpolation property to compute an adaptive learning-rate in closed form. In addition, ALI-G clips the learning-rate to a maximal value, which we prove to be helpful for non-convex problems. Crucially, in contrast to the learning-rate of SGD, the maximal learning-rate of ALI-G does not require a decay schedule, which makes it considerably easier to tune. We provide convergence guarantees of ALI-G in various stochastic settings. Notably, we tackle the realistic case where the interpolation property is satisfied up to some tolerance. We provide experiments on a variety of architectures and tasks: (i) learning a differentiable neural computer; (ii) training a wide residual network on the SVHN data set; (iii) training a Bi-LSTM on the SNLI data set; and (iv) training wide residual networks and densely connected networks on the CIFAR data sets. ALI-G produces state-of-the-art results among adaptive methods, and even yields comparable performance with SGD, which requires manually tuned learning-rate schedules. Furthermore, ALI-G is simple to implement in any standard deep learning framework and can be used as a drop-in replacement in existing code.