← All setups

Stochastic Composite Generalized Accelerated — Stochastic Composite Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Composite Convex Minimization · Lean proof

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.

Proved result

⌈2128+128α−1⋅(1+(L0+192⋅L1⋅σ+L1⋅G)⋅R2ε+(1+L1⋅R)⋅log⁡(2+(1+L1⋅R)⋅ΔL0⋅R2)+(σ⋅Rε)αα−1)⋅(log⁡(8+L1⋅R+(L0+192⋅L1⋅σ+L1⋅G)⋅R2ε+ΔL0⋅R2+σ⋅Rεδ))2+1α−1⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticCompositeGeneralizedSmooth.spec
  OracleTemplate.StochasticCompositeGeneralized.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.