← 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:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where L>0, and a given point x0∈E is within distance R≥0 of a global minimizer x⋆. At query x, the oracle returns g(x,Zk), where (Zk)k≥0 is a stationary, polynomially mixing Markov chain. Under its stationary law, g is unbiased and its centered α-moment is at most σα, with 1<α≤2 and σ≥0. For ε>0, the goal is a measurable output x¯ with integrable objective gap and E[f(x¯)−f(x⋆)]≤ε, averaging over oracle and independent algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. Let Ω be a measurable sample space, and let τ>0 and β>0 be the mixing parameters. The algorithm receives E, Ω, L, R, σ, α, τ, β, ε, and x0; the objective and the oracle’s sampling law are accessed through oracle replies.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is 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∥.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stationary Markov sampling and mixing). The samples form a time-homogeneous Markov chain on Ω with transition probability kernel κ and initial distribution π, where π is a probability measure. It is invariant: for every measurable A⊆Ω, EZ∼π[κ(Z,A)]=π(A). For each integer t≥0, define the total-variation distance using the convention dt(z)=supA⊆Ωmeasurable|κt(z,A)−π(A)|, where κt is the t-step transition kernel and κ0(z,⋅) is the point mass at z. The function dt is integrable under π and satisfies EZ∼π[dt(Z)]≤(1+tτ)−β,t=0,1,2,….

Assumption 4 (Stationary oracle moments). The map g:E×Ω→E is jointly measurable. For every fixed x∈E, 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)∥α]≤σα. These moment conditions are taken under the stationary law at each fixed query point.

Queries may be made at any point of E. The oracle returns g(xk,Zk) on call k, starting at k=0 and using consecutive states of the same chain. The query xk may depend on previous replies and on algorithm randomness, which is independent of the chain. Any calls whose replies are discarded still count toward the oracle-call budget.

After the allotted calls, the output x¯∈E 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 Markov chain and the independent algorithm randomness.

Results

On a second-countable real Hilbert space with its Borel measurable structure, f is convex and differentiable with L-Lipschitz gradient and a minimizer x⋆ satisfying ∥x0−x⋆∥≤R. The jointly measurable oracle satisfies ∫g(x,z)dπ(z)=∇f(x) and ∫∥g(x,z)−∇f(x)∥αdπ(z)≤σα, with the corresponding integrability assumptions. Samples follow a stationary Markov chain with kernel κ, invariant probability π, and integrable dt(z)=TV(κt(z,⋅),π) satisfying ∫dtdπ≤(1+t/τ)−β for every lag. Here L,τ,β,ε>0, R,σ≥0, and 1<α≤2. Target: measurable output with integrable gap and ∫[f(output(ω))−f(x⋆)]dP(ω)≤ε, where P is the stationary path law.

Heavy-tailed Markov smooth convex optimization under HeavyTailedMarkovSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedHeavyTailedMarkovConvex (Ours) (⋆⋆) (review) O((1+A+B)
⋅[1+τ(256A+64B)1/β]). All calls, including skipped samples; deterministic budget.
(2) Accelerated mirror descent with MLMC (Solodkin et al. 2025), Thm. 2, Cor. 2 O([1+A+τmixσ2R2ε2]
⋅polylog(e+A+τmixσ2R2ε2)) expected calls, including batches. Special case: finite-dimensional ball, ∥g−∇f∥≤σ, supzdt(z)≤2−t/τmix, τmix≥1.
(1): Scope: stationary α-moments, including infinite variance, replace bounded noise; π-averaged polynomial mixing replaces uniform geometric mixing. (1): Hilbert geometry only. On the geometric overlap, pays τmix on the deterministic term, up to logarithms; noise order matches up to logarithms.
(3) Ergodic mirror descent (Duchi et al. 2012), Thm. 1, (12); derived bound O(1+Q2[1+τQ1/β]) calls, fixed β. Special case: finite-dimensional ball; convex sample losses with ∥g∥≤G; uniform dt≤(1+t/τ)−β. (1): Scope: no bounded-gradient requirement; averaged rather than uniform mixing. Output: last accelerated iterate instead of averaging. (1): Needs smoothness and stationary start. For α=2, σ≍G, A≤Q2, Q→∞, fixed τ,β: O(τQ2+2/β) versus O(τQ2+1/β).
(4) Accelerated stochastic proximal subgradient (He et al. 2026), Thm. 2(i), (7a) O(1+A+(σR/ε)α/(α−1)) calls, fixed α. Special case: i.i.d., finite-dimensional ball, h=ιB(x0,R), 0<ε<1. (1): Scope: stationary Markov dependence. Matches known i.i.d. rate when τ permits skip length m=1, for fixed α. (1): Requires clipping; (4) does not.

Abbr: A=LR2/ε; B=(256σR/ε)α/(α−1); Q=GR/ε; G bounds sample gradients. TV(μ,ν)=supS measurable|μ(S)−ν(S)|. Geometric overlap: α=2, ∥g−∇f∥≤σ, supzdt(z)≤2−t/τmix, τmix≥1; admissible polynomial parameters are β=1+log⁡(e+A+σ2R2/ε2) and τ=βτmix/log⁡2. polylog retains the unspecified logarithmic factors in Cor. 2. Fixed-exponent bounds need not have uniform constants as α↓1 or β↓0. ι denotes a convex-set indicator.

Duchi, John C., Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. 2012. Ergodic Mirror Descent. https://doi.org/10.48550/arXiv.1105.4681.
He, Chuan, Bowen Li, and Zhaosong Lu. 2026. Accelerated Stochastic First-Order Method for Convex Optimization Under Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2510.11676.
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