← All setups

Stretched Exponential Markov Convex Upper Bound — 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:Rd→R, where d is a positive integer, with an L-Lipschitz gradient, L>0. A given point x0 lies within distance R>0 of a global minimizer x⋆. At a query x, the oracle returns g(x,Zk), where k indexes calls and (Zk) is a stationary real-valued Markov chain with stretched-exponential mixing in averaged total variation. The noise is unbiased under the stationary law and has a uniformly bounded moment of order between one and two. For ε>0, the goal is a measurable output x¯∈Rd with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over the chain and independent algorithm randomness.

The optimization problem is minx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The parameters satisfy d∈N,d≥1,L,R,σ,ε>0,1<α≤2,τ≥1,0<γ≤1,4ε≤LR2,32ε≤σR,LR2ε≤(σRε)α/(α−1). The algorithm receives d,L,R,σ,α,τ,γ,ε, and x0∈Rd.

Our assumptions:

Assumption 1 (Objective and initial distance). The function f is differentiable everywhere, and for every x,y∈Rd and s∈[0,1], f((1−s)x+sy)≤(1−s)f(x)+sf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥. There exists x⋆∈Rd such that f(x⋆)≤f(x)for all x∈Rd,∥x0−x⋆∥≤R.

Assumption 2 (Stationary Markov sampling and mixing). Let κ be a Markov transition kernel on R and let π be a probability measure on its Borel sets. The samples form a Markov chain with initial law Z0∼π and transition kernel κ. The measure π is invariant: for every Borel set A⊆R, EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, define mt(z)=∥κt(z,⋅)−π∥TV,∥μ−ν∥TV=supA∈B(R)|μ(A)−ν(A)|, where B(R) denotes the Borel sets and κ0(z,⋅) is the point mass at z. The function mt is π-integrable and satisfies EZ∼π[mt(Z)]≤exp(−(tτ)γ),t≥0.

Assumption 3 (Stationary oracle moments). The map g:Rd×R→Rd is jointly measurable. For every fixed x∈Rd, the map g(x,⋅) is Bochner integrable under π, the function z↦∥g(x,z)−∇f(x)∥α is π-integrable, and EZ∼π[g(x,Z)]=∇f(x),EZ∼π[∥g(x,Z)−∇f(x)∥α]≤σα.

Queries may be made at any point of Rd. On call k=0,1,…, a query xk receives g(xk,Zk); successive calls use successive states of the same chain. The algorithm’s randomness is independent of the chain. After the allotted calls, its output x¯ must be measurable, the gap f(x¯)−f(x⋆) must be integrable, and EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the chain and the algorithm’s randomness.

Proved result

⌈32⋅L⋅R2ε+(256⋅σ⋅Rε)αα−1⌉+⋅⌈exp⁡(1)⋅τ⋅(log⁡(256⋅L⋅R2ε+64⋅(256⋅σ⋅Rε)αα−1)γ)1γ⌉+

OracleTemplate.Convergence LongTails.Setups.StretchedExponentialMarkovConvex.spec
  LongTails.Theorems.StretchedExponentialMarkovConvexUpperBound.budget

Relevant previous results

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