Private and Non-private Uniformity Testing for Ranking Data
Authors: Robert Istvan Busa-Fekete
Dimitris Fotakis
Manolis Zampetakis
Venue: NeurIPS 2021 Poster (2021)
Keywords: uniformity testing
Mallows model
ranking

Abstract: We study the problem of uniformity testing for statistical data that consists of rankings over $m$ items where the alternative class is restricted to Mallows models with single parameter. Testing ranking data is challenging because of the size of the large domain that is factorial in $m$, therefore the tester needs to take advantage of some structure of the alternative class. We show that uniform distribution can be distinguished from Mallows model with $O(m^{-1/2})$ samples based on simple pairwise statistics, which allows us to test uniformity using only two samples, if $m$ is large enough. We also consider uniformity testing with central and locally differential private (DP) constraints. We present a central DP algorithm that requires $O\left(\max \{ 1/\epsilon_0, 1/\sqrt{m} \} \right)$ where $\epsilon_0$ is the privacy budget parameter. Interestingly, our uniformity testing algorithm is  straightforward to apply in the local DP scenario by its nature, since it works with binary statistics that is extracted from the ranking data. We carry out large-scale experiments, including $m=10000$, to show that these testing algorithms scales very gracefully with the number of items.

Private and Non-private Uniformity Testing for Ranking Data
Róbert Busa-Fekete Google Research, New York, USA
Dimitris Fotakis
National Technical University of Athens, Greece fotakis@cs ntua.gr gr
busarobi@google.co
Manolis Zampetakis
University of California, Berkeley, USA mzampet@berkelee. edu
Abstract
We study the problem of uniformity testing for statistical data that consists of rankings over m items, where the alternative class is restricted to Mallows models. Testing ranking data is challenging because of the size of the large domain that is factorial in m, therefore the tester needs to take advantage of some structure of the alternative class. We show that uniform distribution can be distinguished from Mallows model with O( samples based simple pairwise statistics, which allows us to test uniformity using only two samples, if m is large enough. We also consider uniformity testing with central and local differential privacy (DP) con- straints. We present a central DP algorithm that requires ((max(1/ 1//o, 1//m)), where eo is the privacy budget parameter. Interestingly, our uniformity testing algorithm is straightforward to apply to the local DP scenario, since it works with binary statistics that is extracted from the ranking data. We carry out large-scale periments, including m = 10, 000, to show that our uniformity testing algorithms scale gracefully with m.
Introduction
Testing whether the data conforms with a model is a fundamental problem in data analysis with large number of applications in machine learning and data science. A special case of testing the uniformity testing. i.e. to distinguish between the case that an unknown distribution accessible via samples uniform versus e-far from uniform. Uniformity testing of discrete distribution a long history with several applications, and it is well-understood differential privacy constraints
29 31
well as under
In this paper, we assume that the statistical data consists of rankings over m items. The testing problem that study is decide whether the data is generated from the uniform distribution over rankings, i.e. the probability of observing any ranking is 1/m!, or from a distribution that is e-far from the uniform one in terms of total variation distance. In general, this testing problem cannot be tackled based on polynomial sample complexity, because the domain size for ranking data is ml. Therefore, we restrict the alternative hypothesis class the Mallows model, introduced by [25] a.k.a. the exponential family rankings. The Mallows model is widely used in ranking statistics and machine learning. 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 (o) 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 Machine Learning, name a few, label ranking 24 online learning ( recommendation systems 30 23 and clustering (27
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Testing is a central problem in analysing output of ranking systems where the goal is to decide whether the output ranking data deviates from some expected behaviour, or biased towards some
group of object to be ranked or it is indeed fair [8 25 32 and see Chapter 3-4 of (26)). Significant attention has been attracted to machine learning systems and their ability to discriminate against minorities, historically disadvantaged populations, and other protected groups when allocating resources (e.g., loans) or opportunities (c.g., jobs). For example, the Fair Lending Act - a commonly used fairess requirement introduced in the USA- is explicitly created to impose such unbiasedness on financial companies. This policy even has to be respected in audience targeting in online advertising. Uniformity and parameter testing can be applied to practical settings where we want to collect/provide evidence that our ranking system has no bias towards some group of users.
In this work, we propose two tests to tackle uniformity testing with the Mallows model as alternative class of ranking distributions: one of these tests works with just two samples when the number of items m is large enough, and a more general one, with sample complexity O(1/ (1//m)), works for arbitrary m.
There are several applications where the data to be analyzed contains sensitive information. However, the data owner is willing release some results of analysis based on the data, without revealing information of the individuals. It may thus be of importance to guarantee that working with sensitive data needed to test a statistical hypothesis protects sensitive information about the individual records in the dataset. Differential privacy (DP) is one of the most commonly used privacy preserving framework 15 which has been adopted by several companies including Google [X], and Apple [R] Differential privacy requires that the output of an algorithm has to be statistically close on two similar datasets D and D' that differ in the value of one element which a ranking in our case. We consider the two most common version of DP: central and local DP. In the central model, a trusted curator stores the database, and she runs the algorithm which has DP guaranty to analyze the sensitive data and then the output of the analysis. i.e. accept or reject in case of hypothesis testing, is released to the public [6). Several alternatives to the central model have been proposed that relax the requirement that the users trust the curator to store their private data, for example local DP (LDP). In the local model, each user adds noise to her own data and responds to the analyst directly [I9]. Interestingly, our uniformity testing algorithms can be easily applied in the LDP setting. We can summarize our main results as follows:
We devise a uniformity test which works based on two samples when m is large enough (Subsection
We introduce a uniformity test that works for arbitrary m and has sample complexity O(m 112) (Subsection 4.2)
In the central DP setting, one can apply simple reduction approach which consists of drawing [1/eo] batches of data, and run a non-DP algorithm on one of the batch selected uniformly at random. This approach works well when m is large enough, since the uniformity testing can be solved based on two samples. However, we devise a uniformity test for the central DP setting which has better sample complexity than the reduction approach with data batches for small and medium m. This result is presented in Section
We devise a LDP algorithm as an easy extension of our non non-private algorithm, in Section 6
We demonstrate the versatility of our algorithm running with large m, including m 10000 on synthetic data, and we show that for large m very small deviation form the uniform can be detected with high confidence based on two samples in Section i
2
Related Work
Testing uniformity is one of the most fundamental problem in computer science. Goldreich and considered first uniformity testing problem as a property testing, however with L2 distance. approach that used total variation distance with sample complexity OVV/fe)) where d is the domain size, and it was shown to be optimal by with a restriction that E R(d-1/4). The test statistic used by this optimal test is based on number of bins into which just one sample has fallen. In principle, this test can be applied to ranking data, since the test statistic easy to compute. Nevertheless, the lower bound of this test, which Q ((vd/e2). suggests that it is not the proper choice of method even for ranking data with small m, since d = ml.
Ron 22
Paninski 2 came up with a coincidence-

---

The result of Paninski [29] was strengthen further by several authors including 12 11
so as the lower bound does work for general e and matching algorithmss are also provided. The plug-in based tests, for example [I], do estimate the distribution empirically and then it makes decision by thresholding the total variation distance between the uniform distribution and the empirical estimate. Surprisingly, this test is optimal for all c, 5 > O. Batu and Canonne ?l considered generalized uniformity testing for an arbitrary distribution with unknown domain size and provided a tester with sample complexity Odd2/3/e) fc9). Moreover, Valiant and Valiant [3 showed how achieve instance optimality, when we test arbitrary discrete distributions for uniformity. However, to adapt any of these tests to our setup is out of question since the size of our domain is m!! which is huge, and the test statistic, which is the total variation distance, is already challenging to compute for ranking data. Therefore, we need to come up with a uniformity test that takes advantage of the structure of the alternative hypothesis.
Testing with differential privacy has a solid literature as well. Jayadev Acharya and his colleagues studied uniformity testing with privacy constraint in depth. In [] the central DP model is analysed and shown that it can be tackled with O even
1) samples where eo is the privacy budget parameter. Local private uniformity test is analyzed in [ and had found that it can be tackled with ((k/(c eo samples. In a recent work [21, uniformity testing in local differential private setting was analysed with a special attention to the impact of the public randomness.
La + 24/Seg273 ccn
2//3
3 The Mallows Model, Testing and Differential Privacy
The 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. 6 E [0, 1], π E } with probability mass function Po,no (T) = ad(n,mo)) (Z To). where & and To are the parameters of the model: To E Sm is the location parame- ter also called center ranking and Φ E [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 dx (T,, x') = Ii
(i) - T (a) - x' r()) < 0}. The normalization factor in the definition of the model is equal to ((0) To) = > Po. (T). When the distance metric d
is the Kendall tau distance we have the identity Z(ò, mo) (0) II E== S).
Testing and Uniformity Testing. We assume a parametric family of ranking distribution R {Mo 0 E 22} where denotes the set of parameters. The observation consists of n rankings
D. = :TI....;TT!. from ranking distribution M. The null hypothesis is Ho :M E Ro where Ro C R. As an alternative hypothesis, we consider H1 M E RR R) such that Ro n RR, = Then the test is function f S + {0, 1J. where 0 corresponds to acceptance, and 1 to rejection. The imput of the tester (or the testing algorithm) is a tolerance parameter > 0 and a significance parameter& d (0. 1). We assume that the tester has sample access of the unknown distribution M E R. By definition, an (c, d) -ttter outputs a sample size n and a test function f : S + {0, 13 such that, generating D, from M. we have the following guaranties for f:
1. if the null hypothesis Ho is true, then it outputs reject (f(D,) = 1) with probability at most 6, i.e. EE [f())) 8.
2. if M E R2 such that dTv Ro) > e, then it outputs reject (f(,,) 1) with probability at least 1 - 8, where dTv(M, = M'ER, d'))
The testing problem at hand is called uniformity testing, when the null hypothesis is simple and consists of only the uniform distribution over the domain Sm. More concretely, in this study, we assume that the null hypothesis is the uniform model, which is itself a Mallows model with Φ = 1, thus Ho .M- E Ro [M1,mo with central ranking an arbitrary no E Sm- The alternative hypothesis class contains those Mallows models that are e-far from the uniform distribution, i.c. H1 M E R2 [Mar ddvv(M, Mo.x) > e}. where Sm is some given central ranking and Φ E [0, 1).
Differential Privacy. We also consider uniformity testing under privacy constraint. We work with two different privacy notions: central and local differential privacy. case of central differential privacy (CDP), the data is gathered at a so-called curator, who is trusted. The curator runs the tester,
3

---

which is required to output a response that is not too sensitive to small changes in the input. Small changes can be defined in many different ways for ranking data. We assume that the granularity of the data is whole rankings. With this in hand, we define the notion of CDP follows.
Definition 1 (Central DP Property.). A randomized algorithm A with domain Sm is 60)- differential private for all S C. [ange(A) and for all pairs of inputs D (..,.... Tn) and D'' that differs from in a single ranking, it holds that
P(A(D) E S) S P(A(D)) E SS + 80
If 8 0, the guarantee is called pure differential privacy.
We will also work with a more appealing privacy notion which is often called locally differential privacy (LDP). LDP is stronger privacy guaranty than CDP sense that the data is required be privatized before the tester can observe it. More detailed, the data is assumed to be distributed among peers and the peers add noise the data which noise can be modelled as a conditional distribution, a.k.a. mechanism, W (z (T) for some output space z E Z. The tester only observers the privatized data (zi..... Z₁., so in this case has no access to the original data as it is to be the case in CDP. The notion of LDP therefore can be formalized as a condition on (-I-))
Definition 2 (Locally differentially private.). mechanism W Sm x - (0, 1] eo-locally
differentially private if W satisfies
max max log W(Z W(z/T') S c0
ZEZ N. E8
We assume that each peer has the same mechanism, however there are several setup which assumes that the mechanism can be different for different peers. If public randomness is used by the tester, then the LDP guaranty is extended so as the worst-case log likelihood is computed over the domain of the public random process.
Definition 3 (Locally differentially private with public randomness). A set of mechanisms W., Sm x 2 (0, indexed by U which is the domain of the public random process, eg-locally differentially private if it holds that
max max log Wu(z(T) WEU BEZ a EBm. Wa(z(T') c0
Non-Private Uniformity Testing
4.1 Testing Uniformity of Mallows Models with Two Samples
First, we present a simple algorithm that draws two samples Ti and T2 and applics only if d, is bounded away from 1 by ((1/m). The algorithm computes the Kendall tau distance of a1 and TT. Under the null hypothesis, dx (T(1, R2) 2 m(m - 1)/4 Olym In(1/)),, with probability at least 1 - 5, because the distribution is uniform. Under the alternative hypothesis, dx (T1, S 2 Φx) + m In(1/8)) with probability at least 6, because the distribution is concentrated around some central ranking. This algorithm is referred as 2SAMP and is defined in Algorithm D We show that if o. I 1 2(1/m), can distinguish between the two cases by sufficiently large confidence.
Theorem 4. For all 8 0, if S
then Algorithm 2SAMP, defined in
m mm
Algorithm 7 uses samples and is an (c. Junifforiity test of Mallows models.
The proof is deferred to Appendix A An alternative way of interpreting the guarantee presented above is that for all m and d.. with m > T-o 7, Algorithm 2S is (e, (e, for uniformity
9
with significance 6 and power under an alternative model with spread parameter & at least 1 2e 7
We should also emphasize that we cannot test uniformity with less than 2 samples, even for very large values of c, since it is impossible to tell whether a single sample is uniformly distributed or not.
The computational complexity of Algorithm | is determined by the time required compute d Unfortunatcly, there is closed form of d. function of m and e. However, &e can be computed

---

Algorithm 2SAMP: Uniformity Test with Two Samples
I: Input: significance 8 O, tolerance > 0
2: Fix any To E Sm and let o. = supae jo. (M > c)
3: if 6e > m 61
8
then
4:
Output 1
O close to 1
5: Take samples which are denoted by Tı, T2 E Sm
6: If dx( m(m-1)
11/1/)) Then Accept Else Reject
12
efficiently, using dynamic programming and binary search. We first observe that the total variation distance of Mallows model to the uniform distribution can be computed in ((m²) time, using 2ym(m-1)/2
Z(Ø) Mah(i, m), where Mah(i, m)) denotes the i-th Mahonian number of order m (i.e., the number of permutations with m items at Kendal tau distance to the identity permutation). The Mahonian numbers of order can be computed in O(m²) time, using dynamic programming. while (6) has a closed form [2I]. Furthermore, the total variation distance of Mallows model to the uniform distribution decreases as & increases from 0 to 1. Hence, de be computed efficiently using binary search and the total variation distance computation above.
1
4.2 General Uniformity Testing Algorithm
Algorithm 2SAMP works only when &e S Q(1/m), or equivalently, assuming a fixed de. which tests uniformity for arbitrary o. and m. The idea is consider the relative positions m/2 disjoint random pairs of items in 1-6. 1+85
when m is large enough. Hence, we present Algorithm 2
( lm(1/8)
k == - 12
samples, where μ
Under the alternative hypothesis H1 with
any fixed central ranking n², for any pair of items i and j. with x²()) =('xi > m/8, is lower bound on the bias towards observing before j random ranking from H, (if m is large enough, random item pairing results in m/ R m//8 such item pairs, with high probability). We define the random variables (((+1) to be 1, if precedes i + in sample Te. and 1,, otherwise.
accounts for the deviation of the pair i and i from uniformity.
Under the null hypothesis, the expectation and the variance of Y((+1) are O(1). Under the alternative hypothesis, [[Yn++1)] 52(ku²) and V[Yr(+1)] = O(k2²). Moreover, the random variables Y12, -...... (1)m-)m are mutually independent, because they concern the relative positions of disjoint item pairs the samples. Therefore, = Y12 + Y24 +... Y(m-1)m should be ((m), under the null hypothesis, and ((mkk)²), under the alternative hypothesis. The following is proven in Appendix B and shows that we can distinguish between the two cases with adequate confidence.
Algorithm 2 Uniformity Test (UNIF)
I: Input: significance 8 O, tolerance > 0
2: Let mo E S., be chosen uniformly at random and renumber the items so that To = (1,..., m) th. does not depend To
3: Let d. sup (dry (MM M M)) e)
4: Let µ = 1-am/a and m1 = m/8 m In (2/))/16.
1+67/6
5: Take k = ==
12m ln(2/8) 10, a
m (2/5/)) m
samples DR-
mi
6: Let ......, Th E
Sm denote the samples
7: Let Xe ((-1))
if m,
it and -1 otherwise.
2
8: Let Y((H1)) =
1 Ek Xe ((111)) for all item pairs i(i + 1)
vI.
9: Let Y -12 Yss + Y ((m-1)m
10: I < m/2 + 2/ m ln(1/)
Then Accept Else Reject
https://oeis..r www.oeeisssrrr/00000
5

---

Theorem 5. For all 6, > 0, Algorithm
with
(n(1/))
122
m
samples, where Jt-
1-6m/s 1467/89
is an (c, 8)-finite confidence uniformity test of Mallows models.
Regarding the dependence of μ e-<e/m, for some constant >> 0. Then, l 2 Ite ex78, which does not depend on m. Hence, unless c extremely small, i.e., if c = o(1/ /m), ) / is constant in m and the sample complexity of Algorithm is Om 1/2).
and e, observe that if 1211vmm), then o. 2
1-e-0//
Algorithm 2 exploits a tradeoff between the bias towards the right order of i and + 1 and the values of &e and m. If m is so small that m - m/8 vm (2220)/ becomes much smaller than m, the gain in the sample complexity due to raising @. to m/8 in 1/1²² may be counterbalanced by the increase in sample complexity due to m/mī- Then, we can apply the same analysis with u' 1-#,, essentially regarding all i(i + 1) pairs as consisting of consecutive elements in To. Then, under the alternative hypothesis, [ = m(1 + (k- - (k)=))²))) 1)22)//2, which gives sample complexity of
T+
(1 + )²
48 in + 16 In(1/0)
1=
- 6.)²
m
for Algorithm 2 More generally, if m is relatively small (so small that my becomes negligible), more careful analysis of Algorithm D possible. Then, in the proof of Theorem 5 we can optimize the sample complexity by trading off the exponent of de Jr against the size of m/ As a result, the sample complexity of Algorithm 2 is upper bounded by a family of functions that have the same form as 5 in the proof of Theorem Appendix B but use different values of m, and μ., where we can increase my from m/8 up to m, by subsequently decreasing the exponent of de in from m/8 to 1.
5
Uniformity Test with Central Differential Privacy
The most natural approach to make a testing algorithm differentially private is to add Laplace noise to the test statistic. The variance of the noise should be proportional to the sensitivity of the test statistic, which ensures that small change in the input data does not change drastically the output of the tester. This intuition is formalized in 17 Theorem 3.6]. Accordingly, one can add Laplace noise to the test statistic Y which is computed in line of Algorithm 2
What remains is to compute the sensitivity of Y with respect the input. Assume that we are given two datasets Dj and D/K that consist of rankings and differ from each other in one ranking. Then, the sensitivity of the test statistic computed for D& and D/ is |Y (Dx) Y (D)) < 2m. This calculation is presented in Claim 10 in the Appendix.
Therefore, if we add Laplace noise Z ~ Lap (2m/eo) eo) to Y in line D of Algorithm 2 our algorithm
becomes (co, ojiiifferentially private. However, note that V [Lap (2m//en)] 8 (m//e0)² which is much larger than the variance V [Y] S m of the test statistic of Algorithm 2 Consequently, this
noise results in large increase of sample complexity. For sake of completeness, this approach is presented in Algorithm 4 in Appendix [ The only change with respect to mon-private) Algorithm
is that there is an extra Laplace noise added to the test statistic in line 7 and the rejection threshold has updated accordingly.
The sample complexity of Algorithm P 011/22 (1n(1/)/m) whereas the privatized test requires This means that the naive approach results in an increase in the sample complexity by factor of m²/2/Eg. Next, we try to bring this variance down with truncation technique applied Laplace noise.
O 1m//m11///p//
In Claim 10 it becomes apparent that the sensitivity of the test statistic Y is proportional to the value
of the following sum of independent Rademacher random variables ke Em Σ/= X 1):21) which can be up to 2m. To control the variance (and the sample complexity) of the privatized test statistic, we deal with the case where the value of this sum is 2 (B(mm/k) separately. This is the

---

intuition behind Algorithm which is inspired by 10 Algorithm 1], and distinguishes between different cases. particular, the value of the Laplace noise happens to be high, Algorithm
returns random response, while if E 11,2 = 22(vm/k) /k), the algorithm rejects. Otherwise, the algorithms performs a randomized version of the uniformity test called UNIF, defined in Algorithm In this case, show that the sensitivity of the statistic (and thus, the sample complexity) can be upper bounded reasonably well. We refer to the DP algorithm as TRUNC, which defined in Algorithm
Algorithm 3 Central DP Uniformity Test (TRUN)
1: Input: significance 8 O, tolerance >> 0, DP parameter 60
2: Sample Z ~ Lap 4
kóeo
3: if |Z| kden In 3 then
D. True with probability at most ò
4: Output Accept or Reject with equal probability
5: Let To S. be chosen uniformly at random and renumber the items so that To (I....,m.) m)
6: Let the = 10. (dTv((M,,,)) M Mo.no) > {)
1- and m. m/88 v In (2/6)/16.
7: Let μ 1+0./88
8: Take l samples 23 {T ................................ ) where ls is as in Theorem 6
9: Let X = 1, if mx i and -1 otherwise.
10: if
mK Em Ee X
2
(2i-1).2 7
lm(288)
then In
mb
5kea
11: Reject
12: else
13:
Let (041) = 1 Eé X
((+11)
for all item pairs i(i + 1)
Vk
14:
Let Y = Y12 + Y34 + Y (m-1)m 1)m
15:
B ~ Bernoulli (p) where min
10 /2)
mu
If B=1 Then Accept Else Reject
with 1-4m// 140
Theorem 6. For all 0,e,e0 e0 > O, Algorithm
and
(1/8) 2
(ln(1/8)
1)
== max
112
83/2 vm
p3m)
uego
samples is an (co, differrrentl private (e, -uniformity test of Mallows models.
Theorem 5 has some interesting consequences. First, privacy comes for free in some parameter regime since the first term of the sample complexity, which is dominant if o, is close and not so large, does not depend on the privacy parameter Second, the sample complexity of TRUNC is worse than the simple bucketing approach for other parameter regimes. The bucketing approach is folklore result to convert non-priv -rriiiivae algorithms to private ones. It consists of running non non-private algorithm on [1/cu] number of data batches in parallel, and return one of the outcomes selected uniformly at random. This approach is (Co. diffeeerrntlall private and has sample complexity [1/eo]] times that of the non-private algorithm (see e.g., [0 Theorem 2] for the precise reduction approach). Combining UNIF with the bucketing approach, we obtain (eo, 0) -)diifferentially private algorithm with sample complexity O( m (1(2///)))))))) (olee))mmmmmnnnnaammma
2/co3). The bucketing approach very efficient in our uniformity testing setup, because the sample complexity is of order m m11/2 for the non-private algorithm. So, the bucketing approach requires ((1 samples, if m is large enough. On the other hand, TRUNC can be superior when de is close to and m not so large, in which case the first term of Theorem Ø becomes dominant, as our experimental evidence also justifies.
1/2
6 Uniformity Test with Local Differential Privacy (LDP)
Algorithm can easily extended so as satisfies the LDP constraint, since it extracts a binary sequence from the rankings in Line 7 of Algorithm 2
Adding randomized response (RR) this bit

---

sequence componentwisely results in an simple LDP uniformity testing algorithm. Let us denote the conditional probability of RR by W W.I.), for which W(-1) - + e and W(-1|+1) = W(+1| (.I.) with 7 = 20//m, then the LDP guarantee satisfied. To see that, we consider two rankings and n², for which fx. (-1, ................................ -1) and (T') (1...., 1) for fixed Nu- Then P((I....,11 1)[= m
- As consequence, if all X ((+1)) are passed through a channel
T2 2
log P((L....,
log
Co
2
e
We present our LDP uniformity testing algorithm so as it requires public/shared randomness in the form of a random ranking that is sent to each peer beforehand. The curator algorithm defined in Algorithm 5 and the peer algorithms in Algorithm 0 in Appendix [F] The LDP algorithm is based on Algorithm and uses the same test statistic. If public randomness is available, we can implement
s²-1 which leads an improved sample Algorithm with random item pairing and μm0 1+-0"/3 e'+I
I-dm//
complexity, if de is close to 1 and is relatively large. If only private randomness is available, we 1- _2-1
implement Algorithm 2 with a fixed item pairing and 1 I+ e²41 (see also the discussion after Theorem 5 on how the choice of item pairing affects the value of μ and the sample complexity). The analysis is essentially identical to the proof of Theorem []] since the mean value and the variance of the test statistic are m. m/2 and at most m, respectively, under Hu, and are given by the same funetions of js (or Pb),, under H,. The only essential difference is the decrease of μ (or 1() by factor of s"4) to account for the randomized response. The discussion above is summarized by the following:
Theorem 7. For all 6, e, c > and 7 = 260/ m, Algorithm 5 and Algorithm foorm an (c, 5)-finite confidence uniformity test and (co, Ol-locally differentially private for Mallows modesls with sample complexity:
k
In(1/5) m
where po
1-0m/s Li
5. m- public randomness is used and
M6
a random ranking is sent by the curator algorithum to each peer.
k- =
In(1/5)
where 16 =
1-th.
en-1 if only private randomness is used.
I+ e>+1
Since for 7 = 200/m mm, eT-1 s 2s,, the dependence of the sample complexity of our LDP algorithm on ED is ((1/eo²) )) and on m is (/m3/2).
7 Experiments
We shall present synthetic experiments to assess the performance of the proposed tests. We assess the power of these tests which is the probability of the rejection for various spread parameter o. Every testing algorithm we presented has a tolerance parameter and significance 8. We used in every case. The tolerance parameter does have impact only on the sample size of the testing algorithms. Instead of setting c to a certain value, we plotted the power of the algorithms with various sample size. this way, we could compare the performance of the testing algorithms based on the same number of samples as input. Each result we report here are computed based 1000 repetitions. The central ranking of each model which the random samples are generated from, is selected uniformly random in each each run independently.
0.05
7.1 Uniformity Testing Based on Two Samples
In the first set of experiments, we compare the uniformity testing algorithm based on two samples, called ASM which is defined in Algorithm [ and the more general algorithm, called UNIF which defined in Algorithm 2 running with two rankings as input. We assess the power of these tests which is the probability of the rejection for various spread parameter ó. The results are plotted in Figure M The 28 AMP algorithm does work already for m = 100 and it consistently outperforms UNIF based on two rankings. This can explained by the fact that 2S A MP computes pairwise statistic, which is the Kendall distance, based on each pair of items, whereas UNIF takes into account only the independent pairs. It is worth to emphasize that these tests detect very small deviation from
8

---

the uniform for large m. More concretely, it is detected with zero error, i.c. power is equal to 1, when the spread parameter deviates from 1 with a margin of 10-5 in case of 10000.
100
m1 500
m 1000
m
10000
1.0
0.5
0.0
0.0
0.0
0.8
0.9350
Figure 1: Power function of 2SAMP introduced in Subsection 4.1 and UNIF introduced in Subsec-
tion 4.2 with various parameters of the alternative model. The spread parameter of the underlying Mallows model is shown on the x-axis.
7.2 General Uniformity Testing with Arbitrary m
Testing uniformity
of the motivation of Mallows when he came up with his model (see Section 11 in (25)). Mallows assumed that the central ranking is known and proposed a asymptotic test based on the normal approximation of the sufficient statistic of his model. Even if there is no guaranty of how good this normal approximation is, it seems reasonable when the central ranking fixed, since the distribution of the sufficient statistics is symmetric due to the fact that Mahonian numbers are symmetric, i.e. N₂- = -m(mm1)/// where N₂ is the kth Mahonian number of order m. One can compute the mean and variance of sufficient statistic based on 20 as
M
m(m m 1)
Bg [T)
Σ
iN ml
4
==0
and
Mr. [T,, m(2m + 5) -1)
72
This approximate solution easy to use, since uniformity testing boils down to testing equality of expectation of normal distributions with known variance. Here we consider more general testing problem where we do not assume that the central ranking is known and fixed. We refer to this approach Mallows approximate test (MA). In this test, the normal approximation seems not so accurate as Figure 2 shows. The power of the test converges to I very slowly as @ is getting far from zero. Algorithm UNIF achieves power that is close to one much faster.
10
m
m 10000
Power
05
0.5
0.5
2.5
MA in 1000C)
MA (1
1200
Mk 05 21
MM 21
UNI (n- 100001
UNIF in 100h
UNF In
UNIF m
1.50
902
0.505
0.500
5.555
2.000
0.0000 0.9925 O 0.920 0.5975 1.0000
3-99752, soo0n soato 59920 99301 0320
Figure 2: Power function of MA and UNIF algorithms with various number of items m (10, 100, 1000, 10000} and various sample size n E {10000, 100, 2, 2), respectively.
7.3 Uniformity Testing with Privacy
In this set of experiments, we compare the performance of the presented DP algorithms including the following three of them: (1) bucketed UNIF which consists of running the UNIF algorithm on [1/eu] batches of data indpendently and take the output of one of the runs uniformly at random. We refer to this approach as BUNIF. (2) We run the DP algorithm with truncated Laplace noise that is defined in Algorithm 3 which we refer to TRUNC. (3) We run also the locally differentially private algorithm which is defined in Subsection 6 We set c = 0.33 thus the BUNIF power curve corresponds to the UNIF power curve with 1/3 of the sample complexity.
The power curves of the algorithms are shown in Figure 5 Note that the TRUNC does outperforms
BUNIF when á is close to 1, since in that case μ is very close to 1 and the first term is the dominating

---

5m-10
5m-100
$m-500
$m-1000
POWer
0.5
TRUNC
TRUNC
0.5
TRUNCC
0.5
TRUNN
SUNIF
BUNIF
BUNIF
BUNIF
LDP
LDP
LDP
LDP
2.50
0.32
0.94
0.96
0.50
1.50
0.32
0.96
0.50
1.20
0.085
0.500
0.565
1,000
0.902
0.000
0.555
2.300
Figure 3: Power function of BUNIF, TRUNC and LDP algorithms with various number of items m E f10, 100, 500, 1000} and various sample size. We set the sample size for central DP algorithms, i.e. BUNIF and TRUNC, to n E {10000, 1000, 1000, 100), respectively. In case of LDP, the sample size was set to = (100k; 200k, 300k, 300k). The privacy budget eo was set to 1/3.
one in Theorem 0 Nevertheless, the power BUNIF algorithm converges faster when the underlying model getting farther from the uniformity. In general, the DP algorithms requires much more samples than the non-prite non-private algorithms. This difference is much more pronounced case of LDP. However, local differential privacy is well known to provide some of the strongest privacy guarantees as it impossible for an adversary to know the true ranking from the output of the channel.
8 Conclusion and Future Work
We introduced uniformity testing algorithm with sample complexity upper bound of order O(1/ /m) for ranking data when the alternative model class is constituted by the single parameter Mallows model. The proposed methods can work based on 2 samples, when m is large enough. We also devised testing algorithms in the central and local differential privacy framework. We demonstrated the versatility of these testers on synthetic data. We found that they are scalable, since they could handle large m including m 10000, and are able to detect non- unnf--nifoottyy with very small error, i.e. 1 Φ Rs 10-5 difference could be detected with zero error based on two samples when 10000.
One open question is provide lower bounds on the sample complexity of uniformity testing of Mallows models. It turned out that this is a very challenging problem in the non-private case since, for example, using information theoretic lower bounding technique based on LeCam's 's theorem, one needs to upper bound KL divergence (M For doing so, one needs to have an upper bound for the difference of Φ. from I in terms of e and m. Note that de depends on the total variation distance, thus it seems unavoidable bound for ((b,) as well, which is a very hard nut to crack. So we leave this lower bound as future work. Nevertheless, note that with m 2, the single parameter Mallows class includes the class of Bernoulli distributions, thus the lower bounds that are devised for private uniformity testing of Bernoulli distributions also apply to private uniformity testing of Mallows models. More concretely, [S] showed that testing Bernoulli with parameter in central DP setting cannot be done using o( o(1/En) which implies that our central DP algorithm has optimal dependency on the privacy budget parameter. On the other hand, [6] showed that in the LDP setting, a lower bound on the sample complexity of testing is ((1 )). Theorem 7 matches this lower bound when m 2, since then e² 1 = cu and the sample complexity bound O(1/eo") in this case. Lastly, natural extension of our work is to consider more fine grained atom in the privacy setting, namely one might want to protect each pair of the data instead of whole rankings.
In de 2 In (5) where & E [In de. O].
get
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-1422:
References
[1] Jayadev Acharya, Clement Canonne, Cody Freitag, and Himanshu Tyagi. Test without trust: Optimal locally private distribution testing. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Sventy-Second International Conference Artificial Intelligence
10

---

and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2067-2076. PMLR, 16-18 Apr 2019.
[2] Jayadev Acharya, Clément L.. Canonne, Yanjun Han, Ziteng Sun, and Himanshu Tyagi. Domain compression and its application to randomness-optiine distributed goodness-of-Fe In Confer- ence on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Gruz, AustriaJ, pages 3-40, 2020.
[3] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Suresh. A competitive test for uniformity monotone distributions. Carlos M. Carvalho and Pradeep Ravikumar, editors, Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Muchine Learning Research, pages 57-65, Scottsdale, Arizona, USA, 29 Apr-01 May 2013. PMLR.
[4] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6879-6891 2018.
[5] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private testing of identity and closeness of discrete distributions. In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, page 6879-6891, Red Hook, NY, USA, 2018. Curran Associates Inc.
[6] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Hadamard response: Estimating distributions privately, efficiently. and with little communication. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 1120-11299 PMLR, 16-18 Apr 2019.
[7] Tugkan Batu and Clément L. Canonne. Generalized uniformity testing. In Proc. of the 58th IEEE Symposium on Foundations of Computer Science (FOCS 2017), pages 880-889, IEEE Computer Society, 2017.
[8] Róbert Busa-Fekete, Dimitris Fotakis, Balázs Szörényi, and Manolis Zampetakis. Optimal learning of mallows block model. CoRR, 2019.
[9] Róbert Busa-Fekete, Eyke Hüllermeier, and Balázs Szörényi. Preference-basee 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.
[10] Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it iit' Private and sample efficient identity testing. In Proceedings of the 34th International Conference on Machine Learning. ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, pages
2017.
[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] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Testing identity of structured distributions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego CA, USA, January 4-6, 2015, pages 1841-1854, 2015.
[13] Apple Inc. Differential Privacy Team. Learning with privacy at scale. 2017.
[14] Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, USA, 1st edition, 2009.
(15) Cynthia Dwork. Differential privacy: A survey of results. In Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi an, China, April 25-29, 2008. Proceedings, volume 4978 of Lecture Notes in Computer Science, pages 1-19. Springer, 2008
[16] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
11

---

[17] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3 4):211-4400 August 2014.
[18] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preservin ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS 14, page 1054-1067, 2014.
[19] Alexandre Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the twenty-second ACM SIGART symposium on Principles of database systems, pages 211-222, 2003.
[20] M. A. Fligner and J. S. Verducci. Distance based ranking models. Journal of the Royal Statistical Society. Series B (Methodological), 48(3):359-300 1986.
[21] Michael A Fligner and Joseph S Verducci. Distance based ranking models. Journal of the Royal Statistical Society. Series B (Methodological)) pages 359-369, 1986.
[22] Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electron. Colloquium Comput. Complex., 7(20), 2000.
[23] Guy Lebanon and Yi Mao. Non- Non-parametric modeling of partially ranked data. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-Finte Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 3-6, 2007, pages 357-864, 2007.
[24] Tyler Lu and Craig Boutilier. Effective sampling and learning for mallows models with pairwise- preference data. J. Mach. Learn. Res., 15(1):3783-382) 2014.
[25] C. Mallows. Non-null ranking models. Biometrika, 44(1):114-130, 1957.
[26] John I. Marden. Analyzing and Modeling Rank Data. Chapman & Hall, 1995.
[27] Marina Meila and Le Bao. An exponential model for infinite rankings. Journal of Machine Learning Research, 11:348-33513 2010.
[28] Sumit Mukherjee. Estimation in exponential families on permutations. The Annals of Statistics, 44(2):853 875, 2016.
[29] Liam Paninski. coincidence- data. IEEE Trans. Inf. Theory, 54(10):4750-4777 4755, 2008.
for uniformity given very sparsely sampled discrete
[30] Mingxuan Sun, Guy Lebanon, and Paul Kidwell. Estimating probabilities in recommendation systems. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, AISTATS 201 Fort Lauderdale, USA, April 11-13, 201 I, pages 734 742, 2011.
[31] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. SIAM J. Comput., 46(1 1229 455, 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? [N/A] hope there is no negative societal impacts of my work
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

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 proof' of all theoretical results? [Yes] They are presented in the appendix.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] We reported the number of repetition. Since all number we reported are average of binary values, they standard error implied by the number of reparations.
(d) Did you include the total amount of compute and the type of resources used (c.g.. type of GPUs, internal cluster, or cloud provider)? [N/A] We used data centers to compute the experiments. believe that it is not relevant this work how long the computation did take.
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] used synthetic data.
(c) Did you include any new assets either the supplemental material or as URL?? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you' '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, applicable? [N/A]
(b) Did you describe any potential participant risks, with links 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]
13


Reviews:
[{"review_id": "QyLzS1sWJyX", "reviewer": "Reviewer_efTh", "summary": "This work considers uniformity testing of ranking (or permutation) of a discrete set with and without differential privacy (CDP and LDP). The ranking distributions are assumed to belong to the Mallows model family. The authors designed algorithms for these cases and proved their sample complexities. Synthetic experiments are also conducted for the algorithms.", "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": "Strength:\nThis work provides a comprehensive understanding for the sample complexity upper bounds in uniformity testing of ranking distributions in the Mallows model family. Algorithms are designed for non-private, CDP and LDP settings. The algorithm sample complexities scale as the domain size instead if the number of permutations. \n\nOverall the writing is clear.\n\nMajor concerns:\n1. For CDP setting, it is claimed that TRUNC is better than the naive approach when $m$ is small. However, when $m=10$, TRUNC seems to have a worse performance. Could the authors explain the discrepancy here?\n2. What are the time and space complexities for the algorithms?\n3. For CDP and LDP the maximum domain size is only 1000. Experiments for larger domains could be done at least for CDP. \n\n\nMinor concerns:\n1. $\\phi_\\epsilon$ seems to be hard to compute in practice. Could the authors characterize the relationship between $\\phi_\\epsilon$ and $\\epsilon$, or provide a method to emprically calculate this? \nOr perhaps characterize the problem as testing between $\\phi=1$ and $\\phi\\le1-\\varepsilon$, instead of TV distance?\n2. This work does not include lower bounds (only a lower bound for a special case which can be reduced to testing Bernoulli random), though it is OK not to have them for this submission.\n\nOther comments:\n1. The sample complexity bounds that go to 0 with $m$ (such as$O(1/m^{1/2})$) are not very accurate since you mentioned that it is impossible to do testing with only one sample. You should add a constant term. \n2. For the LDP experiments, what is $k$?\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": "4"}, "extra_text": {}}, {"review_id": "PnRWcAD1L0G", "reviewer": "Reviewer_nEjk", "summary": "This paper studies the problem of (private) uniformity testing in the ranking problem, where the data in the alternative hypothesis is assumed to be generated from the Mallows models. \n\nThe main contributions of this paper are:\n\n1. Devising two uniformity test algorithms accompanied with performance guarantees, for large and general values of $m$.\n\n2. Devising uniformity test algorithms with performance guarantees for central and local DP.", "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": "I found the paper well-written, and somewhat motivated. The introduction is comprehensive and the setup and learning problem are clear. The strong side of this paper is its qualitive contribution. In terms of the technical contributions, I read all the proofs and they seem okay; most of the proofs are somewhat standard and straightforward, unless I am missing something. Saying that, Algorithm 2 and its analysis are interesting and more technical. It would be great if the authors could point out the main difficulties encountered in their proofs as well as the novel arguments/techniques used to establish their results.  \n\nI recommend accepting the paper, mainly due to the fact that I find the setting interesting. \n \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "-f-OoaEA4Ez", "reviewer": "Reviewer_ExtA", "summary": "The paper studies uniformity testing for certain structured distributions on large domains. The classic uniformity testing problem is to decide, using sample access, whether an unknown distribution over a domain of size $n$ is the uniform distribution or $\\epsilon$-far from the uniform distribution in total variation distance. The sample complexity is known to be $\\theta(\\sqrt n)$ for this general problem and hence is not feasible when $n$ is large unless we restrict the class of distributions under consideration. The present paper considers the class of distributions known as the Mallows model: this is a class of exponential distributions on rankings (set of permutations over a domain). More precisely, given sample access to a distribution from the Mallows model: decide whether it is the uniform distribution or $\\epsilon$-far in total variation distance from the uniform distribution. The paper presents both theoretical as well as experimental results on this problem. On the theoretical side, it proves upper bounds on the sample complexity in  various settings including for differentially private testing. On the experimental side, it implements and tests these algorithms for various parameter settings. ", "questions": "", "limitations": "", "rating": 6, "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": "The paper presents several theoretical as well as experimental results. However, this reviewer is concerned about the significance of the problem studies as well as the results.  While Mellows class of distributions may be useful in several settings, it is not at all clear whether a uniformity testing algorithm with privacy or without privacy for this class of distributions is a significant research question. Thus the result might not be of interest to a broad NeurIPS audience. \n\nUpdate After Rebuttal\n\nWhile, as presented in the paper the motivation for investigating this specialized class of distributions for uniformity testing is weak, the paragraph in the rebuttal gives much-needed motivation for the problem considered.  I recommend that the authors add a similar paragraph in the next version. Also, the interesting paper by Mukerjee cited is missing in the submitted version. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author/authors state that \"I hope there is no negative social impact of my work\" in the checklist document. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of testing uniformity of rankings vs a Mallows model, given sample access to these rankings. The paper presents novel algorithms for this problem, both private and non-private. It is a nice contribution to the literature. As one of the reviewers pointed out, it can be helpful to add some remarks in the paper about lower bounds for this problem. 
Decision: Accept (Poster)