← All setups

Markov Nonconvex Stationarity Lower Bound — Nonconvex Stationarity with Markovian Gradients

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Stationarity with Markovian Gradients · Lean proof

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¯)∥]≤ε.

Proved result

⌊τ⋅L⋅Δ⋅σ2256⋅ε4⌋+

OracleTemplate.NonConvergence LongTails.Setups.MarkovSmoothNonconvex.spec
  LongTails.Theorems.MarkovNonconvexStationarityLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.