← All setups

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 f:Rd→R in Euclidean dimension d. Its gradient is Lipschitz, and the objective gap at a given starting point is bounded. Each oracle call returns a stochastic gradient evaluated at the query point and the current state of a stationary, uniformly exponentially mixing Markov chain. At each fixed point, the estimate is unbiased under the stationary law and has bounded variance. For a tolerance ε>0, the goal is an output x¯∈Rd satisfying E∥∇f(x¯)∥≤ε, averaging over the chain and the algorithm’s randomness.

The underlying optimization problem is infx∈Rdf(x). Write ∥⋅∥ for the Euclidean norm. The algorithm receives the dimension d∈N, the starting point x0∈Rd, and the real parameters L,Δ,σ,τ,ε. These satisfy L>0, ε>0, τ≥1, and σ≥4096ε,LΔ≥226ε2,d≥240(1+τLΔσ2ε4)4.

Our assumptions:

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

Assumption 2 (Stationary Markov sampling). The oracle uses successive states Z0,Z1,… of a Markov chain on a measurable space (Z,F) with transition kernel κ and initial law π. The law π is invariant: for every A∈F, EZ∼π[κ(Z,A)]=π(A). For every z∈Z and integer t≥0, the t-step transition law satisfies the total variation bound supA∈F|κt(z,A)−π(A)|≤2exp⁡(−t/τ).

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

Let P be the joint law of the Markov chain and the algorithm’s independent randomness. After the allotted oracle calls, the output x¯ must be measurable, with ∥∇f(x¯)∥ integrable under P, and must satisfy EP[∥∇f(x¯)∥]≤ε.

Results

f:Rd→R has L-Lipschitz gradient and f(x0)−inff≤Δ. Each call returns one vector g(x,Zt) from a stationary chain on a measurable space, with supz∥Pt(z,⋅)−π∥TV≤2e−t/τ. The jointly measurable oracle satisfies Eπg(x,Z)=∇f(x) and Eπ∥g(x,Z)−∇f(x)∥2≤σ2 for every x. All parameters are public. For L,ε>0, τ≥1, σ≥4096ε, LΔ≥226ε2 and d≥240(1+τAV)4, the target is E∥∇f(X)∥≤ε over the stream and algorithm randomness.

Expected stationarity on a single MarkovSmoothNonconvex trajectory. The necessary and sufficient budgets differ by log⁡(σ2/ε2).
Result Oracle complexity Novelty Limitations
(1) MarkovNonconvexStationarityLowerBound (Ours) (⋆⋆⋆) (review) Lower bound (necessary)
Ω(τAV)
(2) MarkovNonconvexStationarity (Ours) (⋆⋆) (review) Upper bound (sufficient)
O(τAVlog⁡V), including discarded replies
(3) (Sun and Wei 2025b, Thm. 3.1, smooth case) Ω(h[A+Vmin{V,A}]) (1) covers all randomized adaptive algorithms. For the lazy-cycle construction, h≍τ. The gain is a factor ≍τ for V≥A, and ≍τmin{V,A/V} for V<A. (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) Ω(hV[1+min{V,A}]) (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)) Ω(AV), IID samples, ε≤cLΔ (1) strengthens the IID lower bound by a factor τ for τ>1 on the Markov class, retaining unrestricted randomized algorithms. (1) needs σ≥4096ε and dimension quartic in the budget scale. Its explicit failure threshold has prefactor 2−56.

Abbr: A=LΔ/ε2, V=σ2/ε2, h is the hitting-time parameter, tmix is the 1/4-TV mixing time, πmin=minzπ(z) on a finite chain, L¯ is the mean-squared smoothness constant, and c is universal.

Table 1, continued.

Result Oracle complexity Novelty Limitations
(6) Derived bound (Beznosikov et al. 2023, Lem. 1, Eq. (6)) O(A+τAV), fixed minibatches (2) allows noise unbounded across states. (6) requires ∥g(x,z)−∇f(x)∥≤σ for every state. (2) costs a factor log⁡V more on the overlap, requires stationary initialization, and controls only the expected norm. (6) gives E∥∇f(X)∥2≤ε2.
(7) (Beznosikov et al. 2023, Cor. 2, δ=0) O(τAVlog2⁡V) expected gradient evaluations. The uncapped stream advance has infinite mean. (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 E∥∇f(X)∥2≤ε2.
(8) Derived bound (Sun and Wei 2025b, Lem. 4.1(1)) O(A+tmixAV/πmin), finite-chain minibatches (2) covers general state spaces. For tmix≍τ, it replaces πmin−1/2 by log⁡V, saving calls when πmin−1/2≫log⁡V. (2) needs a stationary start. For tmix≍τ, it costs more when πmin−1/2≪log⁡V.
(9) MaC-SPIDER (Sun and Wei 2025b, Thm. 4.4) O(tmixπmin[max{σ,σ2}ε2
+L¯Δ(1+σ2)ε3])
(2) permits general state spaces and needs only smoothness of f. (9) requires finite states, mean-squared smoothness and gradient differences across query points using shared samples. For fixed remaining parameters and small ε≤1, (9) achieves ε−3 on its subclass. (2) has ε−4log⁡V dependence.

Abbr: A=LΔ/ε2, V=σ2/ε2, h is the hitting-time parameter, tmix is the 1/4-TV mixing time, πmin=minzπ(z) on a finite chain, L¯ is the mean-squared smoothness constant, and c is universal.

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.
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.” In Advances in Neural Information Processing Systems, edited by A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, vol. 36. Curran Associates, Inc. https://doi.org/10.52202/075280-1941.
Sun, Zhenyu, and Ermin Wei. 2025a. “Improved Lower Bounds for First-Order Stochastic Non-Convex Optimization Under Markov Sampling.” In Proceedings of the 42nd International Conference on Machine Learning, edited by Aarti Singh, Maryam Fazel, Daniel Hsu, et al., vol. 267. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v267/sun25u.html.
Sun, Zhenyu, and Ermin Wei. 2025b. “Learning from a Single Markovian Trajectory: Optimality and Variance Reduction.” In Advances in Neural Information Processing Systems, edited by D. Belgrave, C. Zhang, H. Lin, et al., vol. 38. Curran Associates, Inc. https://doi.org/10.52202/085713-0675.

Lean setup