← All setups

Finite-Variance Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Finite-Variance Generalized Smooth Convex Minimization

We consider minimizing a convex function f:E→R on a separable real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A given point x0∈E has distance at most R>0 and objective gap at most Δ>0 from a global minimizer x⋆. The oracle returns an unbiased stochastic gradient with variance at most σ2, where σ≥0, using independent, identically distributed samples. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E satisfying P(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the samples and independent algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, x0, L0, L1, R, Δ, σ, ε, and δ; the objective and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is Fréchet differentiable on E, and its gradient ∇f:E→E is Fréchet differentiable. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). Generalized smoothness means that ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈E, where ∇2f(x) is a bounded linear operator from E to E.

Assumption 2 (Initial distance and objective gap). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 3 (Finite-variance stochastic gradients). 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 under ν, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. At call k≥0, a query x∈E receives g(x,ξk). The sample variables (ξk)k≥0 are measurable and mutually independent, each with law ν, and their joint law is independent of the algorithm’s randomness.

Queries may be made at any point of E. After the allotted oracle calls, the algorithm must return a measurable output x¯ satisfying P(f(x¯)−f(x⋆)>ε)≤δ.

Results

Convex f on a separable real Hilbert space has differentiable gradient and ∥∇2f(x)∥≤L0+L1∥∇f(x)∥. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ. IID samples with marginal p and joint law P feed a jointly measurable oracle g, with integrable g(x,⋅) and squared error, ∫g(x,ω)dp=∇f(x) and ∫∥g(x,ω)−∇f(x)∥2dp≤σ2. Known parameters satisfy L0,R,Δ,ε>0, L1,σ≥0, 0<δ<1. Target: measurable final output x^ with P{f(x^)−f(x⋆)>ε}≤δ. Costs count all stochastic-gradient samples, including pilots, corrections, and padding.

Finite-variance generalized-smooth convex optimization: FiniteVarianceGeneralizedSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AdaptiveRobustGeneralizedAcceleratedConvex (Ours) (⋆⋆⋆) (review)

O((W+vℓ)[1+log⁡(eM/δ)log⁡(e+WM/(v2ℓ2))]+v2ℓ+vℓlog⁡(eM/δ)).

For fixed c>0, δ≥(e+W)−c implies Oc(W+v2ℓ).

(2) FiniteVarianceGeneralizedAcceleratedConvex (Ours) (⋆⋆) (review) O((W+v2ℓ2)log⁡e(1+T+q+λ)δ)
(3) RCSAG (Lobanov et al. 2026), Thm. 9, App. C; derived bound on Rd, p=2, constant variance, Δ>ε. O((λ+T+qJ+v2)log⁡e(1+λ)δ)

(1): removes the ℓ factor on T when δ≥(e+W)−c and optimization dominates.

(1), (2): for T=1, v≤1, Δ=4ε, δ=1/2, q→∞, cost O(q) becomes O(q2/3), O(q2/3log⁡q), respectively. Extend to separable Hilbert spaces.

(1), (2): require a Hessian bound and finite variance; (3) permits first-order local smoothness, p<2, gradient/gap-dependent noise.

(1): worse for T=v=1, q=0, Δ=2ε, δ→0: O(ℓ2) versus O(ℓ).

(2): extra noise and optimization logarithms.

(4) Clipped accelerated mirror descent (Nguyen et al. 2023), Thm. 4.1; special case L1=0, p=2, Euclidean geometry. O(1+(T+v2)ℓ) (1): O(T) versus O(Tlog⁡T) for T→∞, δ=T−1, v2ℓ≤T, using Δ≤L0R2/2. No gain at constant δ. (1), (2) extend to L1>0. (1), (2) need Δ and differentiable gradients; (4) allows p<2 and mirror geometries. (1) has the tiny-δ loss shown against (3).
(5) (Tyurin 2026), Thm. 4.3; special case σ=0, exact gradients, Δ>ε. O(1+T+q[1+log+⁡min{L12ΔL0,Δε}]+log+⁡ΔL0R2) (2): at T=1, Δ=4ε, δ=1/2, q→∞, O(q2/3log⁡q) versus O(q). (1), (2) extend to finite-variance stochastic gradients. (2) pays log⁡(e(1+T+q+λ)/δ) on T when it dominates, even with exact gradients.
(6) FiniteVarianceGeneralizedRadiusAcceleratedConvex (Ours) (⋆⋆⋆) (review)

O((1+q+T+v2)H3),

H=loge(2+T+q+v)δ.

