Research map / Optimization / Nonconvex and smooth optimization
On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions
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 high-probability convergence of vanilla Adam (with corrective terms) for non-convex smooth stochastic optimization under a general affine/sub-Gaussian-type noise model, achieving Õ(poly(log T)/√T), and extends the result to (L0,Lq)-generalized smoothness.
Problem
Whether Adam, including its bias-correction terms, converges to a stationary point at the SGD-matching rate under affine variance noise with potentially unbounded gradients, and under generalized (L0,Lq)-smoothness, in high probability.
Approach
A proxy step-size a_s built from the gradient-norm bound G_T(s) (rather than the true adaptive step b_s) breaks the correlation between stochastic gradients and adaptive step-sizes; combined with a proxy-iterate descent lemma and an induction argument bounding gradient norms, this yields high-probability rates for Adam under almost-sure generalized affine noise, with hyper-parameters beta2 = 1 - c
Key results
- Adam with beta2 = 1 - c/T and eta, epsilon proportional to sqrt(1-beta2) finds a stationary point with probability at least 1-2delta at rate O~(poly(log T)/sqrt(T)) under generalized affine noise.
- Adam without corrective terms (and RMSProp) achieves O~(1/T + sigma_0/sqrt(T)) in high probability, adaptive to noise level sigma_0.
- The same O(poly(log T)/sqrt(T)) high-probability rate extends to (L0,Lq)-generalized smooth objectives with step-size tuned by L0, Lq.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Adam with β2 = 1-c/T, η = C0√(1-β2), and ε = ε0√(1-β2) | Adam · Non-convex L-smooth, generalized affine variance noise | average squared gradient norm: \mathcal{O}\left(\text{poly}(\log T)/\sqrt{T} \right) | Helped |
| extend the objective condition from L-smooth to (L0,Lq)-smooth and tune the step-size using problem parameters | Adam · Non-convex (L0,Lq)-smooth, generalized affine variance noise | average squared gradient norm: \mathcal{O}(\text{poly}(\log T)/\sqrt{T}) | No clear effect |
| drop the two corrective terms | Adam · Non-convex L-smooth, generalized affine variance noise | average squared gradient norm: \tilde{\mathcal{O}}(1/T+\sigma_0/\sqrt{T}) | Helped |
Experimental setup
Metrics: average squared gradient norm bound convergence rate in T
Baselines: AdaGrad-Norm high-probability analysis Zhang et al. 2022 Adam analysis Wang et al. 2023 (sub-Gaussian Adam, (L0,L1)) SGD with affine variance noise
Builds on: Adam AdaGrad-Norm RMSProp generalized smoothness (L0,L1)
Closest papers by meaning
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD (ICML 2025 · similarity 0.91)
- Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients (NeurIPS 2026 · similarity 0.91)
- Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed (ICML 2025 · similarity 0.89)
- Understanding the Generalization of Stochastic Gradient Adam in Learning Neural Networks (NeurIPS 2025 · similarity 0.89)
- The Implicit Bias of Adam on Separable Data (NeurIPS 2024 · similarity 0.88)
- Adam Exploits $\ell_\infty$-geometry of Loss Landscape via Coordinate-wise Adaptivity (ICLR 2025 · similarity 0.88)
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.