Descriptions may be stale. Consult the linked Lean sources.
Stochastic
Generalized Smooth Composite Minimization
We consider minimizing
over a convex set in a
finite-dimensional real normed space . The function is convex and -smooth, with and , and is convex on . A given starting point has bounded
objective gap and Bregman divergence to a minimizer . The oracle returns unbiased
stochastic derivatives with independent samples and bounded th error moments, , or exact Bregman
proximal points. For and , the goal is a measurable
output satisfying and with
probability at least .
The optimization problem is Write for the continuous dual of , equipped with its induced operator
norm . Let
be the measurable sample
space. The algorithm receives ,
, the starting point , and the parameters The instance supplies the objective and proximal
geometry through the oracle described below.
Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function is convex and
Fréchet differentiable on , with
continuous derivative . For every
and , The set is convex and Borel measurable. The function is measurable on and convex on .
Assumption 2 (Bregman geometry and exact proximal
access). There is an open convex set and a function that is Fréchet
differentiable on . For and , define
The divergence satisfies An exact proximal map is
supplied. For every , , and , The map on given by
is measurable.
Assumption 3 (Initial bounds and a minimizer). The
given point satisfies . There exists such that
Assumption 4 (Stochastic derivative oracle). There
is a probability measure on
and a jointly measurable map
. For every
, the map is Bochner integrable, the
random variable
is integrable for , and
The sample sequence has a joint probability
law on under which its
coordinates are measurable, mutually independent, and each distributed
according to . This sequence is
independent of the algorithm’s randomness. At call , a derivative query at returns ; a proximal query
returns .
Both types of query count toward the same total oracle-call budget.
The output must be
measurable and satisfy where is the
joint law of the algorithm’s randomness and the sample sequence.