← All setups

Adam Heavy Tailed Fixed Momentum — Adam with Heavy-Tailed Gradients

Descriptions may be stale. Consult the linked Lean sources.

Adam with Heavy-Tailed Gradients · Lean proof

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¯)∥]≤ε.

Proved result

1+⌈400000000⋅Δ⋅Lε2⋅(1000000000000+(100000⋅σε)αα−1)⌉+

OracleTemplate.Convergence LongTails.Setups.HeavyTailedAdam.spec OracleTemplate.AdamHeavyTailedFixedMomentum.budget

Relevant previous results

  • Florian Hübler, Ilyas Fatkhullin, Niao He. From Gradient Clipping to Normalization for Heavy Tailed SGD. 2024 (OPT workshop; AISTATS publication 2025). Complexity: O(1+ΔLε2[1+(6σε)α/(α−1)]) stochastic-gradient oracle calls, with fixed cost including initialization, for normalized SGD with momentum and a uniformly selected iterate satisfying E∥∇f(x)∥2≤ε.