Descriptions may be stale. Consult the linked Lean sources.
Strong-Growth
Mean-Square Smooth Convex Minimization
We consider minimizing a differentiable convex function on a separable real
Hilbert space . A given point
lies within distance of a global minimizer . The oracle returns at a pair , using a shared sample from a probability law on a measurable space , independently across calls. The
estimator is
unbiased, with variance bounded by , where , and is mean-square Lipschitz
with constant . For
, the goal is a
measurable output with
integrable objective gap satisfying ,
averaging over oracle and algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with its
Borel sigma-algebra. The algorithm receives , , , , , , and ; the objective is accessed through
the oracle.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function is Fréchet
differentiable everywhere on , and
for every and , There
exists such that
Assumption 2 (Unbiasedness and strong growth). The
map is jointly
measurable. For every , is Bochner integrable under
, the squared error is
integrable, and
Assumption 3 (Mean-square smoothness). For every
, the squared difference
is
integrable under , and
More precisely, the oracle samples form a sequence of measurable, mutually
independent random variables, each with law . Algorithm randomness is independent of
this sequence. At call , the
algorithm may query any pair and receives Each
paired reply counts as one oracle call; both components use the same
sample.
After the allotted oracle calls, the output must be measurable, its objective
gap must be
integrable, and
where is the joint law of the
algorithm randomness and the oracle sample sequence.