Nonconvex Stationarity with Markov Gradients
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Stationarity with Markov Gradients
We seek an approximately stationary point of a possibly nonconvex
function
Write
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Stationarity and average mixing). The
oracle uses a single Markov chain
Assumption 3 (Stochastic gradients under the
stationary law). On call
After the allotted oracle calls, the output
Results
The possibly nonconvex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AverageMixingMarkovSmoothNonconvex
(Ours) |
|||
| (2) Derived bound: blocking (Yu 1994, Lem. 4.1) and normalized minibatch descent (Cutkosky and Mehta 2020, Lem. 2) | (1) removes |
||
| (3) MarkovNonconvexStationarity (LongTails 2026) | (1) matches
(3) on the overlap and allows stationary-average
mixing, every dimension and all |
||
| (4) Derived bound: minibatch GD (Beznosikov et al. 2023, Lem. 1) | (1) needs only stationary-average mixing and stationary variance. | (1) bounds the mean norm.
(4) also bounds its second moment by |
|
| (5) MaC-SPIDER (Sun and Wei 2025, Thm. 4.4) | (1) allows real-valued chains and needs only objective smoothness. (5) requires a finite ergodic chain, mean-square smoothness and access to gradients at two points per state. | For fixed positive parameters as |
Abbr: