Optimal Scaling for Locally Balanced Proposals in Discrete Spaces

Haoran Sun, Hanjun Dai, Dale Schuurmans

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.

Efficiency vs. Acceptance Rate for LBP and RWM on the Ising model. The dashed lines indicate the theoretical optimal rates of 0.574 and 0.234, respectively.

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.

Efficiency vs. Acceptance Rate for LBP on the Bernoulli model. The empirical data points closely match the theoretical curves, peaking at the 0.574 acceptance rate.

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

Abstract

Optimal scaling has been well studied for Metropolis-Hastings (M-H) algorithms in continuous spaces, but a similar understanding has been lacking in discrete spaces.Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open.In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces can also be characterized by an asymptotic acceptance rate that is independent of the target distribution. Moreover, we verify, both theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are $0.574$ and $0.234$ respectively. These results also help establish that LBP is asymptotically $O(N^\frac{2}{3})$ more efficient than RWM with respect to model dimension $N$. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces.We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety of target distributions in discrete spaces, including training deep energy based models.
BibTeX
@inproceedings{sun2022optimal,
  author = {Haoran Sun and Hanjun Dai and Dale Schuurmans},
  title = {{Optimal Scaling for Locally Balanced Proposals in Discrete Spaces}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=kgSv0xe8Y8},
}
Figure