Descriptions may be stale. Consult the linked Lean sources.
Convex
Minimization with Markov Noise
We consider minimizing a differentiable convex function on a separable real
Hilbert space . Its gradient is
-Lipschitz, where , and a given point is within distance of a global minimizer . At query , the oracle returns , where is a stationary,
polynomially mixing Markov chain. Under its stationary law, is unbiased and its centered -moment is at most , with and . For , the goal is a
measurable output with
integrable objective gap and ,
averaging over oracle and independent algorithm randomness.
The optimization problem is The norm is induced by the inner product
on . Let be a measurable sample space, and
let and be the mixing parameters. The
algorithm receives , , , , , , , , , and ; the objective and the oracle’s
sampling law are accessed through oracle replies.
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
every and ,
Assumption 2 (Initial distance). There exists such that
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 ,
For each integer , define the
total-variation distance using the convention where is the -step transition kernel and is the point mass at
. The function is integrable under and satisfies
Assumption 4 (Stationary oracle moments). The map
is jointly
measurable. For every fixed ,
is Bochner integrable
under , the function is
integrable under , and These moment conditions are taken under the
stationary law at each fixed query point.
Queries may be made at any point of . The oracle returns on call , starting at and using consecutive states of the
same chain. The query 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 must be measurable, its
objective gap must be integrable, and it must satisfy
where is the joint law of the
Markov chain and the independent algorithm randomness.