Descriptions may be stale. Consult the linked Lean sources.
Composite
Minimization with Lipschitz Hessian
We consider minimizing
over a convex set in a
finite-dimensional real inner product space . The function is convex and twice
continuously differentiable, with -Lipschitz Hessian, where ; is convex on and has a closed epigraph restricted to
. A given point satisfies for a minimizer
and . Three oracles return exact
gradients, exact Hessians, and exact composite model solutions. For
, the goal is with
almost surely under , the joint
law of algorithm and oracle randomness.
Write . The
optimization problem is The norm
is induced by the inner product on , and denotes the
induced operator norm. The algorithm receives , , , , , and an integer .
Our assumptions:
Assumption 1 (Convex composite objective). The
function is convex on , the set is convex, and is convex on . In particular, for , The restricted epigraph is closed in .
Assumption 2 (Lipschitz Hessian). The function is twice continuously Fréchet
differentiable on . Its Hessian,
viewed as a linear operator from
to , satisfies
Assumption 3 (Minimizer and initial distance). The
given starting point and a
minimizer belong to , with
Gradient and Hessian queries may be made at any . The gradient oracle returns at , and the Hessian oracle returns at .
The third oracle solves composite models. A model query consists of a
center , a vector , a linear operator , a cubic coefficient , and a scale . The operator must satisfy In addition, either , or there exists such that For every such query, the model oracle returns a
point satisfying the exact
variational inequality Equivalently, minimizes over the model The model guarantee holds
for every valid query and every oracle reply, including queries chosen
using previous replies. Gradient, Hessian, and model-solution calls are
counted separately.
After the allotted calls, the output must satisfy Under the joint law , the algorithm’s randomness is
independent of the oracle’s randomness.