← All setups

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 f:Rd→R in Euclidean dimension d. Its gradient is Lipschitz, and the gap from a given starting point to the finite infimum is bounded. Each query returns a stochastic gradient evaluated at the current state of a stationary real-valued Markov chain. At each fixed query point, the reply is unbiased under the stationary law and has bounded variance. The chain mixes exponentially in stationary-average total variation. For a tolerance ε>0, the output x¯ must satisfy E∥∇f(x¯)∥≤ε, averaging over the chain and the algorithm’s independent randomness.

Write f⋆ for the value of the optimization problem infx∈Rdf(x). All norms are Euclidean. The algorithm receives the dimension d∈{0,1,…}, the starting point x0∈Rd, the smoothness constant L>0, the initial gap bound Δ≥0, the noise bound σ≥0, the mixing parameter τ≥1, and the tolerance ε.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is differentiable throughout Rd, and for all x,y∈Rd, ∥∇f(x)−∇f(y)∥≤L∥x−y∥. The infimum f⋆ is finite and satisfies f(x0)−f⋆≤Δ.

Assumption 2 (Stationarity and average mixing). The oracle uses a single Markov chain (Zk)k≥0 on R with transition kernel κ and initial law π. For every Borel set A⊆R, the law π satisfies EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, let κt denote the t-step kernel and define its total variation distance from stationarity by Dt(z)=supA∈B(R)|κt(z,A)−π(A)|, where B(R) is the Borel σ-algebra. The function Dt is π-integrable and satisfies EZ∼π[Dt(Z)]≤2exp⁡(−t/τ).

Assumption 3 (Stochastic gradients under the stationary law). On call k, indexed from zero, a query at any x∈Rd returns g(x,Zk), where g:Rd×R→Rd is jointly measurable. For every 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 output x¯∈Rd must be measurable, with integrable gradient norm satisfying E[∥∇f(x¯)∥]≤ε.

Results

The possibly nonconvex f:Rd→R has L-Lipschitz gradient and f(x0)−inff≤Δ. Each call returns g(x,Zt) from one stationary real-valued Markov chain with kernel P and law π, where ∫∥Pt(z,⋅)−π∥TVπ(dz)≤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 at every fixed x. The parameters L,ε>0, Δ,σ≥0 and τ≥1 are known. The target is E∥∇f(X)∥≤ε over the trajectory and algorithm randomness.

Sufficient oracle budgets for stationarity under stationary-average Markov mixing: sufficient oracle budgets.
Result Oracle complexity Novelty Limitations
(1) AverageMixingMarkovSmoothNonconvex (Ours) (⋆⋆) (review) O(τ(1+D)(1+S)log⁡(2+S)) calls, including discarded transitions.
(2) Derived bound: blocking (Yu 1994, Lem. 4.1) and normalized minibatch descent (Cutkosky and Mehta 2020, Lem. 2) O(τ(1+D)(1+S)log⁡(2+DS)) calls for S≥1. (1) removes D from the logarithm. For S=1, D→∞, the cost falls from O(τDlog⁡D) to O(τD). The factor diverges when D=(2+S)ω(1).
(3) MarkovNonconvexStationarity (LongTails 2026) O(τDSlog⁡S) calls under uniform mixing, S≥40962, D≥226 and d≥240(1+τDS)4. (1) matches (3) on the overlap and allows stationary-average mixing, every dimension and all D,S≥0.
(4) Derived bound: minibatch GD (Beznosikov et al. 2023, Lem. 1) O(1+D+τDS) calls under uniform mixing at scale τ and ∥g(x,z)−∇f(x)∥≤σ for every x,z. (1) needs only stationary-average mixing and stationary variance. (1) bounds the mean norm. (4) also bounds its second moment by ε2. For D≥1, (1) costs an extra factor of order log⁡(2+S) when S≥1, or τ when S≤1/τ.
(5) MaC-SPIDER (Sun and Wei 2025, Thm. 4.4) O(τmixL¯Δ(1+σ2)πminε3) state samples for ε≤min{1,L¯Δ}, with up to two gradient evaluations per sample. (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 ε→0, (5) gives O(ε−3) on its subclass with shared-state access. (1) gives O(ε−4log⁡(1/ε)) with fresh-state calls.

Abbr: D=LΔ/ε2, S=σ2/ε2; TV denotes total variation, τmix the worst-start 1/4-mixing time, πmin the least stationary state mass, and L¯ the root-mean-square Lipschitz constant of the sample gradient.

Beznosikov, Aleksandr, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, and Eric Moulines. 2023. “First Order Methods with Markovian Noise: From Acceleration to Variational Inequalities.” Advances in Neural Information Processing Systems 36: 44820–35. https://doi.org/10.52202/075280-1941.
Cutkosky, Ashok, and Harsh Mehta. 2020. “Momentum Improves Normalized SGD.” Proceedings of the 37th International Conference on Machine Learning, Proceedings of machine learning research, vol. 119: 2260–68. https://proceedings.mlr.press/v119/cutkosky20b.html.
LongTails. 2026. MarkovNonconvexStationarity. Lean theorem in the LongTails repository.
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.
Yu, Bin. 1994. “Rates of Convergence for Empirical Processes of Stationary Mixing Sequences.” The Annals of Probability 22 (1): 94–116. https://doi.org/10.1214/aop/1176988849.

Lean setup