Ranking Recovery under Privacy Considerations
Authors: Minoh Jeong
Alex Dytso
Martina Cardone
Venue: Accepted by TMLR ()

Abstract: We consider the private ranking recovery problem, where a data collector seeks to estimate the permutation/ranking of a data vector given a randomized (privatized) version of it. We aim to establish fundamental trade-offs between the performance of the estimation task, measured in terms of probability of error, and the level of privacy that can be guaranteed when the noise mechanism consists of adding artificial noise. Towards this end, we show the optimality of a low-complexity decision rule (referred to as linear decoder) for the estimation task, under several noise distributions widely used in the privacy literature (e.g., Gaussian, Laplace, and generalized normal model). We derive the Taylor series of the probability of error, which yields its first and second-order approximations when such a linear decoder is employed.  We quantify the guaranteed level of privacy using differential privacy (DP) types of metrics, such as $\epsilon$-DP and $(\alpha,\epsilon)$-Rényi DP. Finally, we put together the results to characterize trade-offs between privacy and probability of error.

Published in Transactions on Machine Learning Research (07/2022)
Ranking Recovery under Privacy Considerations
Minoh Jcong
jeong316 edu
Deportment of Electrical and Computer Engineering University of Minnesota
Alex Dytso
alex. dytso @rjit. edu
Department of Electricol and Computer Engineering New Jersey Institute of Technology
Martina Cardone
meardone Gumm..neeeumm.o edu
Deportment of Electriool and Computer Engineering University of Minnesola
Reviewed on OpenReview: https:// openrrvveeen net/ formm???? id= 2E0VIvRXIe
Abstract
We consider the private ranking recovery problem, where data collector seeks to estimate the permutation/ranking of data vector given randomized (privatized) version of it. We aim to establish fundamental tradc-offs between the performance of the estimation task, measured in terms of probability of error, and the level of privacy that can be guaranteed when the noise mechanism consists adding artificial noise, Towards this end, we show the optimality of a low-complexity decision rule (referred to as lincar dccoder) for the estimation task, under several noise distributions widely used in the privacy literature (e.g., Gaussian, Laplace, and generalized normal model). We derive the Taylor series of the probability of error, which yields its first and second-order approximations when such linear decoder is employed. We quantify the guaranteed level of privacy using differential privacy (DP) types of metries, such as <-DP and (a, e)-Rényi DP. Finally, we put together the results to characterize tradc-offs between privacy and probability of crror.
1 Introduction
Today, ranking algorithuss are of fundamental importance and are used large portfolio of applications, such as search engines (Dwork et al. 2001), biomedical (Chanas Kobylański 1996). recommender systems (Baskin & Krishnamurthi 2009), and feature matching (Jeong et al.) 2020). Broadly speaking, the goal of ranking algorithm is to sort dataset which, in the current Big Data era, is usually massive in size and complexity so that users/ users/individuee /nndviididiils are provided with accurate and relevant results. For instance, recommender system may suggest a new item to buy to a user based on their interests and previous purchases. Although modern ranking algorithms promise efficient means of performing large-scale data processing, there are numerous privacy considerations that must not be overlooked. For instance, the dataset might contain confidential data, such clinical/genone health and banking records, or a user would not like to disclose their previous purchases to recommender system.
In this paper, we study the private ranking recovery problem, which consists of recovering the rank- /eg/permutation of an input data vector from noisy version of it. The importance and timcliness of this problem stems from two major considerations. First, many modern computing systems (e-g,, recom- mender systems) are often more interested in recovering the permutation, i.e., the relative ranking of data points, rather than the values of the data itself. Socond, because of privacy considerations, users might decide privatize their data (c.g., by adding some noise) before sharing it with an external party (c.g., recommender system). These facts give rise to the following practically relevant question: Which perturbation

---

