Adam with Heavy-Tailed Gradients
Descriptions may be stale. Consult the linked Lean sources.
Adam with Heavy-Tailed Gradients
We consider stationarity for a differentiable, possibly nonconvex
function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Heavy-tailed stochastic gradients).
Let
Our result is algorithm-specific: we analyze Adam with constant
parameters and without bias correction. The algorithm chooses
Let
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdamHeavyTailedFixedMomentum
(Ours) |
|||
| (2) NSGD-M (Hübler et al. 2025, Cor. 19, arXiv v3) | (1): Matches known
accuracy exponent with fixed |
(1): Larger constants;
narrower noise model. Euclidean-scale conversion multiplies its noise
term by |
|
| (3) SGD (Liu 2026, Thm. 4.1, constant steps) | (1): For fixed |
(1): Coordinate-noise
penalty and large constants; loses the stronger guarantee |
|
(4) Vector Adam (Pang 2026, Thm. 6.4, v2) |
Expected relaxed |
(1): Ordinary expected
gradient norm; no bounded-gradient assumption; includes |
(1): Requires smoothness.
Accuracy-dependent damping replaces a fixed stabilizer; |
Abbr: Costs count individual stochastic-gradient
calls.