Descriptions may be stale. Consult the linked Lean sources.
Generalized Smooth Convex
Mirror Geometry
We minimize a differentiable convex function on a finite-dimensional
real normed space . The function
is -smooth, with and . A differentiable mirror
function
induces a Bregman divergence
dominating half the squared norm. A given point satisfies and for a
minimizer , where . The oracle returns exact
derivatives and Bregman proximal minimizers. For , the goal is
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is Write for the
continuous dual of . Derivatives
and belong to , and their norms are the induced
operator norms . Define
The algorithm receives , , , , , and ; the tolerance may enter only the
oracle-call budget.
Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function is everywhere
Fréchet differentiable, its derivative is continuous, and Its -smoothness means that, for
every and ,
Assumption 2 (Mirror geometry and proximal access).
The function is everywhere
Fréchet differentiable and satisfies For every and , a selected
proximal minimizer exists:
Assumption 3 (Initial bounds). There exists such that
The oracle returns
at . It also returns on a query
. Both types of
queries are exact, may be made anywhere in their stated domains, and
count toward a single total oracle-call budget.
After the allotted calls, the output must satisfy where the global minimizer is fixed independently of the
algorithm’s randomness.