Descriptions may be stale. Consult the linked Lean sources.
Nonconvex
Optimization with Expected Smoothness
We consider minimizing a differentiable, possibly nonconvex function
on a separable
real Hilbert space . Its gradient
is Lipschitz, and a given starting point has bounded objective gap above
a global lower bound. The oracle returns two unbiased stochastic
gradients evaluated at queried points using a shared sample, with
independent samples across calls. Their mean-square difference is
bounded by squared query distance, and their variance grows at most
linearly with the objective gap. For , the goal is a
measurable output
satisfying , where is the joint law of sampling and
independent algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , which carries its Borel
sigma-algebra. Fix a measurable sample space , a starting point , and parameters The algorithm receives
, , , , , , , and ; the objective, sampling
distribution, and lower bound are accessible only through the stated
oracle information.
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Lower bound and initial gap). There
exists such that
Assumption 3 (Unbiasedness and expected smoothness).
There exist a probability measure on and a jointly measurable map . For every , the map is Bochner integrable and
For every ,
both and
are
integrable under , with
At call , a query returns The
measurable random variables are mutually independent
with common law , and are
independent of the algorithm’s randomness. Both replies within a call
use the same sample. Each such paired query counts as one oracle
call.
After the allotted calls, the output must be measurable, its gradient
norm must be integrable under ,
and it must satisfy