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
over a convex set in a real
Hilbert space , where , is differentiable and convex, and is convex on . A local quadratic upper model for
depends on the objective gap to a
minimizer . A given
feasible starting point has bounded distance and objective gap to . The oracle returns exact
gradients and proximal minimizers. For , the goal is a feasible
output with
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is Write for the inner
product on and for its induced norm. The
algorithm receives , the starting
point , and the parameters
Our assumptions:
Assumption 1 (Convexity and differentiability). The
function is convex and Fréchet
differentiable on . The set is convex, and is convex on .
Assumption 2 (Minimizer and initialization). There
exists such that and
Assumption 3 (Gap-dependent upper model). For every
and satisfying ,
Assumption 4 (Exact proximal access). There is a map
such that, for every and ,
The oracle returns
at . Gradient queries may use any
. A proximal query
returns , with
the minimization property above required for positive . Gradient and proximal calls count
toward a single total oracle-call budget.
After the allotted calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.CompositeGapSmooth.spec OracleTemplate.CompositeGapAccelerated.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.