Log Free Second Order Third Smooth — Nonconvex Optimization with Lipschitz Third Derivatives
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Lipschitz Third Derivatives · Lean proof
Nonconvex
Optimization with Lipschitz Third Derivatives
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space . The
function is three times continuously differentiable with -Lipschitz third derivative, where
. A given point satisfies and
, where and
; derivative norms are
induced operator norms. Two exact oracles return and , respectively. 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 . The Hessian is a linear operator from
to , and is the third derivative
viewed as a trilinear form on .
The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Third-derivative regularity). The
function belongs to , and
Assumption 2 (Initial gap and curvature). The given
point satisfies
Both oracles accept queries at any point of , and their calls are counted
separately. After the allotted calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.ThirdDerivativeSmoothNonconvex.spec
LongTails.Theorems.LogFreeSecondOrderThirdSmooth.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.