Discrete Momentum: Accelerating MCMC Sampling with Temporal Point Processes

TL;DR

Researchers from UCL have unlocked a new frontier in discrete sampling by moving away from standard Markov chains toward Temporal Point Processes (TPPs). By structuring a sampler as a system of queues with deterministic service times, they've introduced a form of "discrete momentum" that prevents the sampler from getting stuck in inefficient random walks. The result? A sampler that is significantly faster and more "effective" than traditional birth-death processes and Zanella samplers.

The Problem: The Curse of the Random Walk

In the world of continuous spaces, we have advanced methods like Hamiltonian Monte Carlo (HMC) that use momentum to glide through distributions. In discrete spaces (like counting or graph structures), we are often stuck with Jump Processes.

The standard approach is the Birth-Death process: if you want to sample a count, you "birth" an instance (increment) or "die" an instance (decrement). The problem is these models have no memory. They are prone to "backtracking"—immediately undoing a jump they just made—which leads to slow exploration of the distribution, or what physicists call "diffusive" or "random-walk" behavior.

Methodology: Queues, Windows, and Momentum

The authors' core insight is to treat the count vector not as a simple state, but as the sum of events over a sliding window $[t-m,t]$.

1. The Sliding Window State

Instead of just saying "the current value is 5," the sampler maintains a history of when those 5 events arrived.

• Arrival (Birth): Driven by a conditional intensity function ${\lambda }^{\ast }(t)$.
• Departure (Death): Deterministic. Once an event is $m$ seconds old, it must leave the window.

2. The Intuition of "Discrete Momentum"

Because the "deaths" are deterministic and tied to the past "births," the sampler cannot easily backtrack. If the sampler just moved from count $4\to 5$, it cannot instantly go back to 4 unless an old event happens to expire at that exact moment. This creates a trajectory through the state space that feels "pushed" forward, reducing the autocorrelation between successive samples.

3. Mathematical Backbone

The sampler is modeled as a system of $M_{Q,t}/D/\infty$ queues.

• $M_{Q,t}$: Arrival rates are dependent on the current window state $Q^{-}(t)$.
• $D$: Deterministic service times ($m$).
• $\infty$: Infinite servers (any number of events can be in the window).

Figure 1: Comparison of Effective Sample Size (ESS) across different target distributions. Note the TPP sampler (red) consistently maintains higher efficiency than the Birth-Death baseline.

Neural Implementation: Biologically Plausible Inference

The paper extends this theory to a Recurrent Stochastic Neural Network. In this model:

• Neurons communicate via spikes (events).
• The "count" is the number of spikes in a time window $m$.
• The relative refractory period (where a neuron is less likely to fire right after firing) emerges naturally from the double-exponential term in the energy function.

This suggests that the brain might not just be "calculating" probabilities, but acting as a high-efficiency TPP sampler, using biological constraints like refractory periods as a feature to improve sampling efficiency.

Experiments & SOTA Performance

The authors tested the sampler on 63 different distributions, including Poisson targets, Sherrington-Kirkpatrick models (Ising models), and Neural Networks.

• Efficiency: The TPP sampler consistently beat the Birth-Death process.
• Speed: Because the "death" of an event is a simple queue operation (no need to recalculate transition rates for deaths), the ESS per CPU second was up to 3.6x higher than competitors.
• Weak vs. Strong Coupling: The TPP sampler shines in "weakly coupled" systems. In highly "tight" distributions (high $\beta$ in Ising models), the advantage diminishes relative to Zanella processes, but the raw speed usually keeps it competitive.

Conclusion and Caveats

This work proves that adding a specific type of memory (a deterministic window) to a discrete sampler provides a rigorous way to implement "momentum" without needing the gradients required by HMC.

Limitations:

1. Support Constraints: The target distribution must be downward-closed (if $\{2,2\}$ is possible, $\{1,2\}$ and $\{2,1\}$ must also be possible).
2. Memory Overhead: Storing exact event times in a queue is more memory-intensive than storing a single integer.

However, for researchers in Bayesian statistics and Computational Neuroscience, this represents a major step toward faster, more realistic discrete simulation.