REVIEW 3 major objections 3 minor 16 references
The Convergence Behavior of Adam under Heavy-Tailed Noise
T0 review · 3 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read The paper proves the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise, with suboptimal but explicit iteration complexity and an optimal rate when the update is clipped to a known doma
desk verdict Genuine plain-Adam heavy-tail result, but the known-radius optimal-rate claim has a fixable algebra slip in Corollary 6.3, and the 'no parameter coupling' bullet oversells. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument is carried by two pieces. First, a generalized discounted-regret-to-nonconvex-stationarity conversion that uses a martingale-difference moment inequality of von Bahr-Esseen type to control heavy-tailed noise; this reduces the optimization guarantee to bounding a discounted regret plus the mean squared norm of the online learner's increments. Second, an exact vector-form Adam viewed as Follow-the-Regularized-Leader with exponentially discounted costs and a quadratic regularizer, including bias-correction terms. The key technical lemmas are a deterministic norm bound for Adam's increment, ||z_t|| <= eta_t sqrt(C(beta)), obtained from the 1-beta1 = C(beta)(1-beta2) relation, and mo
What would settle it
Take the vector-form Adam regret bound with beta1=0.9, beta2=0.99 and cost vectors with a bounded p-th moment for p=1.5 that saturate the moment bound; compute expected discounted regret over many seeds. If the regret exceeds the predicted O((1-beta1)^(-3/4)) scaling, or if for any constructed noise sequence the deterministic inequality ||z_t|| <= eta_t sqrt(C(beta)) fails, the central theorem collapses. A cheaper check: verify that for beta1=0.9, beta2=0.99 the weight ratio max_s w1/w2 stays bounded by 10=C(beta) for all t.
Extended reading notes
Core claim
The central claim is Theorem 6.4. Under a bounded-p-th-moment noise model and the mild coupling 1-beta1 = C(beta)(1-beta2) with fixed C(beta) >= 1, the vector-form Adam update, run inside the discounted conversion procedure, satisfies E[||grad F(x_tilde)||^[rho]] <= (8 + C(R) + 2C(R)C(beta)^{1/p-1/2}) epsilon after T iterations, with an explicit T. The same machinery, with the output clipped to a known domain radius, yields the optimal heavy-tail rate for all p in (1,2]. The paper thus establishes both a positive result -- plain Adam converges under heavy tails -- and a precise measurement of its suboptimality.
Load-bearing premise
All theorems rely on the relation 1-beta1 = C(beta)(1-beta2) for a fixed constant C(beta) >= 1, together with beta1 <= beta2; if the momentum decays are not coupled this way, the deterministic norm bound on Adam's update and every rate that depends on it are not proved.
Editorial extensions
If this is right
- If the main theorem is right, practitioners can trust that plain Adam will not diverge under heavy-tailed noise; its worst-case iteration count grows like epsilon^-13/2 for bounded variance, a concrete price for not modifying the update.
- Because the known-radius clipped version matches the optimal complexity, the result suggests explicit norm control of the update is sufficient to restore optimality; the paper leaves open whether it is necessary.
- The conversion framework now covers heavy-tailed martingale-difference noise, so the same discounted-regret technique can be applied to other adaptive optimizers.
- The p>4/3 restriction for unclipped Adam and p>1 for clipped Adam determines exactly which heavy-tail regimes are covered.
- The numerical stabilizer in Adam's denominator is allowed to be a fixed small constant independent of G and sigma, so the analysis covers the way Adam is usually coded.
- The rates imply that for p=2, plain Adam needs epsilon^-13/2 iterations while the clipped version needs only epsilon^-7/2, quantifying the cost of not using domain information.
Reading between the lines
- A direct consequence the paper does not spell out: if the C(beta) coupling between beta1 and beta2 is violated by an implementation, the deterministic increment bound can fail, which may explain empirically observed instability of Adam in heavy-tailed settings; the paper's summary statement 'only beta1 <= beta2' is stronger than what the proof supports.
- Since the known-radius result clips only the online-learner output, not the gradients, a testable prediction is that equivalent norm control via weight decay or normalization, as in AdamW, could also close the optimality gap without needing the domain radius D.
- The rates suggest a practical schedule for heavy-tailed problems: choose beta1 close to 1 according to epsilon, keep C(beta) small and bounded, and use output clipping when the domain radius is known; the paper does not test this empirically.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the convergence of vector-form Adam under heavy-tailed stochastic noise, assuming only a bounded p-th central moment (p∈(1,2]). It (i) generalizes the discounted online-to-nonconvex conversion framework to heavy-tailed martingale-difference noise, (ii) proves a discounted regret bound for an FTRL formulation of Adam under a β1≤β2 condition with the additional coupling 1−β1=C(β)(1−β2), and (iii) converts this into (ρ,ε)-stationarity guarantees. For unclipped plain Adam the paper obtains a p-dependent, suboptimal iteration complexity (e.g. O(ε^{-13/2}) at p=2), while a clipped/constrained version with known radius is claimed to match the optimal heavy-tail rate (e.g. O(ε^{-7/2}) at p=2).
Significance. If the results are correct as intended, this is a meaningful advance: it provides the first convergence guarantees for a vector Adam update under heavy-tailed noise without explicit truncation of the gradient, and it generalizes the online-to-nonconvex conversion machinery beyond bounded variance. The proof chain is detailed and, away from the issues noted below, internally consistent: the martingale controls, the β-weighted regret decomposition, and the balancing of β1, D, and T are transparent and lead to the claimed exponents. The paper also makes honest statements about the suboptimality of plain Adam, which is a useful conceptual contribution. However, the scope of the claim 'plain Adam' is weakened by the one-step-delayed FTRL formulation and by the C(β) coupling, and one displayed parameter choice in Corollary 6.3 is algebraically inconsistent as written.
major comments (3)
- [§6.3, Corollary 6.3 (statement and proof)] The stated choice η = D√(1−β1) is inconsistent with the displayed regret simplification. Substituting this η into Eq. (3) gives D/(2(1−β1)^{3/2}) as the first term and 2D√β2(1−β1)^{3/2}/(β1(1−β2)) as the second, not the printed D/√(1−β1) times the printed coefficients. The displayed bound is valid only for η = D/√(1−β1). Since Corollary 6.5 uses the √(1−β1) denominator to choose β1 and obtain the claimed optimal heavy-tail exponent, this is load-bearing. The notation must be corrected to η = D/√(1−β1) (or the regret calculation revised), and the proof of Corollary 6.5 re-checked.
- [§1 contributions and §5.2 Remark 5.3] The abstract and contributions state that Adam is analyzed 'without restrictive parameter coupling' and that 'we only require β1 ≤ β2'. This is an overstatement: Remark 5.3 additionally requires 1−β1 = C(β)(1−β2) for a fixed constant C(β)≥1. Proposition 5.4 and the subsequent regret and stationarity bounds depend on this coupling through the deterministic output bound ∥z_t∥ ≤ η_t√C(β). The paper should state the C(β) coupling in the abstract/contributions and not present β1≤β2 as the sole condition. This is a scope issue, not just a wording issue, because the rates apply to the family of parameter pairs satisfying the coupling.
- [§5, Algorithm 2] The algorithm analyzed is not the standard vector-form Adam update as usually implemented. In Algorithm 2, the increment z_t uses gradients v_1,...,v_{t−1} and bias-correction exponents t−1, whereas standard Adam uses v_t and bias-correction exponent t at round t. The paper calls this 'the exact vector-form Adam update' and 'plain Adam', but the one-step delay is an algorithmic modification. The authors disclose the shift in the footnote, but the abstract and contributions should state prominently that the results are for this delayed FTRL form; otherwise the 'plain Adam' claim is misleading and the practical relevance is unclear.
minor comments (3)
- [§6.2, Theorem 6.4] There is an inconsistency between the stated D and the proof. The theorem states D = (1−β1)^{5/4}ε^{1/2}/(C(β)ρ^{1/2}), but the proof's Δ/(DT) term uses √C(β)ρ^{1/2}Δ/((1−β1)^{5/4}ε^{1/2}T), which corresponds to D = (1−β1)^{5/4}ε^{1/2}/(√C(β)ρ^{1/2}). The constants should be aligned.
- [§6.3, Corollary 6.3] The definition of C(R) in Corollary 6.3 is a maximum of two branches, but the proof of the clipped case uses only the second branch. The first branch appears to be a vestige of the unclipped proof and should be removed or explained.
- [§6.3, Corollary 6.5 vs Abstract] Corollary 6.5 states the second T-term with (C(R)G+σ)^{p/(p−1)}, while the abstract and discussion omit C(R). Since C(R) is a constant depending on C(β) and β1, this is not a mathematical issue, but the statements should be harmonized to avoid apparent discrepancies.
Circularity Check
No significant circularity: the paper derives Adam's heavy-tailed convergence as a chain of inequalities from stated moment assumptions and external conversion/regret lemmas; no fitted input is relabeled as a prediction.
full rationale
The derivation chain is self-contained in the relevant sense: Assumptions 3.1 and 3.3 posit bounded p-th moments and unbiased stochastic gradients; Proposition 4.2 and Lemma 4.1 extend the discounted-to-nonconvex conversion using the von Bahr–Esseen inequality; Theorem 6.2 is a regret bound for the vector-form Adam FTRL update; Theorem 6.4 and Corollary 6.5 are obtained by substituting these bounds into Eq. (1) and balancing β1, D, and T. There is no fitted parameter that is later called a prediction: the quantities β1, β2, D, and T are chosen to make each term in the final inequality at most ε, not estimated from data. The C(β) coupling in Remark 5.3 is an explicit parameter-selection strategy, not a hidden reuse of the target result. The 'optimal' rate in Corollary 6.5 is benchmarked against external known complexity results, not derived from the paper's own conclusions. The abstract's phrase 'only β1 ≤ β2' is stronger than the actually used C(β) condition, and the skeptic's reported algebraic mismatch in Corollary 6.3 concerns correctness of the stated η, not circularity. The paper also candidly frames the known-radius improvement and the open question about plain Adam, which is inconsistent with a circular claim. No self-citation chain or imported uniqueness theorem is load-bearing. Thus no step in the paper reduces to its own input by construction.
Assumptions & free parameters
free parameters (5)
- β1 (discount factor) =
1-(ε/(G+σ))^{4p/(3p-4)} in Thm 6.4; 1-(ε/(G+σ))^{p/(p-1)} in Cor 6.5
- β2 (EMA denominator parameter) =
1-(1-β1)/C(β)
- C(β) (coupling constant) =
≥1 (e.g., 100 for β1=0.9, β2=0.999)
- D (comparator/clipping radius) =
(1-β1)^{5/4} ε^{1/2}/(C(β)ρ^{1/2}) for plain; (1-β1)ε^{1/2}/ρ^{1/2} for clipped
- η (learning rate) =
D/(1-β1)^{1/4} for plain; D√(1-β1) for clipped
assumptions (8)
- domain assumption F is differentiable, bounded below, G-Lipschitz and 'well-behaved' (Assumption 3.1)
- domain assumption Stochastic gradients are unbiased martingale differences with E[||g-∇F||^p | x]≤σ^p (Assumption 3.3)
- domain assumption Comparators and online outputs live in a Euclidean ball of radius D (Assumption 3.4)
- standard math von Bahr-Esseen inequality: E||Σ d_t||^p ≤ C_p Σ E||d_t||^p with C_p≤2 for 1≤p≤2
- standard math FTRL decomposition with strong convexity, Young's inequality, and the exponential-random-variable property E[F(x_t)-F(x_{t-1})]=E⟨∇F(x_t), z_t⟩ (Lemma 3.1 of Zhang-Cutkosky)
- ad hoc to paper Algorithm 2 with the specified α_t is algebraically equivalent to the vector-form Adam update with bias-correction exponents t-1 and one-step shift
- ad hoc to paper β1≤β2 and 1-β1=C(β)(1-β2) for fixed C(β)≥1 (Remark 5.3)
- domain assumption Known-domain-radius setting permits clip_D(z_t) and η=D√(1-β1) (Corollary 6.3)
Cite this review
Pith. "Pith review of The Convergence Behavior of Adam under Heavy-Tailed Noise." pith.science (2026). https://pith.science/paper/UOJ2G5MS
@misc{pith2026260727383,
author = {Pith},
title = {Pith review of: The Convergence Behavior of Adam under Heavy-Tailed Noise},
year = {2026},
howpublished = {\url{https://pith.science/paper/UOJ2G5MS}},
note = {Machine review of arXiv:2607.27383}
}
abstract
We establish the first convergence guarantees for the plain vector-form Adam optimizer under heavy-tailed stochastic noise. While several Adam variants are known to achieve optimal iteration complexity in bounded-variance nonsmooth nonconvex optimization, little is understood about their behavior when stochastic gradients admit only a bounded $p$-th central moment for some $p \in (1,2]$, a setting increasingly observed in modern deep learning. To address this gap, we generalize the recent online-to-nonconvex conversion framework to accommodate heavy-tailed martingale-difference noise. Building on this generalized framework, we develop a discounted regret analysis for Adam, without restrictive parameter coupling. Our results show that Adam converges to $(\rho,\epsilon)$-stationary points under heavy-tailed noise. However, it exhibits a suboptimal iteration complexity and $p$-dependent convergence, a suboptimality that persists even in the bounded-variance case ($p=2$). Specifically, the $\epsilon$-dominant term in the iteration complexity for reaching in-expectation stationarity is $T=\mathrm{O}\left(\Delta \rho^{1/2}(G+\sigma)^{\frac{5p}{3p-4}}\epsilon^{-\left(\frac{5p}{3p-4}+\frac{3}{2}\right)}\right)$ for $p\in(\frac{4}{3},2]$, which simplifies to $T=\mathrm{O}(\epsilon^{-13/2})$ when $p=2$. When the domain radius is known and used to control the online-learner output, a standard setup in related literature, the convergence rate improves to match the optimal complexity. In this case, the $\epsilon$-dominant iteration complexity is $T=\mathrm{O}\left(\Delta \rho^{1/2}(G+\sigma)^{\frac{p}{p-1}}\epsilon^{-\left(\frac{p}{p-1}+\frac{3}{2}\right)}\right)$ for $p\in(1,2]$, which simplifies to $T=\mathrm{O}(\epsilon^{-7/2})$ when $p=2$. These findings provide new theoretical insight into the robustness and limitations of Adam in heavy-tailed regimes.
Reference graph
Works this paper leans on
-
[1]
Kwangjun Ahn and Ashok Cutkosky. Adam with model exponential moving average is effective for nonconvex optimization.arXiv preprint arXiv:2405.18199,
-
[4]
Savelii Chezhegov, Yaroslav Klyukin, Andrei Semenov, Aleksandr Beznosikov, Alexander Gasnikov, Samuel Horváth, Martin Takáˇc, and Eduard Gorbunov. Clipping improves adam-norm and adagrad-norm when the noise is heavy-tailed.arXiv preprint arXiv:2406.04443,
-
[5]
Adrien Fradin, Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. Tight lower bounds and optimal algo- rithms for stochastic nonconvex optimization with heavy- tailed noise.arXiv preprint arXiv:2512.18713,
-
[7]
Adam: A method for stochastic opti- mization.arXiv preprint arXiv:1412.6980,
Diederik P Kingma. Adam: A method for stochastic opti- mization.arXiv preprint arXiv:1412.6980,
-
[9]
Ta Duy Nguyen, Alina Ene, and Huy L Nguyen. Improved convergence in high probability of clipped gradient meth- ods with heavy tails.arXiv preprint arXiv:2304.01119,
-
[10]
A modern introduction to online learn- ing.arXiv preprint arXiv:1912.13213,
Francesco Orabona. A modern introduction to online learn- ing.arXiv preprint arXiv:1912.13213,
arXiv 1912
-
[15]
nX t=1 βn−tξt # ≤D E
Supplementary Material Yijiang Pang1 1Michigan State University, East Lansing, USA A MISSING PROOFS OF SECTION 4 Lemma 4.1.Suppose Assumption 3.3 holds. Then for anyβ∈(0,1),n∈[T], and comparatoru n ∈ D, E nX t=1 βn−t⟨ξt,u n⟩ ≤2(1−β)− 1 p σD. Proof.Using∥u n∥ ≤Dand Cauchy–Schwarz, we have nX t=1 βn−t⟨ξt,u n⟩= D nX t=1 βn−tξt,u n E ≤D nX t=1 βn−tξt . Taking...
1965
-
[16]
TX n=1 nX t=1 (1−β)β n−t F(x t)−F(x t−1) | {z } A # +E
Then,∀n∈[T], we have E " nX t=1 βn−t F(x t)−F(x t−1) # ≤ −D1−β n 1−β E Eyn ∇F(y n) + 2(1−β) − 1 p σD+ERegret [β] n (un), wherey n is randomly distributed over{x t}n t=1 asP(y n =x t) = (1−β)β n−t 1−βn , t= 1, . . . , n. Proof. Following the fact about exponential random variable, Lemma 3.1 in Zhang and Cutkosky [2024], E F(x t)− F(x t−1) =E⟨∇F(x t),z t⟩: ...
2024
Show all 16 references
-
[1951]
Gradient normaliza- tion provably benefits nonconvex sgd under heavy-tailed noise.arXiv preprint arXiv:2410.16561, page 5,
Tao Sun, Xinwang Liu, and Kun Yuan. Gradient normaliza- tion provably benefits nonconvex sgd under heavy-tailed noise.arXiv preprint arXiv:2410.16561, page 5,
-
[1965]
Sign-based optimizers are effective under heavy- tailed noise.arXiv preprint arXiv:2602.07425,
Dingzhi Yu, Hongyi Tao, Yuanyu Wan, Luo Luo, and Lijun Zhang. Sign-based optimizers are effective under heavy- tailed noise.arXiv preprint arXiv:2602.07425,
-
[2014]
Online convex optimization with heavy tails: Old algorithms, new regrets, and applications.arXiv preprint arXiv:2508.07473,
Zijian Liu. Online convex optimization with heavy tails: Old algorithms, new regrets, and applications.arXiv preprint arXiv:2508.07473,
-
[2020]
Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise.arXiv preprint arXiv:2506.11214,
Chuan He, Zhaosong Lu, Defeng Sun, and Zhanwang Deng. Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise.arXiv preprint arXiv:2506.11214,
-
[2022]
Random scaling and mo- mentum for non-smooth non-convex optimization.arXiv preprint arXiv:2405.09742,
Qinzi Zhang and Ashok Cutkosky. Random scaling and mo- mentum for non-smooth non-convex optimization.arXiv preprint arXiv:2405.09742,
-
[2023]
General framework for online-to-nonconvex conversion: Schedule-free sgd is also effective for nonconvex opti- mization.arXiv preprint arXiv:2411.07061, 2024a
Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky. General framework for online-to-nonconvex conversion: Schedule-free sgd is also effective for nonconvex opti- mization.arXiv preprint arXiv:2411.07061, 2024a. Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai. Understanding a...
-
[2024]
Linear attention is (maybe) all you need (to understand transformer optimization)
Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear attention is (maybe) all you need (to understand transformer optimization). arXiv preprint arXiv:2310.01082,
-
[2026]
Why gradient clipping accelerates training: A theoretical justification for adaptivity.arXiv preprint arXiv:1905.11881,
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jad- babaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity.arXiv preprint arXiv:1905.11881,
1905 arXiv
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.