Can AdamW Survive Heavy-Tailed Noise? An Open Problem with a Corridor Lower-Bound

Paper: 2606.23676 Authors: Dingzhi Yu, Hongyi Tao, Yuanyu Wan, Luo Luo, Lijun Zhang Categories: cs.LG, cs.AI, math.OC, stat.ML

The Gap

Existing theory for adaptive optimizers like AdamW assumes finite-variance gradient noise — which is convenient but increasingly unrealistic. Large language model (LLM) pretraining empirically produces heavy-tailed noise: occasional gradient spikes with infinite variance, typical of Pareto-like distributions. Meanwhile, sign-based optimizers (Lion, Muon) and AdaGrad have been proven to converge under heavy-tailed noise. AdamW, the de facto choice in LLM training, lacks any rigorous convergence guarantee in this regime. The logical path:

Problem: AdamW convergence under heavy-tailed noise is unknown
    |
    v
Assumption (common): finite variance + i.i.d. gradients
    |
    v
Observation: LLM gradients are heavy-tailed (infinite variance)
    |
    v
Gap: no heavy-tailed theory for AdamW exists
    |
    v
Method: formulate as open problem + prove two things:
         (1) a weighted-metric benchmark (positive)
         (2) a "corridor lower-bound" that shows how
             the second-moment accumulator can obstruct
             convergence by masking large gradients
    |
    v
Evidence: theoretical derivations, no experiments needed
    |
    v
Conclusion: AdamW's heavy-tailed behavior is not trivial;
            the corridor mechanism makes it a genuine open problem

The Increment

One sentence: Before this paper, heavy-tailed convergence theory existed for sign-based methods and AdaGrad but not for AdamW — now the absence is formally recognized, a positive benchmark is given, and a lower-bound mechanism shows why the answer is not obvious.

Core Mechanism

The paper does not propose a new algorithm; instead it dissects the AdamW update under heavy-tailed noise. AdamW maintains two state variables: the biased first moment ( m_t ) (exponential moving average of gradient ( g_t )) and the biased second moment ( v_t ) (EMA of ( g_t^2 )). The parameter update is:
$\theta_{t+1} = \theta_t - \eta \frac{m_t}{\sqrt{v_t} + \epsilon} - \eta \lambda \theta_t$ (the weight decay term).
Under heavy-tailed noise, occasional huge gradients can make ( v_t ) spike, shrinking the effective step size for many subsequent steps. The authors prove that in a “corridor” (a critical parameter region), this memory effect can cause an obstruction: gradients may be hidden by the denominator, preventing convergence even when the noise is well-behaved on average.

[ASCII diagram of method internals — the AdamW update with heavy-tailed input]

Time t: g_t ~ heavy-tailed (infinite variance)
     |
     v
    m_t = beta1 * m_{t-1} + (1-beta1) * g_t
    v_t = beta2 * v_{t-1} + (1-beta2) * g_t^2
     |         |
     |         v
     |     sqrt(v_t) + epsilon
     |         |
     v         v
   theta_{t+1} = theta_t - eta * (m_t / (sqrt(v_t)+eps)) - eta * lambda * theta_t
     |
     v
   output next parameter

The key structural insight is the corridor lower-bound: for a range of ( v_t ) values relative to the gradient magnitude, the update is bounded away from zero regardless of how large ( g_t ) is — the denominator “hides” the gradient. This does not happen for sign-based optimizers (where the update is ±η) or for AdaGrad (which uses cumulative sums rather than EMAs, so spikes decay more slowly but don’t cause a corridor).

Key Concepts

• Heavy-tailed noise: Random variables where the tail decays like a power law, e.g., ( P(|X| > x) \approx x^{-\alpha} ) with $\alpha < 2$. This means the variance is infinite (or undefined), and even the mean may not exist. In LLM training, the gradient distribution often resembles a Pareto with α between 1 and 2. Concretely: imagine a gradient that is usually between -1 and 1, but every thousand steps it jumps to 10⁶. A finite-variance optimizer might treat that as an anomaly; heavy-tailed theory must handle it systematically.

