Descriptions may be stale. Consult the linked Lean sources.
Generalized
Smoothness with Hessian-Vector Oracles
We consider minimizing a possibly nonconvex function , where is an integer. The function is -smooth with and has a continuously
differentiable gradient. A given point has objective gap at
most above a global
lower bound. The oracle returns either an unbiased stochastic gradient
or an unbiased stochastic Hessian-vector product, using independent
samples and allowing heavy-tailed, gradient-dependent errors. For , the goal is a
measurable output with integrable
gradient norm satisfying , averaging over sampling and
independent algorithm randomness.
The optimization problem is We use the
Euclidean norm and its
induced operator norm . Let be a measurable sample space. The
noise parameters satisfy The algorithm receives
, , , , , , , , , , , , and .
Our assumptions:
Assumption 1 (Generalized smoothness). The function
is differentiable everywhere, its
gradient is continuously differentiable, and Here is a linear operator on
.
Assumption 2 (Lower bound and initial gap). There
exists such that
Assumption 3 (Stochastic gradient and Hessian-vector
access). There exist a probability measure on and jointly measurable maps For every , the random vectors
and , with , are Bochner integrable and
satisfy Their respective error norms to powers and are integrable, with At call , a
gradient query at returns , while a Hessian-vector query
at returns . The measurable samples
are mutually
independent with common law ,
and are independent of the algorithm’s randomness.
Queries may use any . Each call requests
one of the two replies, and both query types count toward a single
oracle-call budget. After the allotted calls, the output must be measurable and satisfy
with integrable under
, the joint law of the samples and
the algorithm’s randomness.