Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional
Nonconvex Optimization with Markov Noise
We seek a stationary point of a differentiable, possibly nonconvex
function in high
dimension . The gradient is
Lipschitz, and the gap from a given starting point to the finite infimum
is bounded. Each query returns a gradient estimate driven by the next
state of a stationary real-valued Markov chain whose total variation
distance to stationarity decays exponentially on average. At each fixed
query point, the estimate is unbiased under the stationary law and has
bounded variance. For , the goal is an output
satisfying over chain and algorithm
randomness.
The optimization problem is where
denotes the Euclidean
norm. The algorithm receives the dimension , the starting point , the gradient
Lipschitz bound , the initial
gap bound , the noise scale
, the mixing parameter , and the tolerance . We consider the
parameter regime Writing , the dimension
requirement is
Our assumptions:
Assumption 1 (Smoothness and initial gap). The
function is differentiable
everywhere, and is
finite. For all ,
Assumption 2 (Stationarity and average mixing). The
chain starts with
law on and has Markov transition
kernel . The law is invariant, so for every Borel set
,
For each integer , define
the total variation distance after transitions from by The function is -integrable and satisfies
Assumption 3 (Stochastic gradient oracle). At call
, a query at any returns , where
is jointly measurable. For each fixed , the map is Bochner integrable under
, the squared error is -integrable, and
After the allotted oracle calls, the algorithm must return a
measurable output with integrable
gradient norm satisfying The expectation is over the
Markov chain and the algorithm’s internal randomness, which are
independent.