TL;DR
This paper introduces Mirror PDMPs, a novel framework that combines Piecewise Deterministic Markov Processes with "mirror maps" from convex optimization. These new samplers allow researchers to draw samples from probability distributions constrained to convex sets (like the simplex or positive orthant) without the bias typically introduced by standard stochastic differential equation (SDE) methods, while also supporting efficient "exact subsampling" for big data applications.
What Problem Does This Paper Address?
In Bayesian inference and statistical mechanics, we often need to sample from distributions that are "constrained"—for example, parameters that must be positive or must sum to one.
The standard tool for this is Markov Chain Monte Carlo (MCMC). Common approaches like the Langevin algorithm rely on Stochastic Differential Equations (SDEs). However, when constraints are involved, these methods struggle. You either have to "project" samples back into the valid region (which introduces bias) or use complex transformations that can be computationally expensive.
While a newer class of algorithms called Piecewise Deterministic Markov Processes (PDMPs)—such as the Zig-Zag or Bouncy Particle Samplers—offers the promise of unbiased sampling and the ability to use only a fraction of the data at each step (subsampling), they were originally designed for unconstrained, flat spaces ($\mathbb{R}^d$). This paper bridges that gap.
Methods
The authors propose a "Mirror" approach to PDMPs. The core idea is borrowed from convex optimization:
- Mirror Maps: They use a "barrier function" to create a mirror map that transforms the constrained primal space (where the distribution lives) into an unconstrained dual space.
- Dual Sampling: Instead of trying to navigate the boundaries of the constrained set, the algorithm runs a standard PDMP (like the Zig-Zag Sampler) in the unconstrained dual space. Because of the way the mirror map is constructed, the "boundaries" of the original set are effectively pushed to infinity in the dual space.
- Mapping Back: The samples are then mapped back to the primal space using the inverse mirror map.
The paper specifically develops the Mirror Zig-Zag Sampler (MZZS) and the Mirror Bouncy Particle Sampler (MBPS). Crucially, they also introduce MZZ-SS, a version that uses "Poisson thinning" to perform exact subsampling, allowing the algorithm to scale to massive datasets without introducing the discretization bias found in stochastic Langevin methods.
Datasets
The authors evaluated their methods on three primary types of problems:
- Truncated Gaussian Distributions: A 10-dimensional synthetic problem where the distribution is restricted to a specific box-shaped region.
- Gamma Distributions: A 1-dimensional case used to test how the sampler handles the non-Lipschitz gradients common in many statistical models.
- Latent Dirichlet Allocation (LDA): A synthetic dataset of 10,000 data points from a 5-dimensional multinomial distribution. This is a classic machine learning task where the parameters are constrained to a simplex (they must be positive and sum to one).
Key Insights and Ideas
- The "Infinity" Trick: By using a barrier function, the sampler never actually "hits" a constraint boundary. As the process approaches a boundary in the primal space, its representation in the dual space moves toward infinity, naturally keeping the samples valid.
- Unbiasedness is Key: Unlike SDE-based methods (like the Mirror Langevin Algorithm), which are discrete-time approximations and inherently biased by their step size, MZZS is a continuous-time process that can be simulated exactly.
- Preconditioning via Geometry: The choice of the mirror map acts as a form of preconditioning. By choosing a map that matches the geometry of the constraint, the authors show they can significantly speed up convergence on ill-conditioned problems.
- Subsampling without Sacrifice: The MZZ-SS algorithm proves that you can gain the speed of stochastic gradients (only looking at a few data points at a time) without the mathematical "penalty" of bias.
Key Results
- Superior Accuracy: In the Gamma distribution test, MZZS achieved significantly lower Wasserstein-1 error (a measure of distance between distributions) compared to state-of-the-art Mirror Langevin methods.
- Zero Visible Bias: In the 10D Truncated Gaussian experiment, MZZS and MBPS perfectly matched the "ground truth" (Wall-HMC), whereas standard Langevin methods showed clear systematic bias.
- Efficiency in LDA: For the Dirichlet posterior (LDA), the subsampling version (MZZ-SS) converged faster than the full-data version and remained unbiased, while stochastic SDE-based competitors showed significant bias even after many iterations.
Limitations and Future Work
- Heavy Tails: The authors note that the transformation to the dual space can sometimes result in "heavy-tailed" distributions. This might require choosing different deterministic dynamics (how the "particle" moves between jumps) to maintain efficiency.
- Map Selection: While the paper provides standard barrier functions, the performance is sensitive to the choice of the mirror map. Future work could involve adaptive or data-driven mirror maps that learn the best geometry during the sampling process.
- Riemannian Exploitation: The authors suggest that further integrating the underlying Riemannian manifold structure of these maps could lead to even more powerful sampling dynamics.
Summary updated