← All setups

Polynomial Mixing Confidence Lower Bound — Convex Minimization with Polynomially Mixing Subgradients

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Polynomially Mixing Subgradients · Lean proof

Convex Minimization with Polynomially Mixing Subgradients

We minimize a function f:Rd→R that is convex on a closed Euclidean ball D and attains its minimum there at x⋆, where d is a positive integer. At each query x∈D, the oracle returns a vector driven by the next observation of a stationary, polynomially absolutely regular process. At each fixed x, the reply has a uniformly bounded pth moment for 1<p≤2, and its stationary mean is a subgradient relative to D. For tolerance ε>0 and failure probability δ, the goal is a measurable output x¯∈D satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

With ∥⋅∥ denoting the Euclidean norm, the constrained problem is minx∈Df(x),D={x∈Rd:∥x∥≤R}. The algorithm receives d,R,G,p,β,τ,ε,δ, where R>0 is the radius, G>0 is the moment bound in norm units, and β>0 and τ≥1 are the mixing exponent and time scale. The accuracy parameters satisfy 0<ε≤GR/8 and 0<δ≤1/32.

Our assumptions:

Assumption 1 (Convexity and attainment). For all x,y∈D and s∈[0,1], f((1−s)x+sy)≤(1−s)f(x)+sf(y). There exists x⋆∈D such that f(x⋆)≤f(x) for every x∈D.

Assumption 2 (Polynomial absolute regularity). Let Z=(Zk)k≥0 be the real-valued oracle process, with path law Q on RN0. Write Hn=(Z0,…,Zn) for the past and Fj=(Zj+k)k≥0 for the future starting at j. The process is stationary, so L(Fj)=Q for every j≥0. For all integers n,t≥0, ‖L(Hn,Fn+t)−L(Hn)⊗Q‖TV≤(1+t/τ)−β, where ∥μ−ν∥TV=supB|μ(B)−ν(B)| with the supremum over measurable sets B.

Assumption 3 (Stationary subgradients and moments). At query x∈D on call k, indexed from zero, the oracle returns g(x,Zk) for a jointly measurable map g:D×R→Rd. Let π=L(Z0). For each x∈D, g(x,⋅) is Bochner integrable under π, and ∥g(x,⋅)∥p is integrable under π. With m(x)=Ez∼π[g(x,z)], we require, for all x,y∈D, Ez∼π[∥g(x,z)∥p]≤Gp,f(x)+⟨m(x),y−x⟩≤f(y).

After the allotted oracle calls, the algorithm must return a measurable D-valued output x¯ satisfying P(f(x¯)−f(x⋆)≤ε)≥1−δ, where the probability is over the oracle process and the independent randomness of the algorithm.

Proved result

⌊τ⋅((G⋅R8⋅ε)pp−1⋅(1+1β)⋅log⁡(1δ⋅14)+(16⋅δ)−1β)8⋅(1+2⋅β)⌋+

OracleTemplate.NonConvergence LongTails.Setups.PolynomialMixingSubgradient.spec
  LongTails.Theorems.PolynomialMixingConfidenceLowerBound.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.