PaperlayerView exact revision on arXiv

Source-linked AI summary

Markov Chain Convergence in Kernel-Induced Geometry

Oleksii Kachaiev, Luc Brogat-Motte, Silvia Villa, Lorenzo Rosasco

arXiv:2610.13916v1math.PRstat.ML

TL;DR

For general Markov chains, convergence of empirical occupation measures to a deterministic limit is not automatic, and finite-trajectory error matters in sampling. The paper proves high-probability MMD bounds and applies the framework to KRR for one-step prediction, obtaining source–capacity learning rates.

  • Problem

    For general Markov chains, convergence of empirical occupation measures to a deterministic limiting measure is not automatic, although finite-trajectory discrepancy matters in sampling.

    Source: §1 · pp. 1–2

  • Method

    The paper bounds occupation-measure convergence in MMD under spectral-gap and relaxation conditions, then uses this framework in a KRR analysis of one-step prediction.

    Source: §5 · p. 27

  • Results

    The KRR excess-risk rate is ≲ T^{-2r/(2r+p)}, matching the classical source–capacity exponent for i.i.d. KRR under the stated conditions.

    Source: §1 · p. 3, §5 · p. 28

  • Takeaways & Limitations

    The KRR analysis links statistical learning rates to convergence of the occupation measure in a regularization-dependent MMD geometry.

    Source: §5 · p. 27

    The analysis assumes bounded feature maps and innovations; replacing these with suitable moment or tail conditions remains open.

    Source: §5 · p. 28

Abstract

from arXiv · show

We study the convergence of Markov chains in the geometry induced by Hilbertian embeddings associated with positive definite kernels, also called Maximum Mean Discrepancy (MMD). Under a contraction assumption in the kernel-induced geometry, and a standard spectral gap assumption, we establish non-asymptotic, high-probability bounds for the convergence of the empirical occupation measure to the invariant measure. The obtained bounds separate the roles of the two conditions: the spectral gap determines the effective sample size in the leading term, while the kernel contraction enters only through a linear correction. As an application, we study one-step prediction of dynamical systems from a single trajectory, deriving fast learning rates for a nonlinear least-squares estimator. The rates highlight the interplay between mixing properties in the kernel-induced geometry and the classical source and capacity conditions used in the analysis of least-squares.

1 Introduction

The introduction frames convergence of empirical occupation measures as a finite-trajectory problem and develops MMD bounds for Markov chains. It also presents a kernel-ridge-regression application to one-step prediction, with rates tied to source and capacity conditions.

1 Introduction

  • The empirical occupation measure records time spent in measurable sets, and its convergence to a deterministic limit is not automatic for general Markov chains.Quantifying its discrepancy from the invariant measure makes finite-trajectory sampling error explicit.Source: §1 · pp. 1–2
  • The paper uses integral probability metrics and specializes to MMD, obtained from the unit ball of an RKHS and a positive-definite kernel.The feature-map formulation also applies to measurable maps into a separable Hilbert space when the required integrability holds.Source: §1 · p. 2
  • Earlier high-probability MMD bounds address independent observations or dependent sequences under weak-dependence, φ-mixing, or β-mixing assumptions.The introduction positions the Markov-chain result alongside these existing settings.Source: §1 · p. 2
  • Under an absolute L2(π) spectral gap and uniform MMD relaxation, the occupation-measure bound’s leading term depends on the spectral gap and feature-map second moment, while relaxation constants enter through a T^-1 term.The bound is non-asymptotic and holds with high probability; it is also extended to certain absolutely continuous initial laws without changing the leading term.Source: §1 · pp. 2–3
  • KRR stability is controlled by occupation-measure convergence in a regularization-dependent MMD induced by preconditioned covariance operators.The paper obtains relaxation bounds in this λ-dependent geometry from contraction in a fixed Hilbert scale associated with K(x, y) = k(x, y)^2.Source: §1 · p. 3
  • The KRR learning guarantee achieves the classical source–capacity rate for stationary trajectories, with explicit chain dependence in finite-sample bounds.The source exponent is r ∈ [1/2, 1], and the capacity exponent p ∈ (0, 1) is characterized by N(λ) ≲ λ^-p.Source: §1 · p. 3

2 Background and preliminaries

This section introduces Markov operators and integral probability metrics, then explains how contraction and spectral-gap assumptions act in different geometries. It also identifies limits on transferring contraction or interpreting an L2(π) spectral gap as contraction between measures.

Integral probability metrics

  • An integral probability metric is generated by a class of test functions, and choosing that class determines the geometry used to compare probability measures.The RKHS unit-ball choice gives the maximum mean discrepancy (MMD).Source: §2 · pp. 4–5

Markov operators

  • A Markov operator acts on observables through the transition kernel, and invariance means that applying the operator leaves π unchanged.The section also defines stationarity by X0 ∼ π.Source: §2 · pp. 4, 6

Contraction and duality

  • Strict contraction on a centered function space yields one-step contraction in its dual IPM, including contraction toward π when π is invariant.The contraction is on the complement of the fixed-point space.Source: §2 · p. 6

Comparison of IPMs

  • Comparing two IPMs can transfer uniform geometric convergence, but does not by itself transfer one-step contraction.The resulting bound may involve the stronger IPM.Source: §2 · p. 7

Spectral gap

  • An absolute L2(π) spectral gap controls decay on centered functions, but its induced measure geometry is restricted to measures with L2(π) densities.That geometry generally excludes Dirac measures and is unsuitable for measuring convergence from arbitrary initializations.Source: §2 · pp. 7–8

Hilbert-valued extension

  • The spectral gap on centered scalar L2(π) functions is preserved when the Markov operator is extended to the corresponding Hilbert-valued Bochner space.The extension acts as the tensor product of the centered operator with the identity on the Hilbert space.Source: §2 · p. 8

3 Convergence of occupation measure

This section develops high-probability convergence bounds for Markov-chain occupation measures in MMD geometry and examines conditions for geometric MMD relaxation, including transfer from stronger metrics and contraction directly in kernel-induced Hilbert spaces.

3.1 Uniform relaxation in MMD

  • Uniform geometric MMD relaxation is the section’s central geometric assumption; when the mean embedding is injective, it also ensures uniqueness of the invariant measure.Uniformly bounded feature maps give C=2κ, and one-step contraction toward the invariant measure implies the relaxation assumption.Source: §3.1 · p. 10

3.2 Main results on convergence rate

  • Under stationarity, an absolute L2(π) spectral gap and uniform geometric MMD relaxation yield a high-probability occupation-measure bound whose leading variance term reflects effective sample size and whose contraction-dependent correction is linear in T^-1.At the variance level, a trajectory of length T behaves like Teff independent observations; the leading term can use the centered feature-map norm, which is translation invariant.Source: §3.2 · pp. 10–11
  • The bound has no explicit dimension dependence; dimension enters through the feature-map second moment, and the Hilbertian concentration argument avoids the covering-number prefactor of the cited W1 bound.For the illustrative identity feature map on Rd with π=N(0,Id), the covariance operator is Id.Source: §3.2 · pp. 12–13
  • For a Markov process with ν ≪ π and dν/dπ ∈ Lp(π), p ∈ (1, ∞], and q = p/(p−1), the non-stationary initial-distribution effect appears only at order T^-1; the leading T^-1/2 term remains unchanged.Source: §3.2 · p. 13
  • Without a spectral gap, uniform geometric MMD relaxation alone gives a high-probability bound for arbitrary initial distributions, with leading scale τθ and applicability after any fixed burn-in.Compared with the stationary spectral-gap result, τθ enters the leading term rather than only the T^-1 correction.Source: §3.2 · pp. 13–14
  • The no-gap bound implies almost-sure MMD convergence; on compact X with a continuous characteristic kernel, it also implies weak convergence.The latter follows because MMD metrizes weak convergence under those additional conditions.Source: §3.2 · p. 14

3.3 Sufficient conditions through metric comparison

  • Uniform ergodicity in total variation implies uniform geometric MMD relaxation for uniformly bounded feature maps, with the same geometric rate.The relaxation constant is C=2κCTV.Source: §3.3 · p. 14
  • For the deterministic map Tq(x)=qx on [0,1], convergence to δ0 is geometric in Gaussian-kernel MMD even though total-variation distance remains 1 for every x>0.The MMD distance is bounded by Lip(ϕ)qn.Source: §3.3 · p. 15
  • A β-Hölder feature map transfers one-step metric contraction at rate q into Assumption 3.2 with contraction factor q^β.For Lipschitz feature maps, the factor is q.Source: §3.3 · p. 15
  • The Cantor autoregression contracts uniformly in W1 and hence in MMD, yet its finite-step laws remain mutually singular with the invariant Cantor distribution, giving total-variation distance 1.The invariant distribution is atomless, while each finite-step transition law has finite support.Source: §3.3 · p. 16

3.4 Operator contraction in kernel-induced spaces

  • Under Hilbert-scale contraction, a bounded pointwise realization and Markov-operator contraction on a power space imply uniform geometric relaxation in MMD for every initial law.The assumption requires the power space to admit a measurable pointwise realization and be invariant under the Markov operator.Source: §3.4 · pp. 18–19
  • Contraction in E−α for fixed α > 0 does not alone imply an absolute L2(π) spectral gap; a uniform contraction bound along αn ↓ 0 recovers one when Lϕ is injective.At α = 0, the condition is precisely the usual absolute L2(π) spectral-gap condition when G = L2_0(π).Source: §3.4 · p. 20
  • If the Markov and centered feature operators commute, an absolute L2(π) spectral gap supplies a sufficient route to Hilbert-scale contraction, subject to pointwise realization conditions.The corollary specifies the contraction constant from the L2 gap and requires the Markov operator to preserve the chosen realization.Source: §3.4 · p. 20
  • For noisy expanding maps on the torus, the expansion factor affects contraction in the smoother geometry but not the L2 spectral gap; noise must offset that amplification for one-step smoother-space contraction.For noisy rotations, contraction is determined entirely by the noise; under the stated conditions, both examples yield the geometric MMD relaxation of Proposition 3.13.Source: §3.4 · p. 21

4 Application to statistical learning of Markov chains

The section applies occupation-measure convergence in kernel-induced geometry to one-step prediction from a single Markov-chain trajectory, using kernel ridge regression (KRR). Under source and polynomial eigenvalue-decay conditions, balancing bias and stochastic error gives the classical source–capacity rate for i.i.d. KRR, with chain properties affecting finite-sample performance.

4 Application to statistical learning of Markov chains

  • The application learns the one-step prediction function from a single trajectory, with KRR stability controlled by occupation-measure convergence in a regularization-dependent MMD.This links the learning rate to convergence properties of the underlying chain.Source: §4 · p. 22

4.1 Regularized least squares

  • The regularized least-squares estimator is formed in an RKHS using a kernel feature map, with a unique minimizer and a closed-form representation.The section also introduces population-level regularized quantities for the analysis.Source: §4.1 · p. 23

4.2 Learning guarantees

  • Stationarity and an absolute L2(π) spectral gap control trajectory dependence, while Hilbert-scale contraction controls the KRR stability term; source and eigenvalue-decay conditions are classical learning assumptions.The contraction constants are induced by the unregularized covariance feature and do not depend on λ.Source: §4.2 · pp. 24–25
  • Theorem 4.4 gives a probability-at-least-1−δ guarantee for the estimator with its specified regularization choice, provided T is large enough for condition (167).The guarantee is stated up to logarithmic factors in 1/δ.Source: §4.2 · p. 25
  • The proof separates estimation error into stability, regularization bias, and stochastic terms; Hilbert-scale contraction controls stability through a uniform MMD relaxation bound.The proof combines this stability control with martingale concentration for the stochastic term.Source: §4.2 · p. 26
  • Balancing regularization bias and stochastic error under polynomial effective-dimension growth yields the classical source–capacity rate for i.i.d. KRR.The regularization choice is λ_T ≍ T^−1/(2r+p), where r is the source exponent and p the capacity exponent.Source: §4.2 · p. 27

5 Conclusion

The conclusion presents a high-probability occupation-measure bound in MMD geometry under an absolute L2(π) spectral gap and uniform MMD relaxation. It then applies the framework to single-trajectory KRR and identifies extensions that remain open.

5 Conclusion

  • Under an absolute L2(π) spectral gap and uniform MMD relaxation, the paper obtains a non-asymptotic high-probability occupation-measure bound with a central-limit-scale leading term.The result separates the usual relaxation-time contribution from that of the kernel-induced geometry and does not require reversibility.Source: §5 · p. 27
  • For single-trajectory one-step prediction, KRR under a source condition and polynomial covariance eigenvalue decay yields the stated fast learning rate, up to logarithmic factors.The conclusion gives the rate and regularization choice in equation (177).Source: §5 · p. 28
  • Open directions include replacing bounded feature and innovation assumptions with moment or tail conditions, and extending the analysis to misspecified models and more general initial distributions.The conclusion also identifies sharper lower-order concentration bounds and adaptive kernel or regularization selection as questions for further work.Source: §5 · p. 28

A Proofs

Appendix A gathers proofs for the occupation-measure bounds and learning guarantees, organizing auxiliary results before the main arguments.

A Proofs

  • The appendix first collects auxiliary results used in the proofs, then establishes the occupation-measure bound under stationarity.Source: A Proofs · p. 31
  • The occupation-measure argument is extended to non-stationary initial distributions and then treated without a spectral gap.Source: A Proofs · p. 31
  • The appendix concludes with proofs of the learning error bounds and the resulting sample rate.Source: A Proofs · p. 31

