Finite-Sum Nonconvex Optimization
Descriptions may be stale. Consult the linked Lean sources.
Finite-Sum Nonconvex Optimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Mean-square smoothness). Each
component
Assumption 2 (Lower bound and initial gap). There
exists
Queries may use any index
Results
On a real Hilbert space
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RecursiveGradientNonconvex (Ours) (review) | |||
| (2) Minibatch SARAH (Nguyen et al. 2019,
Thm. 2, Cor. 3). |
(1): Matches known rate, formalized in Lean. Scope: Hilbert spaces. With-replacement instead of without-replacement batches; no rate or tuning-knowledge improvement. | ||
| (3) SpiderBoost (Wang et al. 2020, Thm. 1;
App. G, Thm. 9). |
(1): Scope: mean-squared smoothness instead of componentwise smoothness; Hilbert spaces. Matches rate on the common setup. The smoothness relaxation is already covered by (2). | ||
| (4) PAGE (Li et al. 2021, Thm. 1,
Cor. 2; App. A.1, Eq. (23)). |
(1): Deterministic rather than expected call budget, at matched order on the common setup; this budget guarantee already holds for (2). |
Abbr: