← All setups

Adam with Affine Heavy-Tailed Noise

Descriptions may be stale. Consult the linked Lean sources.

Adam with Affine Heavy-Tailed Noise

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d≥0 is an integer. The function f is (L0,L1)-smooth in the ℓ∞-to-ℓ1 sense, with L0,L1≥0 and L0+L1>0. A given starting point x0 satisfies f(x0)−infxf(x)≤Δ, where Δ≥0. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with coordinatewise noise moments of order p∈(1,2] bounded affinely in the corresponding gradient magnitudes to power p. We analyze minibatch Adam with bias correction. For ε>0, its output x¯ must satisfy E∥∇f(x¯)∥1≤ε, where expectation includes sampling and algorithm randomness and ∥z∥1=∑i=1d|zi|.

The optimization problem is infx∈Rdf(x). The ambient space has its Euclidean inner product, which defines ∇f. Write ∥z∥∞=max1≤i≤d|zi|, with both norms equal to zero when d=0. Let Ω be a measurable sample space, and let σ0=(σ0,i)i=1d and σ1 be nonnegative noise parameters. The algorithm receives d, Ω, L0, L1, σ0, σ1, p, Δ, ε, and x0.

Our assumptions:

Assumption 1 (Generalized smoothness). The function f is Fréchet differentiable everywhere. For all x,y∈Rd satisfying L1∥y−x∥∞≤1, ∥∇f(y)−∇f(x)∥1≤(L0+L1∥∇f(x)∥1)∥y−x∥∞.

Assumption 2 (Initial objective gap). The given starting point satisfies f(x0)−f(x)≤Δfor every x∈Rd.

Assumption 3 (Affine heavy-tailed oracle). There exist a probability measure ν on Ω and a jointly measurable map g:Rd×Ω→Rd. For every x, the map g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). For every x and coordinate i, the random variable |gi(x,ξ)−∇if(x)|p is integrable and satisfies Eξ∼ν[|gi(x,ξ)−∇if(x)|p]≤σ0,ip+σ1p|∇if(x)|p. At call k≥0, a query x∈Rd receives g(x,ξk). Under their joint law Q, the measurable samples (ξk)k≥0 are mutually independent and each has distribution ν. Algorithm randomness is independent of this sample sequence.

Our formulation is algorithm-specific: we analyze minibatch Adam with bias correction and a constant step size. Its tuning parameters satisfy 0≤β1<1,0≤β2<1,η>0,δ>0,B∈{1,2,…},n∈{0,1,…}. These parameters may depend on the supplied inputs. Initialize the moments at m0=v0=0 and the iterate at the given x0. At iteration t≥0, take B consecutive oracle samples at xt and form ht=1B∑b=0B−1g(xt,ξtB+b). For each coordinate i, the update is mt+1=β1mt+(1−β1)ht,vit+1=β2vit+(1−β2)(hit)2,m^t+1=mt+11−β1t+1,v^t+1=vt+11−β2t+1,xit+1=xit−ηm^it+1v^it+1+δ. Each completed iteration uses B oracle calls. For an allotted budget N∈{0,1,…}, let T=⌊N/B⌋ be the number of completed iterations. Any remaining calls are made at xT and do not produce another update.

