Any-scale Balanced Samplers for Discrete Space

Haoran Sun, Bo Dai, Charles Sutton, Dale Schuurmans, Hanjun DaiICLR 2023 · OpenReview

Sampling from complex discrete distributions—such as those found in statistical physics or deep learning—is notoriously difficult. While "locally balanced" (LB) samplers have recently advanced the state-of-the-art, they are inherently limited to tiny, "local" steps. This paper introduces Any-scale Balanced (AB) Samplers, which leverage second-order curvature information and a self-adjusting weight function to enable efficient, large-scale jumps, significantly outperforming existing methods in both speed and accuracy.

The Challenge with Local Jumps

In Markov Chain Monte Carlo (MCMC), the goal is to draw samples from a target distribution. For continuous spaces, powerful tools like Hamiltonian Monte Carlo use gradients to navigate efficiently. However, discrete spaces (like grids of bits or categorical data) lack true gradients, making navigation much harder.

Recently, locally balanced samplers emerged as a breakthrough for discrete spaces. They use a specific weight function to bias jumps toward high-probability regions. However, LB samplers have a major catch: they only work well if the jumps are very small. If a sampler attempts a large, "non-local" jump to explore the space faster, the mathematical assumptions underlying LB samplers break down. The gradient approximations they rely on become wildly inaccurate, leading to slow "mixing" where the sampler gets stuck in one area for too long.

Any-scale Balanced Samplers

To repair the gap in non-local proposals, the authors propose three key innovations:

1. Any-scale Balanced Functions: Instead of using the standard fixed weight function ($g(t) = \sqrt{t}$), they introduce a flexible class of functions, $g(t) = t^\alpha$. They demonstrate mathematically and empirically that the optimal $\alpha$ changes depending on the scale of the jump ($\sigma$). As the jump size increases, the optimal weight function must shift from a square root ($\alpha=0.5$) toward a linear function ($\alpha=1.0$).

The optimal alpha shifts from 0.5 to 1.0 as the jump scale increases.

To handle this dynamically, the authors include an adaptive algorithm that tunes both $\sigma$ and $\alpha$ on the fly, preventing the fixed weight function from becoming a bottleneck for global exploration.

2. Quadratic Approximations: Standard samplers use a first-order (linear) approximation of the distribution, which fails for large steps. AB Samplers use a second-order (quadratic) approximation to capture the "curvature" of the target distribution. By using a global estimate of the Hessian (the matrix of second derivatives), the sampler can make much more accurate large-scale proposals.

3. The Gaussian Integral Trick & SDP: Sampling from a quadratic discrete distribution is mathematically intractable. To solve this, the authors use the Hubbard-Stratonovich transform (a Gaussian integral trick) to introduce a continuous auxiliary variable. They further optimize this process by solving a Semi-Definite Programming (SDP) problem to maximize the variance of the jumps. This ensures the Gaussian integral trick doesn't smother the proposal with too much random noise, keeping the acceptance rate high even for large jumps.

Experimental Validation

The authors evaluated their sampler on a diverse range of distributions, including synthetic models (2D Grid Ising models, Lattice Gaussian Models, Bayesian Logistic Regression) and real-world image data (Deep Energy-Based Models trained on MNIST, Omniglot, and Caltech).

The AB Sampler—specifically the "AB-trace" variant—consistently dominated the baselines.

AB-trace significantly outperforms baseline samplers in Effective Sample Size.

Key Results: * Massive Efficiency Gains: On complex tasks like the Sparse Gaussian model, AB-trace achieved an Effective Sample Size (ESS) of 1227.94, compared to just 71.23 for the previous state-of-the-art (DLP). * Faster Mixing: In deep learning tasks, the AB sampler reached high-quality samples (lower energy states) much faster than standard Gibbs or LB samplers. * Robustness: The adaptive tuning successfully found optimal $(\sigma, \alpha)$ pairs across different temperatures and complexities, proving the method doesn't require manual "magic" constants to work.

Limitations and Future Directions

While highly effective, the approach has a few limitations:

  • Scalability of SDP: The SDP solver is fast for hundreds of dimensions but might become a bottleneck for models with tens of thousands of variables.
  • Rough Hessian Estimation: The current method uses a "global" quadratic approximation. In highly complex distributions, curvature changes locally. Moving toward "Riemannian" or "Quasi-Newton" styles could address this.
  • Stability: The adaptive algorithm for tuning $\sigma$ and $\alpha$ can be unstable before the Markov chain reaches its steady state, which could be problematic when training models from scratch.

Summary updated

Abstract

The locally balanced informed proposal has proved to be highly effective for sampling from discrete spaces. However, its success relies on the "local'' factor, which ensures that whenever the proposal distribution is restricted to be near the current state, the locally balanced weight functions are asymptotically optimal and the gradient approximations are accurate. In seeking a more efficient sampling algorithm, many recent works have considered increasing the scale of the proposal distributions, but this causes the "local'' factor to no longer hold. Instead, we propose any-scale balanced samplers to repair the gap in non-local proposals. In particular, we substitute the locally balanced function with an any-scale balanced function that can self-adjust to achieve better efficiency for proposal distributions at any scale. We also use quadratic approximations to capture curvature of the target distribution and reduce the error in the gradient approximation, while employing a Gaussian integral trick with a special estimated diagonal to efficiently sample from the quadratic proposal distribution. On various synthetic and real distributions, the proposed sampler substantially outperforms existing approaches.
BibTeX
@inproceedings{sun2023any,
  author = {Haoran Sun and Bo Dai and Charles Sutton and Dale Schuurmans and Hanjun Dai},
  title = {{Any-scale Balanced Samplers for Discrete Space}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=lEkl0jdSb7B},
}

Loading related content...

Figure