Descriptions may be stale. Consult the linked Lean sources.
Composite
Minimization with Gap-Controlled Hessians
We consider minimizing
over a convex set in a real
Hilbert space , where are convex on . At each feasible point, has a positive semidefinite Hessian
satisfying , where and minimizes . A given satisfies and , with . The oracle returns exact
feasible gradients or exact proximal minimizers of . For , the goal is with
almost surely.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The algorithm receives , , , , , , and ; the functions and feasible set are
accessed through the oracle.
Our assumptions:
Assumption 1 (Convexity). The set is convex. For every and ,
Assumption 2 (Minimizer and initialization). There
exists such that and
Assumption 3 (Feasible Hessian bound). At every
, the function is Fréchet differentiable, and its
gradient is Fréchet differentiable at as a map on . The Hessian is a bounded
self-adjoint linear operator satisfying These derivatives are ambient derivatives,
including at boundary points of .
Assumption 4 (Exact proximal access). There is a map
such that, for every and , In particular, these minimizers exist and the
returned point is feasible.
The oracle supports two query types. For a gradient query at , the oracle returns at . For a proximal query , it
returns , with
the minimization property above applying when . Both query types count toward one
common oracle-call budget.
After the allotted calls, the output must satisfy where is the joint law of the algorithm’s and
oracle’s randomness, which are independent.