Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Paper has contributed the following
- 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
- Careful simulation is provided with decent performances even with small samples
- Paper is easy to follow and clearly written

This is a decent work and I believe is a good addition to the venue. 

- 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.
- Do we have some assumptions on $\chi^2$ approximations? A brief discussion on this would be good for users avoiding corner cases in practice.
limitations_and_societal_impact: not applicable to this work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.


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.

The 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.

Overall 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.

Strengths:
-------------------------------
> Gives new results for an interesting but under-explored direction in property testing.

> Approach could be useful in other settings where the distribution is supported on combinatorially large number of objects

Weaknesses
-------------------------------
> The guarantee of the efficient algorithm i.e, Theorem 5.4 seems arguably weaker than that of Theorem 5.2.

Comments/Questions for the Authors:
----------------------------------

> Line 33: that is -> that are

> Line 62: from computational -> from a computational

> Line 79: is devised -> was devised

> Line 129: access the -> access to the

> Remark 1: where is $N_k$ used in the definition? Reference for Mahonian number?

> 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 
parameter, 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?


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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). 

Overall, 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. 
1. 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.

2. 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)$.

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: **Main points:**

I believe the paper provides a detailed and well-structured response to a specific and interesting theoretical problem.
I have two main concerns with the work:

1) 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?

2) 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?

**Details:**

* Why is the set of all permutations on $m$ sometimes $S_m$ (e.g. l. 209), sometimes $\mathbb{S}_m$ (e.g. l. 122)?
* What is $\Omega(1/\epsilon^2)$ in l. 183? Is $\Omega$ supposed to be the cardinal of $\Omega$ here?

[r1] Assessing Goodness of Fit of Ranking Models to Data, Cohen and Mallows, 1983

-------------- AFTER READING THE OTHER REVIEWS AND THE RESPONSES

The authors adequately addressed the points I raised and I raised my score to weak accept.
However, 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.
limitations_and_societal_impact: Nothing to declare
review_title: null

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)