← All setups

Markov Quadratic Interpolation

Descriptions may be stale. Consult the linked Lean sources.

Markov Quadratic Interpolation

We consider minimizing a convex quadratic f:E→R on a separable real Hilbert space E. It is the stationary average of quadratic losses sharing a minimizer x⋆, with positive semidefinite Hessians bounded by L>0. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R≥0. At query x, the oracle returns HZ(x−x⋆), where HZ is the Hessian indexed by a finite-state Markov chain Z. The chain starts arbitrarily and its transition law dominates α times its invariant law, with 0<α≤1. For ε>0, the goal is E[f(x¯)−f(x⋆)]≤ε, averaging over the chain and independent algorithm randomness for the output x¯∈E.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives only E, L, x0, and α; the radius R and tolerance ε may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Interpolating quadratic model). There exist a finite index set I={1,…,m} with m≥1, a probability distribution π on I, bounded linear operators Hi:E→E, and a point x⋆∈E such that Hi∗=Hi(i∈I),0≤⟨v,Hiv⟩≤L∥v∥2(i∈I, v∈E),∥x0−x⋆∥≤R. Here Hi∗ denotes the Hilbert space adjoint. The population objective satisfies f(x)−f(x⋆)=12EI∼π[⟨x−x⋆,HI(x−x⋆)⟩],x∈E. In particular, x⋆ is a global minimizer and every component gradient vanishes there.

Assumption 2 (Markov sampling and refresh). Let κ be a Markov transition kernel on I, and write πj=π({j}). Its invariant distribution and refresh condition satisfy EI∼π[κ(I,{j})]=πj(j∈I),κ(i,{j})≥απj(i,j∈I). The samples (Zk)k≥0 form a time-homogeneous Markov chain with transition kernel κ and arbitrary initial distribution μ on I. Algorithm randomness is independent of this chain.

Queries may be made at any point of E. At the kth call, starting with k=0, a query x receives the vector g(x,Zk)=HZk(x−x⋆). Thus successive calls use successive states of the same chain. The distributions π and μ, the kernel κ, the operators Hi, and the minimizer x⋆ are not supplied to the algorithm.

After the allotted oracle calls, the output x¯ must be measurable, its objective gap must be integrable, and it must satisfy E[f(x¯)−f(x⋆)]≤ε.

Results

On a real separable Hilbert space with its Borel measurable structure, let 0⪯Hi⪯LI be self-adjoint operators indexed by a finite state space, with f(x)−f(x⋆)=12∑iπi⟨x−x⋆,Hi(x−x⋆)⟩ and ∥x0−x⋆∥≤R. The oracle returns Hst(x−x⋆) along a Markov chain with stationary law π, arbitrary initial law, and κ(i,⋅)≥απ. Here L>0, R≥0, 0<α≤1, and ε>0. The target is ∫[f(x^)−f(x⋆)]dP≤ε; the setup imposes no algorithm or output-rule restriction.

Comparison for MarkovQuadraticInterpolation.
Result Oracle complexity Novelty Limitations
(1) MarkovQuadraticLastIterate (Ours) (⋆⋆) (review) O(1+LR2αε)
Last-iterate SGD, η=α/(104L).
(2) Derived bound: averaged SGD O(1+LR2αε)
η=1/L; same class, even without stationarity of π.
(1): Matches known rate; last iterate instead of averaging. No problem-class complexity gain. (1): Much larger proved constant; needs α in updates, whereas (2) needs it only for stopping; requires stationarity.
(3) Derived bound: thinned SGD using (Dereziński and Dong 2026), Thm. 3.1 O((1+LR2αε)log⁡(2+LR2ε))
Finite-dimensional restriction; skipped transitions included.
(1): Removes log⁡(2+LR2/ε) for last-iterate accuracy on the finite-dimensional overlap; uses every sample. (1): Larger proved constants; the reported cost crossover requires log⁡(LR2/ε)≳1015.
(4) (Even 2023), Thm. 5.6, interpolation O(Lμlog⁡(2+LR2ε))
Special case: E=Rd, Hi⪰μI, μ>0; arbitrary sampling order.
(1): Scope includes singular operators and infinite dimension. On overlap with LR2/ε≥1, lower-order cost when μR2≪αεlog⁡(2+LR2/ε); no uniform dominance. (1): Requires refresh and known α; for fixed μ,α>0, has ε−1 rather than logarithmic accuracy dependence.

Abbr: P: Markov path law; x⋆: common minimizer; L: component Hessian upper bound; R: initial-distance bound; α: refresh lower bound; μ: component strong-convexity lower bound; η: step size. Costs count component-gradient oracle calls, including calls at discarded transitions.

Dereziński, Michał, and Xiaoyu Dong. 2026. How AI Settled the Complexity of the Oldest SGD Algorithm. https://doi.org/10.48550/arXiv.2606.29593.
Even, Mathieu. 2023. “Stochastic Gradient Descent Under Markovian Sampling Schemes.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 9412–39. https://proceedings.mlr.press/v202/even23a.html.

Lean setup