A.1 Auxiliary results

The auxiliary results include Bernstein inequalities for stationary and nonstationary Markov chains and a localized Hilbert-valued martingale inequality used in the proofs.

A.1 Auxiliary results

  • The stationary Bernstein inequality assumes a positive absolute L2(π) spectral gap and bounded, mean-zero functions along a chain initialized at π.Source: §A.1 · p. 31
  • The nonstationary Bernstein inequality allows an arbitrary initial distribution, and neither theorem requires reversibility or a separate irreducibility assumption.Dependence is controlled by the absolute operator norm ρ.Source: §A.1 · pp. 31–32
  • A localized Pinelis–Bernstein inequality is applied to predictably truncated martingale increments to obtain the stated concentration bound.The appendix identifies the resulting process as a martingale with bounded increments.Source: §A.1 · p. 32

A.2 Occupation measure convergence under stationarity

The stationary convergence argument uses a Poisson equation to decompose the occupation-measure error into a martingale term and a boundary term. Geometric decay in the function space yields an MMD contraction bound, while Hilbert-valued concentration controls the martingale.

A.2 Occupation measure convergence under stationarity

  • The proof reduces occupation-measure concentration to a Hilbert-valued additive functional, decomposed into a martingale term and a bounded boundary term.A Hilbert-valued Bernstein inequality controls the martingale; the boundary term vanishes at order T^-1.Source: §A.2 · p. 33
  • Geometric decay of P^k on centered functions makes I − P invertible on B0 and supplies a solution to the associated Poisson equation.The solution is given by the convergent series of iterates, with norm bounded by C/(1 − ρ) times the norm of the centered function.Source: §A.2 · p. 33
  • The Markov evolution satisfies MMDϕ(P^n(x, ·), π) ≤ Cθ^n, giving geometric convergence to π in the kernel-induced geometry.The same bound is written as ∥(P^nϕ)(x) − πϕ∥H ≤ Cθ^n.Source: §A.2 · p. 34

A.3 Extension to non-stationary initial distributions

For non-stationary initial distributions, the proof retains the Poisson-equation and martingale bounds, modifying the concentration step for predictable quadratic variation. Without a spectral gap, a uniform geometric bound on iterates still supports an occupation-measure convergence result.

A.3 Extension to non-stationary initial distributions

  • The non-stationary extension retains the Poisson solution, martingale decomposition, increment bounds, and boundary term; only predictable-quadratic-variation concentration changes.The modification centers Vu and applies a concentration inequality around Tπ(Vu).Source: §A.3 · p. 36

A.4 Occupation measure convergence without a spectral gap

  • Without a spectral gap, uniform geometric decay of centered iterates yields a bounded Poisson solution and a martingale-difference decomposition for the occupation sum.The proof applies a martingale concentration inequality and bounds the boundary term by 2τθ.Source: §A.4 · p. 37

A.5 Learning guarantees

The learning analysis connects empirical inverse-problem stability to occupation-measure convergence in a preconditioned kernel geometry. Under the source and effective-dimension conditions, balancing regularization bias and stochastic error gives a fast rate, while the correction term is lower order.

A.5 Learning guarantees

  • Empirical inverse-problem stability is governed directly by occupation-measure convergence to π in the preconditioned kernel geometry MMDΦλ.The proof bounds the stability term by applying the occupation-measure convergence result to the preconditioned feature map.Source: §A.5 · pp. 38–39
  • The stochastic correction is described as proof-strategy-specific and likely non-sharp; under the stated regularization schedule, it remains asymptotically dominated.For N(λ) ≲ λ^-p, the correction is of order T^-3/4 λ^-(p+1)/4.Source: §A.5 · p. 41
  • Balancing regularization bias and stochastic error gives the learning rate T^{-r/(2r+p)}, and all terms in the bound are at most this order.The stated conditions include r ≥ 1/2 and polynomial effective-dimension growth; the stability condition is also verified, including at r = 1/2 with a sufficiently large regularization constant.Source: §A.5 · pp. 41–42

B Fourier analysis of randomly perturbed torus maps

The appendix gives a Fourier representation for randomly perturbed torus maps and uses it to establish kernel-space contraction conditions. For noisy rotations, the relevant embedding condition is 2sα > d, with α = 1 permitted when s > d/2.

B Fourier analysis of randomly perturbed torus maps

  • The appendix presents a common Fourier representation for two examples and the covariance kernel used in Appendix B.5.Complex Fourier notation is used for convenience; the constructions can also use real sine and cosine coordinates.Source: B Fourier analysis of randomly… · p. 42, §B.1 · p. 42

