Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper gives an algorithm to sample a distribution given access to pairwise comparisons from it. The technical contribution is to design a Markov chain whose stationary distribution matches the unknown one and then use the coupling from the past algorithm to obtain exact samples. The sample complexity of the resulting algorithm may depend on the structure of the distribution. Therefore the authors give another algorithm for sampling from a parametric Markov chain whose stationary distribution approximately matches the unknown one and which mixes significantly faster given a good approximation for the stationary distribution. They obtain this algorithm using efficient learning from the pairwise comparisons algorithm. 
strengths_and_weaknesses: Strength: The problem is important, the results are original, and the paper is clearly written.

Weakness: 
- The paper lacks any empirical verification, especially regarding how efficient the improved algorithm is in practice. 
- It would have been great to see the upper bound being matched by a lower bound.
questions: None.
limitations: None
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers perfect sampling from a discrete set D given data in the form of pairwise comparisons. A pair of points is sampled from the discrete set, but only the winner of the comparison is revealed (where the winner is distributed according to the conditional distribution over the two points). The goal is to generate a sample from D given only the results of the pairwise comparisons. To develop their sampling scheme, the authors use Coupling From the Past (CFTP), which is a general technique for exact sampling from the stationary distribution of a Markov chain. Unfortunately, CFTP depends on the landscape of D, and can therefore have a poor runtime. To improve on the basic implementation, the authors modify the CFTP strategy. Specifically, the transitions are modified so that the corresponding Markov chain has a uniform distribution. Then, rejection sampling is used to re-weight the sample in order to return to the target distribution over D.
strengths_and_weaknesses: •	This paper has some significant novel ideas, notably the modified CFTP scheme. My impression prior to reading this paper was that CFTP is practical only with monotone chains, but this paper potentially widens the applicability of the technique.

•	The writing is very good; the paper was a pleasant read!

•	No experimental evaluation; would be nice to include to get an idea of how practical this is. 

•	pg. 8: The beginning of the proof sketch of Lemma 5 could be broken up into more sentences.


questions: •	Do you have ideas where your modified CFTP method could be useful? Even speculation would be interesting!

•	Your CFTP method requires an estimate of the target stationary distribution. What if the stationary distribution is known up to a normalizing factor?

•	pg. 8: how can we ensure that the modified transition probabilities correspond to a valid probability distribution? Please show this explicitly.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies perfect sampling from pairwise comparisons. The setup is the following:

