Beyond Random Walks: Accelerating Discrete Sampling with Temporal Point Processes

TL;DR

Sampling from complex discrete distributions is a cornerstone of Bayesian inference and stochastic modeling, yet it is often plagued by "random-walk" inefficiency. This paper proposes a radical shift: instead of jump-based Markov chains, it uses Temporal Point Processes. By counting events in a sliding window, the sampler introduces a form of "discrete momentum" that prevents the process from immediately backtracking, resulting in significantly higher Effective Sample Size (ESS) and computational speed.

Background: The Gap in Discrete Sampling

In the continuous domain, we have advanced tools like Hamiltonian Monte Carlo (HMC) that use gradient info to avoid random walks. In discrete spaces, we usually rely on Gibbs sampling or birth-death processes, which lack momentum. While recent works like Zanella processes have improved discrete sampling through better balancing functions, they remain inherently jump-based and often reversible, limiting their exploration speed.

The Core Insight: Memory as Momentum

The authors treat the sampler as a system of $d$ coupled $M_{Q,t}/D/\infty$ queues.

• Arrivals: New events occur according to a conditional intensity ${\lambda }_i^{\ast }(t)$.
• Service/Memory: Every event stays in "memory" for exactly $m$ time units and then disappears.
• The State: The current sample $y\in {\mathbb{Z}}_{\ge 0}^d$ is simply the number of active events for each dimension within the window $(t-m,t]$.

Why is this better? In a standard birth-death process, a "death" (count decrease) can happen at any time, often immediately after a "birth" (count increase). In this point process sampler, a born event must stay for $m$ seconds. This creates a "forced forward motion" or discrete momentum.

The fundamental intensity formula: ${\lambda }_i^{\ast }(t)$ combines the target density ratio with a base intensity ${\eta }_i^{\ast }$.

Methodology: From Queues to Neural Networks

The authors prove a powerful Convergence Theorem: for any distribution $f(y)$ with "downward-closed support," the point process will converge to the target distribution as $to\infty$.

One of the most exciting applications is in Theoretical Neuroscience. The authors derive a recurrent stochastic neural network where:

1. Spikes are the events.
2. Integration Windows (the $m$ parameter) represent the synaptic integration time.
3. Refractory Periods emerge naturally from the dynamics.

This provides a rigorous mathematical bridge between biological spiking behavior and probabilistic inference (the "Sampling Brain" hypothesis).

Experimental Performance

The researchers tested the sampler against 63 target distributions, including Poisson, Sherrington-Kirkpatrick (Ising) models, and Stochastic Neural Nets.

Figure 1: Comparison of ESS and ESS/second. The Point Process Sampler (in orange) shows a clear advantage in computational efficiency (the right-hand plots).

Key Observations:

• Superiority over Birth-Death: The point process sampler is mathematically a "parent" to the birth-death process. Increasing randomness in point locations "degenerates" the sampler back into a birth-death process, which always performs worse.
• Computational Speed: Because it uses only $d$ conditional intensities (whereas Zanella processes might require evaluating $2d$ possible transitions), the CPU efficiency is unmatched, often 3x faster per second.

Critical Perspective

While the sampler is a breakthrough, it has nuances:

• The Weight Regime: The sampler performs best in "weak-coupling" scenarios. As interactions (weights) become extremely strong, its advantage over Zanella processes diminishes.
• Memory Overhead: Maintaining a queue of event times is slightly more complex than a simple integer state, though the authors' Algorithm 1 shows this is manageable with standard data structures.

Conclusion

This paper elevates temporal point processes from a descriptive tool to a prescriptive sampling engine. By leveraging the physical intuition of "deterministic service times" in queues, it offers a robust, non-reversible alternative to classical MCMC for discrete spaces. For researchers in Bayesian ML and Computational Neuroscience, this provides a highly efficient and biologically plausible new tool for the toolkit.

Ref: Stewart & Sahani, "SAMPLING ON DISCRETE SPACES WITH TEMPORAL POINT PROCESSES", Gatsby Unit, UCL.