← All setups

Stochastic Composite Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Composite Convex Minimization

We consider minimizing F=f+ψ over a measurable convex set Q in a separable real Hilbert space E. The function f:E→R is convex and continuously differentiable, and f is (L0,L1)-smooth with L0>0 and L1≥0; ψ:E→R is measurable and convex on Q. A given feasible point x0 has bounded distance and objective gap to a minimizer x⋆. The oracle returns unbiased stochastic gradients with independent samples and bounded noise moments of order α∈(1,2], or exact proximal points. For ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying x¯∈Q and F(x¯)−F(x⋆)≤ε with probability at least 1−δ.

Write F(x)=f(x)+ψ(x). The optimization problem is minx∈QF(x). The norm ∥⋅∥ is induced by the inner product ⟨⋅,⋅⟩ on E, which carries its Borel sigma-algebra. Let Ω be the measurable sample space. The algorithm receives E, Ω, x0, L0, L1, R, Δ, σ, α, ε, and δ; the parameter G may enter only the oracle-call budget. Their ranges are L0>0,L1≥0,R>0,Δ>0,G≥0,σ≥0,1<α≤2,ε>0,0<δ<1. Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is convex and Fréchet differentiable on E, with continuous gradient. For every x,y∈E and M∈R, ‖∇f(x+θ(y−x))‖≤Mfor all θ∈[0,1]⟹∥∇f(x)−∇f(y)∥≤(L0+L1M)∥x−y∥. The set Q is convex and Borel measurable, and ψ is measurable on E and convex on Q.

Assumption 2 (Initial bounds). The given point x0 belongs to Q. There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ,∥∇f(x⋆)∥≤G.

Assumption 3 (Exact proximal access). There is a map p:R×E×E→E such that, for every a>0 and z,v∈E, p(a,z,v)∈argminu∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}. The map on R×E×E given by (a,z,v)⟼{p(a,z,v),a>0,0,a≤0 is measurable. A proximal query (a,z,v) returns p(a,z,v), with the stated minimization property for positive a.

Assumption 4 (Stochastic gradients and sampling). There is a probability measure μ on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥α is integrable under μ, with Eξ∼μ[g(x,ξ)]=∇f(x),Eξ∼μ[∥g(x,ξ)−∇f(x)∥α]≤σα. The samples (ξk)k≥0 are measurable, mutually independent, and each has law μ under their joint probability law. They are independent of the algorithm’s randomness. At oracle call k, a gradient query at any x∈E returns g(x,ξk); a proximal query returns the exact point specified above.

Gradient and proximal queries share a single total call budget, with each query counting as one call. After the allotted calls, the output x¯∈E must be measurable and satisfy P{x¯∉Q or F(x¯)−F(x⋆)>ε}≤δ, where P is the joint law of the algorithm’s randomness and the oracle samples.

Results

On a second-countable real Hilbert space, minimize F=f+ψ over a measurable convex set Q. The convex C1 function f satisfies ∥∇f(x)−∇f(y)∥≤(L0+L1supz∈[x,y]∥∇f(z)∥)∥x−y∥ globally; ψ is measurable and convex on Q, with an exact measurable proximal oracle. IID samples from μ give a jointly measurable, integrable oracle with ∫g(x,ω)dμ=∇f(x) and ∫∥g(x,ω)−∇f(x)∥αdμ≤σα, 1<α≤2. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R, F(x0)−F(x⋆)≤Δ, and ∥∇f(x⋆)∥≤G, with x0∈Q. Here L0,R,Δ,ε>0, L1,G,σ≥0, 0<δ<1. Target: P{xout∉Q or F(xout)−F(x⋆)>ε}≤δ.

Heavy-tailed composite acceleration under StochasticCompositeGeneralizedSmooth.
Result Oracle complexity Novelty Limitations
(1) StochasticCompositeGeneralizedAccelerated (Ours) (⋆⋆⋆) (review) O(2128α/(α−1)[1+(L0+L1G)R2/ε+T+(σR/ε)p]Hp+1); gradient samples plus prox calls.
(2) (Gorbunov et al. 2024), Thm. 2.7, n=1; derived ball reduction in Rd O(1+LbR2/εhb2+RG/εhb3/2+(σR/ε)phb); samples plus prox calls. (1): polynomial rather than exponential curvature cost when that term dominates noise and logarithmic overhead. At L1=0, removes RG/ε. (1) needs global smoothness and moments, rather than ball-local conditions; higher logarithmic powers and constants diverging as α↓1.
(3) (Kadi and Gorbunov 2026), Thm. 2, Remark 1; derived bound O(h[1+L0R2/ε+(σR/ε)p+(1+L1R)log(2+h(1+L1R)Δ/(L0R2))]); gradient samples. (1) extends unconstrained acceleration to composite/constrained objectives with possibly nonzero ∇f(x⋆). (3) requires Q=Rd, ψ=0, G=0, L1>0. (1) loses roughly logp⁡(⋅/δ) and an α-dependent constant on the overlap; no rate or adaptivity gain.
(4) (LongTails, n.d.) O([1+L0R2/ε+D+(L1RD)2/3+σ2R2ε2(1+log⁡(1/δ))2]hv); gradient samples. (1) adds composite/constrained objectives and 1<α<2. (4) applies only to the unconstrained finite-variance case, ψ=0, G=0, α=2. (1) has a linear L1R transient instead of power 2/3, and larger logarithmic overhead; no improvement on this overlap.

Abbr: p=α/(α−1); T=(1+L1R)log⁡(2+(1+L1R)Δ/(L0R2)); H=log⁡((8+L1R+(L0+L1G+L1σ)R2/ε+Δ/(L0R2)+σR/ε)/δ); Lb=(L0+L1G)e52L1R; hb=1+log⁡((2+LbR2/ε+RG/ε+(σR/ε)p)/δ); h=1+log⁡(K/δ) for the chosen horizon K in (3); D=log⁡(2+Δ/ε); hv=log⁡((2+L0R2/ε+L1R+D)/δ). G enters only the analysis of (1).

Gorbunov, Eduard, Abdurakhmon Sadiev, Marina Danilova, et al. 2024. High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise. https://arxiv.org/abs/2310.01860v2.
Kadi, Taha El Bakkali El, and Eduard Gorbunov. 2026. Acceleration Survives Heavy Tails and Generalized Smoothness. https://arxiv.org/abs/2610.23301v2.
LongTails: FiniteVarianceGeneralizedAcceleratedConvex. n.d. Repository convergence theorem and budget. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/FiniteVarianceGeneralizedAcceleratedConvex.lean.

Lean setup