Smooth Nonconvex Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Smooth Nonconvex Stationarity
We consider a differentiable, possibly nonconvex function
We seek approximate stationarity for the optimization problem
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Lower bound and initial gap). There
exists
Queries may be made at any point of
Results
A differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GdNonconvex (Ours) (review) | |||
| (2) Classical GD, |
(1): Matches known rate;
machine-checked formalization. Already order-optimal in sufficiently
high dimension (Carmon et al. 2020, Thms. 1–2, |
(1) needs |
|
| (3) GD, |
(1): Matches known rate on this finite-dimensional restriction; no established improvement. | (1) has about |
|
| (4) GD, |
(1): Matches known rate on this finite-dimensional restriction; no established improvement. | (1) has about |
Abbr: GD: gradient descent;