← All setups

Convex Minimization with Polynomial Mixing

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Convex L-smooth f on a nontrivial, second-countable real Hilbert space with its Borel structure; a minimizer satisfies ∥x0−x⋆∥≤R. A stationary Markov chain on a measurable space with two distinct measurable singletons supplies jointly measurable gradients g, with ∫g(x,z)dπ(z)=∇f(x) and ∫∥g(x,z)−∇f(x)∥αdπ(z)≤σα; these integrands are integrable. Its integrated total-variation distance satisfies ∫∥κt(z,⋅)−π∥TVdπ(z)≤(1+t/τ)−β. Parameters obey L,R,σ,τ,β,ε>0, 1<α≤2, 16≤T≤S, S≥Cα, and τ≥β(Cα/S)1/β. Target: a measurable output with integrable gap and ∫[f(x^)−f(x⋆)]dP≤ε, where P includes chain and algorithm randomness. Lower bounds concern every randomized adaptive algorithm.

Necessary oracle budgets under PolynomialMixingHeavyTailedConvex.
Result Oracle complexity Novelty Limitations
(1) PolynomialMixingHeavyTailedConvexLowerBound (Ours) (⋆⋆) (review) Lower bound (necessary): Ω(τβ(S/Cα)1+1/β). Failure at every N≤⌊(τ/β)(S/Cα)1+1/β⌋.
(2) Derived bound (Sarkar et al. 2026, App. H.4); stationary convex transfer Lower bound (necessary): Ωα((τ/β)S). Uniform-geometric subclass: supz∥κt(z,⋅)−π∥TV≤e−βt/τ, τ≥2β; expected-gap target. (1): averaged polynomial mixing increases the necessary budget by an asymptotic factor S1/β at fixed α,β. This strengthens hardness for the larger class. (1): restricted to T≤S; constants deteriorate as α↓1 or β↓0.
(3) Derived bound (Sarkar et al. 2026, App. H.4); i.i.d. two-point specialization Lower bound (necessary): Ωα(S). Independent stationary samples; convex expected-gap target. (1): Markov dependence adds an asymptotic necessary-budget factor (τ/β)S1/β at fixed α,β in the stated regime. This strengthens hardness for the larger class.

Abbr: T=LR2/ε, S=(σR/ε)α/(α−1), Cα=2(4α−1)/(α−1); N counts gradient calls, including calls used only to advance the chain. π is invariant, κ is the transition kernel, and P is the joint execution law. Ω denotes a necessary budget; subscripts indicate permitted dependence of its constant.

Sarkar, Dhruv, Aprameyo Chakrabartty, and Vaneet Aggarwal. 2026. High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence. https://doi.org/10.48550/arXiv.2606.26316.

Lean setup