📊 statistics

Almost sure convergence rates of adaptive increasingly rare Markov chain Monte Carlo

This paper establishes almost sure convergence rates for adaptive increasingly rare Markov chain Monte Carlo algorithms under a Wasserstein-like contraction assumption, demonstrating their applicability across various ergodicity settings without requiring technical conditions like diminishing adaptation.

Original authors: Julian Hofstadler, Krzysztof Latuszynski, Gareth O. Roberts, Daniel Rudolf

Published 2026-02-24

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Julian Hofstadler, Krzysztof Latuszynski, Gareth O. Roberts, Daniel Rudolf

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to guess the average height of everyone in a massive, invisible city. You can't see the whole city at once, so you have to send out a single explorer (a "random walker") to visit people one by one. Every time the explorer visits someone, they write down the height. Eventually, if the explorer visits enough people, the average of their notes should match the true average of the city.

This is the basic idea of Markov Chain Monte Carlo (MCMC), a powerful tool statisticians use to solve complex math problems.

However, there's a catch. The explorer is a bit clumsy. If they just wander aimlessly, it might take them a million years to visit enough people to get a good average. To help them, we can give the explorer a GPS that learns. This is Adaptive MCMC. The GPS looks at where the explorer has been and says, "Hey, you keep getting stuck in that one neighborhood; let's change your walking style to explore better."

The Problem with "Always-On" GPS

The problem with a GPS that learns constantly is that it can get confused. If the GPS changes its mind every single step, the explorer never settles into a rhythm. It's like trying to learn to ride a bike while someone keeps changing the handlebars and the seat every second. The math behind this is incredibly messy and hard to prove works.

The Solution: "Increasingly Rare" Adjustments

This paper introduces a clever trick called AIR (Adaptive Increasingly Rare).

Imagine the GPS doesn't change every step. Instead:

First hour: It checks the map and adjusts the route every 10 minutes.
Second hour: It adjusts every hour.
Third hour: It adjusts every day.
Later: It adjusts once a year.

The adjustments happen, but they happen less and less frequently as time goes on. Eventually, the explorer is just walking on a fixed path, but that path was carefully tuned by the GPS earlier.

What This Paper Actually Does

The authors of this paper wanted to answer a very specific question: "How fast does our explorer's average get accurate?"

In math, we often talk about "convergence rates." Think of it like a speedometer.

Slow convergence: The explorer is still guessing wildly after a long time.
Fast convergence: The explorer's guess is very close to the truth very quickly.

The authors proved that with the AIR method, the explorer's guess gets incredibly close to the truth very fast. Specifically, they showed that the error shrinks at a rate that is almost as good as the theoretical best possible speed (known as the "Law of the Iterated Logarithm").

The Secret Sauce: "Wasserstein Contraction"

To prove this, the authors used a concept called Wasserstein contraction. Let's use a metaphor:

Imagine the explorer is a drop of ink falling into a glass of water.

Without contraction: The ink might stay in a clump or swirl around forever.
With contraction: The water is designed so that no matter where the ink starts, it gets squeezed and mixed into the whole glass very quickly.

The authors assumed that their "water" (the mathematical space) has this squeezing property. They proved that if the water squeezes the ink well enough, then even with the "rare adjustments" of the AIR method, the explorer will find the true average very quickly.

Why This Matters

It's Safer: Unlike other adaptive methods that require strict, complicated rules to work, this method is more robust. You don't need to force the GPS to "slow down" its learning speed artificially; the "rare adjustment" schedule does the work for you.
It's Faster: They showed that even if you only run the simulation once (which is what happens in real life), you can be confident that your result is accurate within a predictable timeframe.
It's Flexible: They proved this works for many different types of "cities" (mathematical problems), whether the explorer is walking on a flat plain or a mountainous terrain.

The Bottom Line

This paper is like a manual for a new type of GPS for statisticians. It says: "Don't try to steer the car every second. Just check the map occasionally, and let the intervals between checks get longer and longer. If you do this, you will reach your destination (the correct answer) faster and with more certainty than you thought possible."

It turns a chaotic, hard-to-predict process into a smooth, reliable journey.

1. Problem Statement

The paper addresses the convergence properties of Adaptive Markov Chain Monte Carlo (MCMC) algorithms. In standard MCMC, a Markov chain is constructed to sample from a target distribution $\nu$ . Adaptive MCMC improves efficiency by updating the transition kernel based on the history of the chain. However, this adaptation introduces non-Markovian behavior, making theoretical analysis difficult.

Specifically, the authors focus on Adaptive Increasingly Rare (AIR) MCMC algorithms. In AIR schemes, the adaptation parameter is updated less and less frequently over time (e.g., at times $T_m$ where the gap between updates grows polynomially). While AIR methods are known to perform well empirically and simplify some theoretical proofs by dropping the "diminishing adaptation" assumption, there was a lack of rigorous results regarding almost sure convergence rates for the Monte Carlo sums in these settings, particularly under general contraction conditions.

The goal is to establish path-wise convergence rates for the Monte Carlo estimator:
$S_n f = \frac{1}{n} \sum_{j=1}^n f(X_j) \to \nu(f)$
specifically quantifying the rate at which the error $|S_n f - \nu(f)|$ decays almost surely.

2. Methodology

The authors employ a martingale approximation technique based on solving Poisson's equation, a standard tool in Markov chain theory, adapted for the AIR setting.

Key Technical Components:

Augmented State Space:
The analysis is conducted on an augmented state space $\mathcal{Y} = \mathcal{X} \times \Phi$ , where $\Phi$ represents auxiliary variables (e.g., for handling multimodal targets). This framework generalizes the classical non-augmented setting.
Poisson's Equation Decomposition:
For a function of interest $h$ , the authors solve the Poisson equation $u_\gamma(y) - P_\gamma u_\gamma(y) = h(y) - \pi_\gamma(h)$ . This allows the decomposition of the Monte Carlo sum error into three parts:
- A martingale term ( $M_n$ ): Arising from the sum of differences $u(Y_j) - P u(Y_{j-1})$ .
- A remainder term ( $R_m$ ): Arising from the jumps in the adaptation parameter $\Gamma$ at update times $T_m$ .
- A boundary term: Involving initial and final values of $u$ and $h$ .
Wasserstein-like Contraction:
Instead of assuming uniform or geometric ergodicity directly, the authors assume a contraction condition with respect to a Wasserstein-like function $W$ .
- They define a distance-like function $d$ and a corresponding Wasserstein-like metric $W$ .
- Assumption 3.1: The transition kernels $P_\gamma$ satisfy a uniform contraction property: $\tau(P_\gamma) \le M$ and $\tau(P_\gamma^{k_0}) \le \tau < 1$ for all adaptation parameters $\gamma$ .
Handling the Remainder Term:
A critical innovation is showing that for AIR schemes, the remainder term $R_m$ (which usually requires strong "diminishing adaptation" assumptions in fully adaptive settings) becomes manageable because adaptation occurs rarely. The frequency of adaptation is controlled by a parameter $\beta$ (where update times $T_m \approx m^{1+\beta}$ ).

3. Key Contributions

Path-wise Convergence Rates: The paper derives explicit almost sure convergence rates for AIR MCMC sums. The main result (Equation 2) shows that for a renormalization factor $r(n)$ :
$\lim_{n \to \infty} \frac{1}{r(n)} \sum_{j=1}^n (f(X_j) - \nu(f)) = 0 \quad \text{a.s.}$
where $r(n)$ is close to $\sqrt{n}(\log n)^{1/2+\varepsilon}$ (matching the Law of the Iterated Logarithm for i.i.d. variables).
Relaxation of Assumptions: Unlike previous adaptive MCMC limit theories, this work does not require the "diminishing adaptation" assumption (which states that the change in the kernel must vanish as $n \to \infty$ ). The "increasingly rare" nature of the updates is sufficient to control the error.
General Framework: The results are proven under a Wasserstein contraction assumption. This unifies and generalizes classical settings like simultaneous uniform ergodicity and simultaneous geometric ergodicity.
Small $\beta$ Regime: The authors identify that for very frequent updates (small $\beta$ ), the convergence rate degrades in the general proof. However, they show that under additional Lipschitz and waning adaptation conditions (Assumption 3.14), the optimal rate can be recovered even for small $\beta$ .

4. Main Results

The paper provides three main theorems depending on the ergodicity setting:

Uniformly Bounded Eccentricity (Theorems 3.5 & 3.6):
- If the "eccentricity" (expected distance from a point to the stationary distribution) is uniformly bounded and the function $f$ $f$ is bounded and Lipschitz:
  - For $\beta \ge 1$ : The rate is $O(\sqrt{n}(\log n)^{1/2+\varepsilon})$ .
  - For $\beta \in (0, 1)$ : The rate is $O(n^{1/2+\varepsilon})$ , where $\varepsilon$ depends on $\beta$ .
Lyapunov Condition (Theorem 3.11):
- For unbounded functions $f$ satisfying $|f| \le V^{1/p}$ (where $V$ is a Lyapunov function), the convergence rate is $O(n^{1/2+\varepsilon})$ . The value of $\varepsilon$ depends on the growth of the function ( $p$ ) and the adaptation frequency ( $\beta$ ).
Small $\beta$ Regime (Theorem 3.16):
- If the adaptation parameters satisfy a "waning adaptation" condition (the sum of parameter changes decays sufficiently fast), the optimal rate $O(\sqrt{n}(\log n)^{1/2+\varepsilon})$ is achieved even for $\beta \in (0, 1)$ .

Corollaries 4.5 and 4.10 translate these limit theorems into practical path-wise bounds:
$\left| \frac{1}{n} \sum_{j=1}^n f(X_j) - \nu(f) \right| \le \frac{C(\omega) r(n)}{n}$
This implies the error decays almost like $1/\sqrt{n}$ (up to logarithmic factors).

5. Significance and Applications

Theoretical Advancement: This is one of the first works to establish almost sure convergence rates for adaptive MCMC without relying on the diminishing adaptation assumption, leveraging the specific structure of AIR algorithms.
Practical Relevance: The derived bounds provide users with quantitative information about the speed of convergence for a single run of the algorithm, which is crucial for assessing the reliability of MCMC simulations in practice.
Broad Applicability: The framework covers:
- Simultaneous Uniform Ergodicity: Including adaptive Metropolis on compact sets and adaptive stereographic MCMC.
- Simultaneous Geometric Ergodicity: Including adaptive Metropolis with covariance estimation for distributions with super-exponential tails.
- Weak Harris Ergodicity: Covering infinite-dimensional settings (e.g., pCN algorithms) via weak Harris contraction.
Counter-example: The paper includes a counter-example (Appendix C) demonstrating that if the uniform contraction assumption (Assumption 3.1) is violated, the Law of Large Numbers may fail, highlighting the necessity of the contraction condition.

In summary, the paper provides a robust theoretical foundation for AIR MCMC, proving that these algorithms achieve near-optimal convergence rates under general contraction assumptions, thereby validating their use in complex, high-dimensional statistical problems.