# Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 15 of 15)

- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Convergence Conditions for Stochastic Line Search Based Optimization of Over-parametrized Models](https://mlsanity.com/paper/2408.03199/) (2024)
- [Faster Convergence for Transformer Fine-tuning with Line Search Methods](https://mlsanity.com/paper/2403.18506/) (2024)
- [Improving Line Search Methods for Large Scale Neural Network Training](https://mlsanity.com/paper/2403.18519/) (2024)
- [Why Line Search when you can Plane Search? SO-Friendly Neural Networks allow Per-Iteration Optimization of Learning and Momentum Rates for Every Layer](https://mlsanity.com/paper/2406.17954/) (2024)
- [No learning rates needed: Introducing SALSA -- Stable Armijo Line Search Adaptation](https://mlsanity.com/paper/2407.20650/) (2024)
- [Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems](https://mlsanity.com/paper/2411.07102/) (2024)
- [A Probabilistically Motivated Learning Rate Adaptation for Stochastic Optimization](https://mlsanity.com/paper/2102.10880/) (2021)
- [Fast Line Search for Multi-Task Learning](https://mlsanity.com/paper/2110.00874/) (2021)
- [Adaptive Step-Size Methods for Compressed SGD](https://mlsanity.com/paper/2207.10046/) (2022)
- [Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation](https://mlsanity.com/paper/2404.02378/) (2024)

## Abstract (arXiv)

Adaptive gradient methods are typically used for training over-parameterized models. To better understand their behaviour, we study a simplistic setting -- smooth, convex losses with models over-parameterized enough to interpolate the data. In this setting, we prove that AMSGrad with constant step-size and momentum converges to the minimizer at a faster O(1/T) rate. When interpolation is only approximately satisfied, constant step-size AMSGrad converges to a neighbourhood of the solution at the same rate, while AdaGrad is robust to the violation of interpolation. However, even for simple convex problems satisfying interpolation, the empirical performance of both methods heavily depends on the step-size and requires tuning, questioning their adaptivity. We alleviate this problem by automatically determining the step-size using stochastic line-search or Polyak step-sizes. With these techniques, we prove that both AdaGrad and AMSGrad retain their convergence guarantees, without needing to know problem-dependent constants. Empirically, we demonstrate that these techniques improve the convergence and generalization of adaptive gradient methods across tasks, from binary classification with kernel mappings to multi-class classification with deep networks.