← All setups

Composite Gap Accelerated — Composite Minimization with Gap Smoothness

Descriptions may be stale. Consult the linked Lean sources.

Composite Minimization with Gap Smoothness · Lean proof

Composite Minimization with Gap Smoothness

We consider minimizing F=f+ψ over a convex set Q in a real Hilbert space E, where f,ψ:E→R, f is differentiable and convex, and ψ is convex on Q. A local quadratic upper model for f depends on the objective gap to a minimizer x⋆∈Q. A given feasible starting point has bounded distance and objective gap to x⋆. The oracle returns exact gradients and proximal minimizers. For ε>0, the goal is a feasible output x¯ with F(x¯)−F(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈QF(x),F(x)=f(x)+ψ(x). Write ⟨⋅,⋅⟩ for the inner product on E and ∥⋅∥ for its induced norm. The algorithm receives E, the starting point x0∈E, and the parameters H0,H1≥0,R,Δ,ε>0.

Our assumptions:

Assumption 1 (Convexity and differentiability). The function f is convex and Fréchet differentiable on E. The set Q⊆E is convex, and ψ is convex on Q.

Assumption 2 (Minimizer and initialization). There exists x⋆∈Q such that x0∈Q and F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ.

Assumption 3 (Gap-dependent upper model). For every x∈Q and y∈E satisfying H1∥y−x∥≤1, f(y)≤f(x)+⟨∇f(x),y−x⟩+(H0+H1(F(x)−F(x⋆)))∥y−x∥2.

Assumption 4 (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 oracle returns ∇f(x) at x. Gradient queries may use any x∈E. A proximal query (a,z,v)∈R×E×E returns P(a,z,v), with the minimization property above required for positive a. Gradient and proximal calls count toward a single total oracle-call budget.

After the allotted calls, the output must satisfy x¯∈Q,F(x¯)−F(x⋆)≤εP-a.s.

Proved result

⌈8192⋅(1+R⋅H0ε+H1)⋅log⁡(4+R2⋅(H0ε+H1))⋅log⁡(2+Δε)⌉+

OracleTemplate.Convergence LongTails.Setups.CompositeGapSmooth.spec OracleTemplate.CompositeGapAccelerated.budget

Relevant previous results

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