Gradient-Only Third-Order Nonconvex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Gradient-Only Third-Order Nonconvex Optimization
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
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
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GradientOnlyThirdOrderAcceleration
(Ours) |
|||
| (2) (Carmon et al. 2017, Theorem 2) | (1): Matches the rate on this range using gradients alone; removes all function-value calls. | (1) has a much larger
leading constant and needs |
|
| (3) Restarted AGD (Li and Lin 2023, Theorem 1) | Derived bound: |
(1): Rate gain |
(1) needs Lipschitz third
derivatives and |
| (4) (Zhou et al. 2026, Theorem
1.3; precise Theorem 5.2, |
(1): Dimension-free |
(1) is slower for fixed
small |
Abbr: