← All setups

Markov Quadratic Last Iterate — Markov Quadratic Interpolation

Descriptions may be stale. Consult the linked Lean sources.

Markov Quadratic Interpolation · Lean proof

Markov Quadratic Interpolation

We consider minimizing a convex quadratic f:E→R on a separable real Hilbert space E. It is the stationary average of quadratic losses sharing a minimizer x⋆, with positive semidefinite Hessians bounded by L>0. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0. At query x, the oracle returns HZ(x−x⋆), where HZ is the Hessian indexed by a finite-state Markov chain Z. The chain starts arbitrarily and its transition law dominates α times its invariant law, with 0<α≤1. For ε>0, the goal is E[f(x¯)−f(x⋆)]≤ε, averaging over the chain and independent algorithm randomness for the output x¯∈E.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, L, x0, and α; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Interpolating quadratic model). There exist a finite index set I={1,…,m} with m≥1, a probability distribution π on I, bounded linear operators Hi:E→E, and a point x⋆∈E such that Hi∗=Hi(i∈I),0≤⟨v,Hiv⟩≤L∥v∥2(i∈I, v∈E),∥x0−x⋆∥≤R. Here Hi∗ denotes the Hilbert space adjoint. The population objective satisfies f(x)−f(x⋆)=12EI∼π[⟨x−x⋆,HI(x−x⋆)⟩],x∈E. In particular, x⋆ is a global minimizer and every component gradient vanishes there.

Assumption 2 (Markov sampling and refresh). Let κ be a Markov transition kernel on I, and write πj=π({j}). Its invariant distribution and refresh condition satisfy EI∼π[κ(I,{j})]=πj(j∈I),κ(i,{j})≥απj(i,j∈I). The samples (Zk)k≥0 form a time-homogeneous Markov chain with transition kernel κ and arbitrary initial distribution μ on I. Algorithm randomness is independent of this chain.

Queries may be made at any point of E. At the kth call, starting with k=0, a query x receives the vector g(x,Zk)=HZk(x−x⋆). Thus successive calls use successive states of the same chain. The distributions π and μ, the kernel κ, the operators Hi, and the minimizer x⋆ are not supplied to the algorithm.

After the allotted oracle calls, the output x¯ must be measurable, its objective gap must be integrable, and it must satisfy E[f(x¯)−f(x⋆)]≤ε.

Proved result

⌈10000000000000000⋅L⋅R2α⋅ε⌉++1

OracleTemplate.Convergence LongTails.Setups.MarkovQuadraticInterpolation.spec OracleTemplate.MarkovQuadratic.budget

Relevant previous results

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