There is an unknown distribution D supported on [n], and the goal is to produce a sample from this distribution. The access to D is via 'pairwise comparisons'. There is a distribution Q supported on pairs [n]x[n], and the algorithm observes samples of the following form: first, one draws (x, y) from Q and then w is drawn according to D conditioned on it being either x or y. (A small remark: the algorithm doesn't need to know the distribution Q, but the complexity guarantees will depend on the structure of Q).

At a very high level, the line of work this explores is algorithmic problems on distributions when access model is not the standard independent samples. One could imagine settings where pairwise comparisons are the natural way one interacts with a distribution -- while the authors don't quite provide specific examples, they point to previous work exploring these kinds of questions. For instance, the question of learning a distribution in the same model was studied by [SBB+16] (and will also play a prominent role in the algorithm presented).

Very Straight-forward Approach: There is a very natural way to produce a sample from a distribution which is very close to D via building a natural Markov chain. One starts at an arbitrary element z in [n], and starts drawing samples of the from ({x,y}, w). If z is one of x or y, then we transition to w. The stationary distribution of this Markov chain is D, so given enough steps, one gets a draw from a distribution extremely close to D. The time it takes to produce a sample which is eps-close to D is essentially the time it takes for the Markov chain to mix, which depends on the structure of the Markov chain, which is specified by Q and D. Note that {x, y} is drawn from Q, and w from D conditional on {x,y}, so if M is the Markov chain, the time is proportional to 1 / Gamma(M), where Gamma(M) is the spectral gap of the Markov chain.

Straight-forward Approach: The problem with the approach above is that it is only produces samples from an approximately close distribution. There is actually a technique from Markov chains to produce perfect samples, called 'coupling from the past' (CFTP), which essentially runs n Markov chains backwards until they are all in one element ('coalesced'). Using this technique one can get a perfect sample in n / Gamma(M) (from my understanding, the factor n slowdown is due to the fact one considers n Markov chains?). 

There is one important aspect about the above two approaches which falls short. The running time depends on the spectral gap of the Markov chain M, which depends on Q as well as the unknown target distribution D. Furthermore, the paper provides a relatively natural and simple examples where the resulting Markov chain M takes exponential running time in n in order to mix, and applying the above two natural approaches would lead to algorithms running in exponential time. One natural question would be to have the computational complexity depend solely on the structure of comparisons (via the distribution Q), but not the unknown distribution D. This is what this work achieves.

They give an algorithm which produces a perfect sample from D. The number of pairwise comparison samples is n^2 times 1 / Gamma(Q), where Gamma(Q) is the spectral gap of the distribution Q. The complexity is now worst-case for any unknown distribution D. 

The starting point is the prior work of [SBB+16] on learning D, where an algorithm is presented for learning with n / (eps^2 Gamma(Q)) samples up to small error eps. The main insight of this work is that one may use the learning algorithm to later speed up the sampling algorithm. The idea proceeds as follows: one first learns the distribution D using prior work and small eps. Suppose that ~D is the learned approximation to D. The algorithm uses ~D to bias the Markov chain M to a different Markov chain M' which is close to the behavior of Q (and now mixing time will depend on Gamma(Q)). However, since the bias introduced by ~D is known, one can use a rejection sampling step to remove this bias at the cost of a factor n more samples.
strengths_and_weaknesses: Strengths: 

It is very nice that the paper starts with a very straight-forward approach which obtains undesirable guarantees, and shows that different (but similar) techniques can get different algorithms. The paper is very well-written.

Weaknesses: 

I don't see any major weakness. 
questions: Is it possible to give a concrete application of PC in the paper? I would imagine this would help the presentation of the paper. While I could artificially imagine some instances, I'm not aware of an application where your new algorithm could be useful.
limitations: The authors addressed this.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the problem of obtaining perfect samples from a discrete distribution with access to pairwise comparisons of elements. More specifically, let $\mathcal{D}$ be a distribution on a finite set $X$ and $\mathcal{Q}$ be a distribution on a subset of $X\times X$. Accessible samples are generated as below. A pair $(x,y)$ is first sampled from $\mathcal{Q}$ and then an element $w\in\{x,y\}$ is returned, where $w=x$ with probability $\mathcal{D}(x)/(\mathcal{D}(x)+\mathcal{D}(y))$ and $w=y$ with probability $\mathcal{D}(y)/(\mathcal{D}(x)+\mathcal{D}(y))$. The task is to sample an element from $\mathcal{D}$ using as few sample triples $(x,y,w)$ as possible.

The paper solves this problem with $\tilde{O}(n^2/\lambda(Q))$ samples of the triples, here $n = |X|$, $Q$ is a matrix defined by $Q_{xy} = -\mathcal{Q}(x,y)$ and $Q_{xx} = \sum_{y\neq x} \mathcal{Q}(x,y)$ and $\lambda(Q)$ is the second smallest eigenvalue of $Q$.

The major technical innovation is a new variant of the Coupling from the Past (CFTP) algorithm that allows the perfect sampling with $\tilde{O}(n\log(1/\mathcal{D}_{\min})/\Gamma(M))$ samples, where $M$ is the transition matrix of a Markov chain (depending on both $\mathcal{Q}$ and $\mathcal{D}$) and $\Gamma(M)$ the spectral gap from 1. To remove the dependence on $\mathcal{D}$, the authors use $\tilde{O}(n^2/\lambda(Q))$ samples to estimate the density function of $\mathcal{D}$ up to an $(1\pm 1/\sqrt{n})$-factor (another main technical contribution of the paper) and then modify the new CFTP algorithm to accommodate having just an approximation to $\mathcal{D}$ instead of the exact distribution. 
strengths_and_weaknesses: Strengths: Technically strong, solid theoretical results. Obtained precise sampling not just approximate sampling.

Weaknesses: I don’t see weakness in the results per se. It would be better if the authors can show a lower bound, say, why Omega(1/\lambda(Q)) samples are necessary.

Additional comments: This reads like a TCS paper and probably fits better at a more theoretical conference like COLT. This submission was reorganised from a longer paper to fit within NeurIPS's strict page limits, and as a result, it is incoherent in presentation at various places.  For example, the definitions and notations are relegated to the appendix, making the paper difficult to read; Section 2 refers to Algorithm 4, which also serves as a foundation for the main Algorithm 1 but is relegated to the appendix; a main technical theorem (Theorem 4) refers to Algorithm 5, which is also relegated to the appendix. If the paper is to be accepted, it must be thoroughly reorganised into a more coherent form within the page constraints.

questions: The full version of the paper is well-written. The following are some minor points:
- Lines 72-79: it is not clear at this point whether you are getting a comparison element w in {x,y}
- Line 88: in L_2 norm -> in the L_2 norm
- Line 217: give the full name of TCS
- Algorithm 1, line 4: coallesced -> coalesced
- Algorithm 1, line 12: define Be(...) (the definition only appears in Line 334, which is too late)
- Line 309, why do you need to take the max? Doesn’t |1-f|<=eps imply |1-1/f| <= eps? (after rescaling eps)
- Supplementary, Algorithm 4, line 4: coallesced -> coalesced
- Supplementary, line 816: seems that w=1 and w=0 are inverted? Staying at node i should correspond to w=0 and moving to j correspond to w = 1.
- Supplementary, lines 877, 1152, 1172: missing the word ‘Proof’ at the beginning of the line
- Supplementary, Algorithm 5, line 7: shouldn’t it be just output z’? |z-z’|_infty <= eps is the guarantee. It is also not clear what z is at this point unless one reads Appendix F.2.

limitations: N.A.
review_title: null

Meta-review: metareview: The authors show how to perfectly sample a discrete distribution, given sample access to the Bradley-Terry-Luce model on subsets of size 2. While the learning problem has been previously studied extensively, this work initiates the study of sampling. Technically, the authors introduce re-weighting and rejection sampling ideas that speed up coupling from the past by utilizing an approximate learning algorithm; these techniques could be useful in other applications, as the authors hint in the rebuttal.

The reviewers agreed that the paper is technically quite strong and that it's quite well written. The authors responded to all remaining questions by the reviewers, clearing the path to the paper being accepted.
confidence: Certain
Decision: Accept