Perfect Sampling from Pairwise Comparisons
Authors: Dimitris Fotakis
Alkis Kalavasis
Christos Tzamos
Venue: NeurIPS 2022 Accept (2022)
Keywords: Exact Sampling
Pairwise Comparisons
Truncated Statistics
Coupling From the Past

Abstract: In this work, we study how to efficiently obtain perfect samples from a discrete distribution $\mathcal{D}$ given access only to pairwise comparisons of elements of its support. Specifically, we assume access to samples $(x, S)$, where $S$ is drawn from a distribution over sets $\mathcal{Q}$ (indicating the elements being compared), and $x$ is drawn from the conditional distribution $\mathcal{D}_S$ (indicating the winner of the comparison) and aim to output a clean sample $y$ distributed according to $\mathcal{D}$. We mainly focus on the case of pairwise comparisons where all sets $S$ have size 2. We design a Markov chain whose stationary distribution coincides with $\mathcal{D}$ and give an algorithm to obtain exact samples using the technique of Coupling from the Past. However, the sample complexity of this algorithm depends on the structure of the distribution $\mathcal{D}$ and can be even exponential in the support of $\mathcal{D}$ in many natural scenarios. Our main contribution is to provide an efficient exact sampling algorithm whose complexity does not depend on the structure of $\mathcal{D}$. To this end, we give a parametric Markov chain that mixes significantly faster given a good approximation to the stationary distribution. We can obtain such an approximation using an efficient learning from pairwise comparisons algorithm (Shah et al., JMLR 17, 2016). Our technique for speeding up sampling from a Markov chain whose stationary distribution is approximately known is simple, general and possibly of independent interest.

Perfect Sampling from Pairwise Comparisons
Dimitris Fotakis NTUA
Alkis Kalavasis
Christos Tzamos UW Madison
NTUA
fotakis@cs.c www.i/sccsnuuu..g.m
kalaavasisalkistmaii htt.:aaiiiiiiiaaaaaaaaaaaa.a.. ntua.gr
tzamos@wisc.ent edu
Abstract
In this work, we study how to efficiently obtain perfect samples from a discrete distribution given access only pairwise comparisons of elements of its support. Specifically, we assume access to samples (I., S), where S is drawn from a distri- bution over sets (indicating the elements being compared), and x: is drawn from the conditional distribution Ds (indicating the winner of the comparison) and aim to output a clean sample y distributed according to D. We mainly focus on the case of pairwise comparisons where all sets S have size 2. We design Markov chain whose stationary distribution coincides with D and give an algorithm to obtain exact samples using the technique of Coupling from the Past. However, the sample complexity of this algorithm depends on the structure of the distribution D and be even exponential in the support of D in many natural scenarios. Our main contribution to provide an efficient exact sampling algorithm whose complexity does not depend the structure of D. To this end, give parametric Markov chain that mixes significantly faster given good approximation to the stationary distribution. We obtaín such approximation using an efficient learning from pairwise comparisons algorithm (Shah et al., JMLR 17, 2016). Our technique for speeding up sampling from Markov chain whose stationary distribution is approximately known is simple, general and possibly of independent interest.
Introduction
Machine I Learning questions dealing with pairwise comparisons (PCs) constitute fundamental and broad research area with multiple real-world applications [SBB= 16, Kaz1 LOAF12, SBGWI6 FH10, WJJ13J. For instance, the preference of consumer to choose one product over another constitutes a pairwise comparison between the two products. The two bedrocks of modern ML applications are inference/learning and sampling. The area of learning from pairwise comparisons has vast amount of work [RA14, SBGWI6 16, DKNS01, NOS12, Hun04, JLYY1I, APA18, LSR21, HOX14, SBB + 16, VY16. NOS17, VYZ20]. In this problem, there exist alternatives and an unknown weight vector 1, i..., D is probability distribution over [n]] Roughly speaking, the learner observes pairwise comparisons (or more generally wi-wise comparisons) of the form (w, (u, v}) w
E Rº where D(i) is the weight of the i-th element with D(1) 2
and Σie in] D(i)
[n] x [n] that compare the alternatives u * and w equals either or indicating the winner of the comparison. The most fundamental distribution over pairwise comparisons model [BT52, Luc59] where the probability that the learner observes are compared D(u) + D(v).. The learner's goal is mainly to estimate the underlying distribution D using a small number of pairwise comparisons.
the BTL when the items u,
In this work, we focus on questions concerning sampling, the second bedrock of modern ML. In fact, we will deal with a fundamental area of the sampling literature, namely perfect sampling. In contrast to approximate sampling, perfect (or exact) sampling from probabilistic model requires an exact sample from this model. Problems in this vein of research lie in the intersection of computer science and probability theory and have been extensively studied [PW96, PW98, Hub04, Hubl6, FGY19,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

JSS21, AJ21, GJL19, BC20, HSW21J. Our work poses questions concerning perfect sampling in the area of pairwise comparisons. We ask the following simple yet non- non-trivial question: Is it possible to obtain a perfect sample x distributed as in 'D by observing only pairwise comparisons from D?
Apart from the algorithmic and mathematical challenge of generating exact samples, perfect simula- tion has also practical motivation, noticed in various previous works [Hubl6, JSS21, AJ21J. Crucially, its value does not stem from the fact that the output of the sampling distribution is perfect; usually, one can come up with a Markov chain whose evolution rapidly converges to the stationary measure. Hence, the distance between the (approximate) sampling distribution from the desired one can become small efficiently. This approximate sampling approach has a clear drawback: there is no termination criterion, i.e., the Markov chain has to be run for sufficiently long time and this requires an a priori known bound on the chain's 's mixing time, which may be much larger than necessary. On the contrary, perfect sampling algorithms come with stopping rule and this termination condition can be attained well ahead of the worst-case analysis time bounds in practice.
Second, the question that we pose appears to have links with the important literature of truncated statistics [Gal97, DGTZI8]. Truncation is a common biasing mechanism under which samples from an underlying distribution DD over X are only observed if they fall in a given set S C X. i.e. one only sees samples from the conditional distribution Ds. There exists a vast amount of applications that involve data censoring (that go back to at least [Gal97]) where one does not have direct sample access to D. Recent work in this literature [FKT20] asked when it is possible to obtain perfect samples from some specific truncated discrete distributions (namely, truncated Boolean product distributions). The area of pairwise comparisons can be identified as an extension of the truncated setting where the truncation set can change (i.e.. each subset of alternatives corresponds to some truncation set); while perfect sampling has been a subject of interest in truncated statistics, the neighboring area of pairwise comparisons lacks of efficient algorithms for this important question.
Problem Formulation. Let us define our setting formally (which we call Local Sampling Scheme). This setting is standard (without this terminology) and can be found e.g., at [RA14].
Definition ([RA14]). Let Z be a finite discrete domain. Consider target distribution 'D supported on Z and a distribution Q supported on subsets of Z. The sample oracle Samp (2; is called Local Sampling Scheme (LSS) and each time it is invoked, it returns an example (I. such that: (i) the set S C Z is drawn from Q and (ii) x is drawn from the conditional distribution Ds, where D2(x) = {x E ())) and D(S) = Ezes D(x).
For simplicity, we mostly focus on the case where Q is supported on subset of 2 Z, and often refer to Q as the pair distribution. Then, Q naturally induces an (edge weighted) undirected graph Go on 2, where {u, v) E F(Gg), if {u, v) is supported on Q, and has weight equal to the probability Q(u, v)) that (u. is drawn from Q. When we deal with a pair distribution 2, the above generative model lies in the heart of the pairwise comparisons (FV86, Mar96, WJJ13). The comparisons are generated according to the Bradley-Terry-Lee (BTL) model (where the comparisons have size 2, (BT52, Luc59]): there is an unknown weight vector D E PT (D(u) indicates the quality of item u) and, for two items u, v, the algorithm observes the sample (u, {u, v)), i.e., that beats v with D(u) probability D(a)+D(r)- question:
Motivated by the importance of perfect simulation, ask the following
Question 1. Is there an efficient algorithm that draws i..dd. samples () Samp Q: D) and generates single perfect sumple y ~ 'D?
To put our contribution into context, let us ask another question whose answer is clear from previous work. What is the sample complexity of learning D from a Local Sampling Scheme Samp Q: D)? Here, the goal is to estimate D in some 4, norm given such comparisons. Some works focus on learning the ce-parameterization z E F. with o log (z)). Depending on the context, either the normalization condition (1, D) = 1 or (1, z) = 0 is used. [SBB* 16] deal with the problem of learning the re- paramettrrizztionn in the L- norm when |S| (pairwise comparisons) or [S] (k-wise comparisons with k = O()). The sample complexity for learning in L2 norm from pairwise comparisons is n/ ()(()()))). where X(Q) is the second smallest eigenvalue of a Laplacian matrix Q. induced by the pair distribution Q (the learning result is tight in a minimax sense for some appropriate semi-norm [SBB+16] 16)). In particular, the matrix Q defined as Q.y = Q(xx, v) and Qze = Enee Q(2, v). Hence, in the pairwise comparisons setting, the sample complexity of
2

