Descriptions may be stale. Consult the linked Lean sources.
Parameter-Free
Composite Convex Minimization
We consider minimizing
over a convex set in a real
Hilbert space , where is convex and
continuously differentiable and is convex on . The function is -smooth with hidden constants
and . A given point has bounded distance and
objective gap to a minimizer , whose smooth gradient is
bounded. The oracle returns exact gradients and constrained proximal
minimizers. For ,
the goal is with
almost surely under , the law of
the algorithm’s randomness.
Write . The
optimization problem is The norm
is induced by the inner product on . The algorithm receives only , , and a scalar ; the parameters , , , , , and may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Convexity). The set is convex, is convex on , and is convex on . Thus, for ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere on , and is continuous. For every
and , the segment bound implies
Assumption 3 (Exact proximal minimization). There is
a map such that, for every and ,
Assumption 4 (Initial point and minimizer). The
given point satisfies .
There exists such that
The oracle returns
at . A proximal query returns . Gradient queries may
use any , and proximal
queries may use any
and ; the proximal
minimization condition applies when . Both query types count toward a
single total oracle-call budget.
After the allotted calls, the output must satisfy The minimizer is fixed independently of the
algorithm’s randomness.