Stationarity with Exact Hessian Access
Descriptions may be stale. Consult the linked Lean sources.
Stationarity with Exact Hessian Access
We seek approximate stationarity of a possibly nonconvex function
The underlying optimization problem is
The parameter regime is restricted by
Our assumptions:
Assumption 1 (Third-derivative bound). The function
Assumption 2 (Initial objective and gradient
control). At the reference point
Queries may be made at any
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
(1) PointwiseHessianStationarityLowerBound
(Ours) Lower bound |
Necessary: |
||
(2) PointwiseHessianStationarity (Ours) (review) Upper bound |
Sufficient joint calls: |
||
(3) (Carmon et al.
2020), Theorem 2, Lower bound; Lipschitz-Hessian subclass |
Necessary: |
(1): Necessary budget
increases by |
(1): Requires dimension
of order |
(4) Cubic Newton (Fang et al. 2026), Corollary 1 Upper bound; pointwise condition |
Sufficient joint calls, including backtracking: |
(2): Matches known polynomial rate, with a different additive logarithm; formalizes the transfer to a joint oracle. | (2): Needs |
Abbr: