Ball Proximal Gaussian — Convex Ball Proximal Minimization
Descriptions may be stale. Consult the linked Lean sources.
Convex Ball Proximal Minimization · Lean proof
Convex
Ball Proximal Minimization
We minimize a convex function over a convex set in a finite-dimensional real
inner-product space , with closed
constrained epigraph. A given satisfies and for a
minimizer , where and . At , the oracle returns an exact
minimizer over , where . Ball
proximal iteration must return with
almost surely under , the law of
oracle randomness, for .
The optimization problem is The norm is induced by the inner product
on . The algorithm receives , , , , , and ; the set and function are accessed through the oracle.
Our assumptions:
Assumption 1 (Convexity and closed epigraph). The
set is convex, and for
all and , The constrained epigraph
is closed in .
Assumption 2 (Initialization and minimizer). The
given starting point satisfies . There exists such that
Assumption 3 (Exact ball proximal oracle). For every
query , every oracle reply
satisfies These conditions hold for every query history and
every realization of the oracle randomness. The oracle may select among
multiple minimizers using that history and randomness.
Our formulation is algorithm-specific: we analyze ball proximal
iteration with fixed radius .
Starting at the given , each
step queries the oracle at the current iterate and replaces it by the
returned point: Here is the integer oracle-call budget,
each step uses one call, and the output is the last iterate . All queries therefore lie in
.
The required accuracy is The minimizer is fixed independently of the
oracle randomness.
Proved result
OracleTemplate.Convergence LongTails.Setups.ConvexBallProximal.spec OracleTemplate.BallProximalGaussian.budget
Relevant previous results