Identity testing for Mallows model
Authors: Robert Istvan Busa-Fekete
Dimitris Fotakis
Balazs Szorenyi
Manolis Zampetakis
Venue: NeurIPS 2021 Poster (2021)
Keywords: Identity testing
Mallows model
hypothesis testing

Abstract: In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the \emph{asymptotic} and \emph{non-asymptotic} settings. First we consider the case when the central ranking is known, and devise two algorithms for testing the spread parameter of the Mallows model. The first one is obtained by constructing a Uniformly Most Powerful Unbiased (UMPU) test in the asymptotic setting and then converting it into a sample-optimal non-asymptotic identity test. The resulting test is, however, impractical even for medium sized data, because it requires computing the distribution of the sufficient statistic. The second non-asymptotic test is derived from an optimal learning algorithm for the Mallows model. This test is both easy to compute and is sample-optimal for a wide range of parameters. Next, we consider testing Mallows models for the unknown central ranking case. This case can be tackled in the asymptotic setting by introducing a bias that exponentially decays with the sample size. We support all our findings with extensive numerical experiments and show that the proposed tests scale gracefully with the number of items to be ranked.


Identity testing for Mallows model
Róbert Busa-Fekete Google Research, New York, USA busarobi busarobi@google. com
Dimitris Fotakis
National Technical University of Athens, Greece fotakis$cs .ntu. gr
Balázs Szörényi Yahoo! Research New York, USA balazs. wwwrenyioiiiieeeee wyw.rreen@@yahooinnnoomm com
Manolis Zampetakis Department of Statistics University of California, Berkeley, USA mzampet edu
Abstract
In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the asymptotic and non-asymptotic settings. First we consider the case when the central ranking known, and devise testing the spread parameter of the Mallows model. The first one is obtained by constructing Uniformly Most Powerful Unbiased (UMPU) test in the asymptotic setting and then converting it into a samplc-optiml non-asymptotic identity test. The resulting test is, however, impractical even for medium sized data, because it requires computing the distribution of the sufficient statistic. The second non- asymptotic test is derived from an optimal learning algorithm for the Mallows model. This test is both easy to compute and is sample-optimal for wide range of parameters. Next, we consider testing Mallows models for the unknown central ranking case. This case can be tackled in the asymptotic setting by introducing a bias that exponentially decays with the sample size. We support all our findings with extensive numerical experiments and show that the proposed tests scale gracefully with the number of items to be ranked.
algorithms for
1 Introduction
Identity testing of discrete distributions |1| is one the most fundamental problem which consists of answering yes-or-no question about the closeness of some explicitly given distribution to an unknown distribution from which random samples are observed. This testing problem have been studied in the classical statistical literature [16], and several tests have been devised in the tests and extend the identity testing setup more
asymptotic regime which family hypothesis tests are often referred to as goodness-of routinely used in data analysis ITO. In this work, general domain that includes rankings over m items which can be viewed as a discrete distribution testing problem over domain with size m!. As a consequence, identity testing of ranking data without any assumption is not feasible, since lower bound is known for identity testing for discrete distribution 226 that is ((yn)) where n is the domain size. Therefore we study an important subclass of ranking distributions, which is introduced by 120 and also known as the exponential family on rankings. The model has two parameters, the central ranking To S,, and the spread parameter & [0, 1]. Based on these, the probability of observing ranking E S,, is proportional to (d),, where d is ranking distance, such as the number of discordant pairs, a.k.a Kendall's 's tau distance. There are many applications the Mallows model in Machine Learning, to name a few, label ranking [18], online learning B. recommendation systems [29 15), clustering [23]. The focus of this study is to devise identity tests for Mallows model that are scalable with the number of items m.. Identity testing is central problem in analysing output of ranking systems where the goal is to
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

decide whether the output ranking data deviates from some expected behaviour, or is biased towards
some group of object to be ranked or is indeed fair 20 32 and see Chapter 3-4 of (221).
The hypothesis testing literature that is related to Mallows model, and more generally to ranking distributions, such as Plackett-Luce 27 19 or Babington-Smith (22), is not extensive. In work, we partially fill this gap by devising hypothesis tests for the Mallows model. We focus on identity testing problem, where we assume that the ground truth parameters of a Mallows model are given; this corresponds to the null hypothesis. Our goal is to decide whether the data we observe is generated by the null model or by an alternative one. We show that this kind of goodness-of-ff testing task can be tackled in the traditional asymptotic setting as well as in non asymmpotttiic scenario in an efficient way regardless whether the central ranking is known. We can summarize our main results as follows:
We devise Uniformly Most Powerful Unbiased (UMPU) test for asymptotic case to test spread parameter ó with known central ranking To.
We show that, in general, the UMPU test can be converted into sample-optimal non-asymptotic test which result may be of independent interest. Based on this result, we come up with an optimal non-asymptotic test, however is hard to apply even for medium sized data.
Next, we propose a non-asympiotic test that is optimal for small & and easy to compute.
We also consider the case when the central ranking To is not given, but needs to be estimated, and devise tests for both testing setups.
We demonstrate the versatility of our algorithm running with large m on synthetic data, and we show that for large m 70 to test the spread parameter, only one single sample is enough.
The paper is organized follows. Related work is presented in Section 2 Then, we recall the Mallows model and introduce notations. In Section 4 we describe the asymptotic and non-asymptotic testing setups and present our result on the relation of these two settings. In Section 5 we present algorithms for testing the spread parameter ø. In Section
we present tests where both parameter of Mallows model are tested. Experiments are in Section and finally conclude the paper in Section g
2 Related work
The asymptotic testing has a long history [66] dating back to Pearson's 's fundamental work. To come up with asymptotic test for Mallows model is more challenging from a computational point of view than methodological point of view. Testing ranking distribution can be viewed as multinomial testing problem and thus applied, for example, g however the domain size is m!, so this approach becomes hard to apply even for small m.
The mon-asymptotic testing has also long history 9 6 5 and references therein, including testing for discrete data. Nevertheless, sample optimal tests for wide range of parameter had been only devised recently which was further strengthened in K1I by showing that this lower bound is instance optimal. Those results imply a sample complexity of order O @(vml/=²) in our ranking setting if we do not exploit the structure induced by Mallows model. In the non-asympiotic setting, testing and learning are related problems. There are several so-called "testing by learning" algorithm which first learns a model, and then decides whether the learnt model is close to the null model or far enough from it which requires tight lower bound on the total variation distance. Optimal learning, however, does not necessarily imply optimal testing in general, as is the case for identity testing of discrete distributions (see Subsection 6.6 of [5] for further discussion). Nevertheless, it turned out that for identity testing of Mallows model this is indeed to be the case for a wide range of parameters, since interestingly. upper bound for sample complexity of optimal parameter learning of Mallows model requires asymptotically as many samples as it is needed to show that two models are far from each other in terms of total variation distance in certain parameter regime. Optimal learning is recently devised for Mallows model by 4 which result we rely on.
The testing literature is very limited for ranking distribution in general. Mallows came up with an approximate solution, in 120 Section 11], to test uniformity against a single parameter Mallows model in the non- asypottiiiii setting. His approach relies on a normal approximation of the sufficient statistic. Cohen and Mallows 7 presents a goodness fit test for ranking data a way the ranking data is handled as a sample from a discrete distribution with mi! parameters. That is why their analysis restricted to m and m 4. In addition to this, the authors presented a goodness of fit test for pairwise marginals of various ranking models for larger including Mallows model, Placket-Luce

