# Provable Adaptivity of Adam under Non-uniform Smoothness

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 47 references that are in the map.
- First posted on arXiv 21 Aug 2022.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks](https://mlsanity.com/paper/1511.06434/) (2015)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Adaptive Gradient Methods with Dynamic Bound of Learning Rate](https://mlsanity.com/paper/1902.09843/) (2019)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [A Sufficient Condition for Convergences of Adam and RMSProp](https://mlsanity.com/paper/1811.09358/) (2018)
- [An Improved Analysis of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2007.07989/) (2020)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition](https://mlsanity.com/paper/1308.6370/) (2013)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Why are Adaptive Methods Good for Attention Models?](https://mlsanity.com/paper/1912.03194/) (2019)
- [Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration](https://mlsanity.com/paper/2101.05471/) (2021)
- [AdaShift: Decorrelation and Convergence of Adaptive Learning Rate Methods](https://mlsanity.com/paper/1810.00143/) (2018)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [Asymptotic study of stochastic adaptive algorithm in non-convex landscape](https://mlsanity.com/paper/2012.05640/) (2020)

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

- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity](https://mlsanity.com/paper/2310.17998/) (2023)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [Adam-family Methods for Nonsmooth Optimization with Convergence Guarantees](https://mlsanity.com/paper/2305.03938/) (2023)
- [Towards Quantifying the Preconditioning Effect of Adam](https://mlsanity.com/paper/2402.07114/) (2024)
- [Bilevel Optimization under Unbounded Smoothness: A New Algorithm and Convergence Analysis](https://mlsanity.com/paper/2401.09587/) (2024)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance](https://mlsanity.com/paper/2404.01436/) (2024)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (2025)
- [A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD](https://mlsanity.com/paper/2410.04458/) (2024)
- [High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise](https://mlsanity.com/paper/2311.02000/) (2023)
- [On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Norm](https://mlsanity.com/paper/2505.11840/) (2025)
- [Adam-family Methods with Decoupled Weight Decay in Deep Learning](https://mlsanity.com/paper/2310.08858/) (2023)
- [Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimization](https://mlsanity.com/paper/2410.14054/) (2024)
- [Error Feedback under (L0,L1)-Smoothness: Normalization and Momentum](https://mlsanity.com/paper/2410.16871/) (2024)
- [Simple Convergence Proof of Adam From a Sign-like Descent Perspective](https://mlsanity.com/paper/2507.05966/) (2025)
- [OLion: Approaching the Hadamard Ideal by Intersecting Spectral and ℓ∞ Implicit Biases](https://mlsanity.com/paper/2602.01105/) (2026)
- [Uniform a priori bounds and error analysis for the Adam stochastic gradient descent optimization method](https://mlsanity.com/paper/2603.18899/) (2026)
- [Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad](https://mlsanity.com/paper/2605.18694/) (2026)
- [UAdam: Unified Adam-Type Algorithmic Framework for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2305.05675/) (2023)
- [Signal Processing Meets SGD: From Momentum to Filter](https://mlsanity.com/paper/2311.02818/) (2023)
- [Stochastic Two Points Method for Deep Model Zeroth-order Optimization](https://mlsanity.com/paper/2402.01621/) (2024)
- [Analysis of Adam Algorithms for Stochastic Dynamic Systems](https://mlsanity.com/paper/2606.28879/) (2026)
- [Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness](https://mlsanity.com/paper/2507.08913/) (2025)
- [Combining Adam and its Inverse Counterpart to Enhance Generalization of Deep Learning Optimizers](https://mlsanity.com/paper/2603.07122/) (2026)
- [Understanding Dynamics of Adam in Zero-Sum Games: An ODE Approach](https://mlsanity.com/paper/2605.19392/) (2026)
- [Adam Converges in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2606.22326/) (2026)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)
- [Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients](https://mlsanity.com/paper/2609.37787/) (2026)

## Abstract (arXiv)

Adam is widely adopted in practical applications due to its fast convergence. However, its theoretical analysis is still far from satisfactory. Existing convergence analyses for Adam rely on the bounded smoothness assumption, referred to as the L-smooth condition. Unfortunately, this assumption does not hold for many deep learning tasks. Moreover, we believe that this assumption obscures the true benefit of Adam, as the algorithm can adapt its update magnitude according to local smoothness. This important feature of Adam becomes irrelevant when assuming globally bounded smoothness. This paper studies the convergence of randomly reshuffled Adam (RR Adam) with diminishing learning rate, which is the major version of Adam adopted in deep learning tasks. We present the first convergence analysis of RR Adam without the bounded smoothness assumption. We demonstrate that RR Adam can maintain its convergence properties when smoothness is linearly bounded by the gradient norm, referred to as the emph(L0, L1)-smooth condition. We further compare Adam to SGD when both methods use diminishing learning rate. We refine the existing lower bound of SGD and show that SGD can be slower than Adam. To our knowledge, this is the first time that Adam and SGD are rigorously compared in the same setting and the advantage of Adam is revealed.