Descriptions may be stale. Consult the linked Lean sources.
Stochastic Convex Local
Hessian Regularity
We consider minimizing a twice continuously differentiable convex
function , where is a nonnegative integer. Its Hessian
is locally Lipschitz with a bound depending on the gradient norm. A
given point has bounded
distance and objective gap to a global minimizer . Two oracles return unbiased
stochastic gradients with bounded variance using independent identically
distributed samples, and deterministic uniformly accurate Hessian
approximations. For and , the goal is a measurable
output satisfying ,
where is the joint law of oracle
and algorithm randomness.
The optimization problem is We use the
Euclidean norm and its
induced operator norm on linear maps
from to itself. The
parameters satisfy The algorithm receives , the measurable sample space , , and all the
parameters .
Our assumptions:
Assumption 1 (Convexity and initialization). The
function belongs to and satisfies, for
every and , There
is a global minimizer such that
Assumption 2 (Local Hessian regularity). For every
with ,
Assumption 3 (Stochastic gradients and approximate
Hessians). There are a probability measure on , a jointly measurable map ,
and a measurable map taking each
point in to a linear
operator on . For every
, the random vector
is Bochner integrable and
is
integrable under , with
The sample sequence consists of measurable,
mutually independent random variables with common law , and is independent of the
algorithm’s randomness. At the th
oracle call, a gradient query at
returns , while a Hessian
query at returns the
deterministic operator .
Queries to either oracle may be made at any point of . Gradient calls and Hessian
calls have separately counted budgets. After the allotted calls, the
output must
be measurable and satisfy