Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed Second-Order
Stationarity
We consider minimizing a twice differentiable, possibly nonconvex
function , where . Its gradient and Hessian are
Lipschitz with constants and
, respectively, and a
given point has objective gap
at most above a global
lower bound. The oracle returns unbiased gradient or Hessian-vector
estimates using independent samples, with bounded error moments of order
, allowing heavy-tailed
noise. For , the
goal is a measurable output
satisfying both and for every
, with probability
at least . Here the norm and
inner product are Euclidean.
The optimization problem is We use
for the
induced operator norm on linear maps from to itself. The algorithm
receives , the measurable sample
space , , , the noise bounds , , , , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function is differentiable
everywhere, its gradient is differentiable everywhere, and, for every
,
Assumption 2 (Lower bound and initial gap). There
exists such that
Assumption 3 (Unbiased oracles with bounded
moments). There is a probability measure on and jointly measurable maps where is
the space of linear operators equipped with its operator norm. For every
, the random
vectors and , with , are Bochner integrable and
satisfy Their error moments are integrable and obey The samples are measurable, mutually
independent, and each has law .
They are independent of the algorithm’s randomness.
At call , the algorithm may
query any for the
vector , or any pair
for the vector
. Each call returns one
of these two vectors and uses the next sample in the same sequence. Both
query types count toward a single total oracle-call budget.
After the allotted calls, the output must be measurable
and satisfy where is the joint law of the algorithm’s
randomness and the oracle samples.