(7) Clip-SSTM (El Bakkali El Kadi and Gorbunov 2026), Thm. 2, Remark 1; derived bound on Rd, L1>0, α=2, supplied gap.

O(((1+q)[D+log⁡((1+q)HD)]+T+v2)HD),

D=log⁡(2+Δ/(L0R2)), HD=loge(2+T+q+v+D)δ.

(6): curvature qD→q up to logs; gain when large D dominates logarithmic overhead and unchanged terms. Updates and budget need no Δ. (6): extra logarithmic overhead and larger leading constant; covers only α=2, whereas (7) allows 1<α<2.
(8) Clip-SSTM (El Bakkali El Kadi and Gorbunov 2026), Thm. 2, Remark 2; derived radius-only bound on Rd, L1>0, α=2. O(((1+q)[q+log⁡((1+q)H)]+T+v2)H). (6): curvature q2→q up to logs. For T=v=1, δ=1/2, q→∞: O(qlog3⁡q) versus O(q2log⁡q). No total gain implied when unchanged terms dominate. (6): extra logarithmic overhead and larger leading constant; excludes the α<2 noise allowed by (8).
(9) Earlier repository bound (LongTails, n.d.); comparison with (2) on the identical setup. O((W+v2ℓ2)log⁡e(1+T+q+λ)δ) (6): no Δ needed. For λ≍q→∞, T=v=1, δ=1/2, admissible cosh instances give O(qlog3⁡q) versus O(q4/3log⁡q). (6): worse for small known gaps; e.g. fixed λ,T,v,δ gives O(qlog3⁡q) versus O(q2/3log⁡q). Extra optimization/noise logarithms and larger leading constant.
(10) Clipped SGD (Gaash et al. 2025), Thm. 1; derived bound on Rd, sub-Gaussian noise: Eexp⁡(∥g−∇f∥2/σ2)≤e. O((1+T+q2)H+v2H3) stochastic-gradient calls, including double sampling. (6): T→T and q2→q up to logs on the sub-Gaussian overlap; extends to finite variance. Unchanged noise can mask a total gain. (6): extra logarithmic factors on optimization terms.
(11) (Rudomanov et al. 2026), Thm. 3.7; special case σ=0, L1>0, Rd. O(T+(1+q)log⁡(2+q)) exact-gradient calls, including line-search queries. (6): extends the radius-only guarantee to finite-variance stochastic gradients; retains linear curvature dependence up to logarithms. (6): at σ=0, pays H3 on T and (1+q), versus no logarithm and log⁡(2+q), respectively.

Abbr: T=L0R2/ε, q=L1R, v=σR/ε, ℓ=log⁡(e/δ), λ=1+log⁡(1+Δ/ε), W=1+T+λ+(qλ)2/3, M=1+T+q+λ+v2ℓ2; J=1+min{log⁡(Δ/ε),log+⁡(L12Δ/L0)} in (3). log+⁡u=max{0,log⁡u}, with log+⁡0=0. The logarithmic fraction in (1) is zero at v=0. c>0 is fixed; constants in Oc may depend on c. p in prior-work rows denotes the noise moment order.

El Bakkali El Kadi, Taha, and Eduard Gorbunov. 2026. Acceleration Survives Heavy Tails and Generalized Smoothness. https://doi.org/10.48550/arXiv.2610.23301.
Gaash, Ofir, Kfir Yehuda Levy, and Yair Carmon. 2025. Convergence of Clipped SGD on Convex (L0,L1)-Smooth Functions. https://doi.org/10.48550/arXiv.2502.16492.
Lobanov, Aleksandr, Darina Dvinskikh, and Alexander Gasnikov. 2026. Accelerated Stochastic Method Under (H0,H1)-Smoothness and Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2609.33415.
LongTails: FiniteVarianceGeneralizedAcceleratedConvex. n.d. Repository theorem and public oracle budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/FiniteVarianceGeneralizedAcceleratedConvex.lean.
Nguyen, Ta Duy, Alina Ene, and Huy L. Nguyen. 2023. Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails. https://doi.org/10.48550/arXiv.2304.01119.
Rudomanov, Mikhail, Ivan Fomin, Alexander V. Gasnikov, and Fedor S. Stonyakin. 2026. Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization Under (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2610.21461.
Tyurin, Alexander. 2026. Near-Optimal Convergence of Accelerated Gradient Methods Under Generalized and (L0,L1)-Smoothness. https://doi.org/10.48550/arXiv.2508.06884.

Lean setup