Descriptions may be stale. Consult the linked Lean sources.
Stochastic Convex
Third-Order Regularity
We consider minimizing a convex, three-times continuously
differentiable function , where is an integer, with -Lipschitz third derivative, . A given point satisfies and for a global
minimizer and . Each oracle call returns
gradient and Hessian estimates using a shared sample, independently
across calls. The gradient estimate is unbiased; their mean squared
errors are bounded by
and , respectively, where
. For , the goal is a
measurable output within
distance of for every realization, with with
probability at least .
The optimization problem is We use the
Euclidean norm and its
induced operator and multilinear norms . The algorithm
receives .
Our assumptions:
Assumption 1 (Convexity and third-derivative
regularity). The function belongs
to .
For every and
, Here is the trilinear third derivative; equivalently, its norm
is that of the second derivative of the gradient, viewed as a bilinear
map into .
Assumption 2 (Minimizer and initial bounds). There
is a fixed
such that
Assumption 3 (Paired stochastic oracle). Let be a measurable sample space with
probability measure . There are
jointly measurable maps where
denotes the space of linear operators. For each fixed , the random vector is Bochner integrable for , and both squared errors below
are integrable. They satisfy The measurable samples are mutually independent
with common law , and are
independent of the algorithm’s randomness. At call , a query returns the pair Both
components use the same sample, and the pair counts as one oracle
call.
Queries may be made anywhere in . After the allotted oracle
calls, the output must be
measurable and satisfy and the accuracy
requirement is
where is the joint law of the
algorithm’s randomness and the oracle samples.