← All setups

Adam under Generalized Smoothness

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Differentiable f:Rd→R, f(x0)−inff≤Δ, and ∥∇f(y)−∇f(x)∥≤(L0+L1∥∇f(x)∥)∥y−x∥ whenever L1∥y−x∥≤1. The jointly measurable oracle uses IID samples, is unbiased, and satisfies E∥g(x,ξ)−∇f(x)∥2≤σ2; L0,L1,σ,Δ≥0, ε>0. The setup requires uncorrected coordinate Adam with prescribed β∈[0,1) and a uniformly selected pre-update iterate X. The target is E∥∇f(X)∥2≤ε2, over sampling and output randomization.

Adam under GeneralizedSmoothAdam.
Result Oracle complexity Novelty Limitations
(1) ExpectedGeneralizedSmoothAdam (Ours) (⋆⋆) (review) O(A(1+σ2)ε4+11−β)
(2) Adam (Jin et al. 2026), Thm. B.2; 0<p<1 O(1+d2ε4[1+log+⁡dε]2) Remaining parameters fixed; polynomial factors not displayed. Expected RMS; no p=1 guarantee. (1): Scope extends the same Adam expectation guarantee to p=1, including f=cosh. On the overlap, removes horizon logarithms; no full-class rate comparison. (1) needs IID bounded variance instead of conditional, gap/gradient-dependent second moments; fixes damping 1 and v0=(1+σ2)1.
(3) Adam (Jin et al. 2026), Claim B.1; globally smooth special case O(1+d2P112[1+σ2ε4+1ε2]); expected RMS, damping 1, v0=(1+σ2)1. (1): Smaller explicit polynomial parameter powers on the globally smooth overlap; matches the ε−4 exponent. Constants are unoptimized. (1) requires IID noise; (3) permits conditional bounded variance.
(4) Adam (Jin et al. 2026), Thm. B.1; p=1 O(1+d2(1+log⁡(1/δ))2[1δε4+1ε2]) Remaining parameters fixed; polynomial factors not displayed. Average squared gradient ≤ε2 with probability 1−δ. (1): Expected RMS for one fixed run; (4) tunes steps to δ. Criteria differ; costs are not directly comparable. (1) needs IID bounded variance instead of conditional, gap/gradient-dependent second moments.
(5) Adam (Zhang et al. 2025), Thm. 2; global coordinatewise smoothness O(ε−4) for sufficiently small ε, other parameters fixed; mean gradient norm ≤ε. Parameter factors unextracted; 0<β1≤β2<1. (1): Local Euclidean instead of global coordinatewise smoothness (allows cosh); RMS instead of mean norm. No established cost comparison. (1) requires IID bounded variance; (5) allows conditional coordinatewise affine variance and uses damping inside the square root.
(6) NSGD-M (Hübler et al. 2024), Cor. 16; L1>0 O(1+S4ε4[1+log+⁡Sε]4); mean gradient norm ≤ε. Schedule uses L1; common C2 class. (1): RMS certificate. For the shared mean target, noise dependence is Aσ2 instead of σ4 up to logarithms when σ≥max{1,L1Δ,L0/L1}; total gain requires σ2≫A. (1) has dimension dependence and worse smoothness/gap powers (Δ12 versus Δ4); needs σ for initialization. Noise comparison concerns only (6)’s displayed schedule.

Abbr: Costs count individual stochastic-gradient calls. RMS means (E∥∇f(X)∥2)1/2; mean means E∥∇f(X)∥. log+⁡t=max{0,log⁡t} for t>0, and log+⁡0=0; δ∈(0,1) is failure probability. A=(d+1)2(1+L0+L1)10(1+Δ)12/(1−β)4, S=L1Δ+σ+L0/L1. In (2), p replaces the gradient power 1 in local smoothness, with coefficient Lp>0. In (3), L is a global gradient Lipschitz constant and P=1+(1−β)−2+Δ+∥∇f(x0)∥+L+σ2; compare with (1) at L0=L,L1=0. Global coordinatewise smoothness in (5) means |∂if(y)−∂if(x)|≤(L0/d+L1|∂if(x)|)∥y−x∥ for all x,y,i.

Hübler, Florian, Junchi Yang, Xiang Li, and Niao He. 2024. “Parameter-Agnostic Optimization Under Relaxed Smoothness.” In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, edited by Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li, vol. 238. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v238/hubler24a.html.
Jin, Ruinan, Difei Cheng, Ling Chen, Jun Luo, Hao Zhou, and Youzhi Zhang. 2026. Adam Under Generalized Smoothness with Second-Moment-Type Stochastic Gradients. https://doi.org/10.48550/arXiv.2609.37787.
Zhang, Qi, Yi Zhou, and Shaofeng Zou. 2025. Convergence Guarantees for RMSProp and Adam in Generalized-Smooth Non-Convex Optimization with Affine Noise Variance. https://doi.org/10.48550/arXiv.2404.01436.

Lean setup