---

learning incurs an overhead associated with X(Q) (Table 1). The algorithm of [SBB* 16] is a pivotal component for our main result, as we will see later. [APA18] provide a similar result for learning D in TV distance using random- walk approach. We remark that learning from pairwise comparisons requires some mild conditions concerning the sampling process (LSS in our case). We review them shortly below.
Table 1: Learning and Exact Sampling from PCs of size 2. Ö() subsumes logarithmic factors.
Sample Access
Learning (E (>)0)
Exact Sampling
Definition I with Pairwise
(z, L2) O(n/E)) XQQ Ö(n²)
Comparisons
[SBB+16]
x()) (Theorem 3)
Conditions for Local Sampling Schemes. We provide a standard pair of conditions for Local Sampling Schemes (these similar conditions also needed in the learning problem). We interested in LSSs that satisfy both of these conditions. However, some of our results still hold when only the first condition is true; this will be more clear later. Assumption I is a necessary information-theoreti condition for the pair distribution Q.
Assumption (Identifiability). The support of the pair distribution Q the Local Sampling Scheme contains a spanning free, i.c., the induced graph Go is connected. We define & == B(G2).
Intuitively, the pair distribution Q needs to be supported on a spanning tree. Equivalently, the associated Laplacian matrix Q should have positive Fiedler eigenvalue x(Q) > 0. Assumption 2 is condition about the support of Q and the target distribution D; it allows efficient learning of D from pairwise comparisons and is related to the difficulty of estimating small D p-robabbliities.
Assumption 2 (Efficiently Learnable). There exists a constant o > 1 such that target distribution D D(n) satisfies I (a,() Dly] S Φ, where & is the support of the distribution Q.
From dual perspective, Assumption 2 says that Q is supported only edges where the two corresponding D-ratios are well controlled and implies that any conditional distribution P(r..)) has D(z)D(y)
bounded variance, i.e., (1/6)/(1 + o)² S (D())+ I 00(1 1/0)?. A quite similar property has been proposed in the problem of learning from pairwise comparisons [SBB+16]
Contributions and Techniques. We provide algorithmic answer to Question I regarding perfect sampling (under the above mild conditions) by showing the following:
There exists an efficient algorithm that draws Ö(n² (XQ)) samples from Samp Q:D) and outputs a perfect sample x D.
The tool that makes this possible (and algorithmic) is a novel variant of the elegant Coupling from the Past (CFTP) algorithm of [PW96]. CFTP a technique developed by Propp and Wilson (IPW96, PW98J), that provides an exact random sample from a Markov chain, that has law the (unique) stationary distribution (we refer Appendix A.2.3 for an introduction to CFTP). To make our contribution clear, we provide two theorems; Informal Theorem that directly and "naively" applies CFTP (indicating the challenges behind efficient sample correction) and a more sophisticated Informal Theorem 2 that combines CFTP und learning from pairwise comparisons in order to get the result of Table 1. We show how to efficiently generate "global" samples from the true distribution D from few samples from a Local Sampling Scheme Samp( Q; D). To this end, our novel algorithm combines the CFTP method [PW96, PW98], a remarkable technique that generates exact samples from the stationary distribution of given Markov chain, with (i) an efficient algorithm that estimates ranking models from pairwise (and, in general, k-wise) comparisons [SBB+ 16] and (ii) procedures based on Bernoulli factories [DHKNI7, MP05, NPO5] and rejection sampling.
the parameters of Boodlly-Teery--eee
At technical level, we observe (Section 2) that Local Sampling Scheme Samp( Q: D) naturally induces a canonical ergodic Markov chain on [ni] with transition matrix M. The probability of transition from state to a state y is equal to the probability Q(xr, y), that the pair (z. y) is drawn from Q. times the probability D(y)/(D(r) Dy)), that y is drawn from the conditional distribution Di Then, the unique stationary distribution of the resulting Markov chain coincides with the true
3

---

