The Challenge of Discrete MCMC Sampling
Sampling from complex, high-dimensional discrete distributions—such as binary strings in a Restricted Boltzmann Machine or Ising models in physics—is a fundamental challenge in machine learning and statistics. The gold standard for this task is the Metropolis-Hastings (M-H) algorithm.
In continuous spaces, practitioners have long relied on well-established "optimal scaling" rules. For instance, when using a Random Walk Metropolis (RWM) sampler, the step size should be tuned to hit an acceptance rate of roughly 0.234. For the more advanced Langevin algorithm (MALA), the target is 0.574.
However, in discrete spaces, this theoretical guidance has been missing. Researchers often defaulted to flipping just one bit at a time, which becomes incredibly slow in high dimensions. While recent work introduced "Locally Balanced Proposals" (LBP) that can flip multiple bits simultaneously, there was no principled way to determine the optimal number of bits to flip.
Discovering the "Magic Numbers" for Discrete Spaces
This paper solves this long-standing mystery by performing an asymptotic analysis (letting the dimension $N \to \infty$) to derive the relationship between the number of bits flipped, the efficiency of the sampler, and the resulting acceptance rate.
The authors establish a beautiful symmetry between discrete and continuous spaces:
- Locally Balanced Proposals (LBP): The optimal acceptance rate is 0.574. LBP in discrete space behaves mathematically like MALA in continuous space.
- Random Walk Metropolis (RWM): The optimal acceptance rate is 0.234, mirroring continuous RWM.
Crucially, these optimal acceptance rates are universal constants—they are independent of the specific target distribution. This provides a "set-it-and-forget-it" target for practitioners. Furthermore, the authors prove that for LBP, the optimal number of flips scales with the dimension as $O(N^{2/3})$. Because LBP can effectively flip $O(N^{2/3})$ bits while RWM is stuck flipping $O(1)$ bits to stay efficient, LBP becomes exponentially more powerful as the model size increases.
Adaptive LBP (ALBP)
Based on these findings, the authors propose Adaptive LBP (ALBP). This algorithm automatically adjusts the number of bits it flips during a "warm-up" phase to maintain the target 0.574 acceptance rate, effectively automating the tuning process.
Empirical Validation: Theory vs. Practice
The authors validated their theory across a range of classic and modern distributions, including Bernoulli distributions, Ising models, Factorized Hidden Markov Models (FHMM), Restricted Boltzmann Machines (RBM), and Deep Energy-Based Models (EBMs).
Empirical simulations show an almost perfect match with the predicted theoretical efficiency curves.
As shown in the Ising model experiments above, the efficiency peaks exactly at the predicted acceptance rates. The efficiency is also relatively "flat" around the peak; as long as the acceptance rate is between 0.5 and 0.7 for LBP, the sampler performs near-optimally.
The theoretical predictions hold up rigorously even when plotted against continuous theoretical curves (solid lines) in the Bernoulli model experiments.
Massive Speedups in Application
- Expected Jump Distance: In Bernoulli models, the Adaptive LBP (ALBP) achieved an Expected Jump Distance (EJD) of ~78, compared to just 1.0 for the standard single-bit LBP.
- EBM Training: When training deep Energy-Based Models on datasets like MNIST, Omniglot, and Caltech, ALBP reduced the number of MCMC steps required for Contrastive Divergence by 3x to 6x compared to non-adaptive versions, while maintaining or improving sample quality.
Limitations and Future Directions
While the empirical results are robust, the core theoretical proof assumes the target distribution is a product distribution (independent variables). Although experiments show the results hold for correlated models like Ising and RBMs, a formal proof for highly dependent variables remains open. Additionally, the theory assumes the distribution doesn't have "phase transitions" (sudden, radical changes in behavior), which can occur in certain physics models.
Ultimately, this scaling knowledge bridges a major gap between discrete and continuous MCMC performance, potentially paving the way for "HMC-style" samplers in discrete spaces.
Summary updated