← All setups

Gap-Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Gap-Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. A local quadratic upper model has curvature controlled by the gap to a global minimizer x⋆, and a given starting point has bounded distance and objective gap to that minimizer. The oracle returns independent-sample, unbiased stochastic gradients whose variance is bounded proportionally to the squared gradient norm. For tolerance ε>0 and failure probability δ∈(0,1), the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)>ε}≤δ, where P is the joint law of sampling and independent algorithm randomness.

The optimization problem is minx∈Ef(x). Equip E with its Borel sigma-algebra, and write ∥⋅∥ for the norm induced by its inner product. Let Ω be a measurable sample space and x0∈E the given starting point. The parameters satisfy H0≥0,H1≥0,R>0,Δ>0,ρ≥1,0<ε≤Δ,0<δ<1. The algorithm receives E, Ω, x0, and all seven parameters H0,H1,R,Δ,ρ,ε,δ.

Our assumptions:

Assumption 1 (Convexity and initialization). The function f is Fréchet differentiable everywhere on E and satisfies f((1−t)x+ty)≤(1−t)f(x)+tf(y),x,y∈E,t∈[0,1]. There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R,f(x0)−f(x⋆)≤Δ.

Assumption 2 (Gap-dependent upper model). For every x,y∈E satisfying (23+6)H1∥y−x∥≤1, the objective obeys f(y)≤f(x)+⟨∇f(x),y−x⟩+(H0+H1(f(x)−f(x⋆)))∥y−x∥2.

Assumption 3 (Strong-growth stochastic oracle). 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 ∥g(x,⋅)−∇f(x)∥2 is integrable under ν, with Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤(ρ−1)∥∇f(x)∥2. At call k≥0, a query x∈E receives g(x,ξk), where the measurable samples (ξk)k≥0 are mutually independent with common law ν. Algorithm randomness is independent of the entire sample sequence.

After the allotted oracle calls, the algorithm must return a measurable output x¯∈E with P{f(x¯)−f(x⋆)>ε}≤δ.

Results

Convex differentiable f on a separable real Hilbert space with its Borel σ-algebra; a minimizer x⋆ satisfies ∥x0−x⋆∥≤R and f(x0)−f(x⋆)≤Δ. For all x,y with (23+6)H1∥y−x∥≤1, f(y)≤f(x)+⟨∇f(x),y−x⟩+(H0+H1[f(x)−f(x⋆)])∥y−x∥2. The jointly measurable oracle is integrable, unbiased, and has integrable squared error satisfying ∫∥g(x,ω)−∇f(x)∥2dp(ω)≤(ρ−1)∥∇f(x)∥2; samples are IID with marginal probability measure p and joint law P. Parameters satisfy H0,H1≥0, R,Δ>0, ρ≥1, 0<ε≤Δ, 0<δ<1. Target: a measurable output x^ with P(f(x^)−f(x⋆)>ε)≤δ.

High-probability optimization under GapSmoothStrongGrowth.
Result Oracle complexity Novelty Limitations
(1) GapSmoothStrongGrowthHighProbability (Ours) (⋆⋆⋆) (review) O(ρℓδ[(1+RH1)ℓΔ
+RH0/ε])
(2) RCSAG (Lobanov et al. 2026, Thm. 9, v1)

O(ℓS[S+RH0/ε
+RH1JH
+(ρ−1)R2(H0/ε+H1JH)]).

Rd; pure second-moment specialization; Q=B(x0,R).

(1): at fixed ρ=2, positive H0,H1,R,Δ,δ, ε→0: O(ε−1/2) instead of O(ℓSε−1). More generally, stochastic-term gain when RH0/ε≫ρℓδ/(ρ−1).

H1-term gain if (ρ−1)RH1JH≫ρℓδℓΔ.

(1) excludes additive/gap noise, moments below two, and martingale sampling. Near ρ=1, its curvature term uses ℓΔ instead of JH; no uniform dominance.
(3) (Dvinskikh et al. 2026, App. I, Thm. 7, v1)

O(ρ[1+L1R
+(1+L0R2/ε)3]polylog(Z)).

Rd, L0,L1>0; convex (L0,L1)-smooth components, almost-sure strong growth; supplied gap certificate Δ.

(1): ε−3→ε−1/2 at fixed positive parameters on the overlap H0≍L0, H1≍L12. Scope: second moments replace almost-sure strong growth; no componentwise regularity.
(4) Accelerated SGD (Vaswani et al. 2019, Thm. 2)

O(1+ρT).

H1=0, Rd; expected target E[f(x^)−f(x⋆)]≤ε.

(1): scope extends to H1>0; matches known ρT accuracy dependence at H1=0, with logarithmic confidence overhead. (1) uses batches ⌈ρ⌉; its high-probability budget includes ℓδ and ℓΔ, absent from this expected guarantee.
(5) Derived bound: Markov conversion of (Vaswani et al. 2019, Thm. 2)

O(1+ρT/δ).

H1=0, Rd; high-probability target.

(1): if Δ≤LR2 and T≥1, costs O(ρTℓδ) instead; confidence gain 1/(δℓδ). (1) uses batches ⌈ρ⌉.
(6) Derived bound: AGNES + proxBoost (Gupta and Wojtowytsch 2025, Thm. 15, v3)(Davis and Drusvyatskiy 2020, Thm. 7)

O(ρ(1+T)ℓT[1+log⁡(ℓT/δ)]).

H1=0, Rd; high-probability target.

(1): for Δ≤LR2, T≥1, removes the ℓT overhead, up to nested confidence logarithms. Scope extends to H1>0; smooth-case acceleration is already known. (1) uses batches ⌈ρ⌉.

Abbr: Costs count individual stochastic-gradient samples, including batches and trials. ℓδ=1+log⁡(1/δ), ℓΔ=log⁡(1+Δ/ε), S=⌈log2⁡(Δ/ε)⌉, ℓS=1+log⁡((1+S)/δ). For H0,H1>0, JH=min{S,⌈max{0,log2⁡(H1Δ/H0)}⌉}; JH=0 if H1=0 and JH=S if H0=0<H1. L=2H0, T=LR2/ε, ℓT=1+log⁡(1+T). L0,L1 are component generalized-smoothness constants: ∥∇fω(y)−∇fω(x)∥≤(L0+L1∥∇fω(x)∥)∥y−x∥ for ∥y−x∥≤1/L1; almost-sure strong growth means ∥∇fω(x)∥2≤ρ∥∇f(x)∥2. Z=2+L1R+L12Δ/L0+L0R2/ε+1/δ; polylog(Z) denotes the cited bound’s unspecified fixed polynomial in 1+log⁡Z.

Davis, Damek, and Dmitriy Drusvyatskiy. 2020. “High Probability Guarantees for Stochastic Convex Optimization.” In Proceedings of Thirty Third Conference on Learning Theory, edited by Jacob Abernethy and Shivani Agarwal, vol. 125. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v125/davis20a.html.
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.
Gupta, Kanan, and Stephan Wojtowytsch. 2025. Nesterov Acceleration in Benignly Non-Convex Landscapes. https://doi.org/10.48550/arXiv.2410.08395.
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.
Vaswani, Sharan, Francis Bach, and Mark Schmidt. 2019. “Fast and Faster Convergence of SGD for over-Parameterized Models and an Accelerated Perceptron.” In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, edited by Kamalika Chaudhuri and Masashi Sugiyama, vol. 89. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v89/vaswani19a.html.

Lean setup