Descriptions may be stale. Consult the linked Lean sources.
Radius-Constrained
Composite Convex Minimization
We minimize over a
convex set in a real Hilbert
space , where is differentiable and
convex and is
convex on . The function is -smooth, with and . A given satisfies and for some
minimizer , where and . The oracle returns exact
gradients and constrained proximal minimizers. For , the goal is a feasible
output with
almost surely under , the law of
the algorithm’s randomness.
Writing , the
optimization problem is The norm
is induced by the inner product on . The algorithm receives , , , , , and ; the bound may enter only the oracle-call
budget.
Our assumptions:
Assumption 1 (Convexity). The set is convex. For every ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere on , and is continuous. For every
and ,
Assumption 3 (Exact proximal minimization). There is
a map such that, for every and ,
Assumption 4 (Initial distance and minimizer
gradient). The given starting point satisfies . There exists such that
The oracle returns
at . It also returns on a proximal query . Gradient queries may use any
, and proximal queries may
use any and ; the proximal minimization
requirement applies only for . Both query types count toward a
single total oracle-call budget.
After the allotted calls, the output must satisfy Here
is the law of the algorithm’s randomness, and is a fixed minimizer independent
of that randomness.