Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with
ABC Noise
We consider a differentiable, possibly nonconvex function on a separable real
Hilbert space , with -Lipschitz gradient for and finite infimum . A given point satisfies , where . At , the oracle returns an unbiased vector
using fresh independent
samples with common law ; its noise second moment is at most
, where . For , the goal is a
measurable output with
, where is the joint law of oracle and
independent algorithm randomness.
The underlying optimization problem is The norm is induced by the inner product
on . Let be a measurable sample space. The
algorithm receives , , , , , and ; the objective and its oracle
distribution are accessed through oracle replies.
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere,
and
Assumption 2 (Finite infimum and initial gap). There
exists such
that
Assumption 3 (Independent unbiased oracle with ABC
noise). There exist a probability measure on and a jointly measurable map . For every , the vector is Bochner integrable and is integrable
under , with The sample sequence has a joint probability
law on : its coordinate maps
are measurable, mutually independent, and each has law . At the th query , the oracle returns . Algorithm randomness is
independent of this sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must be measurable,
its gradient norm must be integrable under , and it must satisfy