Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex Composite
Finite Sums
We minimize on a real Hilbert space , where , the functions are convex with -Lipschitz gradients, and is -strongly convex, with . A given point satisfies for a global
minimizer and . The oracle returns component
gradients and exact proximal minimizers of . For , the goal is a
measurable output with
integrable objective gap and ,
where is the law of the
algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with a measurable
structure. The algorithm receives , , , , , , and ; the component functions and
regularizer are accessed through the oracle.
Our assumptions:
Assumption 1 (Convex smooth components). Each is Fréchet differentiable on . For every , , and ,
Assumption 2 (Strongly convex regularizer and
proximal access). For every and , There is a map such
that, for every and ,
Assumption 3 (Initial objective gap). There exists
such that
A component-gradient query specifies and ; the oracle returns at . A proximal query specifies and ; the oracle returns . Its minimization property is
required only for . Each
query of either kind counts as one call toward a shared oracle-call
budget.
After the allotted calls, the output must be measurable, its objective
gap must be integrable under , and
it must satisfy