Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional
Nonconvex Optimization with ABC Noise
We consider minimizing a differentiable, possibly nonconvex function
, where
is a positive integer, with
finite infimum and an -Lipschitz gradient, where . The oracle returns at , using independent real samples with a common probability law. Its
replies are unbiased and satisfy , where . For a tolerance , the goal is a
measurable output satisfying , with expectation over oracle
samples and independent algorithm randomness.
The optimization problem is
Throughout, denotes the
Euclidean norm. A starting point and an initial-gap
bound are
given. The algorithm receives , and .
Our assumptions:
Assumption 1 (Parameter and dimension regime). The
parameters satisfy In particular, these conditions imply and .
Assumption 2 (Smoothness and initial gap). The
function is Fréchet
differentiable everywhere, and Its infimum is finite, and
Assumption 3 (IID stochastic gradients with ABC
noise). There exist a probability measure on and a jointly measurable map
.
At call , a query receives , where is a sequence of
measurable, mutually independent random variables with common law . This sequence is independent of the
algorithm’s randomness. For every fixed , the vector is Bochner integrable and is integrable
for , with
Queries may be made at any point of . Let denote the joint law of the oracle
samples and the independent algorithm randomness. After the allotted
oracle calls, the output
must be measurable, its gradient norm must be -integrable, and it must satisfy