Stochastic Stationarity with Coordinatewise Noise
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Stationarity with Coordinatewise Noise
We seek a stationary point of a differentiable, possibly nonconvex
function
Write
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Sampling and coordinatewise noise). At
call
After the allotted oracle calls, the output
Results
The differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MinibatchSignSgdUpperBound (Ours) (review) | |||
| (2) (Tao et al. 2026, Thm. 1), fixed coordinate noise bounds | (1): Formalizes the
matching rate for |
(1) requires IID draws
and gradient Lipschitzness. (2) allows conditionally
unbiased independent batch samples and requires only |
|
| (3) (Bernstein et al. 2018, Thm. 1), batch size equals iteration count | (1): On the separably
smooth overlap with |
||
| (4) Derived bound, retuned minibatch SignSGD (Bernstein et al. 2018) | (1): Matches the retuned
rate for |
Abbr: