acceptodds
Under review as a conference paper at ICLR 2027

The Heavy-Tail Behavior of Adam: Sharp Rates and a Phase Transition at

21 views

Abstract

Gradient noise in deep learning produces more extremes than models with light tails predict; finite -moment models permit infinite variance (), beyond classical theory. Despite Adam's observed advantage over SGD, whose degradation is partly attributed to heavy tails, analyses rely on Clip-SGD analogies or modified methods, leaving unmodified coordinatewise Adam's convergence a recurring open problem. The difficulty is that conditional second moment proxies control dependence from sample reuse at , but may fail below . We make progress toward resolving this problem under a classical finite horizon parameter setting. Specifically, we derive an explicit upper bound for every constant base stepsize using chord cancellation and an exact identity for an auxiliary iterate. These charge normalization bias and drift in adaptive stepsizes to realized second moment increments, avoiding noise variances and direct momentum recursion. For -smooth objectives bounded below, with fixed and adapted noise having finite conditional -moments () bounded by , with fixed, we select a stepsize yielding the expected average squared gradient norm bound . Lower bounds for over all constant stepsizes establish stepsize minimax sharpness up to logarithms, with a gap of one logarithm for . Thus uniform polynomial stationarity decay is achievable iff , recovering the polynomial exponent at .

Primary area:
optimization
Keywords:
The Heavy-Tail Behavior of Adam

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ycP4OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the convergence of Adam under heavy-tailed noise with bounded conditional pp-moments (1<p≤21 < p \le 2). They show that when the objective is LL-smooth and bounded below and p>6/5p > 6/5, one can choose the Adam parameters appropriately so that the expected average squared gradient norm decays at a polynomial rate. In addition, for each fixed moment bound and step size, with the parameter choice β2=1−1/T\beta_2 = 1 - 1/T, they construct a function and a stochastic oracle for which the rate of Adam matches their upper bound up to a polylog factor.

Critical strengths
  • The setting is clean. The analysis keeps Adam’s core updates and does not require clipping or additional normalization. The upper bound is also accompanied by nearly matching lower bounds.
  • The chord cancellation method seems to be a useful generic approach to analyze the bias of transformed noisy gradients.
Critical weaknesses

The analysis relies heavily on the parameter choice β2=1−1/T\beta_2 = 1 - 1/T. While this also appears in other papers in this field, it is still quite different from common practice and makes the lower bound somewhat restrictive.

Questions for authors
  • Can the analysis be extended to setting where β2\beta_2 is a TT-independent constant, potentially under some additional assumptions?
  • How generic is this chord cancellation method? The reduction to two-point chords part seem fairly general, but secant inequality part exploits Adam's specific normalization. Are there other situations where this method could be useful?
Reviewer_frVbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies Adam under heavy-tailed noise. Under its specified parameter and initialization conditions, it identifies p=6/5p=6/5 as the threshold for uniform polynomial stationarity convergence: above this threshold, the expected average squared gradient norm can decay polynomially; at or below it, no uniform polynomial rate can be guaranteed.

Critical strengths

Through chord cancellation and auxiliary iterates, the paper handles the stochastic dependence between Adam’s numerator and denominator and directly bounds the expected average squared gradient norm along the actual iterates. It allows infinite noise variance without assuming bounded gradients or trajectories. This substantially influences my assessment because it addresses a central analytical difficulty in understanding Adam under heavy-tailed noise and provides a meaningful optimization guarantee under weak assumptions.

The lower bounds cover all constant base stepsizes and match the upper bound’s polynomial exponents for p>6/5p>6/5, up to logarithmic factors. At and below the threshold, the lower bounds rule out uniform polynomial convergence guarantees. Together, these results establish worst-case limitations of the studied algorithm and noise class. This substantially strengthens the completeness and persuasiveness of the theoretical contribution and is an important reason for my inclination toward acceptance.

Critical weaknesses

The results rely on β2=1−1/T\beta_2=1-1/T, strictly positive second-moment initialization, and updates without bias correction, which differ substantially from commonly used default Adam implementations. Consequently, the established convergence rates and phase-transition threshold do not directly transfer to those implementations.

Since understanding Adam’s behavior under heavy-tailed noise is an important motivation, this gap limits the breadth and practical explanatory value of the contribution. These conditions are explicitly stated, however, so this is a limitation of applicability rather than a correctness defect.

Questions for authors

When the denominator includes a positive stabilizer ϵ>0\epsilon>0, which key steps of the current proof still require strictly positive second-moment initialization?

Does the existing argument directly support any guarantee under zero initialization? Please distinguish conditions used by the proof from conditions established to be necessary.

Reviewer_eopiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the convergence of Adam, without modification such as clipping or normalization, under heavy-tailed noise settings. For the analysis, this paper introduce a proof technique called Chord Cancellation, and it resolved the difficulty which arises in the analysis of adaptive methods. The paper establishes a tight convergence bound of Adam (up to log term), with the explicit form of the exponent of TT which depends on the tail index pp, and shows a phase transition of the convergence behavior of Adam at p=65p=\frac{6}{5}.

Critical strengths
  • This paper established a tight (up to log term) upper/lower bounds of Coordinate-wise Adam without clipping or normalization, under heavy-tailed noise setting, which is commonly observed in practice.
  • This paper introduced a novel proof technique called Chord Cancellation, to resolve the difficulty in the convergence analysis of adaptive methods.
Critical weaknesses
  • The upper bound for the case p∈(1,1.2]p\in (1, 1.2] is O(1)\mathcal{O}(1), which indicates the Adam can fail to converge, while the lower bound in the same region is Ω(1log⁡T)\Omega (\frac{1}{\log T}), which converges, although it is not polynomial. Therefore, the convergence itself was not established in this region. Although the ratio of upper and lower bounds is log-scale, the result does not conclude whether Adam can converge when p∈(1,1.2]p\in (1, 1.2], this remains a large gap.
  • A comparison with the bound Θ(T−(p−1)/(3p−2))\Theta(T^{-(p-1)/(3p-2)}) in [1], which is the tight bound under smooth non-convex setting with heavy-tailed noise, seems to be missing. Comparing the Adam lower bound shown in the paper, it concludes that Adam is suboptimal, which is an important implication.
  • This paper focuses on Adam without bias correction, i.e. Adam considered in this paper does not use mt1−β1t\frac{m_{t}}{1-\beta_{1}^t} and vt1−β2t\frac{v_{t}}{1-\beta_{2}^t}, which are standard in most implementations. Furthermore, the paper sets β2=1−1T\beta_{2}=1-\frac{1}{T}, leading to the term 1−β2t=1−(1−1T)t1-\beta_{2}^t = 1-(1-\frac{1}{T})^t, which is not negligible when t=Θ(T)t=\Theta(T).

[1] Zhang, Jingzhao, et al. "Why are adaptive methods good for attention models?." Advances in Neural Information Processing Systems 33 (2020): 15383-15393.

Questions for authors
  • If p∈(1,1.2]p\in (1, 1.2], can Adam (considered in this paper) fail to converge?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.