Descriptions may be stale. Consult the linked Lean sources.
Nonconvex
Optimization with Mixed Relative Noise
We consider minimizing a differentiable, possibly nonconvex function
on a separable
real Hilbert space . Its gradient
is -Lipschitz, where , and a given point satisfies for
. The oracle returns
unbiased stochastic gradients, with second moments controlled by
gradient magnitudes and noise increments controlled jointly by gradient
magnitudes and query distance. Consecutive pairs of calls share a
sample; samples across pairs are independent. For , the goal is a
measurable output with
, averaging over sampling and
algorithm randomness.
The optimization problem is The norm is induced by the inner product
on . Let be a measurable sample space, and
let . The algorithm
receives , , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, and
Assumption 2 (Initial objective gap). The given
point satisfies
Assumption 3 (Mixed relative noise). There exist a
probability measure on and a jointly measurable map . Define the centered
error by For every ,
the random variable
is integrable for , and
Moreover, for every , the same sample is used in the
noise-increment bound
Queries may be made at any point of . Let be measurable,
independent random variables with common law , independent of the algorithm’s
randomness. At call , a query
receives Thus calls and use the same sample , including when the second query
depends on the first reply. Each evaluation counts as one oracle
call.
After the allotted oracle calls, the output must be measurable, its gradient
norm must be integrable, and where is the joint law of the sample sequence
and the independent algorithm randomness.