Descriptions may be stale. Consult the linked Lean sources.
Mean-Squared Hölder
Nonconvex Optimization
We consider finding an approximate stationary point of a
differentiable, possibly nonconvex function on a separable real
Hilbert space . Its gradient is
-Lipschitz, where , and a given point satisfies , where
. At a pair , the oracle returns unbiased
gradient estimates using one shared sample
, with independent samples
across calls. Their variance is bounded by , and their mean-squared
difference by ,
where and . For , the goal is a
measurable output with
, averaging over oracle and
independent algorithm randomness.
The underlying optimization problem is The norm is induced by the inner product
on . The algorithm receives , the measurable sample space , , and all parameters .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere on . For
every ,
Assumption 2 (Unbiased stochastic gradients). There
exist a probability measure on
and a jointly measurable map
. For every
, the random vector is Bochner integrable and is integrable
under , with
Assumption 3 (Mean-squared Hölder continuity). For
every , the random variable
is
integrable under , and
At call , a query receives the pair
The measurable samples are mutually independent
with common law , and are
independent of the algorithm’s randomness. Both evaluations within a
pair use the same sample; one returned pair counts as one oracle call.
Queries may depend on preceding replies.
After the allotted calls, the output must be measurable, its gradient
norm must be integrable, and it must satisfy where is the joint law of the oracle samples
and the algorithm’s randomness.