← All setups

Polynomial Mixing Heavy Tailed Convex Lower Bound — Convex Minimization with Polynomial Mixing

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Polynomial Mixing · Lean proof

Convex Minimization with Polynomial Mixing

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E lies within distance R>0 of a global minimizer x⋆. At call k≥0, the oracle returns g(x,Zk)∈E at query x∈E, where (Zk) is a stationary Markov chain with polynomial mixing. Under its stationary distribution, the replies are unbiased and have uniformly bounded centered moments of order α∈(1,2]. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be the measurable state space of the chain. The algorithm receives E, Ω, x0, and all numerical parameters L,R,σ,α,τ,β,ε; the objective and the oracle’s defining map and transition law are accessed only through oracle replies.

Our assumptions:

Assumption 1 (Parameter regime). The parameters satisfy L,R,σ,τ,β,ε>0,1<α≤2. There exists a unit vector in E, and Ω contains distinct points a,b whose singletons are measurable. The numerical restrictions are 16≤LR2ε,LR2ε≤(σRε)α/(α−1),24α−1≤(σRε)α,β(24α−1(σR/ε)α)1/(β(α−1))≤τ.

Assumption 2 (Objective and initial distance). The function f is convex and Fréchet differentiable everywhere on E. For every x,y∈E and s∈[0,1], f((1−s)x+sy)≤(1−s)f(x)+sf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥. There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stationary polynomial mixing). The chain has a Markov transition kernel κ on Ω and initial distribution π, where π is an invariant probability measure. Thus, for every measurable A⊆Ω, Z0∼π,EZ∼π[κ(Z,A)]=π(A). For every integer t≥0, define dt(z)=supA⊆Ω measurable|κt(z,A)−π(A)|, where κt is the t-step transition kernel and κ0(z,⋅) is the probability measure concentrated at z. This is the total-variation convention without an additional factor of two. Each dt is integrable under π, and EZ∼π[dt(Z)]≤(1+tτ)−β,t≥0.

Assumption 4 (Stationary oracle moments). The map g:E×Ω→E is jointly measurable. For every fixed x∈E, the map g(x,⋅) is Bochner integrable under π, the function ∥g(x,⋅)−∇f(x)∥α is integrable under π, and EZ∼π[g(x,Z)]=∇f(x),EZ∼π[∥g(x,Z)−∇f(x)∥α]≤σα.

Queries may be made at any point of E. The reply to the kth query xk is g(xk,Zk), using consecutive states of the same chain, including when queries are adaptive. Any algorithm randomness is independent of the entire chain. All calls count toward the oracle-call budget, including calls whose replies are discarded.

After the allotted calls, the output x¯ must be measurable, its objective gap must be integrable, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm’s randomness and the stationary Markov chain.

Proved result

⌊τβ⋅((σ⋅Rε)α24⋅α−1)β+1β⋅(α−1)⌋+

OracleTemplate.NonConvergence LongTails.Setups.PolynomialMixingHeavyTailedConvex.spec
  LongTails.Theorems.PolynomialMixingHeavyTailedConvexLowerBound.budget

Relevant previous results

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