Gradient Only Third Order Acceleration — Gradient-Only Third-Order Nonconvex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Gradient-Only Third-Order Nonconvex Optimization · Lean proof
Gradient-Only
Third-Order Nonconvex Optimization
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space . The
function is three times continuously differentiable, with -Lipschitz gradient and -Lipschitz third derivative in the
induced operator norm, where . A given point satisfies , where
. The oracle returns
at . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm, including for multilinear forms. In particular,
is a trilinear form
on . The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Smoothness). The function belongs to , and its gradient
satisfies
Assumption 2 (Third-derivative regularity). The
third derivative satisfies
Assumption 3 (Initial objective gap). The given
starting point satisfies
Queries may be made at any point of . After the allotted gradient calls, the
output must satisfy the first-order stationarity criterion
Proved result
OracleTemplate.Convergence LongTails.Setups.GradientOnlyThirdOrderNonconvex.spec
OracleTemplate.GradientOnlyThirdOrderAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.