High-Dimensional Nonconvex Optimization with Markov Noise
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Nonconvex Optimization with Markov Noise
We seek a stationary point of a differentiable, possibly nonconvex
function
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function
Assumption 2 (Stationarity and average mixing). The
chain
Assumption 3 (Stochastic gradient oracle). At call
After the allotted oracle calls, the algorithm must return a
measurable output
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AverageMixingMarkovSmoothNonconvexLowerBound
(Ours) |
|||
| (2) Uniform mixing (auto-math-bot 2026) | (1) strengthens the bound
inherited from (2) by |
(1) requires |
|
| (3) IID, bounded variance (Arjevani et al. 2023, Thm. 3) | (1) raises the IID lower
bound inherited by the averaged-mixing class by a factor |
(3) also covers
arbitrarily small positive |
|
| (4) IID, bounded error (Jin 2026, Thm. 4.1) | (1) gives a |
(4) establishes hardness
even with almost surely |
|
| (5) Finite chain, hitting-time bound, zero-respecting methods (Sun and Wei 2025, Thm. 3.1) | (1) covers unrestricted
adaptive queries and outputs. At the hard cycles’ mixing scale |
(1) requires higher dimension. The hard-cycle conversion does not compare the hitting-time and averaged-mixing classes in general. |
Abbr: