← All setups

Average Mixing Markov Smooth Nonconvex Lower Bound — High-Dimensional Nonconvex Optimization with Markov Noise

Descriptions may be stale. Consult the linked Lean sources.

High-Dimensional Nonconvex Optimization with Markov Noise · Lean proof

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.

Proved result

⌊τ⋅L⋅Δ⋅σ2⋅log⁡(σε)265⋅ε4⌋+

OracleTemplate.NonConvergence LongTails.Setups.HighDimensionalAverageMixingMarkovSmoothNonconvex.spec
  LongTails.Theorems.AverageMixingMarkovSmoothNonconvexLowerBound.budget

Relevant previous results

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