← All setups

Composite Implicit Transport — Stochastic Composite Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Composite Stationarity · Lean proof

Stochastic Composite Stationarity

We consider minimizing F=f+ψ over a convex set Q in a finite-dimensional real inner product space E. The possibly nonconvex function f:E→R has an L-Lipschitz gradient and a ρ-Lipschitz Hessian, with L>0 and ρ≥0, while ψ:E→R is convex on Q. A given x0∈Q has objective gap at most Δ≥0. The oracle returns unbiased stochastic gradients with variance at most σ2, σ≥0, from independent identically distributed samples, or exact proximal minimizers Ta(z,v) of ∥u−z∥2/(2a)+⟨v,u−z⟩+ψ(u) over u∈Q, for a>0 and z,v∈E. For ε>0, the goal is a feasible output x¯ with E∥L(x¯−T1/L(x¯,∇f(x¯)))∥≤ε.

The optimization problem is minx∈QF(x),F(x):=f(x)+ψ(x). The norm is induced by the inner product on E; operator norms below are the induced operator norms. The algorithm receives E, the measurable sample space Ω, L, ρ, σ, Δ, ε, and x0, and accesses the objective through the oracle described below.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f is Fréchet differentiable on E, its gradient is Fréchet differentiable on E, and, for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥. Here ∇2f(x) is a linear operator from E to E.

Assumption 2 (Convex composite term and proximal access). The set Q⊆E is convex, and, for every x,y∈Q and t∈[0,1], ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y). For every a>0 and z,v∈E, the exact proximal reply satisfies Ta(z,v)∈Q,Ta(z,v)∈argminu∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}. The map on R×E×E equal to Ta(z,v) when a>0 and to 0 otherwise is measurable.

Assumption 3 (Initial objective gap). The given starting point and gap bound satisfy x0∈Q,F(x0)−F(x)≤Δfor every x∈Q.

Assumption 4 (Stochastic gradient access). There is a probability measure μ on Ω and a jointly measurable map g:E×Ω→E. For each x∈E, the random vector 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≤σ2. The oracle samples form a measurable, mutually independent sequence (ξk)k≥0 with common law μ, under a joint probability law P on ΩN. This sequence is independent of the algorithm’s internal randomness. At call k, a gradient query at any x∈E returns g(x,ξk); a proximal query returns Ta(z,v) exactly. Each query of either type counts as one oracle call in a common budget. Proximal queries may use any real a, although the minimization and measurability conditions above concern positive a.

Define the composite gradient mapping by GL(x):=L(x−T1/L(x,∇f(x))). After the allotted oracle calls, the output x¯ must be measurable, its residual norm ∥GL(x¯)∥ must be integrable, and it must satisfy x¯∈QP-a.s.,EP[∥GL(x¯)∥]≤ε, where P is the joint law of the algorithm’s internal randomness and the independent oracle sample sequence.

Proved result

⌈106⋅(L⋅Δε2+(1+σ2ε2)⋅Δ⋅ρ⋅εε2+σ2ε2+1)⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticCompositeHessianLipschitz.spec
  OracleTemplate.CompositeTransport.budget

Relevant previous results

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