Descriptions may be stale. Consult the linked Lean sources.
Stochastic Convex
Minimization with Hessians
We consider minimizing a convex function over a
nonempty compact convex set ,
where is a nonnegative integer.
The gradient is differentiable everywhere, and the Hessian is Lipschitz
on . At each query, the oracle
returns either an unbiased stochastic gradient or a possibly biased,
symmetric positive semidefinite Hessian estimate, using independent,
identically distributed samples. Both estimates have bounded mean-square
error on . For , the goal is a
measurable output lying in
for every realization and
satisfying ,
where minimizes on and expectation includes oracle and
algorithm randomness.
The optimization problem is We use the Euclidean inner product and norm on ; denotes the
induced operator norm. The parameters satisfy The algorithm receives
only , , a given point , , , and ; and may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Feasible set and minimizer). The set
is nonempty,
compact, and convex, and There is a fixed such that for every .
Assumption 2 (Convexity and Hessian regularity). The
function is differentiable on
, its gradient is
differentiable on , and
Its Hessian satisfies
Assumption 3 (Stochastic gradient and Hessian
estimates). Let be a
probability measure on a measurable sample space . The maps are jointly measurable, where is
the space of linear operators equipped with its operator norm and Borel
sigma-algebra. For every ,
is Bochner integrable
under , and both squared error
norms below are integrable. They satisfy For every , , and
,
At call , the algorithm
chooses a point
and requests either or
. The samples are measurable, mutually
independent, and each has law ;
the algorithm’s randomness is independent of the entire sample sequence.
Each request returns only the selected estimate and counts as one call
toward a common budget. Queries may be made throughout , while the stated oracle
error and positivity conditions apply on .
After the allotted calls, the output must be measurable and belong to
for every realization. The
objective gap must be integrable and satisfy
where is the joint law of the
algorithm’s randomness and the oracle sample sequence.