James Bell

Aurélien Bellet

Adrià Gascón

Tejas Kulkarni

Private Protocols for U -Statistics in the Local Model and Beyond

In this paper, we study the problem of computing U -statistics of degree 2, i.e., quantities that come in the form of averages over pairs of data points, in the local model of differential privacy (LDP). The class of U -statistics covers many statistical estimates of interest, including Gini mean difference, Kendall's tau coefficient and Area under the ROC Curve (AUC), as well as empirical risk measures for machine learning problems such as ranking, clustering and metric learning. We first introduce an LDP protocol based on quantizing the data into bins and applying randomized response, which guarantees an -LDP estimate with a Mean Squared Error (MSE) of O(1/ √ n ) under regularity assumptions on the U -statistic or the data distribution. We then propose a specialized protocol for AUC based on a novel use of hierarchical histograms that achieves MSE of O(α 3 /n 2 ) for arbitrary data distribution. We also show that 2-party secure computation allows to design a protocol with MSE of O(1/n 2 ), without any assumption on the kernel function or data distribution and with total communication linear in the number of users n. Finally, we evaluate the performance of our protocols through experiments on synthetic and real datasets.

INTRODUCTION

The problem of collecting aggregate statistics from a set of n users in a way that individual contributions remain private even from the data analysts has recently attracted a lot of interest. In the popular local model of differential privacy (LDP) [START_REF] Duchi | Local privacy and statistical minimax rates[END_REF][START_REF] Kairouz | Extremal mechanisms for local differential privacy[END_REF] Proceedings of the 23 rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020, Palermo, Italy. PMLR: Volume 108. Copyright 2020 by the author(s). et al., 2014), users apply a local randomizer to their private input before sending it to an untrusted aggregator. In this context, most work has focused on computing quantities that are separable across individual users, such as sums and histograms (see [START_REF] Bassily | Local, private, efficient protocols for succinct histograms[END_REF][START_REF] Wang | Locally differentially private protocols for frequency estimation[END_REF][START_REF] Kulkarni | Answering range queries under local differential privacy[END_REF][START_REF] Cormode | Marginal release under local differential privacy[END_REF]Bassily et al., 2017, and references therein).

In this paper, we study the problem of privately computing U -statistics of degree 2, which generalize sample mean statistics to averages over pairs of data points. Let x 1 , . . . , x n be a set of n data points drawn i.i.d. from an unknown ditribution µ over a (discrete or continuous) domain X . The U -statistic of degree 2 with kernel f , given by U f,n = 2 n(n-1) i<j f (x i , x j ), is an unbiased estimate of U f = E x,x ∼µ [f (x, x )] with minimum variance [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]. The class of U -statistics covers many statistical estimates of interest, including sample variance, Gini mean difference, Kendall's tau coefficient, Wilcoxon Mann-Whitney hypothesis test and Area under the ROC Curve (AUC) [START_REF] Lee | U -statistics: Theory and practice[END_REF][START_REF] Mann | On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other[END_REF][START_REF] Faivishevsky | ICA based on a Smooth Estimation of the Differential Entropy[END_REF]. They are also commonly used as empirical risk measures for machine learning problems such as ranking, clustering and metric learning [START_REF] Kar | On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions[END_REF][START_REF] Clémençon | Scalingup Empirical Risk Minimization: Optimization of Incomplete U-statistics[END_REF].

Interestingly, private estimation of U -statistics in the LDP model for arbitrary kernel functions f and data distributions µ cannot be straightforwardly addressed by resorting to standard local randomizers such as the Laplace mechanism or randomized response. Indeed, one cannot apply the local randomizer to the terms of the sum based on the sensitivity of f (as each term is shared across two users), and perturbing the inputs themselves can lead to large errors when passed through the (potentially discontinuous) function f . In this work, we design and analyze several protocols for computing U -statistics with privacy and utility guarantees. More precisely:

1. We introduce a generic LDP protocol based on quantizing the data into k bins and applying kary randomized response. We show that under an assumption on either the kernel function f or the data distribution µ, the aggregator can construct an -LDP estimate of U f,n with a Mean Squared Error (MSE) of O(1/ √ n ).

2. For the case of the AUC on a domain of size 2 α , whose kernel does not satisfy the regularity assumption required by our previous protocol, we design a specialized protocol based on hierarchical histograms that achieves MSE O(α 2 log(1/δ)/n 2 ) under ( , δ)-LDP and O(α 3 /n 2 ) under -LDP, for arbitrary data distribution.

3. Under a slight relaxation of the local model in which we allow pairs of users i and j to compute a randomized version of f (x i , x j ) with 2-party secure computation, we show that we can design a protocol with MSE of O(1/n 2 ), without any assumption on the kernel function or data distribution and with constant communication for each of the n users.

4. To evaluate the practical performance of the proposed protocols, we present some experiments on synthetic and real datasets for the task of computing AUC and Kendall's tau coefficient.

