← All setups

Heterogeneous Adam First Moment — Adam with Heterogeneous Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

Adam with Heterogeneous Symmetric Noise · Lean proof

Adam with Heterogeneous Symmetric Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on the Euclidean space E=Rb×Rh, where b,h≥0 are integers with b+h>0. Its gradient is L-Lipschitz, with L>0, and the given starting point x0 has objective gap at most Δ>0 above the infimum. The oracle returns unbiased stochastic gradients from independent, identically distributed samples. Body-coordinate noise is symmetric with bounded first moment and integrably Lipschitz sample paths; head-coordinate noise has bounded second moment. We analyze heterogeneous Adam, seeking a measurable output x¯ satisfying EP∥∇f(x¯)∥≤ε for ε>0, where P is the joint law of sampling and algorithm randomness.

The optimization problem is infx∈Ef(x). Write x=(xB,xH) for the body and head blocks, with coordinate sets B={1,…,b} and H={1,…,h}. Throughout, ∥⋅∥ denotes the Euclidean norm. The parameters satisfy L,Δ,ε,δ>0,M,σB,σH≥0. The algorithm receives b,h, the measurable sample space Ω, L,M,σB,σH,Δ,ε,δ, and x0∈E.

Our assumptions:

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

Assumption 2 (Unbiased heterogeneous noise). There exist a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, g(x,⋅) is Bochner integrable under p, and Eξ∼p[g(x,ξ)]=∇f(x). Define the noise e(x,ξ)=g(x,ξ)−∇f(x). For every x∈E, Eξ∼p[∑i∈B|eB,i(x,ξ)|]≤σB,Eξ∼p[∑j∈HeH,j(x,ξ)2]≤σH2. The head squared-noise sum is integrable under p. Each body coordinate has a symmetric noise distribution: eB,i(x,ξ)=d−eB,i(x,ξ),ξ∼p,x∈E,i∈B.

Assumption 3 (Samplewise body-noise regularity). There exists a measurable, integrable function K:Ω→R with Eξ∼p[K(ξ)]≤M. For p-almost every ξ, K(ξ)≥0 and, simultaneously for all x,y∈E and i∈B, |eB,i(x,ξ)−eB,i(y,ξ)|≤K(ξ)∥x−y∥.

At call t, a query x∈E returns g(x,ξt). The sample variables (ξt)t≥0 are measurable, mutually independent, and each has law p; they are independent of the algorithm’s randomness.

Our result is algorithm-specific: we analyze heterogeneous Adam, using bias-corrected Adam updates on the body and cumulative squared-gradient normalization on the head. The algorithm chooses a nonnegative integer T, a scalar r0>0, and deterministic positive step sequences (ηtB)t≥0 and (ηtH)t≥0 from the available inputs. The momentum coefficients and denominator offset are fixed as α=910,β=9991000,δ>0. Initialize the iterates at the given x0, with m0=0,vB,i0=0,vH,j0=r02. For gt=g(xt,ξt), the body coordinates obey, for i∈B, mB,it+1=αmB,it+(1−α)gB,it,vB,it+1=βvB,it+(1−β)(gB,it)2,m^B,it+1=mB,it+11−αt+1,v^B,it+1=vB,it+11−βt+1,xB,it+1=xB,it−ηtBm^B,it+1δ+v^B,it+1. The head coordinates obey, for j∈H, mH,jt+1=gH,jt,vH,jt+1=vH,jt+(gH,jt)2,xH,jt+1=xH,jt−ηtHgH,jtvH,jt+1. Independently of the samples, draw J uniformly from {0,…,T}. After N≥0 oracle calls, the output rule is x¯={xJ,J≤N,x0,J>N. Thus, when N≥T, the output is uniformly selected from x0,…,xT. The required output is measurable, its gradient norm is integrable under P, and the accuracy criterion is EP[∥∇f(x¯)∥]≤ε.

Proved result

⌈1084⋅(1+(1+(bodyDim+headDim)2⋅(L+M)2⋅ΔL)⋅(bodyDim⋅δ+σBody+headDim⋅σHead)2ε4+1+(bodyDim+headDim)2⋅(L+M)2⋅ΔL+headDim⋅(1+2⋅L⋅Δ+headDim⋅σHead2)⋅1+(bodyDim+headDim)2⋅(L+M)2⋅ΔLε2)⋅(log⁡(1084⋅(1+σBody)⋅(1+(1+(bodyDim+headDim)2⋅(L+M)2⋅ΔL)⋅(bodyDim⋅δ+σBody+headDim⋅σHead)2ε4+1+(bodyDim+headDim)2⋅(L+M)2⋅ΔL+headDim⋅(1+2⋅L⋅Δ+headDim⋅σHead2)⋅1+(bodyDim+headDim)2⋅(L+M)2⋅ΔLε2)))4⌉+

OracleTemplate.Convergence LongTails.Setups.HeterogeneousSymmetricFirstMoment.spec
  LongTails.Theorems.HeterogeneousAdamFirstMoment.budget

Relevant previous results

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