← All setups

Fixed Memory Adam Affine Heavy Tails — Adam with Affine Heavy-Tailed Noise

Descriptions may be stale. Consult the linked Lean sources.

Adam with Affine Heavy-Tailed Noise · Lean proof

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

Proved result

(1+⌈(131072⋅(σ1+(∑i=0d−1σ0(i))ε))pp−1⌉+)⋅(1+⌈4294967296⋅Δ⋅(L0+L1⋅ε)ε2⌉+)

OracleTemplate.Convergence LongTails.Setups.AffineHeavyTailedAdam.spec
  LongTails.Theorems.FixedMemoryAdamAffineHeavyTails.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.