Variance-Only Second-Order Stationarity
Descriptions may be stale. Consult the linked Lean sources.
Variance-Only Second-Order Stationarity
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness). The function
Assumption 2 (Initial objective gap). The given
starting point satisfies
Assumption 3 (Stochastic gradient oracle). There are
a probability measure
For every fixed
Queries may be made at any point of
Results
On a real inner-product space of dimension
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GatedPerturbedEscapeSosp
(Ours) |
|||
| (2) PSGD (Jin et al. 2019), Thm. 16 and Remark 14; norm-sub-Gaussian noise, without sample-gradient smoothness | (1): on the
norm-sub-Gaussian overlap, |
(1): certification floor
|
|
| (3) SGD (Vlaski and Sayed 2019), Thms. 1–3; relative fourth-moment control, covariance regularity, saddle-noise lower bound | Step-size-dependent guarantee; no explicit
|
(1): finite variance suffices; no fourth-moment control, covariance regularity, or saddle-noise lower bound. | (1): injects perturbations; (3) needs none. |
| (4) (Arjevani et al. 2020), Thm. 4; stochastic gradients and HVPs with almost-sure Hessian-noise bound | (1): gradients only; no almost-sure Hessian-noise bound. |
Abbr: