Descriptions may be stale. Consult the linked Lean sources.
Generalized Smooth
Composite Minimization
We minimize on a real
Hilbert space , where is convex and
continuously differentiable, and is convex and -Lipschitz, with . The function is -smooth, with . A given point satisfies for some global
minimizer of , where . The oracle returns exact
gradients, regularizer values, and proximal points. For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives only , , , , and ; the radius and tolerance may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Convexity and Lipschitz regularizer).
For every and , Moreover, for all ,
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 minimization). There is
a map such that, for every and ,
Assumption 4 (Initial distance). There exists such that
The oracle returns
at . It also returns for a value query at , and for a proximal query .
Each query counts as one call toward a shared oracle-call budget. All
point queries may be made anywhere in .
After the allotted calls, the output must satisfy The minimizer in this requirement is fixed
independently of the algorithm’s randomness.