Nonconvex Stationarity with Markovian Gradients
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Stationarity with Markovian Gradients
We seek an approximate stationary point of a possibly nonconvex
function
The underlying optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Stationary Markov sampling). The
oracle uses successive states
Assumption 3 (Stochastic gradient moments). On call
Let
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MarkovNonconvexStationarityLowerBound
(Ours) |
Lower bound (necessary) |
||
| (2) MarkovNonconvexStationarity
(Ours) |
Upper bound (sufficient) |
||
| (3) (Sun and Wei 2025b, Thm. 3.1, smooth case) | (1) covers all randomized
adaptive algorithms. For the lazy-cycle construction, |
(1) requires quartic dimension. (3) concerns finite chains with bounded hitting time and zero-respecting queries. The cycle conversion is specific to those hard instances. | |
| (4) (Sun and Wei 2025a, Thm. 3.1) | (1) covers arbitrary randomized adaptive queries and unqueried outputs. (4) appends a lazy cycle to a countable chain. Its hitting-time bound alone gives no common TV scale. | (1) requires quartic dimension. (4) uses a hitting-time bound on countable chains and zero-respecting algorithms. | |
| (5) (Arjevani et al. 2023, Thm. 3, Eq. (23)) | (1) strengthens the IID
lower bound by a factor |
(1) needs |
Abbr:
Table 1, continued.
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (6) Derived bound (Beznosikov et al. 2023, Lem. 1, Eq. (6)) | (2) allows noise
unbounded across states. (6) requires |
(2) costs a factor |
|
| (7) (Beznosikov et al.
2023, Cor. 2, |
(2) replaces a statewise noise bound by stationary variance and gives a deterministic budget for all transitions. | (2) requires the stated
noise, gap and dimension regime and controls only the expected norm.
(7) guarantees |
|
| (8) Derived bound (Sun and Wei 2025b, Lem. 4.1(1)) | (2) covers general state
spaces. For |
(2) needs a stationary
start. For |
|
| (9) MaC-SPIDER (Sun and Wei 2025b, Thm. 4.4) | (2) permits general state
spaces and needs only smoothness of |
For fixed remaining parameters and small
|
Abbr: