Stationarity for Nonnegative Smooth Sample Losses
Descriptions may be stale. Consult the linked Lean sources.
Stationarity for Nonnegative Smooth Sample Losses
We consider minimizing a possibly nonconvex expected loss
Let
Our assumptions:
Assumption 1 (Sample losses). For every
Assumption 2 (Paired gradient queries). The oracle
samples
After the allotted oracle calls, the output
Results
On a separable real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NonnegativeSampleStationarity (Ours) (review) | |||
| (2) Normalized STORM (auto-math-bot 2026) | (1): Matches the known
rate and tuning. The sample-level formalization derives |
(1) requires nonnegative smooth losses. (2) allows mean-square smooth gradients with variance bounded by an affine function of the objective gap. | |
| (3) SGD (Khaled and Richtárik 2020, Cor. 1) | (1): For |
(1) needs same-sample pairs. (3) queries one point per sample and bounds the minimum expected squared gradient norm across iterates. | |
| (4) SPIDER (Chen et al. 2023, Thm. 4) | (1) covers samples
violating the affine variance bound required by (4). On
the overlap, its |
(1) requires nonnegative
smooth losses even on affine-variance problems. On the overlap its
leading term is worse when |
Abbr: