Hessian-Lipschitz Second-Order Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Hessian-Lipschitz Second-Order Stationarity
We consider minimizing a possibly nonconvex, twice continuously
differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Hessian regularity). The function
Assumption 2 (Initial objective gap). The given
point
Queries to either oracle may be made at any point of
After the allotted calls, the output must satisfy
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MonotoneHessianSecondOrder
(Ours) |
|||
| (2) Cubic regularization (Nesterov and Polyak 2006), Thm. 1 | (1): cheaper for |
(1): probabilistic
instead of deterministic; |
|
| (3) Lazy cubic Newton (Doikov et al. 2023), Cor. 3.7 | (1): one point satisfies
the gradient and curvature targets; removes the |
(1): probabilistic instead of deterministic; additional dimension- and confidence-dependent logarithms. | |
| (4) Derived bound (Doikov et al. 2023), Thm. 3.1, (15) | (1): same-point
certificate; for |
(1): probabilistic instead of deterministic. | |
| (5) (Adil et al. 2025), Cor. 2 | (1): adds the
second-order certificate with matching polynomial powers; logarithmic
overhead becomes |
(1): probabilistic instead of deterministic. | |
| (6) NALEN (Chen et al. 2026), Thm. 4.1 | (1): extends the |
(1): extra |
Abbr: