PaperlayerView exact revision on arXiv

Source-linked AI summary

Gaussian Approximation for Multivariate Martingale Sums from Uniformly Ergodic Markov Chains

Yixuan Zhang, Qiaomin Xie

arXiv:2609.09480v1math.PRcs.LGstat.ML

TL;DR

Multivariate higher-order Wasserstein Gaussian approximation lacks the IPM reductions available in simpler settings, limiting direct extension of existing Stein techniques. This paper develops antisymmetric Stein couplings and a refresh-then-maximal coupling for Markovian dependence, attaining the canonical O(n^-1/2) rate in the balanced-increment regime and for additive functionals.

  • Problem

    General multivariate Wp approximation for p≥2 lacks the IPM reductions that support existing Stein techniques, while Gaussian approximation for martingale differences is a missing ingredient in stochastic-algorithm analysis.

  • Method

    The analysis combines an Ornstein–Uhlenbeck relative-score formulation using antisymmetric Stein couplings with a refresh-then-maximal coupling tailored to Markovian dependence.

  • Results

    The main result attains the optimal O(n^-1/2) Gaussian approximation rate in the balanced-increment regime and yields the same rate for additive functionals of Markov chains.

  • Takeaways & Limitations

    The bound supplies the higher-order Wasserstein Gaussian approximation ingredient identified as missing for stochastic algorithms and extends the rate to additive functionals of Markov chains.

  • Takeaways & Limitations

    Optimal dimension dependence remains unclear even for sums of independent random vectors, and the bound's dimension dependence is partly implicit in the increment sizes.

Abstract

from arXiv · show

We develop Gaussian approximation bounds in higher-order Wasserstein distance $W_p$, $p\geq2$, for sums of multivariate martingale differences generated by a uniformly ergodic Markov chain. Under an $L^{(2+η)p}$-moment condition with $η>0$, we establish the explicit bound $$ O\left( p^3 \|A\|_4^2 + pd^{1/4}\|A\|_2^{1/2}\|A\|_4^2 \right) $$ where $A\in\mathbb{R}^n$ collects the $L^{(2+η)p}$-sizes of the $n$ individual martingale increments. In the balanced-increment regime where the individual increments have comparable sizes of order $n^{-1/2}$, it yields the first optimal $O(n^{-1/2})$ Gaussian approximation rate for fixed $p$ and $d$. Consequently, we also obtain the first optimal $O(n^{-1/2})$ $W_p$ Gaussian approximation rate for multivariate additive functionals of uniformly ergodic Markov chains. Our analysis develops two techniques for addressing the interplay between higher-order Wasserstein distance and temporal dependence. First, building on the Ornstein--Uhlenbeck relative-score approach of Fang and Koike (2023), we formulate the bound in terms of antisymmetric Stein couplings while retaining the conditional tensor structure. Second, we develop a refresh-then-maximal coupling that combines an independent first-step resampling, which preserves the desired Stein identity, with a subsequent maximal coupling that provides effective control of the coupling increment. These tools may be useful more broadly for Gaussian approximation under temporal dependence.

1 Introduction

The paper studies higher-order Wp Gaussian approximation for multivariate martingale sums induced by Markov chains, addressing a gap in existing multivariate theory. It develops tensor-preserving Stein methods and a refresh-then-maximal coupling, obtaining optimal balanced-increment rates and corresponding additive-functional results.

  • Problem formulation: The paper represents centered Markov-chain additive functionals through a Poisson-equation martingale sum plus a telescoping boundary term.This reduces Gaussian approximation for additive functionals to approximation of the induced martingale sum, with separate boundary-term control.
  • Research gap: Higher-order Wp Gaussian approximation for multivariate Markov-chain-induced martingale differences was previously unavailable for p ≥2.Existing results were limited mainly to smooth metrics, lower Wasserstein orders, or general martingale sequences that do not exploit Markov structure.
  • Main consequences: The resulting bounds attain the optimal O(n^-1/2) rate for balanced increments and yield the first optimal O(n^-1/2) Wp rate for additive functionals under fixed p and d.The additive-functional result improves a previously available O(n^-1/4) rate under weaker geometric-ergodicity conditions.
  • Technical approach: The method retains conditional tensor structure in an Ornstein–Uhlenbeck relative-score argument formulated through antisymmetric Stein couplings.This tensor-level formulation is used to derive sharper estimates in the subsequent Markovian analysis.
  • Technical approach: A refresh-then-maximal coupling combines independent first-transition resampling with blockwise maximal coupling to preserve the Stein identity and control coupling increments.The maximal-coupling stage yields a geometrically decaying meeting time.

2 Problem Setup

The setup assumes a stationary uniformly ergodic Markov chain and a centered function solving a Poisson equation. It defines martingale differences, weighted sums, and the higher-order Wasserstein approximation target, while noting extensions beyond stationary initialization.

  • Markov-chain assumptions: The chain is stationary, uniformly ergodic, and has transition kernel P and stationary distribution π.Expectations and covariances are taken under π unless stated otherwise.
  • Markov-chain assumptions: Uniform ergodicity supplies quantitative stability for stochastic systems driven by Markovian dynamics.The paper cites applications including inventory control, stochastic approximation, and reinforcement learning.
  • Poisson equation: For centered h ∈ L^q(π), with q = (2+η)p, the Poisson equation g − Pg = h has a solution g ∈ L^q(π).The solution follows from convergence of iterated transition operators under the stated ergodicity assumption.
  • Approximation target: The Markov property makes the constructed increments martingale differences, and the objective is to bound L(Sn) against a Gaussian in Wp.The framework allows deterministic matrix weights Mi, with Mi = Id recovering the unweighted sum.
  • Initialization: The analysis is presented under stationary initialization but can extend to suitable arbitrary initial distributions by maximal coupling.The extension requires appropriate moment conditions.

3 Main Results

The paper establishes higher-order Wp Gaussian approximation bounds for multivariate martingale sums generated by uniformly ergodic Markov chains, with explicit dependence on increment sizes, p, and d. In balanced regimes, the result gives optimal n^-1/2 rates and extends to additive functionals.

  • Main theorem: The bound is expressed explicitly through the Lq-sizes of the weighted martingale increments while retaining dependence on p and d.Here q=(2+η)p and A records the increment sizes.
  • Main theorem: Theorem 1 gives the first multivariate Markov-chain martingale Gaussian approximation bound in Wp for p ≥2.The result is stated for weighted sums under the paper’s normalization and moment assumptions.
  • Comparison with existing work: The analysis addresses the absence of general IPM reductions for multivariate Wp when p ≥2.This blocks direct extension of techniques used for multivariate W1 and univariate higher-order Wasserstein distances.
  • Sample-size dependence: O(n^-1/2) is obtained for fixed p and d when balanced increments have comparable scales of order n^-1/2.This recovers the canonical rate and is optimal in general because independent sums are included.
  • Limitations: The paper does not claim optimal dependence on p, and the optimal dimension dependence remains unclear even for independent sums.Dimension also enters implicitly through the increment sizes in A.
  • Comparison with existing work: The result improves on prior multivariate Markov-chain Wp bounds that achieve only O(n^-1/4) under weaker geometric-ergodicity conditions.The paper identifies its O(n^-1/2) rate as the first optimal rate under an L(2+η)p-moment condition.

4 An Ornstein–Uhlenbeck Bound via Antisymmetric Stein Couplings

The paper combines an Ornstein–Uhlenbeck relative-score argument with antisymmetric Stein couplings and conditional tensor bounds. This formulation preserves cancellations needed for Markovian dependence while keeping moment requirements close to order 2p.

  • Score bound: The relative-score approach is formulated directly through antisymmetric Stein couplings and conditional tensors.The construction targets the Wp Gaussian approximation bound through the Ornstein–Uhlenbeck flow.
  • Score bound: The OU transport bound converts control of the relative score along the flow into a Wp Gaussian approximation bound.The score is controlled in Lp after introducing the smoothed variable Wt.
  • Stein couplings: Antisymmetric Stein couplings extend multivariate Stein couplings with an additional symmetry condition under swapping the coupled vectors and negating the auxiliary variable.The auxiliary variable G is separated from the coupling increment and need not be proportional to it.
  • Conditional tensors: Retaining conditional tensor structure allows positive and negative perturbation contributions to cancel before norms are taken.This avoids the stronger moment requirements arising from directly bounding conditional absolute moments.
  • Proof of Proposition 1: The proof uses truncation, a Gaussian shift formula, Hermite expansion, conditional Jensen’s inequality, and tower-property arguments to bound the relative score.The antisymmetric event structure supports the truncated Stein identity and subsequent score representation.

5 Refresh-Then-Maximal Coupling

