Descriptions may be stale. Consult the linked Lean sources.
Euclidean
Strong-Growth Stochastic Minimization
We consider minimizing a differentiable convex function , where is a positive integer. A given point
lies within
distance of a global
minimizer . The stochastic
gradient is unbiased, is Lipschitz in mean square with constant , and has variance bounded by
at each
, where . Each oracle call returns
gradients at two queried points using a shared sample, with independent,
identically distributed samples across calls. For , the goal is a
measurable output with integrable
objective gap satisfying ,
where is the law of the
algorithm’s and oracle’s randomness.
The optimization problem is where
denotes the Euclidean
norm. The parameters satisfy Let
be a measurable sample space containing distinct points whose singletons are measurable. The
algorithm receives , with its measurable structure,
, , , , and ; the objective and the oracle
distribution are accessed through oracle replies.
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function is Fréchet
differentiable everywhere. For every and , There
exists such
that
Assumption 2 (Unbiasedness and strong growth). There
exist a probability measure on
and a jointly measurable map
.
For every , the map
is Bochner integrable,
the squared error is integrable, and
Assumption 3 (Mean-square smoothness and paired
sampling). For every , the squared
difference is integrable
and satisfies The oracle uses a sequence of measurable,
independent random variables, each with law , independent of the algorithm’s
randomness. At call , a query
returns Both components use the same sample, and
the pair counts as one oracle call.
Queries may be chosen adaptively anywhere in . After the
allotted paired oracle calls, the output must be measurable, its objective
gap must be integrable under , and
it must satisfy