Descriptions may be stale. Consult the linked Lean sources.
Convex
Minimization with Polynomially Mixing Subgradients
We minimize a function that is
convex on a closed Euclidean ball
and attains its minimum there at , where is a positive integer. At each query
, the oracle returns a vector
driven by the next observation of a stationary, polynomially absolutely
regular process. At each fixed ,
the reply has a uniformly bounded th moment for , and its stationary mean is a
subgradient relative to . For
tolerance and
failure probability , the
goal is a measurable output satisfying with
probability at least .
With denoting the
Euclidean norm, the constrained problem is The algorithm receives
,
where is the radius, is the moment bound in norm units,
and and are the mixing exponent and
time scale. The accuracy parameters satisfy and .
Our assumptions:
Assumption 1 (Convexity and attainment). For all
and , There
exists such that for every .
Assumption 2 (Polynomial absolute regularity). Let
be the real-valued
oracle process, with path law on
. Write
for the past
and for the
future starting at . The process
is stationary, so for every . For all integers , where
with the supremum over measurable sets .
Assumption 3 (Stationary subgradients and moments).
At query on call , indexed from zero, the oracle returns
for a jointly measurable
map . Let
. For each
, is Bochner integrable under
, and is integrable under
. With , we
require, for all ,
After the allotted oracle calls, the algorithm must return a
measurable -valued output satisfying
where the probability is over the oracle process and the independent
randomness of the algorithm.