Descriptions may be stale. Consult the linked Lean sources.
Stationarity with Affine
Gradient Variance
We consider minimizing a differentiable, possibly nonconvex function
on a separable
real Hilbert space . Its gradient
is Lipschitz, and its objective gap from a given point is bounded.
Stochastic gradients are unbiased, have variance bounded by an affine
function of the squared gradient norm, and satisfy mean-squared
Lipschitz continuity. At queried points , the oracle returns , where is the stochastic gradient map and
is a fresh sample shared within
the pair. For , the
goal is a measurable output with , where is the joint law of algorithm and
oracle randomness.
The optimization problem is The norm is induced by the inner product
on , which carries its Borel
sigma-algebra. Let be a
measurable sample space. The algorithm receives , , the given point , and the parameters It accesses the objective through the
oracle described below.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere on . For
every ,
Assumption 2 (Unbiasedness and affine variance).
There exist a probability measure on and a jointly measurable map . For each , the map is Bochner integrable under
, and is
integrable under . They satisfy
Assumption 3 (Mean-squared smoothness). For every
, the function is integrable
under , and
The oracle uses a sequence of measurable,
independent samples, each with law , independent of the algorithm’s
randomness. On call , a query
receives Each
such paired reply counts as one oracle call; both evaluations use the
same sample. Queries may be chosen adaptively anywhere in .
After the allotted oracle calls, the output must be measurable, its gradient
norm must be integrable under ,
and it must satisfy