Descriptions may be stale. Consult the linked Lean sources.
Nonconvex
Stationarity with Markovian Gradients
We seek an approximate stationary point of a possibly nonconvex
function in Euclidean
dimension . Its gradient is
Lipschitz, and the objective gap at a given starting point is bounded.
Each oracle call returns a stochastic gradient evaluated at the query
point and the current state of a stationary, uniformly exponentially
mixing Markov chain. At each fixed point, the estimate is unbiased under
the stationary law and has bounded variance. For a tolerance , the goal is an output
satisfying
, averaging over the chain and the
algorithm’s randomness.
The underlying optimization problem is Write
for the Euclidean norm.
The algorithm receives the dimension , the starting point , and the real
parameters . These
satisfy , , , and
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable on
. For all ,
Assumption 2 (Stationary Markov sampling). The
oracle uses successive states of a Markov chain on a
measurable space with transition kernel and initial law . The law is invariant: for every ,
For every and
integer , the -step transition law satisfies the total
variation bound
Assumption 3 (Stochastic gradient moments). On call
, a query at any returns , where is jointly measurable. For each fixed and , the vector is Bochner integrable, the squared
error is
integrable, and
Let be the joint law of the
Markov chain and the algorithm’s independent randomness. After the
allotted oracle calls, the output must be measurable, with integrable under
, and must satisfy