Descriptions may be stale. Consult the linked Lean sources.
Composite Generalized
Smooth Minimization
We consider minimizing
over a convex set in a real
Hilbert space , where . The function is convex and continuously
differentiable, is convex on
, and is -smooth with and . A given point has bounded distance and
objective gap to a minimizer , whose gradient norm is bounded.
The oracle returns at
and exact constrained proximal
minimizers. For ,
the goal is with
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The parameters satisfy The
algorithm receives only , and ; and may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Convexity). The set is convex. For every ,
Assumption 2 (Generalized smoothness). The function
is Fréchet differentiable
everywhere on , and is continuous. For every
and , the implication holds.
Assumption 3 (Exact proximal access). There is a map
such that, for every and
,
Assumption 4 (Initialization and minimizer bounds).
The given starting point satisfies . There exists such that
The oracle returns
at . It also accepts a proximal
query and returns ;
the minimization property is required for . Gradient queries may be made at
any . Gradient and proximal
queries each count as one call toward a shared oracle-call budget.
After the allotted calls, the output must satisfy