On Differentially Private U Statistics
Authors: Kamalika Chaudhuri
Po-Ling Loh
Shourya Pandey
Purnamrita Sarkar
Venue: NeurIPS 2024 poster (2024)
Keywords: Differential Privacy
Statistics
Mean Estimation
Primary area: privacy
TL;DR: We devise efficient algorithms for differentially private U-statistics in the Central DP model, achieving nearly optimal error rates in various settings. Previously, this was studied in the local DP model and with U-statistics of degree 2.

Abstract: We consider the problem of privately estimating a parameter $\mathbb{E}[h(X_1,\dots,X_k)]$, where $X_1$, $X_2$, $\dots$, $X_k$ are i.i.d. data from some distribution and $h$ is a permutation-invariant function. Without privacy constraints, the standard estimators for this task are U-statistics, which commonly arise in a wide range of problems, including nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and are the unique minimum variance unbiased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied in a black-box manner to obtain confidence intervals, we show that they can lead to suboptimal private error, e.g., constant-factor inflation in the leading term, or even $\Theta(1/n)$ rather than $O(1/n^2)$ in degenerate settings. To remedy this, we propose a new thresholding-based approach that reweights different subsets of the data using _local Hájek projections_. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.

On Differentially Private U Statistics
Kamalika Chaudhuri
Po-Ling Loh University of Cambridge pl1288cam ac.uk uk
University of California San Diego
kamal i kakukkddddde.m edu
Shourya Pandey
Purnamrita Sarkar University of Texas Austin purna. sarkarQaustin. utexas, edu
University of Texas at Austin shouryap@utexas edu
Abstract
We consider the problem of privately estimating a parameter ( Xx),, where X1, X....., Xg are i..d. data from some distribution and h is permutation- invariant function. Without privacy constraints, the standard estimators for this task are U-statistics, which commonly arise in a wide range of problems, includ- ing nonparametric signed rank tests, symmetry testing, uniformity testing, and subgraph counts in random networks, and are the unique minimum variance unbi- ased estimators under mild conditions. Despite the recent outpouring of interest in private mean estimation, privatizing U-statistics has received little attention. While existing private mean estimation algorithms can be applied a black- box manner to obtain confidence intervals, show that they lead to suboptimal private error, e.g., constant-factor inflation the leading term, or even @ rather than (l/nn²) ) in degenerate settings. To remedy this, propose new thresholding- based approach that reweights different subsets of the data using local Hájek projections. This leads nearly optimal private error for non-degenerate U-statistics and strong indication of near-optimality for degenerate U-statistics.
Introduction
fundamental task statistical inference is estimate a parameter of the form E[h X3)], where h is possibly rector-valued function and {x;) are i.i.d. draws from an unknown distribu- tion. U-statistics are a eellbessablished class of estimators for such parameters and can be expressed as averages of functions of the form h(X,,..., Xa). U-statistics arise many areas of statistics and machine learning, encompassing diverse estimators such as the sample mean and variance, hypothesis tests such as the Hhan-WWittee uniformity testing [26] 21), goodness-or fit tests [58), counts combinatorial objects such as the number of subgraphs in random graph [30], ranking and clustering [1 18), and subsampling [52)
Wilcoxon signed rank, and Kendall's tau tests, symmetry and
U-statistics are natural generalization of the sample mean. However, little work has been done on U-statistics under differential privacy, in contrast to the sizable body of existing work on private mean I0,
estimation 42 39 14 40
41 22 33 [5]. Ghazi et [2 and Bell al. [ consider U- statistics in the setting of local differential privacy 45], while we are interested in privacy guarantees under the central model. Moreover, existing work on private U-statistics focuses on discrete data, and relies simple privacy mechanisms (such as the Laplace mechanism 25 which are usually optimal in these settings.
Many U-statistics converge to a limiting Gaussian distribution with variance O(k²/n) when suitably scaled. This is commonly used in hypothesis testing [35 5 37.. However, there are also examples of non-degenerate U-statistics, which often arise in a variety of hypothesis tests [26] 58 21, where the statistic is degenerate at the null hypothesis (in which case the U-statistic converges to a sum of centered chi-squared distributions [II). Another interesting U-statistic arises in subgraph counts in random geometric graphs [30]. When the probability of an edge being present tends to zero with n, creating a private estimator by simply adding Laplace noise with suitable scale may not be effective.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Our contributions
1. We present new algorithm for private estimation that achieves nearly optimal private and non-private errors for non-degenerate U-statistics with sub-Gaussian kernels.
2. We provide lower bound for privately estimating non-degenerate sub-Gaussiaa kernels, which nearly matches the upper bound of our algorithm. We also derive a lower bound for degenerate kernels and provide evidence that the private error achieved by our algorithm in the degenerate case nearly optimal. A summary the utility guarantees of our algorithm and adaptations of existing private mean estimation methods is presented in Table I
3. The computational complexity of our first algorithm scales as ((())) ). We generalize this algorithm and develop an estimator based on subsampled data, providing theoretical guarantees for a more efficient version with On²²) computational complexity.
The paper is organized as follows. Section reviews the background U-statistics and key concepts in differential privacy. Section
3 introduces an initial set of estimators based on the CoinPress algorithm for private mean estimation [10]. Section 4 presents our main algorithm, which leverages what we term local Hájek projections. Section [5 discusses applications of our algorithm to private uniformity testing and density estimation sparse geometric graphs. Section Sonoonooonne concludes the paper.
2 Background and Problem Setup
Let n and be positive integers with S n. Let D be an unknown probability distribution over a set X' and let h 2² + IR be a known function symmetric in its arguments Let H. be the distribution (X1,, X2.... Xx), where X1, ........ . X DD are i.i.d. random variables. We are interested in providing a e-differentially private confidence interval for the estimable parameter [32 = [E[((X, N Xx)], which is the mean of the distribution H. given access to n i.i.d. samples from D: we use X1, X2. Xn to denote these samples. The kernel h, the degree k, and the estimable parameter 9 are allowed to depend on nı; we omit the subscript n for the sake of brevity.
We consider bounded kernels / and unbounded kernels where the distribution H. is sub-Gaussian. We write Y uub-Gaussian(7 if [E|expA((* (X(( - EY)) S exp(T>²/2) for all X E IR. The quantity is called variance proxy for the distribution H. and satisfies the inequality t 2 o² [59]. Throughout
the paper. we assume that the privacy parameter e = O1)). We also use the notation Ö(-) in error terms, which hides poly-logarithmic factors in n/a.
2.1 U-Statistics
Let [n]] denote samples by X1, X2, 2....,. X,, For any S E In,k, k. let Xs be the (unordered) k-tuple {X; 1::00 E S). The U-statistic associated with the data and the function h is
and let In be the set of all k-element subsets of [n]. Denote the n i.i.d.
Σ Un (11....A)EEZ.,
M(X,, .......... . X
The function h is the kernel of U, and & is the degree of Un. While U-statistics can be vector-valued, we consider scalar U-statistics in this paper. The variance of Un, can be expressed in terms of the conditional variances of (x,,, Xz,..., Xn). . For E [k], we define the conditional variance
Co = Var (E [ XI Xc)).
Equivalently, Çe cov (h(Xs,) ), h(Xs))) where S1, S2 E In, and |S n Szl The number of such pairs of sets S1 and S2 is equal to (i) (#) (K=²). which implies
k c
k
Var(Un)
Se-
(3)
k
'That is. h(21, ...... .., 2x) = (((a(1)) To(2). ... (o(k)) for any permutation a. We do not assume that the distribution H itself is symmetric about its mean.

---

Since U = 8, Un is an unbiased estimate of 8. Moreover, the variance of Un is a lower bound on
the variance of any unbiased estimator of B. (cf Lee [45] Chapter Theorem 3J). We also have the following inequality from Serfling [54] (see Appendix A.2 for proof):
Sk
(4)
k
Infinite-order U-Statisties: Classical U-statistics typically have small, fixed k. However, important
estimators that appear in the contexts of subsampling (2 and Breiman's 's random forest algorithm [56
50 have k growing with n. These types of U-statistics are sometimes referred to as infinit--rdde U-
statistics [7 4 U-statistics also frequently appear in the analysis of random geometric graphs [30]
The difference between this setting and the examples above is that the conditional variances {
vanish with n in the sparse setting. (See Section
Degenerate U-statistics: A U-statistic is degenerate of order é S k 1 i 0 for all E [$] and Ce+1 > 0 (if Ç& O, the distribution is almost surely constant). Degenerate U-statistics arise in hypothesis tests such Cramer- Von Mises and Pearson tests of goodness of fit 313 and tests for unformity (21]. They also appear in tests for model misspecification in econometrics 46 47).
For more examples degenerate U-statistics, see 20
2.2 Differential privacy
The main idea of differential privacy (25] is that the participation or non-participation of a single person should not affect the outcome significantly. A (randomized) algorithm M, that takes input a dataset D E X and outputs an element of its range space S, satisfies e-differential privacy if for any pair of adjacent datasets D and D' and any measurable subset S C S of the range space S. (D) E S) S e Pr(M(D)) E S). A dataset is D = (X1,X,, : from some domain X. for some n which is public. Two datasets D and D' are adjacent if they differ in exactly one index. An important property of differentially private algorithms is composition. We defer composition theorems for differentially private algorithms Appendix[AA.
Basic DP algorithms. One way to ensure an algorithm satisfies differential privacy is through the Laplace Mechanism 255
The global sensitivity of function f X -
GS(f)=
max |DAD
(5)
where DAD' == Hi: D. * DJH A fundamental result in differential privacy is that we can achieve privacy for f by adding noise calibrated to its global sensitivity.
Lemma (Laplace mechanism (25)) Let [ X S be a function and let > 0 be the privacy parameter. Then the algorithm A(D) f(D) + Lap (GS() is c-differentially private.
The global sensitivity of function is the worst-case change in the function value and may be high on atypical datasets. To account for the small sensitivity on "typical" datasets, the notion of local sensitivity is useful. The local sensitivity of a function f : X + S at D is defined as
L) = max |DAD'I= [ - f(D').
(6)
Unfortunately, adding noise proportional to the local sensitivity does not ensure differential privacy, because variation in the magnitude of noise itself may leak information. Instead, [49 proposed the notion of a smooth upper bound on LS(f. D). A function SS(f..) is said to be an e-smooth upper bound on the local sensitivity of ff if (i) SS(F, D) > LS(f, D) for all D, and (ii) SS D) < e' eSS((, D') for all |DD'I = 1. Intuitively, (i) ensures that enough noise is added, and (ii) ensures that the noise itself does not leak information about the data.
Lemma 2. (Smoothed Sensitivity mechanism (49)) Let f: f:X"" X + S be a function, > 0, and SS(f, -) be an e-smooth upper bound on LS(J, }. Then, the algorithm A(D) [(D) SS(F, D)fe. Z, where Z has density h(2) 1t5t is e/ e/10-iffereentillly private.
"The Laplace Distribution with parameter b > 0, denoted Lap(t), has density {(z) exp (-121/6).
3

---

Lower Bounds and Application of Off-the-shelf Tools
Algorithm
Sub-Gaussian, non-degenerate
Bounded, degenerate
Private error
Is non non-onpee privale emror O(Var(U..))²
Private error
Is non-private error O(Var(U,,]]
Naive (Proposition A.1
Ô
No
nc B V
TC
All-tuples (Proposition
Yes
Ô
25
No
Main algorithu
Ry/T
Yes
A./22
Yes
Corollary
Corollary
2
Lower bound for private algorithms
Q Ay/E
log
52 k
Theorem
Theorem
Table 1:
We compare our application of off-the-shelf tools to Algorithm We only provide the for all
leading terms in the private error. The non-private lower bound on E(A unbiased is Var(Un), which our private algorithms nearly match.
We start with simple, non-private estimator involving an average of independent quantities. Let m [n/k], f and define S {6 1)k + ( 1)1: 2....,jkk jkk for all j [m:] Define the naive
estimator 0 maive m (x )/m. Directly applying existing private mean estimation algorithms ΣØ= setting yields error bound of
40 39 10
(V (VVar( VVr((naive)) + kVT/(ne)) = =Ō (VkCa/n kVT/((e))
(7)
since Var (faiiie) = RCCK /n. Note that this variance is larger than the dominant term k//1 of Vur) (see Lemma A.1 and Eq indeed, Onsive is suboptimal estimator of 0.
In Algorithms A.2 and we present general extension of the CoinPress algorithm (10) which is then used to obtain private estimate of 0 with the non-private error matching vVaa(Un.). For completeness, we present the algorithms and their proofs in Appendix A.3
Definition (All-uples family). Let M -() and let Sall = (S S2, ....., Sm} In. & be the of all k-element subsets of [n]]. Call Sau the "allltuples" family.
| Then Wrapper [ with f = all, failure probability a, and A = U-StatMean (Algorithm A.2) returns an estimate Out of the mean such that, with probability at least Ot
Proposition 1. Suppose 0 E [-R, R). Let Sall be the all-tuples family in Definition
(k3/2 (
0aul - 01 00 o0 (Var(Un.)) +
(8)
nae
as long as na δ log SKr) R ("x)
Moreover, the algorithm e-differentially private and runs in time
ò (log(I/a) (k + log Vkr
Remark 1. While Lemmal recovers the correct first term of the deviation, the private error term Ie factor worse. Moreover, we need k.2 k2/n o(1) for the private error to be asymptotically smaller than the non-private error. Note, however, that existing concentration [35 5/ convergence probability results (58] 48) only require
o(n) (see Lemmas A. and in the Appendix).
Remark 2 (Degenerate and sparse settings). While Lemma 7 improves over the naive estimator, the private error can overwhelm the non-private error for degenerate and sparse U-statistics (see Section 5y. We show that for uniformity testing, using this estimator can lead to suboptimal sample complexity if the distribution is already close to uniform.
Proposition immpoves over the naive estimator at the cost of computational complexity. We can trade off the computational and statistical efficiencies using a different family S parameterized by the size M of S. In Appendix 3 we show a result similar to for the subsampled family.
OŌ()) hides logarithmic factors in the problem parameters n, Ck. where is the error probability.

---

Definition 2 (Subsampled Family), Draw M i..dd samples Si...., Sa from the uniform distribution over the elements of kn and let S {S)..... Sm Call Sau the "subsampled" family.
The next result shows a nearly optimal dependence on n and e in the bounds for naive and Ball. In particular, the dependence of the modified Coinpress algorithm (Lemma) D on k is suboptimal.
Theorem 1 (Lower bound for non-degenerate kernels). Let and k be positive integers with k < n/2 and let = QQk/n)) - Let F be the sel of all sub- Gaussian distributions over R with variance proxy 1, and let ji be the oulput of any e-disferentially private algorithm applied to i.i.d. observations from
D. Then, S. R. 1e/j(( 1, ,,,) B[h((1, xx]]] = 9
ne Vlog
12 K
Among unbiased estimators, Un is the best non non- private estimator 33
45 The most widely used
non-pen non-private estimators are U- and V-statistics, which share similar asymptotic properties [58]. The above lower bound also has a log factor arising from an optimal choice of the sub-Gaussian proxy for Bernoulli random variables Proofs are deferred to Appendix A.4
3.1 Boosting the error probability via median-of-means
we use Algorithm A.2 as stated with failure probability a, then the error in the algorithm has O(1/Va) factor, which is undesirable. Instead, we the Algorithm with a constant failure probability (say, 0.25) and then boost this failure probability to a via median-of-meen procedure. We incorporate the mediann-ff-mett in all of our theoretical results.
Wrapper (MedianOlMeans(nn k, Algorithm A, Parameters A, Failure probability a, Family type f {all, ss))). Divide [n] into q 8 log(1 /a)) independent chunks I,, E [9] of roughly the same size. For each E [g), run Algorithm A with subset family S, := S)(()), Dataset (h(Xs) and other parameters A for A to output 0,, E [g]. Return 0 = median (ondian((1,..... (01,...,oy).
In the above wrapper, S₁ (D:) simply creates the appropriate family of subsets for the dataset D;- For example, if D; = i.... ). all, then San (D)) is (S{X:)) If = 88, then (D,) is (h(X))}ses., where S; is the set of M subsampled subsets of D,. Here, na := (n)( Wrapper can be used to boost the failure probability from constant to a by splitting the data into O (a)) chunks, applying the algorithm
each of the chunks, and taking the median output. The expense this procedure is the reduction in the effective sample size to n. = (n// log(1/))). Details and proofs the median-of-nn of-maasss means procedure can be found in Section A.3.2
4 Main Results
we showed that aff-the-shelf private mean estimation tools applied to U-statistics either achieve sub-optimal non-privee non-private error (see Remark (I or sub-optimal private error. If the U-statistic is degenerate of order 1, the non-private and private errors (assuming = (()) are @(1/n). We now present an algorithm that achieves nearly optimal private error for nub-Gaussian non-degenerate kernels. Our algorithm can be viewed as generalization of the algorithm proposed in Ullman and Sealfon [57] for privately estimating the edge density of an Erdös-Rényi graph. We provide strong evidence that, for bounded degenerate kernels, we achieve nearly optimal non- non-private error. All proofs for this section can be found in Section A.5
In Section 3.
4.1 Key intuition
Our key insight is to leverage the Hájek projection
58 45), which gives the best representation of a f(X)):
U-statistic as linear function of the form Σ
S
44)
BXT - (n - 1),
(8) k
B[h(Ks) - 1)0.
Equality (i) gives the form of the Hájek projection for a general statistic T,, whereas (ii) gives the form when T, is U-statistic. Let Th = {S E Ina : E S}. In practice, one uses the estimates
[ == 1
Σ
h(Xs),
(9)
(m=l)
SEI mi
5

---

which we call local Hajek projections. In some sense, this is the U-statistic when viewed locally at X₁. When the dataset is clear from context, we write hI.,, (i), simply h(i), for ([h(Xs))X,
4.2 Proposed algorithm
Consider a family of subsets S S In.k size M. Let S; = (S E S::EE S} and M, = |St]. and suppose M, * 0 for all i E [n]. Assume also that S satisfies the inequalities
Ms/M S 3k/n and Ms/M; S 3k/n
(10)
for any distinct indices i and j in [n]] (one such family is S = In,k.
k. for which M:/M = k/n and Maj/ (k- 1) 1) S k/n, but there other such families). Define
1 Σ 1(xs), and his()) A.( M SES
Σ M(xs), SES:
[m].
(11)
M
Un in Eq (1) and ([)(Xs))X;) in equation ( are the same as the quantities A, (In,k) and fo.,.. (i)-
standard procedure private estimation algorithms is to clip the data to an appropriate interval [TO 41] in such way that the sensitivity of the overall estimate can be bounded. Similarly, use the concentration of the local Hájek projections to define an interval such that each can be classified as
"good" or "bad" based on the distance between lis (t) and the interval. The final estimator is devised so the contribution of the bad indices to the estimator is low and the estimator has low sensitivity.
Let & and be parameters to chosen later; they will be chosen in such way that with high probability, (i) (i) - 0) S & for all i, and (ii) each h (X5) is at most C' away from Define
Ls == arg min (K [hs(() - An) > & + 6kCL/m) < t
(12)
In other words, Ls is the smallest positive integer i such that most indices [m] satisfy
(is(t) An() { + G&Ct (such an integer always exists because t n works). Define
Good(S) (S) ; : his(i) An(S) s 6kCLs/n).
Bad(S) == [m] \ Good.
(13)
For each index i [n]. define the weight of i with respect to S as
(ts max (o, 6Ck dist (hs(i)= An, - 6kCLs/n,
GRCLss/l)): (
(14)
Here, e the privacy parameter and dist(x; I) the distance between x and the interval
Based on whether a datapoint is good or bad, we will define a weighting scheme that reweights the 1(Xss) in equation ( For each S E S, let
wts(S) == min wts (i), and gs(Xs) = h(Xs) + A. (1 wis(S)).
In particular, if (S) = 1, then gs(Xs) = h(Xs); and if wts(S) = 0, then gs (Xs) = An(S). Finally, define the quantities
A.) = M
Σ (xs),,
(1()) = M
Σ gs (Xs) Vi E [n].
(15)
SES
SES.
To simplify notation, we will drop the argument S from L, An, Ån, h, g. Good, and Bad.
Idea behind the algorithm: If all h (i)'s are within & of the empirical mean An, then Bad ø and A, = An- Otherwise, for any set S containing a bad index. we replace h(Xss )) by weighted combination of sx(xs) and A.. This averaging-out of the bad indices allows bound on the local sensitivity Å,. We then provide a smooth upper bound on the local sensitivity characterized by the quantity L, which can be viewed
indicator of how well-coneentrated the data is. The choice of { will be such that L with high probability and that the smooth sensitivity of Ån, at X is small.
This ensures that smaller amount of noise is added to A,, to preserve privacy.

---

Algorithm P
1: M + S
2: S,
S}
3: M; + [S
4: if there exist indices + j such that M; or M./M>> 3k/n My/M, 3k/n, then
5: return
6: end if
7: An f Eses h(Xs)/M
8: for 1, .,,,, do
9: h(t) Eses, h(Xs)/M,
10: end for
11: Let I be the smallest positive integer such that {:: [((() An > + GKCL }
12: Good(S) < : ((i) An S S B&CL |
Bad(S)) x [n] \ (ood(S)
13: for = 1,,, -1,2...., .,, do
wi(i) max (0,1 BCk/n dist (h(() An, 1 G&CL
6RCL
m
n
15: end for
for SESS do
17: g(Xs) + h(Xs) minies wt(i) + An minjes wt(i))
18: end for
19: An Esesg(Xs))
20: max)-es at (#+ (((++0(24t)) (1+e Pooc (iin
(++
21: Draw Z from distribution with density h(z) 1/(1+1211
22: return A. S(8)/e.2 .
Theorem 2. Algorithm is 10e 10e-differentially private for any &. Moreover, suppose h is bounded with additive range C and with probability at least 0.99, we have max, (is(i) - Anl S ç. Run Wrapper wiih f all, and A = PrivateMeenLocalHaieee (Algorithm 7p. With probability at least
1 - a. the output 0 satisfies 10 01 = O VVar(Un.) k.E
k3
Connections to Ullman and Sealfon 57 Ullman and Sealfon [57 estimate the edge density of an Erdōs Renyi graph using strong concentration properties of its degrees. This idea can be loosely generalized broader setting of U-statistics: consider a hypergraph with nodes and (*) edges, where the jth node corresponds to index i. An edge corresponds to k-tuple data points and the edge weight is given by h(Xs). The natural counterpart of degree in graph becomes local Hájek projection, defined as in equation (9). In degenerate cases and cases where k2 < kÇa. the local Hájek projections are tightly concentrated around the mean 0. We exploit this fact and reweight the edges (k-tuples) so that the local sensitivity of the reweighted U-statistic is small.
In,k.
Application to non-degenerate and degenerate kernels
Algorithm I can be extended from bounded kernels to sub-Gaussian(7) kernels. First, split the samples into two roughly equal halves. The first half of the samples will be used to obtain a coarse estimate of the mean 0. For this, we can use any existing private mean estimation algorithm to obtain an E/ /diiiffeerentially private estimate &coasse such that with probability at least kvT/(nee). By union bound, with probability at least a. [h(Xs) 0 within 4 / log ((0) (a) for all S In. and therefore also within o /kr log(n/a) of the coarse estimate 0cunee for some universal constant as long as = Ō(Vk/n).
Ö(vkkC//
Define the projected function X2, Xx) to be the value h(X,, X2...., Xx) projected to the interval [evame - cv/ir AiT log(n/a), Ocurse + ev Kt log(n/a)). The final estimate of the mean 0 is obtained by applying Algorithm to the other half of the samples, the function h, and the
More precisely, suppose sup, h(x) inf, h(x) C.

---

privacy parameter e/2. The following lemma shows that / log((n/a) is a valid choice of the concentration parameter & for sub- aub-Gaussian, non-degenerate kernels.
Lemma 3. If is sub-Gaussian?? the local Hájek projections (ii are also sub (abb-Gasssian()) In particular, with probability at least 1 ot, we have maxigign (i(i)) 01 s 22 log(2n/a)
Combining these parameters with Theorem 2 gives us the following result:
Corollary 1 (Non-degenerate sub-Gaussian kernels). Suppose is sub- Gaa-saaasss)) and the privacy parameter 52(kk///n)) Split the samples into two halves and compute a private estimate of the mean by applying the naive estimator the first half of the sumples with privacy parameter c/2 to ob- tain Ocnorse. Let h be the projection of of the function h onto the interval Ocvarse + O kT log(2n (2n/ a)).. Run Wrapper on the remaining half of the samples with f = all, failure probability x algorithm A = PrivateMeanl ocalHaekk (Algorithm [. C = v 2kr log(m/2ox). & = =v
/2T 2r log(n /2.), func- tion h and privacy parameter e e/20. Then, the output is e-differentially private. Moreover with probability at least
+ + 0 - 0 0 (VVa((Un))))
LVT nhE
k
33.5
+
nge²2
From our lower bound on non-degenerate kernels in Theorem 1 we see that the above corollary is optimal in terms of k n,, e (up to log factors). In contrast, Lemma is suboptimal in k.
Many degenerate U-statistics (e.g., all the degenerate ones in Section 5 have bounded kernlss. For these, we see that the local Hájek projections concentrate strongly around the U-statistic.
Lemma 4. Suppose H is bounded, with additive range C. Let i [n] be an arbitrary index and S; E In, be a set containing i, and suppose I; E IR is some element in the support of D. With probability at least &
n. conditioned on X, = Fi, we have
k B(N(Xs) = x. (IM x;]] 20,1
2n
8Ck
12n
log
log
(16)
n
B
3n
B
where [(((Xs)| =x: Eses, h(Xy) and of = Var (h(X) (x(ss)) ) = x.).
For bounded kernels with additive range C, S C/2 Popoviciu's inequality (53). Moreover, for degenerate kernels, Ç1 = 0. That is, the conditional expectation E [h(Xx,, [X, [
= 24] is equal to 0 for all F,, because the variance of this conditional expectation is Ç1. Based on this,
show that the choice of & Ô (CK2/2 /22 satisfies the requirement that the local Hájek projections are within of with probability at least a.
Corollary 2 (Degenerate bounded kernels), Suppose h is bounded with additive range and the kernel is degenerate Çi O. Let Q(k212 (n) be the privacy parameter. Run Wrapper 7 with = all, failure probability a, and algorithm A = Detetteeeenn..aaHiiiii (Algorithm with
& = O k/n log(n//)) to output Ó. With probability 1 at we have
0 1-00 0 =0 ==(Vaar(Um))) +
b
C
C+ n
k2
ny C
n1.35
Obtaining a result for sub-Gaussiaa degenerate kernels poses difficulties on bounding the concentra- tion parameter &. However, for bounded kernels, error than the application of off-the-shelf methods (Lemma []. In the next subsection, we provide a lower bound for degenerate bounded kernels, which, together with Corollary 2 gives strong indication that our algorithm achieves optimal private emror for private degenerate kernels.
that the above result obtains better private
4.4 Lower bound
To obtain a lower bound of the private error, construct dataset and kernel function such that the local Hájek projections are 1/vn concentrated around the corresponding U-statistic. This is one way of characterizing degenerate U-statistic. The proof of the following theorem is in Appendix A.4

---

Theorem 3. For any n,K E N with &
and e-differentially private
algorithm A x - R. there exists a function x + 10,1) and dataset D such that
[h(1) Un S /ki /k/n (where h(]i and Un are computed on for every i E [n]] and BJA(D) 10/2 n
Ω
where the expectation is taken over the randomness of A.
Remark 3. The above lower bound is in some sense informal because we created deterministic dataset and h that mimics the property of degenerate U statistic; the local Hájek projections concentrate around Un at rate / /k/n. However, gives us a strong reason to believe that the private error cannot be smaller than O(k3/2 / //3/2e) for degenerate statistics of order Note that for bounded kernels, Corollary does achieve this bound, opposed to Lemma]
4.5 Subsampling estimator
We now focus on subsampled U-statistics. Previous work has shown how to use random subsampling
to obtain computationally efficient approximations of U-statistics [38 52 [7]. where the sum is replaced with an average of samples (drawn with or without replacement) from In,k.
Recall Definition 2 Let == [S Sas} denote the subsampled set of subsets, let S; {S E
S E S), and let M, [S.). The proof of Theorem 2 with S In,k (ef. Appendix A.5
the property of In. that M./M- = k/n and Ma/MM M, = k 1)/ 1), so the inequalities (TO) certainly hold. Indeed, we can show that for subsampled data (cf. Lemma A.III. the following inequalities hold with probability at least 1 a, provided M = 02n log(n/a))
M/M & 3k/n and M1//M, S 3k/n.
(17)
Algorithmically, we check if the bounds (17) hold for S, and output 1 if not. Privacy is not compromised because the check only depends on S and is agnostic to the data.
Theorem 4. Let M,, = S2 ((n² kk2) log n.). Then Algorithm 1 modified to output if the bounds (7 do not hold, is 10e-differentially private. Moreover, suppose that with probability at least 0.99, we have max; (is(t) A,l S & and h(S) - 0) S C for all S E Inkk- Run Wrapper with f = ss. failure probability a, and A PrivateMeamLocalHHiie (Algorithm) at least a, we have
to output O. With probability
IA(X) - = (Vaa(UUn))
GN
ke
12C
RBC ng
min k, !.
V
Mr.
+
+ nae
n2
Remark 4. If the kernel is non degeneeneee and the number of times subsample (for each run of the algorithm) is Qi (k2) then Theorem 4 nearly achieves the same error as Algorithm| ! with S In.k with a better computational complexity for 2 3. The lower-order terms have an additional min(k, factor, which can be removed with 1(n2)) subsamples.
5 Applications
We apply our methods to private uniformity testing and estimation random networks. For more applications, see Appendix A.6.4
1. Uniformity testing: A fundamental task in distributional property testing 6 is deciding whether a discrete distribution is uniform on its domain, called the problem of uniformity testing. Let X1, X2, X2...., Xn be i.i.d. samples from a discrete distribution with support [m)]. characterized
by the probability masses PI, P2..... Pm on the atoms. Given an error tolerance 5 > O, the task is
to distinguish between approximately uniform distributions {p (2 U) & 8/ 22m) and far-from- uniform distributions (p= (p, U) 2 8/vm).
Without the constraint of privacy, Diakonikolas et al. 21 perform this test by rejecting the uniformity
hypothesis whenever the test statistic Un := Eie (Xx X²) > +1+ 382 /02/44/mm and show that this test succeeds with probability 0.9 as long in the appendix, instead of using Un. we use the private estimate Ü, using Algorithm
Ω (m /2/2) As detailed in Algorithm A.4
For our algorithm to work, we require the distributions to satisfy < 2/m for all i. Let Ps (1 + az)/m / for all i, with E [., Under H1, we have E[1(X; X2)] = (1 + ||a]] /m)/

---

(1 + m²),m, where ||]]| is the Eg norm of (a1. Q2...... am)....am) Under Ho, the mean is 1/m. The difference between the threshold (1 + 8² /2) m and the mean (under either of the two hypotheses) is at least 8²/ /2m)) Moreover, [1] shows that the standard deviation of U,, is much smaller than the difference in the means under Ho and H1 as long as n = 12(m 1/2 /52). However, we must also account for the noise added to ensure privacy. In Appendix AA661 we show that the choice of
ç = @ + 1/n) works and establish the following result:
Theorem 5. Let ps (1 (1+a;)/me m with E
[. Ei= a; = 0. Les [Xi}ī=1 be i.i.d. multinomial = Ps. for all i E [m]. There exists an algorithm that
random variables such that P(X1 =
distinguishes between ||al]= 2 6² from
||al
with probability at least 1 - a. as long as and is 10c-differentially private.
m
m
2m
m 1/2
1/2 122 1og(m/66) Toe)
m 1/3
+ 82
62472
8475E
The non-private error term of Theorem 5 is the same as in Theorem of [21] and is optimal [22]. Proposition [ shows that Algorithm AA.2) with the all-tuples family leads to a private error bounded by Ö(1/ne). This private error is (622 /m) only when n = (mn/6"²)). In comparison, Algorithm A.4 has error (82 /m) for n 2 (m 1mii(82, .e)), which quadratically better in m.
Remark 5 (Comparison with existing algorithms), Existing results for private uniformity testing M 131 distinguish between the uniform distributions (E, (v, U) = 0) and distributions away from uniform in TV-distance (fi (p, U) 2 8). Our algorithm considers the alternative hypothesis to be f2(p, U) 2 8/ /m. Hence, our results are not strictly comparable. One caveat that we restrict ourselves to distributions p such that &o (p. U) S 1 1/mm. Our algorithm also allows some tolerance in the null hypothesis, similar to 121) and other collision-basee
testers. That is, can allow some slack and take the null hypothesis Ho E2(p, U) S 6/ /2m instead of Up(
2. Sparse graph statistics: The geometric random graph (see (30 has edges hxX;, X2) == ((Ix, X,ll2 S r.). where In governs the average degree. Under suitable distribution for Xn. the subgraph counts show normal convergence for large range of r. [30) Typically, only observe the graph and do not know the underlying distribution of the latent variables X; or the radius rn- This is why estimates of the network moments are of interest since they reveal information about the underlying unknown distribution and parameters.
Let the X,'s 's be uniformly distributed on the dimeediimesiooal sphere to ignore boundary conditions. For edge density, Eh(X,, X3)) x rh For any distinct indices j. & and given X,, the random variables hx,,, X,) and
are independent. Therefore, Çi = We have E2 var Th X,, X,)l Orr2). so the non-private error is (r,,/n). In Appendix 6A.6.2 we provide Algorithm A.5 that uses [lgorithm obtain a private estimate of the edge density of graph [h(X+ Xi, (r)x ( siejenn Note that the X,'s themselves can be unknown. Our methods can also be used for private triangle density estimation. See the extended version [66] for details.
Xx)) =
Theorem 6. Let rw = (i(n-1/2) and e = Ω (1/nr2). Let (X1,..., X,, be i...d. latent positions such that X; is distributed uniformly on U8? Let the observed geometric network have adjacency S. rr)) There exists a 10e-differentially private algorithm that estimates the edge density 0 of the geometric graph. With probability at least
matrix (Ac,, 1 S. j S. n} where Auj = =[[[|x,-
1 - o, the output i satisfies l0 -1=
+ nage2
+
igge
Remark 6. By Lemmal) I the all all-ts estimator [ satisfies 0 s Or/////nn--/// /T//nc) with
probubility 1 a, where T is the variance proxy of the distribution. Since T = (1(1) 14, the private error overpowers the main variance term in sparse settings where I'n o(1)
Discussion
We have considered the problem of estimating 0 = EE(X Xx) for a broad class of kernel functions h. The best non-private unbiased estimator is a U statistic, which is widely used in estimation and hypothesis testing. While existing private mean estimation algorithms can be used for this setting. they can be suboptimal for large & or for non-degenerate U statistics, which have (11/n) limiting variance. We provide lower bounds for both degenerate and non-degenerate settings. We analyze bounded degenerate kernels motivated by typical applications with degenerate U statistics. To extend this to the subgaussian setting is part of future work. We propose an algorithm that matches our lower bounds for sub-Gan aub-Gaussian non-degenerate kernels and bounded degenerate kernels. We also provide applications of our theory to private hypothesis testing and estimation in sparse graphs.
10

---

Acknowledgments and Disclosure of Funding
PS and SP gratefully acknowledge NSF grants 2217069, 2019844, and DMS 2109155. We thank the reviewers and Gautam Kamath for their insightful comments and suggestions.
References
[1] Acharya, Z. Sun, and H. Zhang. Differentially private testing of identity and closeness of discrete distributions. Advances in Neural Information Processing Systems, 31, 2018.
[2] M. Aliakbarpour, I. Diakonikolas, D. Kane, and R. Rubinfeld. Private testing of distributions via sample permutations. Advances in Neural Information Processing Systems, 32, 2019.
[3] T. W. Anderson and D. Darling. Asymptotic theory of certain "goodness of fit" criteria based on stochastic processes. Annals of Mathematical Statisties, 23:193-211 212, 1952.
[4] Julyan Arbel, Olivier Marchal, and Hien D Nguyen. On strict sub-gaussianity, optimal proxy variance and symmetry for bounded random variables. ESAIM: Probability and Statistics, 24:39-55, 55, 2020.
[5] M. A. Arcones and E. Gine. Limit theorems for U-processes. The Annals of Probability, 1344: 1542, 1993.
[6] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing that distributions are close. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 259-269. IEEE, 2000.
[7] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1):1-25, 2013.
[8] Bell, A. Bellet, A. Gascón, and T. Kulkarni. Private protocols for U-statisties in the local model and beyond. In International Conference on Artificial Intelligence and Statistics, pages 1573-1583, PMLR, 2020.
[9] Sergei Bernstein. On a modification of chebyshev's inequality and of the error formula of laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38-49, 1924.
[10] S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 4475-1444855 2020.
[11] Gavin Brown, Samuel Hopkins, and Adam Smith. Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions. In The Thirty Sixth Annual Conference on Learning Theory, pages
PMLR, 2023.
[12] C. Butucea, A. Rohde, and L. Steinberger. Interactive versus noninteractive locally differentially private estimation: Two elbows for the quadratic functional. The Annals of Statistics, (1()):464 486, 2023.
[13] Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it: Private and sample efficient identity testing. In International Conference on Machine Learning, pages 635-644. PMLR, 2017.
[14] Cai, Y. Wang, and L. Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-2887) 2021.
[15] K. Chaudhuri and D. Hsu. Convergence rates for differentially private statistical estimation. In Proceedings of the International Conference on Machine Learning, volume 2012, page 1327. NIH Public Access, 2012.
[16] Kamalika Chaudhuri, Po-Ling Loh, Shourya Pandey, and Purnamrita Sarkar. On differentially private u statistics, 2024.
[17] X. Chen and K. Kato. Randomized incomplete U-statistics in high dimensions. The Annals of Statistics, 47(6):117 - -3156, 2019.

---

[18] S. Clémençon. A statistical view of clustering performance through the theory of U U-processes. Journal of Multivariate Analysis, 124:42-56, 2014.
[19] Clémençon, G. Lugosi, and N. Vayatis. Ranking and empirical minimization of U-statistics. The Annals of Statistics, 36(2):844-87) 2008
[20] Tertius de Wet. Degenerate and v-statistics. South African Statistical Journal, 21:99-129, 1987.
[21] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. arXiv preprint arXiv: 1.03579, 2016.
[22] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Optimal identity testing with high probability. arXiv preprint arXiv: 02728, 2017.
[23] A. Dubois, T. B. Berrett, and C. Butucea. Goodness-off of fit testing for Hölder continuous densities under local differential privacy, In Foundations of Modern Statistics, pages 53 119. Springer, 2019.
[24] John Duchi, Saminul Haque, and Rohith Kuditipudi. A fast algorithm for adaptive private mean estimation. arXiv preprint arXiv:2301.0709 2023.
[25] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265 265-284. Springer, 2006.
[26] Andrey Feuerverger and Roman A. Mureika. The Empirical Characteristic Function and Its Applications. The Annals of Statistics, 5(1):88 97, 1977.
[27] E. W. Frees. Infinite order U-statistics. Scandinavian Journal of Statistics, 16(1):29 45, 1989.
[28] M. Gaboardi, H. Lim, R. Rogers, and Vadhan. Differentially private chi-squared hypothesis testing: Goodness of fit and independence testing. In International conference on Machine Learning, pages 2111-111100 1-2200. PMLR, 2016.
[29] B. Ghazi, P. Kamath, R. Kumar, P. Manurangsi, and A. Sealfon. On computing pairwise statistics with local differential privacy. Advances in Neural Information Processing Systems, 11114475-44485 2020.
[30] E. N. Gilbert. Random plane networks. Journal of The Society for Industrial and Applied Mathematics, 9:533-543, 1961.
[31] G. Gregory. Large sample theory for U-statisties and tests of fit. Annals of Statistics, 5:110-123, 1977.
[32] P. R. Halmos. The theory of unbiased estimation. The Annals of Mathematical Statistics, 17(1):34 - 43, 1946.
[33] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. Proceedings of the forty-second ACM symposium Theory of computing, pages 705-714, 2010.
[34] H.-C. Ho and G. S. Shich. Two-stage U-statistics for hypothesis testing. Scandinavian Journal of Statistics, 33, 2006.
[35] W. Hoeffding. A class of statistics with asymptotically normal distribution. The Annals of Mathematical Statisties, 19(3):293 325, 1948.
[36] Wassily Hoeffding. The strong law of large numbers for u-statistics. Technical report, North Carolina State University. Dept. of Statistics, 1961.
[37] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-34 1963.
[38] Janson. The asymptotic distributions of incomplete U-statistics. Zeitschrift für Wahrschein- lichkeitstheorie und Verwandte Gebiete, 66(4):495-505, 1984.
12

---

[39] G. Kamath, J. Li, V. Singhal, and J. Ullman. Privately learning figh-dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
[40] G. Kamath, O. Sheffet, V. Singhal, and J. Ullman. Differentially private algorithms for learning mixtures of separated Gaussians. Advances in Neural Information Processing Systems, 32, 2019.
[41] G. Kamath, V. Singhal, and J. Ullman. Private mean estimation of heavy-tailed distributions. ArXiv, abs/2002.09464, 2020.
[42] V. Karwa and S. Vadhan. Finite sample differentially private confidence intervals, arXiv preprint arXiv:1711.03908, 2017.
[43] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What learn privately? SIAM Journal on Computing, 40(3):793 826, 2011.
[44] J. Lam-Weil, B. Laurent, and J.-M. Loubes. Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint. Bernoulli, 28(1):579- 600, 2022.
[45] J Lee. U-statistics: Theory and Practice. Routledge, 2019.
[46] C. Li and X. Fan. On nonparametric conditional independence tests for continuous variables. WIREs Computational Statisties, 12(3):e148) 2020.
[47] O. Linton and P. Gozalo. Testing conditional independence restrictions. Econometric Reviews, 33(5-6):523-552 2014.
[48] S. Minsker. U-statistics of growing order and sub-Gaussian mean estimators with sharp constants, 2023.
[49] K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the Thirty-Ninth Anmual ACM Symposium Theory of Computing, pages 75-84,22 2007.
[50] W. Peng, Т. Coleman, and L. Mentch. Asymptotic distributions and rates of convergence for random forests via generalized U-statistics. arXiv preprint 1rX.v:1905.10651, 2019.
[51] Yannik Pitcan. A note concentration inequalities for u-statistics. arXiv:1712.061660 2017.
arXiv preprint
[52] D. N. Politis, J. P. Romano, and M. Wolf. Subsampling. Springer Science & Business Media, 2012.
[53] T. Popoviciu. Sur certaines inégalités qui caractérisent les fonctions convexes. Analele Stiintifice Univ. "Al. I. Cuza", lasi, Sectia Mat, 11:155-164, 1965.
[54] R. J. Serfling. Approximation theorems of mathematical statistics. Wiley Series in Probability and Mathematical Statistics Probability and Mathematical Statistics. Wiley, New York, NY [u.a.], [nachdr.] edition, 1980.
[55] Galen R Shorack and Jon A Wellner. Empirical processes with applications to statistics. SIAM, 2009.
[56] Yanglei Song, Xiaohui Chen, and Kengo Kato. Approximating high-dimensional infinite-order u-statistics: Statistical and computational guarantees. Electronic Journal of Statistics, 13(2), January 2019.
[57] Ullman and A. Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32, 2019.
[58] A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
13

---

[59] R. Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[60] M. J. Wainwright. Iligh-Dimensional Statistics: A Non-Asymplotic Viewpoint, volume 48. Cambridge University Press, 2019.
[61] N. C. Weber. Incomplete degenerate u-statistics. Scandinavian Journal of Statistics, 8(2):100-
123, 1981.
14

---

Roadmap of Appendix
1. Section A.1
U statistics and concentration of U statistics
2. Section A.2
Composition theorems for differential privacy
3. Section A.3
Details
extension of the Coinpress algorithm [T]
4. Section
Proofs of lower bounds
5. Section A
Proofs of the main theorems 2 and
6. Section A.6
More applications and details on uniformity testing and edge-density estimation
A.1 U-Statistics
Let h X* + R be symmetric function, and let Xi...., variables XI,..., Xns (h), associated with is defined as
Xn X. The U statistic the
Un
E A(X.,....... Xix).
(A.18)
(E
The mean of Un based on iid variables X1, XI,...,Xx X, ~ D, for some distribution DD on X, simply 0 : [ X=)]- Moreover, the variance of Un can be expressed succinctly in terms of conditional expectations [45]. For c 1,2,.... ......,, k. define he : X + as
he(X, ..... Xx) = [x( ..... Xx) I1, X Jee,
(A.19)
and let
-a (hol,hoX.,.......
(A.20)
Equivalently, Se cov (f(Xss) h(x,)) where St, S2 E In,k and |S| n S2l The number of such pairs of sets S1 and S2 is equal to (+) (K=R), which implies implies Eq
Hoeffding decomposition. A U statistic of degree ks can be written as the sum of uncorrelated U statistics of degrees 1,2,.... Define
(X1) -((1)) -
and for all ko
Xx) = (Ne(X1,...... - 0)
h (Xs).
& $ESCTe
Then, Un can be written
U. 0 + Σ U(O)
(A.21)
where U is the U statistic on xI....,X. X,, based on the kernel ((0c) Equation A.21 is called the Hoeffding decomposition (or the H-decomposition) of Un [36). (36 also shows that the e functions h2(1) ,...,, (k) are pairwise uncorrelated. That is, let 1 Sc d k and let S. and Sa be subsets of
[n] of sizes e and d respectively. Then,
Cov (m (X
= 0.
This allows to write the variance of U, in terms of the variances of (e), For all [K)], define
8² Var h (o))
(A.22)
Then,
Var(Un) = Σ
71
82
(A.23)
Moreover, the conditional covariances So are related to the variances 52 in the following manner:
(9) Go.
So
82
Σ
(A.24)
i=1
15

---

Lemma A.1. Suppose k S m/22
(i) IfC > 0, then
Var(U,,) h-
+ +0 (ce
1.2
(A.25)
n12
(ii) C1 and C2 > O, then
Var(Un) k2 - 1) 2n(n - 1)
+0
(A.26)
71
Proof. This result follows directly from a calculation appearing in the proof of Theorem 3.1 in 48 Note that
hi
09
==1
for all j E [t]. Moreover,
h
Var(Un)
=
5
k
71
5
89.
3=1
For part (i), we write
2
k2
Var(Un)
83
12
n
j=2
k2 12
k
k
2 n²
+
Ck
1
11
11
n2
n
n
j=2
For part (ii), we write
Var(Un) k2
k2(K - 1)252
k² 1)
Cj
+ Gx
2n(n - 1)
2n(n - 1)
j=3
- k²(k-1)26
4:
k j
2²2 - 1)
2k
+ Ch
Σ
+
2n(n
2n(n - 1)
n
j=
Lemma A.2. For all 1 scsdss
v
(A.27)
d
In particular, KÇ1 S Sk-
Proof. Using equation A.24
Sc = =
)
Σ
c
8
Σ
Sa
d
Lemma A.3 (Concentration of U-statistics).
[37 9
(i) If H. sub- Gaussian with variance proxy T, then for all > 0, we have
[_ 1
PP P(U, 0 2 t) <
2exp
(A.28)
2T
16

---

(ii) H is almost surely bounded in (-C,C) C). then for all t > 0, we have
- [
IP (IU 0 t) S exp
(A.29)
2(n 2C1/3
Proof. Without loss of generality, let 0. For any permutation of [n], let
Vo
h(X ((Xo(((111)+1)) (x(((-1))))))) X (o)))));
where m m= [n/k]. By symmetry, Un = n. Eo Vo. For any 8 >
P PU, 2 t) = P (c 2 edh) S c E [ealin]
= =
exp
8
Σ Vn
n!!
S SE-EE
Σ exp(sVn) = (exp(ssss
n!
e =E=
exp
(
(x))
If H is sub-Gaussian with variance proxy then we can further bound the inequality above
S²T 2m
S²T
(U, se st eep
exp
2m
Set = fm 77 to get the desired result. Note how the argument is similar to the classical Hoeffding's 's inequality argument after applying Jensen's inequality on V,- The second result follows similarly by adapting the tricks of Bernstein's 's inequality 9 to [37]; for a detailed proof, see [51
A.2 Details on Privacy Mechanisms
Lemma A.4. (Basic Composition) If A, : xm - S2 is E.-differentially private for all i E [k], then the mechanism A x S1 Sy defined as
A X.) (Ai (X...... ..)....,AA. (XI,...,X.))
Σ === --difeereniially private.
Lemma A.S. (Parallel Composition) If A, : X" + S₁ is e-differentially private for all E [k], then
the mechanism A 2 - S1 x x S₁. defined as
A(X1...,XKu) = (X).....))) . (Xut1 X2n) ,.., (X 1)tt..... Xkn))
c-differentially private.
A.2.1 Private mean estimation
A fundamental task in private statistical inference is to privately estimate the mean based on set of IID observations. One way to do this via the global sensitivity method, wherein the standard deviation of the noise scales with the ratio between the range of the distribution and the size of the dataset. the fairly realistic case where the range is large or unbounded, this leads to highly noisy estimation even in the setting where typical samples are small in size.
24 has looked into designing better private mean estimators for (suub)Gaaussiee vectors. Our work will build on one such method: CoinPress [10]. The idea to iteratively refine an estimate for the parameters until one obtains a small range containing most of the data with high probability; noise is then added proportional to this smaller range. Note that some dependence on the range of the mean is inevitable for estimation with pure differential privacy B3 [1].
To remedy this effect, line of work 42 39
40
17

---

A.3 Details for Section 3
A.3.1 General result
We will prove a more general theorem than Lemma using other families of subsets derived.
! from which Lemma 1 and related Lemmas
In Algorithms A.2 and A.33 we present natural extension of the CoinPress algorithm 10, which is then used to obtain private estimate of 0 with the son-private term matching Var(Un). Originally, this algorithm was used for private mean and covariance estimation of i.i.d. (sub)Gaussian data. We extend the algorithm to take input data jEjm such that (i) each Y, is equal to h(Xs) for some S, (ii) the Yj's are weakly dependent on each other, and (iii) each Y,. as well as their mean ZjE(m] /mm has sufficiently strong concentration around the population mean.
[n/k] and Y, h(Xs,) for all E [m/] where S, (Ú 1)k- 1..... (j - 1)4 + k). Then Algorithm A.2 reduces to the CoinPress algorithm applied to n/k independent observations ((Ss,) 1(X (xxx) s.)........................ (....)
For instance, suppose
Algorithm A.2 U-StatMean
n, k. h (X))egm)) (.,,... [Sm , R, e, Q(),
I: log (R/Q(7)),
rol f- [-R, R
2: for j = 1..... do
3: Yo,- f- h(Xs,)
4: end for
5: for 1,,,, do
6: [Yi.))E(mm) (2,, r:] < U-StatOneStep (n, (Vi-1.), (1--1, rs r-- 1) 2 7, Q(), Qr))))))()))))))))))))))))))))))
7: end for
8: (Y++1J]E[m) 1e41,7441l + U-StatOnneStep (n, k; (Yrs), mi), e/2, 2/ 00) ())
9: return (6-- + T2+1)/2
Algorithm A.3 U-StatOneetep n, (Xisemmj ,,,
Y2 proji-Q(8).+0003) (Y3) for all 1 S m. m.
2: + dep,..k (+)(3)+2)(33)
3: Z + 1 ΣØ= WW, where W ~ Lap (+) ()) + A log b) 2 (()) + log
4: [[
5: return [Yg)se(m) rl
Let and k be positive integers with k S n/2, and let h x - R be symmetric function and let DD be an unknown distribution over X with E [N([Db]] 0 such that |0| < Rofor some known parameter R.
Setting 1.
Sm be a family of not necessarily distinct elements of Let m be an integer and F= - S Ln,k- Define
f Kij E [m] E
(A.30)
the fraction of indices j such that Sy contains i, and define the maximal dependence fraction
dep n.p,,, (S) max ft. *E(n]
(A.31)
For each j E [m], let Y, denote h(Xs)). Clearly, E [Yg]] = 0. To allow for small noise addition while ensuring privacy, it is desirable to choose S with small dep,.. (S).
Define functions ((3) = Qn..A.,D.((B) and Q"VE( 2 D. (3) on 3 E (0, such that
1
PP
sup jE[m]
Y - Q(8) <B, P
Y,
0 2²T(()) < B. (A.32)
18

---

We will refer to Q and (²)((3) as 8-confidence bounds for supje[m] DY, - 6) and 4. [ Y, 0 respectively. We apply Theorem A.1 (specifically, the form obtained in vh
Lemma A.6 to different F to obtain private estimates of 6, with statistical and computational trade- offs depending on the family F. As Remark A.7 suggesss, we will also need to privately estimate concentration bounds on the Yj's and their average. Naturally, this requires private estimate of the variance Ça- We provide guarantees from Biswas al. [10] for private variance estimation and mean estimation here, where we have translated the mean estimation guarantec to fit our setting.
Before do that, natural approach this problem is view it a standard private mean estimation task: split the data into n/k equally-sized chunks, apply the function h to each chunk, and run any existing private mean estimation algorithm these n/k values. We show that the error guarantee of such an algorithm is suboptimal compared to the error guarantee using the all-tuples estimator or even the subsampling estimator sufficiently many samples are used. Before stating the propositions associated with these families, we state and prove the mother theorem.
Theorem A.I. For O, Algorithm A.2 with input (n, ko,k,,.. h, (Xi) (Xi)eem)) F, R. (M))) returns 6, such that
Q*))())
V Varl VarlE Ejei Yj)
depa, (F) e
log (1)
n 5O
(A.33)
m /
nov-private ervor
private evior
with probability at least 1 6% 6-/Das
as long
Q(7))c
dep... (F) S 10tQ(r/t)log
and
(rr((t/)) Q(7).
(A.34)
where t = [C'looo (R/Q(T)) Moreover, Algorithm A.2 is e-differentially private and runs in time O(n + log (R/Q(n)) + F(F)))
Remark A.7. Theorem A.I assumes that Q(-) and Q**(()) are known, despite the mean being unknown. Note that we only need to know the value of these functions at "y and 7/t for given y. If these bounds are not known, we may first need (privately) compute Q(z) and Q= and then use those privately computed bounds in the algorithm. For example, if the Yi' are sub- Gaussian with variance proxy I, then Q(x) /log(m/x). We will see how to estimate these parameters for various families F of indices used in Algorithm
Proof of Theurem A.7 We will prove privacy and accuracy guarantees separately.
Privacy. Algorithm A.2 makes t + 1 calls to Algorithm A.3 let A, W,, and Z& be the values taken by A, W, and Z in the th call Algorithm A.3 for sist ++++ Let 3 2. can be shown :'
inductively that the interval lengths r; 1; and the values A; do not depend on the dataset. For any 1 I isit note that Y,,, proj, Q.3),, Q(8)) (Y:-1,)) for all 1 < j S m. Suppose we change X, to X for some index w. For any 1 1 2 i i + 1, conditioned on the values of Ze for S < i, most a dep,.. (F) fraction of (Y.,) depend w (this is true by the definition of dep (F)). Since Yo,- proje, 1-)()).: 2(8/mmm (Y,1.j) has range T;-1 4-1 2Q(3), the sensitivity of 1 1ド= Yr, is at most dep,, (F) (r;-1 4-1 + 2Q(3)) = A. Therefore, by standard results (cf. Lemma [}. for all <ish C, the output Z, (and therefore the interval r.), conditioned on Ze for
1 < < žσ -differentially private. Similarly, the output (le+1 + r+++1 1/2 Zr+1. conditioned
on (Z (Ziheet), is e-differentially private.
i ddifferrentially private. By Basic Composition (see Lemma A.4. Algorithm A.2 is
7 Utility. First, we show that if Algorithm A.3 is invoked with 0 E [1, r]. returns an interval [[' such that 0 [?', r'] with probability at least 1 3,8. Consider running variant of Algorithm A.2
with the projection step omitted in every call of Algorithm A.3 With probability at least 1
3.
have > Y: 0 < Q²*((3), and with probability at least
we have [W] log
'The following subsection modifies the algorithm so that the emror depends polylogarihhmicaly in
19

---

Therefore, with probability at least 1 -23, we have
A c' 3
7 0 v QTye
log
in which case 0 E [',r"]
Finally, reintroducing the projection step only increases the error probability by most 3. Taking union bound over steps, we see that 0 E [1,r"], with probability at least 1 1-3y.
Next, we claim that if r - > 28Q(n), then r' - S (r l)/2. Using the assumption, we have Q(7)c
Q(7)c'
dep n.k (F) < 10tQ(T/tt) logt/7 I min log 1/3" 5Q(3) log 1/B
where the second inequality follows from taking c' = c and using the fact that Q(7) Σ Q (7), since the quantile function is nonincreasing. Furthermore, by the assumption Q Q(7), we have
2
2dep..k (F) log 1/3
(r (r- + (2) + 4depn,k n (F) ((3) log 1/3
e'
e'
2(r 1) + (20(g) + 4 $ r-1
(0())))(())))))
5
Thus, after = Ω log ) iterations, we are guaranteed that the length the final interval [e, re] is at most 28Q(7).
Finally, consider lines 8 and 9 of Algorithm A.2 The algorithm returns the midpoint of the interval By Chebyshev's inequality, have
[e+1, T. which is Ze+1 in the final call of A Igorithm A.3
1
m
m
Yo.3
Var
Yo.5
(A.35)
m
m
j=1
with probability at least 1 - and with probability at least 1 none of the Y,'s are truncated in the projection step in the final call of Algorithm A.3 Finally, with probability least 1 7, we have
(A-1)
depm,, (F)
log 1 7
W e++1
O
The conclusion follows from a union bound over all events.
A.3.2 Boosting the error probability via median-of-means
Algorithm A.2 incurs 1/v7 multiplicative factor in the non-private error, stemming from an application of Chebyshev's 's inequality to bound | h(Xs,)/m 0). For specific families F, we may be able provide stronger concentration bounds for Σド= ((Xs,) \/m in inequality (A.35). Instead, we complement the result of Theorem A by applying the following median-of- of-faans procedure that allows for an improved dependence on the failure probability a with only a log (1/a) multiplicative blowup in the sample complexity:
Lemma A.6. Let E (0, and 2 0. Let A be e-differentially private algorithm. Consider
a size n dataset D, 5.1.d D, for distribution D with some unknown parameter 0 such that with probability least 0.75, we have
- Tn-
Split D, into q == llg((//)) equal independent chunks and run A on each chunk to obtain e-differentially private estimates (0nz) of 0. Let @meed be the median of these estimates. Then ğueed is e-differentially private, and with probability at least 1 a, we have
gomed 0 Tn/g
(A.36)
"Assume for simplicity that divisible by q and is odd integer.
20

---

Proof. The privacy of @ follows from parallel composition (Lemma A.5 For utility, we know from the hypothesis that for each [g], with probability at least 3/4, the estimate On, satisfies
10.. 01 S Tn/4
more than half the estimates 6n. satisfy the above equation, then does the median. Let be the random variable that assumes the value 0 if dn,, satisfies the above equation and assumes the value 1 otherwise. Then, [[]:] S 1/4, and it suffices show that
Pr (T(Ti + T2 + T, S q/2) 2 a.
This follows from a standard Hoeffding inequality; as long as q 2 8 8log(1/a),
(T + + Tg 9/2) Pr
C - 9/4 //4 S 0e-2(1/1) S a.
A.3.3 Application to the all-tuples family: proof of Proposition 1
For any E [n]] there are exactly (R=1) sets S E I, such that E Following the notation from
the setting of Theorem A.1 we have fa (t=)) / (x) tt2 for all i [nx] so dep,,, (Fan) &
Moreover, for each S E In we have (Ih(Xs) 0| 2 y) S 2 exp
(-²² 2+
Letting
2n
2 11 (7)) (-
@(7) = 2Tk log log
2r log
we see that each Y; is within Q(7) of 0 with probability at least
A union bound implies that this
choice of Q(7) is valid. For the concentration of the average can use Lemma A.3) to see that
jElm] Vj, which is simply Un. we
Q (7) = 2 log 2
n
a valid choice. We now verify the conditions in Theorem
k Q(7)E
E
log 2n/
dep,n,k (8)
101Q(T/1) log(1/7)
10/ 10/ log(1/7) V
log 2ml /
if and only if
10kt log(t/>)
log 2nt/
n
log 2n/7
Recalling that [Clog (R/Q(7))) see that this holds under the sample complexity assumption on n. Furthermore, we have Q (7/() < Q(7) if and only if
k log 2t
log 21/7 n
2 log
n
log n//7
which is also true by assumption. Therefore, with probability at least 6y, we have
0 0| 5o (+/ Var(Un) +
2rk log
me
Algorithm A.3
uses constant failure probability of 7 0.01, which assures success probability of
least 0.75. This is further boosted by Wrapper Now, an application of Lemma A.6 gives the
stated result.
21

---

A.3.4 Application to the naive family
Definition A.3. Consider the following estimator: divide the n data points into n//k disjoint chunks, compute h xx) ) on each of these chunks, and apply the CoinPrest algorithm (TO) to obtain private estimate of the mean O. We will call this naive estimator maive-
The following proposition records the guarantee of the naive estimator Onaive:
Proposition A.I. The naive estimator Ouoive satisfies
kCk
RVT
0 naive -0 S
+ +0
THE
with probability at least 0.9, as long as n = 52 f log
R vF
The estimate Quaive is e-differentially
private and the algorithm runs in time Ô nn + log
R v7
First, suppose the variance Ça known. It easy to see that dep,,, (Fraive) that (Xxs) is r-sub-Gaussian, we have
&. n.
By the assumption
y²
P(I((Xs) - 0 2 v) S 2 exp
2T
Hence, with probability at least 7/m, we have
1 0 S / 2r log(2m/7),
(A.37)
for each S S m, where we use the notation as in the setting of Theorem A. By union bound, Moreover, since the Yj 's are independent,
we can take the quantile function Q(7)
2T log
2n
the average Σ)ε() Y, is I Sub-Gaussian with variance St. Therefore, we have
1
2xxp (- my²
P
Y
m
2T
This yields a bound of Q²²8(7) = We have
2kr 1og(2/7)
It remains to verify the conditions of Theorem A.1
Q(7)e
log(2n/kr) log(2nt (2ntt/kn)) kzy)
<
< 10t log(tt/)))
n 10HQ(1/t)log(t/))
n
and
2kT log (2t(tt)))
Q"E(n/t)< < <(()) -
2 / 27 Log((22// kz)
log (2g(2t/r)
log (2m 2m/ky)²
which are both true by the sample size assumption, noting that = [Cloo(Rt/(()))) Therefore, with probability at least 6y, we have
O 0 s o (12 Var (aaavee)
2 (og((22)))) log 2)
Choosing be an appropriate constant, arrive at the deisred result.
22

---

A.3.5 Application to the subsampled family
Unlike the all all-pairs family San, the subsampled Ss in Definition 2 is randomized. Define 8ss Σe=1 M(Xs,)/M. Recall from discussion before (ef. Theorem A.1 that we want each of the h(Xs,) )'s, as well as l... to concentrate around 6, and we also want dep,, (Sys) to be small. As we show, the former concentration holds as in the all-tuples case, and the latter holds with high probability.
Proposition A.2. Let M, = (2((n/))))) log n.. Then Wrapper 7 with f f ss, failure probability a, algorithm A U-StatMean (Algorithm A.2 S(1)) set of Mn, i.i.d. subsets of size k picked with replacement from 1, returns an estimate 0 such that, with probability least a.
00s 01 S 50 (Var(Una)) + +0
(V(
SK
63/2V5
Mnn
nhe
as long as na = 52 & (log ( Moreover, the estimator Ozs is E-differentially private and runs time Ô (log(1/a) (k log VKT) Mn.)
First, need the following helper lemmas:
Lemma A.7. Define 8_ M Eser, h(Xs). We have Var [0.] (1 M) Var(Un) + Sr-
Proof. Clearly, [[]=] 0. We compute both terms of the following decomposition of the variance of fx separately; recall that X {X;
Var (ms)) Var
(m [0l1x]
+ E VVa (0 [smlx)]
Now,
Var
E
[0ss( [x]
Var
E
1
Σ h (Xs,) X x )) = Var(Un),
M
JE[M]
and
1 M
E
Var
Oss
x)
=
E
Var
h(Xs;)
=
E [aar (h(Xs)) X)I
M
M
j=1
E
Σ h(Xg)²
Σ h(Xs)
M
SETn.k
SETTukk
1
GK Var(Un)
((Cs + 02) (Var(Un) + 02))
M
M
Adding the two equalities yields the result.
Lemma A.8. Let y > O, and let M = 226 log "). Then dep (Fa) < 4k with probability at least
1 1-%
Proof. Let Z; be the number of sampled subsets of which is element. Observe that Z; Binom(M, k/n), with mean = Mk/n. By a Chernoff bound, for any 8 and any i E [n], we have
P
(A.38)
(1 111+5
23

---

By union bound, we have
P (depmn (Fs)
4h
mmax Zi > 4p) In
e
"
Mk n
(1+ (1+33) 3)143
S nexp
71
which is at most y by our choice of M.
Let Gn denote the event that dep,, k (Fa) S 4k which occurs with high probability by Lemma
A.8
Note also that conditioned on any family Fss of subsets of In the run of Algorithm A.2 is differentially private. Since the randomness of F&s is independent of the data, the algorithm (along with the private variance estimation) is still 2e-differentially private.
Let
4n and (7 - -V min (M, m)
TK
4n
Q(7) - v k log
log
We show that these are indeed the corresponding confidence bounds for Ys, S Fas and 0zs.
By a sub-Gaussian tail bound, for any In, the probability that (h(Xs) - 0 > Q(7) is at most
2 In S z.. By a union bound over all (?) sets S, we then have I((Xs) S Q(7) for all
SE In,k: with probability least 1 - 3 Call this event Ey.
Next, 1|0 X²1 Un. Moreover, for any > 0,
P 10ss 01 2 )) < (10== - Unl 2 2/12 + P ((U 0 2 c/2)
(-nc² nc²
I Ex Xx
X, P (10ss - Unl 2 c/2|X1...... Xn) + 2 exp
(-8kT
8kT
where we used Lemma A.3 to bound the second term. For the first term in inequality (..40.. note that conditioned on the data XI,..., the h ((xs))ss are independent draws from uniform distribution over the (2) values (h(Xs) with mean Un. and the (M(Xs,) 0l's 'ss are bounded
by maxseT,,, [1((s)-00 < Q(7). Therefore, each h(xs)) -U is Gaussiannu(())) implying that
E
Unl 2 c/2/X11 ......... x - 2E exp [10s-
M
|X Ix.,...., NK,....X...6. E
+ P(ES)
8Q(7)2
2
< 2 2exp
+ +(()))
16rk lorklog(44//) (ogg(4///))
M
$ 2exp
+
(A.39)
167k log(4n/7))
=2-
Combining inequalities (A.40) and AA.99
we have
TP (0s. - 01 2 e) s 2exp
M
+
7
2exp
no²
S7.
(A.40)
167k log
8k7
as long as
rk log
2n
8
C 4V min (M,n)
log
This justifies the choice of Qav8(7). We now verify the conditions in Theorem Gy, we have
A.1
Conditioned on
4k Q(7)e
log 4n/7 log 4nt/
depn.k(S)
10)Q(n/1) log(t/?)
10t log(t/>)
n
24

---

1 if and only if
40kt log(t/7)
log 4nt / log 4n/y
Recalling that = log (R/Q(T))] we see that the above holds under the sample complexity assumption Furthermore, Q (n/t) Q(7) iff
rk
Ant
4n
log( (og(4nt/7)) log 4n/7
V min (M, n) S 2
log
= min(M, n)
Since M 2 E log the assumption the sample complexity of implies the above result.
Conditioned E,, the projection steps are never invoked in Algorithm A.2
A.3
so we have 0sx
0gs 1 Wi+1, where W is Laplace random variable with parameter 24
where d
(coming from the noise added to M E Y, in the (t + 1)th step of Algorithm Lemma A.8. we have
A.2
Finally, using
24 E
2dep,.. (5)
L
8k
1
4n with
00s dsl WW++1|
log
log
log
2rk log
7
716
on the event Gy- Combined with Lemmas A.6 probability least 1 - 77, obtain
A.7
incquality
(A.40), and Theorem
A.1
k
1 kk log
4n
10x- 01 5
Var(Un)
log
Vr
M
ne
7
The success probability is Try instead of 6- because we also require dep.., (Fx) S which holds with probability - as in Lemma A.8 Algorithm (A.tthmm[A.] Juses constant failure probability of
7 = 0.01, which assures a success probability at least 0.75. This further boosted by Wrapper] Now, application of Lemma A.6 gives the stated result.
A.4 Proofs of Lower Bounds
this appendix, we provide the proofs of our two lower bound results.
A.4.1 Proof of Theorem
Letp= (P,, be a fintte family of distributions over domain X such that for any + the total variation distance between P. and P, at most a. Suppose there exists positive integer n and an c-differentially private algorithm B X > [[P]] such that for every P. P, we have
Lemma A.9 (Lemma 6.2 in 41
Pr X PPP
(B(X
.., = 2/3
Then, n Ω log [P]
Lemma A.10 (Proposition 4.1 in (4) The Bernoulli distribution Beru(p) is uub-Gaussian with optimal variance proxy Tp. where
1 -
Tp T1-p
log - 1)
for p E 10 (1/2). In particular, if0 < < 1/10, then Tp S 2 log oF
Define Do = Bern(1) and D, Bern(1 3)), where B = e. and c small enough such that
ne
k3 1/10. The TV-distance between D, and D, is B. Since se. also choose small enough
25

---

such that Lemma A.9 is violated: for any e-differentially private algorithm B :00,1 + {0,1). there exists an i [0. } such that
Pr ( = 2/33
(A.41)
by Lemma A.9
Consider now the task of e-privately estimating the parameter
((D) == Ex,,... I.c.... X [h(X1, ;,)....;))]..
where X2 D and
((X1, X2, Xx) = (T(=3)
1 (X1 X2 ... Xx = 1),
for some distribution D. Suppose there exists e-differentially private algorithm such that
1
1 (1 3)
E Ex X. ~ D |A(XI, X.)
(A.42)
(1-8)"
for any DD such that the distribution H. of 1(X1...... Bern(1-8), Lemma A. shJswss that the distribution H of Xx) is indeed sub-Gaussian(1), If inequality (A.42) holds, then by Markov's inequality.
X&.) is sub-Gaussian(1) (1). If Bern(1) or
1- 11-1-80 3)th
Pr XiND,
(i)X,,...,,,)-0000
2
(1=
3
for E {0, 1}.
Also, 0 (Do) 1I- and 0 (Di) = (1- 8)* /TI/ The difference between these means is
0 (Do) - 0 (D₁) 1 (1
(1-9)"
Therefore, the following algorithm violates inequality AA.1I: Run A on X1, Xi...., X,, to obtain A.
Output 0 if 0 is closer (Do) than to ((Di), and output I otherwise.
This implies inequality (A.42) does not hold, so we have lower bound on the expected error. Theorem [ follows from the calculation
1 1- (1 (1-3)* 3)
k3
1
log 1 k3
2oo
θ
kB (
111-
2
1
2 31-3)a)
where we used 1 - kB < 8) <
k3/2 for kB < 1/10.
A.4.2 Proof of Theorem 3
Consider two datasets Dq and Dj size each, differing in at most 1/c data points. Suppose (AA) - Un(DD) have
< 10 [U, - Un()ii) for E Do, Di}. By Markov's inequality, we
Pr (A(D) (n) 1 UD.(DD)) Un, (Di)) 0.8.
for E (Do, D1). Moreover, since A is eddifferentialy private, we have
Pr (A((D)) - (IA(D))-U,,DD)))) Un()))l (Do) - -Un(Di))) - (D) - (IDDD--Un(DD)) -Un(Di))
1 Pr (A(DD)-UUs(D)
0.8
By the triangle inequality, the event (I((D)) U,,))) < (UDDD is disjoint from the event (IA(D.) - (n,)) < (U.))
(D.)) }. The sum probabilities of these two events
26

---

at least 0.8 + 0.8c > 1, contradiction. Therefore, A has expected error Q (Do) - (D())) on least one of Do or Dr. Next, we will define appropriate choices of Do and D
For simplicity, assume 1/c is an integer. Define bn [k + 221(22222) / range of implies that bn 2 2k/e. e. Let h(x1...... σk) = 1(21 = xx). We define Do such that
1 The assumed
1,
i S bn
3i
i, i> bn.
We define D1 = -u,,...,, ,nn) such that y/ = for all & (b., + 1, 1,...,h + +/e} and y/ = 1 for bn < iss S bn + 1. Hence,
bbtt///
Un(Di) Un(Do)
n
Furhtermore, for & s bn, using the fact that (1 x1)" S
1 for 1, 1/rr,, we have I-rx
(0m)
k-1
bn -
bn
1
k
= 1
bn 1/E -i 21 -
Nn tu/c//
bn + 1/e
k
1=U
(1-
1/e
1
k/e
= 1
21
on + 1/c)
k/e 1
on + (1e 1)/c²
butl/e
implying that
k/C
+//+1/)) (bn + 1/cc
Un(Di) - -n(())))((D)) bn + (k: 1)fE
(A.43)
k
k
(-))
For with x; = 1 in Do. we have hD (1)
S Un.))). For with I; = 1 in D1. we have
(-:1)
Tud (i) (1e-1/e1)
$ Un(D.). Therefore, we have (nn(1) Un(D)) - (i) S E for all and
D E (Do, Dit. where
(n+t1/-11)
k-1
- i bn + 1/c -
On + 1/c
h-1
k
g:
II
S
= 0
n
n
by our choice of bn. Moreover, we have
> bn + 1/c k
h k2/(2k-2) 2-1/(22-22)
k-1
k
(A.44)
k
By inequality A.43 and the definition of &, we see that
ke/c
bn + 1/c
k 3ne E,
U,(D:)) - (Do))) b, 2k/e
where the second inequality follows from the assumption that k/c S bn. Using the lower bound on as in inequality (A.44). we obtain the desired result.
A.5 Proof of Theorems and
We first prove Theorem f with S equal to any subsampled family that satisfies the inequalities (17). In particular, the following lemma guarantees that the required bounds hold with high probability for a subsampled family chosen uniformly at random from In
and let M S. n=2 log (:)). Let S be collection of M i.i.d sets k.2
Lemma A.11. Let ? >
sampled uniformly from In,k- For each i [n], let Se be the number sets in S containing and define M, = { For each i i jE E [n], let Siz be the number of sets in S containing i and j. and
define M.j (Sizl. With probability at least 1 7, for all distinct indices i and j, we have
M2
2k
M
2k.
<
<
<
<
2m
M
2n
M
27

---

Proof. Note that Mj ~ Binom(M, k/n). By a Chernoff bound, for any 5 > 0 and any i E [n], we have
Pr
M₁
kM
kM
S e (0.55)(kM/m)//) se 0 l)
72
2n
which is much smaller than 2_ Call this event E,, and for the remaining argument, assume & holds
2n for all i (which, by union bound, holds with probability at least 1 - )) This gives the first inequality.
For any distinct j E [n], conditioned the value of M,, we have Ma Binom (k- 1)/(r) 1)). By a Chernoff bound, for any 5 > and i E [xx] with j 7 i, we have
Pr (MLs (k- M) (n 1)
(k: M) 2(n 1)
?
Me
Se
2n
using the fact that M, 2 &M and our assumption on M. The second inequality then follows from a union bound over all pairs of indices.
2n
A.5.1 Proof of Theorem 4
Consider two adjacent datasets X = (X1, X2...., X.) and X' = (X X2.., differing only in the index i", that is, X = X2 for all * i Throughout the proof, we will use the superscript prime to denote quantities related to X'.
Let B = (Bad(X) X) U Bad(Ba())))) (X)) \ ((*) and G = (Good(X) n Good( (x)) {t*). Then
m An An. Σe (9(Xs) g(X'))
SES
Σ (o(Xs) g(X's))+
Σ (o(Xs) - 9(X)))+ + Σ - ox(ss)) (A.45) 8
Sh
858
$5
Ts
Ti
12
We bound each of the three terms separately. The term T2 is equal to 0: all indices i S have weight 1, and i & S. so (Xx)) = h(Xs) = h(X') = g We prove some preliminary lemmas before bounding the first and last terms. Recall the definitions of L and wt in equations 12 and respectively.
Lemma A.12. We have:
(i) AA, A', < 2&C and L L'| < 1.
(ii) For all i + i", we have
4kC [mv(()) A'1 - -lh(1) Anl
(A.46)
n
[wr(1) wr sc
(A.47)
and for S, such that i" & S,
[wr(S) wf Se.
(A.48)
Proof. For (i), note that
M,C 2kC
AA, A,
Σ
(((ss)n(X3) h(X')) <
M <
(A.49)
M
SES.
where the last inequality comes from Lemma A.ll Similarly, for any f i we have
[1()) - -i)
1
(h(Xs) h(X3)) <
Mr C
2kC
(A.50)
M
M
SES.,
28

---

(t
A
6kCL
6kCI.
+
R(1)
Figure A.1: Weighting scheme in Eq
(4p
Therefore, if an index i * is in Good using inequalities A.49 and (..50), we have
(i)()) - 4,, - (1) (1) - h(ii) + [h(1) - An + |An A
(A.51)
2kC + (E E 6kCL) + 2hC
kC (4 6L)
+
n
which leaves at most potential indices for which (hx(1) (1) A/ > { 6kC(1+L), the indices
(X) and the index i", Therefore, L' < Similarly, 5 L' + 1.
For (ii), note that from inequalities (A.49) and (A.50). we have (ix(1) - A', - (h(1) A, < 4
for of i Recalling the definition this implies that the difference between the weights on an index i can never be greater than
Finally, note that the weight wt(() differs by e. Say wS') large we will set (a) wt(aa + c and take some other b and set wt'(b) (b) = wt(b)
subset S, wT(() minss wt(i). Now, by inequality (A.47), each arg min wt(i). In order to make the difference between wt(S) and
such that wt' (b) < (a). But then, wt(a) I wt(b)= S wt(a) 2c. This completes the proof of inequality (A.48).
Next, we show that the weighted Hájek variants (()) are close to the empirical mean A, and have low sensitivity.
Lemma A.13. For all indices we have (0) - Anl S E + 9KCL + have
GGC. ar
Moreover, if + i", we
(()(1) A.) (g. A/ S g+ kC(14 6L)
10kC
4k2C (1 (1+22).
n
n²
Proof. If wt([) = 0, then s(xs) An for all S and g(i) An. For clarity, we add picture of this weighting scheme here: Otherwise, we write
(()) A, M,
Σ (M(Xs) A,))w(()
SES.
1 Σ (h(Xs) An) wi(l) +
Σ (h(Xs) An) (wt(S) wt(i))
M, SES.
M; SES,
1 M,
-hh(i) A.))t(()
Σ (h(Xs) And (w((S) wt()))
(A.52)
SES.
From equation 14 and the assumption that the weight of index i is strictly positive, the magnitude of the first term in equation (.52) is bounded by & + GkCL 6kC For the second term, note
29

---

that wt(S) wt(i) unless an index j with lower weight than exists. Note that such an index j is necessarily Bad(X) (X). Therefore, the absolute value of the second term bounded above by mi E (xB C 2KCL This proves the first part of the lemma.
To bound the sensitivity (t). by the triangle inequality, we have
(1(1)) An)wt(i) (hv (1) A,,) (,))((())
< (1))) - An (w((i) wt (i) + (h(1) - A..) - (h) - -1h)) wi(
S + &C (4+ +6L)
+ 6kC
6kC
c e n
11.
me
&C (10+ + 6L) +6))
6kC
+
e n
(A.53)
n
where the argument for the second inequality is as follows: To bound the first term, note that when wt(i) (i) it is zero. If wt(i) > 0, then (h(i) Anl S E G&CL GRCL Now, if (i) - Aml > 5 + G&CL + G&CL
n
ne
+ 1kC then wt(i) = 0, and by inequality (A.46) of Lemma A. 12
we see that (i) A E + GRCL 6&CL so wt' will also be zero. The second term is ne
bounded directly by Lemma A.12 Overall, we arrive at a bound on the sensitivity of the first term in
equation (A.52..
For the sensitivity of the second term of equation (A.52), note that if i has minimum weight among the indices in SS, then wt(5) wt(i). Otherwise, some indx S has strictly lower weight than i. Such an index j is necessarily in Bad (X) U (xd(X') because it has weight less than 1. If S also does
not contain the index i", then (Xxs) h(X's), so by Lemma A.12 we have
2kC
1(h(X() - A,, (h(Xs) An) S |An A s
((wi(S)) wi) -(wt(S) wt(1)) s 2e,
and letting
Ts: = ((h(Xs) An) (wi(S) - wi(i)) - (b(x's) - A',) -w(((s))(((())) (i)))
have [Ts] $ 2&C + 2Ccc.
Moreover, there are at most Mas- sets containing both and i", and for each such set S, the change in (h(Xs) - A,) (wt(S)- wt(i)) is at most 2C, since the weights lie in [0, 1] and (X(s) - A, <
C. Combining these bounds, we obtain
1 M
Σ SES.
((h(s)) An) (wt(S) w((i) (h(X') A%d (w) wt (i))
Σ
[Ts| (Bad U Bad (a)() >0] +
Σ [Tsl
M,
(S,,
SES.
2kC
2Cc +
1(SS n (Bad U (ad( 0)
Σ 20
n
Mi
M, SES,
SES
20e + 2hC
1
+ 20 Me,
Σ
Σ
n
M
Mi
jEBad(X) (uad X SES.
2kC
Myj
M
20c +
([Bad(X) + BBa (x)
sup ((BBi(X)
+ 2C
n
Mi
M4
2k:
2C' + 2kC' (1 + 2L) + 4kC
(A.54)
n
where the first inequality uses the fact that the weights are all equal if S (Ba((X) U Bad (')) = 0. and the last inequality uses Lemma A.11 Combining inequalities (A.53) and (A.54) into equa- tion A.52 yields the result.
30

---

To bound the term 7i in A..45 we decompose it as
min(k, BD
- T-EY E (o(Xs) 9(x)))
Σ
Σ SES
(a (a- (1-1) (A.55)
ZEB SES, ES
|s
The first term counting every subset with a elements in common with B exactly 1 times. The second term corrects for this over-counting, akin an inclusion-exclusion argument. The following lemmas bound each of the two terms: Lemma A.14. For all E B, we huve
over all subsets that contain some element in B. However, this leads to
1 M
Σ
(o(Xs) 9(('))) $ +
20kCL
12kC
14 n2
n
ES
Proof. We have
(g(Xs) 9(X'))) M, (0(1) 0(1))
E (o(Xs) g(X)))
(A.56)
SES,
SES.
2" F
By Lemmas A.12
and A.13 have
4C111++61
12kC
(Ø(i) g(i)
E +
E
+
n2
(1 2L).
Moreover, the second term in equation (A.56) is clearly upper-bounded by
4kC
8k2C
2CM,, I
M, <
M,.
n²
Summing these two bounds yields the result.
For the second term of equation A.55 we use the following lemma: Lemma A.15. have
(in(ke.
36221?
64C min 2L)M.
Σ
(a 9(X's) -
220c+
n²
SES
|sn
Moreover, S = In with m (x), we have the stronger inequality
mi)(k,|B)
9
6kC
Σ
(a - o(X'sss
220c +
n²
n
SES
|S **$S
Proof. For any S not containing i", we have
1o(Xs) - g(X (X5s) = ((h(Xs) An)wt((S) + An - (1(X)) Ar) A'1 ((h(ss) - h(xx))) + IA, - -A,1 < ((((s) - (wt(w( wt((s))
< 2Ce + 6kC
using Lemma A.12 and the fact that the second term is zero. Moreover, we have
mil(k.|Bl)
Σ
Σ (a-1)<
min(k,|B)
Σ
min(k, (B])
SES
o=2
SES
SES |snB|22
ShB 1" g.
|
962
Σ
Σ
min(k, [B]) min (k:, [B|) Bl3m.
n
i.jBB SES igf
31

---

The last inequality follows from Lemma A.11
which implies that
My M
0
k2 n2
In the case when S = In, .sr we have
min(k,1B
min(A.1B)
Σ
Σ
Σ
(a
1)
[B8)
|B8 (n-1B)
n
k
4=2
SES |Sn 1" ES
a=2
B|
n
B
1
+
k
12
B|
n2
[B]
+
1
k
1
B|
1-2 B|| n2
+
k)
R|B
n2 k
where the first equality used the identities Σ (*) (m-a)
mn and Σ a (w) (=ma)
&
ak ("t"), and the third inequality used the fact that (1 x²)* S
1
for all E [0, 1.. The
m+n
1+ke
statement in the lemma follows because [B] < 2L + < 3L.
Combining the results of Lemma A.14 and A. A.13 yields Lemma A.16
Lemma A.16. We have
kM
((s+ 20ACL
24kC
C8 9kL² 2C
6kC
)
T
2E +
+
11
n
n²
n
where y = 4 mmink: 2L). IfS=== = Kn then the bound also holds for y = 1.
It remains to bound the third term, T3. of equation A.45
which we do in the following lemma:
Lemma A.17. We have
2k n
kC(11 18L)
12kC
T3l
S
2
M.
n
ne
Proof. Using Lemmas
1.12 and A.13
we have
1 M
I3' = 10()") - 9. (in) S 15(1")
A.l + 1 - A,,
+ A,, A
9kCL
+ 64C
+ E 9kCI/
6kC
2kC
$ g +
ne
AC(11
18L)
12kC
S 25 +
The lemma follows after using the fact that M,- <
2h M.
Combining the bounds Ti and T3 from Lemmas A.16 and A.17 in equation (A.45). sensitivity of An, at X is then bounded as
the local
LS A, (X) = o k ( &CL (1 (1+ + C²CL² min(k, L)
(
kC
R2C n
E
n²
Let g(E, L, n) denote the upper bound, where simplify the following argument, we assume the constant prefactor is 1, i.e..
g(C, I, n) = k / n
(1+ (s+kC))(+)))
(CT.)
12CT2 min(k: L.)
(ct k: m) +
k²C
n
n n²e
Note that g is strictly increasing in L. Also define
S(X)=
max
"( Tix + l.
(A.57)
EEZ20
32

---

Lemma A.18. The function S(X) is an e-smooth upper bound on LS An (X).
S(X) =0 k (s+
+C(1/e+ L) (1 (1++1)+ 12C(1/e+ L)² min(k (k, 1/e + L)
( (6+ k 1²O
n
n²
n²c
Proof of Lemma Clearly, we have S(X) 2 g(5, Lx. n) 2 AS (X), and for any two adjacent X and X', we have
S(X')
max at 9(5, Lx +., - max 20
el g(5. Lx + + + 1.
1E
(t- + L, S
max e " g(E, Lx L, = e SXX). tEžgo
max
EE
This shows that S is indeed a e-smooth upper bound on the local sensitivity. As for the upper bound on S, for any 8 2 O, we have
of 9(s, Lx + (,n) = k
fe (E--1//2 + kClle e/2 + Le Le)2))
(e
(6-d/2 + Eelee 11/2 + LE LE(2)))
e(le-1112
2²
h
Ce
Clee- + Le Le/333 min(kii-ea 4// 10000/111 + Le 10/3)
c+
+
n²
n
n²c
k
( (C((//++)) {+
(
k2
2
12
(1 (1+ ((+
C + L n²
min
k; - - L
+
+
n
niee
where we used multiple places the inequalities e = and
Le fjo S c/e, for any c > 0.
By Lemma A.18 it is clear that the term S(X) added to A, in Algorithm is the smoothed sensitivity defined in equation (A.57).
Therefore, + 1 S(X), Z, where Z is sampled from the distribution with density h(z) 1/(1 1/(1+1=/*), (()) Jdifferrerett private, by Lemma 2] Moreover, if S In,,, the above bound on the smooth sensitivity holds without the min(k; 1/c + L.) term, due Lemma A.15
Utility. By Chebyshev's inequality, we have
AA, - 01 S Vyy
Var(An) VY
(Var(Un) +
Ck
m
with probability at least 1 - Moreover, with probability at least - each of the Hajek projections is within & of A,. This implies that every index has weight 1, which further implies that g(Xs) h(Xg) for all E S, and consequently, An = An. Also,
for such an X. Finally, with probability at least 1 7, we have Z < Combining these inequalities and using
Lemma A.18 we have
[A(X) 01
An
An
+ +An -1 (8(X)\c Z
VT ( Var(UU.) +
CK
kg
K²C n2e2
KaC n
+
+
ki
(A.58)
m
ne
with probability at least 47, recalling that = ((1) when simplifying the expression. Algorithm I uses constant failure probability y 0.01, which ensures a success probability of at least 0.75. This is further boosted by Wrapper]] Now, an application of Lemma A.ol the stated result.
A.5.2 Proof of Theorem
The proof of this theorem proceeds nearly identically to that of Theorem with some exceptions. If = I,,kk the smoothed sensitivity bound has no min(k; 1/e) term, owing to Lemmas A. A.
which gives the bound
1 - (O(VVan (Vaa(( (n)( -1- v7
KE 1PC n²2²
1OC n
-1
+
+
(A.59)
ne
Furthermore, since S = In.k. we have A,, = Un with probability at least 3y. Algorithm 1 uses constant failure probability of = 0.01. This ensures success probability at least 0.75, which further boosted by Wrapper [
An application of Lemma A.6 gives the stated result.
33

---

A.5.3 Concentration of local Häjek projections
Proof of Lemma S
We first show that if Y1, 2..... ... Y are random variables such that each Y, is
Ty-sub-Gaussaan, the sum Yi + ... + Yt is (VTI + VT2 + ......... ++) " -sbb-Gaussian.
Define Pj- = Ei vT5
Clearly, we have Σj=1 1/pj 1. By Hölder's inequality, for any À > 0, we
have
A²p7T
1/pi
IE
exp
E
exp(AX;)
<
E (exp(AV.)
exp
i=1
i==1
APPpTi 2
12
72
vTT)
exp
= exp
2
Now, h(Xs) is sub-Gaussian({ for all S E InA Since h(i) is the average of t (x=1) such quantities, is clear from the previous claim that (1) sub- Ga-Gaussiin with parameter
V VT2² =T.
terms
Proof of Lemma 4 Define of = Var (M(X)s)) =;)). First, conditioned on X,, the projection (i) can be viewed as U-statistic on the other data points. First, for this lemma, we use
S = In,kk and
h(1) - (M(xs) Eses, h(Xs)
Since is bounded, the random quantity h(i) (X) X, [-20, satisfies the Bernstein
moment condition and also the Bernstein tail inequality (cf. Proposition 2.3 in [60). By Bernstein's inequality for U-statistics (see inequality (A.29)) for all t 0, we have
( (XX)s 2 1 xxx.) s 2exp (h(0 -
20 + 401/3
which is at most 8/n as long as = o.v log
2n
+
SCK
log
2n
A.6 Applications
A.6.1
Uniformity testing
To motivate the test, consider the expectation 0 = E[h(X, X,)) and the variance var
Lemma A.19. We have E[ X2)]
In particular, the means under the two hypothesis |a
classes differ by at least
8²
Zm
Proof. We have
m
m
20; +
a²
|all
Blh(X,, X2)l
Σ
p
m2
70
m2
i=1
Under approximate uniformity, this is most and under the alternative hypothesis, this quantity at least 8a
8a
34

---

Lemma A.20. The variance of Un is
2
2 var(Un) nan-11 -1 2(n - 2) Σ
m
m2
Pipy(pi - PD))
Σ
pr
>
ps
i<j
Proof. The conditional variances Ç1 and (2 can be written as
<i = E[ x2] = Xs]] [ = [ = Xz]]
Σ p
Σ ps
Σ
(1ips + p.P
2p(p3) = Σ
Pip;(Pi - PD;)² 2 0, and
isj
2 = cov cww.oooohhaccoc (h(X,, h(X,, X²)) = Σ
ps
P
Aml
Also from equation have
-1 (2(n 2) + C2).
var(U,,) =
2
Combining the above bounds with equation
3 shows the result.
Algorithm A.4 PrivateUniffrrmityyeee n, m. X (Xilien) .c)
I: C c 1, + 0.01
2: { < 6/m (oggoo4/n////
3: S ((i,g) Siiij S m
4: 8 PrivateMeanHajeeiin
(1(x:=x))((0))) C),
5: if > 1+36"/4 then
6: DEC t m
(Reject approximate uniformity)
7: else
8: DEC <- (Accept approximate uniformity)
9: end if
10: return DEC
Proof of Theorem Recall that Ô denotes the private test statistic, which is thresholded the value 1+368/4 to determine the output of the hypothesis test. We claim that the validity of the test is established we can show that
82
TP [0-
1-
2 1
(A.60)
4m
under both hypotheses. Indeed, it would then hold that:
Under approximate uniformity,
52
82
1 35 /4
2m
4m
m
(ii Under the alternative hypothesis,
1
52
82
1 + 362/4
02
m
m
4m
m
To establish inequality A.60)
we further write
8²
8²
82
00 EUU,]
<
10
Unl
+
1Un - E[Um]
(A.61)
4m
8m
8m
35

---

can be bounded as The second term can be controlled using argument in Diakonikolas et al. [21], which further develops the variance bound in Lemma A.20foo. the two hypothesis classes and then uses Chebyshev's inequality. It is shown that the second probability term in inequality (A.61 can be bounded by if 7
V
7-2
To bound the first probability term in inequality (A.6I), study the concentration parameter & for the local Hájek projection h(t) - Ejzi (X,,, X2). We have the following result:
Lemma A.21. f m n
blog(4n/7) and 7, then ((())) Unl for all i, with probubility
least -.-
Proof. By the triangle inequality, we have
(i) U, - (1) (l,(X1, X2) X1] + [X, X2) 01 IU 8). (A.62)
We will provide bound each of these three terms. Note that
[2) ~ Bern(px,),
which has variance
of var(h X,) = px, px,)
m
Hence, with probability at least
3. the first term in inequality (A.62)
4n
16
4n
2
7
4n
(i) E[L(X,, s X2)
2/ mn
log
log
log
3n
m
n
where we have used the AM-GM inequality. The second term in inequality (A.62)
can be bounded as
+ ax, ( + m )
||a||"
||a||
- ax; m
+
S
m
m
m
Finally, by Chebyshev's inequality, the third term can be bounded probability at least 1 - 3. It remains to find the variance of Un.
Un, 01 s
Uv.
with
By Lemma A.20 if |a:l I 1 for all i, we have
2
a:) (1+a;)(1
(1+ +
+ aaj) - -a,)²
(1 + a;)²
(1 + a;)² m
var(Un)
2(n 2)
n2n2-
1)
m
m²
2
2(n - 2)
Σ
(1 a1) + +0;) (a) - -a,3
(1 + a;)2
n(n - 1)
m
m2
K
4
m
4m
8
8
2(n 2)
+
(A.63)
n 1)
m
2
2
mn?
Combining the three bounds into inequality (A.62).
with probability at least 1 we have
4n
2
V2
2/2
2v2
(()) Unl <
+ log
+
+
m
V
myn
/mn
4
7 7log 4n/y)
4/V7
4/v7
m
n
myn
n
Vmn
8log(4n/7)
m
n
where in the second inequality, we used the AM-GM inequality and the assumption statement of the lemma follows after discarding lower-order terms.
> 16 The
7.
0
36

---

By Lemma A.21 with probability at least 1 7, the weights of all projections in Algorithm are equal to 1 and Un An. Then 1 Un| is simply the magnitude of the noise added in the final step of Algorithm D (which uses a constant 7 = 0.01), which (ef. the proof of Theorem 2 takes the form
(
5 +
log n
1
0
+
+
n²e2
n²e3
n²eE
n²e2
with probability at least 0.75. This is bounded by
6² 8m
as long as
= Ω ( m/2
mm//2 8el/2
m/2
m 1/3
log
de1/2
de
82/3E
Wrapper further boosts this constant probability of success. Now, an application Lemma A.6 gives the stated result.
A.6.2 Sparse graph statisties
Algorithm A.5 PrivateNetwworEddggn, m, (At (Ai)ssissnn))
1: C 1, 7 0.01
2: Un + (5)
Ei<j40 Ai
3: 2² +- Un 1 2, where a standard Laplace random variable
4: if < then
5: return
6: end if
7: { 24v, "
log
2n log +
V7
8: S - ((i.j) S Iiijj
9: 8 Private (1(A,) E),
return 0
A.6.3 Proof of Theorem 6
The privacy the algorithm follows by composing (see Lemma A.4) the e-privacy of and the O(c)-arivacy conditioned on v. remains show the utility of the algorithm.
The kernel ((x, 3) = 1[1 y/ r.,) is degenerate, since P(J xx- S r does not depend on X,. So var( EE[((,,, (X,, X, x)) = We have var var[h((e (x,, X,) S T.? so the non-private error is (rn/n)) (Eq 3). Using Proposition 2.3 from Arcones and Gine (5). there exist universal constants ei, c2, and c3 such that
n (Un - 2t) S exp (- CsTn + fonn+tt/n/// (t/n) 2
C2t
P
Setting & = n/r//1., 16, we have, for large enough n, since Tn = 1112),
P P(U,, - ( / S ci exp
Canr2
ci ccceppl-cle cxpep((-'nr(/3 Ô (exp(-nl/3)).
CaTn + 2/3
Therefore, with probability 1 - o(1), we have
U, E
2² = Un + Z/ne E r/22)
(A.64)
In particular, the probability that U, + computed in step of Algorithm A.5 then positive.
From Lemma 4 we have
(() (2)((1 211/ s 40y
2n
16
2n
log
+
log
(A.65)
3n
?
37

---

with probability at least - where of = Var Xh), x1) S m.
Thus, from Eq A.64
that:
0 S T S 9TV2
Moreover, since g is degenerate, we have , = On. Using the fact that IU, - 0nl S (Var(U...)
5rn I with probability at least 1 O(7), we have
max (i) - Unl I max (()) 8n + 6n Unl
2n
16
2n
5r
T
40:
log
log
11
3n
71
2n
16
2n
15v
$ 24
log
log
E,
3n
with probability 1 O(7). Hence, using Theorem that the estimate 0 output by Algorithm
and noting that Ō
we can ensure
satisfies
kg
h:2
0 0 =
Var(Unn)
+
+
+
C
ng
I'
E
I'
In
1
=0
na
+ c
n2ee2
2
n
=
aa
+
aa
3/2
+
n
+
n
m
with probability at least 0.75. Wrapper[] further boosts this probability of success from constant to 1 a. Now, an application Lemma A.6 gives the stated result.
A.6.4 Other applications
In this section, we provide more applications of U statistics for important hypothesis testing problems.
1. Goodness-of-ft testing: The Cramer- Von Mises statistic for testing the hypothesis that the cumulative distribution function of a random variable is equal to a function Fo is given by
ΣΣ / (b())) (1{X, x} Fo(x)) dFo(x).
Under the null Ho : X Fo, the distribution of the statistic is degenerate [58). Thus, our techniques from Section 4.2 provide method for private goodness-of-fit testing based the Cramer- Von Mises statistic. Private goodness-of-ftt testing has so far mostly been studied in the setting of discrete 2. For continuous distributions,
data 28
only aware of work that analyzes the local DP 12]. which is therefore not directly comparable to our proposed approach.
framework 23
2. Pearson's 's chi-squared test: The chi- chi-squared goodness of fit test is widely used to test if a discrete random variable comes from a given distribution. The corresponding statistic (which can be written as U statistic plus smaller order term) is degenerate 20
Symmetry testing: Testing the symmetry the underlying distribution of i.i.d. Xj...., X,, is
often used in paired tests. (26) use the test statistic (,, - X,) g(X; + x,))/n2 (which a U statistic plus lower-order term), where is the characteristic function of some distribution symmetric around 0. When the distribution of X; is symmetric, this degenerate.
38

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
We have assured that the abstract and introduction accurately reflect our contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have acknowledged any limitations of our work in the paper and in the discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
39

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We have provided proofs for all theoretical results in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced
statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
40

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7/
gewss CCodeSoodieeeeeee ssi mollicyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
41

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma eгrоr bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
42

---

Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics http://ssspppppp.p.caaaaaa///eea
Question:
Answer: [Yes]
Justification: Yes, followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents theoretical work whose goal is to advance the field of differential privacy and statistics. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
43

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, pappessii thcode. www.com//a/oo/oc datasat has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "ra4UMKf4MF", "reviewer": "Reviewer_vFH3", "summary": "This paper studies differentially private estimation of U-statistics (estimators for such statistics are averages of functions $h$ that depend on a number of i.i.d. samples $X_1,\\dots,X_k$). This is a generalization of the commonly studied mean estimation problem where $k=1$ and such estimators with $k>1$ are widely applied across statistics. The authors are primarily interested in cases where $h$ is a subgaussian kernel i.e. the distribution of $h(X^k)$ is subgaussian or cases where the range of $h$ is bounded (and satisfies a certain degeneracy property).\n\nThe main contributions of the paper are as follows:\n1) They first consider approaches that reduce differentially private U-statistics to differentially private mean estimation and argue that natural approaches result in estimators that are either suboptimal in either the non-private error terms or the private error-terms. The estimators they consider are a naive estimator that reduces to the i.i.d. case by computing the function $h$ on a partition of the dataset before applying a subgaussian mean estimation algorithm on the resulting sample of function values, and a more complicated estimator that generalizes the CoinPress algorithm to work with weakly dependent samples. The former has suboptimal non-private error while the latter has a suboptimal privacy term (the dependence on $k$ is suboptimal).\n\n2) They then consider a different strategy inspired by work on privately estimating the sampling probability for Erdos-Renyi graphs. This strategy exploits the concentration of the 'local Hajek projections' around the true mean.  The idea is to classify coordinates into good and bad coordinates respectively based on how close their projections are to the optimal non-private statistic, and reduce the local sensitivity of the average being computed by reducing the influence of bad coordinates by reducing the weight of the corresponding terms in the average. They can then compute an appropriate smooth upper bound to the local sensitivity of this average and add less noise. They use this idea to obtain a general result for bounded kernels, and then use it to get the optimal rate for subgaussian-nondegenerate kernels, and a bound for general degenerate bounded kernels. They also provide some indication that their bound for general degenerate bounded kernels may be optimal.\n\n3) They also show that their results can be used to privatize 'subsampled' estimators with similar error rates that are computationally much more efficient. Finally, they apply these results to settings where U statistics are used such as various hypothesis testing problems.", "questions": "In equation A.41/42 is S missing from the subscript? Also what is j here? Do you mean $i^*$?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) U-statistics are widely used across statistical testing and estimation, and have been relatively understudied in the privacy literature. This paper explores them quite generally and does a good job of suggesting problems for future work.\n\n2) They do a good job of explaining how natural extensions of traditional DP mean estimators perform sub-optimally in estimating U-statistics.\n\n3) The estimator based on local Hajek projections (and smooth sensitivity) seems quite technically novel and interesting.", "weaknesses": "1) In the applications section, it would be good to discuss existing private algorithms for the corresponding tasks (if there are any) and compare the bounds that are obtained.\n\n2) In the Hajek projection algorithm, it would be nice if they explained how they build on the techniques from [Ullman Sealfon NeurIPS 2019]- which parts are borrowed from that work and which parts are new.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and for noting that our estimator based on local Hájek projections (and smooth sensitivity) is technically novel and interesting.\n\n**[Re: Comparison of our applications with existing private algorithms]:** The setting we consider, where the probabilities of the atoms in the distribution are close to uniform, has not been considered in literature before. However, there are existing private algorithms in the more general setting, which when restricted to our setting lead to suboptimal guarantees in the privacy parameter $\\epsilon$.\n\n[2] considers the $\\ell_1$ distance between the distributions $ (p_1, p_2, \\dots, p_m)$ and the uniform distribution $(1/m, 1/m, \\dots, 1/m)$ on a set of $m$ atoms. Our assumption of $\\sum_i(p_i-1/m)^2\\leq \\delta^2/m$ implies a bound of $\\delta/2$ on the $\\ell_1$-distance considered in [2]. The collision-based statistic we consider is simpler than that in [2]. While they consider a broader class of probability distributions over the atoms, their sample complexity $O\\left(\\frac{\\sqrt{m}}{\\delta^2} + \\frac{\\sqrt{m\\log m}}{\\delta^{3/2}\\epsilon} \\right )$ has a worse factor in $\\delta$ compared the sample complexity $O\\left( \\frac{\\sqrt{m}}{\\delta^2} + \\frac{\\sqrt{m}}{\\delta \\epsilon} + \\frac{\\sqrt{m} \\log(m/\\delta \\epsilon)}{\\delta \\epsilon^{1/2}} \\right)$ of our algorithm. We will incorporate this into the revision and elaborate on the comparison. \n\n**[Re: Connection between [1] and our algorithm]:** We will more clearly describe the connection of our algorithm with the algorithm of [1]. \n\nA key idea in this work is to exploit the concentration of the degrees of Erdős-Renyi graphs, and we generalize this idea to the broader setting of U-statistics as follows. Consider a $k$-uniform complete hypergraph with $n$ nodes (and ${n\\choose k}$ edges), where the nodes are the data indices. An edge corresponds to a $k$-tuple of data points $S\\in I_{n,k}$, where $I_{n,k}$ is the family of all $k$-element subsets of $[n]$, and the weight of this edge is $h(X_S)$.  The local Hájek projection $\\frac{1}{\\binom{n-1}{k-1}} \\sum_{i \\in S} h(X_S)$ is simply the degree normalized by ${n-1\\choose k-1}$.\n\nOur algorithm uses the property of local Hájek projections to re-weight the hyperedges ($k$-tuples) such that the local sensitivity of the re-weighted U-statistic is small.  In degenerate cases and in cases where $ \\zeta_1 \\ll \\zeta_k/k$, where $\\zeta_1 = \\textup{var}(\\mathbb{E}[h(X_1, X_2, \\dots, X_k)|X_1])$ is the variance of the conditional expectation and $\\zeta_k = \\textup{var}(h(X_1,X_2, \\dots, X_k))$, similar to the Erdős-Renyi case, the local Hájek projections concentrate tightly around the mean $\\theta$, leading to a near-optimal error guarantee. It turns out that even when the U statistic is non-degenerate and the Hájek projections do not concentrate as strongly, our algorithm (Algorithm 1) achieves near-optimal private error guarantees. Algorithm 1 also works with subsampled family $\\mathcal{S} \\subseteq I_{n,k}$, where the size of $\\mathcal{S}$ can be as small as $\\tilde{O}(n^2/k^2)$. This allows for a computationally efficient algorithm for all $n$ and $k$.\n\n**[Re: Typographical error in Eq A.41/A.42]:** Yes, the index $j$ should be $i^*$. In equation A.41, we are summing over $S$ such that $S \\in \\mathcal{S}_{i, i^*}$. We will correct this and other typographical errors in the final version.\n\n[1] J. Ullman and A. Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32, 2019.\n\n[2] J. Acharya, S. Ziteng, and H. Zhang. “Differentially private testing of identity and closeness of discrete distributions.” Advances in Neural Information Processing Systems 31 (2018).", "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": "", "extra_scores": {}}, {"review_id": "490HNDim2b", "reviewer": "Reviewer_MPw8", "summary": "This paper introduces a new algorithm for constructing U-statistics under central DP. Compared to the naive method, the proposed estimator exhibits lower variance. The authors also derive a lower bound for private algorithms. Several statistical applications are presented to illustrate the methodology.", "questions": "1. Could the authors consider refining the computation of the privacy budget? Specifically, users may prefer a $\\epsilon$-DP method over an $\\mathcal{O}(\\epsilon)$-DP method.\n\n2. Following the first point, could the authors discuss the performance of the proposed method across different values of $\\epsilon$?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "U-statistics are widely applied in statistical inference. The improvements in private estimation presented in this paper are useful, and the theoretical results are solid.", "weaknesses": "The calculation of the privacy budget lacks precision.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**[Re: Privacy budget]:** Lemma 3 (line 130) shows that the CoinPress algorithm from [2], adapted to the all-tuples family, is $2\\epsilon$-DP. The following argument shows that Algorithm 2 is $10\\epsilon$-DP as stated. Corollary 2.4 in [1] shows that for any function $f:\\mathcal{X} \\to \\mathbb{R}$, the output $f(X) + \\frac{2(\\eta+1)S(X)}{\\epsilon} Z$, where $Z$ is sampled from the distribution with density $\\propto \\frac{1}{1+|z|^\\eta}$ and $S(X)$ is a $\\beta$ smooth upper bound on the local sensitivity $LS(X)$ of $f$, is $\\epsilon$-DP as long as $\\beta \\le \\frac{\\epsilon}{2(1+\\eta)}$ and $\\eta>1$.\n\nThus, as stated with $\\eta=4$, Algorithm 1 (Theorem 2, line 196), is $10\\epsilon$-DP. We chose $\\eta = 4$ somewhat arbitrarily, and we can improve this to almost $4\\epsilon$-DP by choosing $\\eta$ arbitrarily close to $1$.\n\nCorollary 1 (line 209) follows by composing our extension of the algorithm from [2] and our main algorithm. Passing in $\\epsilon/2$ to Algorithm A.2. with $\\mathcal{S} = \\mathcal{I}_{n,k}$ and $\\epsilon/20$ (which can be improved to $\\epsilon/8$ from the discussion above) to our main algorithm results in an $\\epsilon$-DP algorithm for non-degenerate, subgaussian kernels.\n\n**[Re: Performance across different $\\epsilon$]:** We assume $\\epsilon=O(1)$. But the dependence of the private error of our algorithm on $\\epsilon$ nearly matches our lower bound for both degenerate and non-degenerate settings. See Table 1 (page 4).\n\n[1] K. Nissim, S. Raskhodnikova, and A. Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC '07). Association for Computing Machinery, New York, NY, USA, 75–84.\n\n[2] S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33:14475–14485, 2020.", "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": "", "extra_scores": {}}, {"review_id": "7PeC6S6ZhW", "reviewer": "Reviewer_8Ha8", "summary": "The paper addresses the problem of private estimation of U-statistics. The authors propose a new thresholding-based approach using local Hájek projections to achieve nearly optimal private error in both non-degenerate and degenerate settings.", "questions": "1. What is the asymptotic results of the private U-statistics?\n2. How do you ensure get DP estimators for the variance when doing inference?", "limitations": "1. The paper should discuss the differences and potential advantages of the proposed method compared to directly adding noise to the estimators.\n2. The authors should include asymptotic normality results for the DP estimators, similar to those available for non-private U-statistics.\n3. The paper would benefit significantly from experiments that validate the theoretical findings and demonstrate the practical applicability of the proposed methods.\n4. The author should specify the dimension of $X$ and discuss its impact on the results.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper provides solid theoretical foundations, including lower bounds for the private error and theoretical guarantees for the proposed algorithm.\n2. The proposed method is applicable to a wide range of U-statistics problems, from hypothesis testing to subgraph counting in random geometric graphs.\n3. The method aims to provide private confidence intervals for U-statistics, addressing a gap in existing literature.", "weaknesses": "1. The paper is difficult to read due to the heavy use of parameters and notations, many of which are not well-defined or explained, particularly in the algorithmic sections.\n2. The manuscript provides non-asymptotic results for the DP estimators, but lacks the asymptotic normality results typical for non-private version of U-statistics, which are crucial for practical applications. I think the asymptotic variance of the private U-statistics will change compared to the non-private version. More discussion on expected on this difference. \n3. To provide private confidence intervals, the variance should also be estimated privately. This aspect is not thoroughly discussed, making the testing problem in Section 5 less meaningful.\n4. There are no experimental results to demonstrate the practical performance of the proposed algorithms, which is a significant omission.\n5. The paper only consider the 1-dimensional data $X$ throughout the paper. A general discussion of d-dimensional vector are needed because it may suffer from the curse of dimensionality, which will affect the generalizability of the results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your kind words regarding the solid theoretical foundations and wide applicability of our work.\n\n**[Re: Asymptotic distribution]:** To our knowledge, differential privacy results typically focus on finite sample guarantees. \n\n_We show under mild conditions on $n,k,$ and $\\epsilon$ that our estimator has the same asymptotic distribution as the non-private U statistic in the degenerate (of order $1$) and non-degenerate cases. Thus, the asymptotic variance doesn’t change._ \n\nFor simplicity, let $k=O(1)$ and $\\mathcal{S}=I_{n,k}$, the set of all size $k$ subsets of $[n]$. Consider a scaling factor $c_n$, set to $n$ ($\\sqrt{n}$) for degenerate (non-degenerate) kernels. Recall that our estimator $\\mathcal{A}(X)=\\tilde{A}_n+S(X)/\\epsilon Z$, where $Z$ has density $f(z)\\propto 1/(1+z^4)$. We have,\n$$c_n(\\mathcal{A}(X)-\\theta)=c_n(\\tilde{A}_n-A_n)+c_n(A_n-\\theta)+c_n \\frac{S(X)}{\\epsilon} Z.$$\n\nFor $\\mathcal{S}=I_{n,k}$, $A_n=U_n$ and hence $c_n(A_n-\\theta)$ converges to either a Gaussian ($h$ is non-degenerate, $c_n=\\sqrt{n}$) or weighted sum of centered Chi-squared distributions ($h$ is degenerate, $c_n=n$). We show that for any choice of $c_n$, the second term is $o_P(1)$. Define $\\mathcal{E}_1=\\{\\exists i: |\\hat{h}(i)-\\theta|\\geq C_1\\sqrt{k/n}\\log(n/\\alpha)\\}$ and $\\mathcal{E}_2=\\{|A_n-\\theta|\\geq C_1\\sqrt{k/n}\\log(n/\\alpha)\\}$.\nBy Lemmas A.21 (line 854) and A.3 (line 494), $P(c_n|\\tilde{A}_n-A_n|\\geq t)\\leq P(\\tilde{A}_n\\neq A_n)\\leq P(\\mathcal{E}_1)+P(\\mathcal{E}_2)\\leq 2\\alpha$. \n\nFor non-degenerate subgaussian kernels, $h$ is truncated using one-half of the data. So the same argument as in lines 201-208 shows that the probability that none of the $h(X_S)$ is truncated is at most $\\alpha$. For finite-sample guarantees, we take $\\alpha$ as a constant and then boost it via median-of-means. For distributional convergence, we take $\\alpha=n^{-c}, c>0$. Thus the first term is $o_P(1)$. Finally, conditioned on $\\mathcal{E}_1\\cap\\mathcal{E}_2$, $L=1$ for $\\xi=\\tilde{O}(\\sqrt{k/n})$ (Lemma A.21, line 854) in the degenerate case and $\\xi=\\tilde{O}(\\sqrt{k\\tau})$ (Lemma A.22, line 863) in the non-degenerate case. Some calculations show that as long as $\\frac{k^3}{n\\epsilon^2}=o(1)$, $c_n S(X)/\\epsilon =o_P(1)$. Since $Z = O_P(1)$, the third term is also $o_P(1)$.\n\nOverall, $|c_n(\\mathcal{A}(X)-\\theta) - c_n(A_n-\\theta)| = o_P(1)$, establishing that the asymptotic distributions of the private and non-private estimates are the same.\n\n**[Re: Private confidence intervals]:** Our goal is not to provide a confidence interval but finite sample error guarantees. If desired, the variance of a U-statistic could be computed using our method since it also involves a U-statistic of degree $2k-1$. However, our algorithms require an upper bound on the ratio between $\\tau$ and the $\\zeta_k = \\textup{var}(h(X_S))$, similar to the state-of-the-art algorithms for private mean estimation [1,2]. Lemma A.7 (lines 588-591) shows how to estimate the variance $\\zeta_k$ within a multiplicative factor. We will discuss this in more detail.\n\n**[Re: Dimension]:** First, we do not require $X_i$ to be scalars; rather, $h(X_S)$ is assumed to be a scalar. In fact, for our application to sparse graphs, $X_i$ are latent vectors in $\\mathbb{R}^d$ (lines 301-304). \n\n_In fact, our techniques easily generalize when $h(X_S)\\in \\mathbb{R}^d$, as we show next._\n\nLemma 2.10 in [3] shows that if $Z\\sim N(0,I_d)$ is a $d$ dimensional Gaussian and $S(X)$ is a $\\beta$-smooth upper bound on the local sensitivity, then adding noise equal to $S(X)/\\alpha Z$ achieves $(\\epsilon,\\delta)$-DP, where $\\alpha = \\frac{\\epsilon}{5\\sqrt{2 \\log(2/\\delta)}}$ and $\\beta=\\frac{\\epsilon}{4(d+\\log(2/\\delta))}$.\n\nFor simplicity, let $\\mathcal{S} = I_{n,k}$. Consider $h(X_S)$ lying in an $\\ell_2$-ball of radius $C$. In Algorithm 1, the sets in lines 5 and 6 should be modified to have the $\\ell_2$ distance $||\\hat{h}(i)-A_n||_2$. In line 8, the weights to the indices should be based on the ($\\ell_2$) distances from the ball $\\mathbb{B}\\left(0, \\xi+4kCL/n\\right)$. Finally, the $\\epsilon$ in every step except line 15 should be replaced with $\\beta$, the $\\epsilon$ in the last step should be replaced with $\\alpha$, and $Z \\sim \\mathcal{N}(0, I_d)$.\n\nWe can show that Lemma A.20 (line 831) holds with $\\beta$ as above. With probability at least 3/4, $L = 1$ and $S(X) = O\\left(\\frac{k\\xi}{n}+\\frac{k^2Cd}{n^2\\epsilon}+\\frac{k^2Cd}{n^2\\epsilon} + \\frac{k^3Cd^2}{n^3\\epsilon^2}\\right).$ The noise added in line 15 is $S(X)/\\alpha \\cdot Z$. \n\nIn all, with constant success probability,\n$$||\\mathcal{A}(X)-\\theta||_2 \\le O\\left(\n\\sqrt{\\textup{Tr}(\\textup{Cov}(U_n))}+\\frac{k\\xi d^{1/2}}{n \\epsilon}+\\frac{k^2Cd^{3/2}}{n^2\\epsilon^{2}} + \\frac{k^3Cd^{5/2}}{n^3 \\epsilon^{3}}\\right).$$\nTo see that this is a desirable result, consider the task of mean estimation of $N(\\mu, I_d)$ random vectors with $\\tau = 1, k = 1, h(X) = X, C = O(\\sqrt{dk\\tau \\log n/\\alpha})$, (as in Corollary 1, line 209) and $\\xi = O(\\sqrt{d\\tau\\log n/\\alpha})$. Then, our algorithm achieves error\n$$||\\mathcal{A}(X)-\\theta||_2 \\le \\tilde{O}\\left(\n\\sqrt{\\frac{d}{n}} + \\frac{d}{n \\epsilon} + \\frac{d^{2}}{n^2\\epsilon^{2}} + \\frac{d^{3}}{n^3\\epsilon^{3}}\\right).$$\nThis error is at most $\\eta$ as long as $ n \\gtrsim \\frac{d}{\\eta^2} + \\frac{d}{\\eta\\epsilon},$\nnearly matching the $\\tilde{\\Omega}\\left(\\frac{d}{\\eta^2} + \\frac{d}{\\eta\\epsilon}\\right)$ lower bound (see Corollary 3.13. of [4]).\n\n[1] G. Brown, S. Hopkins, and A. Smith. \"Fast, sample-efficient, affine-invariant private mean and covariance estimation for subgaussian distributions.\" COLT 2023.\n\n[2] J. Duchi, S. Haque, and R. Kuditipudi. \"A fast algorithm for adaptive private mean estimation.\" COLT 2023.\n\n[3] K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. STOC 2007.\n\n[4] X. Liu, W. Kong, and S. Oh. \"Differential privacy and robust statistics in high dimensions.\" COLT 2022.", "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": "", "extra_scores": {}}, {"review_id": "R1Rnu9t9Df", "reviewer": "Reviewer_B5Tq", "summary": "This paper addresses the problem of estimating U statistics under central differential privacy. U statistics are established minimum variance unbiased estimators for estimable parameters in the form $\\mathbb{E} h (X_1, ..., X_k)$, where $h$ is a kernel and for all $i$ $X_i$ is i.i.d. from some underlying distribution. In other words, U statistics estimate averages of kernels applied to subsets of the data of degree (size) $k$. This type of problem arises in multiple statistical tests such as goodness-of-fit tests and Pearsons's chi-squared tests, uniformity testing, subsampling and other scenarios. While many methods have been studied for differentially private mean estimation, the research on private U statistics is in its early stage and has so far mainly focused on local differential privacy models and discrete data. This paper seeks to provide differentially private U statistics estimators achieving nearly optimal private error for both the case of non-degenerate kernels and degenerate kernels.\n\nThe main contributions of this paper are: i) it derives the lower bound for private algorithms for the non-degenerate kernel case (Theorem 1); ii) it finds that applying off-the-shelf private mean estimation procedures to U statistics estimation yields suboptimal error; iii) it proposes an algorithm that achieves nearly optimal private error in the non-degenerate kernel case, and evidence of near optimality for bounded degenerate kernels. \n\nThe proposed algorithm (Algorithm 1) is based on representing U statistics via the Hájek projection, and leverages the fact that local Hájek projections enjoy strong concentration around the conditional mean. Basically, if all local Hájek projections $\\hat h(i)$ are within a certain threshold distance from the pre-computed empirical mean $A_n$, the output $\\tilde{A}_n$ on line 14 is going to be equal to $A_n$; if not, for every subset $S$ containing a bad index, $h(S)$ is replaced by a weighted combination of $h(S)$ and $A_n$. The choice of threshold $\\xi$ ensures $L = 1$ with high probability, maintaining a balance between excluding bad data and preserving good data, while also keeping the sensitivity of the final adjusted mean $\\tilde{A}_n$ small​, which is crucial for differential privacy. A lower bound for sub-Gaussian non-degenerate kernels is provided (Corollary 1) and Algorithm 1 is proven to match this lower bound. It is also shown that Algorithm 1 matches the lower bound for bounded degenerate kernels (Corollary 2).\n\nThe paper discusses a wide range of applications of the proposed method to uniformity testing, goodness-of-fit tests, Pearson’s chi-squared tests, symmetry testing, and sparse graph statistics.", "questions": "I would ask the authors to address the minor points I mentioned in \"Weaknesses\". I don't have other questions at the moment.", "limitations": "Limitations of the proposed method are sparsely mentioned throughout the paper. As I mentioned under \"Weaknesses\", it would be preferable to add a dedicated paragraph to the limitations, even if short.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is clear, well-structured and provides rigorous derivations and proofs to back the proposed methods and claims. \n\nThe paper addresses a notable gap in current differential privacy research, which is U statistics under differential privacy. The authors derive lower bounds for both the private sub-Gaussian non-degenerate kernel case and the private bounded degenerate kernel case. These bounds support the proofs that the proposed method achieves i) near-optimality for sub-Gaussian non-degenerate kernels and ii) strong evidence of near optimality for the bounded degenerate case. These results are valuable in the context of the differential privacy research community.\n\nThe contributions are clearly highlighted.\n\nI appreciate the effort by the authors to make the results as clear as possible for the reader. In particular, the table summary of the error of different private methods in Table 1 makes it easy to understand the relative error performance of different methods at glance; similarly, in a couple of instances the authors provide key intuitions behind the proposed methods, which helps break down important technical steps that are fundamental to the proposed method. The notation is also clear and consistent.\n\nThe proposed method has wide applicability, as demonstrated in the Applications section, where the authors describe the usefulness of the method spanning multiple statistical tests and sparse graph statistics. \n\nComputational complexity and alternative computationally efficient approximations of U statistics are also discussed.\n\nExtensive proofs and supporting technical derivations are provided in Appendix, although I did not review it in detail due to time constraints.", "weaknesses": "I didn’t find any significant weaknesses in this paper. The paper is highly technical and notation-heavy, but as I described in the previous section, it still reads very clearly. A few of minor notes:\n\n- Since [53] appears to be foundational to the development of the main proposed method, it is worth dedicating a short description of it and/or specification of which ideas in [53] have been built upon.\n- Theorem 2 is not followed by a pointer to its proof in Appendix. Please reference the proof in Appendix.\n- Limitations of the proposed methods are briefly mentioned throughout the paper, but I would prefer if they were addressed separately in a short dedicated paragraph or subsection, making them more easily identifiable by a reader skimming through the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for mentioning that our work addresses a notable gap in differential privacy research and for your kind words on its wide applicability. In a revision, we will add pointers to the proofs of all theorems immediately after their statements.\n\n**[Re: Connection between [1] and our algorithm]:** We will more clearly describe the connection of our algorithm with the algorithm of [1]. A key idea in this work is to exploit the concentration of the degrees of Erdős-Renyi graphs, and we generalize this idea to the broader setting of U-statistics as follows. \nConsider a $k$-uniform complete hypergraph with $n$ nodes (and ${n\\choose k}$ edges), where the nodes are the data indices. An edge corresponds to a $k$-tuple of data points $S\\in I_{n,k}$, where $I_{n,k}$ is the family of all $k$-element subsets of $[n]$, and the weight of this edge is $h(X_S)$.  The local Hájek projection $\\frac{1}{\\binom{n-1}{k-1}} \\sum_{i \\in S} h(X_S)$ is simply the degree normalized by ${n-1\\choose k-1}$.\n\nOur algorithm uses the property of local Hájek projections to re-weight the hyperedges ($k$-tuples) such that the local sensitivity of the re-weighted U-statistic is small.  In degenerate cases and in cases where $ \\zeta_1 \\ll \\zeta_k/k$, where $\\zeta_1 = \\textup{var}(\\mathbb{E}[h(X_1, X_2, \\dots, X_k)|X_1])$ is the variance of the conditional expectation and $\\zeta_k = \\textup{var}(h(X_1,X_2, \\dots, X_k))$, similar to the Erdős-Renyi case, the local Hájek projections concentrate tightly around the mean $\\theta$, leading to a near-optimal error guarantee. It turns out that even when the U statistic is non-degenerate and the Hájek projections do not concentrate as strongly, our algorithm (Algorithm 1) achieves near-optimal private error guarantees. Algorithm 1 also works with subsampled family $\\mathcal{S} \\subseteq I_{n,k}$, where the size of $\\mathcal{S}$ can be as small as $\\tilde{O}(n^2/k^2)$. This allows for a computationally efficient algorithm for all $n$ and $k$.\n\n**[Re: Limitations]:** As per your suggestion, we will compile the limitations of our methods from different parts of the paper to one dedicated section.\n\n[1] J. Ullman and A. Sealfon. Efficiently estimating Erdos-Renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32, 2019.", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their valuable feedback and suggestions. We think we have addressed most of the questions adequately, and summarize our responses here. We will fix all typographical errors and we do not address them here.

### **Connections between [1] and our algorithm (Reviewer vFH3 and Reviewer B5Tq)**

We will more clearly describe the connection of our algorithm with the algorithm of [1] in the revision. A key idea in this work is to exploit the concentration of the degrees of Erdős-Renyi graphs, and we generalize this idea to the broader setting of U-statistics as follows. 
Consider a $k$-uniform complete hypergraph with $n$ nodes (and ${n\choose k}$ edges), where the nodes are the data indices. An edge corresponds to a $k$-tuple of data points $S\in I_{n,k}$, where $I_{n,k}$ is the family of all $k$-element subsets of $[n]$, and the weight of this edge is $h(X_S)$.  The local Hájek projection $\frac{1}{\binom{n-1}{k-1}} \sum_{i \in S} h(X_S)$ is simply the degree normalized by ${n-1\choose k-1}$.

Our algorithm uses the property of local Hájek projections to re-weight the hyperedges ($k$-tuples) such that the local sensitivity of the re-weighted U-statistic is small.  In degenerate cases and in cases where $ \zeta_1 \ll \zeta_k/k$, where $\zeta_1 = \textup{var}(\mathbb{E}[h(X_1, X_2, \dots, X_k)|X_1])$ is the variance of the conditional expectation and $\zeta_k = \textup{var}(h(X_1,X_2, \dots, X_k))$, similar to the Erdős-Renyi case, the local Hájek projections concentrate tightly around the mean $\theta$, leading to a near-optimal error guarantee. It turns out that even when the U statistic is non-degenerate and the Hájek projections do not concentrate as strongly, our algorithm (Algorithm 1) achieves near-optimal private error guarantees. Algorithm 1 also works with subsampled family $\mathcal{S} \subseteq I_{n,k}$, where the size of $\mathcal{S}$ can be as small as $\tilde{O}(n^2/k^2)$. This allows for a computationally efficient algorithm for all $n$ and $k$.

### **Regarding privacy budget (Reviewer MPw8)** 

Lemma 3 (line 130) shows that the CoinPress algorithm from [3], adapted to the all-tuples family, is $2\epsilon$-DP.

The following argument shows that Algorithm 2 is $10\epsilon$-DP as stated. Corollary 2.4 in [1] shows that for any function $f:\mathcal{X} \to \mathbb{R}$, the output $f(X) + \frac{2(\eta+1)S(X)}{\epsilon} Z$, where $Z$ is sampled from the distribution with density $\propto \frac{1}{1+|z|^\eta}$ and $S(X)$ is a $\beta$ smooth upper bound on the local sensitivity $LS(X)$ of $f$, is $\epsilon$-DP as long as $\beta \le \frac{\epsilon}{2(1+\eta)}$ and $\eta>1$. 

Thus, as stated with $\eta=4$, our algorithm, Theorem 2 (line 196), is $10\epsilon$-DP. We chose $\eta = 4$ somewhat arbitrarily, and we can improve this to almost $4\epsilon$-DP by choosing $\eta$ close to $1$. 

Corollary 1 (line 209) follows by composing our extension of the algorithm from [2] and our main algorithm. Passing in $\epsilon/2$ to Algorithm A.2. with $\mathcal{S} = \mathcal{I}_{n,k}$ and $\epsilon/20$ to our main algorithm results in an $\epsilon$-DP algorithm for non-degenerate, subgaussian kernels.

### **Regarding Distributional Convergence (Reviewer 8Ha8)**

To our knowledge, differential privacy results typically focus on finite sample guarantees. However, we can show that under mild conditions on $n,k,$ and $\epsilon$, our estimator has the same asymptotic distribution as the non-private U statistic in the degenerate (of order $1$) and non-degenerate cases. Thus, the asymptotic variance doesn’t change.

For simplicity, let $k=O(1)$ and $\mathcal{S}=I_{n,k}$, the set of all size $k$ subsets of $[n]$. Consider a scaling factor $c_n$, set to $n$ ($\sqrt{n}$) for degenerate (non-degenerate) kernels. Recall that our estimator $\mathcal{A}(X)=\tilde{A}_n+S(X)/\epsilon Z$, where $Z$ has density $f(z)\propto 1/(1+z^4)$. We have,
$$c_n(\mathcal{A}(X)-\theta)=c_n(\tilde{A}_n-A_n)+c_n(A_n-\theta)+c_n \frac{S(X)}{\epsilon} Z.$$

For $\mathcal{S}=I_{n,k}$, $A_n=U_n$ and hence $c_n(A_n-\theta)$ converges to either a Gaussian ($h$ is non-degenerate, $c_n=\sqrt{n}$) or weighted sum of centered Chi-squared distributions ($h$ is degenerate, $c_n=n$) [2]. We show that for any choice of $c_n$, the second term is $o_P(1)$. Define $\mathcal{E}_1=\{\exists i: |\hat{h}(i)-\theta|\geq C_1\sqrt{k/n}\log(n/\alpha)\}$ and $\mathcal{E}_2=\{|A_n-\theta|\geq C_1\sqrt{k/n}\log(n/\alpha)\}$.
By Lemmas A.21 (line 854) and A.3 (line 494), $P(c_n|\tilde{A}_n-A_n|\geq t)\leq P(\tilde{A}_n\neq A_n)\leq P(\mathcal{E}_1)+P(\mathcal{E}_2)\leq 2\alpha$. 

For non-degenerate subgaussian kernels, $h$ is truncated using one-half of the data. So the same argument as in lines 201-208 shows that the probability that none of the $h(X_S)$ is truncated is at most $\alpha$. For finite-sample guarantees, we take $\alpha$ as a constant and then boost it via median-of-means. For distributional convergence, we take $\alpha=n^{-c}, c>0$. Thus the first term is $o_P(1)$. Finally, conditioned on $\mathcal{E}_1\cap\mathcal{E}_2$, $L=1$ for $\xi=\tilde{O}(\sqrt{k/n})$ (Lemma A.21, line 854) in the degenerate case and $\xi=\tilde{O}(\sqrt{k\tau})$ (Lemma A.22, line 863) in the non-degenerate case. Some calculations show that as long as $\frac{k^3}{n\epsilon^2}=o(1)$, $c_n S(X)/\epsilon =o_P(1)$. Since $Z = O_P(1)$, the third term is also $o_P(1)$.

Overall, $|c_n(\mathcal{A}(X)-\theta) - c_n(A_n-\theta)| = o_P(1)$, establishing that the asymptotic distributions of the private and non-private estimates are the same.

### **References**

[1] J. Ullman and A. Sealfon. Efficiently estimating Erdos-Renyi graphs with node differential privacy. NeurIPS 32, 2019.

[2] A. J. Lee. U-statistics: Theory and Practice. Routledge, 2019.

[3] S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. NeurIPS 33:14475–14485, 2020.

Meta-review: The paper studies differentially private estimation of U-statistics (estimators for such statistics are averages of functions $h$ that depend on a number of i.i.d. samples $X_1,\dots,X_k$). All reviewers are pro-acceptance and so we are happy to accept to NeurIPS 24. Please however take the reviewers comments to heart and try to incorporate them in the camera-ready version of the paper.
Decision: Accept (poster)