← All setups

Expected Generalized Smooth Adam — Adam under Generalized Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Adam under Generalized Smoothness · Lean proof

Adam under Generalized Smoothness

We consider minimizing a differentiable, possibly nonconvex function f:Rd→R, where d≥0 is an integer. The function f is (L0,L1)-smooth with L0,L1≥0, and a given starting point x0 satisfies f(x0)−infxf(x)≤Δ for Δ≥0. At x, the oracle returns an unbiased stochastic gradient with variance at most σ2, where σ≥0, using independent, identically distributed samples. We analyze Adam with positive initial second moments. For ε>0, the goal is a measurable output x¯ satisfying E∥∇f(x¯)∥2≤ε2, with expectation over sampling and algorithm randomness.

The optimization problem is infx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The algorithm receives d, the measurable sample space Ω, L0,L1,σ,Δ,ε, the starting point x0∈Rd, and a momentum parameter β∈[0,1).

Our assumptions:

Assumption 1 (Generalized smoothness). The function f is differentiable everywhere, and for every x,y∈Rd, L1∥y−x∥≤1⟹∥∇f(y)−∇f(x)∥≤(L0+L1∥∇f(x)∥)∥y−x∥.

Assumption 2 (Initial objective gap). For every x∈Rd, f(x0)−f(x)≤Δ.

Assumption 3 (Stochastic gradient oracle). Let p be a probability measure on Ω. The oracle is represented by a jointly measurable map g:Rd×Ω→Rd. For every x∈Rd, the map g(x,⋅) is Bochner integrable, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2. The sample sequence (ξt)t≥0 has a joint probability law Q on ΩN: its coordinate maps are measurable, mutually independent, and each has law p. At its tth query x, the oracle returns g(x,ξt). The algorithm’s randomness is independent of this sequence. Queries may be made at any point of Rd.

Our result is algorithm-specific: we analyze Adam with the following recurrence. The algorithm chooses constants 0<ρ≤1,η>0,τ>0,vinit>0,n∈Z≥0, using the available inputs. Starting from the given x0, it initializes m0=0 and vi0=vinit for i=1,…,d. Each query and update is gt=g(xt,ξt),mt+1=βmt+(1−β)gt,vit+1=(1−ρ)vit+ρ(git)2,xit+1=xit−ηmit+1vit+1+τ,i=1,…,d. The algorithm independently draws K uniformly from {0,…,n}. After an allotted budget of T∈Z≥0 oracle calls, its output is x¯={xK,K<T,x0,K≥T. Thus, when T≥n+1, the output is the uniformly selected queried iterate xK.

The required output is measurable, its squared gradient norm is integrable, and it satisfies EP[∥∇f(x¯)∥2]≤ε2, where P is the joint law of the independent selection K and sample sequence (ξt)t≥0.

Proved result

⌈2100⋅(d+1)2⋅(1+L0+L1)10⋅(1+σ2)⋅(1+Δ)12(1−β)4⋅ε4+21−β⌉+

OracleTemplate.Convergence LongTails.Setups.GeneralizedSmoothAdam.spec
  OracleTemplate.ExpectedGeneralizedSmoothAdam.budget

Relevant previous results

  • Shen-Yi Zhao, Yin-Peng Xie, Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. 2021. Complexity: O((1+L0Δ/ε2)(1+σ2/ε2)) stochastic-gradient oracle calls, including minibatches, for SNGD to achieve E∥∇f(X)∥≤ε; L0,L1,σ>0 and ε≤cL0/L1, with universal c>0.
  • Amirhossein Reisizadeh, Haochuan Li, Subhro Das, Ali Jadbabaie. Variance-reduced Clipping for Non-convex Optimization. 2023 preprint, v2; published ICASSP 2025. Complexity: O((1+L0Δ/ε2)(1+σ2/ε2)) stochastic-gradient oracle calls, including minibatches, for ClippedSGD to achieve E∥∇f(X)∥≤ε; L0>0 and ε≤cL0/L1, with universal c>0 and no such restriction when L1=0.