Stationarity for Nonnegative Smooth Sample Losses
Descriptions may be stale. Consult the linked Lean sources.
Stationarity for Nonnegative Smooth Sample Losses
We seek a stationary point of a possibly nonconvex objective
The parameters satisfy
Our assumptions:
Assumption 1 (Sample loss regularity). For each
Assumption 2 (Population objective and initial
value). There is a probability distribution
On call
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NonnegativeSampleStationarityLowerBound
(Ours) |
Lower bound: |
||
| (2) (Peng et al. 2026, Thm. 3.1) | Lower bound: |
(1) proves |
(1) ties |
| (3) (Arjevani et al. 2022, Thm. 3, Eq. (24)) | Lower bound: |
(1) establishes hardness
under individual smoothness, nonnegativity and bounded initial risk.
(3) gives the same order formally at |
(1) covers gradient-only replies. (3) also allows exact objective values. |
Abbr: