← All setups

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 f:Rd→R, where d≥0 is an integer. Its gradient is L-Lipschitz, with L>0, and a given starting point x0 satisfies f(x0)−infxf(x)≤Δ, with Δ≥0. The oracle returns unbiased stochastic gradients with independent, identically distributed samples and coordinatewise noise moments of order α∈(1,2] whose sum is bounded by σα, where σ≥0. We analyze Adam with a randomly selected iterate x¯; the goal is E∥∇f(x¯)∥≤ε, where ε>0 and expectation includes sampling and iterate selection.

The underlying optimization problem is infx∈Rdf(x), and ∥⋅∥ denotes the Euclidean norm. The algorithm receives d, the measurable sample space Ω, L, σ, α, Δ, ε, and x0∈Rd.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere, and for every x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(x0)−f(x)≤Δ.

Assumption 2 (Heavy-tailed stochastic gradients). Let p be a probability measure on Ω. The oracle is a jointly measurable map g:Rd×Ω→Rd. For each x∈Rd, the map g(x,⋅) is Bochner integrable, and the scalar random variable ∑i=1d|gi(x,ξ)−∇if(x)|α is integrable for ξ∼p. They satisfy Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∑i=1d|gi(x,ξ)−∇if(x)|α]≤σα. At call k, a query x∈Rd receives g(x,ξk). The measurable sample variables (ξk)k≥0 are mutually independent with common law p under their joint law Q, and are independent of the algorithm’s randomness.

Our result is algorithm-specific: we analyze Adam with constant parameters and without bias correction. The algorithm chooses 0≤β<1,0<ρ≤1,η>0,τ>0,n∈Z≥0, using the available inputs. Starting from the given x0 and m0=v0=0, it queries at xk and performs the coordinatewise updates gk=g(xk,ξk),mk+1=βmk+(1−β)gk,vik+1=(1−ρ)vik+ρ(gik)2,xik+1=xik−ηmik+1vik+1+τ,i=1,…,d. Independently of the samples, it draws J uniformly from {0,…,n}. Its saved output is initialized to x0 and replaced by the pre-update iterate xJ when call J is made. Thus, after B≥0 oracle calls, its output is x¯={xJ,J<B,x0,J≥B. In particular, with B=n+1 calls the output is the uniformly selected iterate xJ from x0,…,xn; the final call and update are included in this budget.

Let P be the joint law of the samples and the independent index J. The required output x¯ is measurable, ∥∇f(x¯)∥ is integrable under P, and the accuracy requirement is EP[∥∇f(x¯)∥]≤ε.

Results

f:Rd→R is differentiable, ∇f is L-Lipschitz, and f(x0)−inff≤Δ, with L>0, Δ≥0. A jointly measurable, integrable oracle uses IID samples of law μ, with ∫g(x,ω)dμ=∇f(x) and ∫∑i|gi(x,ω)−∂if(x)|αdμ≤σα, 1<α≤2, σ≥0. The setup restricts algorithms to coordinate Adam. (1) uses no bias correction, β1=0.9, and damping outside the square root; its uniform pre-update output satisfies ∫∥∇f(xI)∥2dP≤ε, ε>0, under execution law P.

Heavy-tailed Adam under the HeavyTailedAdam setup.
Result Oracle complexity Novelty Limitations
(1) AdamHeavyTailedFixedMomentum (Ours) (⋆⋆⋆) (review) O(1+LΔε2[1+cα(σε)r])
(2) NSGD-M (Hübler et al. 2025, Cor. 19, arXiv v3) O(1+LΔε2[1+(σ2ε)r]) (1): Matches known accuracy exponent with fixed β1 and no normalization; method-specific advance, no problem-class rate improvement. No tuning-knowledge gain. (1): Larger constants; narrower noise model. Euclidean-scale conversion multiplies its noise term by d(2−α)/(2(α−1)).
(3) SGD (Liu 2026, Thm. 4.1, constant steps)

O(1+LΔε2+(σ2LΔε2)r)

ε≤2LΔ.

(1): For fixed α<2, noise-term gain scales as (LΔ/ε)(2−α)/(α−1) at equal scales; after Euclidean conversion, (LΔ/(dε))(2−α)/(α−1) when LΔ>dε. No exponent gain at α=2. (1): Coordinate-noise penalty and large constants; loses the stronger guarantee E[(K−1∑k=1K∥∇f(xk)∥22)α/2] ≤εα. Gain concerns the shared expected-norm target.

(4) Vector Adam (Pang 2026, Thm. 6.4, v2)

G-Lipschitz differentiable objectives; α>4/3.

O(1+(Bε)8α−43α−4[1+log⁡G+σ2ε]

+ΔλB5α3α−4ε5α3α−4+3/2)

Expected relaxed (λ,ε)-stationarity; 0<ε<G+σ2, fixed α and memory coupling.

(1): Ordinary expected gradient norm; no bounded-gradient assumption; includes 1<α≤4/3. Different criteria and classes: rates not comparable. (1): Requires smoothness. Accuracy-dependent damping replaces a fixed stabilizer; 1−β2≤10−12.

Abbr: Costs count individual stochastic-gradient calls. r=α/(α−1); cα=105α/(α−1); K is the iteration count. σ2 bounds (E∥g−∇f∥2α)1/α: the setup implies σ2≤σ, while Euclidean noise permits σ=d1/α−1/2σ2. Rate comparisons hold at fixed α; prior-work constants may depend on α. In (4), G bounds ∥∇f∥2, λ>0 is the relaxation parameter, B=CG+σ2, and C is the regret constant in Thm. 6.4 (bounded for fixed memory coupling and sufficiently small accuracy). Relaxed stationarity uses infEY=x{∥E∇f(Y)∥2+λE∥Y−x∥22}. In (1), β2=1−ρ, τ=ε/(105ρ), and ρ=(1012+(105σ/ε)r)−1; tuning uses L,Δ,σ,α,ε.

Hübler, Florian, Ilyas Fatkhullin, and Niao He. 2025. “From Gradient Clipping to Normalization for Heavy Tailed SGD.” In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, edited by Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan, vol. 258. Proceedings of Machine Learning Research. PMLR. https://doi.org/10.48550/arXiv.2410.13849.
Liu, Zijian. 2026. In-Expectation Convergence of Stochastic Gradient Methods Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2606.00520.
Pang, Yijiang. 2026. The Convergence Behavior of Adam Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2607.27383.

Lean setup