Descriptions may be stale. Consult the linked Lean sources.
Nonconvex
Optimization with Curvature-Aligned Noise
We consider minimizing a differentiable, possibly nonconvex function
on a
finite-dimensional real inner product space . The objective admits global quadratic
upper models with bounded curvature along its gradient and a bounded
initial gap to a lower bound. The oracle returns an unbiased stochastic
gradient at each query, using independent, identically distributed
samples. Its noise has bounded variance and bounded expected curvature
relative to its second moment. For , the goal is a
measurable output with
, where expectation includes oracle
and independent algorithm randomness.
The optimization problem is Write for the inner
product and for its
induced norm. Fix a starting point and parameters The algorithm receives
, the measurable sample space
, , and all five parameters; the
objective and oracle distribution are accessed through oracle
replies.
Our assumptions:
Assumption 1 (Quadratic upper models). The function
is Fréchet differentiable
everywhere. There exists a family of continuous linear maps such that, for every ,
Assumption 2 (Initial objective gap). There exists
such
that
Assumption 3 (Unbiased curvature-aligned noise).
There exist a probability measure on and a jointly measurable map . Define the noise by
For every fixed , the map is
Bochner integrable under , and
both and are integrable under
. For , they satisfy At call , a query returns , where the measurable sample
variables are
mutually independent and each has law . The algorithm’s randomness is
independent of the entire 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, and it must satisfy where is the joint law of the oracle samples
and the algorithm’s randomness.