← All setups

Accelerated Heavy Tailed Markov Convex — Convex Minimization with Markov Noise

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Markov Noise · Lean proof

Convex Minimization with Markov Noise

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given point x0∈E is within distance R≥0 of a global minimizer x⋆. At query x, the oracle returns g(x,Zk), where (Zk)k≥0 is a stationary, polynomially mixing Markov chain. Under its stationary law, g is unbiased and its centered α-moment is at most σα, with 1<α≤2 and σ≥0. For ε>0, the goal is a measurable output x¯ with integrable objective gap and E[f(x¯)−f(x⋆)]≤ε, averaging over oracle and independent algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be a measurable sample space, and let τ>0 and β>0 be the mixing parameters. The algorithm receives E, Ω, L, R, σ, α, τ, β, ε, and x0; the objective and the oracle’s sampling law are accessed through oracle replies.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E and s∈[0,1], f((1−s)x+sy)≤(1−s)f(x)+sf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stationary Markov sampling and mixing). The samples form a time-homogeneous Markov chain on Ω with transition probability kernel κ and initial distribution π, where π is a probability measure. It is invariant: for every measurable A⊆Ω, EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, define the total-variation distance using the convention dt(z)=supA⊆Ωmeasurable|κt(z,A)−π(A)|, where κt is the t-step transition kernel and κ0(z,⋅) is the point mass at z. The function dt is integrable under π and satisfies EZ∼π[dt(Z)]≤(1+tτ)−β,t=0,1,2,….

Assumption 4 (Stationary oracle moments). The map g:E×Ω→E is jointly measurable. For every fixed x∈E, g(x,⋅) is Bochner integrable under π, the function ∥g(x,⋅)−∇f(x)∥α is integrable under π, and EZ∼π[g(x,Z)]=∇f(x),EZ∼π[∥g(x,Z)−∇f(x)∥α]≤σα. These moment conditions are taken under the stationary law at each fixed query point.

Queries may be made at any point of E. The oracle returns g(xk,Zk) on call k, starting at k=0 and using consecutive states of the same chain. The query xk may depend on previous replies and on algorithm randomness, which is independent of the chain. Any calls whose replies are discarded still count toward the oracle-call budget.

After the allotted calls, the output x¯∈E must be measurable, its objective gap must be integrable, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the Markov chain and the independent algorithm randomness.

Proved result

max{1,⌈32⋅L⋅R2ε+(256⋅σ⋅Rε)αα−1⌉+}⋅max{1,⌈τ⋅(256⋅L⋅R2ε+64⋅(256⋅σ⋅Rε)αα−1)1β⌉+}

OracleTemplate.Convergence LongTails.Setups.HeavyTailedMarkovSmoothAndConvex.spec
  OracleTemplate.HeavyTailedMarkovGradient.budget

Relevant previous results

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