The paper is organized as follows. Section 2 gives some background on U -statistics and local differential privacy. In Section 3 we present a generic LDP protocol based on randomizing quantized inputs. Section 4 introduces a specialized LDP protocol for computing the Area under the ROC Curve (AUC). In Section 5, we introduce a generic protocol which operates in a slightly relaxed version of the LDP model where users can run secure 2-party computation. We present some numerical experiments in Section 6, and conclude with a discussion of our results and future work in Section 7.

BACKGROUND

In this section, we introduce some background on Ustatistics and local differential privacy.

U -Statistics

Definition and Properties

Let µ be an (unknown) distribution over an input space X and f : X 2 → R be a pairwise function (assumed to be symmetric for simplicity) referred to as the kernel.

Given a sample S = {x i } n i=1 of n observations drawn from µ, we are interested in estimating the following population quantity:

U f = E X1,X2∼µ [f (X 1 , X 2 )].
(1)

Definition 1 [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF]. The U -statistic of degree 2 with kernel f is given by

U f,n = 2 n(n-1) i<j f (x i , x j ).
(2)

U f,n is an unbiased estimate of U f . Denoting by

ζ 1 = Var(f (x 1 , X 2 ) | x 1 )) and ζ 2 = Var(f (X 1 , X 2 ),
its variance is given by [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF][START_REF] Lee | U -statistics: Theory and practice[END_REF]:

Var(U f,n ) = 2 n(n-1) (2(n -2)ζ 1 + ζ 2 ). (3)
The above variance is of O(1/n) and is optimal among all unbiased estimators of U f that can be computed from S. This incurs a complex dependence structure, as each data point appears in n-1 pairs. The statistical behavior of U -statistics can be investigated using linearization techniques [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF] and decoupling methods (de la Pena and Giné, 1999), which provide tools to reduce their analysis to that of standard i.i.d. averages. One may refer to [START_REF] Lee | U -statistics: Theory and practice[END_REF] for asymptotic theory of U -statistics, to [START_REF] Van Der Vaart | Asymptotic Statistics[END_REF] (Chapter 12 therein) and (de la Pena and Giné, 1999) for nonasymptotic results, and to [START_REF] Clémençon | Ranking and empirical risk minimization of Ustatistics[END_REF][START_REF] Clémençon | Scalingup Empirical Risk Minimization: Optimization of Incomplete U-statistics[END_REF] for an account of U -statistics in the context of machine learning and empirical risk minimization.

Motivating Examples

U -statistics are commonly used as point estimators of various global properties of distributions, as well as in statistical hypothesis testing [START_REF] Lee | U -statistics: Theory and practice[END_REF][START_REF] Mann | On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other[END_REF][START_REF] Faivishevsky | ICA based on a Smooth Estimation of the Differential Entropy[END_REF]. They also come up as empirical risk measures in machine learning problems with pairwise loss functions such as bipartite ranking, metric learning and clustering. Below, we give some concrete examples of U -statistics of broad interest to motivate our private protocols.

Gini mean difference. This is a classic measure of dispersion which is often seen as more informative than the variance for some distributions [START_REF] Yitzhaki | Gini's Mean Difference: A Superior Measure of Variability for Non-Normal Distributions[END_REF]. Letting X ⊂ R, it is defined as

G = 2 n(n-1) i<j |x i -x j |, (4)
which is a U -statistic of degree 2 with kernel f (x i , x j ) = |x i -x j |. Gini coefficient, the most commonly used measure of inequality, is obtained by multiplying G by (n -1)/2 n i=1 x i . Remark 1. The variance of a sample, obtained by replacing the absolute difference by the squared difference in (4), is also a U -statistic. However we note that computing the variance can be achieved by computing two sums of locally computable variables (x i and x 2 i ), which can be done with existing LDP protocols.

Rényi-2 entropy. Also known as collision entropy, this provides a measure of entropy between Shannon's entropy and min entropy which is used in many applications involving discrete distributions (see Acharya et al., 2015, and references therein). It is given by

H 2 = -ln 2 n(n-1) i<j I[x i = x j ] .
(5)

The expression inside the log is a U -statistic of degree 2 with kernel f

(x i , x j ) = I[x i = x j ].
Kendall's tau coefficient. This statistic measures the ordinal association between two variables and is often used as a test statistic to answer questions such as "does a higher salary make one happier?". In learning to rank applications, it is used to evaluate the extent to which a predicted ranking correlates with the (humangenerated) gold standard (see e.g., [START_REF] Joachims | Optimizing search engines using clickthrough data[END_REF][START_REF] Lapata | Automatic Evaluation of Information Ordering: Kendall's Tau[END_REF]. Formally, assuming continuous variables for simplicity, let X ⊂ R 2 and S = {x i = (y i , z i )} n i=1 . For any i < j, the pairs x i = (y i , z i ) and x j = (y j , z j ) are said be concordant if (y i > y j ) ∧ (z i > z j ) or (y i < y j ) ∧ (z i < z j ), and discordant otherwise. Let C and D be the number of concordant and discordant pairs in S. Kendall rank correlation coefficient is defined as:

τ = C -D C + D = 1 n 2 i<j sign(y i -y j ) sign(z i -z j ), (6)
which is a U -statistic of degree 2 with kernel f (x i , x j ) = sign(y i -y j ) sign(z i -z j ). 1

Area under the ROC curve (AUC). In binary classification with class imbalance, the Receiver Operating Characteristic (ROC) gives the true positive rate with respect to the false positive rate of a predictor at each possible decision threshold. The AUC is a popular summary of the ROC curve which gives a single, threshold-independent measure of the classifier goodness: it corresponds to the probability that the predictor assigns a higher score to a randomly chosen positive point than to a randomly chosen negative one. AUCs are widely used as performance metrics in machine learning [START_REF] Bradley | The use of the area under the ROC curve in the evaluation of machine learning algorithms[END_REF][START_REF] Herschtal | Optimising area under the ROC curve using gradient descent[END_REF], and have also been recently studied as fairness measures [START_REF] Kallus | The Fairness of Risk Scores Beyond Classification: Bipartite Ranking and the xAUC Metric[END_REF][START_REF] Vogel | Learning Fair Scoring Functions: Fairness Definitions, Algorithms and Generalization Bounds for Bipartite Ranking[END_REF]. Formally, let X ⊂ R × {-1, 1} and S = {x i = (s i , y i )} n i=1 where for each data point i, s i ∈ R is the score assigned to point i and y i ∈ {-1, 1} is its label. For convenience, let S + = {s i : y i = 1} and S -= {s i :

y i = -1} and let n + = |S + | and n -= |S -|. The AUC is given by AU C = 1 n + n - si∈S + sj ∈S -I[s i > s j ], (7)
where

I[σ] is an indicator variable outputting 1 if the predicate σ is true and 0 otherwise. Up to a n 2 /n + n - factor, it is easy to see that AU C is a U -statistic of degree 2 with kernel f (x i , x j ) = I[s i > s j ∧ y i > y j ] + I[s i < s j ∧ y i < y j ].
1 One can easily modify the kernel to account for ties.

Machine learning with pairwise losses. Many machine learning problems involve loss functions that operate on pairs of points [START_REF] Kar | On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions[END_REF][START_REF] Clémençon | Scalingup Empirical Risk Minimization: Optimization of Incomplete U-statistics[END_REF]. This is the case for instance in metric learning [START_REF] Bellet | Metric Learning[END_REF], bipartite ranking [START_REF] Clémençon | Ranking and empirical risk minimization of Ustatistics[END_REF] and clustering [START_REF] Clémençon | A statistical view of clustering performance through the theory of U-processes[END_REF]. Empirical risk minimization problems have therefore the following generic form:

min θ∈Θ 2 n(n-1) i<j θ (x i , x j ), (8)
where θ ∈ Θ are model parameters. The objective function in (8), as well as its gradient, are U -statistics of degree 2 with kernels θ and ∇ θ θ respectively.

Local Differential Privacy

The classic centralized model of differential privacy assumed the presence of a trusted aggregator which processes the private information of individuals and releases a perturbed version of the result. The local model instead captures the setting where individuals do not trust the aggregator and randomize their input locally before sharing it. This model has received wide industrial adoption [START_REF] Erlingsson | Rappor: Randomized aggregatable privacy-preserving ordinal response[END_REF][START_REF] Fanti | Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries[END_REF]Differential Privacy Team, Apple, 2017;[START_REF] Ding | Collecting telemetry data privately[END_REF].

Definition 2 [START_REF] Duchi | Local privacy and statistical minimax rates[END_REF]. A local randomizer R is ( , δ)-locally differentially private (LDP) if for all x, x ∈ X and all possible output O in the range of R:

P r[R(x) = O] ≤ e P r[R(x ) = O] + δ.
The special case δ = 0 is called pure -LDP.

Most work in LDP aims to compute quantities that are separable across individual inputs, such as sums and histograms (see [START_REF] Bassily | Local, private, efficient protocols for succinct histograms[END_REF][START_REF] Wang | Locally differentially private protocols for frequency estimation[END_REF][START_REF] Kulkarni | Answering range queries under local differential privacy[END_REF][START_REF] Cormode | Marginal release under local differential privacy[END_REF]Bassily et al., 2017, and references therein). In contrast, our goal is to design LDP protocols for computing Ustatistics, where each term involves a pair of inputs.

GENERIC LDP PROTOCOL FROM QUANTIZATION

Discrete inputs. We first consider the case of discrete inputs taking one of k values. The possible values of the kernel function can be written as a matrix A ∈ R k×k where A ij = f (i, j). In this case, we can set the local randomizer R to be k-ary randomized response to generate a perturbed version R(x i ) of each input x i . Let e i denote the vector of length k with a one in the i-th position and 0 elsewhere. For each perturbed input in one-hot encoding form e R(xi) we can deduce an unbiased estimate of e xi . As the discrete U -statistic is Algorithm 1: LDP algorithm based on quantization and private histograms Public Parameters: Privacy budget , quantization scheme π, number of bins k.

Input:

(x i ∈ X ) i∈[n] Output: Estimate U f,n of U f 1 for each user i ∈ [n] do 2 Form quantized input π(x i ) ∈ [k] 3 For β = k/(k + e -1), generate xi ∈ [k] s.t. P (x i = i) = 1 -β for i = π(x i ), β/k for i = π(x i ), (9)
4

Send xi to the aggregator 5 end 6 Return U f,n computed from x1 , . . . , xn and β a linear function of each of these vectors, computing it on these unbiased estimates gives an unbiased estimate U f,n which can be written as:

U f,n = 1 n 2 1≤i<j≤n f A (R(x i ), R(x j )),
and is itself a U -statistic with kernel f A given by

f A (R(x 1 ), R(x 2 )) = (1-β) -2 (e R(x1) -b) T A(e R(x2) -b),
where 1 -β is the probability of returning the true input in k-ary randomized response (see Eq. 9) and b is the vector of length k with every entry β/k. Details and analysis of this process, leveraging Hoeffding's decomposition of U -statistics [START_REF] Hoeffding | A class of statistics with asymptotically normal distribution[END_REF][START_REF] Lee | U -statistics: Theory and practice[END_REF], can be found in Section A.1 of the supplementary material. The resulting bounds on the variance of U f,n are summarized in the following theorem.

Theorem 1. If f (x, x ) ∈ [0, 1] for all x, x , then Var( U f,n ) ≤ 1 n(1 -β) 2 + (1 + β) 2 2n(n -1)(1 -β) 4 .
In order to achieve -LDP with a fixed k this becomes,

Var( U f,n ) ≈ (1 + k/ ) 2 n + (1 + k/ ) 4 2n 2 ≈ k 2 n 2 ,
Continuous inputs. For U -statistics on discrete domains, e.g. Renyi-2 entropy, the above strategy can be applied directly. Possibly more importantly however, this then leads to a natural protocol for the continuous case. In this protocol (see Algorithm 1), the local randomizer proceeds by quantizing the input into k bins (for instance using simple or randomized rounding) before applying the previous procedure.

There are two sources of error in this protocol. The first one is due to the randomization needed to satisfy LDP in the quantized domain as bounded in Theorem 1.

The second source of error is due to quantization. In order to control this error in a nontrivial way, we rely on an assumption on the kernel function (namely, that it is Lipschitz) or the data distribution (namely, that it has Lipschitz density). Under these assumptions and using an appropriate variant of the kernel function on the quantized domain, we show that we can bound the error with respect to the original domain by a term in O(1/k 2 ) (see Section A.2 of the supplementary material). This leads to the following result.

Theorem 2. For simplicity, assume bounded domain X = [0, 1] and kernel values f (x, y) ∈ [0, 1] for all x, y ∈ X . Let π correspond to simple rounding, > 0, k ≥ 1 and β = k/(k + e -1). Then Algorithm 1 satisfies -LDP. Furthermore:

• If f is L f -Lipschitz in each of its arguments, then MSE( U f,n ) is less than or equal to 1 n(1 -β) 2 + (1 + β) 2 2n(n -1)(1 -β) 4 + L 2 f 2k 2 . • If dµ/dλ is L µ -Lipschitz w.r.t. some measure λ, then MSE( U f,n ) is less than or equal to 1 n(1 -β) 2 + (1 + β) 2 2n(n -1)(1 -β) 4 + 4L 2 µ k 2 + 4L 4 µ k 4 .
Remark 2. The use of simple rounding is not optimal in many situations. In the case of sum, and possibly of the Gini coefficient, it would be more accurate if randomized rounding were used instead of simple rounding. We leave this investigation for later work.

Setting k so as to balance the quantization and estimation errors leads to the following corollary. Corollary 1. Under the conditions of Theorem 2, for ≤ 1 and large enough n,

taking k = n 1/4 √ L leads to MSE( U f,n ) = O(L/ √ n ),
where L corresponds to L f or L µ depending on the assumption. This result gives concrete error bounds for U -statistics whose kernel is Lipschitz, for arbitrary data distributions. One important example is the Gini mean difference, whose corresponding kernel f (x i , x j ) = |x i -x j | is 1-Lipschitz. On the other hand, for U -statistics with non-Lipschitz kernels, the data distribution must be sufficiently smooth (if not, it is easy to construct cases that make the algorithm fail).

LOCALLY PRIVATE AUC

In this section, we describe an algorithm for computing AUC (7), whose kernel is discontinuous and therefore non-Lipschitz. We assume X to be an ordered domain of size d, that is with each datum in [0..d -1]. Note that all data is in practice discrete when represented in finite precision, so this is general. For simplicity of presentation we will assume that (i) d = 2 α for some integer α, and (ii) that the classes of the data, the y i , are public.

Our solution for computing AUC in the local model relies on a hierarchical histogram construction that has been considered in previous works for private collection of high-dimensional data [START_REF] Chan | Privacypreserving stream aggregation with fault tolerance[END_REF], heavy hitters [START_REF] Bassily | Practical locally private heavy hitters[END_REF], and range queries [START_REF] Kulkarni | Answering range queries under local differential privacy[END_REF]. A hierarchical histogram is essentially a tree data structure on top of a histogram where each internal node is labelled with the sum of the values in the interval covered by it (see Figure 1). That allows to answer any range query about u by checking the value associated with O(log |u|) nodes in the tree. We first define an exact version of such hierarchical histograms and explain how to compute AUC from one.

Notation on trees. We represent a binary tree h of depth α with integer node labels as a total mapping from a prefix-closed set of binary strings of length at most α to the integers. We refer to the i-th node in level l of the tree by the binary representation of i padded to length l from the left with zeros. With this notation, h λ is the label of the root node, as we use λ to denote the empty string, h 0 (resp. h 1 ) is the integer label of the left (resp. right) child of the root of h, and in general h p is the label of the node at path p from the root, i.e. the label of the node reached by following left or right children from the root according to the value of p (0 indicates left and 1 indicates right). Let b i be the i-th node in the bottom level. For two binary strings p, p ∈ {0, 1} * we denote the prefix relation by Algorithm. We use hierarchical histograms to compute AUC as follows. Let S + and S -be the samples of the positive and negative classes from which we Figure 2: Our algorithm can be seen as a breath-first traversal of a tree, where at each level some nodes are selected for their subtrees to be explored further.

want to estimate AUC. Let h + and h -be hierarchical histograms for S + and S -. Note that h + λ = n + and h - λ = n -. We can now define the unnormalized AUC, denoted UAUC, over hierarchical histograms recursively by letting UAUC(h + , h -, p) be 0, if p is a leaf, and otherwise setting:

UAUC(h + , h -, p) = h + p•1 h - p•0 + i∈{0,1} UAUC(h + , h -, p•i) .
Thus we have AUC(S + , S -) = AUC(h

+ , h -, λ) = 1 n + n -UAUC(h + , h -, λ).
The above definition naturally leads to an algorithm that proceeds by traversing the trees h + , h -top-down from the root λ, accumulating the products of counts from h + , h -at nodes that correspond to entries in h + that are bigger than entries in h -. We now define a differentially private analogue. Later we will describe an efficient frequency oracle which can be used to compute an LDP estimate ĥ of a hierarchical histogram h of n values in a domain of size 2 α . This will provide the following necessary properties (i) ĥ is unbiased, (ii) Var( ĥ) ≤ v, with v defined as Cnα for some small constant C (iii) the ĥp are pairwise independent and (iv) Each level of ĥ is independent of the other levels.

Our private algorithm for computing an estimate of UAUC is then defined in terms of parameters n + and n -, v + and v -(bounding the variance of ĥ+ and ĥrespectively), and a > 1 is a small number depending on n + , n -, α and C.

For a symbol ℵ we write ℵ ± to simultaneously refer to ℵ + and ℵ -. Let h± p = max( ĥ± p , √ av ± /2), i.e. h+ p = max( ĥ+ p , √ av + /2) and hp = max( ĥp , √ av -/2), and

let τ = a √ v -v + .
Our private estimate is defined as follows. If p is a leaf then UAUC( ĥ+ , ĥ-, p) is 0, else if h+ p hp < τ then it is given by

1 2 i∈{0,1} ĥ+ p•i i∈{0,1} ĥ- p•i .
Otherwise, it is given recursively by

ĥ+ p•1 ĥ- p•0 + i∈{0,1} UAUC( ĥ+ , ĥ-, p • i) . ( 10
)
As before, this definition leads to an algorithm. Note that the only difference with its non-private analogue is that this procedure does not recurse into subtrees whose contribution to the UAUC is upper bounded sufficiently tightly. More concretely, the server starts by querying ĥ+ , ĥat the root, namely with p = λ. If p is a leaf then we return 0 as the AUC. Otherwise, the algorithm checks whether h+ p hp < τ . If so, then the algorithm concludes that there is not much to gain in exploring the subtrees rooted at p•0 and p•1, and returns

1 2 i∈0,1 ĥ+ p•i i∈0,1
ĥp•i as an estimate of 1 2 h + p h - p . This estimate might seem equivalent to 1 2 ĥ+ p ĥp , but takes the previous form for a technical reason that is made clear in the proof. In this case we call p a discarded node. On the other hand, if h+ p hp ≥ τ , the algorithm proceeds as its non-private analogue, accumulating the contribution to the UAUC from the direct subtrees of p and recursing into nodes p • 0 and p • 1. In this case we refer to p as a recursed node. Thus every node p ∈ {0, 1} ≤α will be either recursed, a leaf or there will be a discarded node p such that p p. This is depicted in Figure 2.

Analysis. Note that our algorithm has two sources of error: (i) the one incurred by discarding nodes and (ii) the error in estimating the contribution to the UAUC of the recursed nodes. The threshold τ is carefully chosen to balance these two errors.

Let R m be the set of nodes recursed on at level m. Our accuracy proof starts by bounding the expected value of |R m | (see Lemma 4 in Section B.1 of the supplementary) by a quantity B that is independent of m. We now describe a central argument to our accuracy proof, stated in the next theorem. Let E R m be the contribution to the error by nodes in R m . Then, the total contribution to the error by recursed nodes is

E R = m∈[α] E R m . A useful identity is E(E R 2 ) = m∈[α] E(E R m 2 ), as we can bound E(E R m 2
), for any m, in terms of B (see detailed proof in the supplementary).

Note that this identity follows from E(E R m E R m ) = 0, with m > m. The latter would hold if errors E R m and E R m were independent, since our frequency oracle is unbiased. However, errors at a given level are not independent of previous levels. However E(E R m E R m ) = 0 because the conditional expectation of E R m with respect to the answers of the frequency oracles up to level m is 0 i.e. E R 1 , . . . , E R m is a martingale difference sequence. The idea of conditioning on previous levels is used several times in our proofs, also to bound the error due to discarded nodes.

Next, we state our accuracy result, which is proven in detail in Section B.1 of the supplementary. Our proof tracks constants: this is important for practical purposes, and we show empirically in Section D.1 that our bound is in fact quite tight.

Theorem 3. If α ≤ √ n and the following holds:

1. E( ĥ± p -h ± p ) = 0 i.e. frequency estimates are unbiased.

E(( ĥ±

p -h ± p ) 2 ) ≤ v ± i.e. MSE of frequency estima- tor is bounded by v ± = Cn ± α.
3. For distinct p, p ∈ {0, 1} ≤α with |p| = |p |, ĥ± p and ĥ± p are independent i.e. the frequency estimates are pairwise independent.

4. For all m ≤ log(d), the lists ( ĥ± p ) p∈{0,1} ≤m and ( ĥ± p ) p∈{0,1} >m are independent of each other.

Then, MSE( UAUC) is given by

Cn -n + α 2 2n + (4a + 1) min(n -, n + ) + 21 √ 2nCα √ a -1
Instantiating ĥ. So far, Theorem 3 does not yield a complete algorithm as it does not specify an algorithm for computing estimates ĥ of a hierarchical histogram that satisfy the conditions of Theorem 3. In Section B.2 of the supplementary, we show how to instantiate such an algorithm in a communication-efficient manner by combining ideas from [START_REF] Bassily | Practical locally private heavy hitters[END_REF], in particular the use of the Hadamard transform, with an modified version of the protocol from [START_REF] Kulkarni | Answering range queries under local differential privacy[END_REF]. This leads to the following result.

GENERIC PROTOCOLS FROM 2PC

So far, we have proposed a specialized LDP protocol for AUC, and a generic LDP protocol which requires some assumption on the kernel function or the data distribution to guarantee nontrivial error bounds. We conjecture that no LDP protocol can guarantee nontrivial error for arbitrary kernels and distributions, but we leave this as an open question for future work.

In this section, we slightly relax the model of LDP by allowing pairs of users i and j to compute a randomized version f (x i , x j ) of their kernel value f (x i , x j ) with 2-party secure computation (2PC). This gives rise to a computational differential privacy (CDP) model [START_REF] Mironov | Computational Differential Privacy[END_REF]. Unsurprisingly, we show that in this model we can match the MSE of O( ln(1/δ) n 2 ) for computing regular (univariate) averages in the ( , δ)-LDP model by using advanced composition results [START_REF] Dwork | Boosting and Differential Privacy[END_REF]. However, such a protocol requires O(n 2 ) communication as all pairs of users need to compute f (x i , x j ) via 2PC, and does not satisfy pure -DP.

Proposed protocol. To address these limitations, we propose that the aggregator asks only a (random) subset of pairs of users (i, j) to submit their randomized kernel value f (x i , x j ). The idea is to trade-off between the error due to privacy (which increases as more pairs are used, due to budget splitting) and the subsampling error (for not averaging over all pairs). Given a positive integer P (which should be thought of as a small constant independent of n) and assuming n to be even for simplicity, we propose the following protocol:

1. Subsampling: The aggregator samples P independent permutations σ 1 , . . . , σ P ∈ S n of the set of users {1, . . . , n}. This defines a set of P n/2 pairs P = (σ p (2i -1, 2i)) p∈[P ],1≤i≤N/2 .

2. Perturbation: For each pair of users (i, j) ∈ P, users compute f (x i , x j ) via 2PC and sends it to the aggregator.

Aggregation:

The aggregator computes an estimate of U f as a function of { f (x i , x j )} (i,j)∈P .

Analysis. We have the following result for the Laplace mechanism applied to real-valued kernel functions (the extension to randomized response for discrete-valued kernels is straightforward). The proof relies on an exact characterization of the subsampling error by leveraging results on the variance of incomplete U -statistics [START_REF] Blom | Some properties of incomplete Ustatistics[END_REF], see Section C.1 of the supplementary for details.

Theorem 5 (2PC subsampling protocol with Laplace mechanism). Let > 0, P ≥ 1 and assume that the kernel f has values in [0, 1]. Consider our subsampling protocol above with f (x i , x j ) = f (x i , x j ) + η ij where η ij ∼ Lap(P/ ), and the estimate computed as U f,n = 2 P n (i,j)∈P f (x i , x j ). Then the protocol satisfies -CDP, has a total communication cost of O(P n) and

MSE( U f,n ) = 2 P n 2(P -1) 1 - 1 n -1 ζ 1 + 1 + P -1 n -1 ζ 2 + 2P n 2 ,
where ζ 1 and ζ 2 are defined as in (3).

The MSE in Theorem 5 is of O( 1 P n + P n 2 ). Remarkably, this shows that the O(1/n) variance of the estimate that uses all pairs is preserved when subsampling only O(n) pairs. This is made possible by the strong dependence structure in the O(n 2 ) terms of the original U -statistic.

As expected, P rules a trade-off between the errors due to subsampling and to privacy: the larger P , the smaller the former but the larger the latter (as each user must split its budget across P pairs). The optimal value of P depends on the kernel function and the data distribution (through ζ 1 and ζ 2 ) on the one hand, and the privacy budget on the other hand. This trade-off, along with the optimality of the proposed subsampling schemes, are discussed in more details Section C.1 of the supplementary material. In practice and as illustrated in our experiments, P can be set to a small constant.

Implementing 2PC. Securely computing the randomized kernel value f (x i , x j ) can be done efficiently for many kernel functions and local randomizers of interest, as the number of parties involved is limited to 2. We assume semi-honest parties (see [START_REF] Goldreich | The Foundations of Cryptography -Volume 2, Basic Applications[END_REF], for a definition of this threat model). A suitable 2PC technique in this application are garbled circuits [START_REF] Yao | How to generate and exchange secrets[END_REF][START_REF] Lindell | A proof of security of yao's protocol for two-party computation[END_REF][START_REF] Evans | A pragmatic introduction to secure multi-party computation[END_REF], which are well-suited to compute Boolean comparisons as required in several of the kernels mentioned in Section 2.1.2. The circuits for computing the kernels can then be extended with output perturbation following ideas from [START_REF] Dwork | Our data, ourselves: Privacy via distributed noise generation[END_REF] and [START_REF] Champion | Securely sampling biased coins with applications to differential privacy[END_REF]. We refer to Section C.2 of the supplement for details on design and complexity.

Remark 3 (Beyond 2PC). One could further relax the model to allow multi-party secure computation with more than two parties, e.g. by extending the garbled circuit computing the kernel with secure aggregation over the P n pairs before performing output perturbation. This would recover the utility of centralized DP at the cost of much more computation and quadratic communication, which is not practical, as well as robustness. More interesting trade-offs may be achieved by securely aggregating small subsets of pairs. We leave the careful analysis of such extensions to future work.

EXPERIMENTS

AUC. We use the Diabetes dataset [START_REF] Strack | Diabetes data[END_REF] for the binary classification task of determining whether a patient will be readmitted in the next 30 days after being discharged. We train a logistic regression model s which is used to score data points in [0, 1], and apply our protocol to privately compute AUC on the test set. Patients readmitted before 30 days form the positive class. Class sizes are shown in Figure 3. Class information is not considered sensitive, as opposed to the score s(x) on private user data s(x), which includes detailed medical information. Figure 3 shows the standard error achieved by our protocol for different values of the domain size d. For each value of d we run our protocol with inputs s(fp(s(x i ), d)), where fp The plot shows that the protocol is quite robust to the choice of d, and that increasing beyond 2 does not improve results significantly. Recall that the error of our AUC protocol depends on the size of the smallest class, which is quite small here (only 693 examples).

Kendall's tau. We use the Tripadvisor dataset [START_REF] Wang | Trip advisor data[END_REF]. The dataset consists of discrete user ratings (from scale -1 to 5) for hotels in San Francisco over many service quality metrics such as room service, location, room cleanliness, front desk service etc. After discarding the records with missing values, we have over 246K records. Let x i = (y i , z i ) be ratings given by user i to the room (y i ) and the cleanliness (z i ). The goal is to privately estimate the Kendall's tau coefficient (KTC) between these two variables, whose true value is 0.58. We compare the privacy-utility trade-off of our randomized response protocol (Algorithm 1 without quantization, since inputs can take only 6 × 6 = 36 values), our 2PC protocol based on subsampling, and the 2PC protocol that computes all pairs and relies on advanced composition (for which we set δ = 1e -8 ). The 2PC primitive to compute f (x i , x j ) is simulated. The results shown in Figure 4 show that the 2PC protocol with all pairs performs worst due to composition. The randomized response protocol performs slightly better, thanks to the small domain size. Finally, our 2PC protocol with subsampling achieves the lowest error by roughly an order of magnitude in high privacy regimes ( ≤ 2) while keeping the communication cost linear in n. As predicted by our analysis, P = 1 is best in high privacy regimes, where the error due to privacy dominates the subsampling error. We also see that P > 1 can be used to reduce the overall error in low privacy regimes (for = 10 one can use an even larger P to match the error of the randomized response protocol).

CONCLUDING REMARKS

In this paper, we tackled the problem of computing U -statistics from private user data, covering many statistical quantities of broad interest which were not addressed by previous private protocols.

Relative merits of our protocols. Our three protocols are largely complementary, insofar as each of them is well-suited to specific situations. Our first protocol (quantization followed by randomized response) can gracefully handle cases where the kernel is Lipschitz or the data is discrete in a small domain. It may also work well for non-Lipschitz kernels when quantizing data into few bins does not lose too much information (e.g., when the data distribution is smooth enough). As the latter hypothesis is difficult to assess in advance, we argue that there can exist specialized protocols that work well for non-Lipschitz kernels on continuous data or large discrete domains. Our second protocol illustrates this for the case of AUC: we leverage a hierarchical histogram structure to scale much better with the number of bins than the first protocol (see Section D for experiments comparing these two protocols). Finally, if one is willing to slightly relax the LDP model to allow pairwise communication among users, and if the kernel can be computed efficiently via 2PC, our third protocol is expected to perform best in terms of accuracy.

Extension to higher degrees. While we focused on pairwise U -statistics, our ideas can be extended to higher degrees. A prominent example is the Volume Under the ROC Surface, the generalization of the AUC to multi-partite ranking [START_REF] Clémençon | Ranking data with ordinal labels: Optimality and pairwise aggregation[END_REF].

Future work. A promising direction for future work is to develop private multi-party algorithms for learning with pairwise losses [START_REF] Kar | On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions[END_REF][START_REF] Clémençon | Scalingup Empirical Risk Minimization: Optimization of Incomplete U-statistics[END_REF] by combining private stochastic gradient descent for standard empirical risk minimization [START_REF] Bassily | Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds[END_REF][START_REF] Shokri | Privacypreserving deep learning[END_REF] and our protocols to compute the gradient estimates.

Figure 1 :

 1 Figure 1: Hierarchical histogram h for multiset {0, 1, 2, 2, 3} over the domain {0, 1, 2, 3}.

  p p, and their concatenation as p • p . Definition 3. Let S = {s 1 , . . . , s n } be a multiset, with s i ∈ [0..d -1]. A hierarchical histogram of S is a total mapping h : {0, 1} ≤log(d) → Z defined as h(b) = |{s ∈ S | ∃b ∈ {0, 1} * : b • b = b s }|. For simplicity, we denote h(b) by h b .

Theorem 4 .

 4 There is a one-round non-interactive protocol for computing AUC in the local model with MSE bounded by O(α 2 log(1/δ)/n 2 ) under ( , δ)-LDP and O(α 3 /n 2 ) under -LDP. Every user submits one bit, and the server does O(nlog(d)) computation and requires O(log(d)) additional reconstruction space.

Figure 3 :Figure 4 :

 34 Figure 3: Mean and std. dev. (over 20 runs) of the absolute error of our AUC protocol on the scores of a logistic regression model trained on a Diabetes dataset.

Acknowledgments J. B. was supported by The Alan Turing Institute underthe EPSRC grant EP/N510129/1, and the UK Government's Defence & Security Programme in support of the Alan Turing Institute. A. B. was supported by grants ANR-16-CE23-0016-01 and ANR-18-CE23-0018-03, by the European Union's Horizon 2020 Research and Innovation Program under Grant Agreement No. 825081 COMPRISE and by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020. A. B. thanks Jan Ramon for useful discussions. Work partly done when A. G. was at The Alan Turing Institute and Warwick University, and supported by The Alan Turing Institute under the EPSRC grant EP/N510129/1, and the UK Government's Defence & Security Programme in support of the Alan Turing Institute. T. K. thanks Graham Cormode for arranging a trip to Inria Lille. His visit was supported by Marie Curie Grant 618202.