← All setups

Adam with Heterogeneous Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

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

Results

f:Rb+h→R is differentiable with L-Lipschitz gradient and f(x0)−inff≤Δ. The jointly measurable, integrable oracle g(x,ξ) is unbiased, with IID samples of law p. For z=g−∇f, body coordinates are individually symmetric, Ep∥zb(x,ξ)∥1≤σb, and Ep∥zh(x,ξ)∥22≤σh2. Almost surely, |zi(x,ξ)−zi(y,ξ)|≤K(ξ)∥x−y∥2 for every body coordinate and all x,y, with measurable K≥0 and EpK≤M. Here b+h>0, L,Δ,ε,δ>0 and M,σb,σh≥0. The setup restricts algorithms to bias-corrected body Adam with (β1,β2)=(0.9,0.999) and head AdaGrad. Target: ∫∥∇f(xJ)∥2dP≤ε, where J is independent and uniform over executed iterates and P includes the IID sample law.

Comparison for HeterogeneousSymmetricFirstMoment.
Result Oracle complexity Novelty Limitations
(1) HeterogeneousAdamFirstMoment (Ours) (review) O(Q[1+log⁡((1+σb)Q)]4) single-sample gradient calls.
(2) Derived bound: median-of-three + SGD (Ghadimi and Lan 2013, Cor. 2.2) O(1+LΔε2+LΔ(σb2+σh2)ε4) gradient calls, counting three samples per step. Body medians; one sampled head. Full target problem class; no K assumption. (1): No established improvement. Method-specific fixed-memory Adam/AdaGrad analysis; no adaptivity gain: updates use L,Δ,d,T. (1) needs K; noise coefficient inflated by at least d2(1+M/L)2, plus logarithms. For bδ>0, noiseless cost retains ε−4; large universal constant.
(3) Median method (MedianFirstMomentNonconvex.lean, n.d.). Special case h=0; paired-query oracle.

O([1+log⁡(1+LΔ/ε2)]2

⋅[1+LΔ+σb2ε2+bMσbΔε3]) paired calls (two gradients at a shared sample per call), including median batches.

(1): Single-point oracle on h=0 overlap. Scope: also permits a nonsymmetric finite-variance head. (1): ε−4 versus ε−3 for fixed positive M,σb; stronger samplewise noise regularity. Different oracle access.
(4) Adam (Dereich et al. 2026, Thm. 1.2). Strongly convex expected C2 loss, bounded IID data and uniformly bounded iterates; initialization independent of samples. O(nB) gradient calls; Lp parameter error Oβ(B−1+γn) for fixed β. Requires β12<β2, β2≥1/p, γn↓0, and γn−γn+1γn2+∑m=n∞γmp→0. No comparable stationarity budget. (1): Adam-specific scope extends to nonconvex objectives and unbounded symmetric first-moment body noise, including atoms, with fixed memory. Classes are incomparable. (1) requires body symmetry and K; expected random-iterate stationarity replaces Lp parameter accuracy.

Abbr: b,h: body/head dimensions; d=b+h; δ: Adam stabilizer; Δ: initial gap bound; σb,σh: noise bounds; M: mean noise-Lipschitz modulus. A=1+d2(L+M)2Δ/L; Q=1+A(bδ+σb+hσh)2/ε4+[A+h(1+LΔ+hσh2)A]/ε2. T: horizon. In (3), the full-vector first-moment and averaged noise-Lipschitz bounds are σb and bM. In (4), B: batch size, n: steps, γn: step size, β: memory parameters, and integer p bounds iterate norms and specifies the error moment; Oβ holds for fixed problem data and β.

Dereich, Steffen, Thang Do, Arnulf Jentzen, and Philippe von Wurstemberger. 2026. Adam Symmetry Theorem: Characterization of the Convergence of the Stochastic Adam Optimizer. https://doi.org/10.48550/arXiv.2511.06675.
Ghadimi, Saeed, and Guanghui Lan. 2013. “Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming.” SIAM Journal on Optimization 23 (4): 2341–68. https://doi.org/10.1137/120880811.
MedianFirstMomentNonconvex.lean. n.d. Lean theorem in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/MedianFirstMomentNonconvex.lean.

Lean setup