Descriptions may be stale. Consult the linked Lean sources.
Stochastic
Composite Stationarity
We consider minimizing
over a convex set in a
finite-dimensional real inner product space . The possibly nonconvex function has an -Lipschitz gradient and a -Lipschitz Hessian, with and , while is convex on . A given has objective gap at most . The oracle returns unbiased
stochastic gradients with variance at most , , from independent identically
distributed samples, or exact proximal minimizers of over , for and . For , the goal is a feasible
output with .
The optimization problem is The norm is induced by the inner
product on ; operator norms below
are the induced operator norms. The algorithm receives , the measurable sample space , , , , , , and , and accesses the objective through
the oracle described below.
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function is Fréchet
differentiable on , its gradient
is Fréchet differentiable on ,
and, for every , Here is a linear operator from to .
Assumption 2 (Convex composite term and proximal
access). The set is
convex, and, for every and
,
For every and , the exact proximal reply
satisfies The map on equal to when and to otherwise is measurable.
Assumption 3 (Initial objective gap). The given
starting point and gap bound satisfy
Assumption 4 (Stochastic gradient access). There is
a probability measure on and a jointly measurable map . For each , the random vector is Bochner integrable and is integrable
under , with The oracle samples form a measurable, mutually
independent sequence with common law , under a joint probability law on . This sequence is
independent of the algorithm’s internal randomness. At call , a gradient query at any returns ; a proximal query returns
exactly. Each query of
either type counts as one oracle call in a common budget. Proximal
queries may use any real ,
although the minimization and measurability conditions above concern
positive .
Define the composite gradient mapping by After the allotted oracle calls, the output must be measurable, its residual
norm must be
integrable, and it must satisfy
where is the joint law of the
algorithm’s internal randomness and the independent oracle sample
sequence.