Published in Transactions on Machine Learning Research (07/2022)
mechanisms allow for data privatization, while still allowing to correctly recover the permutation of the input data vector with high probability?
1.1 Related Work
Recently, problems with a similar flavor to the private ranking recovery problem (studied in this paper) have been analyzed. For instance, Jeong et al. (2020 2021 focused characterizing the probability of error of estimating the original permutation of data perturbed by adding Gaussian noise. In particular, they characterized sufficient and necessary conditions of the Gaussian noise covariance matrix that ensure that the optimal (i.e., that minimizes the probability of error) decision rule consists of simply declaring a permutation intiionnnndeeeneent linear function of the noisy observation. The rank aggregation problem was studiod under differential privacy constraints by Shang et al. (2014) and Hay al. (2017), and under local differential privacy by Yan et al. (2020) and Allbi et al. (2021). Differential privacy (DP), which is statistical guarantee introduced by Dwork et al. (2006b) for indistinguishabiiii whether any data element exists or not in a dataset, is one of the most common adopted privacy metrics. Several notions of DP have been introduced and analyzed that range from the basic e-DP metric (which can be guaranteed by using the Laplace randomized mochanism) (Dwork 2008), to more relaxed versions of it, such as the (c. 5)DD) Dwork et al. (2006a), the e-mutual information DP and the e-Kullacck-Libler (KL) DP Cuff & Yu (2016): and the (ax, e)Réény DP (RDP) Mironov (2017). In particular, the (a, c.-DDD encompasses: (i) the e-DP if a + oo, and (ii) the <-L DP if a + 1. Morcover, some important propertics of the c-D,, c.g., the composition thcorem, remain applicable in the RDP framework.
When data is confidential and hence, needs to be privatized before being shared with an external party (which will perform some operations on it) a natural question arises: For a fized target performance guarantee fa. utility) required on the data, what is a randomized mechanism that achieves the mazimum level of privacy? To answer this question, one needs to understand the trade-off between privacy and utility. Such trade-off has been studied in the literature in several settings, where different utility measures have been used. For instance, WWaserman & Zhou (2010) compared several randomized mechanisms (from statistical point of view) by using the Kolmogorov Smirnov and the Le distances among distributions and densitics. [Wi et al.] (2020) showed a tradc-off between the convergence of federated lcarning algorithm (utility) and the level of privacy (measured in terms of DP) that can be guaranteed, hence suggesting the amount of artificial noise that should be used in this context. Avent et al. (2019) studied the privacy-utility trade-off for a hyperparameterized algorithm using multi-objective optimization and Pareto front For a single real-valued query. Geng al. (2015) identified the staircase distribution (i.c., a geometric mixture of uniform random variables) as a distribution that minimizes the In loss (utility) under a fixed given level of e-DP. The staircase distribution has also been shown to be the optimal eDDP mechanism under other utility constraints -Soria-Comas & Comingo-Ferrer 2013). More recently, Geng et al. (2019) studied trade-offs between O0- and the Lp loss function for a single real-valued query function.
1.2 Contributions and Paper Organization
In this paper, we study the privule ranking recovery problem, where confidential input data vector needs to be privatized (by means of a randomized mechanism) before being shared with an external party, We seek to retrieve the true ordering of the input data vector given the privatized data. Our main goal is to characterize the trade-off between the performance of estimating the permutation of the input data vector (measured in terms of error probability) and the level of privacy (measured in terms of cDD and (a,c)-RDP) that the used mechanism guarantees.
First, in Section 2 formulate the private ranking recovery problem within DP framework. In particular, we adopt the (a, RDP as privacy metric; our choice mainly stems from the fact that the (a, RDP encompasses othe widely employed DP metrics such as the e-DP (Dwork 2008) if a - co, and the e-KL DP (Cuff & Yu, 2016) if a + 1. Moreover, as pointed out in [Mironov 2017 Proposition 3), (a, c)-DD can be converted to OP..
Second, in Section 3 we show that under mild assumptions on the input data vector (i.c., the input data distribution is exchangeable) and the randomized mechanism (i.e., it has an e--ppheiiaal distribution),
2

---

Published in Transactions on Machine Learning Research (07 (222)
Table 1: Trade-off between privacy and utility in the low-noise regime with i..d. noise components. Privacy is measured by (a, c)-RDP for the Gaussian and Laplace mechanisms and by c-DP for the generalized normal mechanism. The utility is quantified by Po.
K(o)
Trade-off
1(,,1
Po x (2) (2)
Lap (0,22)
Pe x
GN (0,
T(p 1) I(3p ((3p-1).P)
Pe x (t) 1/P
declaring the permulation of the observed noisy vector is an optimal decision rule for recovering the permutation of the input data vector. Because of this, and using the terminology introduced in JJoon et al. (2020) 2021 we refer to such a decision rule as linear decoder. This has complexity O(n ((nlog n). which is significant reduction with respect to the (n!) complexity of a naive brute-force implementation of the optimal decoder.
Third, in Section E we characterize the error probability of the linear decoder, by deriving the Taylor series of it. This result suggests that the private ranking recovery problem is noise dominated, i.c., the crror probability is large even for small values of the noise variance. Further, we derive the first-order approximation of the error probability with respect to the noise standard deviation, and verify through numerical simulations that this approximation is indeed accurate. In particular, our first-order approximation expression decouples the effects of the input data distribution and noise distribution on the error probability. We also derive the exact expression for the linear slope of the error probability for the case of i.i.d. input data vector entries.
Finally, in Section f we derive the trade-off between privacy (measured by e-DP and (a, c)-DP) and utility (measured by the error probability P.) in the low-noise regime. We consider widely used noise addition mechanisms, i.e., the Laplace, the Gaussian, and the generalized normal. As indicated in Table I these mechanisms have different relationships between and P.. The trade-offs for W/ 1) and Lap (0. are obtained based on (a,e)-RDP, and for the generalized normal mechanism with S 1, e-DP is considered. We observe that the generalized normal mechanism with p < 1 offers the best trade-off.
1.3 Notation
Boldface upper case letters X denote random vectors; the boldface lower case letter x indicates specific realization of X; Xim denotes the i-th order statistics of X E R"; [mi m2] is the set of integers from to 2 nı; In is the identity matrix of dimension O, is the column vector of dimension n of all zeros; ||ж||p denotes the f--norm of x E R"; calligraphic letters indicate sots; |A] is the cardinality of A. XAA is the subvector of X where only the elements in A are retained. For two n--dimensional vectors x and y, if for all i E [1 n), the i-th element of is larger than or equal to the i-th element of y, then we use x 2 y; Is is the indicator function over the set S. For any x R" and y E RR", the Hamming distance is defined yx, = Ein (u:#w:)i denotes equality in distribution; .V (N K) is the n-dimensional Gaussian distribution with mean He, and covariance matrix K; Lap(μ, b) is the Laplace distribution with mean μ and scale by GN(U,, a,p) is the generalized normal distribution (Nadarajah 2005 Dytso et. al. 2018 with mean P, scale a, and shape p. We let P be the set of all permutations of an n-dimensional vector. For T E P, we define
H, = (x R. Ir S xr. S S J
(1)
The probability error Pe is proportional up to the first-order term (1)
3

---

Published in Transactions on Machine Learning Research (07/2022)
X
K(o, X)
Decode
Data
Collector
#x
Figure 1: Graphical representation of the considered private ranking recovery framework.
with 2 [1 : n| being the 7,-th element of x, and T, i e [L n] being the i-th element of т. For example, in the 3-dimensional space there exist |P] 6 permutations, and we have
H(1233 X1 S X2 S X3, H4.32 : X1 S X3 S X2,
H(2,133 X2 S X1 S X3,
H(2331) X2 S X3 S X1,
H(3,12) X3 $ X1 X2, H(3,211) X3 X2 S X1:
where X,, E [1: 3] is the i-th element of X.
2 Problem Formulation
We consider the private ranking recovery problem, as shown in Figure 1 In this setting, because of privacy considerations, a randomized mechanism KC-) is applied on the confidential n-dimensional data vector X RR" before this data is collected by an external party (e.g., recommender system). In other words, XC(-) is applied so as to hide the values of X from the collector (i.e., privatize X). The goal of the data collector is then to retrieve the permutation according to which X is sorted, i.e., to output the estimate fx.
In the framework described above, a natural trade-off arises between the performance the estimation task, referred to as utility function in the remaining of this paper, and the privacy level that can be guaranteed. In particular, such trade-off dictated by the distribution of X, and K(-). In this work, we are interested in characterizing such trade-off for randomized mechanisms that consist of noise addition on the data vector X, namely
K(oo, X) X X
(2)
where e Ra is the n-dimensional noise random vector and o 2 0 is a parameter controlling the power of the noise.
Utility Function. As utility function, consider the probubility of ervor incurred in the estimation of xx. With reference to Figure [ we let Φ(-) R + P denote the decoder that the data collector uses to output *x. Then, the probability of error of the estimation task depends both on o(-) and KC(-), that is
Kc(o,K) Pr (o(K(a, X)) TX).
(3)
Privacy Metric. Given ([ in 22 it is important to quantify the privacy level guaranteed by this mechanism. Towards this end, we leverage the c-DP (Dwork 2008 in Definition 2.1 and the e). RDP (Mironov) 2017) in Definition 2.2
Definition 2.1. Let &' be the set of possible n-dimensional real-valued data, vectors. Let (X, X) 2 be pair of adjacent data vectors, which differ in at most one element, i.e,, dy (X, X) S 1. Then, the randomized mechanism KC(-) gives eDDP if, for any set. S, we have that
Pr(K(o,X) S) S e X)
Definition 2.2. Let X' be the set of possible re-dimenional real-valued data vectors. Let (X, 2 be pair of adjacent data vectors, which differ in most one element, i.e., du (X, X) < 1. Then, for > 1, the randomized mechanism K(-) gives (a, RDP if
RDP (DP
(5a)
where
RDPx(K)= =
sup (x.
D (II((,)))
(5b)
4

---

Published in Transactions on Machine Learning Research (07 (0222)
and, for X and Y with equal support,
(xxx)
a7
Dx
a a-1 log (x
(5c)
with (x(-) and (f(+) being the probability density functions (PDFs) of X and Y, respectively. Da(-Il-) is the Rényi divergence of order a.
Several rationales behind our choice of using the (a, RDDDD a privacy measure. First, the (a, RDD encompasses other widely employed DP metrics, e.g., the e-DP (wwork] 2008) if oc, and the e-LL DP (Cuff& & Yu 2016) if a + 1. The (ar, e)-RDP also bypasses some limitations of the e-DP (e.g., Gaussian noise adding mechanism is not c-DP), while still retaining similar appealing properties (e.g., composition properties (Mironov 2017]) as those of the e-P.
Our goal in this paper is to characterize the privacy-utility trade-off when the randomized mechanism is used. In other words, we seek determine Pe K.) in (3) subject to the constraint that RDP (XC) in is set to be equal to E (for e-DP we set oe). In particular, will focus scenarios where X is exchangeable and N E Sn.p. as defined below.
Definition 2.3. A sequence of random variables XI,..., Xn is said to be exchangeable if, for any permutation π (TI..... nT) of [1 n], we have
(XI....,X,, X,)) (X Xx,))
Definition 2.4. A function f is en-sperricllyy non-increasing if it can be written as
f(x) g( [x(1))
(6)
where g 1R + R2 a non-increasing function. We denote by Sn.p the set of n-dimensional distributions which have an fp-spherically non-incrcasing density function.
Our assumption on X being exchangaable includes data that does not need to be necessarily i.i.d., but can be correlated. For instance, any convex combination of i.i.d. random variables, and any spherically contoured distribution are exchangeable" We also highlight that N E Sn.p implies that N is exchangeable; this follows since the f--norm is permutation invariant. Finally, we conclude this section with a few examples (see Appendix A for the details), which show that distributions on N widely used in the DP literature are in Snp-- Thus, the assumption that N Sn.p can also be considered as mild. Example 2.5. The following distributions belong to Sn.p.
N'O,,, o ) in this case, p p= 2;
N consists i.idd. Lap(0, b): in this case, p p= 1;
N consists of i.idd GN(0, p)p
N has staircase distribution (Geng et al. 2015 ; in this case, p 1;
N Unif (B,(On,T) with > 0, where B, (O,,,,,)) r) = fx E R" ||x||p < rJ is the ba-ball centered at O,,.
3 Accuracy of Ranking Recovery
In this section, we seek to derive an expression for the probability of error of estimating Tx. In Section 3.1 first revisit low-complexity decoder, and show its optimality under the assumptions of Section 2 Then, in Section 3.2 characterize (e for this decoder. In Section 3.3 we derive accurate first-order approximation of Pe(g, K.), which we will leverage to characterize the privacy-utility trade-offs. Finally, in Section 3.4. we evaluate the derived first-order approximation of (o,,K) for the case when the data X is i.i.d. and n is large (i.e., the high-dimensional regime).
2This restriction can be thought of limitation of results. However, to make progress this problem in Bayesian framework, making assumptions eventually inevitable otherwise, the problem becomus intractable, and oue will not be able say much about the limits of permutation recovery. Assuming au exchangeable data distribution is reasonable whenever the data has natural order. particular example is relational data such social network users, ratings, and preference data [Lloyd 2012). The exchangeability assumption, our opinion, strikes good balance hetween how permutation recovery would behave practice and the problem theoretical solvability.
5

---

Published in Transactions on Machine Learning Research (07 (07/2022)
3.1 Optimal Decoder with Low- Low-Complexity
As illustrated in Section 2 the data collector uses decoder o(.) IR" + P to output fx. In what follows, we let dopt(> (-) denote the optimal decoder, i.e, the decoder that recovers fx such that the probability of error defined in 3 is minimized. We also consider a (potentially sub-optimal) decoder to which (borrowing the terminology used by Jeong et al. (2020) 2021 we refer as linear decoder and formally define below. Definition 3.1. Given the noisy data vector y R", the linear decoder is defined as
@tin = my:
(7)
where By denotes the permutation according to which is sorted.
The decoder in 7 is a special case of a more general linear decoder Tyy+b. where A E RRan and E R" such a linear decoder can be optimal when the noise has memory (Nomakuchi Sakata, 1988a b Jeong et al. 2020 In (7), we set A I and b O,.-
The linear decoder (-) has several advantages, among which its low-complexity: it simply consists of sorting operation and hence, it has complexity of Oon This is significant reduction with respect to the O(n!) complexity of naive brute-force implementation of the optimal decoder (.pp(.) based on the
maximum a posteriori (MAP) decision rule (Kay 1998). Moreover, as we will show in Theorem 3.3 the
linear decoder (-) is indeed optimal (i.e., Onin (+) = (.pr()) under the assumptions stated in Section
particular, to show this result we will leverage the following lemma (proof in Appendix B).
Lemma 3.2. For any two n-dimensional vectors Hy and y E Hy, and p 2 1, we have that
T E arg min ly -yy-P Xlp WEP
(8)
where Pa Pa-so is the permulation malriz that permules E Hy into Pa- E Ha.
Lemma 3.2 states that, when 1, the f--norm of the difference between two given vectors is minimized when the two vectors are sorted according to the same permutation. Lemma 3.2 allows us to prove our first main result, which is given by the next theorem.
Theorem 3.3. Let X E R" exchangeable, and assurne that the randomized mechanism K(a, X) adopts N Sn.p p p21 Then, given any noisy data vector y E I", we have that
Oope = Onin (y).
(9)
Proof. Since X is exchangeable, all hypotheses are cqually-likely (i.c., Pr(X E HG)= di Vr E P), and the maximum likelihood decoder optimal Kay 1998). This can be shown as follows,
dopt (y) = arg max Pr(X E H, |K(o,X)=>) y)
TEP
Pr(X Hcr
arg max TEP IKCO, (y) SK(G.XOY X E xH,
= arg max TEP
fk(G,) (y X E H.),
(10)
where fk((.)) is the PDF of K(oo, X). We note that the second equality follows by the Bayes' rule, and the last equality follows by the facts that Pr(X E H+) is a constant for all P and that fk(O.))(Y) is independent T. Therefore, given y Rn for K(a, X), optimal decoder is given by
popt (y) arg max (y X x+H. TEP
(11)
Since X and N are independent, the conditional density function in 11 can be written as
fx(O,)) X H.,) = / [x(x H.),HHH) x) dx
= n!
-x(pp) dx.
(12)
6

---

Published in Transactions on Machine Learning Research (07/2022)
where in the last equality used Definition 2.4 with g(-) being non-increasing function. Similarly, we have
xx X E Hny) = n! / (x (x) xl(p) dx
nl / 1 P du,
(13)
where 13 follows by substituting x Pr-
Now, by laking the difference between 12 and
13
oblain
1 n! (JK(ax)(y x x+) - (x X E H,)) = [
[x(x) (o(ly - x11p) - g(ll Pr)))xlp)))x (14)
XEHr
Using Lemma 3.2
we have that if y E Hr, then the integrand in 14 is always non-negative. Hence, for any sorted according to Ty, we have
(y) argaram max x) X E H,) TT ())(()) TEP
where the last equality follows from Definition 3.1 This concludes the proof of Theorem 3.3
Remark 3.4. We highlight that Jeong et al. 2020
2021 showed a similar result as in Theorem 3.3 for the
case of Gaussian noise, under some specific conditions on the noise covariance matrix. Theorem 3.3 extends the result on the optimality of the linear decoder beyond Gaussian noise, i..,, whenever E Sn.ps p 2 1. particular, to show this result we have leveraged completely new proof which uses a generalized version of the rearrangement inequality needed in the proof of Lemma 3.2 (see Appendix B
3.2 Error Analysis for dnin (+)
We here charactcrize the error probability the low-complexity and optimal (as proved in Theorem 3.3 under some assumptions) decoder (-)m()) in Definition 3.1 From (3), the error probability when v-m(.) used is
Po(onn: KC) = Pr(chi (K((a, X)) + xx).
Before deriving Pe(éiin KC), we first introduce the matrix T, (n- 1jxn for all E P, as follows
(T+). = Denat [f=n}
(15)
For instance, let 4 and 14)2 then,
0
1
T (122,1133)
1
-1
0
-1
0
1
0
Remark 3.5. For any exchangeable X R", have that Pyke 1965
T,X X X H, d W, VT EP,
(16a)
where W E ---1 is known as the spacing vector David & Nagaraja 2004 with
W, d = X, Xun, i [1 : n- 1],
(16b)
where Xin is the i-th order statistics of X.
The theorem below provides an expression for the error probability of the private ranking recovery problem when the linear decoder (-)(-) in Definition 3.1 used. In particular, this expression derived by considering the Taylor series of the error probability at 0.

---

Published in Transactions on Machine Learning Research (07/2022)
Theorem 3.6. Assume that oi+ Ws (ow) xo, for all C [1 n- where (0) (ow) = 3o (ww(ow) Then, the Taylor series of Pe (oun: K)) is given by
20 p(
Pe (e xC=
(17)
where
min
p(,)
Σ
(-1) (1)
(2)
klaj blal--kk)) (0 (0
and
(w) (w)
E
P (8-k) (wu)du,
0
I[ HER
1
where Fvz(-) the cumulative distribution function (CDF) of VI with V; No+1 N₂ for E [1 n 1].
We defer the proof of Theorem 3.6 to Appendix
Note that Theorem 3.6 (and also the following Corollary 3.7
gencralizes the result in Jeong et al. (2021) under two aspects: (i) from the first-order cocfficient to an
arbitrary order coefficient; and (ii) beyond Gaussian noise.
As an application of Theorem 3.6 we next present a corollary (proof in Appendix D) which provides the sccond-order approximation of Pe(Oni; KC) for ~ oN(O,,, and any exchangeable distribution of X.
Corollary 3.7. Let N ~ NoO.,, In) Assume that, for i,j E [1 n - 1], Ifw, (w)) < co, Ve and fw.,w,(u, < oo, v(u,v) v). Then, a second order approximation of Pe the low-noise regime is given by
Pe(Onn KN) = c1a + 022 +(00),
(18)
where
(0+)
VT
Sw, (0+) - 0.108998
n
Σ Sw. (0
1
Σ
Sw.,w, (0,),
(1)) 12141
We note that the constants and C2 in Corollary 3.7 depend on the distribution of X. Next, as example, we derive closed-form expressions for ej and 02 for X; ~ Unif(O, 1) and X, ~ Exp(A). The detailed proof of
these examples can be found in Appendix [ where we also provide various simulation results that graphically showcase the accuracy of the result in Corollary 3.7
Erample 3.8. Let X; Unif(O, 1) and N NO,,, II)) Then, the constants Ci and 02 in Corollary 3.7 are
n(n- 1)
G
Vx
~ 2 nn(n 1)2 10.108998mm(n - 1)(n 2) n(n - 1)(n - 2)(n - 3).
2x
Example 3.9. Let Xi ~ Exp(A) and N ~OO,,, I2), Then, the constants C₁ and 02 in Corollary 3.7 are
C1 n(n- - 1)A
2/T
C2 X2m(2n2 - 3m + 1) 0.108998
X2n(n - 1)(n - X2n(n - 1)(n - 2) - 3)
12
3
8M
Remark 3.10. If X is exchangeable and N E Sn.p. p21 1 in Theorem 3.6 then Pa (e K.) = Pe Peoppt K.). This
follows since under those conditions, from Theorem 3.3 we have Pope = (lan.)).
TTee approximation cg be made by replacing 0.198998 with its exact value E[max(0, Vi} max(0, V23) where V are defined in Thereom 3.6
8

---

Published in Transactions on Machine Learning Research (07 (07/202) 2022)
10
0:01
Pa Pohin
1
S10
1C KG
10.3
-0h 1st approx K. KG
K. RT.
-0 1st approx K. K.t.
K. KGN
-a- 1st approx K KAN
10
0.04
0.06
0.08
Figure 2: Pe Pe K)) vs. its first-order approximation.
3.3 First-Ordes Approximation for Pe
From Section 3.2 one can infer that the private ranking recovery problem is noise dominated, i.c., the error probability is large even when is small. For instance, Example 3.8 and Example 3.9 suggest. that the first-order coefficient сд grows quadratically with Thus, it becomes important to analyze the problem in the low-noise regime, where reliable permutation recovery can be possible (i.e,, P. < 1). Towards this end, we next derive the first-order expansion of Pe (e K)) with respect to a for any exchangeable N (note that Corollary 3.7 assumed ~ N'O,,, o2 I)). The proof the corollary below can be found in Appendix
Corollary 3.11. Let N be exchangeable and V N1 N2. Assume that fw. < oc, Vw. Then, in the low-noise regime, the first-orter upprozimation of Pa given by
CxE
Pe (c KC)
2 a + O(o?),
0(02))
(19)
with
n-1 Cx = fw,
(20)
Remark 3.12. The first-order approximation of Pa (o(in IC) in 19 decouples the effects of the input data distribution (captured by Cx) and of the noise distribution (captured by E[[V]). The assumptions of Corollary 3.11 are not too restrictive: as shown in Jeong et al. 2021 fw.(.) is bounded if X ii.d, and the PDF of X is bounded.
Remark 3.13. For the expansion of P. (o KC) in 19 natural question arises: How accurate is this? Figure (see more figures in Appendix E.1 shows that this approximation is indeed accurate when N E RM is i.i.d. according to three different distributions, namely Gaussian (red curve), Laplace (blue curve), and generalized normal with p = 0.5 (green curve). Our rationale for choosing such distributions is because in 4 we will establish privacy-utility trade-offs for them. In Figure ( the components X were chosen be i.i.d. according to Unif((, 100) with 20. The solid curves (probability of error) were obtained by Monte- Carlo simulation with 10 iterations, while the dashed curves (first order approximation of the error probability) where obtained by simply evaluating 19
Section

---

Published in Transactions on Machine Learning Research (07 (07/2022)
3.4 Input Data Vector with i.i.d. Entries
We here show that, for ii.. X, X, the dependence of the first-order approximation of Pe K) in 19 the distribution of X is rather weak (i..., it only needs the L2 norm of the PDF of X, and not the exact distribution). The approximation of Pa(ónn, KC) in (19) depends on the distribution of X only through Cx.
and this term can be expressed in closed-form as stated in the following proposition (proof in Appendix G
Proposition 3.14. Let X consist of i..dd random variables with PDF fx()). Then,
Cx n(n 1) where llfx = / (x)dx
(21)
According to Proposition 3.14 the first-order approximation of Pe Pe K)) depends on the distribution of X only through the Ly norm of its PDF. The significance of this result is that we do not need to know the exact distribution of the data vector to analyze Pe(tinn; K.).
Remark 3.15. Proposition 3.14 shows that Cx grows quadratically in n. We now provide few evaluations of Cx in 21
If X Unif(a, b), Cx = n(n-1), b-o
X Exp(A), Cx = An(n-1)
2
If ~ ~(0, 1), Cx n(n-1) 2VA
4 Privacy and Utility Trade-off
In this section, we investigate the relationship between privacy (measured by the (a,e)-RDP in Definition 2.2 and utility measured by Pa(Ou,; KC) In particular, we focus on the low-noise regime where, as highlighted Section 3.3 a reliable permutation recovery is possible.
For proper definition of DP, we need to consider "well-behaved" query functions Dwork 2008 This is the so-called sensitivity property which, for a query function q(-), requires that the sensitivity (formally defined below) is finite.
Definition 4.1 (l, sensitivity Liu 2018)). For all (X, X) X²2 such that du dx, X) S 1, the e, sensitivity of query g is defined
Ap(9)
llg(X) {(x)
(22)
(x
where p > 0.
The lp sensitivity is generalized version the E sensitivity for the Laplace mechanism (Dwork et al. 2006b and of the lg sensitivity for the Gaussian mechanism (Dwork Roth 2014). In our framework, we have that the query function q()) is the identity function, i.c., ((x)
Thus, in order to have finite Ep sensitivity
in [22], we need to have domain constraint on the data input, namely X E X' where X' = [x: E [0, {)
With this, from 22 we have that the tp sensitivity is given by
A = A(X)= = (x.X) (X
max
IX-XI, XII = E, Vp > 0.
(23)
and is finite. In what follows, we let A(X) = l denote the ln sensitivity for any p > 0, i.e., this notation indicates that the é, sensitivity is independent of p > O. Next, in Section 4.1 we derive a general expression for the urivacy-utility trade-off, which holds for any additive noise mechanism. Then, we evaluate it for practically relevant additive noise mechanisms, such as the Laplace (Section 4.2) the Gaussian (Section 4.3 and the generalized normal (Section 4.4p mechanisms.
10

---

Published in Transactions on Machine Learning Research (07 (0222)
4.1 On the General Trade-off
For the additive noise mechanism in given (a,e) and the sensilivity A(X) f in 23 we define the following operation,
RDP inf RDP (K(o, X)) & (,A(())
(24)
In words, (e, the smallest standard deviation of K(::)) that ensures that we meet the (a, < e-RDD constraint when the query sensitivity is equal to L. If the set in (24) is empty, then we set RDP (e, {) oc.
With the definition in (2 in mind and by using the first-order expansion of Peloum; K) in Corollary 3.11 arrive at the following general privacy-utility trade-off.
Proposition 4.2. Consider additéve noise mechanism K(o, X) in ( that adopts N E Sn.p- Let the assumptions in Corollary 3.11 hold. Then, the privacy-utility trade-off for the ranking recovery problem is given by
E[IVI[Cx
RDP : (((DP2'((.)))))
(o K.
(25)
2
where V and Cx are defined in Corollary 3.11
Remark 4.3. The Taylor series of the error probability in Theorem 3.6 allows to characterize higher order approximations for Pe Pe(oii K)), which in principle can lead to more accurate trade-offs in (25). The error term (((RDP in (25 arises from the approximation error in the Taylor expansion of Pe.
The expression in 25 can, in principle, be used to find a privacy-utility trade-off for any additive noise mechanism. As expected, from (25) we note that Pelmnn, K.): (i) decreases increases, and (ii) increases with the data size n. Moreover, for ii.d. data, by using the closed-form expression in [1] we obtain the following trade-off,
Pelotin n(n 1) [ II (e, 0 (()))=(((.))))
(26)
2
In the rest of this section, we soek evaluate Proposition 4.2 and provide results in terms of instead of the implicit function (e, Towards this end, we consider several important mechanisms for which the behavior of RDP_' () can be determined RDP-*(s, E) is already known and simply needs to be remapped to our notation (e.g., Gaussian mechanism). For other mechanisms, the expression for exists in closod-form, but the inverse RDP E) does not have a closed-form (e.g., Laplace mechanism). In such a case, we provide upper and lower bounds on RDP E) that indicate its behavior. Yet, in other cases, we find new expressions for RDP (c, E) (e.g., generalized normal mechanisms for = oo).
function of and L. For some mechanisms, the expression for
4.2 Laplace Mechanism
We consider a randomized mechanism (o, X) that consists of adding Laplace noise. Such a mechanism gives (a, R)DRDP as shown the next result, the proof of which uses the results by Gil et al. 2013 (proof Appendix
Proposition 4.4. For a > 1, the randomized mechanism Ko, X) Lap(O,b) gives (a,e)-RDP with e given by
2 with N being i.i.d. according
ae (1-())))t/(a)) - -(1 a) a-- (a)((a))
(27)
2a -
Morcover, letting ca n-1 In
we have that
20
i ca. ca ses l ob
1 ca - a
(2n-13
(28)
ab
We note that Proposition 4.4 is a generalization of the RDP analysis for the Laplace mechanism in Mironov 2017| that considered the 1-dimensional case. Although the generalization under the i.i.d. assumption is
11

---

Published in Transactions on Machine Learning Research (07 (07/2022)
straightforward and follows similar proof, we here reported the proof of Proposition 4.4 for completeness. In addition, the upper and lower bounds on are also provided, which we leverage next to provide the privacy-utility trade-off. Furthremore, the gap (i.e,, difference) between the upper bound and the lower bound in 28) given by _e- لل Thus, we can conclude that the bounds is not too small, and the bounds become tight as a + oc.
28 are moderately tight when a
We now combine Proposition 1.4 and Corollary 4.2 and obtain an explicit first-order approximation of Pe in terms of e and for the Laplace mechanism in the following corollary (proof in Appendix D.
Corollary 4.5. Let Kr be such that N is ii.d. according to Lap 0. +/2) Let the assumptions in Corollary 3.1 hold. Then, for a > 1, the privacy-utility trade-off is given by
3Cx
PeldhinKKi,
R
RDP
(29)
4/2
2
where
22
S RDP-D f), S /28
(30)
In 2a-1
Although Corollary 1.5 provides the trade-off in terms of upper and lower bounds, implics that the trade-off is at least. Pa 1 by considering the lower bound RDP (c, f). We note that for the case of 0o, which is equivalent to e-D,, the bound in (30 becomes exact and (e, x/2/
<
Remark 4.6. Since RDP (c, f) does not have a closed-form, the bounds on RDP, (c, E) in 30
were provided
to indicate its behavior with respect to and l. However, if one needs an exact value of RDP (e, E) for a given (c, f), this can casily be done numorically by inverting (27
As an example, we next evaluate (2 when X is i.i.d. and has a uniform distribution.
Enample 4.7. If X ~ Unif([0, () then Cx m(n-1) and the trade-off in Corollary 4.5 becomes
Pe(Oia KL) = 3n(n - 1) R R
( 2
(E) +0
4
where
< R
(c)
5
1
In
20-1
4.3
Gaussian Mechanism
We here analyze a mechanism Ko X) that consists of adding Gaussian noise. This gives (a, ()DP) shown in the next result, the proof of which can be found in Appendix and uses the results in Gil et al. (2013). We note that this result was already derived by Mironov (2017), but report it here for completeness
Proposition 4.8. Kola, X) in with N being i. according to (O. 1) gives (a,
ot 20
-RDP. Consequenlly,
RDP a (P,p"((c()))))
-
Val
al
(31)
2
We now evaluate the trade-off stated in Proposition 1.2
For independent standard Gaussian random variables
Ni and N2, we have that [[[ E||N, N2]] then obtain the urivacy-utility trade-off for the Gaussian mechanism as shown in the following corollary.
3/ By leveraging Proposition 4.8 and Corollary 3.11
Corollary 4.9. Consider the Gaussion mechanism KG(a, X) with N being i.i.d according to _N(00 1). Let the assumptions in Corollary 3.11 hold. Then, for 1, the privacy-utile trade-off is given by
PCx
Pe Po( Ko)
O
(32)
2n
"The approximation arises from the Taylor series of P. Corollary 3.11
12

---

Published in Transactions on Machine Learning Research (07 (07/2022)
From 32 observe that the Gaussian mechanism gives Pe that is inversely proportional to vē. while the Laplace mechanism in (29) offers a Pe that scales inversely proportional to as shown in Corollary 4.5 Thus, we can conclude that the Laplace mechanism outperforms the Gaussian mechanism in terms of the rate of the privacy-utility tradc-off. We complete this subsection by giving an example when X is i.id. and has a uniform distribution.
Example 4.10. If X Unif([O, (()), then Cx m(n=1)
b and the trade-off in Corollary 4.9 becomes
PelOting KG) n(n - 1) je to +o())
V Ve
4.4 Generalized Normal Mechanism
Corollary 1.5 and Corollary 4.9 suggest that P. x (1/e)1/r, where p is the power of the exponent in the noise PDF. In other words, the smaller the p is, the better the trade-off appears to be. Motivated by this observation, consider generalized normal mechanism (Liu 2018) denoted by KGN where N is i.i.d. according to GN(00, a. with < 1. Although can be greater than 1, we only consider S as motivated by the trade-off Pe x (1/e)1/P, Different from the previous RDP analysis for the Laplace and Gaussian mochanisms, we here study only c-DP for KGN (i.e., a = 20). Recall that c-DP offers a stronger privacy guaranlee than RDP. The e-DP of KaN is given in the next proposition (proof in Appendix K..
Proposition 4.11. Let N be ii.dd according to N GN(O, h())))))))) with I and h(p) = / r(-) is the gamma function. Then, the generalized normal mechanism KoN(a) gives eDP with
Tip-') r(3p by where
p
(33)
@h(pp)
Consequently,
RDP (e,
(34)
h(p))
Remark 4.12. We note that the work of Liu 2018 only considered integer values for the parameter The above result extends the work of (Liu 2018) to any E (0,
We combine Proposition 4.2 and Proposition
and obtain the trade-off in the corollary below.
Corollary 4.13. Consider the generalized normal mechanism KGN(a, X) with p S 1. Let the assumptions Corollary 3.11 hold. Then, the privacy- utility trade-off is given by
Pelotin KGN) EiIN -N'I
(1) 7
+0
(35)
2h(p)
where N and N' are independent and N' N.
Remark 4.14. Corollary 4.13 confirms our observation that the smaller the is, the better the trade-off is. Thus, for a = xo (or e-DP), the generalized normal distribution with p S offers a better privacy-utility trado-off than the Laplace and Gaussian mechanisms. In addition, note that the constant in the first-order term of (35) can be upper bound by using Jensen's 's inequality follows,
EJJN - N'I < E - -N = /2Var(N) = 22,
where we have used the fact that Var(N) = 1. Furthermore, seek to minimize order to find the best generalized normal mechanism given an eDD constraint. We refer to Appendix L where we discuss this and provide the best p.
35 with respect to in
13

---

Published in Transactions on Machine Learning Research (07/ (0722222)
5 Conclusions
We studied the private ranking recovery problem within the DP framework. We designed a low-complexity decoder and characterized sufficient conditions for its optimality. We derived the Taylor series of the error probability when such a decoder is used, as well as the first-order approximation of it. We leveraged the first-order approximation the error probability, along with the (a, e)-RDP, to obtain utility-privacy trade-offs for the Gaussian, Laplace, and generalized normal mechanisms. These results allow us to compare different noise mechanisms in order to determine the best utility-privacy trade-off. In addition, our results show that, the problem of private ranking recovery is noise dominated, i.c., the values of the noise variance. This suggests that the exact recovery imposed in our work might need to be relaxed. Finally, possible future directions include the following: (i) partial recovery in which we seek to recover the permutation of only part of the input data; (ii) approzimate recovery in which we allow a fixed number of errors given a ranking distance function (Kumar & Vassilvitski] 2010) (e.g., Hamming distance, Kendall's lau distance); (iii) investigating or generalizing the results this paper to hold universally, for any distribution on the input data vector.
probability is large
for small
Acknowledgments
The work of M. Jeong and M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757. The authors are grateful to the reviewers and the editor for useful comments and suggestions.
References
Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1964.
Daniel Alabi, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Private rank aggregation in central and local models. arXiv preprinl Xiv:v22 12. 14652, 2021.
Brendan Avent, Javier Gonzalez, Tom Diethe, Andrei Paleyes, and Borja Balle. Automatic discovery of privacy-utility pareto fronts. arXie preprint orxi::1905. 10862, 2019.
Jacob Baskin and Shriram Krishnamurthi. Preference aggregation group recommender systems for committee decision-making In Proceedings of the third ACM Conference on Recommender Systems, pp. 337-340, 2009.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Stefan Chanas and Prozemyslaw Kobylański. A new hcuristic algorithm solving the lincar ordering problem. Computational Optimization and Applications, 6(2):191-205, 1996.
Paul Culf and Lanqing Yu. Differential privacy as mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS '16, pp. 43 43-54, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450341394. doi: 10.1145/2976749.208888
URL https:://aat org/ 10. 1145/2976749 0t11//297774992978888 2978308
Herbert Aron David and Haikady Navada Nagaraja. Order Statistics. Wiley Online Library, 2004.
Cynthia Dwork. Differential privacy: survey of results. In International Conference on Theory and Applications of Models of Computation, pp. 1-19. Springer, 2008.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 933-4):211-400 2014.
Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th International Conference World Wide Web, pp. 613 622, 2001.
14

---

Published in Transactions on Machine Learning Research (07/2022)
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 486 503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 263-284. Springer, 2006b.
Alex Dytso, Ronit Bustin, H Vincent Poor, and Shlomo Shamai. Analytical properties of generalized Gaussian distributions. Journal of Statislicul Distribulions and Applications, 5(1):1-40, 2018.
Quan Geng, Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The staircase mechanism in differential privacy. IEEE Journal of Selected Topics in Signal Processing, 9(7):1176 1184, 2015.
Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. n noise-adding mechanism in additive differential privacy. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 11-20. PMLR, 2019.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 249:124-131, 2013.
Michael Hay, Liudmila Elagina, and Gerome Miklau. Differentially private rank aggregation. In Proceedings of the 2017 SIAM International Conference on Dala Mining, pp. 669 677. SIAM, 2017.
Jan Holstermann. A generalization of the rearrangement inequality. Mathemalical Reflections, 5(4), 2017.
Minoh Jeong, Alex Dytso, Martina Cardone, and H. Vincent Poor. Recovering data permutations from noisy observations: The linear regime. IEEE Journal on Selected Areas in Information Theory, 1(3):854-86)
2020. doi: N.1109/JSATTI 2020.334199.
Minoh Jeong, Alex Dytso, and Martina Cardone. Retrieving data permutations from noisy observations: High and low noise asymptotics. In Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), July 2021.
S. M. Kay, Fundamentals of Statistical Signal Processing, vol. 2: Detection Theory. Prentice Hall PTR, 1998.
Ravi Kumar and Sergei Vassilvitskii. Generalized distances between rankings. In Proceedings of the 19th international conference on World wide web, pp. 571-580, 2010.
Fang Liu. Generalized Gaussian mechanism for differential privacy. IEEE Transactions on Knowledge and Dala Engineering, 31(4::747 756, 2018.
James Lloyd, Peter Orbanz, Zoubin Ghahramani, and Daniel Roy. Random function priors for exchangeable arrays with applications graphs and relational data. Advances in Neural Information Processing Systems, 25, 2012.
Henryk Minc and Leroy Sathre. Some incqualitics involving (r!) 1/r. Proceedings of the Edinburgh Mathematioal Society, 14(1):41-46, 1964.
Nya Mironov. Réuyi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263 275. IEFE, 2017.
Saralees Nadarajah. A generalized normal distribution. Journal of Applied Statistics, 32(7):685-66) 694, 2005.
Kentaro Nomakuchi and Toshio Sakata. Characterization of conditional covariance and unified theory in the problem of ordering random variables. Annals of the Institute of Statistical Mathematics, 40(1):93 99, 1988a.
Kentaro Nomakuchi and Toshio Sakata. Characterizations of the forms of covariance matrix of an elliptccally contoured distribution. Sankhyā: The Indian Journal of Statistics, Series A, pp. 205 205-210, 1988b.
15

---

Published in Transactions on Machine Learning Research (07 (07/2022)
R. Pyke. Spacings. Journal of the Royal Statistical Society. Series B (Methodological) 27(3):395 449, 1965.
ISSN 00359246. URL http:://wwtt jstor org/ org/staabee/344799
Shang Shang, Tiance Wang, Paul Cuff, and Sanjeev Kulkarni. The application of differential privacy for rank aggregation: Privacy and accuracy. In 17th International Conference on Information Fusion (FUSION), pp. 1-7. LEEE, 2014.
Jordi Soria-Comas and Josep Domingo- Ferrer. Optimal data-independent noise for differential privacy. Information Sciences, 250:200 214, 2013.
Larry Wasserman and Shuheng Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105 105(4))) 389, 2010.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Securily, 15:3454 3469, 2020.
Ziqi Yan, Gang Li, and Jiqiang Liu. Private rank aggregation under local diffcrential privacy. International Journal of Intelligent Systems, 35(10):1495 1519, 2020.
A Proof of Example 2.5
A.1 Gaussian Noise
If N ~ No,,,, its PDF is
[|ll] 20 = =9(12 (((2))2),
[N(2) = (2
(36)
with s()
(2m 20
Since g()) is non-increasing function in 1 >> O, then W(nn, E Sn.2.
A.2 Laplace Noise
If N consists of i.i.d N₂ ~ Lap(0, 6), its PDF is
(N(
II
=9(12|1))
(37)
2b
(2b)a
with gt) = (26 ee which a non-increasing function in t > O. Thus, a joint distribution iidd Lap(0, b) is a member of Sn,1-
A.3 Generalized Normal Noise
If N consists of i.idd N; GN(O,, a, p),, its PDF is Nadarajah (005
II Kexp (-1 2 21")= K Kxexp
Ei |zil"
IN 22)
(38)
a
p where K = 2aF(1/p] is the normalization factor, and g(t) = K" KTexp (- 12
which is a non-increasing function
in / 0. Thus, joint distribution of i.i.d. GA a, p) is member of Sn.
16

---

Published in Transactions on Machine Learning Research (07 (022)
A.4 Staircase Noise
If N has staircase distribution with (A, ,, A), its PDF is of the form Geng et al. 2015
fN(2) = -B (M(())
(39)
with
k if | E [kA, (K- + +)A,, k 1 if |2//1 E [(k: + 7) (A: + 1)4},
h(z)
(40)
where 7 E [0 and A given, and / is normalization parameter.
Since (z)) is non-decreasing function in || then fN(z) is non-increasing in ||/|/1 Thus, staircase distribution is member of Sn,1-
A.5 Uniform Noise
Tf ~ (ni,(BB(Onn,))) r)) with r > O, its PDF is given by
[N(2) Vol(B, r)) (EEB,(0..)))
Vol(B, r)) (11)))))))
(41)
where Vol(S) denotes the volume of the set S. Clearly, the PDF in 41 is non-increasing function in ||z||p and hence, (ni((B,(0n,r)) is Sn.p-
B Proof of Lemma 3.2
Our goal is to show that a solution & for the following optimization problem,
arg min ||y - Pn-txx(ppp KEP
(42)
for any 7 P. H, and x E Hy, is given by & =. We start by noting that, by the property of permutation invariance of the f--norm, without loss of generality, we can consider = (1, .1,,,,..,n) which indicates that y is sorted in ascending order. In addition, a solution to 42 does not depend the permutation of x, i.e.
can start the problem with any H,, This beause we consider every possible permulation matrix Pa-ee's 's with P. Hence, set 1) = T, which implies that x is also sorted according to the ascending order, i.c., x and y are sorted according to the same permutation т.
The key tool that will enable our proof is the following generalized version of the rearrangement inequal- ity Holstermann 2017
Lemma B.1. Consider sequence of real numbers S... S and collection of functions f((.) [a, an] + R for i []:n] and for some fixed n. Suppose that for all x E [ai, anl we have that
(43)
Then, for any permuulation & E P, we have that
Σ [ann-it))) S > fi(Orn a
(44)
where ax; (Prrna) i nn]..
17

---

Published in Transactions on Machine Learning Research (07 (07/2022)
For the given Hr, in order to apply Lemma B.1 define sequence of functions
fi(t) 1h-i+1 tP, i E [1 [1:n] n).
(45)
Note that 1/1 S 1/2 S ... S Uh- For the time being assume that
((() S fjO,, W W
(46)
for all <. The claim in 466, which will be shown later, guarantees that use Lemma B.1
Therefore,
by setting 0; 2; in Lemma B.1 and recalling that x and are sorted according to the same permutation т, we arrive at
lly x
Un-i+1 Fn-i+11
i=1
(zn
fi (((
Un-itt1 Dxn-ex1 P
im
0n-i+1 (P (Pr=xX)n-441P
ly x p.
for all & E P. This indeed shows that, under the assumption
46 a solution for the optimization
problem in 42 is given by A =.
To complete the proof it remains to verify that the condition in 46 holds. Towards this end, observe that
f((t) p(t yn-i+1) Vn-i+1l"
for all E [1 n]. We now show that f((t)= < ft( for all t R and <.j. This follows by simple comparison, which consists of subtracting (t) from ft(,), namely
f1()) f5(() p(t 9n-s-1)lf 8n-s-1
p(t yn-j+tilit yn-j+1l
(47)
where In-i+1 Dn-ÿ+1 since y by assumption is sorted in ascending order. 447 less than or equal zero, then 46 holds. We now show that 447 is indeed always less than or equal zero.
1 E (-00, yn [+]] In this case,
47 becomes
f((t) (t() -p (in t)p-1 +p (yn-j+1 t)p-1
which is always less than equal to zero;
e [1n-j+11 Ba- i+1 In this case, 47
becomes
f((t) - ft( -p (yn-++1 - -t)-1 11-0----pp pp oot--yn-ttll yn-s411
which always less than or equal to zero;
t [8m-s41, In this case, 47 becomes
f()) (t) -p (t - Vn-141) pt yn-s4z)pー1
which is always less than or equal to zero.
The above three cases imply that the inequality 46) holds for any j and hence, the sequence of
functions in (45) satisfies (3) This concludes the proof of the desired claim and the proof of Lemma 3.2
18

---

Published in Transactions on Machine Learning Research (07 (022)
C Proof of Theorem 3.6
The probability of error is given by Jeong et al. 2021
Corollary 1),
T
Pelorin K.) - Pr
V
x
x E Hr
(48)
where T. is defined in [5). We now note that, from Remark vector W and hence, we can equivalently rewrite 48 as
3.5
can write T,X E H, as spacing
Vi m }
Pe (olii K2) =1
V < Wi }
Pr
2-1
(-1)--1 Σ
Pr (r(A))
(49)
1m 1
where the last equality follows from the inclusion-cxchusion principle where Az NiezA: with A, = (Va < -...
For any set [Z] = k, we have
V < W; })
n VET
Pr(Az) Pr
o
- SWERS
(W)
Fv..
fw: (w)dw
Fvz (-u) fwz (ou)o
(50)
HERk
where the last equality follows from a change of variable. By substituting
50 into
49
we obtain
n-1
Pelonns K.)
Σ
(-1)*taau(1))
(x
(51)
k=1
where
ax( = Σ /
(v,(-u)w,,(ouddd
(52)
HER*
IC -k
Let p(m) (ou)
T 3rm (wu). By the Leibniz integral rule, the m-th derivative of ax(o) w.r.t. a is
(m) (a) = Σ
Fyz (-z(-u) (u) (ou))) (ou)du.
(33)
uER!
I: 1]
1
Since 53 is bounded at 0+ (i.c., lim, 1a
(a) < (m)()))
(m))
00), after some trivial algebra, obtain that
the m-th derivative of Pe (e KC) in 51 at a + is
min nin(m,n-1)
p(m)
p(m) (
Σ
(-1)²-1
( kla (m
(m-k) k)+t))
(54)
a-+0+
We conclude the proof of Theorem 3.6 by plugging
54 into the Taylor series of P (e at 0+.
19

---

du Published in Transactions on Machine Learning Research (07 (07/2022)
D Proof of Corollary 3.7
Since Pe Pel0un: K) as + 0+, the first order rate is given from Theorem 3.6 by
((1)
lim
a
IC [[n=1]
uEER
[1=1
1-1
lim a-0
Pr(Ve S -u)sw:(ow) -w)
du
NUR+
Σ /
Q(o)/w, de
VERT
/ Q(u)V2 de
fw. (ot)
JERR
Sw; (0+)
(55)
where (a) follows using the change of variable u= 22v toegther with the fact that V, (00 with Q(-) being the Q function of the standard normal distribution; and (b) follows by the dominated convergence theorem.
The second order rate is also given from Theorem 3.6 by
2 (2- (0t)= oft (0 a2*0)).
2 2 Σ
p(2)
(-1)
Kla
(56)
k:
We need to compute aj (1 (0+) and (2())). Firstly, we have
(ot) = lim
Σ
Fv, (n(- du
Pr(vs -uyufu (oru) du
HER
/
fwr (0+)
Pr(Vi < -uju du
WEE+,
flv (0+) / JIER,
Q(v)2u du
= 2 Σ fw. (0*),
(57)
where the labeled equalitics follow from: (a) letting fw, (au)
= Sw sw. (w) (w) (b) using the dominated convergence theorem; and (c) using the change of variable 22 similar to the step (a) in 55
20

---

Published in Transactions on Machine Learning Research (07 (0222)
The second term in 566 is given from Theorem 3.6 by
(2(0)) = lim
Σ
Pr(Vz S - -u)/ww(ou) du
a=
[[ VER:
12|=2
Σ fw,(
/
Pr(Vz S -u) du
TC I=--1]
2
n-2
Σ fw.. (05)
Pr(V, S -u, Vi+1 S -u2) du
DERR
Σ
(0.)
Pr(V, -1 V,, S 22)) du
!uERq
(1)) j2++1
( Qr(u) du )²
Jw., (05) /
JuERR
Qvi du
Σ
fw.,w; (05)
(1.))(L2n-11p j3i+1
= E|max (0, ViJ max (0, 12))
Σ
Sw. Wan (0 E² [max (0, ViJl
Σ
Sw,,w, (0
==1
(1-))( j>141
0.108998
Jw.... (0+)+
1 π
Σ
Sw,., (0)),
(58)
(1.))(1mn-1f² j,1t1
where (a) follows by the dominated convergence thcorem; (b) is due to the independence of V, and V, if jl > (since V, = No+1 N₂ and V, = N5+1 N, with iid. N); (c) follows by noting that E max (0, V1} max (0, V2]] Fo 0.108998 and [max (0, ViHl =
By substituting and into 56
we obtain
n-1
n-2
2(2)
Σ
fwr (0+)
0.108998 0.109995
Σ
W... (0+)-
Σ
fw..w (0
(59)
2
(1.))(11nn112
j
This concludes the proof of Corollary 3.7
E Simulation Results and Proof of Example 3.8 and 3.9
E.1
Simulation Results shown in Figure 3
For the simulations illustrated in Figure 3 we set Unif 1) and Exp(1) for X,,i E [L rJ and NN The curves for the true error probability (elim) were obtained by Monte-Carlo simulation using 10 iterations, whereas we obtained the curves for the first. and second order approximations by evaluating the expression in Corollary 3.7 The data dimension set to n = 10 for (a) and (b), and to n = 20 for (c) and (d). It is shown from (a) and (c) that the first and second-order approximations well fit the truc P. (o(mn)) around a = Further, (b) and (d) show the approximations in the low-noise regime and illustrate that, the targeted error probability is small, then the first-order approximation is very close to the true error probability.
21

---

Published in Transactions on Machine Learning Research (07/202) 2022)
Pliuu 1)
Pajea.XX Unaf(0 1)
0.9
(du). Unif(0 1)
P. (dta), ()
(en) x 1
0.05
0 A. (Ax). (o.5(0
0.8
P.luu x Exp(l)
0 P. Exp(1)
0.7
R [dh.. Exp(1)
(dua), Exp(1)
+ R. (0m). (0m)) X Exp(l)
0.04
0 P. (4x). Esp(3)
0.6
02
0.03
0.4
0.02
0.3
0.2
0.01
0.1
0.005
0.01
0.015
0.02
2
10
x10
(a)
(b)
0.07
P.oanli Unif(0,
0.9
P. (dta) Unit(o
0.06
A (0n), Unit(o.
600
0.8
9 P. Iohai Unif(0
(0.), Uni((o
P.0nl. Exp(1)
B(ba). Exp(I)
0.7
+ P. (.x.). X Exp(1)
0.05
R. (0x.). Exp(1)
+ P. (dhal, X Exp(1)
P. (dha.. Exp(1)
0.6
40 0.5
0.09
0.4
0.3
0.02
0.01
0.1
0
x10
x10
(c)
(d)
Figure 3: Comparison between (omnn) the first-order approximation P1at (dun), and the second-order
approximation fand (chin). We set X, ~ Uni[(0, 1) and X, ~ Exp(1) for E n]: (a) n = 10; (b) n = 10 low-noise; (c) 20; (d) n 20 in low-noise.
E.2 Proof of Example 3.8
To evaluate the expression in Corollary 3.7 we need Sw, (0
fy (0+) and (0 For X, Unif(O, 1),
the PDF of the spacing W; and W,, W. are given by Pyke 1965
fw, (w) = n01 w) w)-- Vi E [1 :
1).
(60)
fw.,w, (u = nnnn - 1)(
w)" n Vi Vi+ * j.
(61)
which gives
Jw; (0:(0) n, Vi,
Jw.ww (0%) n(n - 1), Vi +
By differentiating
60
with respect to we also obtaîn
fw. (w) = -n(n - 1) w: w)nn fw, (w,(0t) -n(n 1), Vi.
22

---

Published in Transactions on Machine Learning Research (07 2022)
This concludes the proof of Example 3.8
E.3 Proof of Example 3.9
To evaluate ej and 62, make use of the fact Pyke 1965
that the spacings of Exp(A) random variables are independent exponential random variables with parameters depending on the dimension n and A. Specifically, for ii.d. X; ~ Exp(A) the spacings become independent Wi's that are distributed as
W; Exp(A(n - i)). Vi E [1 [1:n- 11:n-111 11.
(62)
It then follows that
fw; (0+)) lim X(n - i)e 100--1o A(n-()))) = A(n - i), Vi,
(63)
w-+01
fw..w, (0t) fw. fw, fw;(00) )- >2 i)(n - -j], Vi + j.
(64)
It is also easy to evaluate
fw, (0+ = lim
-2² e)2e >(n-i)w 22 - 2)? Vi.
(65)
--+
By substituting Example 3.9
63
and
65
into and 02 in Corollay 3.7 with some algebras, we conclude the proof of
F Proof of Corollary 3.11
Since Pelvin KC) 0 as + 0+, the first order rate is given from Theorem 3.6 by
Pelona K) = p! O(o²).
(66)
where
p(2) =01(0t)
lim
Σ
/
Fvzl Fvz(-u)fw((ou) du
UER
[[ Z|=1
n-1
lim
Pr(V, S -u)fw,(ou)) du
a
Pr(Ki 2 (ou) du
fw. (0t) / Pr(Vi 2 u) du
/ E [[] du Sw. (o+)
Sw: (0+)
1 ( du [axx(Vi.u
Sw. (0+) E
1 du
fw. (o+) E [max f 0H
fw. (0+ [[V]]]
(67)
23

---

Published in Transactions on Machine Learning Research (07 (07/2022)
where the labeled equalities follow from: (a) the exchangeability N (i.e., Vi = -N 1 N, = -V and V2 = v v(i,)); (b) the dominated convergence theorem; (c) the Monili-Tonelli theorem; and (d) the
symmetry of V as we have used in step (a). We conclude the proof of Corollary 3.11 by substituting
into 166)
G Proof of Proposition 3.14
For i.d. X; ~ Fx, where Fx is the CDF of X, we observe that Pyke 1965
Σ fw. Σ
n-1 1 n-1
1)1(n= - i 1)! {
n!
(IX()))
dr
n!
1)l(n - -i -1 - de
(i
n
(n-i+ (o- dr
-- - dr,
(68)
where (a) follows by using the Fubini-Tonchl theorem, and (b) follows from the change of variable j = - To simplify the integrand in 68), we make use of the following,
(n -1
Σ
(n j)(n - (
==U
(4)
E [nn Bn B- 1)] - (x)
= n - 2n -
[ (1-
= nnn -))))))))+ + +x7 -x(x))-
(n² -
-
nnn 11((1 (xx(x)+++++))+ = =n(n 1),
-xxxx)
(69)
where in (c) we let B ~ Bin(n, Fx (x)) be the binomial random variable with parameters n and Fx(x), and the expectation is with respect to B.
Then, we have
(ot) / n(n 1)f((z)dz
n(n 1) / (x(ddr.
This concludes the proof of Proposition 3.14
Proof of Proposition 4.4
We consider the Laplace mechanism such that.
Kz(a,X)= X + oN,
24

---

Published in Transactions on Machine Learning Research (07 (0722222)
where N is i..d. according to L).( This result has already been shown by Mironov 2017 and we present it here for completeness. By using the definition of (DP.(Kr) in Definition 2.2 we obtain
RDP (KC))
sup (a((()))I((())
(x (X
(
sup Pr-=
Da (1 |bl Lap(22, ob))
sup Da (O, ob)l ob))
rE(0,4]
1
In ae (1- (1 ane aar/(b))
sup
rE(o,]]
a
2a -
( ae ae (e--(aa)//(05) (1 a)e-at/(ob)
(70)
2a 1
where the labeled equalities follow from: (a) the fact that K(XX and KC have nearly identical distributions that differ only one coordinate; (b) the closed-form expression by Gil et al. (2013): and (c) the fact that
Da [La((, ab)) ab)) is increasing function in Therefore, (o, X) gives (a, c)-RDP with given in 70p.
For the upper and lower bounds, we first obtain an upper bound by using the concavity property of the logarithm and its first-order condition (Boyd et al. 2004), i.c.,
In(z + y) _ 1n(2))) + x² ky.x> 0.
(71)
Using the above inequality, we can upper bound 70 as
1
In ae (1 (1-0)8((o))
a)e aaf((bb)
a 1
2a
1
In (rela-1e/((b))
(a 1)e
a 1
2a
ae (a- 1)e/(ab)
1
aela- 1)8/(ab))
12a 1>8
ln
e
a
2a
1
a
L
1
a
(20-1)6
In
(72)
ab
-
20
A lower bound can be obtained by dropping the second exponential term in
70
1
ae (1 (11-a){((ob)
c 2
In
a
1
2a 1
{
1
a
+
In
(73)
ob
1
2a 1
This concludes the proof of Proposition
4.4
Proof of Corollary 4.5
From the lower bound in 28 in Proposition
4.4 we directly obtain the lower bound of a as
S a.
(74)
b
1 In
2a-1
a-1
In addition, the upper bound in
28 can be further bounded by
(75)
ab'
25

---

Published in Transactions on Machine Learning Research (07 (022)
which follows from the fact that - In 2a-1 + e and & 2 O, and the limit is 0, i.e.
(2a 1)
increasing a 1 for any values of o > 0, 0,
Cx
12 11
lim 00
In
+
-C
ob
0.
2a 1
The bound
75 gives the upper bound on a as
(76)
be
and hence, with 74 we have that, for the Laplace mechanism,
RDP (c, bc
(77)
E q In 2a-1
We now leverage Proposition
4.2
which requires B[[]]- In order to have Var(N) for N ~ Lap(O, b), we follows. The PDF of V Nı N2, where N₂ and N2 are independent
set /2 and evaluate E
Lap (o. )
is given by
/
fv(0)
(2) 2) dz
V2
v2
de
V2
V2
/2/0|
1
1//
/2[ul
(78)
2/2
2
Then, by the symmetry of V we have
//00
vfv(v) de 3
E
V =
(79)
2
We obtain the trade-off expression by combining
77 and
25
3Cx
Polonin KC)
RDP RDP (c, +0
(80)
4/2
where
22
RDP-D (E, < V2e
(81)
In 2
a-1
This concludes the proof of Corollary 4.5
J Proof of Proposition 4.8
Consider the Gaussian mechanism such that
Kola, X)= X + +NN,
26

---

Published in Transactions on Machine Learning Research (07 (07/2022)
where N is ii.d. according to (o 1). By using the definition of RDPa in Definition 2.2
obtain
RDP
sup (x
(a(((()|I((X))
(
sup
-
Da (a ((
sup rEjo,q
1 arp
sup
re0,
o²
1 al
(82)
o²
where the labeled equalities follow from: (a) the fact that XC(X) and KC(X) have nearly identical distributions
that differ at only one coordinate; (b) the closed-form expression by Gil et al. (2013) and (c) the fact that obtain
and oz is an increasing function in r. Using 24
af
RDP (E, = -
(83)
2
This concludes the proof of Proposition 4.8
K Proof of Proposition
We start by noting that oN with N ~ GN h(p).p) has variance equal to o² and PDF given by Nadarajah (2005).
(-1-222)) p [h(pp)
(Th(p)) )
faN(z)= = -Kxxp
(84)
where h(p) / r(p-t) r(3p 17 and K (p Tj.
Since (xc,c)-RDP.. is equivalent to e-DP, we evaluate the Rênyi divergence of order a: = 0o. From Definition 2.2 the Rényi divergence of order a = oo between x + oN and + oN with du (x, x) <
Dxo(K(x ( + +o)) (a) Doo + + ON))I(((NN)
(a r)
sup log ZER
SON (z)
r ah(p)
sup 2ER
+
[h((p)
r
(85)
ah(p)
where the labeled equalities follow from: (a) the fact that [-e, is the difference between and x, and without loss of generality we consider positive E [0, due to the symmetry of N; (b) the definition of the Rényi divergence of order = oo; and (c) the fact that the maximum of the function & 1 1/p - |t - r| is obtained at = r for < < 1.
Since 85 is an increasing function in r [0, E), we obtain
RDP >KaN) sup re ah(p)
(86)
or hh(p))
This concludes the proof of Proposition 4.11
27

---

Published in Transactions on Machine Learning Research (07 (0722)
L
Minimizing
335
with respect to 0 < p S 1
To find the minimum value (or minimizer) of h(p) (2) with respect to p S 1, differentiate it with respect to p and obtain
0
1 = (V T(p-1)
T(3p-) 1)
3p
h(p)
Op
Op- a
T(3p-)
Op 0p-1
T(w-1)
(x)
0p 0
v (3a -mn
(1)
Op dr
1 (3v(3r) - (xxx) -2 c)
T(3z)
1
p²
[(x)
r 2
(3b(3p - (bp 2 2l
(87)
2p
where the labeled equalities follow from: (a) the change of variable p= and (b) letting (xx)
de In ((x)= = T()
[z)x) be the digamma function Abramowitz & Stegun 1964, p.258).
By using the change of variable = --- [1, oc), have equivalent expression for the derivative,
x² r(3z) T(x)
( (3t((2)) - vxx) 2n
(88)
2 T(x) (2)* is negative for all x E (o), it sufficient to consider the last term (34(3z) - (x) 2 In e). The digamma function (x) does not have a closed-form expression and hence, instead use the approximation (xx)) z In 1 where S < 2 is constant. This approximation
Since the sign of 2 T(3z)
expression comes from the following bounds Minc & Sathre 1964
Lemma 2) for 2 1,
S (bx)) In 1
I
(89)
x
2r
Using (bx)) 2 In x cx we have that
(3x))) - (xx) - 2lne Ro In(27=²) lnea.
(90)
which is increasing in x. Hence, 88 is negative if 3/3 < and is positive otherwise, which implies that the
minimum value of h(p] (+) can be obtained by choosing p such that = = 3/3 Due to the condition
S 1, we finally obtain the approximed minimizer for hpp) (t) given by
3333 1
p = min
(91)
Noto that an exact expression for the minimizer is = min(p', , 1} where p' is such that
v ( 2 2ln = 0,
34b
(92)
1
which be obtained numerically.
28


Reviews:
[{"review_id": "8NJibi8DDi", "reviewer": "Reviewer_iKza", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem setting is well motivated and the presentation is generally clear. I checked the proof of Theorem 3.3 and it makes sense and is correct to the best of my knowledge. The weaknesses I see are the following:\n1. The privacy part is really only relevant at the end, and moreover the privacy-utility tradeoff is a bit heuristic (as I will elaborate), so the paper can be thought of as just dealing with ranking recovery from a noisy data vector (where the noise has to satisfy certain regularity properties). In this way the problem setting seems to be the same as what was considered by Jeong et al. Remark 3.4 clarifies that there are some technical improvements over these prior results, so it seems that the paper checks the novelty box.\n2. Many technical statements seem imprecise and too informal for my taste. For example, at the beginning of the proof of Theorem 3.3, it says that “the maximum likelihood decoder is optimal [for minimizing the probability of incorrect recovery]” and there is a reference to a whole book. While I don’t think there is a bug in the proof, this is a kind of statement that requires either a more precise reference or a proof. Please formalize. The results in Section 4 are likewise informal; since the probability of error is only approximated using a Taylor series argument, I wouldn’t call statements such as Theorem 4.2 and Theorem 4.5 “theorems”. Please either clarify that this comparison is heuristic given that an approximation for the error is used, or make a rigorous mathematical statement.\n3. While the paper positions itself as a privacy paper, the actual privacy discussion is fairly trivial. In particular, the non-trivial analysis is in analyzing ranking recovery from noisy data (which is not a newly analyzed problem). At the end the privacy only comes in when relating the noise level to a privacy parameter, and these identities are well known. Please cite the corresponding results in Mironov (2017).\n4. There are several small points that need or are worth addressing:\n\na) For example, in Section 4 sensitivity is defined as l1-sensitivity but the different noise mechanisms require different sensitivity measures (Gaussian requires l2—I know l1 bounds l2 but relying on this bound seems a bit sloppy). \n\nb) There is no sigma anywhere in the proof of Theorem 3.3 even though it’s a parameter of the randomization, please fix. \n\nc) It is remarked that the probability of error grows quadratically in n; what is preventing this value from exceeding 1? For example, in Example 3.8, as we let n tend to infinity wouldn’t c1 go to infinity and thus Pe>1? \n\nd) In the definition of alpha_k(sigma) on page 7, I was confused by the use of sigma as the argument since you’ve been using sigma as the noise magnitude. \n\ne) The correct reference for DP is “Calibrating noise to sensitivity in private data analysis”, Dwork, McSherry, Nissim, Smith (2006) (top of page 2 in the submission).\n\n5. I don’t understand the motivation for studying the generalized normal model. Can you give some important references in DP that study this noise model? It doesn’t seem nearly as fundamental as the other two and the analysis for it is looser.\n6. I don’t understand the comment saying “private ranking recovery is noise dominated”; please elaborate.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission studies the problem of recovering the ranking of data vector entries given a privatized version of the data. The main contributions are the following: 1) showing that a simple, computationally efficient mechanism (in a way, the “obvious” one) for ranking estimation is optimal under potentially restrictive but reasonable assumptions; 2) approximating the probability of error in ranking recovery via a Taylor series argument; 3) (heuristically) quantifying the tradeoff between Renyi differential privacy and probability of error given a Taylor approximation.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The requested changes are outlined in the previous section. Point 2 is the most critical to address.", "broader_impact_concerns": "I don’t think the paper raises broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ND50iKkIKT", "reviewer": "Reviewer_P18b", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nI think the problem of the paper is interesting and important. The authors nicely combine ranking problem and the differential privacy tools to protect the data privacy. The authors have adequately cited related work as well as honestly commented on differences and similarities with existing literature. The analysis is not entirely novel but it is definitely interesting.\nThe submission looks technically sound and makes a solid theoretical contribution. And the authors kindly give some examples to make the results more readable.  I did go through the proofs in detail and they seem to be correct. It is good to bring some simulations results for different distributions of input data.\n\nWeaknesses:\nThe authors give three upper bounds for trade-off, but there is no evidence (such as lower bound) to show whether they are optimal. The authors should give some experiments on real world data to verify the theoretical results. \n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studied private ranking recovery problem by using Gaussian, Laplace and generalized normal model as randomizer under Renyi differential privacy. The authors aim to establish the trade-off between privacy and utility by measuring the probability error in estimation and the level of privacy in RDP. When linear decoder is employed, they derive Taylor series of the probability of error, and use first and second-order approximations to characterize trade-offs between privacy and probability of error.\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The authors should give some experiments on real world data to verify the theoretical results.\n\n", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rzYN7LlYY0", "reviewer": "Reviewer_NH5D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The approach based on the analysis of the error estimation probability $P_e$ (Eq. 3) for rankings of noisy vectors seems interesting and might be useful addition to DP literature.\n\n- The paper is mostly well written, easy to follow.\n\nWeaknesses:\n\n- I think the main weakness is that the contribution seems quite thin. The only valid RDP bounds are those of Prop. 4.1 (simply a Laplace mechanisms RDP, given already in reference Mironov, 2017), and that of Prop. 4.7. The bound of Prop. 4.7 is not really an RDP bound as it only gives the cases $\\alpha=1$ and $\\alpha=\\infty$, i.e. the KL and pure eps-DP bound. \n\n- Some of the results are hard to read. I cannot understand why the error function $P_e$ appears in the $\\varepsilon$-approximations of Section 4. As far as I see, looking at eq. 2, the noise adding mechanism which is analysed in these results is inpendent of the error function $P_e$. It is quite uncommon in DP literature to give approximations for epsilon-values (security mindset, we should always report upper bounds), and especially here I think it is very unclear how rough these approximations are.\n\n- The basics of DP and RDP should be introduced more carefully. I think that the claim on. p 2 that RDP encompasses eps-DP and (eps,delta)-DP is wrong.\n\n\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers \"the private ranking recovery problem, where a data collector seeks to estimate the permutation/ranking of a data vector given a randomized (privatized) version of it.\"\n\nIt considers the Rényi differential privacy (RDP) for a mechanism that for input data vector X adds noise N, where N is $\\ell_p$ - spherical noise, in particular '$\\ell_p$ - spherically non-increasing'. This is related to the 'ranking recovery' problem presented in \n\nMinoh Jeong, Alex Dytso, and Martina Cardone. Retrieving data permutations from noisy observations: High and low noise asymptotics. In Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), July 2021,\n\nupon which this works seems to build (lot of similar notation used as well).\n\nApproximations for the $\\varepsilon$-RDP values of various noise adding mechanisms are given, as well as few strict bounds.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think the paper would need a major revision before being ready for publication. \n\nFirst of all, the results should be rewritten: I do not see a reason for having the error function in the RDP bounds if the noise adding mechanism is the one that is being analysed. Also, here, the property of post-processing of DP (and of RDP, due to data processing inequality) would be useful. Otherwise, I would imagine that the error function $P_e$ could be useful in case the output of the RDP mechanism would be the ranking, for example.\n\nThe $\\varepsilon$-approximations of Section 4 should be replaced by upper bounds. In that case the expansion of $P_e$ given in Thm 3.6 might be less useful as it seems to be quite a complicated expression.\n\nThere should be some illustration of the tightness of the obtained bounds.\n\nAll of these are crucial in my opinion, the paper is not ready for publication.", "broader_impact_concerns": "This is theory paper and would potentially improve differential privacy techniques, I do not see anything reason for having a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were pleased by the significant revisions performed by the authors, which addressed their comments. While some reviewers still feel that the contributions are somewhat modest, they all nonetheless supported the paper for acceptance as-is. 

Indeed, consulting the two guidelines for acceptance:
- Are the claims made in the submission supported by accurate, convincing and clear evidence?
- Would at least some individuals in TMLR's audience be interested in the findings of this paper?
the reviewers felt that both were true, and thus the paper should be accepted.
Decision: Accept (poster)