---

and the Thurstonian model, but their focus was to decide which model fits better to the data in terms of pairwise marginals. Whereas we were interested in testing the parameters of Mallows model with large m values. There are some recent paper for testing ranking data, but these works are not related to parametric ranking models. For example, [21 17 uses statistics based on permutation kernel functions for testing the equality of two ranking distributions in the asymptotic setting. Finally, there is a very recent paper which testing identity of preference matrices which are marginals of ranking distributions
PS
3 Preliminaries and Notation
Single Parameter Mallows Model. The Mallows model or, more specifically, Mallows Φ- distribution is a parametrized, distance-based probability distribution that belongs to the family of exponential distributions R = [Ma.= á [o, 1 E Sm with probability mass function Po.n. (T)) )d((, /Z(ó, TO) where é and To are the parameters of the model: To Sm is the location parameter also called center ranking and ó E [0, 1] the spread parameter. Moreover, d(.,-) is distance metric on permutations, which for our paper will be the Kendall tau distance, that is, the number of discordant item pairs dx (T, T') = Eiskess I (i) x (T)) (i) T r()) < 0}.
The normalization factor in the definition of the model is equal to [ TO) = E Po.x. (T). When the distance metric d is the Kendall tau distance we have the identity Z(0, mb) = (())
I Σj= d³. Observe that the family of distributions as stated is not an exponential family because of the location parameter xo- If we fix the permutation parameter then the family R( = {Ma | Φ E [0, 1]} is an exponential family with natural parameter 0 In From now on, if we use the neutral parametrization, we shall write 0, i.c. Z(0) = -[ - EE= ed0 The log partition function is denoted by ax()= log (0)). In Appendix A we review the basic properties of exponential families which we use in our work.
Metries between distributions. Let p. 9 be two probability measures in the discrete probabil- ity space A) then the total variation distance between p and q is defined as drv (p. q) I Even (p(z) <(x)] = maxAed (p(A) - q(A)), and the KL-divergence between and q is de- p(a)
fined as DKL (pllg) EZen
4 Testing ranking distributions
We shall consider two types of identity tests: asymptotic and non-asymplotic tests. the asymptotic case, set of observations and a significance level a > 0 are given in advance, and then our goal is to come up with a test that maximizes the power, i.e. the probability of rejection, if the alternative hypothesis is true, subject to the given level of significance a, i.c. the probability of rejection must be below or equal to a if the null hypothesis is true [6]. More concretely, assume that we are given parametric family of ranking distribution R- [MM] E 22} where li denotes the set of parameters. The observation consists of n rankings D' = = (TTT,... ,T) from a ranking distribution M. The null hypothesis is Ho .M Ro where Ro R. As alternative hypothesis, we consider H1: : M E (C R) such that R2 n R2 = 0. Then the test is a function f : S% + {0. 1} where O corresponds to the acceptance, and to the rejection, such that probability of rejection E [f(D.)] S whenever M E Ro where the expectation is with respect to M. Our goal is to find a test I for which the power By(M) E (D(..)) for all M E R1 is large as possible. We will deal with randomized test so we consider tests in the form of f SR > [0, 1] where the output means the probability of rejection.
test f is called most powerful for a given a and M' E R2, if there is no test f' such that 3, < (MM'.. A test is uniformly most powerful (UMP) if it is most powerful for any distribution from the alternative hypothesis class. Furthermore, a test is unbiased, if supMER, 3Y( & a S inf MER, (MM. The unbiased UMP test is referred to UMPU test.
In case of non-asymptotic setup, the input is tolerance parameter & > and significance parameter 8 E (0, 1), and we assume that the tester has sample access to the unknown distribution M. An (c, 8) non-asymptotie testing algorithm outputs a sample size n and a test function f S + {0, 1} such that, generating D,, from M, we have the following guaranties for f:
3

---

1. if the null hypothesis Ho is true, then it outputs reject (f(D,) = 1) with probability at most 6, i.e. E (Px) 8
2. if M E R1 such that drv Ro) > E, then it outputs reject (f(D,) = 11) with probability at least 5 where (M,, R₂) = inf M'RR, dTv(),
Given & and ó, we say that a testing algorithm is sample-optimal for Ro versus Ri if no algorithm have the same confidence guarantee using less samples. If testing algorithm sample-optimal for any and 8, we say that it is uniformly samplc-optimal (USO),
One can show that the existence of UMPU test implies the existence of sample non non-asymptotic test as follows with a partieular (c,5).
Proposition 4,1 If there exists UMPU test fn with given significance level a for Ro versus R1 for sample size n, n = 2.2.... then one can define sample-optimal non-asymptotic testing algorithm that outputs n and f on input ò = and
sup dry(M,Ro)
Ef
MERIVR()
where R(f) (M : 21 8}.
The proof of Proposition 4.1 is deferred to Appendix B The opposite direction does not hold, since a non-asymptotic test does not guarantee anything for any M Ri such that drv (JM, Ro) e.
5
Testing spread parameter with known central ranking
In this section, we will focus on testing the spread parameter when the central ranking is known.
5.1 Asymptotic case: UMPU test for spread parameter
We will characterize an UMPU test for testing the spread parameter of Mallows model in the asymptotic setting. The UMPU test simply rejects the null hypothesis when the Kendall distance of the data deviates from its expected value under the null hypothesis by a certain margin. This is formalized by Theorem 5.I whose proof is deferred to Appendix C
Theorem 5.1 Let us define a lest fa(D,) = gn (Dx) with Ta = EEEED dx( r') and
S t I 12 where gm = 1il & [ti, tel) + ci . lfe = t1] + C2 1se = t2) with c1,0 E [0 such that
1 =
a
Σ(1 (1 - (1-g(())) Mag P (TrO (Dn) =)=
Σ (1 9n (() Mog (T (D,) = E).
2
where 11 = Magino (Dr)) Then Ju is an UMPU level a test with sample size for Ho : M E
Ro- (Moo versus HI, M E R2 {Maa Φ + do, =
Even if the UMPU test fn defined in Theorem 5.1 plays central role in the asymptotic regime, is
hard to compute exactly, as this is discussed next in Remark T However it can be approximated by
using X2 distribution which is presented in Appendix D
Remark 1 (Computational complexity) To determine the critical region of the test fnr one needs to compute the distribution of the sufficient statistic Txo (Dn)) based on samples under null hypothesis that is defined as
P P. (Dn)))=
Z(0)" N((,n)
where N₁. = Ng(m) #T E Sm dx( Tua) kJ is the Mahonian number One can compute the Mahonian number in O(m²) time using the recursion formula, Similarly, N n) can be computed using recursion in Omm2 time. From practical point of view, it is more challenging to compute P M (T(D,) = E) for some that depends on the fraction of large integers. In this regime, the numerical error can get significant for large n
https://oeis. http:///eessorrr000000/00 0008002

---

5.2 An optimal non-asymptotic test based on UMPU test
To tackle the non-asymptotic case to test Hu M Ro (M versus H1 M E R₁ {Ma... dry (Ma Mou.zol E), first we convert the UMPU test fr. into (s, non-asympiotic test based on Proposition 4.1 For doing this, we pick the smallest n so the drv (Mro Maxx) 8 for where By (Ma.))
6. This algorithm is defined in Algorithm
Algorithm Non-asymptooic test for spread parameter based on UMPU
Input: E,
2: n" min fn E Z+ s(n) 2 }) where s(n) = sup suR, (R(.)) dry (M, Moo,To)
3: Take n" samples D,- and ouput fn- (Dz-)
Based the concentration of the sufficient statistic of exponential family one can compute an upper bound on n²" The proof of Theorem 5.2 is deferred to Appendix
Theorem 5.2 The sample size n* required by Algorithm 1 at most 2 log T.
Algorithm I is uniformly sample optimal non asymptotii test, since was derived from an UMPU test. However, the upper bound for the sample complexity given in Theorem 5.2 might not be tight. To show that it is indeed tight, we apply the result of [4] regarding optimal leamning of Mallows model in terms total variation.
According to Proposition 4.
Corollary 5.3 Any non-asymptotic testing algorithm which distinguishes Ho -M E Ro (Moo.50) from H1 M E Rı = (Ma drv (Ma.so: Moo. > E} requires (211/²2) samples.
The proof of Corollary 5.3 is presented Appendix F
The upper bound given in Theorem 5.2 on the one hand is tight up logarithmic factor, and on the other hand it does not depend on m in an explicit way, but R(f,) indeed does which used Line of Algorithm for computing s(n).
Algorithm Non-asymptotic test for spread parameter
I: Input: 8
2: EL min fa E [0. øol h(x) 2 2} where h(x) drv (Moo Møn-z,50
3: ER = min fx E [0, Φo) h( h((x))= 2 =
4: éo = min
5: Take E Ω
1og(1/62 meg
samples D, and solve V In Z(d)
n LT
(Dn) obtain o
6: If 3 - Øol S co Then Output Else Output
Based on Theorem 5.4
5.3 Scalable non-asymptotic test based on optimal learning
the set R(fv) has to be computed, that requires to compute the distribution of the sufficient statistic for n samples which is not scalable according to Remark [ Motivated by this fact, next we devise a more practical algorithm with weaker optimality guaranty. We recall the result of [4] for optimal parameter learning of Mallows models. For known central ranking To. one can compute an estimate for 0 = In by finding the root of V In (()) ! T (D) = O. Since In Z(0) is monotone increasing in & based Theorem A.1 2), we can find an estimate ò such that l ol < y in (log(1/>)) time based on binary search, therefore
Algorithm| I has nice optimality properties, however to solve the optimization Line 2
shall neglect the numerical error. If we are given enough sample, the parameter estimate & determines a Mallows model that is close the true one. We recall this result from (see Theorem 7 therein for more details).
Theorem 5.4 For any & in 2 (log (1/6)/ (1/6)/(m=))) (m=z)), then P (10 Φ1 S <E) 2 8-
Theorem 5.4 implies that with 2 Ω (log (1/8)/me8)) samples, we can estimate the true & with additive error that is of order Eg. This observation suggests testing algorithm which is presented
5

---

in Algorithm The proposed testing algorithm first computes the neighborhood Φu for which the total variation smaller than E and then test whether the estimated spread parameter is in this neighborhood. Therefore this test falls in the family of "testing by learning". In fact, 4 Corollary 9] implies that if
(ololoog(//)///// Algorithm requires single sample.
To show that the sample complexity O (log (m/))(me²)) of Algorithm 2 is optimal, it is enough to show that matches the lower bound given in Corollary 5.3 In other words, we have to show that Eo is of order E/ /m. This claim is shown next in the Theorem 5.5 for a wide range of parameters.
Theorem 5.5 There exists a constant c such that, for any o, Φ E [0, 1] and for every л E Smo holds that
1. if 0'1 S c/m and Φ, o > c, then drv drv (L(mml - (')). (( r)
2. 1/ 00 S c/ v and o, o' > then dry (M.
The proof of Theorem 5.5 is deferred to Appendix Theorem 5.3 implies that Algorithm 2 is optimal when the difference of parameters of the alternative and the null hypothesis is smaller than c/m, because in this case, drv
Mod.aa) > é implies that 6 = (e(e/ mm) Thus the sample complexity of Algorithm 2 is (1)))())))/") that matches the lower bound given in Corollary 5.3 up to logarithmic factor. Albeit to show that Algorithm 2 is optimal for larger parameter values is an interesting open question. Nevertheless, we believe that this algorithm is optimal based on some numerical analysis that is shown in Figure lower bound that is linear in the difference of the parameters seems to be a very tight approximation even if 100 - øl >> 1/m, whereas the approximation based the Hellinger distance, i.e. Theorem 5.5 seems underestimate the total variation distance for small 1@b ø). On the other hand, the liner lower bound does not hold for large value of |do <). and the lower bound based on Hellinger distances captures the non- non- linearity of the
total variation for larger 10o Φ)
m 50
1.0
0.8
0.6
0.2
Holliprrmig mlp
AP
TV
0.0
0.2
0.6 90l. 0o = 0.5
L.0
Figure 1: Total variation distance and its approximation based on Theorem 5.5 σu = 0.3. The x-axis shows the difference in parameters, i.e. 1@0 - Φ).
We set m 50 and
Remark 2 The Algorithu 7 and the Algorithm 2 are very close to each other when E is small enough and Φn is bounded away from O and 1. In this case the upper bound drv : Mo), S /m (do- - %hl is very tight and hence both the test and the sample complexity of the two tests are essentially the same. When E is larger or do is close to either 1 or 0 then the testing problem becomes easier and Algorithm takes advantage of this fact and needs less samples, whereas Algorithm requires the number of samples given by the worst-case bound.
The optimization tasks defined in Lines and 3 of Algorithm D can be solved by using binary search since the total variation distance is monotone increasing and decreasing function of e' with do + e' and Φn - E', respectively. More- over, one can compute the total variation distance in an efficient way as dTv Maxto) = Et=0 m(m--1)/2 Ne o6 ((u) 6²| Z( This implementation works for moderate number of items, Le. m S 30. However, based on Theorem 5.3 Algorithm 2 can be implemented in a more scalable way without computing the total variation distance. More detailed, Theorem 5.3 provides an easy way to decide whether the model with estimated parameter is e-close to the null model in terms of total variation distance.
Remark 3 (Scalable implementation of Algorithm 2

---

6 Testing for spread parameter with unknown central ranking
6.1 Asymptotic case
In this section, we consider that case when the null hypothesis consists of a single model Ho M e Rg = [Mao.ro) J and the alternative hypothesis set is H1 : . E R1 = {M&g 6 * Φ V a of To Let us consider a hypothetical test which knows the central ranking of the underlying model M and it always applies the (Dn) = In (T~(() (D)) where 9r. is defined in Theorem 5.1 The power of this test is clearly upper bound for the UMPU tests for this testing problem- if there exists UMPU test at all- since we know that L is UMPU if и is known based on Theorem 5.1 However, one can show that in general there is unbiased test in this case which follows from the following argument.
Remark 4 (Non-existence of UMPU test.) If there exists an a level unbiased test f for testing Hg: : .M& E Ro = (M vs H1 .M E R1 = {Ma.= : + d0 т & mo), based on Theorem 5. and the unbiasedness property, it necessarily accepts all sample 'D for which T (D) E (21,12) where l and 12 the border of the critical region of the a level test f%o. By setting a small enough, the critical region of fn will include Tx (1x')) ) some nt such that dg(To, T²) 2 1. Consequently, (y(Masr)) = 0 < (M( = a which means that the test is biased.
Nevertheless, will devise easy-to-implement test with small bias that is vanishing exponen- tially fast in n. To devise such test, we need to get an estimate of the central ranking with high probability. To find the central ranking No that maximizes likelihood under Mallows model is known to be an NP-hard, since there is a reduction to the weighted feedback are set problem M. Instead, we shall consider an estimator of central ranking based average ranking which can recover the central ranking with high probability as follows.
Let Dn = { J is a set of rankings generated ii.d. from Ma. and let it is the ranking that sorts [m]] descending order based on their average rank s; = + >x (1). Then holds that Pf # σ) < 6 c=n(1_6))2+22 (22 22222o
Lemma 6.1
The proof based on 2 and presented in Appendix C We would like to note that 30 analysed P(# * ι by giving lower bound and upper bound algorithm which approach can be used as well. Based on Lemma 6. we can have a simple 2-stage test: 1) take first half of D, to compute मं To then reject else 2) apply f using the rest of D,. Let us denote this 2-stage test by fn which works with n samples. Based on Lemma 6. one can compute an upper bound on the bias of this test.
Theorem 6.2
Using the notation above, for any E (0, 1/2) and n > Fen is an a level test and its bias is at most 1/2e-n(11 ((10))/2222
2 log om it holds that T-o
2
The proof is presented in Appendix The power of fn is at least if the the central ranking of the alternative hypothesis does not coincide with mo.
6.2 Non-asymptotic case
Based on Lemma 6.1 it is easy to see that average ranking algorithm recovers the central ranking with 0 (1-- log 8) samples with probability at least 1 5, thus it can be applied in the non- asymptotic case. This leads us to two stage algorithm
test Ho M E Ro = [M versus H1 (Ma. : drv (Moo.ta; Mg. > e} which first estimates the central ranking based on the average ranking algorithm, and then runs Algorithm or with the estimated central ranking. The sample complexity of this two stage algorithm is O (max T-o log(m/5), 1og(1/))}) which remains optimal up to a log m factor since the lower bound presented in Corollary 5.3 appllie in this case as well.
7 Experiments
We shall present synthetic experiments to assess the performance asymptotic and non-asymptotic tests. Each result are computed based on 100 repetitions.
7

---

7.1 X" approximation of UMPU test
The goal of the first set of experiments is to compare the power the non-asymptotic test Jn defined in Theorem 5.1 based exact computation of the distribution of the sufficient statistic and its x2 approximation. Figure[Jshows shows their power for various null and alternative hypothesis. We picked the central ranking to be the identity ranking, since it has no impact the results. One see that the approximation slightly deteriorates the power of In for small sample size, but the difference is 10 and
marginal for = 50. We could not compute fn with approximation can be run with larger m as well as n. As we can see from this experiment, the X approximations is accurate already for small sample size and small number of items.
50 in python. However the x²
7.2 Testing parameters of Mallows model for m S 30
In the second experiments we compare Algorithm I and 2 To implement Algorithm I we need to compute s(n) suPMER; (R((.) drv Mo. which is based on the distribution of the sufficient statistic. We used x² approximation for the sufficient statistic when we compute s(n). More detailed, we carried out two nested binary searches, one over n and a second nested one over ø to compute s(n). To compute sn)), the ö and - 5 quantile of the distribution of sufficient statistic based on n samples need to be estimated, so the x² approximation has to be good on the tails. With this heuristic, there no performance guaranty for Algorithm ① that is why it is interesting to test its performance empirically versus an optimal algorithm. The power of Algorithm | and and2an are shown in Figure 3 We run Algorithm 2 with log (1/8) (2mme))- There some general trends revealed by these experiments. First, note that the sample sizes are not increasing with m, as one we expected since the sample complexity of both algorithm is O (l/)).))). On the other hand, as we pointed out in Remark 2 these two tests are very close to each other when do is not close too neither 0 nor 1. It can be seen that for ΦD 0.5, the power of these two tests are very close each other, and for | has higher power for almost the same number of samples. Note that we used
Φu = 0.1 Algorithm an x2 approximation of Algorithm whereas Algorithm 2 is based on exact computation. Hence, we can verify that the x² approximation indeed does work well in our setting even for moderate m.
7.3 Scalable implementation, using single sample
As we observed Algorithm 2 requires only a single sample whenever Eo 22( 1og(1/8)/m)) In addition to this, eo goes to zero as goes to infinity, since with a fixed e, the parameter the converges to e when m goes to infinity. Therefore for large m single sample is enough for Algorithm 2 We tested this observation with large If we run Algorithm and 2 to a very simple algorithm which consists of estimating the @ based on a single sample and the estimate is far from on. i.c. lô Φol is bigger than a threshold, then it rejects. This threshold is computed by using x² approximation for Algorithm I and based Theorem 5.5 for Algorithm 2 Figure 4 shows the results for mn E {100, 1000]. As we can see, very similar results can be obtained for large like before for m S 30, using only single ranking which indeed shows that these testing algorithms do scale gracefully with m. For an intuitive explanation, our tests for the spread parameter extract information about & from the outcome of pairwise comparisons between items in wo, this is how the Kendall-tau distance is computed. The larger m. the more pairwise comparisons available that is why these tests can work based on a single sample intuitively.
single ranking, they boil down
rample sire: 20, m 5
rample stre: 30, mis
sample size: 50, mis
sample stee: 50, mi
1.0
1.0
244
222
0.2
3.0
2.4
022
0.6
0.5
0.5
0.05 based on = {10, 50} random rankings. The axis presents parameter & of the underlying model. The solid lines shows the power of the exact test fn wheres the dashed ones shows the power of the approximate test when the likelihood ratio is approximated by x" distribution.
Figure 2: The power of asymptotic tests with m E {5, 10} and on E (0.1,0.5,0.9)
8

---

#sample: 134/106
Power
Power of Agg
24:
0.4
Psample:
#sample:
6A
Figure 3: Power function for non-asymptotic tests. The null hypothesis is de 0.51, 0.9] and E = 0.1, = 0.05. The sample size required by algorithms and is shown in the title of the plots, respectively.
100
100
100
10
Ahmo
0.8
Algorithm 1
10
Algor thm
0.8
Algor thm
Algorithm
0.8
Algor thm
0.6
0.6
0.6
0.4
0.4
0.3
0.2
0.2
0.1
0.0
0.00
0.05
0.10
3.15
0.20
0.40
0.45
0.50
0.55
0.60
0.50
0.85
0.50
2.95
1.00
1000
m 1000
m 1000
10
1.0
Alger thm
Algonthi Algorithm
Algorittm
Algor thm
0.8
0.8
Algorichm
9.6
0.2
0.0
0.50
0.55
0.00
0.35
0:50
0.50
0
Figure 4: Power function for non-asympiotic tests with m E (100, 1000) by using single ranking
as input. The null hypothesis do E (0.1, 0.9] and 0.1, 8 0.05.
10a
Sample size
10a
102
= 0.1
$ 0.5
10a
0.9
10a
10a
102
10a
104
Number of items (m)
Figure 5: The sample size with error bar that average rank algorithms requires for recovering the central ranking of Mallows model with various number of items ranged from 5 to 10000.

---

7.4 Experiments with unknown central ranking
In the next set of experiments, we test the average ranking algorithm to recover the central ranking. We run this algorithms with different input sample size and estimate their accuracy, i.e. how many times they can recover the central ranking. The results are shown in Figure D Note that recovering the central ranking can be done based on relatively small number of examples, that is we need only 100 to recover the central ranking with high probability, even it is shown that this is an NP-hard problem.
8 Conclusion and Future Work
We introduced several identity tests for Mallows model. We had found that the x² approximation does not deteriorate the performance of the exact UMPU test fn by a significant margin. Based on the asymptotic exact test, we devised non-asymptotic test for which we applied the same x² approximation and we had found that this test achieves similar result to the non-asymptotic test based on optimal learning. Our results clearly show that scalable identity test for Mallows model is indeed feasible even for m = 1000, since the spread parameter can be tested based on a single ranking when m is large and, moreover, the central ranking can be also recovered based samples when Φp < 0.5. This suggest very simple and scalable approach for identity testing of ranking data that generated from Mallows model: take 100 rankings, estimate the central ranking on 100 rankings, and use only a single sample to test the spread parameter by using either Algorithm with x" approximation or Algorithm
small number of
One interesting future direction is to explore hypothesis testing for the Generalized Mallows Model 12]. Apart from testing for the vector of the spread parameters, it would be interesting if we can test whether the samples come from a simple Mallows model, with the alternative that the samples come from Generalized Mallows Model.
Acknowledgments and Disclosure of Funding
Dimitris Fotakis is supported by the Hellenic Foundation for Research and Innovation (H.F.R.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.
References
[1] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. In Proceedings of the Thirty-sevntth Annual ACM Symposium Theory of Computing, pages
2005.
[2] Mark Braverman and Elchanan Mossel. Sorting from noisy information. CoRR, abs/0910.1 2009.
[3] Róbert Busa-Fekete, Eyke Hüllermeier, and Balázs Szörényi. Preference-basse rank elicitation using statistical models: The case of Mallows. In ICML, volume 32 of JMLR Workshop and Conference Proceedings, pages 1071-1079. JMLR.org, 2014.
[4] Róbert Busa-Fekete, Balázs Szörényi, Dimitris Fotakis, and Manolis Zampetakis. Optimal learning for mallows block model. In International Conference on Computational Learning Theory (COLT), pages ??-??, 2019.
[5] Clément L. Canonne. A Survey on Distribution Testing: Your Data Big. But is it Blue? Number 9 in Graduate Surveys Theory of Computing Library, 2020.
[6] Siu-on Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant. Optimal algorithms for testing closeness of discrete distributions. CoRR,
2013.
[7] Ayala Cohen and C. I.. Mallows. Assessing goodness of fit of ranking models to data. Journal of the Royal Statistical Society. Series D (The Statistician), 32(4):361-374, 1983.
10

---

[8] Noel Cressie and Timothy R. C. Read. Multinomial goodness-of of-ss fit tests. Journal of the Royal Statistical Society. Series (Methodological), 46(3):440 1984.
[9] Constantinos Daskalakis, Haa Diakonikolas, and Rocco A Servedio. Learning poisson binomial distributions. Algorithmica, 72(1):316-357, 2015. 2015.
[10] Persi Diaconis and Bernd Sturmfels. Algebraic algorithms for sampling from conditional distributions. Ann. Statist., 26(1):363-39, 02 1998.
[11] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Sample-optimal identity testing with high probability. Electron. Colloquium Comput. Complex., 24:133, 2017.
[12] Michael A Fligner and Joseph S Verducci. Distance based ranking models. Journal of the Royal Statistical Society. Series (Methodological), pages 359-369, 1986.
[13] P.D. Grünwald. The minimum description length principle. The MIT Press, 2007.
[14] Robert W Keener. Theoretical statistics: Topics for a core course. Springer, 2011.
[15] Guy Lebanon and Yi Mao. Non-parametric modeling of partially ranked data. Advances in Neural Information Processing Systems 20, Proceedings of the Twenty- First Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 857-864, 2007.
[16] E.L. Lehmann and J. P. Romano. Testing Statistical Hypotheses. Springer, 2005.
[17] Bruce G. Lindsay, Marianthi Markatou, and Surajit Ray. Kernels, degrees of freedom, and power properties of quadratic distance goodness-of-fit tests. Journal of the American Statistical Association, 109(505):395-10,, 2014.
[18] Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwise- preference data. J. Mach. Learn. Res., 15(1):3783-3829 2014.
[19] R. Luce and P. Suppes. Handbook of Mathematical Psychology, chapter Preference, Utility and Subjective Probability, pages 449.410. Wiley, 1965.
[20] C. Mallows. Non-null ranking models. Biometrika, 44(1):114-133 1957.
[21]
Horia Mania, Aaditya Ramdas, Martin J. Wainwright, Michael I. Jordan, and Benjamin Recht. On kernel methods for covariates that are rankings. Electron. J. Statist., 1222):5337-2577 2018.
[22] John I. Marden. Analyzing and Modeling Rank Data. Chapman & Hall, 1995.
[23] Marina Meila and Le Bao. An exponential model for infinite rankings. Journal of Machine Learning Research, 11:3481-3518 2010.
[24] Sumit Mukherjee. Estimation in exponential families on permutations. The Annals of Statistics, 44(2):853 875, 2016.
[25] Frank Nielsen and Vincent Garcia. Statistical exponential families: A digest with flash cards. arXiv preprint arXiv:0911.4863, 2009.
[26] Liam Paninski. coincidence- based test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory, 54(10):4750-4755 2008
[27] R. Plackett. The analysis of permutations. Applied Statistics, 24:193-202, 1975.
[28] Charvi Rastogi, Sivaraman Balakrishnan, Nihar Shah, and Aarti Singh. Two-san saoo-samle testing on pairwise comparison data and the role of modeling assumptions. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 1271-1276, 2020.
[29] Mingxuan Sun, Guy I Lebanon, and Paul Kidwell. Estimating probabilities in recommendation systems. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2011, Fort Lauderdale, USA, April 11-13, 2011, pages 734-742, 2011.
11

---

[30] Wenpin Tang. Mallows ranking models: maximum likelihood estimate and regeneration. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6125-6134. PMLR, 09-15 Jun 2019.
[31] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM Journal Computing, 46(1):429-453 2017.
[32] L. H. Philip Yu, Jiaqi Gu, and Hang Xu. Analysis of ranking data. Wiley Interdisciplinary Reviews:
Computational Statistics, 2019.
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]
(c) Did you discuss any potential negative societal impacts of your work? [No] We hope there none.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [No] We used synthetic data.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] We reported the repetitions from the error bar is clear for binary error. Otherwise we reported error bar.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (e.g., code, data, models) 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 assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're
using/curating? [N/A]
(c) 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, applicabl???
[N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "jLFK7y61KfY", "reviewer": "Reviewer_vdjk", "summary": "The authors propose asymptotic and non-asymptotic test for the hypothesis $\\phi = \\phi_0$ where $\\phi$ is the spread parameter of a Mallows model. To do that, they first prove that we can derive a non-asymptotic test from an asymptotic one (Prop 4.1), then show that an optimal unbiased UMP test can be defined is too computationally costly when the number of items to order ($m$) is large (Theorem 5.1), due to the calculation of the probability in Eq (2).  To alleviate this limitation, they propose to estimate the most likely spread parameter $\\hat{\\phi}$ which allows them to efficiently approximate the quantity in Eq (2) and control the deviation (Theorem 5.4). Finally, the authors address testing for spread with unknown central ranking, by showing that the average rank aggregation is asymptotically close to the central ranking. Finally, they confirm the efficiency of their method in experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Main points:**\n\nI believe the paper provides a detailed and well-structured response to a specific and interesting theoretical problem.\nI have two main concerns with the work:\n\n1) I do not neglect your contribution to ranking models, but I believe there is a lack of motivation for this problem in your paper when presenting to a machine-leaning conference. The related problems of ranking aggregation does not suffer from this, since ranking aggregation is a practical problem in many situations. Can you identify a significant (or several) practical problems where testing for the spread value of a Mallows model is important?\n\n2) I am not perfectly familiar with reference [r1] (added below), but they assess the goodness of fit of parameters to the Mallows Model in particular, a problem very related to testing,  and they also deal with the case of large $m$, as you do in your paper. Could you explain why your contributions are significant wrt their propositions?\n\n**Details:**\n\n* Why is the set of all permutations on $m$ sometimes $S_m$ (e.g. l. 209), sometimes $\\mathbb{S}_m$ (e.g. l. 122)?\n* What is $\\Omega(1/\\epsilon^2)$ in l. 183? Is $\\Omega$ supposed to be the cardinal of $\\Omega$ here?\n\n[r1] Assessing Goodness of Fit of Ranking Models to Data, Cohen and Mallows, 1983\n\n-------------- AFTER READING THE OTHER REVIEWS AND THE RESPONSES\n\nThe authors adequately addressed the points I raised and I raised my score to weak accept.\nHowever, I still believe that the reviews that we (the reviewers) were unable to put the theoretical contribution in perspective, which requires a thorough knowledge of ranking models (which is rare due to the focus on score-based approaches). It would be interesting to have the additional opinion of someone that is very familiar with testing ranking models.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing to declare", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "eLEXQ0Zj7Rl", "reviewer": "Reviewer_E5Zn", "summary": "The paper studies the problem of identity testing for the Mallows model, which is a popular parametrized distribution over rankings. It gives identity testers for the non-asymptotic and asymptotic setting which are sample optimal but not necessarily computationally efficient. It also gives a efficient identity tester, with weaker guarantees, and also extends the results to the setting where the central ranking is not unknown.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the problem of identity testing for the Mallows model which is a well studied family of distributions over rankings i.e, given a set of samples (rankings) $\\pi_1,\\ldots,\\pi_n$ drawn from $M(\\pi_0,\\phi)$ with $\\pi_0$ being the central ranking and $\\phi$ being the spread parameter, the objective is distinguish where $\\{\\pi_i\\}$'s are drawn from $M$ or from a distribution which is $\\epsilon$-far from $M$ in the total variation metric. The main contributions of the paper are that it gives testers for the asymptotic and the non-asymptotic settings, which are then shown to be sample complexity optimal. The paper then extends these results to the setting where the central ranking $\\pi_0$ is not unknown.\n\nThe main technical challenge here is that naïve application of identity testers from present literature will result in algorithms whose sample complexity have prohibitive dependence on the size of the ranking $m$, and therefore a more fine tuned approach is needed which exploits the properties of the distribution function of the mallows model. Using a careful argument, the authors first explicitly characterize the analytic form of an unbiased asymptotic tester, which is then subsequently used to give a (computationally expensive) sample complexity optimal tester for the asymptotic setting. They also give a computationally efficient tester which is based on the testing-by-learning approach, using recent results on learning Mallows block models.\n\nOverall I think this is an interesting direction to explore in the setting of property testing, and the paper provides a nice set of first such results for the setting of Mallows model.\n\nStrengths:\n-------------------------------\n> Gives new results for an interesting but under-explored direction in property testing.\n\n> Approach could be useful in other settings where the distribution is supported on combinatorially large number of objects\n\nWeaknesses\n-------------------------------\n> The guarantee of the efficient algorithm i.e, Theorem 5.4 seems arguably weaker than that of Theorem 5.2.\n\nComments/Questions for the Authors:\n----------------------------------\n\n> Line 33: that is -> that are\n\n> Line 62: from computational -> from a computational\n\n> Line 79: is devised -> was devised\n\n> Line 129: access the -> access to the\n\n> Remark 1: where is $N_k$ used in the definition? Reference for Mahonian number?\n\n> Section 5.3: I am a bit confused about the main result of this section, as far as I understand, Alg. 2 gives a tester for the spread \nparameter, but then it's not clear if it immediately yields an $(\\epsilon,\\delta)$-identity tester as well? For e.g., how is it dealing with $(\\pi,\\phi)$ pairs where $\\phi = \\phi_0$, but $d_K(\\pi_0,\\pi)$ is large?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "X_KSL_uKu0n", "reviewer": "Reviewer_6PWT", "summary": "This paper is concerned with the hypothesis testing of Mallows ranking models, which is parametrized by a central ranking and a spread parameter. The authors proposed two different methods: one based on the classical Type I error, and the other based on an optimal learning approach. The authors presented a complete theory regarding testing Mallows rankings, and also provided empirical results to corroborate the theory. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers the problem of hypothesis testing for a popular ranking model -- Mallow's ranking model. The paper fills in the gap of testing procedures for a large random discrete object (ranking with a large size of items), which is important for the practical use. The authors then proposed two different approaches: one through the classical test framework involving significance level and power, and the other based on an optimal learning procedure. Both approaches were treated rigorously, and the results are scientifically correct. Empirical results were also provided, and showed that the proposed optimal learning testing is valid for testing a Mallows ranking with $1000$ items (this is considered to be large in testing ranking models). \n\nOverall, I like the paper and enjoy reading it. Below I provide a few more references that the authors could add, and compare with their results. \n1. Some nice development of Mallows model, and related models were made in late 80s by Fligner and Verducci, see \"Distance based ranking models\", Journal of the Royal Statistical Society. Series B (Methodological), pp. 359–369, 1986, and \"Multistage ranking models\", Journal of the American Statistical association, 83(403):892–901, 1988.\n\n2. Regarding testing Mallows model with unknown central ranking, the authors indicated that the MLE is NP hard, and proposed to use the average rank instead. In particular, they proved in Lemma 6.1 a 'rate of convergence' of the average rank estimate. I would like to point out a parallel result for the MLE, which could be found in \"Mallows Ranking Models: Maximum Likelihood Estimate and Regeneration\", Proceedings of the 36th International Conference on Machine Learning (ICML 2019) PMLR 97, 6125-6134.  There Theorem 3.2 provides a lower and an upper bound for $\\mathbb{P}(\\pi_{MLE} \\ne \\pi)$. It may be worth pointing out that Lemma 6.1 is much better for large random models, since the rate is $m^2 \\exp(-Cn)$ while for the MLE the rate is $m! \\exp(-Cn)$.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "2faGy-BwYO", "reviewer": "Reviewer_CfhN", "summary": "Paper provided a UMPU test on Mallows model's spread parameter. And based on that paper introduced many variations and discussed their properties. Paper contributes to the testing literature by providing a UMPU test and associated math tools.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Paper has contributed the following\n- A UMPU test on the based point hypothesis testing, based on which some finite sample variations and other sorts such as central ranking unknown is discussed, with mathematical properties provided\n- Careful simulation is provided with decent performances even with small samples\n- Paper is easy to follow and clearly written\n\nThis is a decent work and I believe is a good addition to the venue. \n\n- Figure 2 is hard to read. Venue format requirement may played a role here. Maybe increase the graph size and / or change data presentation is going to be better when submitting long ver to journals.\n- Do we have some assumptions on $\\chi^2$ approximations? A brief discussion on this would be good for users avoiding corner cases in practice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable to this work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Mallows model are a popular distribution of rankings. This papers studies the problem of testing whether the underlying distribution is equal to a known Mallows model or is far from it. This is a clean question, and is a novel avenue for applying goodness-of-fit testing. The paper is above the bar for NeurIPS. 
Decision: Accept (Poster)