TL;DR
This paper establishes a Large Deviation Principle (LDP) for the empirical measure of the zig-zag process, a popular non-reversible MCMC sampler. By deriving an explicit rate function, the authors prove that to maximize the speed of convergence from a large deviations perspective, one should use the minimum possible switching rate—a finding that adds a nuanced counterpoint to existing spectral analysis.
What Problem Does This Paper Address?
In the world of Bayesian statistics and machine learning, we often need to sample from complex probability distributions. Traditional Markov Chain Monte Carlo (MCMC) methods like Metropolis-Hastings can be slow. Recently, Piecewise Deterministic Markov Processes (PDMPs), such as the Zig-Zag Sampler, have emerged as a powerful alternative. They are non-reversible, meaning they don't "waste time" retracing their steps, which often leads to faster convergence.
However, quantifying how much faster they converge is difficult. Standard tools like the "spectral gap" provide some insight but don't always capture the full picture of how empirical averages (the stuff we actually calculate) behave over time. The authors use Large Deviation Theory to study the "rate function," which essentially measures the exponential rate at which the probability of the empirical average being "wrong" (far from the truth) decays.
A major technical hurdle is that standard large deviation theory (Donsker-Varadhan) assumes the process is somewhat "fuzzy" or diffusive. PDMPs are deterministic between jumps, creating "atomic" components in their transition kernels that break standard proofs.
Methods
The authors employ the Feng-Kurtz approach, which uses a Hamilton-Jacobi framework to establish the LDP. This allows them to bypass the regularity requirements of the classical Donsker-Varadhan theory.
The paper proceeds in three main steps:
- Abstract Framework: They develop a general semigroup-based framework for establishing LDPs for a broad class of position-velocity PDMPs.
- Application to Zig-Zag: They verify that the zig-zag process (on both a compact torus and 1D Euclidean space) satisfies the necessary conditions for this framework.
- Explicit Derivation: For the compact case, they go beyond the usual "variational" form of the rate function to derive an explicit analytical expression. This is a rare feat for non-reversible processes.
Datasets
Not discussed in the paper. This is a theoretical mathematical work; no empirical datasets or benchmarks were used.
Key Insights and Ideas
- The "Atomic" Problem: The authors highlight why PDMPs are hard to analyze: because they move deterministically for periods, there is a non-zero probability that the process hasn't "jumped" yet at time $t$. This lack of "smoothing" requires the more robust Feng-Kurtz machinery.
- Non-Reversibility and the Rate Function: The paper provides one of the first explicit rate functions for a non-reversible process that lacks a drift-diffusion character.
- The Refreshment Rate Trade-off: In the zig-zag process, you can add an "excess switching rate" ($\gamma$) to help the process explore. The authors found that the rate function is strictly decreasing as a function of $\gamma$.
- Convergence vs. Equilibrium: Interestingly, while some spectral analyses suggest that a small amount of extra switching ($\gamma > 0$) might help reach equilibrium faster, this paper shows that for the convergence of empirical averages, the smallest possible switching rate ($\gamma = 0$) is actually optimal.
Key Results
- Theorems 3.3 & 3.4: These establish the existence of the LDP for the zig-zag process in both compact (torus) and non-compact (real line) settings.
- Proposition 3.5: Provides the explicit formula for the Donsker-Varadhan rate function $I(\mu)$.
- Optimization of $\gamma$: The authors calculate the derivative of the rate function with respect to the refreshment rate $\gamma$ and show it is non-positive (Equation 11). This proves that increasing the switching rate actually slows down the decay of error probabilities for empirical measures.
Limitations and Future Work
- Dimensionality: While the abstract framework is general, the explicit rate function and the optimization of the switching rate are primarily derived for the one-dimensional case.
- Multi-dimensional Challenges: The authors note that extending the verification of the "mixing property" (Assumption A.5) to higher dimensions ($d > 1$) is "substantially more difficult" and remains an open area for research.
- Other PDMPs: While the framework is "aimed at" processes like the Bouncy Particle Sampler, the explicit results in this paper are specific to the Zig-Zag process. Applying these explicit derivations to other PDMPs is a natural next step.
Summary updated