STOC Conference 2023 Conference Paper
Parallel Discrete Sampling via Continuous Walks
- Nima Anari
- Yizhi Huang
- Tianyu Liu
- Thuy-Duong Vuong
- Brian Xu
- Katherine Yu
We develop a framework for sampling from discrete distributions µ on the hypercube {± 1} n by sampling from continuous distributions supported on ℝ n obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions µ, the result of the convolution is well-conditioned log-concave, whenever the Gaussian’s variance is above an O (1) threshold. We plug off-the-shelf continuous sampling methods into our framework to obtain novel discrete sampling algorithms. Additionally, we introduce and study a crucial notion of smoothness for discrete distributions that we call transport stability, which we use to control the propagation of error in our framework. We expect transport stability to be of independent interest, as we connect it to constructions of optimally mixing local random walks and concentration inequalities. As our main application, we resolve open questions raised by Anari, Hu, Saberi, and Schild on the parallel sampling of distributions which admit parallel counting. We show that determinantal point processes can be sampled via RNC algorithms, that is in time log( n ) O (1) using n O (1) processors. For a wider class of distributions, we show our framework yields Quasi-RNC sampling, i.e., log( n ) O (1) time using n O (log n ) processors. This wider class includes non-symmetric determinantal point processes and random Eulerian tours in digraphs, the latter nearly resolving another open question raised by prior work.