Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies the problem of uniformity testing in ranking data: that is testing whether an unknown distribution is uniformly random over possible rankings OR it is epsilon away from it (in total variation distance). Noting that this problem in general is quite hard, they consider the special case where the alt-hypothesis is that the unknown distribution is a single parameter  Mallows model (i.e., exponential decay of permutations around an unknown fixed ranking). 

The key contributions of the paper include a testing method for this problem with O(1/\sqrt(m)) samples. They also show that they can adapt their algorithm to enable local differential privacy. 
main_review: As I mentioned, the central contributions of the paper include a testing method for this problem with O(1/\sqrt(m)) samples (they also show only two samples are needed when m, the number of items,  is large enough -- which also follows from the above result (?). Why not just present this one result instead of two). They also show that they can adapt their algorithm to enable differential privacy. 

The underlying idea behind this (non-private) result is quite simple to describe: partition the items into m/2 random disjoint pairs and construct a random variable that accounts for the deviations between the pairs of items. The idea is if the null hypothesis is satisfied value of the above random variable is large, else if the unknown distribution follows the mallows model, then the value is significantly small. 

I like the simplicity of the algorithm -- which means it can useful in practice. On the flip side, I wonder if the assumption on alternative hypothesis class being a single variable exponential around a fixed ranking makes the problem too simple and uninteresting. The proof structure seems to following standard concentration analyses. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
The paper considers the problem of uniformity testing for permutations against the Mallows model with an unknown central ranking. More precisely, given random samples  $\mathcal D_n=\{\pi_1, \pi_2, \ldots \pi_n\}$  from $S_m$ (the collection of all permutations of size $m$), the authors determine the sample complexity for testing whether $\mathcal D_n$ is generated from the uniform distribution on $S_m$ versus whether $\mathcal D_n$ is generated from some Mallows model with total variation distance $\epsilon$ from the uniform distribution. They provide an algorithm for this testing problem with sample complexity $O(1/\sqrt m)$.  The authors then study this problem under privacy constraints. In particular, they provide algorithms  for uniformity testing in the Mallows model under central as well as local differential privacy constraints. The results are validated by simulation experiments. 

main_review: 

The problem studied in the paper is interesting and relevant. However, the paper often omits important details and it is difficult to parse the  sample complexities. It is unclear what the dependencies on the various parameters are and how close they are to the optimal, which makes it difficult to appreciate the technical contributions of the paper. Moreover, the main ideas of the papers are packed in to the algorithms and it is not clear how some of the quantities are computed. 


Specific Comments: 


I am not sure if this is because of space constraints, but a few important recent references on uniformity testing problems are missing. For example: 

G. Valiant and P. Valiant, An automatic inequality prover and instance optimal identity testing,  SIAM J. Comput., 46(1):429--455,  2017. 

T. Batu and C. Canonne, Generalized uniformity testing, FOCS, 2017.


Page 3, Line 120: In the definition of the class $\mathcal R_1$, it would be good to mention that $\phi$ can vary over $[0, 1)$ and the central permutation $\pi_0$ over $S_m$.  


Page 4, Algorithm 1: How does one compute the function $\phi_\epsilon$ efficiently? Is there an expression for the TV distance between Mallows models that is being used here and also how is the supremum calculated? It would be good see some discussion regarding the running time of the algorithms. 

Moreover, it might be mathematically more accurate to define $\phi_\epsilon$ as $\inf_{\pi_0 \in S_m} \sup_{\phi \in [0, 1]} \{ d_{TV}(\mathcal M_{1, \pi_0}, \mathcal M_{\phi, \pi_0}) > \epsilon \}$. 


Page 4, Line 174: The notation $X_{i(i+1)}^{\ell}$ is confusing. It would be better to have something like  $X_{i, (i+1)}^{\ell}$


Page 5, Algorithm 2: Why does the algorithm only consider inversions between consecutive pairs $i$ and $ i+1$? Why not consider  inversions between all pairs $i, j$? Does considering consecutive pairs simplify the analysis of the algorithm? 


Page 5, Theorem 5: I don't  understand how $\mu^2$ depends on $m$ and $\epsilon$. It should be explained why $\mu$ is constant in $m$. Moreover, what is the dependence of $\epsilon$ that comes out this sample complexity? Also, it is obvious that $\phi_\epsilon < 1$? 


The discussion following Theorem 5 is unclear and needs to be clarified. 


The classical problem where the central ranking is known should be highlighted more. For example, discussion in Section 7.2 is nice and very relevant, and should probably be mentioned earlier in the paper. 





limitations_and_societal_impact: 

As mentioned above, it is sometimes unclear how some of the quantities depend on the sample complexity. For example, what is the dependence on $\epsilon$ in the results? Is this dependence expected to optimal?

Also, it might be better to assume that $\delta$ is fixed. It is unlikely that the dependence on $\delta$ is optimal and it would significantly clean up the sample complexity in the private setting.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies uniformity testing for ranking data in which the alternative class is restricted to the Mallows model. In the non-private setting, the authors first give a uniformity tester that only needs two samples for large enough m (where m is the number of items over which the ranking is considered), then the authors give a general tester that works for arbitrary m. In the private setting, the authors give differentially-private uniformity testers for both the centralized and local models of DP. They provide synthetic experiments to support their theoretical results. 

main_review: Testing uniformity of data is a well-studied direction in property testing. There has also been recent work on testing uniformity under differential privacy constraints. In this work the authors focus on testing if a distribution is the uniform distribution over all permutations on m elements (called rankings) or epsilon far from this distribution in total variation distance, both in the standard setting and under central and local differential privacy. The collection of 
distributions that are far are considered in the Mallows model: a distribution over permutations is parameterized by parameters phi in [0,1] (the spread) and a fixed permutation pi0 (the center), and the probability mass function assigns mass to permutation pi that is a normalization of phi^{d(pi, pi0), where d is the Kental tau distance of two permutations, thus counting the number of inversions.

The paper starts with a simple test that picks two rankings from the given distribution, and correctly accepts/rejects as long as the parameter phi is large enough (>1-\Omega(m)).

Leveraging this simple test, the authors obtain a general test. The idea is to draw samples and estimate the variance of the relative ordering of m/2 pairs of items. They show that this is enough to distinguish between the two cases. 

Here, please discuss for what parameters the sample complexity is interesting. In many places (eg, abstract and conclusions) where the phi’s are suppressed your sample complexity is below 1! (m^{-½}). Please fix these typos everywhere and add a discussion about the tradeoffs between the parameters of the model and m.

To get the DP version, they first observe that by adding Laplace noise proportional to the sensitivity of the test statistic the query complexity would blow up by another factor of m^{3/2}/ To bring this down, the authors carefully add Laplacian noise to the previous algorithm only when the variance is well-behaved, namely it’s not too small and not too large. Achieving this step uses some ideas from [9]. Finally, achieving LDP appears to be much easier now, as one can add some randomized response to the output of the classical algorithm.

Originality 

Although uniformity testing has a vast literature, uniformity testing for ranking data in which the alternative class is restricted to the Mallows model has not been well-studied, so the results presented are novel. 

Quality
The paper is generally well-written, with full definitions and clear exposition. I have not verified the technical proofs in the supplemental material. 

Clarity
There are minor typos and grammatical errors sprinkled across the entire submission. For e.g., Line 88: ``Local private uniformity test is analyzed in [1] and had found that it can…’’ Please also see the comment above about the typos in the testing complexity. 


Significance
The paper would be interesting to the property testing, differential privacy and machine learning communities.



limitations_and_societal_impact: Yes/
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
The authors study the problem of differentially private (DP) uniformity testing for rankings:
are the rankings uniformly and randomly generated (under the null hypothesis) or are the rankings
generated in such a way that the distribution of rankings are $\epsilon$ far from the rankings generated under
the uniform distribution.
They present two main algorithms: 2SAMP (works in certain paramter regimes and uses two samples) and UNIF.
In Section 7, they present simulations on synthetic data to validate their methods.
main_review: Their results are obtained under the Mallows model, which is widely used in the ML rankings literature.
The model has two main inputs: $\pi_0$ and $\phi\in[0, 1]$. $\pi_0$ is a central ranking and
$\phi$ is the "spread" around this central ranking.

Algorithm 1 (2SAMP) is a uniformity tester that uses two samples and works only when $\phi\leq 1 - \Omega(1/m)$,
where $m$ is the number of items to be ranked.
Algorithm 2 (UNIF), on the other hand, works on any arbitrary $\phi$.

In Section 7, Figures 1, 2, and 3 serve to experimentally validate their methods, algorithms, and assumptions.

I believe that their work provides novel applications (to uniformity testing) of known methods in the DP literature. They provide both central and local DP algorithms for uniformity testing.

Minor Comments
==============

- Use of $\epsilon$s and $\delta$:
I think $\epsilon_0$ is used as the privacy parameter and $\epsilon$ is used for how
far from uniform the distribution of rankings is, under the alternative hypothesis.
And $\delta$s are used for significance? This might be confusing. [response acknowledged]

- Line 202 states that the variance of the Laplace is $8b^2$ for scale b. Shouldn't this be $2b^2$? [response acknowledged]


limitations_and_societal_impact: They address the limitations of 2SAMP compared to UNIF and vice versa.  Also, in the conclusion section, they mention some open questions.
review_title: null

Meta-review: Reviewers appreciated the natural and well-motivated problem under consideration, the simplicity and practicality of the proposed algorithms, and the general technical execution of the paper. They raised a few low-level technical concerns, primarily about notation and about details of subroutines used in the algorithms. These were sufficiently addressed in author feedback so as to reach a consensus to accept during discussion.
Decision: Accept (Poster)