TL;DR
This paper introduces the first efficient (polynomial-time) algorithm for combinatorial Bernoulli factories. It allows researchers to transform coins with unknown biases into exact samples of complex combinatorial objects—like perfect matchings—ensuring the expected value of the sample perfectly matches the unknown input biases.
What Problem Does This Paper Address?
Imagine you have a set of coins, each with an unknown probability $x_i$ of coming up heads. You want to use these coins to sample a complex object, such as a perfect matching in a graph, such that the probability of any edge $(i, j)$ appearing in your sample is exactly $x_{ij}$.
This is the "Bernoulli factory" problem. While approximate sampling is easy (just flip the coins many times to estimate the biases), exact sampling is notoriously difficult because any non-linear function of an empirical mean is inherently biased. Exactness is crucial in fields like mechanism design (to preserve incentive compatibility) and Monte Carlo simulations (to prevent errors from compounding).
Previous work established that such factories exist for a specific class of shapes called "affine slices of the cube." However, the existing algorithms were agonizingly slow—requiring an exponential number of coin flips (e.g., $n^{2n-1}$ for a graph with $n$ vertices). This paper tackles the challenge of making these factories practical by reducing the complexity from exponential to polynomial.
Methods
The authors propose a "batch and correct" framework. The core algorithm, INTERIOR, works as follows:
- Batch and Project: Flip each input coin $m$ times to get an empirical mean vector $Z$. Project $Z$ onto the affine hull of the target polytope $P$ to get a point $Y$. Because projection is an affine map, $E[Y]$ is exactly the unknown bias vector $x$.
- Handling Infeasibility: While $Y$ has the correct mean, it might occasionally fall outside the polytope $P$ (see Figure 1). Simply discarding these samples would introduce bias.
- The Reserve and Correction: The algorithm uses a "reserve" probability $\alpha$. With probability $1-\alpha$, it outputs a rounded version of $Y$. With probability $\alpha$, it runs a correction step.
- Lottery over Anchors: The correction step compensates for the "residual" error when $Y$ falls outside $P$. It performs a lottery over a set of "anchor points" $\{u_i^\pm\}$ surrounding a known interior point $u$ (see Figure 2). The probabilities for this lottery are generated using a standard scalar linear Bernoulli factory.
For the "Universal" version of the algorithm (where the distance to the boundary is unknown), the authors add a pilot stage that adaptively estimates the required batch size and reserve probability from the coins themselves.
Datasets
Not discussed in the paper. As a theoretical contribution in computer science and probability, the "evaluation" consists of mathematical proofs of complexity bounds rather than empirical tests on datasets.
Key Insights and Ideas
- Projection is the Secret Sauce: The realization that projecting an empirical mean onto an affine hull preserves the expected value exactly allows the algorithm to stay "on track" even when individual batches are noisy.
- Don't Discard, Correct: Instead of the usual "accept-reject" sampling which can be slow, the authors use the "residual" from failed batches to tilt a lottery, effectively "paying back" the bias introduced by those failures.
- Boundary as a Statistic: For affine slices, the distance to the boundary ($\delta_*$) is a property of the coin biases themselves. This means a "pilot" stage can look at the coins to decide how hard it needs to work, without needing a human to provide a safety margin parameter.
Key Results
- Polynomial Complexity: The expected number of coin flips is $O(d^{7/2} \delta_*^{-3} \log(d/\delta_*))$, where $d$ is the dimension and $\delta_*$ is the distance to the boundary.
- Exponential Speedup for Matchings: For the specific case of perfect matchings, the complexity is $O(n^8 \delta_*^{-2} \log(n/\delta_*))$. This is a massive improvement over the previous $n^{2n-1}$ baseline. For a uniform doubly stochastic matrix ($1/n$ entries), the new bound is $O(n^{10} \log n)$, whereas the old one was effectively impossible to compute for even moderate $n$.
- Generality: The reduction works for any rational polytope, provided you have a point deep inside and a promise that the unknown $x$ is also far from the boundary.
Limitations and Future Work
- The Boundary Problem: The algorithm's complexity scales with $1/\delta_*$, meaning it slows down significantly as the unknown bias $x$ approaches the boundary of the polytope. It does not terminate if any $x_i$ is exactly 0 or 1.
- Interior Point Requirement: The algorithm requires knowledge of a rational point $u$ that is strictly inside the polytope. While this can be found via linear programming for many combinatorial objects, it's a necessary prerequisite.
- Optimization: The authors note they have not tried to optimize the polynomial exponents (e.g., the $n^8$ for matchings), suggesting there is likely room for even more efficient implementations.
Summary updated