B.1 Hilbert-scale space

  • The centered kernel’s RKHS is Eα, and including or omitting the constant mode leaves the centered Hilbert scale and probability-measure MMD unchanged.The kernel and canonical feature map are given in the Hilbert-scale construction.Source: §B.1 · pp. 42–43

B.2 Contraction formula

  • When Rα < 1, the Fourier contraction formula gives bounded action of P on Eα and verifies Assumption 3.12.The operator norm on Eα equals Rα.Source: §B.2 · p. 44

B.3 Noisy rotations

  • For noisy rotations, the embedding series is finite exactly when 2sα > d; if s > d/2, α = 1 is permitted and the feature map satisfies the contraction bound.The pointwise-preservation requirement is met because P is Feller, π has full support, and Eα consists of continuous functions when sα > d/2.Source: §B.3 · p. 45

B.4 Noisy expanding maps

The appendix analyzes noisy expanding maps through a drift–noise factorization, making one-step contraction conditions explicit and distinguishing them from contraction of iterates.

Hilbert-scale condition

  • The embedding constant is finite exactly when sα > 1/2, and under the stated condition the contraction factor is ρα = ℓ^{sα}e^{-2π²η²}.This verifies Assumption 3.12 and yields the claimed MMD bound by Proposition 3.13.Source: §B.4 · p. 45

One-step versus iterated contraction

  • For every η > 0, the iterated Fourier action tends to zero even when ρα ≥ 1, so the sufficient one-step threshold is not necessary for contraction of iterates.When sα > 1/2, the same argument also gives the stated MMD bound.Source: §B.4 · p. 45

Drift–noise factorization

  • The Markov operator factors into deterministic and noise operators, whose bounded actions on the centered space yield a product bound on its contraction norm.Both factors must preserve the centered space and act boundedly there.Source: §B.4 · p. 46

Conditions and scope

  • The factorization bound requires separate preservation of the centered space, and boundedness of UF on a smooth function space requires suitable regularity of F.Invariance of π under P alone does not ensure either factor preserves the centered space; duality gives the same bounds on E−α.Source: §B.4 · p. 46

Noisy expanding map

  • For a noisy expanding map, the sharp contraction factors are ℓ^{sα} for deterministic frequency amplification and e^{-2π²η²} for noise attenuation.Their product gives the contraction bound; for a translation, ℓ=1 and the deterministic factor is an isometry.Source: §B.4 · p. 46

B.5 Statistical learning assumptions for a noisy doubling map

For a noisy doubling map, the appendix verifies stationarity, spectral-gap, kernel, and regression conditions needed to apply the least-squares learning theorem.

Noise distribution and stationarity

  • The chain is the modulo-one noisy doubling map, initialized at the uniform invariant distribution; that distribution is unique and has finite second moment.The transition kernel also satisfies P(x, ·) ≥ (1/3)π.Source: §B.5 · pp. 46–47

The L2(π) spectral gap

  • The Fourier-based analysis establishes an L2(π) spectral gap for the example with wrapped Gaussian noise.The supplied passage identifies the spectral-gap calculation but does not state its numerical value.Source: §B.5 · p. 47

Bounded features and covariance spectrum

  • The periodic kernel has bounded continuous features and polynomial eigenvalue decay with B = 5, b = 2, and p = 1/2.Its Fourier series converges absolutely and uniformly, and the resulting RKHS is separable.Source: §B.5 · pp. 47–48

The covariance kernel

  • The covariance kernel's nonzero eigenvalues are c_m, and its centered version verifies Assumption 3.12 with a supremum attained at m = 1.For every x, the corresponding norm satisfies ∥δ_x − π∥_{−α} = κα.Source: §B.5 · p. 49

The regression function and innovations

  • The prediction innovation satisfies the bounded-innovation assumption with M = 1 and σ² = 1/4.These constants describe prediction innovations, not the Gaussian perturbation scale η.Source: §B.5 · pp. 49–50

Well-specifiedness and the source condition

  • The regression function is well specified in the RKHS, and the source condition holds for every r ∈ [1/2, 1].The series representation converges in H and its pointwise realization agrees with the regression function.Source: §B.5 · p. 50

Verification of learning assumptions

  • Together, the example's assumptions for Theorem 4.4 hold for every α ∈ (1/2, 1] and r ∈ [1/2, 1].The constants κ, κα, and G⋆ are finite.Source: §B.5 · p. 50
Loading 2610.13916v1…