Comparison-Based Nonconvex Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Comparison-Based Nonconvex Stationarity
We consider a twice continuously differentiable, possibly nonconvex
function
We seek approximate stationarity for the optimization problem
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function
Assumption 2 (Initial objective gap). The given
point
Queries may be any pair
We restrict the output to a finite list of previously queried points
and the given starting point. Precisely, in any run with
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ComparisonTrustAccelerated
(Ours) |
|||
| (2) (Wang et al. 2026, Thm. 8, v1) | (1): leading cost saves
|
(1) loses second-order
accuracy |
|
| (3) (Zhang and Li 2024, Thm. 4, v1) | (1): leading cost saves
|
(1) needs Lipschitz Hessian and guarantees a containing list, not a selected stationary point. |
Abbr: