Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

Jeonseong Kim, Chenglin FanarXiv 2026 · arXiv

TL;DR

This paper reveals that Adam's stability constant, $\varepsilon$, is more than just a numerical safeguard—it's a critical hyperparameter for convergence. The authors prove that while standard Adam uses a single shared $\varepsilon$ for all parameters, achieving optimal convergence rates under heavy-tailed noise requires a coordinatewise $\varepsilon_i$ tailored to the specific noise and curvature of each parameter.

What Problem Does This Paper Address?

In the world of Large Language Models (LLMs), Adam and its variant AdamW are the go-to optimizers. Traditionally, researchers treat the $\varepsilon$ in the denominator ($1/\sqrt{v_t + \varepsilon}$) as a tiny constant (like $10^{-8}$) meant only to prevent division by zero.

However, recent observations in deep learning show two challenging phenomena:

  1. Heavy-Tailed Noise: Stochastic gradients often have "outliers" or extreme values, meaning they don't have finite variance (only finite $p$-th moments for $p \in (1, 2]$).
  2. Heterogeneity: Different coordinates (parameters) in a model can have vastly different "curvatures" (how fast the gradient changes) and noise levels.

The authors ask: Does using the same $\varepsilon$ for every parameter hurt us when the landscape is this messy? They specifically investigate if a shared $\varepsilon$ prevents Adam from reaching the "sharp" convergence rates achieved by other heavy-tail-robust methods.

Methods

The paper is a theoretical tour de force that analyzes the "Adam family" of optimizers in a non-convex, stochastic setting.

  • The Setup: They assume coordinatewise smoothness (different $L_i$ for each dimension) and coordinatewise heavy-tailed noise (different $\sigma_i$ scales).
  • Coordinatewise Tuning: They propose a specific way to choose $\varepsilon_i$ for each coordinate based on its local noise ($\sigma_i$) and curvature ($L_i$). Specifically, they set $\varepsilon_i$ to balance momentum noise and gradient drift.
  • Lower Bound Construction: To prove that a shared $\varepsilon$ is inherently limited, they construct a "hard" objective function. This function uses "paired coordinates" and a control coordinate to show that any single scalar $\varepsilon$ will inevitably be too large for some dimensions or too small for others, leading to sub-optimal progress.

Datasets

Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs of convergence rates. It does not use empirical benchmarks or real-world datasets.

Key Insights and Ideas

  • The "Mismatch" in Adam: Adam is designed to be a coordinatewise adaptive method because it tracks $m_t$ and $v_t$ separately for each parameter. However, the authors argue that by using a shared $\varepsilon$, we reintroduce a "global" scale that "regularizes several incompatible local regimes." This effectively breaks the coordinatewise adaptivity Adam was meant to provide.
  • $\varepsilon$ as a Regularizer: If $\varepsilon$ is large, it dominates the denominator, making the update look like standard SGD. If $\varepsilon$ is small, the update is dominated by the second-moment estimate $v_t$. Under heavy tails, the random denominator $\sqrt{v_t}$ actually helps "tame" the noise, but only if $\varepsilon$ is tuned correctly to let that signal through.
  • The Sharp Rate: The paper shows that with coordinatewise $\varepsilon_i$, Adam hits the $O(T^{-\frac{p-1}{3p-2}})$ benchmark. This is significant because this rate is known to be the theoretical optimum for smooth non-convex stochastic optimization under heavy-tailed noise.

Key Results

  • Upper Bound (The Good News): By choosing $\varepsilon_i \approx \max\{\sigma_i, \frac{L_i}{L}\Sigma\}$, Adam achieves the optimal heavy-tailed convergence rate. This rate is uniform across dimensions, meaning it doesn't get significantly worse just because the model is large.
  • Lower Bound (The Bad News): For any shared $\varepsilon_t$ (even if it changes over time), there exists a problem where Adam is stuck at a much slower rate of $\Omega(T^{-\frac{p-1}{2p}})$.
  • The Gap: As the noise becomes "heavier" (as $p$ approaches 1), the gap between the optimal rate and the shared-$\varepsilon$ rate grows significantly, suggesting that standard Adam tuning becomes increasingly problematic for very noisy, heavy-tailed data.

Limitations and Future Work

  • Oracle Knowledge: The optimal coordinatewise $\varepsilon_i$ depends on knowing the local noise scales ($\sigma_i$) and curvature bounds ($L_i$) in advance. In practice, these are rarely known. A natural next step is developing algorithms that can estimate these scales online.
  • Weight Decay: The analysis assumes zero weight decay. Since AdamW (which includes weight decay) is the standard for LLMs, extending this theory to include weight decay is a vital future direction.
  • Stationarity Metric: The results are framed in terms of $\ell_1$-stationarity (the average absolute value of the gradient). While relevant for coordinatewise analysis, practitioners often care more about the $\ell_2$ norm.
  • Hyperparameter Complexity: Moving from one $\varepsilon$ to $d$ different $\varepsilon_i$ values adds significant hyperparameter complexity. The authors suggest this is a "mismatch" in current adaptive methods that needs a more elegant architectural solution.

Summary updated

Abstract

Adam estimates second moments coordinatewise, but typically adds the same scalar $\varepsilon$ to every denominator. We study how this shared $\varepsilon$ affects convergence when noise and curvature vary across coordinates. Under coordinatewise finite-$p$ noise moments, $p\in(1,2]$, choosing $\varepsilon_i$ from the noise and curvature bounds for each coordinate attains the heavy-tailed $\ell_1$-stationarity benchmark $O(T^{-\frac{p-1}{3p-2}})$, matching the known optimal time exponent for smooth nonconvex stochastic optimization. For $1<p<2$, Adam with a shared $\varepsilon_t$ admits a lower bound of order $Ω(T^{-\frac{p-1}{2p}})$. This lower bound holds for every predictable scalar choice of $η_t$, $β_{1,t}$, $β_{2,t}$, and $\varepsilon_t$, precluding a dimension-uniform benchmark rate for this class.
BibTeX
@misc{kim2026coordinatewise,
  author = {Jeonseong Kim and Chenglin Fan},
  title = {{Coordinatewise Epsilon for Adam under Heavy-Tailed Noise}},
  year = {2026},
  eprint = {2611.09596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.09596},
}
Figure