summaries: 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. 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. 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.   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. 
abstractText: 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 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 nonasymptotic 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.
authors.name: Róbert Busa-Fekete
authors.name: Dimitris Fotakis
authors.name: Manolis Zampetakis
references.authors: Nir Ailon Moses Charikar Alantha Newman
references.title: Aggregating inconsistent information: Ranking and clustering
references.venue: In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing,
references.authors: Mark Braverman Elchanan Mossel
references.title: Sorting from noisy information
references.venue: CoRR, abs/0910.1191,
references.authors: Róbert Busa-Fekete Eyke Hüllermeier Balázs Szörényi
references.title: Preference-based rank elicitation using statistical models: The case of Mallows
references.venue: In ICML,
references.authors: Róbert Busa-Fekete Balázs Szörényi Dimitris Fotakis Manolis Zampetakis
references.title: Optimal learning for mallows block model
references.venue: In International Conference on Computational Learning Theory (COLT),
references.authors: Clément L. Canonne
references.title: A Survey on Distribution Testing: Your Data is Big. But is it Blue? Number 9 in Graduate Surveys
references.venue: Theory of Computing Library,
references.authors: Siu-on Chan Ilias Diakonikolas Gregory Valiant Paul Valiant
references.title: Optimal algorithms for testing closeness of discrete distributions
references.venue: CoRR, abs/1308.3946,
references.authors: Ayala Cohen C.L. Mallows
references.title: Assessing goodness of fit of ranking models to data
references.venue: Journal of the Royal Statistical Society. Series D (The Statistician),
references.authors: Noel Cressie Timothy R.C. Read
references.title: Multinomial goodness-of-fit tests
references.venue: Journal of the Royal Statistical Society. Series B (Methodological),
references.authors: Constantinos Daskalakis Ilias Diakonikolas Rocco A Servedio
references.title: Learning poisson binomial distributions
references.authors: Persi Diaconis Bernd Sturmfels
references.title: Algebraic algorithms for sampling from conditional distributions
references.venue: Ann. Statist., 26(1):363–397,
references.authors: Ilias Diakonikolas Themis Gouleakis John Peebles Eric Price
references.title: Sample-optimal identity testing with high probability
references.venue: Electron. Colloquium Comput. Complex.,
references.authors: Michael A Fligner Joseph S Verducci
references.title: Distance based ranking models
references.venue: Journal of the Royal Statistical Society. Series B (Methodological),
references.authors: P.D. Grünwald
references.title: The minimum description length principle
references.venue: The MIT Press
references.authors: Robert W Keener
references.title: Theoretical statistics: Topics for a core
references.authors: Guy Lebanon Yi Mao
references.title: Non-parametric modeling of partially ranked data
references.venue: In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-First Annual Conference on Neural Information Processing Systems,
references.authors: E.L. Lehmann J.P. Romano
references.title: Testing Statistical Hypotheses
references.venue: Springer
references.authors: Bruce G. Lindsay Marianthi Markatou Surajit Ray
references.title: Kernels, degrees of freedom, and power properties of quadratic distance goodness-of-fit tests
references.venue: Journal of the American Statistical Association,
references.authors: Tyler Lu Craig Boutilier
references.title: Effective sampling and learning for mallows models with pairwisepreference data
references.venue: J. Mach. Learn. Res.,
references.authors: R. Luce P. Suppes
references.title: Handbook of Mathematical Psychology
references.venue: chapter Preference, Utility and Subjective Probability, pages 249–410. Wiley
references.authors: C. Mallows
references.title: Non-null ranking models
references.venue: Biometrika, 44(1):114–130
references.authors: Horia Mania Aaditya Ramdas Martin J. Wainwright Michael I. Jordan Benjamin Recht
references.title: On kernel methods for covariates that are rankings
references.venue: Electron. J. Statist.,
references.authors: John I. Marden
references.title: Analyzing and Modeling Rank Data
references.authors: Marina Meila Le Bao
references.title: An exponential model for infinite rankings
references.venue: Journal of Machine Learning Research,
references.authors: Sumit Mukherjee
references.title: Estimation in exponential families on permutations
references.venue: The Annals of Statistics,
references.authors: Frank Nielsen Vincent Garcia
references.title: Statistical exponential families: A digest with flash cards
references.venue: arXiv preprint arXiv:0911.4863,
references.authors: Liam Paninski
references.title: A coincidence-based test for uniformity given very sparsely sampled discrete data
references.venue: IEEE Trans. Inf. Theory,
references.authors: R. Plackett
references.title: The analysis of permutations
references.venue: Applied Statistics, 24:193–202
references.authors: Charvi Rastogi Sivaraman Balakrishnan Nihar Shah Aarti Singh
references.title: Two-sample testing on pairwise comparison data and the role of modeling assumptions
references.venue: IEEE International Symposium on Information Theory (ISIT),
references.authors: Mingxuan Sun Guy Lebanon Paul Kidwell
references.title: Estimating probabilities in recommendation systems
references.venue: In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics,
references.authors: Wenpin Tang
references.title: Mallows ranking models: maximum likelihood estimate and regeneration
references.venue: Proceedings of the 36th International Conference on Machine Learning,
references.authors: Gregory Valiant Paul Valiant
references.title: An automatic inequality prover and instance optimal identity testing
references.venue: SIAM Journal on Computing,
references.authors: L.H. Philip Yu
references.title: Jiaqi Gu
references.venue: and Hang Xu. Analysis of ranking data. Wiley Interdisciplinary Reviews: Computational Statistics
sections.heading: 1 Introduction
sections.text: Identity testing of discrete distributions [9, 11] is one of the most fundamental problem which consists of answering a 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 asymptotic regime which family hypothesis tests are often referred to as goodness-of-fit tests and are routinely used in data analysis [10]. In this work, we extend the identity testing setup to a more general domain that includes rankings over m items which can be viewed as a discrete distribution testing problem over a 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 [26, 11] that is ⌦( p n) where n is the domain size. Therefore we study an important subclass of ranking distributions, which is introduced by [20] and also known as the exponential family on rankings. The model has two parameters, the central ranking ⇡0 2 Sm and the spread parameter 2 [0, 1]. Based on these, the probability of observing a ranking ⇡ 2 Sm is proportional to d(⇡,⇡0), where d is a ranking distance, such as the number of discordant pairs, a.k.a Kendall’s tau distance. There are many applications of the Mallows model in Machine Learning, to name a few, label ranking [18], online learning [3], 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 a central problem in analysing output of ranking systems where the goal is to
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  decide whether the output ranking data deviates from some expected behaviour, or is biased towards some group of object to be ranked or it is indeed fair ([24, 20, 32] and see Chapter 3-4 of [22]).
  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 our 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-fit testing task can be tackled in the traditional asymptotic setting as well as in non-asymptotic scenario in an efficient way regardless whether the central ranking is known. We can summarize our main results as follows:
  • We devise a Uniformly Most Powerful Unbiased (UMPU) test for asymptotic case to test spread parameter with known central ranking ⇡0. • We show that, in general, the UMPU test can be converted into a 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 it is hard to apply even for medium sized data. • Next, we propose a non-asymptotic test that is optimal for small and easy to compute. • We also consider the case when the central ranking ⇡0 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 as 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 our algorithms for testing the spread parameter . In Section 6, we present tests where both parameter of Mallows model are tested. Experiments are in Section 7 and finally conclude the paper in Section 8.
sections.heading: 2 Related work
sections.text: The asymptotic testing has a long history [16] dating back to Pearson’s fundamental work. To come up with a 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, [8], however the domain size is m!, so this approach becomes hard to apply even for small m.
  The non-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 [11] which was further strengthened in [31] by showing that this lower bound is instance optimal. Those results imply a sample complexity of order ⇥( p m!/"2) in our ranking setting if we do not exploit the structure induced by Mallows model. In the non-asymptotic 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 a tight lower bound on the total variation distance. Optimal learning, however, does not necessarily imply optimal testing in general, as it 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 a 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 [20, Section 11], to test uniformity against a single parameter Mallows model in the non-asymptotic setting. His approach relies on a normal approximation of the sufficient statistic. Cohen and Mallows [7] presents a goodness of fit test for ranking data in a way the ranking data is handled as a sample from a discrete distribution with m! parameters. That is why their analysis is restricted to m = 3 and m = 4. In addition to this, the authors presented a goodness of fit test for pairwise marginals of various ranking models for larger m 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 [28].
sections.heading: 3 Preliminaries and Notation
sections.text: 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 = {M ,⇡ | 2 [0, 1],⇡ 2 Sm} with probability mass function p ,⇡0(⇡) =
  d(⇡,⇡0)/Z( ,⇡0) where and ⇡0 are the parameters of the model: ⇡0 2 Sm is the location parameter also called center ranking and 2 [0, 1] the spread parameter. Moreover, d(·, ·) is a distance metric on permutations, which for our paper will be the Kendall tau distance, that is, the number of discordant item pairs dK(⇡,⇡0) = P 1i<jm I {(⇡(i) ⇡(j))(⇡0(i) ⇡0(j)) < 0}. The normalization factor in the definition of the model is equal to Z( ,⇡0) = P
  ⇡2Sm p ,⇡0(⇡). When the distance metric d is the Kendall tau distance we have the identity Z( ,⇡0) = Z( ) =Qm 1
  i=1 Pi j=0
  j . Observe that the family of distributions as stated is not an exponential family because of the location parameter ⇡0. If we fix the permutation parameter then the family R(⇡0) = {M ,⇡0 | 2 [0, 1]} is an exponential family with natural parameter ✓ = ln . From now on, if we use the neutral parametrization, we shall write ✓, i.e. Z(✓) = Qm 1 i=1 Pi j=0 e
  j✓. The log partition function is denoted by ↵(✓) = logZ(✓). In Appendix A, we review the basic properties of exponential families which we use in our work.
  Metrics between distributions. Let p, q be two probability measures in the discrete probability space (⌦,A) then the total variation distance between p and q is defined as dTV (p, q) = 1 2 P x2⌦ |p(x) q(x)| = maxA2A |p(A) q(A)|, and the KL-divergence between p and q is defined as DKL (p||q) = P x2⌦ p(x) ln ⇣ p(x) q(x) ⌘ .
sections.heading: 4 Testing ranking distributions
sections.text: We shall consider two types of identity tests: asymptotic and non-asymptotic tests. In the asymptotic case, a set of observations and a significance level ↵ > 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 ↵, i.e. the probability of rejection must be below or equal to ↵ if the null hypothesis is true [16]. More concretely, assume that we are given a parametric family of ranking distribution R = {M✓|✓ 2 ⌦} where ⌦ denotes the set of parameters. The observation consists of n rankings Dn = {⇡1, . . . ,⇡n} from a ranking distribution M. The null hypothesis is H0 : M 2 R0 where R0 ⇢ R. As an alternative hypothesis, we consider H1 : M 2 R1(⇢ R) such that R0 \R1 = ;. Then the test is a function f : SnM 7! {0, 1} where 0 corresponds to the acceptance, and 1 to the rejection, such that probability of rejection E [f(Dn)]  ↵ whenever M 2 R0 where the expectation is with respect to M. Our goal is to find a test f for which the power f (M) = E [f(Dn)] for all M 2 R1 is as large as possible. We will deal with randomized test so we consider tests in the form of f : SnM 7! [0, 1] where the output means the probability of rejection.
  A test f is called most powerful for a given ↵ and M0 2 R1, if there is no test f 0 such that f (M0) < f 0(M0). 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 supM2R0 f (M)  ↵  infM2R1 f (M). The unbiased UMP test is referred to as UMPU test.
  In case of non-asymptotic setup, the input is a tolerance parameter " > 0 and significance parameter 2 (0, 1), and we assume that the tester has sample access to the unknown distribution M. An (", ) non-asymptotic testing algorithm outputs a sample size n and a test function f : SnM 7! {0, 1} such that, generating Dn from M, we have the following guaranties for f :
  1. if the null hypothesis H0 is true, then it outputs reject (f(Dn) = 1) with probability at most , i.e. E [f(Dn)]  2. if M 2 R1 such that dTV(M,R0) > ", then it outputs reject (f(Dn) = 1) with probability at least 1 where dTV(M,Ri) = infM02Ri dTV(M,M0)
  Given " and , we say that a testing algorithm is sample-optimal for R0 versus R1 , if no algorithm can have the same confidence guarantee using less samples. If a testing algorithm sample-optimal for any " and , we say that it is uniformly sample-optimal (USO).
  One can show that the existence of UMPU test implies the existence of sample-optimal non-asymptotic test as follows with a particular (", ).
  Proposition 4.1 If there exists a UMPU test fn with a given significance level ↵ for R0 versus R1 for sample size n, n = 1, 2, . . . , then one can define a sample-optimal non-asymptotic testing algorithm that outputs n and f on input = ↵ and
  "f = sup M2R1\R(f) dTV(M,R0) (1)
  where R(f) = {M 2 R1 : f (M) 1 }.
  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 2 R1 such that dTV(M,R0)  ".
sections.heading: 5 Testing spread parameter with known central ranking
sections.text: In this section, we will focus on testing the spread parameter when the central ranking is known.
sections.heading: 5.1 Asymptotic case: UMPU test for spread parameter
sections.text: 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.1 whose proof is deferred to Appendix C.
  Theorem 5.1 Let us define a test fn(Dn) = gn(T⇡0(Dn)) with T⇡(D) = P ⇡02D dK(⇡,⇡ 0) and 0  t1  t2 where gn(`) = {` /2 [t1, t2]} + c1 · {` = t1} + c2 · {` = t2} with c1, c2 2 [0, 1] such that
  1 ↵
  2 =
  X
  `2[t1,µ]
  (1 gn(`))PM 0,⇡0 (T⇡0(Dn) = `) = X
  `2[µ,t2]
  (1 gn(`))PM 0,⇡0 (T⇡0(Dn) = `) .
  where µ = EM 0,⇡0 [T⇡0(Dn)]. Then fn is an UMPU level ↵ test with sample size n for H0 : M 2 R0 = {M 0,⇡0} versus H1 : M 2 R1 = {M ,⇡ : 6= 0,⇡ = ⇡0}.
  Even if the UMPU test fn defined in Theorem 5.1 plays central role in the asymptotic regime, it is hard to compute exactly, as this is discussed next in Remark 1. However it can be approximated by using 2 distribution which is presented in Appendix D.
  Remark 1 (Computational complexity) To determine the critical region of the test fn, one needs to compute the distribution of the sufficient statistic T⇡0(Dn) based on n samples under null hypothesis that is defined as
  PM ,⇡ (T⇡(Dn) = `) = `
  Z( )n N(`, n) (2)
  where Nk = Nk(m) = #{⇡ 2 Sm : dK(⇡,⇡id) = k} is the Mahonian number 1. One can compute the Mahonian number in O(m2) time using the recursion formula. Similarly, N(`, n) can be computed using recursion in O(m2n) time. From practical point of view, it is more challenging to compute PM 0,⇡ (T (Dn) = `) for some ` that depends on the fraction of large integers. In this regime, the numerical error can get significant for large n or m.
  1https://oeis.org/A008302
sections.heading: 5.2 An optimal non-asymptotic test based on UMPU test
sections.text: To tackle the non-asymptotic case to test H0 : M 2 R0 = {M 0,⇡0} versus H1 : M 2 R1 = {M ,⇡0 : dTV (M ,⇡0 ,M 0,⇡0) > "}, first we convert the UMPU test fn into (", ) non-asymptotic test based on Proposition 4.1. For doing this, we pick the smallest n so as the dTV(M 0,⇡0 ,M ,⇡) " for where fn(M ,⇡) 1 . This algorithm is defined in Algorithm 1.
  Algorithm 1 Non-asymptotic test for spread parameter based on UMPU 1: Input: ", 2: n⇤ = min {n 2 Z+ : s(n) "} where s(n) = supM2R1\R(fn) dTV (M,M 0,⇡0) 3: Take n⇤ samples Dn⇤ and ouput fn⇤(Dn⇤)
  Based on 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 E.
  Theorem 5.2 The sample size n⇤ required by Algorithm 1 is at most 12"2 log 2 .
  According to Proposition 4.1, Algorithm 1 is a uniformly sample optimal non-asymptotic test, since it 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 learning of Mallows model in terms of total variation.
  Corollary 5.3 Any non-asymptotic testing algorithm which distinguishes H0 : M 2 R0 = {M 0,⇡0} from H1 : M 2 R1 = {M ,⇡0 : dTV (M ,⇡0 ,M 0,⇡0) > "} requires ⌦(1/"2) samples.
  The proof of Corollary 5.3 is presented in Appendix F. The upper bound given in Theorem 5.2, on the one hand is tight up to a logarithmic factor, and on the other hand it does not depend on m in an explicit way, but R(fn) indeed does which is used in Line 2 of Algorithm 1 for computing s(n).
  Algorithm 2 Non-asymptotic test for spread parameter 1: Input: ", 2: "L = min {x 2 [0, 0] : h(x) "} where h(x) = dTV (M 0,⇡0 ,M 0 x,⇡0) 3: "R = min {x 2 [0, 1 0) : h( x) "} 4: "0 = min{"L/2, "R/2}
  5: Take n 2 ⌦ ⇣
  log(1/ ) m"20 ⌘ samples Dn and solve r lnZ( ) 1nT⇡0(Dn) = 0 to obtain ̂
  6: If |̂ 0|  "0 Then Output 0 Else Output 1 . Based on Theorem 5.4
sections.heading: 5.3 Scalable non-asymptotic test based on optimal learning
sections.text: Algorithm 1 has nice optimality properties, however to solve the optimization in Line 2, the set R(fn) has to be computed, that requires to compute the distribution of the sufficient statistic for n samples which is not scalable according to Remark 1. 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 a known central ranking ⇡0, one can compute an estimate for ✓ = ln by finding the root of r lnZ(✓) 1nT⇡0(D) = 0. Since lnZ(✓) is monotone increasing in ✓ based on Theorem A.1 2), we can find an estimate ̂ such that |̂ | < in O(log(1/ )) time based on binary search, therefore we shall neglect the numerical error. If we are given enough sample, the parameter estimate ̂ determines a Mallows model that is close to the true one. We recall this result from [4] (see Theorem 7 therein for more details).
  Theorem 5.4 For any < 1, if n ⌦ log (1/ )/(m"20) , then P ⇣ |̂ |  "0 ⌘ 1 .
  Theorem 5.4 implies that with n ⌦ log (1/ )/(m"20) samples, we can estimate the true with additive error that is of order "0. This observation suggests a testing algorithm which is presented
  in Algorithm 2. The proposed testing algorithm first computes the neighborhood 0 for which the total variation is smaller than " 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 "0 = ⌦( p log(1/ )/m), Algorithm 2 requires a single sample.
  To show that the sample complexity O log (1/ )/(m"20) of Algorithm 2 is optimal, it is enough to show that it matches to the lower bound given in Corollary 5.3. In other words, we have to show that "0 is of order "/ p 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 > 0 such that, for any , 0 2 [0, 1] and for every ⇡ 2 Sm, it holds that
  1. if | 0|  c/m and , 0 > c, then dTV(M ,⇡,M 0,⇡) 2 ⌦( p m| 0|), 2. if | 0|  c/ p m and , 0 > c then dTV(M ,⇡,M 0,⇡) 2 ⌦( p m| 0|2).
  The proof of Theorem 5.5 is deferred to Appendix G. Theorem 5.5 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, dTV(M ,⇡,M 0,⇡) > " implies that "0 = ⌦("/ p m). Thus the sample complexity of Algorithm 2 is O(log(1/ )/"2) that matches the lower bound given in Corollary 5.3 up to a 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 1.The lower bound that is linear in the difference of the parameters seems to be a very tight approximation even if | 0 | 1/m, whereas the approximation based on the Hellinger distance, i.e. Theorem 5.5 seems to underestimate the total variation distance for small | 0 |. On the other hand, the liner lower bound does not hold for large value of | 0 |, and the lower bound based on Hellinger distances captures the non-linearity of the total variation for larger | 0 |.
  Remark 2 The Algorithm 1 and the Algorithm 2 are very close to each other when " is small enough and 0 is bounded away from 0 and 1. In this case the upper bound dTV
  M 0,⇡0 ,M 00,⇡0 
  p m | 0 00| is very tight and hence both the test and the sample complexity of the two tests are essentially the same. When " is larger or 0 is close to either 1 or 0 then the testing problem becomes easier and Algorithm 1 takes advantage of this fact and needs less samples, whereas Algorithm 2 requires the number of samples given by the worst-case bound.
  Remark 3 (Scalable implementation of Algorithm 2.) The optimization tasks defined in Lines 2 and 3 of Algorithm 2 can be solved by using binary search since the total variation distance is monotone increasing and decreasing function of "0 with 0 + "0 and 0 "0, respectively. Moreover, one can compute the total variation distance in an efficient way as dTV(M 0,⇡0 ,M ,⇡0) = 1 2 Pm(m 1)/2 `=0 N` `0/Z( 0) `/Z( ) . This implementation works for moderate number of items, i.e. m  30. However, based on Theorem 5.5, Algorithm 2 can be implemented in a more scalable way without computing the total variation distance. More detailed, Theorem 5.5 provides an easy way to decide whether the model with estimated parameter is "-close to the null model in terms of total variation distance.
sections.heading: 6 Testing for spread parameter with unknown central ranking
sections.heading: 6.1 Asymptotic case
sections.text: In this section, we consider that case when the null hypothesis consists of a single model H0 : M 2 R0 = {M 0,⇡0} and the alternative hypothesis set is H1 : M 2 R1 = {M ,⇡ : 6= 0 _ ⇡ 6= ⇡0}. Let us consider a hypothetical test which knows the central ranking ⇡ of the underlying model M and it always applies the f⇡n (Dn) = gn(T⇡(D)) where gn is defined in Theorem 5.1. The power of this test is clearly an upper bound for the UMPU tests for this testing problem– if there exists UMPU test at all– since we know that f⇡n is UMPU if ⇡ is known based on Theorem 5.1. However, one can show that in general there is no unbiased test in this case which follows from the following argument.
  Remark 4 (Non-existence of UMPU test.) If there exists an ↵ level unbiased test f for testing H0 : M 2 R0 = {M 0,⇡0} vs H1 : M 2 R1 = {M ,⇡ : 6= 0 _ ⇡ 6= ⇡0}, based on Theorem 5.1 and the unbiasedness property, it necessarily accepts all sample D for which T⇡0(D) 2 (t1, t2) where t1 and t2 is the border of the critical region of the ↵ level test f⇡0n . By setting ↵ small enough, the critical region of f⇡0n will include T⇡0({⇡0}) for some ⇡0 such that dK(⇡0,⇡0) 1. Consequently, f (M0,⇡0) = 0 < f (M 0,⇡0) = ↵ which means that the test is biased.
  Nevertheless, we will devise an easy-to-implement test with a small bias that is vanishing exponentially fast in n. To devise such a test, we need to get an estimate of the central ranking with high probability. To find the central ranking ⇡0 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 [1]. Instead, we shall consider an estimator of central ranking based average ranking which can recover the central ranking with high probability as follows.
  Lemma 6.1 Let Dn = {⇡1, . . . ,⇡n} is a set of rankings generated i.i.d. from M ,⇡ and let ⇡̄ is the ranking that sorts [m] descending order based on their average rank si = 1n Pn i=1 ⇡j(i). Then it holds that P(⇡̄ 6= ⇡)  e n(1 )/2+2 logm
  The proof is based on [2] and presented in Appendix C. We would like to note that [30] analysed P(⇡̄ 6= ⇡) by giving lower bound and upper bound algorithm which approach can be used as well. Based on Lemma 6.1, we can have a simple 2-stage test: 1) take first half of Dn to compute ⇡̄, if ⇡̄ 6= ⇡0 then reject else 2) apply f ⇡̄n using the rest of Dn. Let us denote this 2-stage test by f̄n which works with n samples. Based on Lemma 6.1, one can compute an upper bound on the bias of this test.
  Theorem 6.2 Using the notation above, for any ↵ 2 (0, 1/2) and n > 21 log 2 ↵m2 , it holds that f̄2n is an ↵ level test and its bias is at most 1/2e n(1 )/2+2 logm.
  The proof is presented in Appendix I. The power of f̄n is at least 1 ↵ if the the central ranking of the alternative hypothesis does not coincide with ⇡0.
sections.heading: 6.2 Non-asymptotic case
sections.text: Based on Lemma 6.1 it is easy to see that average ranking algorithm recovers the central ranking with O 1
  1 log m samples with probability at least 1 , thus it can be applied in the non-
  asymptotic case. This leads us to a two stage algorithm to test H0 : M 2 R0 = {M 0,⇡0} versus H1 : {M ,⇡ : dTV (M 0,⇡0 ,M ,⇡) > "} which first estimates the central ranking based on the average ranking algorithm, and then runs Algorithm 1 or 2 with the estimated central ranking. The sample complexity of this two stage algorithm is O(max{ 11 log(m/ ), 1 " log(1/ )}) which remains optimal up to a logm factor since the lower bound presented in Corollary 5.3 applies in this case as well.
sections.heading: 7 Experiments
sections.text: We shall present synthetic experiments to assess the performance asymptotic and non-asymptotic tests. Each result are computed based on 100 repetitions.
sections.heading: 7.1 2 approximation of UMPU test
sections.text: The goal of the first set of experiments is to compare the power of the non-asymptotic test fn defined in Theorem 5.1 based on exact computation of the distribution of the sufficient statistic and its 2 approximation. Figure 2 shows their power for various null and alternative hypothesis. We picked the central ranking to be the identity ranking, since it has no impact on the results. One can see that the approximation slightly deteriorates the power of fn for small sample size, but the difference is marginal for n = 50. We could not compute fn with m > 10 and n = 50 in python. However the 2 approximation can be run with larger m as well as n. As we can see from this experiment, the 2 approximations is accurate already for small sample size and small number of items.
sections.heading: 7.2 Testing parameters of Mallows model for m  30
sections.text: In the second experiments we compare Algorithm 1 and 2. To implement Algorithm 1, we need to compute s(n) = supM2R1\R(fn) dTV (M,M 0,⇡0), which is based on the distribution of the sufficient statistic. We used 2 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 s(n), the and 1 quantile of the distribution of sufficient statistic based on n samples need to be estimated, so the 2 approximation has to be good on the tails. With this heuristic, there is no performance guaranty for Algorithm 1, that is why it is interesting to test its performance empirically versus an optimal algorithm. The power of Algorithm 1 and 2 are shown in Figure 3. We run Algorithm 2 with log (1/ ) /(2m"20). There are 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(1/" log(1/ )). On the other hand, as we pointed out in Remark 2, these two tests are very close to each other when 0 is not close too neither 0 nor 1. It can be seen that for 0 = 0.5, the power of these two tests are very close to each other, and for 0 = 0.1 Algorithm 1 has higher power for almost the same number of samples. Note that we used an 2 approximation of Algorithm 1, whereas Algorithm 2 is based on exact computation. Hence, we can verify that the 2 approximation indeed does work well in our setting even for moderate m.
sections.heading: 7.3 Scalable implementation, using single sample
sections.text: As we observed Algorithm 2 requires only a single sample whenever "0 = ⌦( p log(1/ )/m). In addition to this, "0 goes to zero as m goes to infinity, since with a fixed ", the parameter " converges to when m goes to infinity. Therefore for large m single sample is enough for Algorithm 2. We tested this observation with large m. If we run Algorithm 1 and 2 on a single ranking, they boil down to a very simple algorithm which consists of estimating the based on a single sample and if the estimate is far from 0, i.e. |̂ 0| is bigger than a threshold, then it rejects. This threshold is computed by using 2 approximation for Algorithm 1 and based on Theorem 5.5 for Algorithm 2. Figure 4 shows the results for m 2 {100, 1000}. As we can see, very similar results can be obtained for large m like before for m  30, using only a 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 ⇡0, 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.
sections.heading: 7.4 Experiments with unknown central ranking
sections.text: 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 5. 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 if it is shown that this is an NP-hard problem.
sections.heading: 8 Conclusion and Future Work
sections.text: We introduced several identity tests for Mallows model. We had found that the 2 approximation does not deteriorate the performance of the exact UMPU test fn by a significant margin. Based on the asymptotic exact test, we devised a non-asymptotic test for which we applied the same 2 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 on a small number of samples when 0  0.5. This suggest a 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 1 with 2 approximation or Algorithm 2.
  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 a 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.
title: Identity testing for Mallows model