Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization
with Hölder Noise
We consider a differentiable, possibly nonconvex function with -Lipschitz gradient, where and . A given point satisfies , where . Each oracle call at returns using a fresh
independent binary sample . The
estimator is unbiased, with
variance at most and
centered increments of mean square at most , where , , and is the Euclidean norm. For
, the goal is a
measurable output
satisfying , where is the joint law of sampling and
independent algorithm randomness.
The underlying optimization problem is The
algorithm receives , and
. We restrict
these parameters further to
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere. For every ,
Assumption 2 (Unbiased gradients and Hölder noise).
There exist a probability distribution on and a jointly measurable map
.
Define the centered error by For every
, Here is Bochner integrable, and
both squared norms in these expectations are integrable under .
The sample sequence consists of measurable,
mutually independent random variables with common law , independent of the algorithm’s
randomness. On call , the
algorithm may query any pair ,
based on its randomness and previous replies. The oracle returns
Thus the two replies share a sample, and each such pair 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