Large deviations for the empirical measure of the zig-zag process

Joris Bierkens, Pierre Nyquist, Mikola C. Schlottke

Abstract

The zig-zag process is a piecewise deterministic Markov process (PDMP) in position and velocity space. The process can be designed to have an arbitrary Gibbs-type marginal probability density for its position coordinate, which makes it suitable for Monte Carlo simulation of continuous probability distributions. An important question in assessing the efficiency of this method is how fast the empirical measure converges to the stationary distribution of the process. In this paper, we provide a partial answer to this question by characterizing the large deviations of the empirical measure from the stationary distribution. Based on the Feng-Kurtz approach, we develop an abstract framework aimed at encompassing piecewise deterministic Markov processes in position-velocity space. We derive explicit conditions for the zig-zag process to allow the Donsker-Varadhan variational formulation of the rate function, both for a compact setting (the torus) and one-dimensional Euclidean space. Finally, we derive an explicit expression for the Donsker-Varadhan functional for the case of a compact state space and use this form of the rate function to address a key question concerning the optimal choice of the switching rate of the zig-zag process.

Introduction

In Bayesian statistics and machine learning, sampling from complex probability distributions is a fundamental challenge. While traditional Markov Chain Monte Carlo (MCMC) methods like Metropolis-Hastings are staples of the field, they often suffer from slow convergence due to their reversible nature. Recently, Piecewise Deterministic Markov Processes (PDMPs), such as the Zig-Zag Sampler, have emerged as a powerful non-reversible alternative. By avoiding the "back-and-forth" movement characteristic of random walks, these samplers can explore the state space more efficiently.

However, quantifying the convergence speed of these non-reversible processes is mathematically demanding. While spectral gap analysis provides some insight into how quickly a process reaches equilibrium, it does not always capture the behavior of the empirical averages—the actual values calculated during a simulation. This paper addresses this gap by applying Large Deviation Theory to study the rate at which the probability of the empirical average being "wrong" (deviating significantly from the true distribution) decays over time.

The Challenge of Piecewise Determinism

Establishing a Large Deviation Principle (LDP) for PDMPs is technically difficult. Standard LDP frameworks, such as the classical Donsker-Varadhan theory, typically assume a level of "fuzziness" or diffusion in the process. PDMPs, by definition, move deterministically between discrete jump events. This creates "atomic" components in their transition kernels; there is a non-zero probability that the process has not yet jumped at a given time $t$. This lack of smoothing prevents the application of standard proofs.

To overcome this, the authors utilize the Feng-Kurtz approach, which employs a Hamilton-Jacobi framework to establish the LDP. This allows the researchers to bypass the strict regularity requirements of classical theory and develop a general semigroup-based framework for a broad class of position-velocity PDMPs.

Methodology and Framework

The research proceeds through three primary stages:

  1. Abstract Framework Development: The authors establish a general framework for proving LDPs for PDMPs, focusing on the relationship between the process's generator and the resulting Hamilton-Jacobi equations.
  2. Verification for Zig-Zag: The authors verify that the zig-zag process—on both a compact torus and 1D Euclidean space—satisfies the necessary conditions (such as the mixing property) required by the abstract framework.
  3. Explicit Rate Function Derivation: For the compact case, the authors derive an explicit analytical expression for the Donsker-Varadhan rate function. Such explicit forms are rare for non-reversible processes and provide a powerful tool for optimization.

Key Insights: The Refreshment Rate Trade-off

A critical parameter in the zig-zag process is the "excess switching rate" or refreshment rate ($\gamma$). While the process naturally switches direction based on the target distribution's gradient, practitioners often add a small amount of extra switching to ensure the process explores the space thoroughly and remains ergodic.

A central question in the field has been: What is the optimal value for $\gamma$?

Interestingly, the large deviation analysis reveals a nuanced answer. The authors demonstrate that the rate function is strictly decreasing as a function of $\gamma$. From the perspective of the convergence of empirical averages, this implies that the smallest possible switching rate ($\gamma = 0$) is actually optimal. While some spectral analyses suggest that a small $\gamma > 0$ might help the process reach its equilibrium distribution faster, this work proves that for the accuracy of the time-averages themselves, additional switching only serves to slow down the decay of error probabilities.

Conclusion and Future Work

This paper provides a rigorous theoretical foundation for understanding the long-term behavior of the zig-zag sampler. By establishing Theorems 3.3 and 3.4, the authors confirm the existence of the LDP in both compact and non-compact settings. The explicit formula for the rate function (Proposition 3.5) and the subsequent optimization of $\gamma$ offer immediate practical guidance for MCMC implementation.

However, limitations remain. The explicit rate function and the optimization results are primarily focused on the one-dimensional case. Extending these results to higher dimensions ($d > 1$) involves significant technical hurdles, particularly in verifying the "mixing property" (Assumption A.5). Future research will likely focus on generalizing these explicit derivations to other PDMPs, such as the Bouncy Particle Sampler, and tackling the complexities of multi-dimensional state spaces.

Summary updated

Abstract

The zig-zag process is a piecewise deterministic Markov process in position and velocity space. The process can be designed to have an arbitrary Gibbs type marginal probability density for its position coordinate, which makes it suitable for Monte Carlo simulation of continuous probability distributions. An important question in assessing the efficiency of this method is how fast the empirical measure converges to the stationary distribution of the process. In this paper we provide a partial answer to this question by characterizing the large deviations of the empirical measure from the stationary distribution. Based on the Feng-Kurtz approach, we develop an abstract framework aimed at encompassing piecewise deterministic Markov processes in position-velocity space. We derive explicit conditions for the zig-zag process to allow the Donsker-Varadhan variational formulation of the rate function, both for a compact setting (the torus) and one-dimensional Euclidean space. Finally we derive an explicit expression for the Donsker-Varadhan functional for the case of a compact state space and use this form of the rate function to address a key question concerning the optimal choice of the switching rate of the zig-zag process.
BibTeX
@article{bierkens2021large,
  author = {Joris Bierkens and Pierre Nyquist and Mikola C. Schlottke},
  title = {{Large deviations for the empirical measure of the zig-zag process}},
  journal = {The Annals of Applied Probability},
  year = {2021},
  doi = {10.1214/21-aap1663},
}
Figure