← All setups

Average Mixing Markov Smooth Nonconvex — Nonconvex Stationarity with Markov Gradients

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Stationarity with Markov Gradients · Lean proof

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

Proved result

(⌊2048⋅L⋅Δε2⌋++1)⋅((⌊256⋅σ2ε2⌋++1)⋅(⌊τ⋅log⁡(32+8192⋅σ2ε2)⌋++1))

OracleTemplate.Convergence LongTails.Setups.AverageMixingMarkovSmoothNonconvex.spec
  LongTails.Theorems.AverageMixingMarkovSmoothNonconvex.budget

Relevant previous results

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