← All setups

Convex Minimization with Polynomially Mixing Subgradients

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On the closed radius-R ball in Rd, f is convex and attains its minimum f∗. Each call returns g(x,Zt) from one stationary real stream with past–future absolute regularity coefficient at most (1+t/τ)−β at lag t. The jointly measurable replies have a stationary mean supporting f on the ball and satisfy E∥g(x,Z0)∥p≤Gp at every query point. Here d≥1, R,G>0, 1<p≤2, β>0, τ≥1, 0<ε≤GR/8, and 0<δ≤1/32. The target is a measurable feasible x^ with Pr(f(x^)−f∗≤ε)≥1−δ.

High-confidence subgradient complexity under polynomial mixing.
Result Oracle complexity Novelty Limitations
(1) PolynomialMixingConfidenceUpperBound (Ours) (⋆⋆⋆) (review)

Upper bound (sufficient calls)

O(τL2[(224X)k+(322L2/δ)1/β])

(2) PolynomialMixingConfidenceLowerBound (Ours) (⋆⋆⋆) (review)

Lower bound (necessary calls)

Ω(1+τ1+β[(X/8)kL+(16δ)−1/β])

(3) Derived bound: Berbee blocking and clipped SGD (Liu and Zhou 2023, Thm. 3)

Sufficient calls, including skipped samples

Op,β(τ(XL)kδ−1/β)

(1): Accuracy and confidence costs add. At p=2, β=1, O(τX4L4/δ) becomes O(τL2[X4+L2/δ]), a polynomial saving as X and 1/δ grow. (1): The certified accuracy factor 224k can delay the saving.
(4) Online projected gradient descent (Agarwal and Duchi 2013, Thm. 3)

Sufficient calls

Oβ(τX2+1/βδ−1/βlog⁡(τX/δ))

(1): Allows unbounded replies. On the bounded convex Lipschitz sample-loss overlap at p=2, saves calls when δ−1≫XL2β and δ−1 grows polynomially in X. (1): Requires past–future mixing where (4) needs single-time mixing against the past. At fixed confidence and τ,β, the accuracy exponent rises from 2+1/β to 2+2/β.
(5) Ergodic mirror descent (Duchi et al. 2012, Thm. 2)

Sufficient calls

Oβ(τX2+1/βlog⁡(τX1/β/δ))

(1): Allows heavy-tailed replies and dispenses with uniform conditional mixing. (5) assumes convex Lipschitz sample losses and a uniform conditional total-variation envelope. (1): On the bounded, uniformly mixing overlap at p=2, the accuracy exponent rises by 1/β and confidence costs a power of 1/δ instead of a logarithm.

Abbr: X=GR/ε, L=log⁡(8/δ), a=p/(p−1), k=a(1+1/β). In (6), Lf is the gradient Lipschitz constant, σ the centered moment scale, and H=((σR/ε)p/24p−1)1/(p−1). In (7), m is the geometric mixing scale, n the transition count, and σp the moment scale. Order-symbol subscripts indicate allowed constant dependence.

Table 1, continued.

Result Oracle complexity Novelty Limitations
(6) Expected-gap lower bound (LongTails 2026)

Necessary calls

Ω(1+(τ/β)H1+1/β) for H≥1, τH1/β≥β, 16≤LfR2/ε≤(σR/ε)a.

(2): The same accuracy exponent now carries L, and linear objectives force an additive Ωβ(τδ−1/β). For fixed p,β, (1), (2) differ by factors L and L2+2/β on the respective terms. (2), (6): Rates are not directly comparable. (6) targets expected error for smooth unconstrained objectives, centered moments and stationary average-TV mixing Markov chains.
(7) Quadratic lower bound (Sarkar et al. 2026, Thm. 4)

Necessary transitions at constant confidence

Ωp(m(σp2/ε)a/2) for m≥2, n≥8m, σp≥1.

(2): Quantifies polynomial confidence dependence for every admissible δ. (7) proves constant-probability failure for one-dimensional quadratics under uniform geometric mixing. (2), (7): Rates are not directly comparable. (7) starts the chain at a fixed state and measures quadratic objective error.

Abbr: X=GR/ε, L=log⁡(8/δ), a=p/(p−1), k=a(1+1/β). In (6), Lf is the gradient Lipschitz constant, σ the centered moment scale, and H=((σR/ε)p/24p−1)1/(p−1). In (7), m is the geometric mixing scale, n the transition count, and σp the moment scale. Order-symbol subscripts indicate allowed constant dependence.

Agarwal, Alekh, and John C. Duchi. 2013. “The Generalization Ability of Online Algorithms for Dependent Data.” IEEE Transactions on Information Theory 59 (1): 573–87. https://doi.org/10.1109/TIT.2012.2212414.
Duchi, John C., Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. 2012. Ergodic Mirror Descent. https://doi.org/10.48550/arXiv.1105.4681.
Liu, Zijian, and Zhengyuan Zhou. 2023. Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, in-Expectation Rate and Initial Distance Adaptation. https://doi.org/10.48550/arXiv.2303.12277.
LongTails: PolynomialMixingHeavyTailedConvexLowerBound. 2026. Lean theorem and necessary oracle budget. https://github.com/k3nfalt/longtails/blob/8f5916c359090fe5b4506d2d837cb10399da71b6/LongTails/Theorems/PolynomialMixingHeavyTailedConvexLowerBound.lean.
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