Smooth Convex Proximal Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth
Convex Proximal Minimization
We consider minimizing over
a convex set in a real Hilbert
space , where . The function is differentiable, convex, and smooth
with a hidden constant ,
while is convex on . For a given proximal parameter , the oracle returns exact
proximal minimizers of over and of over . A given point satisfies for some minimizer and radius . For
, the goal is a
feasible output 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 parameters satisfy The algorithm receives only , , , and ; the remaining parameters , , and may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
all , The set is
convex, and is convex on : for all and ,
Assumption 2 (Exact proximal access). For every
, the oracle returns the
respective minimizers Both minimizers exist for every query point.
Either type of query may be made anywhere in , and both types count toward a single
total oracle-call budget.
Assumption 3 (Minimizer and initial distance). There
exists such that
After the allotted oracle calls, the output must satisfy
Results
Lean setup