distribution D. Applying (a non-adaptive version of) the Coupling from the Past algorithm, we obtain the following result under Assumption 1 and Assumption 2 for target distribution D over [n|. For the matrix M, we let T ((M) be its absolute spectral gap (see Appendix A. for extensive notation).
Informal Theorem (Direct Exact Sampling from LSS). With an expected number of Ô
n²
[[M))
samples from Local Sampling Scheme Samp( Q D), there exists an algorithm (Algorithm 1) that generates sample distributed as in D.
The sample complexity of Informal Theorem 1 is, for instance, attained by the instance of Figure 1, which we will discuss shortly.' We remark that Informal Theorem 1 holds more generally for Local Sampling Schemes that only satisfy Assumption 1 and not Assumption 2; for a formal version of the above result, we refer to Theorem 2 and for a discussion on the resulting sample complexity, we refer also to Remark 1. Let us now see why Informal Theorem I is quite unsatisfying.
In Informal Theorem 1, the matrix M contains the transitions induced by Samp( (D) and the transition u + v is performed with probability Q(u, v) ( + D(v)) and r(M) is the absolute spectral gap of the Markov chain's 's transition matrix M on which CFTP performed. Note that both M and [(M) depend on Q and the target distribution D. In many natural cases, c.g., if D is multimodal or includes many low probability points, the CFTP-based algorithm of Informal Theorem 1 can be quite inefficient! For instance, Figure 1 is bad instance for the standard CFTP algorithm. It corresponds to an instance where the support of Q is the path graph over [n] and the target distribution D is bimodal, satisfying Assumption and Assumption 2 with ø = 2. In this case, M captures the transitions of a negatively biased nearest-neighhor random walk on the path, i.e., the probability of moving to the boundary is larger than moving to the interior. The coalescence probability of the two extreme points is of order a" for some 0 < a < 1. This probability is connected to the maximum hitting time and, consequently, we get that the mixing time is a(a ") [LP17] and so the coalescence time is exponentially large. Informal Theorem I depends on ((M) and hence the exponential dependence on is reflected in the conductance of the chain, which is exponentially small. So, can we eliminate the bias due to Definition 1 efficiently?
1/1
1/4
1/8
1/8
2
3 4 5
Figure 1: A bad instance for Informal Theorem 1.
As technical contribution, we provide a novel exact sampling algorithm whose convergence does not depend on DD We show how to improve the efficiency of CFTP by removing the dependence of its sample (and computational) complexity on the structure of the true distribution D. In particular, in Section 3, we show the following under Assumption and Assumption 2:
Informal Theorem (Exact Sampling from LSS using Learning). There exists an algorithm (Algo-
rithm 2 & Algorithm 3) that draws expected number of Ô ?
samples from a Local Sampling
x(Q)
Scheme Samp( Q: D), and generates sample distributed as in D.
In the above. X(Q) is the second smallest cigenvalue (a.k.a,, the Fiedler cigenvalue) of Q, the weighted Laplacian matrix of the graph Go induced by Q: this is the same matrix that appears in the learning result of Table 1. Crucially, the sample complexity in the above result is polynomial in n, provided that the pair distribution Q reasonable. For the path graph of Figure 1 with Q the uniform distribution, Informal Theorem 1 yields an exponential sample complexity but the spectrum of the matrix of Informal Theorem 2 is spec(Q) = { e - cos Hence, since 1 cos (z) sin (x/2) x x², we get that the sample complexity is poly(n). Moreover, the runtime of the algorithm is sample polynomial.
For the instance of Figure I one can reduce the sample complexity of our results by a factor of n, since the state space has a natural ordering and one could apply monotone CFTP (it suffices to coalesce two random processes and not n).

---

Technical Overview. A first key idea towards establishing Informal Theorem 2 is to exploit learning in order to accelerate the convergence of CFTP. We first apply modification of) the gradient-based algorithm of [SBB+ 16] to the empirical log-likelihood objective, which estimates the parameters of BTL, ranking models from PCs, with samples from Samp(Q; D). As a result of this learning algorithm (whose efficiency requires Assumption 2, as in [SBB+ 16]). we get a probability distribution D, which approximates D with small relative error, in the sense that D(x) (1 + D(x), for any x in D's support. As we saw in Table 1, the sample complexity will be roughly of order ((n((MQ) ))). To be precise, this learning phase gives us sample complexity term of order O(n²) (xQ)) and corresponds to a single execution of the above learning algorithm for the target 'D in relative error with accuracy ( /n) (the accuracy's i choice will be more clear later).
The new idea is that we can use the output of the learning algorithm D and a Bernoulli factory mechanism to transform the Markov chain induced by Samp Q D) into an ergodic chain with almost uniform stationary probability distribution, whose transition probabilities (and mixing time) essentially do not depend on D! To do so, for each pair of states 2, y, with (I, y) E E and D(x)= > Dly), we can use Bernoulli downscaling (which constitutes essential building block for general Bernoulli factories, see e.g., [DHKN17, MP05, NPO5]) to transform the (unknown) probability of a transition from y to I to (D(r) + D(w)) ((x) (conditional that the edge (z., y) is drawn). Since D(x) x D(z), for all states x. this makes the probability of transition from x to y almost equal to the probability of a transition from y to x, which, in turn, implies that the stationary distribution of the modified Markov chain is almost uniform. Thus,
speed up the CFTP algorithm by removing the modes due to the landscape of the target D and can get an exact sample from the stationary distribution of the modified Markov chain with O (n log(n)/X(Q) Namely, the sample complexity of this parameterized variant of the CFTP algorithm does not depend on the structure of 'D anymore (of course, it does depend on the size n of D's support). The above constitute our second key idea and the intuition behind this re-weighting comes from the method of simulated tempering [MP92, GLRI8) 18b, GLR18a].
samples.
Our third idea deals with the output of the algorithm. Since we want an exact/clean sample from D, rejection sampling,
cannot simply print the output of the above process. As last step. guided by the distribution D. and apply the "reverse" modification, bringing the distribution of the resulting sample back to 'D (see Algorithm 2). With high probability, this last rejection sampling will succeed after (n) executions of the parameterized CFTP algorithm. However, note that we do not have to execute the learning algorithm again. Hence, the total sample complexity is equal to the cost of the learning phase (that is performed only once and its output is given as input to the parameterized CFTP algorithm: see Algorithm 2) and the cost of the modified CFTP multiplied by (()) (due to
rejection sampling), which yields a total of Ö(n² (Q))) samples. The above modification of the Markov chain induced by Samp( Q D), which improves possibly significantly its mixing time, is simple and general and the parameterized variation of the standard CFTP algorithm (Algorithm 2) might be of independent interest. In Appendix G, we discuss how to extend the analysis of the main Algorithm 2 to sets of size larger than 2.
Related Work. Our results are related to and draw ideas from several areas of theoretical computer science, which we review below.
Exact Sampling. Exact sampling comprises a well-studied field [Ken05, Hub16] with numerous applications in theoretical computer science (e.g.. to approximate counting [Hub98]). One of our main tools, the Coupling From the Past algorithm, is the breakthrough result of [PW96, PW98], which established the applicability of perfect simulation, and made efficient simulation of challenging problems (e.g., Ising model) feasible. After this fundamental result, the literature of perfect simulation flourished and various exact sampling procedures have been developed, see e.g., [PW96, GM99, Wi100, HSO0, FHOO, Hub04J), and the references therein.
Learning and Ranking from Pairwise Comparisons. There is a vast amount of literature on ranking and parameter estimation from pairwise comparisons (see e.g., [FV86, Mar96, Cat12] and the references therein). A significant challenge in that field is to come up with models that accurately capture uncertainty in pairwise comparisons. The standard ones are the Boudley-Terry-Lene model [BT52, Luc59] and the Thurstone model [Thu27]. Our work is closely related to previous work on the BTL model [RA 14, SBGW16, 16, DKNS01, NOS12, Hun04, JLYY11, APA18, LSR21] and our sample complexity rates depend on the Fiedler eigenvalue of a pairwise comparisons matrix, as in [HOX14, SBB* 16, VY16, NOS17, VYZ20J.
(BTL)
5

---

Truncated Statistics. Our work falls in the research agenda of efficient learning and exact sampling from truncated samples [Bre96, Coh16]. Recent work has obtained efficient algorithms for efficient learning from truncated [DGTZ18, KTZ,19, DGTZ11,, IZID00, DR720, BDNP21, NP19, FKT20, DKTZ21] and censored [MMS21, FKKT21, Ple21] samples. Closer to our work, [FKT20] also deal with the question of exact sampling from truncated samples.
Correction Sampling. Sample correction is field closely related to our work. This area of research deals with the case where input data are drawn from noisy or imperfect source and the goal is to design sampling correctors [CGR 18] that operate as filters between the noisy data and the end user. These algorithms exploit the structure of the distribution and make "on-the-fly" corrections to the drawn samples. Moreover, the problem of local correction of data has received much attention in the contexts of self-correcting programs, locally conrectable codes, and local filters for graphs and functions (see e.g.. [BLR93, SS10, JR13, ACCL04, BGJ 10, GLT20J)-
Conditional Sampling. Conditional sampling deals with the adaptive learning analog of L.S,, where the goal is again to learn an underlying discrete distribution from conditiona//ruunateed samples, but the learner can change the truncation on demand and is extensively studied [Can15, FJO+ 15, ACK15b, BC18, ACKI5a, GTZ17, KT19, CCK+19)
An Exact Sampling Algorithm using CFTP
Consider a discrete target distribution D. For pair distributions Q. the Local Sampling Scheme Samp( Q; D) can be regarded graph G (V, E) with V = (D) and supp(2) We let V = [n]. Let M denote the canonical transition matrix of the Markov chain, associated with the oracle Samp( Q: D). The entries of M [Maylawe(N] are defined as:
D(y)
May Q(., 5) D(x) + D(y)
for any x + y and M.z = 1- 1-11--MM for x E [n].
(1)
Observe that the transition from to y performed when both the edge {xr y} is drawn from Q. with probability proportional to Q(x, y) and is drawn from the conditional distribution D (ar.g) The Markov chain, whose transitions are described by M, has some notable properties: it has D as stationary distribution and is ergodic. We can invoke the fundamental CFTP algorithm over the Markov chain of [PW96, PW98] obtain a perfect sample from D.
Algorithm 1 Exact Sampling from Local Sampling Schemes of Informal Theorem & Theorem
1: procedure EXACTSAMPLER()
> Sample access the LSS oracle Samp( Q; D).
2:
+
3: Fo(x) +- x. for any I E [n]
4:
while Fe has not coalesced do
b. While no coalescence has occured.
5:
t + t-1
6:
Draw sample (i.j. w) with (1,5) E E and w E {1,5)
7:
for x = 1...n n do
In order to update state D- Append F, in the past.
8:
i $ {i,j} or x = w then Fe(x) < (x)
else Fa(x) <- Fw+ New transition with probability ((x, w) D(w)
9:
D(m)"
end end
11:
Output (1) end procedure
>> Output the perfect sample.
13:
We extensively discuss CFTP in Appendix A.2.3 for the interested reader. CFTP yields the following (unsatisfying) result, whose proof can be found at the Appendix B.
Theorem 2 (Direct Exact Sampling from LSS). Let Dunn be the minimum value of the target distribution D. Under Assumption 1 and for any 8 > 0, Algorithm I draws, with probubility at least
1 1- 8, N = O n log[1//Diii)
T(M) log(3)) samples from Local Sampling Scheme Samp( Q; D) over [n]],
runs in time polynomial in N and outputs a sample distributed as in D.
Note that in the above result (Theorem 2), the confidence parameter 5 corresponds to the number of samples required and not the quality of the output sample (the sample is perfect with probability

---

1). We comment that the proof of the above Theorem is nearly straightforward and follows from the analysis of the CFTP algorithm: the purpose of Theorem is to indicate that direct application of CFTP would potentially lead to an exponential number of samples due to the shape of the target distribution. Our main technical contribution begins the next section: We give an exact sampler that surpasses the dependence on the target's structure using learning and rejection sampling.
3 Improving the Exact Sampling Algorithm using Learning
The main drawback of Theorem's 2 algorithm is that its sample complexity depends on both Q and D and consequently in many natural scenaria the sample complexity may be exponentially large in n. Next, we present Algorithm 2, which will allow us to remove the dependence on D for the Markov chain and reduce the sample complexity to polynomial in the domain size. The crucial differences compared to Algorithm are the orange lines. Algorithm 2 is parameterized extension of CFTP and its input a vector p E [0, 1)". We remark that when p is the all-ones vector 1, we obtain the previous Algorithm 1.
Algorithm 2 Parameterized Extension of Algorithm
Input: p [0, 1]nh
b For instance, this may be the output of Algorithm b Sample access to the LSS oracle Samp( Q: D).
2: procedure EXACTSAMPLERiS
3:
+ 0, Fo(2) f H, for any æ E [n]
4: while F, has not coalesced do
While coalescence has occured.
5:
1. 16-
6:
Draw sample (i, w) with (i,j) E & and E {i,5)
7:
for x = 1.... do
In order to update state x.
8:
if $ {i.5} or w then Fi(x) + Fz)
else Fi(z) + {
Fe+((),, with probability min(p())/m(w)) 1} P(t1(1),
9:
otherwise
10:
end end
11:
12:
Draw C ~ (e(p((())))
> Be(p) is a p-biased Bernoulli coin.
13:
C' then Output (1) else Output 1
> Output the perfect sample Fail.
14:
end procedure
We perform Algorithm 2 using input parameter an estimate DD of the target D with (relative) error of order e = 1/vn (this estimate obtained via Theorem Algorithm 5 using ((n/)((Q) samples from Samp(Q: D), as we will see later). Under the perspective of LSSs random walks on an irreducible Markov chain, Algorithm proceeds by executing CFTP. Recall that in each draw from Samp( Q; D), transition can be realized by the matrix M The fact that this transition depends on the target D is pathological, as we observed previously. The algorithm, instead of performing this transition (as the non-adaptive CFTP algorithm of Theorem 2 does), performs Bernoulli factory mechanism (downscaling). using the estimates D in order to make each transition almost uniform (see Line 9 of Algorithm 2). This change introduces some (known) bias to the random walk and changes the stationary distribution from D an almost uniform one. By performing the CFTP method, the algorithm iteratively reconstructs the past of the infinite simulation, until all the simulations have coalesced time (almost uniform) stationary distribution. Since the introduced bias is known (it corresponds to the inverse of the estimates D), the algorithm accepts the sample using rejection sampling, guided by D, so that the final sample distributed according to the target distribution D (see Line 13 of Algorithm 2). Specifically, we show (for the proof, see Appendix C) that:
When coalescence occurs, the algorithm has exact sample from the biased
Theorem 3 (Exact Sampling from LSS using Learning). Under Assumption I and Assumption 2, for any O, there exists an algorithm (Algorithm 3) that draws, with probability least N O (n2 log (n)) (n)/X(Q) (og(118) samples from a Local Sampling Scheme Samp( Q; D), runs in time polynomial in N, and outputs a sample distributed as in D.
We proceed with the analysis of Algorithm 3, which can be decomposed into two parts: the Learning Step (Line 2) and several iterations of Algorithm 2 (Line 5).
7

---

Algorithm 3 Exact Sampling from Local Sampling Schemes of Informal Theorem & Theorem 3
1: procedure
The algorithm of Theorem 3.
2: D LEARN(E == 1/vn,0) Learn D in relative error with Algorithm 5 (Theorem 4).
3: X 1-1
4: while =1 repeat
5: x EXACTSAMPLER(D)
D Call Algorithm 2.
6: Output
7: end procedure
Learning Step. For two distributions D, D with ground set [n]], we introduce the sequence/list (of Observe that the pair of sequences (1-D/D, 1-D/D)
length n) 1-D/D := (1 DD=))(((()))>xe) captures the relative error between the two distributions. The sample complexity of the task of learning D in c-relative error is summarized by the following:
Theorem (Learning Phase). For any e, 5 > O, there exists an algorithm (Algorithm 5) that draws N =
xQ) log(t) samples from Samp( Q; D) satisfying Assumptions 1 and 2, runs in time polynomial in N, and, with probubility at least 1 - 6, computes an estimate 'D of the target distribution DD that satisfies the relative error guarantee max [ D/D lo, || | >/D]l>> S.
We execute once the learning algorithm (Algorithm 5) that estimates D in relative error and we choose accuracy 1/ We would like to shortly comment the choice of the accuracy value: An accuracy of constant order would still potentially yield a biased random walk. After the re-weighting step, goal is to show that the target distribution becomes almost uniform and that the absolute spectral gap of the reformed matrix is of order X(Q) (see the proof of Lemma 15). In order to ensure this, any accuracy that vanishes with n is sufficient. We chose to set = 1///n so that the complexity of learning ( n
(xQ)2=) matches that of the exact sampling procedure ( (x(q)) ). This learning step costs
n²/ (P((QQ
(Q) samples and the estimate D is used as input to Algorithm 2. For the proof of Theorem 4, refer to the Appendix E. We can now move Line 5.
We next focus on a single execution of the parameterized CFTP algorithm. Our goal is to transform the Markov chain of the Local Sampling Scheme defined in Equation (1) to a modified Markov chain with an almost uniform stationary distribution. We are going to provide some intuition. Applying Theorem 4, we consider that, for any [n), there exists coefficient D(x)= (z)). The idea is to use ((x) and make the stationary distribution of the modified chain close to uniform. Intuitively, this transformation should speedup the convergence of the CFTP algorithm. The downscaling method of Bernoulli factories gives us a tool to do this modification.
Executing Algorithm 2.
We can implement the modified Markov chain via downscaling as follows: Consider an edge (z. y} with transition probability pair (Pay- (Pay-Pyz) Pyx). Without loss of generality, we assume that D(y) > ((x)) (which intuitively means that we should expect that Pay > Pya) Then, the downscaler leaves Pyz unchanged and reduces the mass of Pzy make the two transitions almost balanced. Consider the LSS D(y)
transition matrix M with May = Q(x; y) D(x)) and M = Σyta Mzy- Also, let D be an estimate for the distribution D (Theorem 4). For the pair (z,8), we modify the transition probability
Díg) D(z) RJ
Pay = May only if Pay > Pyz, to be equal to the following: Pay = Q(x, v) D(z)+ D(p)
Q y) P(x)
D(z)+D(g) = Pyz where we use that D(x) As D(x) and D(y) R D(y). The transition
probability from to corresponds to Bernoulli variable Be(pzy), which is downscaled by
D(x)/ D(w) < The modified transition probability Pay can be implemented by drawing a A (e(D(x)) /D()) and then drawing P ~ Be(pay) (from Samp( Q; D)) and, finally, realizing the y only if AP 1. This implementation is valid since the two sources of
transition from randomness are independent. So, we perform a downscaled random walk based on the transition matrix M with May Pay (the "small" probability Pyr remained intact). We call M the D-scaling of M. Lemma 5 summarizes the key properties of M. The definition of the mixing time, used below, can be found at the notation Appendix A. and the full proof can be found at the Appendix D.
8

---

Lemma 5 (Properties of Rescaled Random Walk), Let 'D be a distribution on [n] and consider an c-relative approximation D of D, as in Theorem 4 with = 1// Consider the transition matrix M of the Local Sampling Scheme Samp( 2; D) (see Equation (1)), and let M be the D-scaling of M. Then, the transition matrix M (i) has stationary distribution To with To(z) = (11/n) for all
x E [n] and (ii) the mixing time of the transition matrix M is Tiix (mix(M) = X(Q)
log(n)
Sketch. Set Jay = D(x) + D(y). For pair (x. v) E E, before the downscaling, the pairwise (xc, y)cooparrioon corresponds to the random coin (D(y) / Jay; / and let D(y) > D(x). After the downscaling, this coin becomes (locally) almost fair, i.c. (D(z) ( Jay + Eay: (()))(())n))))
Hence, the modified transition matrix M can be written as M D ② Q + Q [Eny], where D is a symmetric matrix with D Day min (D(r,, D(y) + D(y) D Dyz Q is the Laplacian matrix of the graph Ge and [Exy] is a matrix with entries Exy where Ery is only non-zero in the modified transitions x + y. i.e., if Pay > Pyr then May = Q(x, y) (D(x)/ /Ja + Exy): for this pair, we set Suz = Finally, Q a [Exy] denotes the modified Hadamard product² between Q and [Say]- Due to the accuracy of the learning algorithm, we have that Kryl = O(1/ Vn).
We analyze (i) the stationary distribution and (ii) the mixing time. For Part (i), the chain M remains irreducible and the detailed balance equations of M satisfy Pay/Pyz= D(y) (Dx)/(D(y) D(z)). Since D is an e-relative approximation of D with = O(1 it holds that for any x E [n]: D(x) E [1 c. 1).. Hence, the unique stationary distribution To satisfies: (x(2)/ /o (v) E for any x, y E [n]. So, must be the case that ((x) = ((1mm)
O (n) +
it suffices to show (by Lemma 9) that (i) the minimum value of the stationary distribution is O(1/n) and (ii)
For Part (ii), in order to show that the mixing time is of order (llo(())/\(Q)
the absolute spectral gap ((M) of M satisfies T(M) = ((A(Q)). where x(Q) is the minimum non-zero eigenvalue of the Laplacian matrix Q. The first property follows directly from the closeness of the stationary distribution of M to the uniform one. We now focus on the latter. Our goal is to control the absolute spectral gap l'(M). In fact, this matrix can be seen as a perturbed version of the matrix D 2 Q we discussed in the beginning of the proof sketch. The perturbation noise matrix E = Q o [Syy] is a matrix whose entries contain (among others) the approximation errors use Weyl's inequality [Taol2] in order to control the absolute spectral gap of M. This inequality gives a crucial perturbation bound for the singular values for general matrices. Since the matrix M can be seen as a perturbation (as we discussed previously), we can (informally speaking) use Weyl's inequality to control the singular values After some algebraic manipulation, we derive that I(M) = (()(()).
[Ezy]. Hence,
So, a single iteration of the parameterized CFTP algorithm with transition matrix M (see Line 5 of Algorithm 3) guarantees that with expected number of N = Ö (M) Ô (n log(n) (QQ)) samples, it reaches Line 12 with a sample y = (1) that is generated by the parameterized CFTP algorithm (the iterations in Line 4). We then have study the quality of the outpul sample y- Crucially, by the utility of the standard CFTP algorithm, the law of y is the normalized measure that is proportional to D D/D, i.e., (v())= = (D(u)/ (Dt))/D()/////) EpE(n) D(x)/'((x) (this is the stationary distribution of the modified random walk). Hence. we cannot simply output y. For this reason, we perform rejection sampling. Specifically, as we will see, a single execution of Algorithm 2 either produces a single sample distributed as in D with some known probability or fails to output any sample with probability - p (this is because we do not sample from D but from an almost uniform distribution). If the rejection sampling process is successful, then the while loop (Line 4) of Algorithm 3 will break and the clean sample will be given as output. One can show that O(n) iterations of the parameterized CFTP algorithm suffice to generate perfect sample. Hence, the total sample complexity is of order On log(n) (1) log(n/ (// (()) (at each step 8' = =0(5/n)) We continue with sketch behind the rejection sampling process of Line 13 of Algorithm 2.
We have that (QoA) zy
QayAay, (Qo (Q=A) xz
EyEts Qay

---

Claim 1 (Sample Quality and Rejection Sampling). Algorithm 2, with input the output of the Learning Phase, outputs a state z E [n] with probability proportional to D(z) or outputs I. Moreover, Algorithm 3 outputs perfect sample from 'D with probability I.
To see this, set A Eyena D(y)/D(v). At the end of Line 11, Algorithm 2 outputs x oc / ((x), since the unique stationary distribution is ((z) of the CFTP guarantees that the outputs state follows the stationary distribution. For the sample x, we perform a rejection sampling process, with acceptance probability D(x)). Algorithm has n + 1 potential outputs: It either prints 2 [n]] or 1 indicating failure. The arbitrary sample x [n] is observed with probability ((x) D(x)= = DA.)/A. The remaining probability mass is assigned to I. We claim that the output of Line 6 of Algorithm 3 has law D. Observe that the whole stochastic
(D(=))/((=))/A and the utility
process of Algorithm 3 outputs x E [n] with probability Ei Pr[Reject]' Pr(æ is Accepted] =
D(z)/A =i= Pr| Pr(Rejoct]', where Pr Pr[Reject] = Eye[m) D(u)
- A (0, 1). As result, we get that the probability that is the output of the above stochastic process is D(x).
D(v) (1 (1-D(y)
4
Conclusion
We close with an open question: Is the bound Ó(n²/A(Q) tight? The main difficulty is that is not clear how to obtain lower bound against any possible exact sampling algorithm. We would like to mention that the dependence on 1/A(Q) is expected and intuitively unavoidable. This term is connected the mixing time. Let us become more specific. The (sample) complexity of our proposed method (n²2/((Q)) The term 1/x(Q) appears due to the mixing time of the (transformed) Markov chain. The complexity of CFTP is ((TTmix). Hence, any CFTP-based exact sampler (or more broadly random walk based algorithm) will have that kind of spectral dependence.
Similarly, a dependence on the support's size n necessary in general. Note that the structure the target distribution 2> is crucial: if the target is uniform (or generally "flat"), then bound of order (()) is obtained by the naive CFTP method; for distributions with modes, achieves quadratic dependence on n. The sample complexity of a potential (not necessarily random- walk based) exact sampling algorithm will depend Q. but might achieve a sample complexity not directly dependent on X(Q). The unclear part is our algorithm's 's dependence on n. While our algorithm attains a bound of (nn²), it is not obvious whether an algorithm with sample complexity o(n²) exists.
algorithm
Similarly, it is interesting to ask whether there are (efficient) ways to transform the chain in order to get a faster sample corrector. Our learning method finds a vector p (input of Algorithm 2) that makes the re-weighted distribution close to uniform. Is it possible to find another p (without our learning algorithm) such that (i) when transforming the chain with p, we obtain fast mixing chain; and (ii) the success probability in the rejection sampling step will be sufficiently high?
This work provided theoretical understanding to perfect sampling from pairwise comparisons. We believe it is an interesting direction to experimentally evaluate our proposed methodology.
We mention that this work is purely theoretical and has no negative societal impact.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for useful remarks and comments on the presentation of our manuscript. This work was supported by the Hellenic Foundation for Research and Innovation (H.FR.I.) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procurement of high-cost research equipment grant", project BALSAM, HFRI- FM17-1424.
10

---

References
[ACCL044 Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. data reconstruction. In International Symposium Algorithms and Computation, pages 16-27. Springer, 2004.
[ACK15a] Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. Adaptive Estimation in Weighted Group Testing. In Proceedings of the 2015 IEEE International Symposium on Information Theory, ISIT 15, pages 21-2-0. IEEE Computer Society, 2015.
[ACK15b] Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A Chasm Between Identity and Equivalence Testing with Conditional Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM '15, pages 449-466, 2015.
[AJ21] Konrad Anand and Mark Jerrum. Perfect sampling in infinite spin systems via strong spatial mixing. arXiv preprint arXiv:2106. 15992, 2021.
[APA18] Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal. Accelerated spectral ranking. In International Conference on Machine Learning, pages 70-79. PMLR, 2018. URL: pdf.
mlr. press//80.. /ttp////////aaaa////////////////
[BC18] Rishiraj Bhattacharyya and Sourav Chakraborty. Property Testing of Joint Distributions using Conditional Samples. Transactions on Computation Theory, 10(4):16:1-16:00, 2018.
[BC20] Siddharth Bhandari and Sayantan Chakraborty. Improved bounds for perfect sampling of k-colorings in graphs. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 631 631-642, 2020.
[BDNP21] Amnb Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas. Efficient statistics for sparse graphical models from truncated samples. In International Conference on Artificial Intelligence and Statisties, pages 1450-1458. PMLR, 2021.
[BGJ 10] Arnb Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhod- nikova, and David P Woodruff. Lower bounds for local monotonicity reconstruction from transitive-closure spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithmss and Techniques, pages 448-461 Springer 2010.
[BLR93] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/corrctiing with applica- tions to numerical problems. Journal of computer and system sciences, 47(3):549-595. 1993.
[Bre96] Richard Breen. Regression models: Censored, sample selected, or truncated data, volume 111. Sage, 1996.
[BT52] R.A. Bradley and M.E. Terry. Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons. Biometrika, 39:324, 1952.
[Can15] Clément L. Canonne. Big Data on the Rise? - Testing Monotonicity of Distributions. In Proceedings of the 42nd International Colloquium Automata, Languages, and Programming, ICALP '15, pages 294-305, 2015.
[Cat12] Manuela Cattelan. Models for paired comparison data: A review with emphasis on dependent data. Statistical Science, pages 412-433, 2012.
[CCK+19] Clément L Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random Restrictions of Biigh-Dimnnsioal Distributions and Uniformity Testing with Subcube Conditioning. CoRR, abs/1911 2019.
[CGR18] Clément L Canonne, Themis Gouleakis, and Ronitt Rubinfeld. Sampling correctors. SIAM Journal on Computing, 1773-1133 2018.
[Coh16] A. Clifford Cohen. Truncated and censored samples: theory and applications. CRC press, 2016.

---

[DGTZ18] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Efficient Statistics, High Dimensions, from Truncated Samples. In 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 639-649. IEFF, 201 8.
[DGTZI9] Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Computationally and Statistically Efficient Truncated Regression. In Conference on Learning Theory (COLT), pages 955-9999999 960, 2019.
[DHKN17] Shaddin Dughmi, Jason D) Hartline, Robert Kleinberg, and Rad Niazadeh. Bernoulli factories and black-box reductions in mechanism design. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 158-169, 2017. URL: https://arxiv peteeiivvoor//ppee org/pdf 1703. 04143. pdf.
[DKNSO1] Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pages 613-622, 2001.
[DKTZ21] Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, and Emmanouil Zam- petakis. A statistical taylor theorem and extrapolation of truncated densities. In Confer- ence on Learning Theory, pages 1395-1338. PMLR, 2021.
[DRZ20]
Constantinos Daskalakis, Dhruv Rohatgi, and Manolis Zampetakis. Truncated linear regression in high dimensions. arXiv preprint 1xXiv:2007.45533 2020.
[FGY19] Weiming Feng, Heng Guo, and Yitong Yin. Perfect sampling from spatial mixing. arXiv preprint arxiv:/907 000300633, 2019.
[FHOO] James Allen Fill and Mark Huber. The randomness recycler: a new technique for perfect sampling. In Proceedings st annual symposium on foundations of computer science, pages 503-511. IEEE, 2000.
[FH10] Johannes Fürnkranz and Eyke Hüllermeier. Preference learning and ranking by pairwise comparison. In Preference learning, pages 65-82. Springer, 2010.
[FJO+15] Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Faster Algorithms for Testing under Conditional Sampling. In Proceedings of the 28th Anmual Conference on Learning Theory, COLT '15 pages 607-636. 2015.
[FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient algorithms for learning from coarse labels. In Conference on Learning Theory, pages 2060-2079. PMLR, 2021.
[FKT20] Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Efficient parameter estimation of truncated boolean product distributions. In Conference on Learning Theory, pages 1606. PMLR, 2020.
[FV86] Michael A Fligner and Joseph S Verducci. Distance Based Ranking Models. Journal of the Royal Statistical Sociery. Series B (Methodological), pages 359-369, 1986.
[Gal97] Francis Galton. An examination into the registered speeds of American trotting horses. with remarks on their value as hereditary data. Proceedings of the Royal Society of London, 62(379-387)330--315 1897.
[GJL19] Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the lovász local lemma. 66(3), 2019.
[GLR18a] Rong Ge. Holden Lec, and Andrej Risteski. Beyond log-concavity: provable guarantees for sampling multi-modal distributions using simulated tempering langevin monte carlo. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 1858-7867, 2018.
[GLR18b] Rong Ge Holden Lee, and Andrej Risteski. Simulated tempering langevin monte carlo ii: An improved proof using soft markov chain decomposition. arXiv preprint arXiv:1812.00793, 2018.
12

---

[GLT20] Evangelia Gergatsouli, Brendan Lucier, and Christos Tzamos. Black-box methods for restoring monotonicity, International Conference on Machine Learning, pages 3463-3473, PMLR, 2020.
[GM99] Peter J Green and Dunean J Murdoch. Exact sampling for bayesian inference: towards general purpose algorithms, Bayesian statistics, 6:301-321, 1999.
[GTZ17] Themistoklis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Faster Sublinear Algorithms Using Conditional Sampling. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms,, SODA '17, pages 1743-1757. SIAM, 2017.
[HJ12] Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge university press, 2012.
[HOX14] Bruce Hajek, Sewoong Oh, and Jiaming Xu. Minimax-optimal inference from partial rankings. Advances in Neural Information Processing Systems, 27:1475-1483, 2014.
[HS00] Olle Häggström and Jeffrey E Steif. Propp- wilson algorithms and finitary codings for high noise markov random fields. Combinatorics, Probability and Computing, 9(5):425 439, 2000.
[HSW21] Kun He, Xiaoming Sun, and Kewen Wu. Perfect sampling for (atomic) lov' "asz local lemma. arXiv preprint 1XXiv:207.003922 2021.
[Hub98] Mark Huber. Exact sampling and approximate counting techniques. In Proceedings of the thirtieth annual ACM symposium Theory of computing, pages 31 31-40, 1998.
[Hub04] Mark Huber. Perfect sampling using bounding chains. The Annals of Applied Probability, 14(2):734-75,, 2004.
[Hub16] Mark L. Huber. Perfect simulation, volume 148. CRC Press, 2016.
[Hun04] David R. Hunter. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1))384-406, 2004.
[HW71] David Lee Hanson and Farroll Tim Wright. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42(3):1079-1083, 1971.
[IZD20] Andrew Ilyas, Emmanouil Zampetakis, and Constantinos Daskalakis. A theoretical and practical framework for regression and classification from truncated samples. In International Conference Artificial Intelligence and Statistics, pages 4463 4473. PMLR, 2020.
[Jer03] Mark Jerrum. Counting, sampling and integrating: algorithms and complexity. Springer Science & Business Media, 2003.
JLYY11] Xiaoye Jiang, Lek-Heng Lim, Yuan Yao, and Yinyu Ye. Statistical ranking and combina- torial hodge theory. Mathematical Programming, 127(1):203-244 2011.
[JR13] Madhav Jha and Sofya Raskhodnikova. Testing and reconstruction of lipschitz functions with applications to data privacy. SIAM Journal on Computing, 42(2):700-731, 2013.
[JS221] Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. Perfectly sampling k 2 (8/3+o(1)) colorings in graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1589-1600,, 2021.
[JSV04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-ting approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51()):671-697 2004.
[Kaz11] 1] Gabriella Kazai. In search of quality in crowdsourcing for search engine evaluation. In European conference information retrieval, pages 165-176. Springer, 2011.
13

---

[Ken05] Wilfrid S. Kendall. Notes on perfect simulation. Markov chain Monte Carlo: innovations and applications. 7. 2005.
[KT19] Gautam Kamath and Christos Tzamos. Anaconda: A Non-Adaptive Conditional Sam- pling Algorithm for Distribution Testing, In Proceedings of the Thirtieth Annual ACM- SIAM Symposium on Discrete Algorithms, pages 679 093. SIAM, 2019.
[TTZ19] Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis. Efficient Truncated Statistics with Unknown Truncation. In 260th Anmual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1578-1595, IEEE, 2019.
[LOAF12] Miguel Angel Luengo-Oroz, Asier Arranz, and John Frean. Crowdsourcing malaria parasite quantification: an online game for analyzing images of infected thick blood smears, Journal of medical Internet research, 14(6):e2338, 2012.
[LP17] David A. Levin and Yuval Peres. Markov chains and mixing times, volume 107. Amer- ican Mathematical Soc., 2017. URL: https: / /www. stat. www.:sttttttttt..e.. berkeley..du/useee edu/users/ P0tooo///0O-PMMLLeeeiii---- Peren-eeeeeeeeeeeee Wiisse-imeer...... lff
[LSR21] Wanshan Li, Shamindra Shrotriya, and Alessandro Rinaldo. The performance of the mle in the bradley-terry- model in lo -loss and under general graph topologies. arXiv preprint arXiv:21 10022,, 2021. URL: https: //txx//xxvvv/////////////////xv/ org/ /a////////// abs/aass/111////////////./aaa//t 10825.
[Luc59] R.D. Luce. Individual Choice Behavior. Wiley, 1959.
[Mar96] John I. Marden. Analyzing and modeling runk data. CRC Press, 1996.
[MMS21] Ankur Moitra, Elchanan Mossel, and Colin P Sandon. Learning to sample from censored markov random fields. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3419-3451. PMLR, 15-19 Aug 2021.
[MP92] Enzo Marinari and Giorgio Parisi. Simulated tempering: new monte carlo scheme. EPL (Europhysics Letters), 19(6),51,, 1992.
[MP05] Elchanan Mossel and Yuval Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6):777-724, 2005.
[NOS12] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise comparisons. In Advances in neural information processing systems, pages 2474-2482, 2012.
[NOS17] Sahand Negahban, Sewoong Oh, and Devavrat Shah. Rank centrality: Ranking from pairwise comparisons. Operations Research, 656))266-2287 2017.
[NPO5] Serban Nacu and Yuval Peres. Fast simulation of new coins from old. Annals of Applied Probability, 15(1A):93-115, 2005.
[NP19] Sai Ganesh Nagarajan and Ioannis Panageas. On the Analysis of EM for truncated mixtures of two Gaussians. In 31st International Conference on Algorithmic Learning Theory (ALT), pages 955-960, 2019.
[Plc21] Orestis Plevrakis. Learning from censored and dependent data: The case of linear dynamics. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3771-3787. PMLR, 15-19 Aug 2021.
[PW96] James Gary Propp and David Bruce Wilson. Exact sampling with coupled markov chains and applications statistical mechanics. Random Structures & Algorithmss 91-2))2233 252, 1996. URL:
ist .eu..p.u.cee 1.1.46. 3607/arre--rrepltttppppp..
[PW98] James Gary Propp and David Bruce Wilson. How to get perfectly random sample from generic markov chain and generate a random spanning tree of a directed graph. Journal of Algorithms, 27(2):70-217 1998.
14

---

[RA14] Arun Rajkumar and Shivani Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data, In International Conference on Machine Learning, pages 118-126, 2014.
[RV13] Mark Rudelson and Roman Vershynin. Hanson-wrighh inequality and sub- gab-gaussian concentration. Electronic Communications in Probability, 18, 2013.
[SBB + 16] Nihar B Shah, Sivaraman Balakrishnan, Joseph Bradley, Abhay Parekh, Kannan Ramchandran, and Martin J Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. The Journal of Machine Learning Research, 17 (7(1):004--0955 2016. URL: https://jmlr arg/papers. ppppers/volmmelllllspppppppppppp /ollume1/
15-189 10099/1511000 189. pdf.
[SBGW16] Nihar Shah, Sivaraman Balakrishnan, Aditya Guntuboyina, and Martin Wainwright. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. In International Conference on Machine Learning, pages 11 11-20. PMLR, 2016.
[SS10] Michael Saks and Comandur Seshadhri. Local monotonicity reconstruction. SIAM Journal on Computing, 39(7):297722966, 2010.
[Tao12] Terence Tao. Topics in random matrix theory, volume 132. American Mathemati- cal Soc., 2012. URL: http:/ htttp://ww..ee /ttp///stttttt www.sstat.ula..comm www.. eolla.edu/yyvuuu htt.://ww.w....aee///////aaeaaaa
B00KS/TTaRanddoMMatrix. pdff
[Thu27] Louis I. Thurstone. A law of comparative judgment. Psychological review, (riie,34(4):273, 1927.
[Tro15] Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-234) 2015. URL: https://arxiv, org/pdf/ 1501.0155 www.0.151.......
[VY16] Milan Vojnovic and Seyoung Yun. Parameter estimation for generalized thurstone choice models. In International Conference on Machine Learning, pages 498-506, 2016.
[VYZ20] Milan Vojnovic. Se- Young Yun, and Kaifang Zhou. Convergence rates of gradient descent and mm algorithms for bradley-terry models. In International Conference on Artificial Intelligence and Statistics, pages 1254 1264. PMLR, 2020. URL: https: //arxiv.. org/ absaa/////0 00150.
[Wil00] David Bruce Wilson. How to couple from the past using read-once source of random- ness. Random Structures & Algorithms, 16(1):85-113, 2000.
[WJJ13] Fabian Wauthier, Michael Jordan, and Nebojsa Jojic. Efficient ranking from pairwise comparisons. In International Conference on Machine Learning, pages 109-117. PMLR, 2013.
[ZCKM20] Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Unknown mixing times in apprenticeship and reinforcement learning. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pages 430 439. PMLR, 03 06 Aug 2020. URL: https: https://proceediie http://pooceeen..ee/ee mlr, www.mmmrr........mmmmm...mmmm..e wwwps//eellp// 2w124/2aaay222..aammmmmm html.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have presented the assump- tions of our models in Section We have also explained future research directions that will further improve this work in the Conclusion paragraph at the end of the main body.
15

---

(c) Did you discuss any potential negative societal impacts of your work? [Yes] We have discussed that the Conclusion paragraph the end of the main body.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] We have specified the theoretical models we working on, see the Problem Formulation in Section 1.
(b) Did you include complete proofs of all theoretical results? [Yes] Due to space con- straints we have included the full proofs of the results the Appendix.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "t39R7easxKx", "reviewer": "Reviewer_PftA", "summary": "The paper studies perfect sampling from pairwise comparisons. The setup is the following:\n\nThere 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).\n\nAt 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).\n\nVery 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.\n\nStraight-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?). \n\nThere 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.\n\nThey 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. \n\nThe 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.", "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nIt 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.\n\nWeaknesses: \n\nI don't see any major weakness. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bLD2v25AXb4", "reviewer": "Reviewer_y8bp", "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.", "questions": "•\tDo you have ideas where your modified CFTP method could be useful? Even speculation would be interesting!\n\n•\tYour CFTP method requires an estimate of the target stationary distribution. What if the stationary distribution is known up to a normalizing factor?\n\n•\tpg. 8: how can we ensure that the modified transition probabilities correspond to a valid probability distribution? Please show this explicitly.", "limitations": "Yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "•\tThis 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.\n\n•\tThe writing is very good; the paper was a pleasant read!\n\n•\tNo experimental evaluation; would be nice to include to get an idea of how practical this is. \n\n•\tpg. 8: The beginning of the proof sketch of Lemma 5 could be broken up into more sentences.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RxKjudhJpqP", "reviewer": "Reviewer_BvYp", "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. ", "questions": "None.", "limitations": "None", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The problem is important, the results are original, and the paper is clearly written.\n\nWeakness: \n- The paper lacks any empirical verification, especially regarding how efficient the improved algorithm is in practice. \n- It would have been great to see the upper bound being matched by a lower bound.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "38A7ygjqj5", "reviewer": "Reviewer_RUQw", "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.\n\nThe 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$.\n\nThe 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. ", "questions": "The full version of the paper is well-written. The following are some minor points:\n- Lines 72-79: it is not clear at this point whether you are getting a comparison element w in {x,y}\n- Line 88: in L_2 norm -> in the L_2 norm\n- Line 217: give the full name of TCS\n- Algorithm 1, line 4: coallesced -> coalesced\n- Algorithm 1, line 12: define Be(...) (the definition only appears in Line 334, which is too late)\n- Line 309, why do you need to take the max? Doesn’t |1-f|<=eps imply |1-1/f| <= eps? (after rescaling eps)\n- Supplementary, Algorithm 4, line 4: coallesced -> coalesced\n- 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.\n- Supplementary, lines 877, 1152, 1172: missing the word ‘Proof’ at the beginning of the line\n- 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.\n", "limitations": "N.A.", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Technically strong, solid theoretical results. Obtained precise sampling not just approximate sampling.\n\nWeaknesses: 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.\n\nAdditional 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept