Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with
Polynomial Mixing
We consider minimizing a differentiable convex function on a separable real
Hilbert space . Its gradient is
-Lipschitz, with , and a given point lies within distance of a global minimizer . At call , the oracle returns at query , where is a stationary Markov chain with
polynomial mixing. Under its stationary distribution, the replies are
unbiased and have uniformly bounded centered moments of order . For , the goal is a
measurable output with
integrable objective gap satisfying .
The optimization problem is The norm is induced by the inner product
on . Let be the measurable state space of
the chain. The algorithm receives , , , and all numerical parameters ;
the objective and the oracle’s defining map and transition law are
accessed only through oracle replies.
Our assumptions:
Assumption 1 (Parameter regime). The parameters
satisfy There exists a unit vector in , and contains distinct points whose singletons are measurable. The
numerical restrictions are
Assumption 2 (Objective and initial distance). The
function is convex and Fréchet
differentiable everywhere on . For
every and , There exists such that
Assumption 3 (Stationary polynomial mixing). The
chain has a Markov transition kernel on and initial distribution , where is an invariant probability measure.
Thus, for every measurable , For every integer
, define where is the -step transition kernel and is the probability
measure concentrated at . This is
the total-variation convention without an additional factor of two. Each
is integrable under , and
Assumption 4 (Stationary oracle moments). The map
is jointly
measurable. For every fixed ,
the map is Bochner
integrable under , the function
is integrable under , and
Queries may be made at any point of . The reply to the th query is , using consecutive states of
the same chain, including when queries are adaptive. Any algorithm
randomness is independent of the entire chain. All calls count toward
the oracle-call budget, including calls whose replies are discarded.
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 algorithm’s randomness and the stationary Markov
chain.