Average Mixing Markov Smooth Nonconvex — Nonconvex Stationarity with Markov Gradients
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Stationarity with Markov Gradients · Lean proof
Nonconvex Stationarity
with Markov Gradients
We seek an approximately stationary point of a possibly nonconvex
function in Euclidean
dimension . Its gradient is
Lipschitz, and the gap from a given starting point to the finite infimum
is bounded. Each query returns a stochastic gradient evaluated at the
current state of a stationary real-valued Markov chain. At each fixed
query point, the reply is unbiased under the stationary law and has
bounded variance. The chain mixes exponentially in stationary-average
total variation. For a tolerance , the output must satisfy , averaging over the chain and the
algorithm’s independent randomness.
Write for the value of
the optimization problem All norms
are Euclidean. The algorithm receives the dimension , the starting point
, the smoothness
constant , the initial gap
bound , the noise bound
, the mixing parameter
, and the tolerance .
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
throughout , and for
all , The infimum is finite and satisfies .
Assumption 2 (Stationarity and average mixing). The
oracle uses a single Markov chain on with transition kernel and initial law . For every Borel set , the law satisfies
For each integer , let denote the -step kernel and define its total
variation distance from stationarity by
where is
the Borel -algebra. The
function is -integrable and satisfies
Assumption 3 (Stochastic gradients under the
stationary law). On call , indexed
from zero, a query at any returns , where
is jointly measurable. For every fixed , the map is Bochner integrable under
, the squared error is -integrable, and
After the allotted oracle calls, the output must be
measurable, with integrable gradient norm satisfying
Proved result
OracleTemplate.Convergence LongTails.Setups.AverageMixingMarkovSmoothNonconvex.spec
LongTails.Theorems.AverageMixingMarkovSmoothNonconvex.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.