Descriptions may be stale. Consult the linked Lean sources.
Convex
Minimization with Markov Noise
We consider minimizing a differentiable convex function , where is a positive integer, with an -Lipschitz gradient, . A given point lies within distance of a global minimizer . At a query , the oracle returns , where indexes calls and 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 , the goal is a
measurable output with integrable
objective gap satisfying ,
averaging over the chain and independent algorithm randomness.
The optimization problem is where
denotes the Euclidean
norm. The parameters satisfy The algorithm receives ,
and .
Our assumptions:
Assumption 1 (Objective and initial distance). The
function is differentiable
everywhere, and for every and , There exists such that
Assumption 2 (Stationary Markov sampling and
mixing). Let be a Markov
transition kernel on and
let be a probability measure on
its Borel sets. The samples form a Markov chain with initial law and transition kernel . The measure is invariant: for every Borel set
,
For each integer , define
where denotes the Borel
sets and is the
point mass at . The function is -integrable and satisfies
Assumption 3 (Stationary oracle moments). The map
is jointly measurable. For every fixed , the map is Bochner integrable under
, the function is
-integrable, and
Queries may be made at any point of . On call , a query receives ; successive calls use
successive states of the same chain. The algorithm’s randomness is
independent of the chain. After the allotted calls, its output must be measurable, the gap must be integrable,
and where
is the joint law of the chain and the algorithm’s randomness.