Descriptions may be stale. Consult the linked Lean sources.
Convex
Interpolation with Distance-Growing Subgradients
We minimize an expected loss
on Euclidean space of
dimension . The smooth
convex sample losses share a minimizer and have the same gradient at the
given starting point . The
oracle returns a sample gradient using a fresh independent draw, or the
query point itself for a projection query. The gradient’s second moment
is bounded by an affine function of squared distance from . For tolerance and failure probability
, the goal is a
measurable output
satisfying with
probability at least .
The optimization problem is The
algorithm receives , where
and control the second moment, bounds the initial distance to a
common minimizer, and . At call ,
the oracle uses a sample from a
sequence of independent, identically distributed random variables with
law on a measurable space . The sequence is independent
of the algorithm’s randomness.
Our assumptions:
Assumption 1 (Interpolating sample losses). For each
and , the loss is
convex and . There exist
with
such that,
for every and , For every
and , is integrable and the
measurable convex objective satisfies In
particular, minimizes .
Assumption 2 (Distance-dependent second moment). The
subgradient reply at on call
is , where
is jointly measurable and for every
. For each and , the vector is Bochner integrable and is integrable. For all ,
Both query types accept any and count toward the
same call budget. After the allotted calls, the output must be a measurable -valued random variable
satisfying where is the
joint law of the algorithm’s randomness and the oracle samples.