Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization
with Symmetric 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 , where
. The oracle returns
, with symmetric noise
having tail radius and
relative-energy regularity parameter . Consecutive pairs of calls
share a sample , independently
across pairs. For ,
the goal is a measurable output satisfying , where expectation includes
sampling and independent algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , equipped with its Borel
sigma-algebra. Let be a
measurable sample space. The algorithm receives , , , , , , , and ; it accesses through the oracle described below.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere, and, for every ,
Assumption 2 (Symmetry and tail radius). There exist
a probability measure on and a jointly measurable map . Define the noise by
For every ,
under , Here equality in distribution is equality of the
induced probability measures on .
Assumption 3 (Relative-energy regularity). For every
, the noise evaluated with
the same sample satisfies The ratio is defined to be zero when its
denominator is zero.
Oracle queries may be made at any point of . Let be measurable, mutually
independent sample variables, each with law , and independent of the algorithm’s
randomness. Index calls starting at zero. At query , call returns Thus calls and use the same sample, including when
the second query depends on the first reply.
After the allotted oracle calls, the output must be measurable and satisfy
where is the joint law of the samples and the
algorithm’s independent randomness.