• Second-moment accumulator (v_t): In AdamW, ( v_t ) is an exponential moving average of squared gradients. Under heavy-tailed noise, one huge gradient can make ( v_t ) huge for many steps, even after the spike has passed. This is like a thermometer that, after measuring a boiling pot, stays hot for a long time and incorrectly suggests everything is still boiling. The paper shows this memory can create a “corridor” where the update step is tiny, effectively hiding the true gradient direction.

• Corridor lower-bound: A formal mechanism: given certain assumptions on the sequence of ( v_t ) and the current gradient ( g_t ), the effective update magnitude ( \eta m_t/(\sqrt{v_t}+\epsilon) ) is bounded below by a positive constant that does not depend on the size of ( g_t ). This means increasing the gradient does not increase the update — a form of gradient vanishing caused by the accumulator. The authors prove that this corridor exists for some heavy-tailed configurations, making convergence impossible unless specific conditions on the parameters or noise decay hold.

Framework Shift

Before (mainstream heavy-tailed theory):        After (this paper):
+-------------------------------+               +-------------------------------+
| Heavy-tailed noise assumed    |               | AdamW explicitly analyzed     |
| for sign-based (Lion, Muon)   |               | under same heavy-tailed noise |
| and AdaGrad.                  |               |                               |
| AdamW only analyzed under     |               | Positive benchmark: weighted  |
| finite variance.              |               | metric can ensure convergence |
|                               |               | if epsilon is chosen right.   |
+-------------------------------+               | Negative result: corridor     |
                                                 | lower-bound shows obstruction.|
                                                 | Open problem: which regime    |
                                                 | dominates?                    |
                                                 +-------------------------------+

One sentence: From assuming AdamW works by analogy with finite-variance theory, to proving that its EMA second-moment accumulator introduces a genuine obstruction under heavy-tailed noise — shifting the burden of proof onto a non-trivial open question.

Expert Assessment

Problem choice: This is a real gap. LLM practitioners rely on AdamW but the theory community had largely ignored heavy-tailed noise. The paper correctly identifies a missing piece in the convergence theory of one of the most used optimizers. It sits at a timely intersection of optimization theory and large-scale ML.

Method maturity: The contribution is a problem statement plus a theoretical lower-bound — clever rather than brute force. There is no simpler approach because the question is still open; the paper provides the first rigorous boundary. The corridor mechanism is a clean insight suggesting that the answer won’t be a simple “yes.”

Experimental integrity: No experiments are presented (the paper explicitly states none are needed for a theoretical open problem). This is fine given the genre. The derived bounds are mathematically sound; no red flags in the theoretical assumptions.

Writing quality: The structure is clear, but some sections (like the weighted-metric benchmark proof) are dense and under-motivated. The corridor lower-bound part is the highlight and should be expanded with an intuitive example. The abstract is concise. A rewrite of the proof sketches with more intuition would elevate the paper.

Verdict: weak accept — An honest, well-scoped open problem with a nontrivial lower-bound; it doesn’t solve AdamW’s heavy-tailed case but correctly reframes the research agenda. It’s worth attention for optimizer theorists, but practitioners should not change workflows yet.

Takeaways

• The “corridor lower-bound” idea is transferable: any optimizer with an EMA of squared gradients (RMSprop, Nadam) may face similar hiding effects under heavy-tailed noise. Practitioners using such optimizers for long-tailed input distributions should be cautious.
• The weighted-metric benchmark suggests that adding a large enough epsilon (or a different normalization) might circumvent the corridor. This is a concrete knob to turn in future optimizer designs.
• The paper’s framing — “here’s why the naive analogy fails” — is a useful style for other open problems in optimizer theory. Steal that rhetorical structure.