Independently of the samples, draw J uniformly from {0,…,n}. The output rule saves the selected iterate immediately before its update; explicitly, x¯={xJ,J<T,x0,J≥T. In particular, when N≥B(n+1), this is a uniform selection from x0,…,xn. Let P be the joint law of J and the oracle samples. The output must be measurable, ∥∇f(x¯)∥1 must be integrable under P, and the required accuracy is EP[∥∇f(x¯)∥1]≤ε.

Results

Differentiable f:Rd→R satisfies f(x0)−f(x)≤Δ for every x and ∥∇f(y)−∇f(x)∥1≤(L0+L1∥∇f(x)∥1)∥y−x∥∞ whenever L1∥y−x∥∞≤1. Here L0,L1,Δ,σ0,i,σ1≥0, L0+L1>0, 1<p≤2, and ε>0. IID samples have law μ; the jointly measurable oracle is integrable, with ∫g(x,ω)dμ=∇f(x) and integrable coordinate errors satisfying ∫|gi(x,ω)−∂if(x)|pdμ≤σ0,ip+σ1p|∂if(x)|p. The setup restricts algorithms to bias-corrected coordinatewise Adam with arithmetic minibatches and a uniformly selected pre-update iterate xI. The target is ∫∥∇f(xI)∥1dP≤ε, with measurable output and integrable gradient norm; P includes the IID samples and independent uniform selection.

Comparison for AffineHeavyTailedAdam.
Result Oracle complexity Novelty Limitations
(1) FixedMemoryAdamAffineHeavyTails (Ours) (⋆⋆) (review) O([1+Δ(L0+L1ε)ε2]
⋅[1+217q(σ1+s0/ε)q]) stochastic-gradient calls.
(2) Minibatch signSGD, Derived bound from (Kornilov et al. 2025) O([1+Δ(L0+L1ε)ε2]
⋅[1+(σ1+s0/ε)q]) calls; same problem and expected accuracy, without the Adam restriction.
(1): Matches known rate for fixed p using canonical bias-corrected Adam with fixed memories (0.9,0.999); no problem-class complexity improvement. (1) has much larger constants, including 217q, unbounded as p↓1.
(3) Minibatch signSGD (Kornilov et al. 2025), Thm. 1 O([1+ΔdL0Eε2+Δd3/2L1Eε]
⋅[1+(s0/ε)q](1+log⁡(1/α))) calls for average gradient norm ≤ε with probability 1−α; Euclidean generalized smoothness, σ1=0.
(1): Scope extends to affine noise and anchored ℓ∞→ℓ1 smoothness; (2) already covers this problem class. No established same-guarantee rate improvement. (1) gives expected accuracy, not the high-probability average-gradient guarantee of (3).
(4) Adam (Li et al. 2026), Cor. 1 O(1+dLΔε2+d2LΔσ2ε4) single-sample calls; p=2, L1=σ1=0, Euclidean L-smoothness and variance σ2. (1): Extends Adam to p<2, affine noise and generalized smoothness; fixed memories. On the overlap, no worse order if L0≤dL, s0≤dσ, dLΔ≥ε2. For L0=L, s0=σ, LΔ≥ε2, σ≥ε: O(LΔσ2/ε4) versus O(d2LΔσ2/ε4). (1) needs batches of order 1+s02/ε2, accuracy-dependent damping and a much smaller step. If dLΔ<ε2, its additional s02/ε2 cost can be worse.
(5) Vector Adam (Pang 2026), Thm. 6.4 Polynomial cost for relaxed (ρ,ε)-stationarity; bounded gradients, additive p-moment noise, p>4/3. Different criterion and function class; rates not comparable. (1): Ordinary gradient stationarity, unbounded gradients and all 1<p≤2 under generalized smoothness; canonical updates instead of random step multipliers. (1) requires generalized smoothness and accuracy-sized batches; (5) does not require gradient Lipschitz regularity.

Abbr: s0=∑iσ0,i; q=p/(p−1); α∈(0,1) is failure probability. L0E,L1E are Euclidean generalized-smoothness constants; L is the Euclidean gradient Lipschitz constant; σ2 bounds E∥g−∇f∥22 in (4). ρ>0 is the relaxation parameter in (5). The O constants in (2), (3) may depend on fixed p; all costs count individual stochastic-gradient calls, including batches.

Kornilov, Nikita, Philip Zmushko, Andrei Semenov, Mark Ikonnikov, Alexander Gasnikov, and Alexander Beznosikov. 2025. Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2502.07923.
Li, Huan, Yiming Dong, and Zhouchen Lin. 2026. On the O(dK1/4) Convergence Rate of AdamW Measured by ℓ1 Norm. https://doi.org/10.48550/arXiv.2505.11840.
Pang, Yijiang. 2026. The Convergence Behavior of Adam Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2607.27383.

Lean setup