← All setups

Convex Minimization with Markov Noise

Descriptions may be stale. Consult the linked Lean sources.

Convex Minimization with Markov Noise

We consider minimizing a differentiable convex function f:Rd→R, where d is a positive integer, with an L-Lipschitz gradient, L>0. A given point x0 lies within distance R>0 of a global minimizer x⋆. At a query x, the oracle returns g(x,Zk), where k indexes calls and (Zk) is a stationary real-valued Markov chain with stretched-exponential mixing in averaged total variation. The noise is unbiased under the stationary law and has a uniformly bounded moment of order between one and two. For ε>0, the goal is a measurable output x¯∈Rd with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over the chain and independent algorithm randomness.

The optimization problem is minx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The parameters satisfy d∈N,d≥1,L,R,σ,ε>0,1<α≤2,τ≥1,0<γ≤1,4ε≤LR2,32ε≤σR,LR2ε≤(σRε)α/(α−1). The algorithm receives d,L,R,σ,α,τ,γ,ε, and x0∈Rd.

Our assumptions:

Assumption 1 (Objective and initial distance). The function f is differentiable everywhere, and for every x,y∈Rd 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⋆∈Rd such that f(x⋆)≤f(x)for all x∈Rd,∥x0−x⋆∥≤R.

Assumption 2 (Stationary Markov sampling and mixing). Let κ be a Markov transition kernel on R and let π be a probability measure on its Borel sets. The samples form a Markov chain with initial law Z0∼π and transition kernel κ. The measure π is invariant: for every Borel set A⊆R, EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, define mt(z)=∥κt(z,⋅)−π∥TV,∥μ−ν∥TV=supA∈B(R)|μ(A)−ν(A)|, where B(R) denotes the Borel sets and κ0(z,⋅) is the point mass at z. The function mt is π-integrable and satisfies EZ∼π[mt(Z)]≤exp(−(tτ)γ),t≥0.

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

Queries may be made at any point of Rd. On call k=0,1,…, a query xk receives g(xk,Zk); successive calls use successive states of the same chain. The algorithm’s randomness is independent of the chain. After the allotted calls, its output x¯ must be measurable, the gap f(x¯)−f(x⋆) must be integrable, and EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the chain and the algorithm’s randomness.

Results

Convex L-smooth f:Rd→R, d≥1, with a minimizer x⋆ satisfying ∥x0−x⋆∥≤R. A stationary real-state Markov chain with kernel κ and invariant probability π supplies jointly measurable gradients with ∫g(x,z)dπ(z)=∇f(x) and ∫∥g(x,z)−∇f(x)∥αdπ(z)≤σα; these quantities and the mixing distances are integrable. Averaged mixing obeys ∫∥κt(z,⋅)−π∥TVdπ(z)≤e−(t/τ)γ. Here L,R,σ,ε>0, 1<α≤2, τ≥1, 0<γ≤1, 4ε≤LR2, 32ε≤σR, and LR2/ε≤(σR/ε)α/(α−1). Target: measurable output with integrable gap ∫[f(x^)−f(x⋆)]dP≤ε, where P is the execution law. The setup permits arbitrary randomized adaptive algorithms. The necessary and sufficient orders match for fixed α,γ in this noise-dominated regime; constants are not uniform as α↓1 or γ↓0.

Necessary and sufficient budgets for StretchedExponentialMarkovConvex.
Result Oracle complexity Novelty Limitations
(1) StretchedExponentialMarkovConvexLowerBound (Ours) (⋆⋆) (review) Ω(τ8−kS[k2log⁡σR8ε]1/γ)
(2) StretchedExponentialMarkovConvexUpperBound (Ours) (review) O(τ256kS[log⁡Wγ]1/γ)
(3) (LongTails, n.d.), specialized polynomial-mixing guarantee

O(τ256kS[log⁡Wγ]1/γ)

β=log⁡W, τp=τ(β/γ)1/γ.

(2): Matches known rate, algorithm and output; identical budget under the envelope inclusion. (2): Finite-dimensional, noise-dominated specialization of a Hilbert-space guarantee.
(4) (Solodkin et al. 2025), Thm. 2/Cor. 2

Expected total cost:

O([LR2ε+τσ2R2ε2]

×polylog(2+LR2ε+τσ2R2ε2)).

Special case: α=2, γ=1, ∥g−∇f∥≤σ a.s., uniform geometric mixing; Euclidean ball of radius R.

(2): Scope: stationary α-moment noise and averaged stretched-exponential mixing replace bounded noise and uniform geometric mixing. Matches polynomial accuracy dependence at α=2, γ=1, up to logarithms. (2): Euclidean geometry only.
(5) Derived bound, (Duchi et al. 2012), Thm. 1/(12)

O(τG2R2ε2[log⁡8GRε]1/γ).

Special case: convex sample losses, ∥g∥≤G on the radius-R ball, uniform mixing with τTV(δ)≤τlog1/γ⁡(1/δ).

(2): Matches the G-based rate for fixed γ at α=2, σ≤2G; removes bounded gradients and uniform mixing; last iterate replaces averaging. (2): Needs smoothness and a stationary start; Euclidean geometry only.

Abbr: k=α/(α−1), S=(σR/ε)k, W=256LR2/ε+64⋅256kS; G bounds stochastic-gradient norms. τp,β are the scale and exponent of (1+t/τp)−β. τTV(δ) is the uniform total-variation mixing time at tolerance δ. polylog denotes unspecified logarithmic factors in the cited guarantee, including randomized batching costs. Budgets count all gradient calls and skipped Markov transitions; Ω denotes a necessary budget, O a sufficient budget.

Duchi, John C., Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. 2012. Ergodic Mirror Descent. https://doi.org/10.48550/arXiv.1105.4681.
LongTails: AcceleratedHeavyTailedMarkovConvex.lean. n.d. Lean convergence theorem and oracle budget in the LongTails repository. https://github.com/k3nfalt/longtails/blob/main/LongTails/Theorems/AcceleratedHeavyTailedMarkovConvex.lean.
Solodkin, Vladimir, Andrew Veprikov, and Aleksandr Beznosikov. 2025. Methods for Optimization Problems with Markovian Stochasticity and Non-Euclidean Geometry. https://doi.org/10.48550/arXiv.2408.01848.

Lean setup