← All setups

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 f:Rd→R in high dimension d. The gradient is Lipschitz, and the gap from a given starting point to the finite infimum is bounded. Each query returns a gradient estimate driven by the next state of a stationary real-valued Markov chain whose total variation distance to stationarity decays exponentially on average. At each fixed query point, the estimate is unbiased under the stationary law and has bounded variance. For ε>0, the goal is an output x¯ satisfying E∥∇f(x¯)∥≤ε over chain and algorithm randomness.

The optimization problem is infx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The algorithm receives the dimension d∈N, the starting point x0∈Rd, the gradient Lipschitz bound L>0, the initial gap bound Δ, the noise scale σ, the mixing parameter τ≥1, and the tolerance ε>0. We consider the parameter regime 226ε2≤LΔ,216ε≤σ. Writing r=σ/ε, the dimension requirement is d≥240(1+LΔε2)4(1+τr2log⁡r).

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable everywhere, and f⋆=infx∈Rdf(x) is finite. For all x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(x0)−f⋆≤Δ.

Assumption 2 (Stationarity and average mixing). The chain (Zk)k≥0 starts with law π on R and has Markov transition kernel κ. The law π is invariant, so for every Borel set A⊆R, EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, define the total variation distance after t transitions from z by Dt(z)=supA∈B(R)|κt(z,A)−π(A)|. The function Dt is π-integrable and satisfies EZ∼π[Dt(Z)]≤2exp⁡(−t/τ).

Assumption 3 (Stochastic gradient oracle). At call k=0,1,…, a query at any x∈Rd returns g(x,Zk), where g:Rd×R→Rd is jointly measurable. For each fixed x, the map g(x,⋅) is Bochner integrable under π, the squared error ∥g(x,⋅)−∇f(x)∥2 is π-integrable, and EZ∼π[g(x,Z)]=∇f(x),EZ∼π[∥g(x,Z)−∇f(x)∥2]≤σ2.

After the allotted oracle calls, the algorithm must return a measurable output x¯∈Rd with integrable gradient norm satisfying E[∥∇f(x¯)∥]≤ε. The expectation is over the Markov chain and the algorithm’s internal randomness, which are independent.

Results

Let f:Rd→R have L-Lipschitz gradient and f(x0)−inff≤Δ. Each call returns g(x,Zt) at the next state of one stationary real-valued chain with kernel P and law π, where ∫∥Pt(z,⋅)−π∥TVdπ(z)≤2e−t/τ for every t. The jointly measurable oracle satisfies Eπg(x,Z)=∇f(x) and Eπ∥g(x,Z)−∇f(x)∥2≤σ2 for every x. The target is E∥∇f(x^)∥≤ε for a measurable output of any randomized adaptive algorithm. In (1), L,ε>0, τ≥1, A≥226, r≥216 and d≥240(1+A)4(1+τr2log⁡r).

Necessary stochastic-gradient calls for nonconvex stationarity under stationary-averaged Markov mixing.
Result Oracle complexity Novelty Limitations
(1) AverageMixingMarkovSmoothNonconvexLowerBound (Ours) (⋆⋆⋆) (review) Ω(τLΔσ2ε4log⁡r)
(2) Uniform mixing (auto-math-bot 2026) Ω(τAr2) (1) strengthens the bound inherited from (2) by log⁡r under averaged mixing, matching the upper bound there. The dimension threshold falls from 240(1+τAr2)4. (1) requires r≥216 versus 212 in (2). Its hard chain lacks uniform mixing at scale τ. The lower-bound prefactor falls from 2−56 to 2−65.
(3) IID, bounded variance (Arjevani et al. 2023, Thm. 3) Ω(Ar2) (1) raises the IID lower bound inherited by the averaged-mixing class by a factor τlog⁡r throughout the common high-noise, high-dimensional regime. (3) also covers arbitrarily small positive σ for ε≤cLΔ.
(4) IID, bounded error (Jin 2026, Thm. 4.1) Ω(A(1+r2)) (1) gives a τlog⁡r larger lower bound for averaged mixing with stationary variance control, where ε≤2−20min{σ,LΔ} and dimension suffices for (1), (4). (4) establishes hardness even with almost surely σ-bounded error. The hard oracle in (1) exceeds this bound.
(5) Finite chain, hitting-time bound, zero-respecting methods (Sun and Wei 2025, Thm. 3.1) Ω(τh[A+r2min{r2,A}]) (1) covers unrestricted adaptive queries and outputs. At the hard cycles’ mixing scale τ≍τh2, the gain is τlog⁡r for r2≥A. For r2<A, the noise term grows from τr4 to τAr2log⁡r. (1) requires higher dimension. The hard-cycle conversion does not compare the hitting-time and averaged-mixing classes in general.

Abbr: A=LΔ/ε2, r=σ/ε, τh bounds the maximum expected state-to-state hitting time, c>0 is universal. Ω denotes a lower bound on necessary calls (one chain sample per call).

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2023. “Lower Bounds for Non-Convex Stochastic Optimization.” Mathematical Programming 199: 165–214. https://doi.org/10.1007/s10107-022-01822-7.
auto-math-bot. 2026. LongTails: MarkovNonconvexStationarityLowerBound. Lean lower-bound theorem, commit c8bf1984. https://github.com/k3nfalt/longtails/blob/c8bf1984b886b440e7edd8ac587ed08234d8d33d/LongTails/Theorems/MarkovNonconvexStationarityLowerBound.lean.
Jin, Jikai. 2026. A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise. https://doi.org/10.48550/arXiv.2608.09004.
Sun, Zhenyu, and Ermin Wei. 2025. “Learning from a Single Markovian Trajectory: Optimality and Variance Reduction.” Advances in Neural Information Processing Systems 38: 20004–33. https://doi.org/10.52202/085713-0675.

Lean setup