Nonconvex Optimization with Lipschitz Third Derivatives
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Lipschitz Third Derivatives
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Third-derivative regularity). The
function
Assumption 2 (Initial gap and curvature). The given
point
Both oracles accept queries at any point of
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) LazyQuarticHessianTradeoff
(Ours) |
|||
| (2) (Doikov and
Grapiglia 2025), Thm. 3.5, Cor. 3.6 ( |
(1): Dimension-free; for
Example: |
(1) needs |
|
| (3) (Hinder 2018),
first-order variant after (8); globally |
(1): Scope extends beyond
global |
(1) needs Hessians;
larger cost when |
|
| (4) (Carmon et al.
2017), Thm. 2; globally |
Valid for |
(1): Scope extends beyond
global |
(1) needs Hessians and
|
| (5) LogFreeSecondOrderThirdSmooth
(Ours) |
|||
| (6) (He and Zhang
2026), Thm. 4.7; globally |
(5): Removes
multiplicative logarithm when |
(5) loses second-order
stationarity; adds |
Abbr: