# AdaLoss: A computationally-efficient and provably convergent adaptive gradient method

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 39 references that are in the map.
- First posted on arXiv 17 Sep 2021.

## Builds on (most cited first, 26 of 26)

- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Learning Transferable Architectures for Scalable Image Recognition](https://mlsanity.com/paper/1707.07012/) (2017)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [How to train your ViT? Data, Augmentation, and Regularization in Vision Transformers](https://mlsanity.com/paper/2106.10270/) (2021)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks](https://mlsanity.com/paper/1806.06763/) (2018)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Variants of RMSProp and Adagrad with Logarithmic Regret Bounds](https://mlsanity.com/paper/1706.05507/) (2017)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification](https://mlsanity.com/paper/1812.00151/) (2018)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019)
- [Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network](https://mlsanity.com/paper/1902.07111/) (2019)
- [WNGrad: Learn the Learning Rate in Gradient Descent](https://mlsanity.com/paper/1803.02865/) (2018)

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

- [Robust Implicit Regularization via Weight Normalization](https://mlsanity.com/paper/2305.05448/) (2023)
- [Provable Regret Bounds for Deep Online Learning and Control](https://mlsanity.com/paper/2110.07807/) (2021)
- [Adaptively Weighted Data Augmentation Consistency Regularization for Robust Optimization under Concept Shift](https://mlsanity.com/paper/2210.01891/) (2022)
- [Unified convergence analysis for gradient descent optimization methods in the training of deep neural networks](https://mlsanity.com/paper/2607.04233/) (2026)

## Abstract (arXiv)

We propose a computationally-friendly adaptive learning rate schedule, "AdaLoss", which directly uses the information of the loss function to adjust the stepsize in gradient descent methods. We prove that this schedule enjoys linear convergence in linear regression. Moreover, we provide a linear convergence guarantee over the non-convex regime, in the context of two-layer over-parameterized neural networks. If the width of the first-hidden layer in the two-layer networks is sufficiently large (polynomially), then AdaLoss converges robustly to the global minimum in polynomial time. We numerically verify the theoretical results and extend the scope of the numerical experiments by considering applications in LSTM models for text clarification and policy gradients for control problems.