Descriptions may be stale. Consult the linked Lean sources.
Stochastic Composite
Convex Minimization
We consider minimizing
over a measurable convex set in a
separable real Hilbert space . The
function is convex
and continuously differentiable, and is -smooth with and ; is measurable and
convex on . A given feasible point
has bounded distance and
objective gap to a minimizer . The oracle returns unbiased
stochastic gradients with independent samples and bounded noise moments
of order , or exact
proximal points. For and , the goal is a measurable
output satisfying and with
probability at least .
Write . The
optimization problem is The norm
is induced by the inner product on , which carries its Borel sigma-algebra.
Let be the measurable sample
space. The algorithm receives ,
, , , , , , , , , and ; the parameter may enter only the oracle-call budget.
Their ranges are Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function is convex and
Fréchet differentiable on , with
continuous gradient. For every and ,
The set
is convex and Borel measurable, and is measurable on and convex on .
Assumption 2 (Initial bounds). The given point belongs to . There exists such that
Assumption 3 (Exact proximal access). There is a map
such that, for every and
, The map on given by is measurable. A proximal query returns , with the stated minimization
property for positive .
Assumption 4 (Stochastic gradients and sampling).
There is a probability measure
on and a jointly measurable
map . For every
, is Bochner integrable and
is integrable under , with The samples are measurable, mutually
independent, and each has law
under their joint probability law. They are independent of the
algorithm’s randomness. At oracle call , a gradient query at any returns ; a proximal query returns the
exact point specified above.
Gradient and proximal queries share a single total call budget, with
each query counting as one call. After the allotted calls, the output
must be measurable and
satisfy where is the
joint law of the algorithm’s randomness and the oracle samples.