Descriptions may be stale. Consult the linked Lean sources.
Variance-Only Second-Order
Stationarity
We consider minimizing a possibly nonconvex function on a
positive-dimensional finite-dimensional real inner product space . The function is twice continuously
differentiable, with -Lipschitz
gradient and -Lipschitz
Hessian, where . A given
point satisfies , where
. The oracle returns
unbiased stochastic gradients from independent, identically distributed
samples, with variance at most , where . For and satisfying , the goal is a
measurable output
satisfying and for every
, with probability at least
.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The Hessian is the derivative of the gradient. The algorithm
receives , the measurable sample
space , , , , , , , and .
Our assumptions:
Assumption 1 (Smoothness). The function belongs to , and, for every ,
Assumption 2 (Initial objective gap). The given
starting point satisfies
Assumption 3 (Stochastic gradient oracle). There are
a probability measure on and a jointly measurable map . The samples are measurable, mutually
independent random variables with common law under a joint probability law on . At its th query , the oracle returns .
For every fixed , the map
is Bochner integrable
and is
integrable under , with Any algorithm randomness is independent of the
sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
algorithm must return a measurable output such that where is the joint law of the algorithm
randomness and the sample sequence with law .