# Quadratic Speedups in Parallel Sampling from Determinantal Distributions

arXiv: https://arxiv.org/abs/2203.11190 · HTML: https://mlsanity.com/paper/2203.11190/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2022.

## Built on by (most cited first, 1 of 1)

- [Parallel Sampling via Counting](https://mlsanity.com/paper/2408.09442/) (2024)

## Abstract (arXiv)

We study the problem of parallelizing sampling from distributions related to determinants: symmetric, nonsymmetric, and partition-constrained determinantal point processes, as well as planar perfect matchings. For these distributions, the partition function, a.k.a. the count, can be obtained via matrix determinants, a highly parallelizable computation; Csanky proved it is in NC. However, parallel counting does not automatically translate to parallel sampling, as classic reductions between the two are inherently sequential. We show that a nearly quadratic parallel speedup over sequential sampling can be achieved for all the aforementioned distributions. If the distribution is supported on subsets of size k of a ground set, we show how to approximately produce a sample in widetildeO(k^frac12 + c) time with polynomially many processors for any constant c>0. In the two special cases of symmetric determinantal point processes and planar perfect matchings, our bound improves to widetildeO(√ k) and we show how to sample exactly in these cases. As our main technical contribution, we fully characterize the limits of batching for the steps of sampling-to-counting reductions. We observe that only O(1) steps can be batched together if we strive for exact sampling, even in the case of nonsymmetric determinantal point processes. However, we show that for approximate sampling, widetildeOmega(k^frac12-c) steps can be batched together, for any entropically independent distribution, which includes all mentioned classes of determinantal point processes. Entropic independence and related notions have been the source of breakthroughs in Markov chain analysis in recent years, so we expect our framework to prove useful for distributions beyond those studied in this work.