Research map / Optimization / Nonconvex and smooth optimization
On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves an O(sqrt(d)/K^{1/4}) convergence rate for AdamW (and NAdamW) measured by the l1 norm of the gradient under a weight-decay bound that keeps iterates inside the l_inf constraint, and validates the d-dependence empirically on ResNet-50 and GPT-2.
Problem
Convergence rate of AdamW for non-convex stochastic optimization is theoretically poorly understood; prior analyses need exponentially decaying weight decay or bounded gradients, and the gradient-norm metric is unclear.
Approach
Measures convergence by the l1 norm of the gradient, which under a modest weight decay (iterates satisfying ||x||_inf < 1/lambda, the KKT-relevant constraint) is a meaningful stationarity metric. It bounds the weight-decay term by controlling ||x||_inf and sets epsilon = sigma^2/d, obtaining an O(sqrt(d)/K^{1/4}) rate analogous to SGD's l2 rate, without explicit epsilon dependence.
Key results
- Theorem gives (1/K) sum E||grad f(x^k)||_1 <= 10 sqrt(d)/K^{1/4} (sigma_hat^2 L (f(x^1)-f*))^{1/4} + 66 sqrt(dL(f(x^1)-f*)/K) for AdamW under weight-decay and epsilon settings, matching SGD's K^{-1/4} rate in l2 norm up to sqrt(d).
- Under sigma^2 small, the rate improves to O(sqrt(d/K)), matching gradient descent in l1 norm.
- Empirically, ||grad f||_1 = Theta(sqrt(d)) ||grad f||_2 on ResNet-50 and GPT-2 training, supporting the analogy to SGD's rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NAdamW's double-momentum mechanism instead of AdamW's momentum | AdamW · Nonconvex stochastic optimization | average ℓ1 gradient norm convergence rate: same convergence rate | No clear effect |
| Set weight decay λ=0, recovering Adam from AdamW | AdamW · Nonconvex stochastic optimization | average ℓ1 gradient norm convergence rate: same convergence rate | No clear effect |
| Reduce gradient noise variance below the stated threshold | AdamW · Nonconvex stochastic optimization | average ℓ1 gradient norm convergence rate: O(\frac{\sqrt{d}}{K^{1/4}}) -> O(\sqrt{\frac{d}{K}}) | Helped |
| Use a large weight-decay parameter above a certain threshold | AdamW · Toy quadratic example | gradient norm convergence | Hurt |
Surprising findings
- Large weight decay values (e.g., 0.1, 0.01 in toy example) can prevent AdamW from converging to the minimizer or a KKT point, showing the upper bound on lambda is necessary.
- Full-batch analysis of Adam with common hyperparameters can fail to converge in prior constructed examples, so practical configurations may not guarantee convergence.
Limitations
- Convergence analysis uses theoretical parameter settings (eta very small, theta and beta near 1) that differ from standard practice (0.9, 0.999).
- Assumes smoothness and bounded noise variance; the lower bound for d dependence is only conjectured, so tightness in d is unresolved.
- Requires weight decay bound lambda small relative to d and K and initialization constraint on ||x^1||_inf, which may be restrictive.
Experimental setup
Datasets: CIFAR-100 ImageNet OpenWebText
Benchmarks: CIFAR-100 ImageNet OpenWebText
Metrics: l1 norm of full gradient averaged over iterations l2 norm of gradient training loss ratio of l1 to l2 gradient norm
Baselines: Adam with l2 regularization AdamW convergence analysis of Zhou et al. 2024 (exponentially decaying weight de RMSProp convergence results (Shi et al.) SGD convergence rate
Builds on: Adam AdamW RMSProp NAdamW
Closest papers by meaning
- Implicit Bias of AdamW: $\ell_\infty$-Norm Constrained Optimization (ICML 2024 · similarity 0.90)
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD (ICML 2025 · similarity 0.88)
- Adam Exploits $\ell_\infty$-geometry of Loss Landscape via Coordinate-wise Adaptivity (ICLR 2025 · similarity 0.87)
- Small Batch Size Training for Language Models: When Vanilla SGD Works, and Why Gradient Accumulation is Wasteful (NeurIPS 2025 · similarity 0.86)
- Adam Reduces a Unique Form of Sharpness: Theoretical Insights Near the Minimizer Manifold (NeurIPS 2025 · similarity 0.86)
- On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.