The paper constructs a refresh-then-maximal coupling that simultaneously preserves the Stein identity, conditional exchangeability, prefix measurability, and geometric control of the coupling increment.

  • Construction: The coupling independently resamples the first transition, then uses symmetric blockwise maximal coupling for subsequent trajectories.The first step supplies the fresh-transition property, while the later coupling controls meeting times.
  • Coupling properties: The construction preserves prefix measurability at block boundaries, allowing the analysis to exploit the Markov chain’s mixing behavior.Classical global maximal couplings may use future trajectory information and therefore lack this property automatically.
  • Consequences: The constructed variables satisfy the antisymmetry and Stein-coupling identities required by the relative-score proposition.This enables the proof to apply the proposition and derive the Wp approximation theorem.
  • Consequences: The blockwise maximal stage yields a geometrically decaying meeting-time tail and sharp control of the coupling increment.The resulting estimates feed directly into the relative-score bound used for Gaussian approximation.
  • Coupling properties: The coupled suffixes are conditionally exchangeable given the observed prefix, and each has the correct Markov-chain marginal law.These properties establish the symmetry needed for the antisymmetric Stein coupling.

6 Completion of the Proof of Theorem 1

The proof combines conditional tensor estimates, coupling moment bounds, and the relative-score proposition to establish the Gaussian approximation bound for the normalized martingale sum.

  • Proof strategy: The proof applies the relative-score proposition after bounding the coupling’s operator discrepancies through tensor estimates.The three discrepancy terms are controlled separately before deriving the Wp bound.
  • Conclusion of proof: Substituting the resulting score estimate into the Wasserstein argument proves the stated bound for W = S_n.The final substitution completes Theorem 1.
  • Moment bounds: The moment analysis uses the L^(2+η)p assumption together with Hölder, Minkowski, Young convolution, and martingale orthogonality inequalities.These estimates control the coupled increments and conditional tensor fluctuations.
  • Moment bounds: The coupling supplies bounds for the coupled-coordinate and increment norms that are proportional to the individual increment sizes.For example, the proof records bounds of the form ∥Ξ_i∥_L2s ≤ 2a_i and ∥∆_i∥_L2s ≤ C a_i.
  • Conditional fluctuations: Conditional fluctuations are controlled using prefix measurability and the absolute-regularity decay of the stationary Markov chain.The argument combines mixing estimates with conditional Jensen and moment inequalities.

7 Conclusion

The paper develops higher-order Wasserstein Gaussian approximation for multivariate martingale sums from uniformly ergodic Markov chains and obtains the optimal balanced-increment rate.

  • Contributions: The theory covers higher-order Wp Gaussian approximation for multivariate martingale sums generated by uniformly ergodic Markov chains.The result tracks dependence on both the Wasserstein order p and dimension d.
  • Main result: O(n^-1/2) is attained in the balanced-increment regime for fixed p and d.This is identified as the optimal rate in that regime.
  • Applications: The same O(n^-1/2) rate extends to additive functionals of Markov chains through the Poisson decomposition.The decomposition transfers the martingale approximation result to the original additive functional.
  • Techniques: The analysis combines an antisymmetric-Stein-coupling formulation of the relative-score method with a refresh-then-maximal coupling.The construction separates the Stein identity from coupling-increment control while preserving conditional tensor structure.

A Proof of Lemma 1

The proof establishes contraction properties for the Markov operators and uses interpolation to control centered functions. It then constructs an L^r-limit solving the Poisson equation with zero π-mean.

  • Stationarity and Jensen’s inequality show that P^m and Π are contractions on L1(π; R^d).
  • The proof uses the dual representation of the Euclidean norm together with the preceding operator bound for each x∈X.
  • Riesz–Thorin interpolation applied to P^m−Π yields the required bound for centered functions.For π(f)=0, P^m f=(P^m−Π)f.
  • The partial sums of P^m f converge in L^r to a function g_f, while P is also an L^r contraction.
  • The limit satisfies g_f−Pg_f=f in L^r and has zero π-mean.This follows from the limiting relation and invariance of π.

B Proof of Corollary 1

The proof decomposes the additive functional into a martingale component and a boundary term, identifies the martingale covariance, and controls the boundary contribution in Wasserstein distance.

  • The Poisson equation g−Pg=h supplies the representation used to decompose the sum.
  • Summing the resulting relations yields the martingale decomposition S_n=M_n+B_n.
  • Because (D_i)_{i≥1} is stationary and martingale-difference, the covariance of the martingale component can be identified.
  • The covariance of B_n divided by n is O(n^-1), while the cross-covariance between M_n and B_n divided by n is O(n^-1/2).
  • After standardizing the martingale component so Cov(eS_n)=I_d, Theorem 1 is applied and its bound is substituted into the corollary.
  • The remaining boundary term is controlled using the original coupling and the triangle inequality for W_p.
  • Stationarity and Jensen’s inequality provide the moment comparison needed in the proof.
Loading 2609.09480v1…