Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization
with Symmetric Remainders
We consider minimizing a differentiable convex function , where , with an -Lipschitz gradient, . A given point lies within distance of a global minimizer . The oracle returns at , using independent samples from a fixed probability
distribution. Each coordinate error has a distribution decomposable into
a symmetric measure and a centered remainder with bounded second moment,
together with a uniform tail-quantile bound; the symmetric component may
be heavy-tailed. For , the goal is a
measurable output with
integrable objective gap satisfying ,
averaging over oracle and algorithm randomness.
The optimization problem is where
denotes the Euclidean
norm. Fix a measurable sample space and noise parameters and . The algorithm receives , , , , , , , and .
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is differentiable
everywhere, and for every and ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Sampling and oracle). There is a
probability measure on and a jointly measurable map .
At call , a query receives . Under a joint probability law
on , the coordinate
samples are measurable,
mutually independent, and each has distribution . Algorithm randomness is independent
of this sample sequence.
Assumption 4 (Symmetric remainder and quantile
bound). For every
and , let be the distribution of the
scalar error for .
There exist finite nonnegative Borel measures and on such that where . The functions and are
integrable with respect to ,
and
After the allotted oracle calls, the output must be
measurable, its objective gap must be integrable, and it must satisfy
where is the joint law of the
algorithm randomness and the oracle sample sequence.