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 0( 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/ 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 {2} 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, (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 (n))))), 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-1m 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 - 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.oeeiissrrr/A0000./0
5

---

Theorem 5. For all 6, > 0, Algorithm
with
(n(1/))
122
m
samples, where Jt-
is an (c, 8)-finite confidence uniformity test of Mallows models. 1467/89
1-6m/s
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 ():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 (BVmm/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), 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 eo > 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-pric -rriiiivte 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( m1xx11// (1/(p))))))))))// (otee))mmmmmnnnnaammna
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) - +(+1|+11) 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₂- = Nm(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( ((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
In de 2 In (5) where & E [In de. O].
get
testing is (11//u" )). 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.
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 First 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--3513 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": "lC5Lvrf0-M2", "reviewer": "Reviewer_C58N", "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). \n\nThe 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. ", "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": "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. \n\nThe 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. \n\nI 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. ", "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": "2-3 hours"}, "extra_text": {}}, {"review_id": "GKYsHq-Rl2o", "reviewer": "Reviewer_r9MB", "summary": "\nThe 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. \n", "questions": "", "limitations": "", "rating": 6, "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": "\n\nThe 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. \n\n\nSpecific Comments: \n\n\nI am not sure if this is because of space constraints, but a few important recent references on uniformity testing problems are missing. For example: \n\nG. Valiant and P. Valiant, An automatic inequality prover and instance optimal identity testing,  SIAM J. Comput., 46(1):429--455,  2017. \n\nT. Batu and C. Canonne, Generalized uniformity testing, FOCS, 2017.\n\n\nPage 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$.  \n\n\nPage 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. \n\nMoreover, 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 \\}$. \n\n\nPage 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}$\n\n\nPage 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? \n\n\nPage 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$? \n\n\nThe discussion following Theorem 5 is unclear and needs to be clarified. \n\n\nThe 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. \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\n\nAs 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?\n\nAlso, 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. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72 hours "}, "extra_text": {}}, {"review_id": "7WNO1AWMwQ", "reviewer": "Reviewer_G2iJ", "summary": "\nThe authors study the problem of differentially private (DP) uniformity testing for rankings:\nare the rankings uniformly and randomly generated (under the null hypothesis) or are the rankings\ngenerated in such a way that the distribution of rankings are $\\epsilon$ far from the rankings generated under\nthe uniform distribution.\nThey present two main algorithms: 2SAMP (works in certain paramter regimes and uses two samples) and UNIF.\nIn Section 7, they present simulations on synthetic data to validate their methods.", "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": "Their results are obtained under the Mallows model, which is widely used in the ML rankings literature.\nThe model has two main inputs: $\\pi_0$ and $\\phi\\in[0, 1]$. $\\pi_0$ is a central ranking and\n$\\phi$ is the \"spread\" around this central ranking.\n\nAlgorithm 1 (2SAMP) is a uniformity tester that uses two samples and works only when $\\phi\\leq 1 - \\Omega(1/m)$,\nwhere $m$ is the number of items to be ranked.\nAlgorithm 2 (UNIF), on the other hand, works on any arbitrary $\\phi$.\n\nIn Section 7, Figures 1, 2, and 3 serve to experimentally validate their methods, algorithms, and assumptions.\n\nI 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.\n\nMinor Comments\n==============\n\n- Use of $\\epsilon$s and $\\delta$:\nI think $\\epsilon_0$ is used as the privacy parameter and $\\epsilon$ is used for how\nfar from uniform the distribution of rankings is, under the alternative hypothesis.\nAnd $\\delta$s are used for significance? This might be confusing. [response acknowledged]\n\n- Line 202 states that the variance of the Laplace is $8b^2$ for scale b. Shouldn't this be $2b^2$? [response acknowledged]\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "approximately 3 hours"}, "extra_text": {}}, {"review_id": "5aCTZnl8WY8", "reviewer": "Reviewer_Czjv", "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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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 \ndistributions 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.\n\nThe 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)).\n\nLeveraging 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. \n\nHere, 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.\n\nTo 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.\n\nOriginality \n\nAlthough 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. \n\nQuality\nThe paper is generally well-written, with full definitions and clear exposition. I have not verified the technical proofs in the supplemental material. \n\nClarity\nThere 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. \n\n\nSignificance\nThe paper would be interesting to the property testing, differential privacy and machine learning communities.\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": "1"}, "extra_text": {}}]

Author rebuttal:

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)