← All setups

Nonconvex Optimization with Expected Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Expected Smoothness

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is Lipschitz, and a given starting point has bounded objective gap above a global lower bound. The oracle returns two unbiased stochastic gradients evaluated at queried points using a shared sample, with independent samples across calls. Their mean-square difference is bounded by squared query distance, and their variance grows at most linearly with the objective gap. For ε>0, the goal is a measurable output x¯∈E satisfying EP[∥∇f(x¯)∥]≤ε, where P is the joint law of sampling and independent algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which carries its Borel sigma-algebra. Fix a measurable sample space Ω, a starting point x0∈E, and parameters L>0,A≥0,C≥0,Δ≥0,ε>0. The algorithm receives E, Ω, L, A, C, Δ, ε, and x0; the objective, sampling distribution, and lower bound are accessible only through the stated oracle information.

Our assumptions:

Assumption 1 (Smoothness). The function f is Fréchet differentiable everywhere on E, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Lower bound and initial gap). There exists flow∈R such that flow≤f(x)for every x∈E,f(x0)−flow≤Δ.

Assumption 3 (Unbiasedness and expected smoothness). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable and Eξ∼ν[g(x,ξ)]=∇f(x). For every x,y∈E, both ∥g(x,ξ)−∇f(x)∥2 and ∥g(x,ξ)−g(y,ξ)∥2 are integrable under ν, with Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L2∥x−y∥2,Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤2A(f(x)−flow)+C.

At call k, a query (x,y)∈E×E returns (g(x,ξk),g(y,ξk)). The measurable random variables (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. Both replies within a call use the same sample. Each such paired query counts as one oracle call.

After the allotted calls, the output x¯ must be measurable, its gradient norm must be integrable under P, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Results

On a second-countable real Hilbert space with its Borel measurable structure, f is differentiable, ∇f is L-Lipschitz, f≥flow, and f(x0)−flow≤Δ. The jointly measurable unbiased oracle g uses IID samples from p, with integrable gradients and squared noise/differences, and satisfies Ep∥g(x)−g(y)∥2≤L2∥x−y∥2 and Ep∥g(x)−∇f(x)∥2≤2A(f(x)−flow)+C. Here L,ε>0 and A,C,Δ≥0. Same-sample pairs are available. The target is a measurable output with ∫∥∇f(xout(ω))∥dP(ω)≤ε.

Expected-smoothness nonconvex optimization: ExpectedSmoothnessNonconvex.
Result Oracle complexity Novelty Limitations
(1) NormalizedStormExpectedSmoothness (Ours) (⋆⋆) (review) O(1+AL+LΔ+AΔ+Cε2+LΔAΔ+Cε3)
(2) NSTORM (Upadhyay et al. 2026), Thm. 2(i), derived bound O(1+(LΔ)2ε4+(AΔ+C)LΔε2+(AΔ+C)3/2ε)
LΔ≥1, γ0=Δ/L; initialization included.
(1): ε−3 instead of ε−4 at fixed positive parameters. No worse order when LΔ≥1, ε2≤LΔ. (1) needs ABC structure; (2) also handles distance-growing BG noise beyond ABC.
(3) SGD (Khaled and Richtárik 2020), Cor. 1 O(1+LΔε2+LΔ(AΔ+C)ε4) (1) reduces the leading stochastic term by ≍AΔ+C/ε when ε≤min{AΔ+C,LΔ}. (1) needs MSS and same-sample pairs (two gradients); (3) needs single gradients and only objective smoothness LF≤L.
(4) SPIDER (Chen et al. 2023), Thm. 4, derived bound; affine-variance special case O(1+LΔ(1+Γ2)+Λ2ε2+LΔ(1+Γ)Λε3)
Varpg(x)≤Γ2∥∇f(x)∥2+Λ2; MSS restriction, A=LΓ2, C=Λ2. Retuning valid for ε≤min{1,LΔ}, Λε≤1+Γ.
(1): scope extends to ABC without affine variance. For Γ≥1, Λ≥LΔ, the ε−3 coefficient improves by ≍min{Γ,Λ/LΔ} within the stated range. (1) has a worse ε−3 coefficient when Λ≪ΓLΔ/(1+Γ); at Λ=0, ΓΔ>0, it loses ε−1 against (4).
(5) SPIDER-SFO (Fang et al. 2018), Thm. 1; bounded-variance special case A=0, C=σ2 O(1+LΔ+σ2ε2+LΔσε3)
0<ε≤σ.
(1) matches the known rate at A=0; scope extends to function-value-dependent, potentially unbounded variance.

Abbr: MSS: mean-square smoothness; ABC: the displayed function-gap variance bound; BG: Blum–Gladyshev noise. Varpg(x)=Ep∥g(x)−∇f(x)∥2; P: output probability law; LF: objective smoothness constant. Costs count stochastic gradient evaluations, including batches; one pair call costs two evaluations, so the same big-O bound applies. Γ,Λ,σ≥0 are the variance parameters in their rows. ≍ denotes equality up to universal factors.

Chen, Ziyi, Yi Zhou, Yingbin Liang, and Zhaosong Lu. 2023. “Generalized-Smooth Nonconvex Optimization Is as Efficient as Smooth Nonconvex Optimization.” In Proceedings of the 40th International Conference on Machine Learning, edited by Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, vol. 202. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v202/chen23ar.html.
Fang, Cong, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. 2018. “SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator.” Advances in Neural Information Processing Systems 31. https://proceedings.neurips.cc/paper_files/paper/2018/hash/1543843a4723ed2ab08e18053ae6dc5b-Abstract.html.
Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.
Upadhyay, Antesh, Arda Fazla, and Abolfazl Hashemi. 2026. Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization Under Blum–Gladyshev Noise. https://doi.org/10.48550/arXiv.2605.15314.

Lean setup