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 on a separable real
Hilbert space . It is the
stationary average of quadratic losses sharing a minimizer , with positive semidefinite
Hessians bounded by . A given
point satisfies , where . At query , the oracle returns , where is the Hessian indexed by a
finite-state Markov chain . The
chain starts arbitrarily and its transition law dominates times its invariant law, with
. For , the goal is ,
averaging over the chain and independent algorithm randomness for the
output .
The optimization problem is The norm is induced by the inner product
on . The algorithm receives only
, , , and ; the radius 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 with , a probability distribution on , bounded linear operators
, and a point such that Here
denotes the Hilbert space adjoint. The population objective satisfies
In particular, is a global minimizer and every
component gradient vanishes there.
Assumption 2 (Markov sampling and refresh). Let
be a Markov transition
kernel on , and write
. Its invariant
distribution and refresh condition satisfy The samples form a time-homogeneous
Markov chain with transition kernel and arbitrary initial distribution
on . Algorithm randomness is
independent of this chain.
Queries may be made at any point of . At the th call, starting with , a query receives the vector Thus
successive calls use successive states of the same chain. The
distributions and , the kernel , the operators , and the minimizer are not supplied to the
algorithm.
After the allotted oracle calls, the output must be measurable, its objective
gap must be integrable, and it must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.MarkovQuadraticInterpolation.spec OracleTemplate.MarkovQuadratic.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.