Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization
with Symmetric Noise
We consider minimizing a differentiable, possibly nonconvex function
, where
is a nonnegative integer. Its
gradient is -Lipschitz, with , and a given point satisfies , with . Each oracle call returns
unbiased stochastic gradients at two queried points using one shared
sample, independently across calls. The noise has symmetric coordinate
marginals, a bounded first moment, and Lipschitz dependence on the query
in mean norm. For ,
the goal is a measurable output with , averaging over sampling and
algorithm randomness.
The optimization problem is where
denotes the Euclidean
norm. Let be a measurable
sample space, and let denote the noise
regularity and first-moment bounds, respectively. The algorithm receives
, with its measurable structure,
, , , , , and ; the objective is accessed through
the oracle.
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and
Assumption 2 (Symmetric first-moment noise). There
exist a probability measure on
and a jointly measurable map
.
For every , the map
is Bochner integrable
under . Define the noise by For
all , Each coordinate marginal of the noise is
symmetric about zero: for every and ,
At call , the algorithm
may query any pair ,
and the oracle returns
The sample variables are measurable, mutually
independent, and each has law .
They are independent of the algorithm’s randomness. Both replies in a
pair use the same sample, and one such paired query counts as one oracle
call.
After the allotted calls, the output must be measurable and must be integrable,
with where is the joint law of the samples and the
independent algorithm randomness.