← All setups

Stochastic Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Smooth Convex Minimization

We consider minimizing a differentiable 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 unbiased stochastic gradients with variance at most σ2 and an exponential squared-error bound, where σ≥0, using independent identically distributed samples. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ over oracle and 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 everywhere, its gradient is Fréchet differentiable, and for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇2f(x)∥op≤L0+L1∥∇f(x)∥. Here ∇2f(x):E→E is the derivative of the gradient.

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 (Light-tailed stochastic gradients). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable, its squared error is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. When σ>0, the exponential below is integrable and satisfies, for every x∈E, Eξ∼ν[exp⁡(∥g(x,ξ)−∇f(x)∥2σ2)]≤e. When σ=0, the variance condition gives g(x,ξ)=∇f(x) for ν-almost every ξ, for each fixed x.

The samples (ξk)k≥0 are measurable, mutually independent random variables with common law ν under a joint probability law Q. At call k, a query x∈E receives g(x,ξk). The algorithm’s randomness is independent of the entire sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯∈E must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the algorithm’s randomness and the oracle samples with law Q.

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⋆)≤Δ. The jointly measurable oracle is unbiased, with integrable gradient and squared error, E∥g(x,ξ)−∇f(x)∥2≤σ2, and Eexp⁡(∥g(x,ξ)−∇f(x)∥2/σ2)≤e for σ>0; σ=0 means exact gradients almost surely. Samples are IID with marginal p under probability law P. Parameters L0,R,Δ,ε>0, L1,σ≥0, and δ∈(0,1) are supplied. Target: measurable x^ with P{f(x^)−f(x⋆)>ε}≤δ. Costs count individual stochastic-gradient samples, including batches and trials.

High-probability convex optimization under StochasticGeneralizedSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) StochasticGeneralizedAcceleratedConvex (Ours) (⋆) (review) O(1+L0R2ε+min{⌈t2/3⌉ℓ,ℓ+(tℓ)2/3}+σ2R2ε2log⁡eδ)
(2) ARC-SG (Dvinskikh et al. 2026, Thm. 3)
Finite-dimensional case.
O~(1+t+(1+t)L0R2ε+(1+t)3σ2R2ε2+(1+t)3σ2L12L02) (1) removes (1+t)1/2 from optimization and (1+t)3 from noise, plus burn-in: polynomial termwise gains for t≫1. Scope: separable Hilbert spaces. (1)’s curvature term ℓ+(tℓ)2/3 can exceed t through logarithms when ℓ2≳t; no uniform total-cost dominance.
(3) RCSAG (Lobanov et al. 2026, Thm. 9)
Derived bound: finite-dimensional case, p=2, additive noise, Q=B(x0,R).
O([ℓ+L0R2ε+tJ+σ2R2ε2]log⁡eℓδ) (1): tJ becomes ℓ+(tℓ)2/3. For σ=0, Δ=L0R2, ε=L0R2/t4/3, t→∞, fixed δ: O(t2/3log2/3⁡t) versus (3)’s O(tlog⁡tlog⁡log⁡t). Otherwise unchanged terms can dominate. (1) needs light tails and batching; (3) allows finite pth moments, 1<p≤2, and gradient/gap-dependent noise. Logarithmic losses possible when L12Δ≲L0 and ℓ2≫t.
(4) Clipped SGD (Gaash et al. 2025, Thm. 1)
Finite-dimensional case.
O(1+(L0R2ε+t2)log⁡eTδ+σ2R2ε2log3⁡eTδ) (1): optimization L0R2/ε→L0R2/ε; startup t2→ℓ+(tℓ)2/3. For σ2log⁡(e/δ)≤L0ε, the optimization-term gain persists; total savings depend on noise/startup. Noise-dominated gain: log3⁡(eT/δ)→log⁡(e/δ). Scope: Hilbert spaces; stopped iterate instead of averaging. (1) additionally needs Δ and batching. (4) uses two samples per step.

Abbr: t=L1R, ℓ=1+log⁡(1+Δ/ε), J=min{ℓ,1+log⁡(1+L12Δ/L0)}. In (3), H0=O(L0), H1=O(L12), σ0=σ, σ1=σ2=0; p there is the moment order. T is the sufficient step count in (4) (two calls per step), defined implicitly by its bound. O~ in (2) suppresses polylogarithms in 1+t, 1+L12Δ/L0, 1+L0R2/ε, and 1/δ. ⌈⋅⌉ denotes upward rounding.

Dvinskikh, Darina, Alexander Gasnikov, Aleksandr Lobanov, and Ilgam Latypov. 2026. Localize, Restart, Accelerate: Stochastic Optimization Under Generalized Smoothness. https://doi.org/10.48550/arXiv.2609.06555.
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.

Lean setup