Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization
with Hölder Noise
We consider minimizing a differentiable, possibly nonconvex function
on a separable
real Hilbert space . Its gradient
is -Lipschitz, with , and a given point satisfies , with
. Each oracle call
returns unbiased gradients at two queried points using one shared
sample, with independent samples across calls. The centered noise has
variance at most and
mean-square Hölder increments bounded by , where and . The goal is a measurable
output satisfying
, where and expectation includes
sampling and algorithm randomness.
The optimization problem is where
is the norm induced by the inner product on . The algorithm receives , the measurable sample space , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere, and 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 (Hölder noise increments). Define the
centered noise by . For
every , the squared
increment is
integrable under and
satisfies
At call , a query receives
The sample sequence consists of measurable,
mutually independent random variables with common law . Algorithm randomness is independent of
the entire sample sequence. Queries may depend on earlier replies, and
each paired reply counts as one oracle call.
After the allotted calls, the output must be measurable, its gradient
norm must be integrable, and where is the joint law of the sample sequence
and the algorithm’s randomness.