On Differentially Private U Statistics

Authors: kamalika  chaudhuri
po-ling  loh
shourya  pandey
purnamrita  sarkar
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 08:10:40

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.

Main paper: 
 introduction: 
 A fundamental task in statistical inference is to estimate a parameter of the form E[h(X 1 , . . . , X k )], where h is a possibly vector-valued function and {X i } n i=1 are i.i.d. draws from an unknown distribution. U-statistics are a well-established class of estimators for such parameters and can be expressed as averages of functions of the form h(X 1 , . . . , X k ). U-statistics arise in many areas of statistics and machine learning, encompassing diverse estimators such as the sample mean and variance, hypothesis tests such as the Mann-Whitney, Wilcoxon signed rank, and Kendall's tau tests, symmetry and uniformity testing [26, 21] , goodness-of-fit tests [58] , counts of combinatorial objects such as the number of subgraphs in a random graph [30] , ranking and clustering [19, 18] , and subsampling [52] .U-statistics are a 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 estimation [42, 39, 14, 40, 10, 41, 24, 11, 33, 15] . Ghazi et al. [29] and Bell et al. [8] consider Ustatistics in the setting of local differential privacy [43] , while we are interested in privacy guarantees under the central model. Moreover, existing work on private U-statistics focuses on discrete data, and relies on 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 2 /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 [31] ). 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 a suitable scale may not be effective.1. We present a new algorithm for private mean estimation that achieves nearly optimal private and non-private errors for non-degenerate U-statistics with sub-Gaussian kernels.2. We provide a lower bound for privately estimating non-degenerate sub-Gaussian 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 is nearly optimal. A summary of the utility guarantees of our algorithm and adaptations of existing private mean estimation methods is presented in Table 1 .3. The computational complexity of our first algorithm scales as Õ( n k ). We generalize this algorithm and develop an estimator based on subsampled data, providing theoretical guarantees for a more efficient version with O(n 2 ) computational complexity.The paper is organized as follows. Section 2 reviews the background on 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 in sparse geometric graphs. Section 6 concludes the paper.A fundamental task in distributional property testing [6, 7] is deciding whether a discrete distribution is uniform on its domain, called the problem of uniformity testing. Let X 1 , X 2 , . . . , X n be n i.i.d. samples from a discrete distribution with support [m], characterized by the probability masses p 1 , p 2 , . . . , p m on the atoms. Given an error tolerance δ > 0, the task is to distinguish between approximately uniform distributions p :ℓ 2 (p, U ) ≤ δ/ √ 2m and far-from- uniform distributions {p : ℓ 2 (p, U ) ≥ δ/ √ m}.Without the constraint of privacy, Diakonikolas et al. [21] perform this test by rejecting the uniformity hypothesis whenever the test statisticU n := i<j 1(X i = X j )/ n k > (1 + 3δ 2 /4)/m, and show that this test succeeds with probability 0.9 as long as n = Ω m 1/2 /δ 2 . As detailed in Algorithm A.4 in the appendix, instead of using U n , we use the private estimate Ũn using Algorithm 1.For our algorithm to work, we require the distributions to satisfy p i ≤ 2/m for all i. Letp i = (1 + a i )/m for all i, with a i ∈ [-1, 1]. Under H 1 , we have E[1(X 1 = X 2 )] = (1 + ∥a∥ 2 /m)/m ≥ (1 + δ 2 )/m, where ∥a∥ is the ℓ 2 norm of (a 1 , a 2 , . . . , a m ). Under H 0 , the mean is 1/m. The difference between the threshold (1 + δ 2 /2)/m and the mean (under either of the two hypotheses) is at least δ 2 /(2m). Moreover, [21] shows that the standard deviation of U n is much smaller than the difference in the means under H 0 and H 1 as long as n = Ω(m 1/2 /δ 2 ). However, we must also account for the noise added to ensure privacy. In Appendix A.6.1, we show that the choice of ξ = Θ(1/m + 1/n) works and establish the following result:Theorem 5. Let p i = (1+a i )/m with a i ∈ [-1, 1], m i=1 a i = 0. Let {X j } n j=1 be i.i.d. multinomial random variables such that P (X 1 = i) = p i , for all i ∈ [m]. There exists an algorithm that distinguishes between ∥a∥ 2 m 2 ≥ δ 2 m from ∥a∥ 2 m 2 < δ 22m with probability at least 1 -α, as long asn α = Ω m 1/2 δ 2 + m 1/2 (δϵ) + m 1/2 log(m/δϵ) δϵ 1/2 + m 1/3 δ 2/3 ϵ + 1 δ 2, and is 10ϵ-differentially private.The non-private error term of Theorem 5 is the same as in Theorem 1 of [21] and is optimal [22] . Proposition 1 shows that Algorithm A.2 with the all-tuples family leads to a private error bounded by Õ(1/nϵ). This private error is O(δ 2 /m) only when n = Ω(m/δ 2 ϵ). In comparison, Algorithm A.4has error O(δ 2 /m) for n = Ω m 1/2 /min(δ 2 , δϵ) , which is quadratically better in m.Remark 5 (Comparison with existing algorithms). Existing results for private uniformity testing [1, 13] distinguish between the uniform distributions (ℓ 1 (p, U ) = 0) and distributions away from uniform in TV-distance (ℓ 1 (p, U ) ≥ δ). Our algorithm considers the alternative hypothesis to beℓ 2 (p, U ) ≥ δ/ √ m.Hence, our results are not strictly comparable. One caveat is that we restrict ourselves to distributions p such that ℓ ∞ (p, U ) ≤ 1/m. Our algorithm also allows some tolerance in the null hypothesis, similar to [21] and other collision-based testers. That is, can allow some slack and take the null hypothesisH 0 : ℓ 2 (p, U ) ≤ δ/ √ 2m instead of ℓ 2 (p, U ) = 0. 
background and problem setup: 
 Let n and k be positive integers with k ≤ n. Let D be an unknown probability distribution over a set X , and let h : X k → R be a known function symmetric in its arguments 1 . Let H be the distribution of h(X 1 , X 2 , . . . , X k ), where X 1 , X 2 , . . . , X k ∼ D are i.i.d. random variables. We are interested in providing a ϵ-differentially private confidence interval for the estimable parameter [32] θ = E[h(X 1 , X 2 , . . . , X k )], which is the mean of the distribution H, given access to n i.i.d. samples from D; we use X 1 , X 2 , . . . , X n to denote these n samples. The kernel h, the degree k, and the estimable parameter θ are allowed to depend on n; we omit the subscript n for the sake of brevity.We consider bounded kernels h and unbounded kernels h where the distribution H is sub-Gaussian. We write Y ∼ sub-Gaussian(τ ) if E[exp(λ(Y -EY ))] ≤ exp(τ λ 2 /2) for all λ ∈ R. The quantity τ is called a variance proxy for the distribution H and satisfies the inequality τ ≥ σ 2 [59] . Throughout the paper, we assume that the privacy parameter ϵ = O (1) . We also use the notation Õ(•) in error terms, which hides poly-logarithmic factors in n/α.Let [n] denote {1, . . . , n}, and let I n,k be the set of all k-element subsets of [n] . Denote the n i.i.d. samples by X 1 , X 2 , . . . , X n . For any S ∈ I n,k , let X S be the (unordered) k-tuple {X i : i ∈ S}. The U-statistic associated with the data and the function h isEQUATIONThe function h is the kernel of U n and k is the degree of U n . While U-statistics can be vector-valued, we consider scalar U-statistics in this paper. The variance of U n can be expressed in terms of the conditional variances of h(X 1 , X 2 , . . . , X n ). For c ∈ [k], we define the conditional variance EQUATIONEQUATIONSince E[U n ] = θ, U n is an unbiased estimate of θ. Moreover, the variance of U n is a lower bound on the variance of any unbiased estimator of θ. (cf Lee [45, Chapter 1, Theorem 3] ). We also have the following inequality from Serfling [54] (see Appendix A.2 for a proof):EQUATIONInfinite-order U-Statistics: Classical U-statistics typically have small, fixed k. However, important estimators that appear in the contexts of subsampling [52] and Breiman's random forest algorithm [56, 50] have k growing with n. These types of U-statistics are sometimes referred to as infinite-order Ustatistics [27, 48] ). 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 {ζ c } vanish with n in the sparse setting. (See Section 5.)Degenerate U-statistics: A U-statistic is degenerate of order ℓ ≤ k -1 if ζ i = 0 for all i ∈ [ℓ] and ζ ℓ+1 > 0 (if ζ k = 0, the distribution is almost surely constant). Degenerate U-statistics arise in hypothesis tests such as Cramer-Von Mises and Pearson tests of goodness of fit [31, 3, 55] and tests for unformity [21] . They also appear in tests for model misspecification in econometrics [46, 47] .For more examples of degenerate U-statistics, see [20, 61, 34] .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 as input a dataset D ∈ X n and outputs an element of its range space S, satisfies ϵ-differential privacy if for any pair of adjacent datasets D and D ′ and any measurable subset S ⊆ S of the range space S, Pr(M (D) ∈ S) ≤ e ϵ Pr(M (D ′ ) ∈ S). A dataset is D := (X 1 , X 2 , . . . , X n ) 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 to Appendix A.2.Basic DP algorithms. One way to ensure an algorithm satisfies differential privacy is through the Laplace Mechanism [25] . The global sensitivity of a function f : X n → S isEQUATIONwhere D∆D ′ := |{i : D i ̸ = D ′ i }| A fundamental result in differential privacy is that we can achieve privacy for f by adding noise calibrated to its global sensitivity. Lemma 1. (Laplace mechanism [25] ) Let f : X n → S be a function and let ϵ > 0 be the privacy parameter. Then the algorithmA(D) = f (D) + Lap GS(f ) ϵ 2 is ϵ-differentially private.The global sensitivity of a 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 n → S at D is defined asEQUATIONUnfortunately, 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 ϵ-smooth upper bound on the local sensitivity of f if (i) SS(f, D) ≥ LS(f, D) for all D, and (ii) SS(f, D) ≤ e ϵ SS(f, D ′ ) for all |D∆D ′ | = 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 : X n → S be a function, ϵ > 0, and SS(f, • ) be an ϵ-smooth upper bound on LS(f, • ). Then, the algorithmA(D) = f (D) + SS(f, D)/ϵ • Z, where Z has density h(z) ∝ 1 1+z 4 , is ϵ/10-differentially private. log nϵ k Ω k 3/2 C n 3/2 ϵfor private algorithms Theorem 1 Theorem 3Table 1 : We compare our application of off-the-shelf tools to Algorithm 1. We only provide the leading terms in the private error. The non-private lower bound on E( θ -Eh(X 1 , . . . , X k )) 2 for all unbiased θ is Var(U n ), which our private algorithms nearly match.We start with a simple, non-private estimator involving an average of independent quantities. Let m = ⌊n/k⌋, and define S j = {(j -1)k + 1, (j -1)k + 2, . . . , jk} for all j ∈ [m]. Define the naive estimator θnaive := m j=1 h(X Sj )/m. Directly applying existing private mean estimation algorithms [42, 40, 39, 10] to our setting yields an error bound of 3Var( θnaiveEQUATIONsince Var( θnaive ) = kζ k /n. Note that this variance is larger than the dominant term k 2 ζ 1 /n of Var(U n ) (see Lemma A.1 and Eq 4); indeed, θnaive is a suboptimal estimator of θ.In Algorithms A.2 and A.3, we present a general extension of the CoinPress algorithm [10] , which is then used to obtain a private estimate of θ with the non-private error term matching Var(U n ). For completeness, we present the algorithms and their proofs in Appendix A. EQUATIONas long asn α = Ω k ϵ log R √ kτ .Moreover, the algorithm is ϵ-differentially private and runs in timeÕ log(1/α) k + log R √ kτ nα k.Remark 1. While Lemma 1 recovers the correct first term of the deviation, the private error term is a √ k factor worse. Moreover, we need k 2 /n = o(1) for the private error to be asymptotically smaller than the non-private error. Note, however, that existing concentration [35, 5] or convergence in probability results [58, 48] only require k = o(n) (see Lemmas A.1 and A.3 in the Appendix). Remark 2 (Degenerate and sparse settings). While Lemma 1 improves over the naive estimator, the private error can overwhelm the non-private error for degenerate and sparse U-statistics (see Section 5) . We show that for uniformity testing, using this estimator can lead to suboptimal sample complexity if the distribution is already close to uniform.Proposition 1 improves 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 1 for the subsampled family.Definition 2 (Subsampled Family). Draw M i.i.d. samples S 1 , . . . , S M from the uniform distribution over the elements of I n,k , and let S ss := {S 1 , . . . , S M }. Call S all the "subsampled" family.The next result shows a nearly optimal dependence on n and ϵ in the bounds for θnaive and θall . In particular, the dependence of the modified Coinpress algorithm (Lemma 1) on k is suboptimal. Theorem 1 (Lower bound for non-degenerate kernels). Let n and k be positive integers with k < n/2 and let ϵ = Ω(k/n). Let F be the set of all sub-Gaussian distributions over R with variance proxy 1, and let μ be the output of any ϵ-differentially private algorithm applied to n i.i.d. observations from D. Then, sup h,D:H∈F E |μ(X 1 , . . . , X n ) -E[h(X 1 , . . . , X k )]| = Ω k nϵ log nϵk . Among unbiased estimators, U n is the best non-private estimator [35, 45] . The most widely used 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 [4] . Proofs are deferred to Appendix A.4.The geometric random graph (see [30] ) has edges h(X i , X j ) :=1(∥X i -X j ∥ 2 ≤ r n ), where r n governs the average degree. Under a suitable distribution for X 1 , . . . , X n , the subgraph counts show normal convergence for a large range of r n [30] . Typically, we only observe the graph and do not know the underlying distribution of the latent variables X i or the radius r n . 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 i 's be uniformly distributed on the three-dimensional sphere to ignore boundary conditions. For edge density, Eh(X i , X j ) ∝ r 2 n . For any distinct indices i, j, k and a given X i , the random variables h(X i , X j ) and h(X i , X k ) are independent. Therefore,ζ 1 = cov(h(X i , X j )h(X i , X k )) = 0. We have ζ 2 = var[h(X i , X j )] = O(r 2n ), so the non-private error is O(r n /n). In Appendix A.6.2, we provide Algorithm A.5 that uses Algorithm 1 to obtain a private estimate of the edge density of a graph {h(X i , X j )} 1≤i<j≤n . Note that the X i 's themselves can be unknown. Our methods can also be used for private triangle density estimation. See the extended version [16] for details. Theorem 6. Let r n = Ω(n -1/2 ) and ϵ = Ω 1/nr 2 n . Let {X 1 , . . . , X n } be i.i.d. latent positions such that X i is distributed uniformly on ∂S 2 . Let the observed geometric network have adjacency matrix {A ij , 1 ≤ i < j ≤ n} where A ij = 1(∥X i -X j ∥ ≤ r n ). There exists a 10ϵ-differentially private algorithm that estimates the edge density θ of the geometric graph. With probability at least1 -α, the output θ satisfies | θ -θ| = Õ rn nα + 1 n 2 α ϵ 2 + 1 n 3 α ϵ 3Remark 6. By Lemma 1, the all-tuples estimator (1) satisfies | θall -θ| ≤ Õ (r n /n + √ τ /nϵ) with probability 1 -α, where τ is the variance proxy of the distribution. Since τ = Ω(1) [4] , the private error overpowers the main variance term in sparse settings where r n = o(1).The 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 a U statistic plus a smaller order term) is degenerate [20] .• 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 a specific model and empirical evaluation, it may be necessary to either make it 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 NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or 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.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
boosting the error probability via median-of-means: 
 If we use Algorithm A.2 as stated with failure probability α, then the error in the algorithm has a O(1/ √ α) factor, which is undesirable. Instead, we use the Algorithm with a constant failure probability (say, 0.25) and then boost this failure probability to α via a median-of-means procedure. We incorporate the median-of-means in all of our theoretical results. Wrapper 1 (MedianOfMeans(n, k, Algorithm A, Parameters Λ, Failure probability α, Family type f ∈ {all, ss})). Divide [n] into q = 8 log(1/α) independent chunks I i , i ∈ [q] of roughly the same size. For each i ∈ [q], run Algorithm A with subset family S i := S f (I i ), Dataset {h(X S )} S∈Si , and other parameters Λ for A to output θi , i ∈ [q]. Return θ = median( θ1 , . . . , θq ).In the above wrapper, S f (D i ) simply creates the appropriate family of subsets for the dataset D i . For example, ifD i = {X 1 , . . . X nα }, f = all, then S all (D i ) is {h(X S )} S∈I nα ,k . If f = ss, then S ss (D i ) is {h(X S )} S∈Si , where S i is the set of M subsampled subsets of D i . Here, n α := n 8 log(1/α) .Wrapper 1 can be used to boost the failure probability from constant to α by splitting the data into O(log(1/α)) chunks, applying the algorithm on each of the chunks, and taking the median output. The expense of this procedure is the reduction in the effective sample size to n α = Θ(n/ log(1/α)). Details and proofs on the median-of-means procedure can be found in Section A.3.2. 
main results: 
 In Section 3, we showed that off-the-shelf private mean estimation tools applied to U-statistics either achieve a sub-optimal non-private error (see Remark 1) or a sub-optimal private error. If the U-statistic is degenerate of order 1, the non-private and private errors (assuming ϵ = Θ(1)) are Θ(1/n). We now present an algorithm that achieves nearly optimal private error for sub-Gaussian non-degenerate kernels. Our algorithm can be viewed as a 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-private error. All proofs for this section can be found in Section A.5.Our key insight is to leverage the Hájek projection [58, 45] , which gives the best representation of a U-statistic as a linear function of the form n i=1 f (X i ):Ŝn (i) = n i=1 E[T n |X i ] -(n -1)E[T n ] (ii) = k n n i=1 E[h(X S )|X i ] -(n -1)θ.Equality (i) gives the form of the Hájek projection for a general statistic T n , whereas (ii) gives the form when T n is a U-statistic. LetI (i) n,k = {S ∈ I n,k : i ∈ S}.In practice, one uses the estimatesEQUATIONwhich we call local Hájek projections. In some sense, this is the U-statistic when viewed locally at X i . When the dataset is clear from context, we write ĥI n,k (i), or simply ĥ(i), for E[h(X S )|X i ].Consider a family of subsets S ⊆ I n,k of size M . Let S i = {S ∈ S : i ∈ S} and M i = |S i |, and suppose M i ̸ = 0 for all i ∈ [n]. Assume also that S satisfies the inequalitiesEQUATIONfor any distinct indices i and j in [n] (one such family is S = I n,k , for which M i /M = k/n and M ij /M i = (k -1)/(n -1) ≤ k/n, but there are other such families). DefineA n (S) := 1 M S∈S h(X S ), and ĥS (iEQUATIONU n in Eq (1) and E[h(X S )|X i ] in equation ( 9) are the same as the quantities A n (I n,k ) and ĥI n,k (i).A standard procedure in private estimation algorithms is to clip the data to an appropriate interval [10, 41] in such a way that the sensitivity of the overall estimate can be bounded. Similarly, we use the concentration of the local Hájek projections to define an interval such that each i can be classified as "good" or "bad" based on the distance between ĥS (i) 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 C be parameters to be chosen later; they will be chosen in such a way that with high probability, (i) | ĥ(i) -θ| ≤ ξ for all i, and (ii) each h(X S ) is at most C away from θ. DefineEQUATIONIn other words, L S is the smallest positive integer t such that at mostt indices i ∈ [n] satisfy | ĥS (i) -A n (S)| > ξ + 6kCtn (such an integer t always exists because t = n works). Define Good(S)EQUATION)For each index i ∈ [n], define the weight of i with respect to S as wt S (i) := max 0, 1 -EQUATIONHere, ϵ is the privacy parameter and dist(x, I) is the distance between x and the interval I.Based on whether a datapoint is good or bad, we will define a weighting scheme that reweights the h(X S ) in equation (1) . For each S ∈ S, let wt S (S) := min i∈S wt S (i), and g S (X S ) := h(X S )wt S (S) + A n (S) (1wt S (S)) .In particular, if wt S (S) = 1, then g S (X S ) = h(X S ); and if wt S (S) = 0, then g S (X S ) = A n (S).Finally, define the quantitiesEQUATIONTo simplify notation, we will drop the argument S from L, A n , Ãn , ĥ, ĝ, Good, and Bad.Idea behind the algorithm: If all ĥ(i)'s are within ξ of the empirical mean A n , then Bad = ∅ and Ãn = A n . Otherwise, for any set S containing a bad index, we replace h(X S ) by a weighted combination of h(X S ) and A n . This averaging-out of the bad indices allows a bound on the local sensitivity of Ãn . We then provide a smooth upper bound on the local sensitivity characterized by the quantity L, which can be viewed as an indicator of how well-concentrated the data is. The choice of ξ will be such that L = 1 with high probability and that the smooth sensitivity of Ãn at X is small. This ensures that a smaller amount of noise is added to Ãn to preserve privacy.Algorithm 1 PrivateMeanLocalHájek(n, k, {h(X S ), S ∈ S}, ϵ, C, ξ, S)1: M ← |S| 2: S i ← {S ∈ S : i ∈ S} 3: M i ← |S i | 4: if there exist indices i ̸ = j such that M i = 0 or M i /M > 3k/n or M ij /M i > 3k/n, then 5:return ⊥ 6: end if 7: A n ← S∈S h(X S )/M 8: for i = 1, 2, . . . , n do 9: ĥ(i) ← S∈Si h(X S )/M i 10: end for 11: Let L be the smallest positive integer such that i : ĥ(i) [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 to a broader setting of U-statistics: consider a hypergraph with n nodes and n k edges, where the i th node corresponds to index i. An edge corresponds to a k-tuple of data points S ∈ I n,k , and the edge weight is given by h(X S ). The natural counterpart of a degree in a graph becomes a local Hájek projection, defined as in equation (9) . In degenerate cases and cases where k 2 ζ 1 ≪ kζ k , the local Hájek projections are tightly concentrated around the mean θ. We exploit this fact and reweight the edges (k-tuples) so that the local sensitivity of the reweighted U-statistic is small.-A n > ξ + 6kCL n ≤ L 12: Good(S) ← i : ĥ(i) -A n ≤ ξ + 6kCL n ; Bad(S) ← [n] \ Good(S))(1+ϵ(L+ℓ))+ k 2 C(L+ℓ) 2 min(k,(L+ℓ)) n 2 (ϵ+ k n )+ k 2 CAlgorithm 1 can be extended from bounded kernels to sub-Gaussian(τ ) 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 θ. For this, we can use any existing private mean estimation algorithm to obtain an ϵ/2-differentially private estimate θcoarse such that with probability at least 1 -α,| θcoarse -θ| = Õ( kζ k /n + k √ τ /(nϵ)). By a union bound, with probability at least 1 -α, |h(X S ) -θ| is within 4 τ log n k /α for all S ∈ I n,k , and therefore also within c kτ log(n/α) of the coarse estimate θcoarse , for some universal constant c, as long as ϵ = Ω(√ k/n).Define the projected function h(X 1 , X 2 , . . . , X k ) to be the value h(X 1 , X 2 , . . . , X k ) projected to the interval [ θcoarse -c kτ log(n/α), θcoarse + c kτ log(n/α)]. The final estimate of the mean θ is obtained by applying Algorithm 1 to the other half of the samples, the function h, and the privacy parameter ϵ/2. The following lemma shows that 2τ log(2n/α) is a valid choice of the concentration parameter ξ for sub-Gaussian, non-degenerate kernels.Lemma 3. If H is sub-Gaussian(τ ), the local Hájek projections ĥ(i) are also sub-Gaussian(τ ). In particular, with probability at least 1 -α, we have max 1≤i≤n | ĥ(i) -θ| ≤ 2τ log(2n/α).Combining these parameters with Theorem 2 gives us the following result: Corollary 1 (Non-degenerate sub-Gaussian kernels). Suppose h is sub-Gaussian(τ ) and the privacy parameter ϵ = Ω(k 1/2 /n). Split the samples into two halves and compute a private estimate of the mean by applying the naive estimator on the first half of the samples with privacy parameter ϵ/2 to obtain θcoarse . Let h be the projection of of the function h onto the interval θcoarse ± O( kτ log(2n/α)).Run Wrapper 1 on the remaining half of the samples with f = all, failure probability α/2, algorithm A = PrivateMeanLocalHájek (Algorithm 1), C = 2kτ log(n/2α), ξ = 2τ log(n/2α), function h, and privacy parameter ϵ/20. Then, the output θ is ϵ-differentially private. Moreover, with probability at least 1 -α,| θ -θ| = O Var(U nα ) + Õ k √ τ n α ϵ + k 2.5 √ τ n 2 α ϵ 2 + k 3.5 √ τ n 3 α ϵ 3.From our lower bound on non-degenerate kernels in Theorem 1, we see that the above corollary is optimal in terms of k, n, ϵ (up to log factors). In contrast, Lemma 1 is suboptimal in k.Many degenerate U-statistics (e.g., all the degenerate ones in Section 5) have bounded kernels. 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 i ∈ I n,k be a set containing i, and supposeEQUATIONwhereE[h(X S )|X i = x i ] = S∈S i h(X S ) ( n-1 k-1 ), andσ 2 i = Var (h(X Si )|X i = x i ).For bounded kernels with additive range C, σ i ≤ C/2 by Popoviciu's inequality [53] . Moreover, for degenerate kernels,ζ 1 = 0. That is, the conditional expectation E [h(X Si )|X i = x i ] is equal to θ for all x i , because the variance of this conditional expectation is ζ 1 .Based on this, we can show that the choice of ξ = Õ Ck 1/2 /n 1/2 satisfies the requirement that the local Hájek projections are within ξ of θ with probability at least 1 -α. Corollary 2 (Degenerate bounded kernels). Suppose h is bounded with additive range C and the kernel is degenerate ζ 1 = 0. Let ϵ = Ω(k 1/2 /n) be the privacy parameter. Run Wrapper 1 with f = all, failure probability α, and algorithmA = PrivateMeanLocalHájek (Algorithm 1) with ξ = O(C k/n log(n/α)), to output θ. With probability 1 -α, we have θ -θ = O Var(U nα ) + Õ k 1.5 n 1.5 α ϵ C + k 2 n 2 α ϵ 2 C + k 3 n 3 α ϵ 3 C ,Obtaining a result for sub-Gaussian degenerate kernels poses difficulties on bounding the concentration parameter ξ. However, for bounded kernels, we see that the above result obtains better private error than the application of off-the-shelf methods (Lemma 1). 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 error for private degenerate kernels.To obtain a lower bound of the private error, we construct a dataset and kernel function such that the local Hájek projections are 1/ √ n concentrated around the corresponding U-statistic. This is one way of characterizing a degenerate U-statistic. The proof of the following theorem is in Appendix A.4.Theorem 3. For any n, k ∈ N with k ≤ n, ϵ = Ω((k/n) 1-1/2(k-1)), and ϵ-differentially private algorithm A : X n → R, there exists a function h : X k → {0, 1} and dataset D such that | ĥ(i)-U n | ≤ k/n (where ĥ(i) and U n are computed on D) for every i ∈[n] and E|A(D)-U n | = Ω k 3/2 n 3/2 ϵ, where the expectation is taken over the randomness of A. Remark 3. The above lower bound is in some sense informal because we created a deterministic dataset and h that mimics the property of a degenerate U statistic; the local Hájek projections concentrate around U n at a rate k/n. However, it gives us a strong reason to believe that the private error cannot be smaller than O(k 3/2 /n 3/2 ϵ) for degenerate U statistics of order k. Note that for bounded kernels, Corollary 2 does achieve this bound, as opposed to Lemma 1.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, 17] , where the sum is replaced with an average of samples (drawn with or without replacement) from I n,k .Recall Definition 2. Let S := {S 1 , . . . , S M } denote the subsampled set of subsets, let S i := {S ∈ S : i ∈ S}, and letM i := |S i |. The proof of Theorem 2 with S = I n,k (cf. Appendix A.5) uses the property of I n,k that M i /M = k/n and M ij /M i = (k -1)/(n -1), so the inequalities (10) certainly hold. Indeed, we can show that for subsampled data (cf. Lemma A.11), the following inequalities hold with probability at least 1 -α, provided M = Ω(n 2 /k 2 log(n/α)):EQUATIONAlgorithmically, we check if the bounds ( 17) hold for S, and output ⊥ if not. Privacy is not compromised because the check only depends on S and is agnostic to the data.Theorem 4. Let M n = Ω (n 2 /k 2 ) log n . Then Algorithm 1, modified to output ⊥ if the bounds (17)do not hold, is 10ϵ-differentially private. Moreover, suppose that with probability at least 0.99, we havemax i | ĥS (i) -A n | ≤ ξ and |h(S) -θ| ≤ C for all S ∈ I n,k .Run Wrapper 1 with f = ss, failure probability α, and A = PrivateMeanLocalHajek (Algorithm 1) to output θ. With probability at least 1 -α, we have|A(X) -θ| = O Var(U nα ) + ζ k M nα + kξ n α ϵ + k 2 C n 2 α ϵ 2 + k 3 C n 3 α ϵ 3 min k, 1 ϵ .Remark 4. If the kernel is non-degenerate and the number of times we subsample (for each run of the algorithm) is Ω n 2 α /k 2 , then Theorem 4 nearly achieves the same error as Algorithm 1 with S = I n,k with a better computational complexity for k ≥ 3. The lower-order terms have an additional min(k, 1/ϵ) factor, which can be removed with Ω(n 3 ) subsamples. 
applications: 
 We apply our methods to private uniformity testing and estimation in random networks. For more applications, see Appendix A.6.4.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an 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 NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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. If only a 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) is recommended, but including URLs to data and code is permitted. 
discussion: 
 We have considered the problem of estimating θ := Eh(X 1 , . . . , X k ) 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 k or for non-degenerate U statistics, which have O(1/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-Gaussian non-degenerate kernels and bounded degenerate kernels. We also provide applications of our theory to private hypothesis testing and estimation in sparse graphs.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 on our extension of the Coinpress algorithm [10] 4. Section A.4: Proofs of lower bounds 5. Section A.5: Proofs of the main theorems 2 and 4 6. Section A.6: More applications and details on uniformity testing and edge-density estimationLet h : X k → R be a symmetric function, and let X 1 , . . . , X n ∈ X . The U statistic on the n variables X 1 , . . . , X n , U n (h), associated with h is defined asU n = 1 n k {i1,...,i k }∈I n,k h(X i1 , . . . , X i k ). (A.18)The mean of U n based on iid variables X 1 , . . . , X n ∼ D, for some distribution D on X , is simplyθ := E[h(X 1 , . . . , X k )].Moreover, the variance of U n can be expressed succinctly in terms of conditional expectations [45] . For c = 1, 2, . . . , k, define h c :X c → R as h c (X 1 , . . . , X c ) := E[h(X 1 , . . . , X k )|X 1 = x 1 , . . . , X c = x c ], (A.19) and let ζ c = Var (h c (X 1 , . . . , X c )) . (A.20) Equivalently, ζ c = cov (h(X S1 ), h(X S2 )) where S 1 , S 2 ∈ I n,k and |S 1 ∩ S 2 | = c. The number of such pairs of sets S 1 and S 2 is equal to n k k c n-k k-c, which implies implies Eq 3.Hoeffding decomposition. A U statistic of degree k can be written as the sum of uncorrelated U statistics of degrees 1, 2, . . . , k. Define h (1) (X 1 ) = h(X 1 ) -θ and for all 2 ≤ c ≤ k, h (c) (X 1 , . . . , X c ) = (h c (X 1 , . . . , X c ) -θ) - ϕ⊊S⊊Ic,i h (i) (X S ) .Then, U n can be written asU n = θ + k c=1 k c U (c) n , (A.21)whereU (c)n is the U statistic on X 1 , . . . , X n based on the kernel h (c) . Equation A.21 is called the Hoeffding decomposition (or the H-decomposition) of U n [36] . [36] also shows that the c functions h (1) , . . . , h (k) are pairwise uncorrelated. That is, let 1 ≤ c < d ≤ k and let S c and S d be subsets of [n] of sizes c and d respectively. Then,cov h (c) (X Sc ), h (d) (X S d ) = 0.This allows us to write the variance of U n in terms of the variances of h (c) . For all c ∈ [k], defineδ 2 c = Var(h (c) ). (A.22) Then, Var(U n ) = k c=1 k c 2 n c -1 δ 2 c . (A.23)Moreover, the conditional covariances ζ c are related to the variances δ 2 c in the following manner:ζ c = c i=1 c i δ 2 i , δ 2 c = c i=1 (-1) c-i c i ζ i . (A.24) Lemma A.1. Suppose k ≤ n/2. (i) If ζ 1 > 0, then Var(U n ) = k 2 ζ 1 n + O ζ k k 2 n 2 . (A.25) (ii) If ζ 1 = 0 and ζ 2 > 0, then Var(U n ) = k 2 (k -1) 2 ζ 2 2n(n -1) + O ζ k k 3 n 3 . (A.26)Proof. This result follows directly from a calculation appearing in the proof of Theorem 3.1 in [48] . Note thatζ k = k j=1 k j δ 2 j ≥ k j δ 2 j for all j ∈ [k]. Moreover, Var(U n ) = k j=1 k j 2 n j -1 δ 2 j .For part (i), we writeVar(U n ) = k 2 ζ 1 n + k j=2 k j 2 n j -1 δ 2 j ≤ k 2 ζ 1 n + k j=2 k j n j -1 ζ k ≤ k 2 ζ 1 n + ζ k k j=2 k n j ≤ k 2 ζ 1 n + k 2 ζ k n 2 1 - k n -1 ≤ k 2 ζ 1 n + 2k 2 ζ k n 2 .For part (ii), we writeVar(U n ) = k 2 ζ 1 n + k 2 (k -1) 2 ζ 2 2n(n -1) + k j=3 k j 2 n j ζ j ≤ k 2 (k -1) 2 ζ 2 2n(n -1) + ζ k k j=3 k j n j ≤ k 2 (k -1) 2 ζ 2 2n(n -1) + ζ k k j=3 k n j = k 2 (k -1) 2 ζ 2 2n(n -1) + 2k 3 ζ k n 3 . Lemma A.2. For all 1 ≤ c ≤ d ≤ k, ζ c c ≤ ζ d d . (A.27)In particular,kζ 1 ≤ ζ k .Proof. Using equation A. 24 ,ζ c c = c i=1 1 c c i δ 2 i = c i=1 1 i c -1 i -1 δ 2 i ≤ c i=1 1 i d -1 i -1 δ 2 i ≤ d i=1 1 d d i δ 2 i = ζ d d .Lemma A.3 (Concentration of U-statistics). [37, 9] (i) If H is sub-Gaussian with variance proxy τ , then for all t > 0, we haveP (|U n -θ| ≥ t) ≤ 2 exp - ⌊ n k ⌋t 2 2τ . (A.28) (ii) If H is almost surely bounded in (-C, C), then for all t > 0, we haveP (|U n -θ| ≥ t) ≤ exp -n k t 2 2ζ k + 2Ct/3 . (A.29)Proof. Without loss of generality, let θ = 0. For any permutation σ of [n], letV σ := 1 m m i=1 h(X σ(k(i-1)+1) , X σ(k(i-1)+2) , . . . , X σ(ki) ),where m = ⌊n/k⌋. By symmetry,U n = 1 n! σ V σ .For any s > 0,P (U n ≥ t) = P e sUn ≥ e st ≤ e -st E e sUn = e -st E exp s n! σ V n ≤ e -st E 1 n! σ exp(sV n ) = e -st E [exp(sV id )] = e -st E exp s m h(X 1 , . . . , X k ) m .If H is sub-Gaussian with variance proxy τ , then we can further bound the inequality above asP (U n ≥ t) ≤ e -st exp s 2 τ 2m 2 m = exp -st + s 2 τ 2m .Set s = tm τ 2 to get the desired result. Note how the argument is similar to the classical Hoeffding's inequality argument after applying Jensen's inequality on V σ . The second result follows similarly by adapting the tricks of Bernstein's inequality [9] to [37] ; for a detailed proof, see [51] .Lemma A.4. (Basic Composition) If A i : X n → S i is ϵ i -differentially private for all i ∈ [k], then the mechanism A : X n → S 1 × • • • × S k defined as A (X 1 , . . . , X n ) = (A 1 (X 1 , . . . , X n ) , . . . , A k (X 1 , . . . , X n )) is k i=1 ϵ i -differentially private. Lemma A.5. (Parallel Composition) If A i : X n → S i is ϵ-differentially private for all i ∈ [k], then the mechanism A : X kn → S 1 × • • • × S k defined as A (X 1 , . . . , X kn ) = A 1 (X 1 , . . . , X n ) , A 2 (X n+1 , . . . , X 2n ) , . . . , A k X (k-1)n+1 , . . . , X kn is ϵ-differentially private.A fundamental task in private statistical inference is to privately estimate the mean based on a set of IID observations. One way to do this is 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. In 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.To remedy this effect, a line of work [42, 39, 14, 40, 24, 11] has looked into designing better private mean estimators for (sub)-Gaussian vectors. Our work will build on one such method: CoinPress [10] . The idea is 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 [33, 15] .We will prove a more general theorem than Lemma 1, from which Lemma 1 and related Lemmas using other families of subsets are derived.In Algorithms A.2 and A.3, we present a natural extension of the CoinPress algorithm [10] , which is then used to obtain a private estimate of θ with the non-private term matching Var(U n ). Originally, this algorithm was used for private mean and covariance estimation of i.i.d. (sub)Gaussian data. We extend the algorithm to take as input data {Y j } j∈[m] such that (i) each Y j is equal to h(X S ) for some S, (ii) the Y j 's are weakly dependent on each other, and (iii) each Y j , as well as their mean j∈[m] Y j /m, has sufficiently strong concentration around the population mean. For instance, suppose m = ⌊n/k⌋ and Y j = h(X Sj ) for all j ∈ [m], where S j = {(j -1)k + 1, . . . , (j -1)k + k}. Then Algorithm A.2 reduces to the CoinPress algorithm applied to n/k independent observations h(X S1 ), h(X S2 ), . . . , h(X Sm ).Algorithm A.2 U-StatMean n, k, h, {X i } i∈[n] , F = {S 1 , . . . , S m }, R, ϵ, γ, Q(•), Q avg (•) 1: t ← log (R/Q(γ)) , [l 0 , r 0 ] ← [-R, R] 2: for j = 1, . . . , m do 3: Y 0,j ← h(X Sj ) 4: end for 5: for i = 1, 2, ..., t do 6: {Y i,j } j∈[m] , [l i , r i ] ← U-StatOneStep n, k, {Y i-1,j }, F, [l i-1 , r i-1 ], ϵ 2t , γ t , Q(•), Q avg (•) 7: end for 8: {Y t+1,j } j∈[m] , [l t+1 , r t+1 ] ← U-StatOneStep (n, k, {Y t,j }, F, [l t , r t ], ϵ/2, γ, Q(•), Q avg (•)) 9: return (l t+1 + r t+1 )/2 Algorithm A.3 U-StatOneStep n, k, {Y i } i∈[m] , F, [l, r], ϵ ′ , β, Q(•), Q avg (•) 1: Y j ← proj l-Q(β),r+Q(β) (Y j ) for all 1 ≤ j ≤ m. 2: ∆ ← dep n,k (F) (r -l + 2Q(β)) 3: Z ← 1 m m j=1 Y j + W , where W ∼ Lap ∆ ϵ ′ 4: [l, r] ← Z -Q avg (β) + ∆ ϵ ′ log 1 β , Z + Q avg (β) + ∆ ϵ ′ log 1 β 5: return {Y j } j∈[m] , [l, r]Setting 1. Let n and k be positive integers with k ≤ n/2, and let h : X k → R be a symmetric function and let D be an unknown distribution over X with E h(D k ) = θ such that |θ| < R for some known parameter R.Let m be an integer and F = {S 1 , S 2 , . . . , S m } be a family of not necessarily distinct elements of I n,k . Definef i := |{j ∈ [m] : i ∈ S j }| m , (A.30)the fraction of indices j such that S j contains i, and define the maximal dependence fraction dep n,k (S) := maxi∈[n] f i . (A.31) For each j ∈ [m], let Y j denote h(X Sj ). Clearly, E [Y j ] = θ.To allow for small noise addition while ensuring privacy, it is desirable to choose S with small dep n,k (S).Q(β) = Q n,k,h,D,S (β) and Q avg (β) = Q avg n,k,h,D,S (β) on β ∈ (0, 1] such that P sup j∈[m] |Y j -θ| > Q(β) < β, P   1 m m j=1 Y j -θ > Q avg (β)   < β. (A.32)We will refer to Q(β) and Q avg (β) as β-confidence bounds for sup j∈[m] |Y j -θ| and 1 m j∈[m] Y j -θ , respectively. We apply Theorem A.1 (specifically, the form obtained in Lemma A.6) to different F to obtain private estimates of θ, with statistical and computational tradeoffs depending on the family F. As Remark A.7 suggests, we will also need to privately estimate concentration bounds on the Y j 's and their average. Naturally, this requires a private estimate of the variance ζ k . We provide guarantees from Biswas et al. [10] for private variance estimation and mean estimation here, where we have translated the mean estimation guarantee to fit our setting.Before we do that, a natural approach to this problem is to view it as 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 to 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 1 or even the subsampling estimator 2 if sufficiently many samples are used. Before stating the propositions associated with these families, we state and prove the mother theorem.Theorem A.1. For ϵ > 0, Algorithm A.2 with input n, k, h, {X i } i∈[n] , F, R, ϵ, γ, Q(•), Q avg (•) returns θn such that | θn -θ| ≤ O      Var( j∈[m] Y j ) m √ γ non-private error + dep n,k (F) Q(γ) ϵ • log 1 γ private error      , (A.33)with probability at least 1 -6γ, 5 as long asEQUATIONwhere t = ⌈C log (R/Q(γ))⌉. Moreover, Algorithm A.2 is ϵ-differentially private and runs in timeO(n + m log (R/Q(γ)) + k|F|).Remark A.7. Theorem A.1 assumes that Q(•) and Q avg (•) are known, despite the mean θ being unknown. Note that we only need to know the value of these functions at γ and γ/t, for a given γ. If these bounds are not known, we may first need to (privately) compute Q(x) and Q avg (x) and then use those privately computed bounds in the algorithm. For example, if the Y ′ i s are sub-Gaussian with variance proxy 1, then Q(x) = log(m/x). We will see how to estimate these parameters for various families F of indices used in Algorithm A.2.Proof of Theorem A.1. We will prove privacy and accuracy guarantees separately.Privacy. Algorithm A.2 makes t + 1 calls to Algorithm A.3; let ∆ i , W i , and Z i be the values taken by ∆, W, and Z in the i th call to Algorithm A.3, for 1 ≤ i ≤ t + 1. Let β := γ t . It can be shown inductively that the interval lengths r i -l i and the values ∆ i do not depend on the dataset. For any1 ≤ i ≤ t, note that Y i,j = proj li-1-Q(β),ri-1,Q(β) (Y i-1,j ) for all 1 ≤ j ≤ m. Suppose we change X w to X ′w for some index w. For any1 ≤ i ≤ t + 1, conditioned on the values of Z i ′ for 1 ≤ i ′ < i, at most a dep n,k (F) fraction of {Y i,j } j∈[m] depend on w (this is true by the definition of dep n,k (F)). Since Y i,j = proj li-1-Q(β),ri-1+Q(β/m) (Y i-1,j ) has range r i-1 -l i-1 + 2Q(β), the sensitivity of 1 m m j=1 Y i,j is at most dep n,k (F) (r i-1 -l i-1 + 2Q(β)) = ∆ i .Therefore, by standard results (cf. Lemma 1), for all 1 ≤ i ≤ t, the output Z i (and therefore the interval Therefore, with probability at least 1 -2β, we have[l i , r i ]), conditioned on Z i ′ for 1 ≤ i ′ < i, is ϵ 2t -differentially private. Similarly, the output (l t+1 + r t+1 )/2 = Z t+1 , conditioned on {Z i } i∈[t] , is ϵ 2 -differentially private. By Basic Composition (see Lemma A.4), Algorithm A.2 is ϵ-differentially private. Utility. First, we show that if Algorithm A.3 is invoked with θ ∈ [l, r], it returns an interval [l ′ , r ′ ] such that θ ∈ [l ′ ,|Z -θ| ≤ Q avg (β) + ∆ ϵ ′ log 1 β , in which case θ ∈ [l ′ , r ′ ].Finally, reintroducing the projection step only increases the error probability by at most β. Taking a union bound over t steps, we see that θ ∈ [l ′ , r ′ ], with probability at least 1 -3γ.Next, we claim that if r -l > 28Q(γ), then r ′ -l ′ ≤ (r -l)/2. Using the assumption, we havedep n,k (F) ≤ Q(γ)ϵ 10tQ(γ/t) log t/γ ≤ min ϵ ′ 5 log 1/β , Q(γ)ϵ ′ 5Q(β) log 1/β ,where the second inequality follows from taking ϵ ′ = ϵ 2t and using the fact that Q(γ) ≤ Q γ t , since the quantile function is nonincreasing. Furthermore, by the assumption Q avg (β) < Q(γ), we haver ′ -l ′ = 2dep n,k (F) log 1/β ϵ ′ (r -l) + 2Q avg (β) + 4dep n,k (F) Q(β) log 1/β ϵ ′ ≤ 2(r -l) 5 + 2Q(γ) + 4 5 Q(γ) ≤ r -l 2 .Thus, aftert = Ω log R Q(γ)iterations, we are guaranteed that the length of the final interval [l t , r t ] is at most 28Q(γ).Finally, consider lines 8 and 9 of Algorithm A.2. The algorithm returns the midpoint of the interval [l t+1 , r t+1 ], which is Z t+1 in the final call of Algorithm A.3. By Chebyshev's inequality, we haveEQUATIONwith probability at least 1 -γ, and with probability at least 1 -γ, none of the Y i 's are truncated in the projection step in the final call of Algorithm A.3. Finally, with probability at least 1 -γ, we haveW t+1 = O ∆ t+1 ϵ = O dep n,k (F) Q(γ) ϵ log 1 γ .The conclusion follows from a union bound over all events.Algorithm A.2 incurs a 1/ √ γ multiplicative factor in the non-private error, stemming from an application of Chebyshev's inequality to bound | m j=1 h(X Sj )/m -θ|. For specific families F, we may be able to provide stronger concentration bounds for m j=1 h(X Sj )/m in inequality (A.35). Instead, we complement the result of Theorem A.1 by applying the following median-of-means procedure that allows for an improved dependence on the failure probability α with only a log (1/α) multiplicative blowup in the sample complexity: Lemma A.6. Let α ∈ (0, 1) and ϵ ≥ 0. Let A be an ϵ-differentially private algorithm. Consider a size n dataset D n i.i.d ∼ D, for a distribution D with some unknown parameter θ such that with probability at least 0.75, we have|A(D n ) -θ| ≤ r n .Split D n into q := 8 log(1/α) equal independent chunks, 6 and run A on each chunk to obtain ϵ-differentially private estimates { θn,i } i∈[d] of θ. Let θmed n be the median of these q estimates. Then θmed n is ϵ-differentially private, and with probability at least 1 -α, we have θmed n -θ ≤ r n/q . (A.36)Proof. The privacy of θmed n follows from parallel composition (Lemma A.5). For utility, we know from the hypothesis that for each i ∈ [q], with probability at least 3/4, the estimate θn,i satisfies | θn,i -θ| ≤ r n/q .If more than half the estimates θn,i satisfy the above equation, then so does the median. Let T i be the random variable that assumes the value 0 if θn,i satisfies the above equation and assumes the value 1 otherwise. Then, E[T i ] ≤ 1/4, and it suffices to show thatPr (T 1 + T 2 + • • • + T q ≤ q/2) ≥ 1 -α.This follows from a standard Hoeffding inequality; as long as q ≥ 8 log(1/α),Pr (T 1 + T 2 + • • • + T q > q/2) ≤ Pr i (T i -E[T i ]) > q/4 ≤ e -2(1/4) 2 q ≤ α.For any i ∈ [n], there are exactly n-1 k-1 sets S ∈ I n,k such that i ∈ S. Following the notation from the setting of Theorem A.1, we havef i = n-1 k-1 / n k = k n for all i ∈ [n], so dep n,k (F all ) = k n . Moreover, for each S ∈ I n,k , we have P (|h(X S ) -θ| ≥ y) ≤ 2 exp -y 2 2τ . Letting Q(γ) := 2τ k log 2n γ > 2τ log 2 γ n k , we see that each Y i is within Q(γ) of θ with probability at least γ ( n k ). A union bound implies that this choice of Q(γ) is valid. For the concentration of the average 1 m j∈[m] Y j , which is simply U n , we can use Lemma A.3) to see thatQ avg (γ) := 2τ k log 2 γ nis a valid choice. We now verify the conditions in Theorem A.1:dep n,k (S) = k n ≤ Q(γ)ϵ 10tQ(γ/t) log(t/γ) = ϵ 10t log(t/γ) log 2n/γ log 2nt/γ if and only if n ≥ 10kt log(t/γ) ϵ log 2nt/γ log 2n/γ .Recalling that t = ⌈C log (R/Q(γ))⌉, we see that this holds under the sample complexity assumption on n. Furthermore, we haveQ avg (γ/t) ≤ Q(γ) if and only if 2τ k log 2t γ n ≤ 2τ k log n γ ⇐⇒ n ≥ log 2t/γ log n/γ ,which is also true by assumption. Therefore, with probability at least 1 -6γ, we have| θall -θ| ≤ O 1 √ γ Var(U n ) + k nϵ 2τ k log 2n γ .Algorithm A.3 uses a constant failure probability of γ = 0.01, which assures a success probability of at least 0.75. This is further boosted by Wrapper 1. Now, an application of Lemma A.6 gives the stated result.Definition A.3. Consider the following estimator: divide the n data points into n/k disjoint chunks, compute h(X S ) on each of these chunks, and apply the CoinPress algorithm [10] to obtain a private estimate of the mean θ. We will call this naive estimator θnaive .The following proposition records the guarantee of the naive estimator θnaive :Proposition A.1. The naive estimator θnaive satisfies| θnaive -θ| ≤ O kζ k n + Õ k √ τ nϵ ,with probability at least 0.9, as long asn = Ω k ϵ log R √ τ .The estimate θnaive is ϵ-differentially private and the algorithm runs in timeÕ n + n k log R √ τ .First, suppose the variance ζ k is known. It is easy to see that dep n,k (F naive ) = k n . By the assumption that h(X S ) is τ -sub-Gaussian, we haveP (|h(X S ) -θ| ≥ y) ≤ 2 exp - y 2 2τ .Hence, with probability at least 1 -γ/m, we haveEQUATIONfor each 1 ≤ j ≤ m, where we use the notation as in the setting of Theorem A.1. By a union bound, we can take the quantile function Q(γ) = 2τ log 2n kγ . Moreover, since the Y j 's are independent, the average 1 m j∈[m] Y j is τ m -sub-Gaussian with variance ζ k m . Therefore, we haveP   1 m m j=1 Y j -θ ≥ y   ≤ 2 exp - my 2 2τ .This yields a bound of Q avg (γ) = 2kτ log(2/γ) n . It remains to verify the conditions of Theorem A.1. We haveEQUATIONQ avg (γ/t) < Q(γ) ⇐⇒ 2kτ log(2t/γ) n ≤ 2τ log(2n/kγ) ⇐⇒ n ≥ k log(2t/γ) log(2n/kγ) ,which are both true by the sample size assumption, noting that t = ⌈C log(R/Q(γ))⌉. Therefore, with probability at least 1 -6γ, we haveθnaive -θ ≤ O 1 √ γ Var( θnaive ) + k nϵ 2τ log(2n/kγ) log 1 γ .Choosing γ to be an appropriate constant, we arrive at the deisred result.Unlike the all-pairs family S all , the subsampled S ss in Definition 2 is randomized. Define θss = M j=1 h(X Sj )/M . Recall from our discussion before (cf. Theorem A.1) that we want each of the h(X Sj )'s, as well as θss , to concentrate around θ, and we also want dep n,k (S ss ) 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 n = Ω((n/k) log n). Then Wrapper 1, with f = ss, failure probability α, algorithm A = U-StatMean (Algorithm A.2), S(I i ) a set of M nα i.i.d. subsets of size k picked with replacement from I i , returns an estimate θss such that, with probability at least 1 -α,| θss -θ| ≤ O Var(U nα ) + Õ ζ k M nα + k 3/2 √ τ n α ϵ , as long as n α = Ω k ϵ log R √ kτ. Moreover, the estimator θss is ϵ-differentially private and runsin time Õ log(1/α) k + log R √ kτ M nα .First, we need the following helper lemmas:Lemma A.7. Define θss = 1 M S∈Fss h(X S ). We have Var θss = 1 -1 M Var(U n ) + 1 M ζ k .Proof. Clearly, E[ θss ] = θ. We compute both terms of the following decomposition of the variance of θss separately; recall thatX = {X i } i∈[n] : Var θss = Var E θss |X + E Var θss |X . Now, Var E θss |X = Var   E   1 M j∈[M ] h (X Si ) X     = Var(U n ),andE Var θss X = E   Var   1 M M j=1 h(X Sj ) X     = 1 M E [Var ( h(X S )| X)] = 1 M E    1 n k S∈I n,k h(X S ) 2 -   1 n k S∈I n,k h(X S )   2    = 1 M ζ k + θ 2 -Var(U n ) + θ 2 = ζ k -Var(U n ) M .Adding the two equalities yields the result.Lemma A.8. Let γ > 0, and let M = Ω( n k log n γ ). Then dep n,k (F ss ) ≤ 4k n with probability at least 1 -γ.Proof. Let Z i be the number of sampled subsets of which i is an element. Observe that Z i ∼ Binom(M, k/n), with mean µ := M k/n. By a Chernoff bound, for any δ > 0 and any i ∈ [n], we haveP (Z i ≥ (1 + δ)µ) ≤ e δ (1 + δ) 1+δ µ . (A.38)By a union bound, we haveP dep n,k (F ss ) > 4k n = P max i Z i > 4µ ≤ n e 3 (1 + 3) 1+3 µ ≤ n exp - M k n ,which is at most γ by our choice of M .Let G γ denote the event that dep n,k (F ss ) ≤ 4k n , which occurs with high probability by Lemma A.8. Note also that conditioned on any family F ss of subsets of I n,k , the run of Algorithm A.2 is ϵdifferentially private. Since the randomness of F ss is independent of the data, the algorithm (along with the private variance estimation) is still 2ϵ-differentially private.LetQ(γ) = 2τ k log 4n γ and Q avg (γ) = 4 τ k min (M, n) log 4n γ .We show that these are indeed the corresponding confidence bounds for Y S , S ∈ F ss and θss .By a sub-Gaussian tail bound, for any S ∈ I n,k , the probability that |h(X S ) -θ| > Q(γ) is at most2 γ 4n k ≤ γ 2n k .By a union bound over all n k sets S, we then have |h(X S ) -θ| ≤ Q(γ) for all S ∈ I n,k , with probability at least 1 -γ 2 . Call this event E γ . Next, E[ θss |X 1 , . . . X n ] = U n . Moreover, for any c > 0,P | θss -θ| ≥ c ≤ P | θss -U n | ≥ c/2 + P (|U n -θ| ≥ c/2) ≤ E X1,...,Xn P | θss -U n | ≥ c/2|X 1 , . . . , X n + 2 exp - nc 2 8kτ ,where we used Lemma A.3 to bound the second term. For the first term in inequality (A. 40) , note that conditioned on the data X 1 , . . . , X n , the h(X Sj )'s are independent draws from a uniform distribution over the n k values {h(X S )} S∈I n,k , with mean U n , and the h(X Sj ) -θ 's are bounded by max S∈I n,k |h(X S )-θ| ≤ Q(γ). Therefore, each h(X Sj )-U n is sub-Gaussian(Q(γ) 2 ), implying thatE P | θss -U n | ≥ c/2|X 1 , . . . , X n ≤ 2E exp - M c 2 8Q(γ) 2 |X 1 , . . . , X n , E γ + P (E c γ ) ≤ 2 exp - M c 2 16τ k log(4n/γ) + P (E c γ ) ≤ 2 exp - M c 2 16τ k log(4n/γ) + γ 2 . (A.39)Combining inequalities (A.40) and (A.39), we haveP | θss -θ| ≥ c ≤ 2 exp - M c 2 16τ k log(4n/γ) + γ 2 + 2 exp - nc 2 8kτ ≤ γ, (A.40)as long asc ≥ 4 τ k min (M, n) log 2n γ log 8 γ .This justifies the choice of Q avg (γ). We now verify the conditions in Theorem A.1. Conditioned on G γ , we have Recalling that t = ⌈C log (R/Q(γ))⌉, we see that the above holds under the sample complexity assumption on n. Furthermore,dep n,k (S) = 4k n ≤ Q(γ)ϵ 10tQ(γ/t)Q avg (γ/t) ≤ Q(γ) iff 4 τ k min (M, n) log 4nt γ ≤ 2τ k log 4n γ ⇐⇒ min(M, n) ≥ log(4nt/γ) 2 log 4n/γ .Since M ≥ n k log n γ , the assumption on the sample complexity of n implies the above result.Conditioned on E γ , the projection steps are never invoked in Algorithm A.2 or A.3, so we have θss = θss + W t+1 , where W t+1 is a Laplace random variable with parameter 2∆ ϵ , where ∆ =dep n,k (F )Q(γ) ϵ(coming from the noise added to 1 M M i=1 Y i in the (t + 1) th step of Algorithm A.2). Finally, using Lemma A.8, we have| θss -θss | = |W t+1 | ≤ 2∆ ϵ log 1 γ = 2dep n,k (S) Q(γ) ϵ log 1 γ ≤ 8k nϵ log 1 γ 2τ k log 4n γon the event G γ . Combined with Lemmas A.6, A.7, inequality (A.40), and Theorem A.1, with probability at least 1 -7γ, we obtain| θss -θ| ≤ O 1 √ γ Var(U n ) + 1 √ γ ζ k M + k nϵ log 1 γ τ k log 4n γ .The success probability is 1 -7γ instead of 1 -6γ because we also require dep n,k (F ss ) ≤ 4k n , which holds with probability 1 -γ as in Lemma A.8. Algorithm A.3 uses a constant failure probability of γ = 0.01, which assures a success probability of at least 0.75. This is further boosted by Wrapper 1. Now, an application of Lemma A.6 gives the stated result.In this appendix, we provide the proofs of our two lower bound results.Lemma A.9 (Lemma 6.2 in [41] ). Let P = {P 1 , P 2 , . . . } be a finite family of distributions over a domain X such that for any i ̸ = j, the total variation distance between P i and P j is at most α. Suppose there exists a positive integer n and an ϵ-differentially private algorithm B : X n → [|P|] such that for every P i ∈ P, we havePr X1,...,Xn∼Pi,B (B(X 1 , . . . , X n ) = i) ≥ 2/3. Then, n = Ω log |P| αϵ .Lemma A.10 (Proposition 4.1 in [4] ). The Bernoulli distribution Bern(p) is sub-Gaussian with optimal variance proxy τ p , whereτ p = τ 1-p = 1 2 -p log 1 p -1 ,for p ∈ (0, 1) \ {1/2}. In particular, if 0 < p < 1/10, then τ p ≤ nϵ and c > 0 is small enough such that kβ < 1/10. The TV-distance between D 0 and D 1 is β. Since n = c βϵ , we also choose c small enough such that Lemma A.9 is violated: for any ϵ-differentially private algorithm B : {0, 1} n → {0, 1}, there exists an i ∈ {0, 1} such thatPr (B(X 1 , . . . , X n ) = i) < 2/3, (A.41)by Lemma A.9.Consider now the task of ϵ-privately estimating the parameterθ(D) := E X1,...,X k ∼D [h(X 1 , X 2 , . . . , X k )] ,whereX i ∼ D and h(X 1 , X 2 , . . . , X k ) = 1 √ τ (1-β) k 1 (X 1 = X 2 = • • • = X k = 1) ,for some distribution D. Suppose there exists an ϵ-differentially private algorithm A such thatE X1,...,Xn∼D,A |A(X 1 , . . . , X n ) -θ(D)| ≤ 1 8 • 1 -(1 -β) k √ τ (1-β) k , (A.42)for any D such that the distribution H of h(X 1 , . . . , X k ) is sub-Gaussian (1) . If D = Bern(1) or Bern(1-β), Lemma A.10 shows that the distribution H of h(X 1 , . . . , X k ) is indeed sub-Gaussian(1). If inequality (A.42) holds, then by Markov's inequality,Pr Xi∼Di |A(X 1 , . . . , X n ) -θ (D i )| ≤ 3 8 • 1 -(1 -β) k √ τ (1-β) k ≥ 2 3 , for i ∈ {0, 1}. Also, θ (D 0 ) = 1/ √ τ 1-β and θ (D 1 ) = (1 -β) k / √ τ 1-β . The difference between these means is θ (D 0 ) -θ (D 1 ) = 1 -(1 -β) k √ τ (1-β) k .Therefore, the following algorithm violates inequality (A.41): Run A on X 1 , . . . , X n to obtain θ. Output 0 if θ is closer to θ(D 0 ) than to θ(D 1 ), and output 1 otherwise.This implies inequality (A.42) does not hold, so we have a lower bound on the expected error. Theorem 1 follows from the calculation1 -(1 -β) k √ τ (1-β) k ≥ kβ 2 • 2 log 1 2 (1 -(1 -β) k ) = Θ kβ log 1 kβ ,where we used 1 -kβ < (1 -β) k < 1 -kβ/2 for kβ < 1/10.Consider two datasets D 0 and D 1 of size n each, differing in at most 1/ϵ data points. SupposeE A |A(D) -U n (D)| < 1 10 |U n (D 0 ) -U n (D 1 )| for D ∈ {D 0 , D 1 }. By Markov's inequality, we have Pr |A(D) -U n (D)| < 1 2 |U n (D 0 ) -U n (D 1 )| ≥ 0.8, for D ∈ {D 0 , D 1 }. Moreover, since A is ϵ-differentially private, we have Pr |A(D 1 ) -U n (D 0 )| < |U n (D 0 ) -U n (D 1 )| 2 ≥ 1 e Pr |A(D 0 ) -U n (D 0 )| < |U n (D 0 ) -U n (D 1 )| 2 ≥ 0.8 e .By the triangle inequality, the event|A(D 1 ) -U n (D 0 )| < |Un(D0)-Un(D1)| 2 is disjoint from the event |A(D 1 ) -U n (D 1 )| < |Un(D0)-Un(D1)|. The sum of the probabilities of these two events is at least 0.8 + 0.8e -1 > 1, a contradiction. Therefore, A has expected error Ω(|U n (D 0 ) -U n (D 1 )|) on at least one of D 0 or D 1 . Next, we will define appropriate choices of D 0 and D 1 .For simplicity, assume 1/ϵ is an integer. Defineb n = ⌈k + k 1/(2k-2) n 1-1/(2k-2) -1 ϵ ⌉. The assumed range of ϵ implies that b n ≥ 2k/ϵ. Let h(x 1 , . . . , x k ) = 1(x 1 = • • • = x k ).We define D 0 such thatx i = 1, i ≤ b n , i, i > b n .We define D 1 = {y 1 , . . . , y n } such that y i = x i for all i ̸ ∈ {b n + 1, . . . , b n + 1/ϵ} andy i = 1 for b n < i ≤ b n + 1 ϵ . Hence, U n (D 1 ) -U n (D 0 ) = bn+1/ϵ k n k - bn k n k.Furhtermore, for k ϵ ≤ b n , using the fact that(1 + x) r ≤ 1 1-rx for x ∈ [-1, 1/r), we have 1 - bn k bn+1/ϵ k = 1 - k-1 i=0 b n -i b n + 1/ϵ -i ≥ 1 - b n b n + 1/ϵ k = 1 -1 - 1/ϵ b n + 1/ϵ k ≥ 1 - 1 1 + k/ϵ bn+1/ϵ = k/ϵ b n + (k + 1)/ϵ , implying that U n (D 1 ) -U n (D 0 ) ≥ k/ϵ b n + (k + 1)/ϵ b n + 1/ϵ k n k . (A.43) For i with x i = 1 in D 0 , we have ĥD0 (i) = ( bn-1 k-1 ) ( n-1 k-1 ) ≤ U n (D 0 ). For i with x i = 1 in D 1 , we have ĥD1 (i) = ( bn +1/ϵ-1 k-1 ) ( n-1 k-1 ) ≤ U n (D 1 ). Therefore, we have | ĥD (i) -U n (D)| ≤ ĥD (i) ≤ ξ for all i and D ∈ {D 0 , D 1 }, where ξ := bn+1/ϵ-1 k-1 n-1 k-1 = k-1 i=1 b n + 1/ϵ -i n -i ≤ b n + 1/ϵ n k-1 = O k n ,by our choice of b n . Moreover, we haveξ ≥ b n + 1/ϵ -k n -k k-1 ≥ k 1/(2k-2) n 1-1/(2k-2) n k-1 = k n . (A.44)By inequality (A.43) and the definition of ξ, we see thatU n (D 1 ) -U n (D 0 ) ≥ k/ϵ b n + 2k/ϵ b n + 1/ϵ n ξ ≥ k 3nϵ ξ,where the second inequality follows from the assumption that k/ϵ ≤ b n . Using the lower bound on ξ as in inequality (A.44), we obtain the desired result.We first prove Theorem 4 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 I n,k :Lemma A.11. Let γ > 0, and letM = Ω n 2 k 2 log n γ .Let S be a collection of M i.i.d sets sampled uniformly from I n,k . For each i ∈ [n], let S i be the number of sets in S containing i, and defineM i = |S i |. For each i ̸ = j ∈ [n], let S ij be the number of sets in S containing i and j, and defineM ij = |S ij |.With probability at least 1 -γ, for all distinct indices i and j, we havek 2n ≤ M i M ≤ 2k n , k 2n ≤ M ij M i ≤ 2k n .Proof. Note that M i ∼ Binom(M, k/n). By a Chernoff bound, for any δ > 0 and any i ∈ [n], we havePr M i - kM n > kM 2n ≤ e -(0.5) 2 (kM/n)/3 ≤ e -Ω( n k log n γ ) ,which is much smaller than γ 2n . Call this event E i , and for the remaining argument, assume E i holds for all i (which, by a union bound, holds with probability at least 1 -γ2 ). This gives the first inequality. For any distinct i, j ∈ [n], conditioned on the value of M i , we have M ij ∼ Binom(m i , (k -1)/(n -1)). By a Chernoff bound, for any δ > 0 and i, j ∈ [n] with j ̸ = i, we havePr M ij - (k -1)M i (n -1) > (k -1)M i 2(n -1) M i ≤ e -(0.5) 2 ((k-1)M i /(n-1)) 3 ≤ e -k 2 M 48n 2 ≤ γ 2n 2 ,using the fact that M i ≥ kM 2n and our assumption on M . The second inequality then follows from a union bound over all pairs of indices.Consider two adjacent datasets X = (X 1 , X 2 , . . . , X n ) andX ′ = (X ′ 1 , X ′ 2 , . . . , X ′ n ) differing only in the index i * , that is, X ′ i = X i for all i ̸ = i * .Throughout the proof, we will use the superscript prime to denote quantities related to X ′ .Let B := (Bad(X) ∪ Bad(X ′ )) \ {i * } and G := (Good(X) ∩ Good(X ′ )) \ {i * }. Then m Ãn -Ã′ n = S∈S (g(X S ) -g(X ′ S )) = S∩B̸ =∅ i * / ∈S (g(X S ) -g(X ′ S )) T1 + S∩B=∅ i * / ∈S (g(X S ) -g(X ′ S )) T2 + i * ∈S (g(X S ) -g(X ′ S )) T3 . (A.45)We bound each of the three terms separately. The term T 2 is equal to 0: all indices i ∈ S have weight 1, and i * / ∈ S, so g(X S ) = h(X S ) = h(X ′ S ) = g(X ′ S ). We prove some preliminary lemmas before bounding the first and last terms. Recall the definitions of L and wt in equations ( 12) and ( 14), respectively. Lemma A.12. We have:(i) |A n -A ′ n | ≤ 2kC n and |L -L ′ | ≤ 1. (ii) For all i ̸ = i * , we have | ĥ′(i) -A ′ n | -| ĥ(i) -A n | ≤ 4kC n , (A.46) |wt(i) -wt ′ (i)| ≤ ϵ, (A.47)and for S, such that i * ̸ ∈ S,|wt(S) -wt ′ (S)| ≤ ϵ. (A.48)Proof. For (i), note that|A n -A ′ n | = 1 M S∈S i * (h(X S ) -h(X ′ S )) ≤ M i C M ≤ 2kC n , (A.49)where the last inequality comes from Lemma A.11. Similarly, for any i ̸ = i * , we have Therefore, if an index i ̸ = i * is in Good(X), using inequalities (A.49) and (A.50), we haveĥ(i) -ĥ′(i) = 1 M i S∈Sij (h(X S ) -h(X ′ S )) ≤ M ij C M i ≤ 2kC n . (A.50)ĥ′(i) -A ′ n ≤ ĥ′(i) -ĥ(i) + ĥ(i) -A n + |A n -A ′ n | (A.51) ≤ 2kC n + ξ + 6kCL n + 2kC n = ξ + kC (4 + 6L) n , which leaves at most 1 + L potential indices i for which | ĥ′(i) -A ′ n | > ξ + 6kC(1+L)n : the indices in Bad(X) and the index i * . Therefore,L ′ ≤ L + 1. Similarly, L ≤ L ′ + 1.For (ii), note that from inequalities (A.49) and (A.50), we have| ĥ′(i) -A ′ n | -| ĥ(i) -A n | ≤ 4kC n for i ̸ = i * .Recalling the definition (14) , this implies that the difference between the weights on an index i can never be greater than ϵ.Finally, note that the weight of a subset S, wt(S) = min i∈S wt(i). Now, by inequality (A.47), each wt(i) differs by ϵ. Say a = arg min i∈S wt(i). In order to make the difference between wt(S) and wt(S ′ ) large we will set wt ′ Next, we show that the weighted Hájek variants ĝ(i) are close to the empirical mean A n and have low sensitivity.Lemma A.13. For all indices i, we have |ĝ(i) -A n | ≤ ξ + 9kCL n + 6kC nϵ . Moreover, if i ̸ = i * , we have |(ĝ(i) -A n ) -(ĝ′(i) -A ′ n )| ≤ ξ + kC(14 + 6L) n ϵ + 10kC n + 4k 2 C n 2 (1 + 2L).Proof. If wt(i) = 0, then g(X S ) = A n for all S ∋ i and ĝ(i) = A n . For clarity, we add a picture of this weighting scheme here: Otherwise, we writeĝ(i) -A n = 1 M i S∈Si (h(X S ) -A n )wt(S) = 1 M i S∈Si (h(X S ) -A n ) wt(i) + 1 M i S∈Si (h(X S ) -A n ) (wt(S) -wt(i)) = ( ĥ(i) -A n )wt(i) + 1 M i S∈Si (h(X S ) -A n ) (wt(S) -wt(i)) . (A.52)From equation ( 14) and the assumption that the weight of index i is strictly positive, the magnitude of the first term in equation (A.52) is bounded by ξ + 6kCL n + 6kC nϵ . For the second term, note that wt(S) = wt(i) unless an index j with a lower weight than i exists. Note that such an index j is necessarily in Bad(X). Therefore, the absolute value of the second term is bounded above by1 mi j∈Bad(X),j̸ =i C ≤ 2kCL n .This proves the first part of the lemma. To bound the sensitivity of ĝ(i), by the triangle inequality, we have( ĥ(i) -A n )wt(i) -( ĥ′(i) -A ′ n )wt ′ (i) ≤ ĥ(i) -A n |wt(i) -wt ′ (i)| + ( ĥ(i) -A n ) -( ĥ′(i) -A ′ n ) wt ′ (i) ≤ ξ + kC (4 + 6L) n + 6kC nϵ ϵ + 6kC n = ξ + kC (10 + 6L) n ϵ + 6kC n , (A.53)where the argument for the second inequality is as follows: To bound the first term, note that when wt(i) = wt ′ (i), it is zero. If wt(i) > 0, then | ĥ(i) -A n | ≤ ξ + 6kCL n + 6kCL nϵ . Now, if | ĥ(i) -A n | > ξ + 6kCL n + 6kCLnϵ + 4kC n , then wt(i) = 0, and by inequality (A.46) of Lemma A.12, we see that | ĥ(i)-A ′ n | > ξ + 6kCL n + 6kCLnϵ , so wt ′ (i) will also be zero. The second term is 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 S, then wt(S) = wt(i). Otherwise, some index j ∈ S has strictly lower weight than i. Such an index j is necessarily in Bad(X) ∪ Bad(X ′ ) because it has weight less than 1. If S also does not contain the index i * , then h(X S ) = h(X ′ S ), so by Lemma A.12, we have|(h(X ′ S ) -A ′ n ) -(h(X S ) -A n )| ≤ |A n -A ′ n | ≤ 2kC n , |(wt ′ (S) -wt ′ (i)) -(wt(S) -wt(i))| ≤ 2ϵ, and letting T S := ((h(X S ) -A n ) (wt(S) -wt(i)) -(h(X ′ S ) -A ′ n ) (wt ′ (S) -wt ′ (i))) , we have |T S | ≤ 2kCn + 2Cϵ. Moreover, there are at most M i,i * sets S containing both i and i * , and for each such set S, the change in (h(X S ) -A n ) (wt(S)wt(i)) is at most 2C, since the weights lie in [0, 1] and |h(X S ) -A n | ≤ C. Combining these bounds, we obtain1 M i S∈Si ((h(X S ) -A n ) (wt(S) -wt(i)) -(h(X ′ S ) -A ′ n ) (wt ′ (S) -wt ′ (i))) T S ≤ 1 M i   S∈Si\S ii * |T S |1(|S ∩ (Bad(X) ∪ Bad(X ′ ))| > 0) + S∈S ii * |T S |   ≤ 2Cϵ + 2kC n 1 M i S∈Si\S ii * 1(|S ∩ (Bad(X) ∪ Bad(X ′ ))| > 0) + 1 M i S∈S ii * 2C ≤ 2Cϵ + 2kC n 1 M i j∈Bad(X)∪Bad(X ′ ) S∈Sij 1 + 2C M i,i * M i ≤ 2Cϵ + 2kC n (|Bad(X)| + |Bad(X ′ )|) sup j∈Bad(X)∪Bad(X ′ ) M i,j M i + 2C M i,i * M i ≤ 2k n 2Cϵ + 2kC n (1 + 2L) + 4kC n , (A.54)where the first inequality uses the fact that the weights are all equal if S ∩ (Bad(X) ∪ Bad(X ′ )) = ∅, and the last inequality uses Lemma A.11. Combining inequalities (A.53) and (A.54) into equation (A.52) yields the result.To bound the term T 1 in (A. 45 ), we decompose it asT 1 = i∈B S∈Si i * / ∈S (g(X S ) -g(X ′ S )) - min(k,|B|) a=2 S∈S |S∩B|=a i * / ∈S (a -1) (g(X S ) -g(X ′ S )) . (A.55)The first term sums over all subsets that contain some element in B. However, this leads to overcounting every subset with a elements in common with B exactly a -1 times. The second term corrects for this over-counting, akin to an inclusion-exclusion argument. The following lemmas bound each of the two terms: Lemma A.14. For all i ∈ B, we have1 M i S∈Si,i * / ∈S (g(X S ) -g(X ′ S )) ≤ ξ + 20kCL n ϵ + 12kC n + 14k 2 CL n 2 .Proof. We have S∈Si i * / ∈S (g(X S ) -g(X ′ S )) = M i (ĝ(i) -ĝ(i)) - S∈S i,i * (g(X S ) -g(X ′ S )) . (A.a=2 S∈S |S∩B|=a i * / ∈S (a -1) |g(X S ) -g(X ′ S )| ≤ 9k 2 L 2 n 2 2Cϵ + 6kC n m.Proof. For any S not containing i * , we have|g(X S ) -g(X ′ S )| = |(h(X S ) -A n )wt(S) + A n -(h(X ′ S ) -A ′ n )wt ′ (S) -A ′ n | ≤ |(h(X S ) -A n )(wt(S) -wt ′ (S))| + |(h(X S ) -h(X ′ S ))wt ′ (S)| + |A n -A ′ n | ≤ 2Cϵ + 6kC n ,using Lemma A.12 and the fact that the second term is zero. Moreover, we havemin(k,|B|) a=2 S∈S |S∩B|=a i * / ∈S (a -1) ≤ k a=2 S∈S |S∩B|=a min(k, |B|) = S∈S |S∩B|≥2 min(k, |B|) ≤ i,j∈B i̸ =j S∈Sij min(k, |B|) ≤ 9k 2 n 2 min(k, |B|)|B| 2 m.The last inequality follows from Lemma A.11, which implies that Mij M = O k 2 n 2 . In the case when S = I n,k , we havemin(k,|B|) a=2 S∈S |S∩B|=a i * / ∈S (a -1) ≤ min(k,|B|) a=2 (a -1) |B| a n -|B| k -a = n k k|B| n -1 + n -|B| k ≤ n k k|B| n -1 + n k 1 - |B| n k ≤ n k k|B| n -1 + n k 1 k|B| n + 1 ≤ k 2 |B| 2 n 2 n k ,where the first equality used the identities , and the third inequality used the fact that (1 -x) k ≤ 1 1+kx for all x ∈ [0, 1]. The statement in the lemma follows because |B| ≤ 2L + 1 ≤ 3L.Combining the results of Lemma A.14 and A.15 yields Lemma A.16. Lemma A.16. We have|T 1 | ≤ kM n ξ + 20kCL n 2ϵ + 24kC n + 28k 2 CL n 2 + 9kL 2 n 2Cϵ + 6kC n γ ,where γ = 4 min(k, 2L). If S = I n,k , then the bound also holds for γ = 1.It remains to bound the third term, T 3 , of equation (A.45), which we do in the following lemma: Lemma A.17. We have|T 3 | ≤ 2k n 2ξ + kC(11 + 18L) n + 12kC nϵ M.Proof. Using Lemmas A.12 and A.13, we have1 M i * |T 3 | = |ĝ(i * ) -ĝ′(i * )| ≤ |ĝ(i * ) -A n | + |ĝ′(i * ) -A ′ n | + |A n -A ′ n | ≤ ξ + 9kCL n + 6kC nϵ + ξ + 9kCL ′ n + 6kC nϵ + 2kC n ≤ 2ξ + kC(11 + 18L) n + 12kC nϵ .The lemma follows after using the fact thatM i * ≤ 2k n M .Combining the bounds on T 1 and T 3 from Lemmas A.16 and A.17 in equation (A.45), the local sensitivity of Ãn at X is then bounded asLS Ãn (X) = O k n ξ + kCL n (1 + ϵL) + k 2 CL 2 min(k, L) n 2 ϵ + kC n + k 2 C n 2 ϵ .Let g(ξ, L, n) denote the upper bound, where to simplify the following argument, we assume the constant prefactor is 1, i.e.,g(ξ, L, n) := k n ξ + kCL n (1 + ϵL) + k 2 CL 2 min(k, L) n 2 ϵ + k n + k 2 C n 2 ϵ .Note that g is strictly increasing in L. Also defineS(X) = max ℓ∈Z ≥0e -ϵℓ g(ξ, L X + ℓ, n). (A.57)Lemma A.18. The function S(X) is an ϵ-smooth upper bound on LS Ãn (X).S(X) = O k n ξ + kC(1/ϵ + L) n (1 + ϵL) + k 2 C(1/ϵ + L) 2 min(k, 1/ϵ + L) n 2 ϵ + k n + k 2 C n 2 ϵ .Proof of Lemma A.18. Clearly, we have S(X) ≥ g(ξ, L X , n) ≥ LS Ãn (X), and for any two adjacent X and X ′ , we have S(X ′ ) = maxℓ∈Z ≥0 e -ϵℓ g(ξ, L X ′ + ℓ, n) ≤ max ℓ∈Z ≥0 e -ϵℓ g(ξ, L X + ℓ + 1, n) = max ℓ∈Z>0 e -ϵ(ℓ-1) g(ξ, L X + ℓ, n) ≤ e ϵ max ℓ∈Z ≥0e -ϵℓ g(ξ, L X + ℓ, n) = e ϵ S(X).This shows that S is indeed a ϵ-smooth upper bound on the local sensitivity. As for the upper bound on S, for any ℓ ≥ 0, we havee -ϵℓ g(ξ, L X + ℓ, n) = k n ξe -ϵℓ/2 + kC(ℓe -ϵℓ/2 + Le -ϵℓ/2) n e -ϵℓ/2 + ϵ(ℓe -ϵℓ/2 + Le -ϵℓ/2 ) + k 2 n 2 C(ℓe -ϵℓ/3 + Le -ϵℓ/3 ) 2 min(ke -ϵℓ/3 , ℓe -ϵℓ/3 + Le -ϵℓ/3 ) ϵ +k n + k 2 Ce -ϵℓ n 2 ϵ ≤ k n ξ + kC(1/ϵ + L) n (1 + ϵ(1 + L)) + k 2 n 2 C 2 ϵ + L 2 min k, 2 ϵ + L ϵ + k n + k 2 C n 2 ϵ ,where we used in multiple places the inequalities e -ϵℓ ≤ 1 and ℓe -ℓ/c ≤ c/e, for any c > 0.By Lemma A.18, it is clear that the term S(X) added to Ãn in Algorithm 1 is the smoothed sensitivity defined in equation (A.57).Therefore, Ãn + S(X) ϵ • Z, where Z is sampled from the distribution with density h(z) ∝ 1/(1 + |z| 4 ), is O(ϵ)-differentially private, by Lemma 2. Moreover, if S = I n,k , the above bound on the smooth sensitivity holds without the min(k, 1/ϵ + L) term, due to Lemma A.15.Utility. By Chebyshev's inequality, we have|A n -θ| ≤ 1 √ γ Var(A n ) = 1 √ γ Var(U n ) + ζ k m ,with probability at least 1 -γ. Moreover, with probability at least 1 -γ, each of the Hájek projections is within ξ of A n . This implies that every index i has weight 1, which further implies that g(X S ) = h(X S ) for all S ∈ S, and consequently, Ãn = A n . Also, L = 1 for such an X. Finally, with probability at least 1 -γ, we have Z ≤ 3 √ γ . Combining these inequalities and using Lemma A.18, we have|A(X) -θ| ≤ Ãn -A n + |A n -θ| + |S(X)/ϵ • Z| = 1 √ γ O Var(U n ) + ζ k m + kξ nϵ + k 2 C n 2 ϵ 2 + k 3 C n 3 ϵ 3 min k, 1 ϵ , (A.58)with probability at least 1 -4γ, recalling that ϵ = O(1) when simplifying the expression. Algorithm 1 uses a constant failure probability of γ = 0.01, which ensures a success probability of at least 0.75. This is further boosted by Wrapper 1. Now, an application of Lemma A.6 gives the stated result.The proof of this theorem proceeds nearly identically to that of Theorem 4 with some exceptions. If S = I n,k , the smoothed sensitivity bound has no min(k, 1/ϵ) term, owing to Lemmas A.15 and A.16, which gives the bound|A(X) -θ| ≤ 1 √ γ O Var(A n ) + kξ nϵ + k 2 C n 2 ϵ 2 + k 3 C n 3 ϵ 3 . (A.59)Furthermore, since S = I n,k , we have A n = U n with probability at least 1 -3γ. Algorithm 1 uses a constant failure probability of γ = 0.01. This ensures a success probability of at least 0.75, which is further boosted by Wrapper 1. An application of Lemma A.6 gives the stated result.Proof of Lemma 3. We first show that if Y 1 , Y 2 , . . . , Y t are random variables such that each Y j is τ j -sub-Gaussian, the sumY 1 + • • • + Y t is √ τ 1 + √ τ 2 + • • • + √ τ t 2 -sub-Gaussian. Define p j = t i=1√ τi √ τj. Clearly, we have t j=1 1/p j = 1. By Hölder's inequality, for any λ > 0, we haveE exp λ t i=1 Y i = E t i=1 exp(λY i ) ≤ t i=1 E [exp(λY i ) pi ] 1/pi ≤ t i=1 exp λ 2 p 2 i τ i 2 1/pi = t i=1 exp λ 2 p i τ i 2 = exp λ 2 ( √ τ 1 + √ τ 2 + • • • + √ τ t ) 2 2 .Now, h(X S ) is sub-Gaussian(τ ) for all S ∈ I n,k . Since ĥ(i) is the average of t = n-1 k-1 such quantities, it is clear from the previous claim that ĥ(i) sub-Gaussian with parameter1 t 2 ( √ τ + √ τ + • • • + √ τ t terms ) 2 = τ.Proof of Lemma 4. Define σ 2 i := Var (h(X Si )|X i = x i ). First, conditioned on X i , the projection ĥ(i) can be viewed as a U-statistic on the other n -1 data points. First, for this lemma, we use S = I n,k , andĥ(i) = E [h(X S )|X i ] = S∈Si h(X S ) n-1 k-1Since h is bounded, the random quantity ĥ(i) -E [h(X S )|X i ] ∈ [-2C, 2C] 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 haveP ĥ(i) -E [h(X S )|X i ] ≥ t X i ≤ 2 exp   -n-1 k-1 t 2 2σ 2 i + 4Ct/3   .which is at most β/n as long as t = σ i 4k n log 2n β + 8Ck n log 2n β .To motivate the test, consider the expectation θ := E[h(X i , X j )] and the variance var(U n ):Lemma A.19. We have E[h(X 1 , X 2 )] = 1 m + ∥a∥ 2 m 2 .In particular, the means under the two hypothesis classes differ by at least δ 2 2m .Proof. We haveE[h(X 1 , X 2 )] = m i=1 p 2 i = m i=1 1 + 2a i + a 2 i m 2 = 1 m + ∥a∥ 2 m 2 .Under approximate uniformity, this is at most δ 2 2m ; and under the alternative hypothesis, this quantity is at least δ 2 m .Lemma A.20. The variance of U n is var(U n ) = 2 n(n -1)   2(n -2) i<j p i p j (p i -p j ) 2 + m i=1 p 2 i - m i=1 p 2 i 2   .Proof. The conditional variances ζ 1 and ζ 2 can be written asEQUATIONζ 2 = cov(h(X 1 , X 2 ), h(X 1 , X 2 )) = m i=1 p 2 i - m i=1 p 2 i 2 .Also from equation (3), we havevar(U n ) = n 2 -1 (2(n -2)ζ 1 + ζ 2 ) .Combining the above bounds with equation (3) shows the result. Algorithm A.4 PrivateUniformityTest n, m, X = {X i } i∈[n] , ϵ 1: C ← 1, γ ← 0.01 2: ξ ← 6/m + 8 log(4n/γ)/n 3: S ← {(i, j) : 1 ≤ i < j ≤ n} 4: θ ← PrivateMeanHájek(n, 2, {1(X i = X j ), (i, j) ∈ S}, ϵ,P | θ -E[U n ]| ≤ δ 2 4m ≥ 1 -O(γ) (A.60)under both hypotheses. Indeed, it would then hold that:(i) Under approximate uniformity,θ < 1 m + δ 2 2m + δ 2 4m = 1 + 3δ 2 /4 m .(ii) Under the alternative hypothesis,θ ≥ 1 m + δ 2 m - δ 2 4m = 1 + 3δ 2 /4 m .To establish inequality (A.60), we further writeP | θ -E[U n ]| > δ 2 4m ≤ P | θ -U n | > δ 2 8m + P |U n -E[U n ]| > δ 2 8m . (A.61)The second term can be controlled using an argument in Diakonikolas et al. [21] , which further develops the variance bound in Lemma A.20 for 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 n = Ω √ m γδ 2 . To bound the first probability term in inequality (A.61), we study the concentration parameter ξ for the local Hájek projection ĥ(i) = 1 n-1 j̸ =i h(X i , X j ). We have the following result: Lemma A.21. If ξ = 6 m + 8 log(4n/γ) n and n ≥ 16 γ , then | ĥ(i) -U n | ≤ ξ for all i, with probability at least 1 -γ.Proof. By the triangle inequality, we have| ĥ(i) -U n | ≤ | ĥ(i) -E[h(X 1 , X 2 )|X 1 ]| + |E[h(X 1 , X 2 )|X 1 ] -θ| + |U n -θ|.(A.62)We will provide a bound on each of these three terms. Note thath(X 1 , X 2 )|X 1 ∼ Bern(p X1 ),which has varianceσ 2 i = var(h(X i , X j )|X i ) = p Xi (1 -p Xi ) ≤ 2 m .Hence, with probability at least 1 -γ 2 , the first term in inequality (A.62) can be bounded as| ĥ(i) -E[h(X 1 , X 2 )|X 1 ]| ≤ 2 2 mn log 4n γ + 16 3n log 4n γ ≤ 2 m + 7 n log 4n γ ,where we have used the AM-GM inequality. The second term in inequality (A.62) can be bounded as1 + a Xi m - 1 m + ∥a∥ 2 m 2 ≤ a Xi m + ∥a∥ 2 m 2 ≤ 2 m .Finally, by Chebyshev's inequality, the third term can be bounded as |U n -θ| ≤ 2var(Un) γ with probability at least 1 -γ 2 . It remains to find the variance of U n . By Lemma A.20, if |a i | ≤ 1 for all i, we havevar(U n ) = 2 n(n -1)   2(n -2) i<j (1 + a i )(1 + a j )(a i -a j ) 2 m 4 + i (1 + a i ) 2 m 2 - i (1 + a i ) 2 m 2 2   ≤ 2 n(n -1)   2(n -2) i<j (1 + a i )(1 + a j )(a i -a j ) 2 m 4 + i (1 + a i ) 2 m 2   ≤ 2 n(n -1) 2(n -2) 4 m 4 m 2 + 4m m 2 ≤ 8 m 2 n + 8 mn 2 . (A.63)Combining the three bounds into inequality (A.62), with probability at least 1 -γ, we have| ĥ(i) -U n | ≤ 2 m + 7 n log 4n γ + 2 m + √ 2 √ γ 2 √ 2 m √ n + 2 √ 2 √ mn = 4 m + 7 log(4n/γ) n + 4/ √ γ m √ n + 4/ √ γ √ mn ≤ 6 m + 8 log(4n/γ) n ,where in the second inequality, we used the AM-GM inequality and the assumption n ≥ 16 γ . The statement of the lemma follows after discarding lower-order terms.with probability at least 1 -γ, where σ 2 i = Var (h(X 1 , X 2 )|X 1 = x 1 ) ≤ πr 2 n . Thus, from Eq A.64, we see that:σ 2 i ≤ πr 2 n ≤ 9πν 2 Moreover, since g is degenerate, we have E[h(X i , X j )|X i ] = θ n . Using the fact that |U n -θ n | ≤ 2Var(Un) γ ≤ 5rn n 1γ with probability at least 1 -O(γ), we havemax i | ĥ(i) -U n | ≤ max i | ĥ(i) -θ n | + |θ n -U n | = 4σ i 1 n log 2n γ + 16 3n log 2n γ + 5r n n 1 γ ≤ 24ν 1 n log 2n γ + 16 3n log 2n γ + 15ν n 1 γ =: ξ,with probability 1 -O(γ). Hence, using Theorem 2, and noting that ξ = Õ rn √ n , we can ensure that the estimate θ output by Algorithm 1 satisfies| θ -θ| = O Var(U nα ) + kξ n α ϵ + k 2 n 2 α ϵ 2 + k 3 n 3 α ϵ 3 C . = O r n n α + ξ n α ϵ + 1 n 2 α ϵ 2 + 1 n 3 α ϵ 3 = Õ r n n α + r n n 3/2 α ϵ + 1 n 2 α ϵ + 1 n 2 α ϵ 2 + 1 n 3α ϵ3 with probability at least 0.75. Wrapper 1 further boosts this probability of success from constant to 1 -α. Now, an application of Lemma A.6 gives the stated result.In this section, we provide more applications of U statistics for important hypothesis testing problems.1. Goodness-of-fit testing: The Cramer-Von Mises statistic for testing the hypothesis that the cumulative distribution function of a random variable is equal to a function F 0 is given by1 n n i=1 n j=1 (1{X i ≤ x} -F 0 (x)) (1{X j ≤ x} -F 0 (x)) dF 0 (x).Under the null H 0 : X ∼ F 0 , the distribution of the statistic is degenerate [58] . Thus, our techniques from Section 4.2 provide a method for private goodness-of-fit testing based on the Cramer-Von Mises statistic. Private goodness-of-fit testing has so far mostly been studied in the setting of discrete data [28, 1, 2] . For continuous distributions, we are only aware of work that analyzes the local DP framework [23, 44, 12] , which is therefore not directly comparable to our proposed approach.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: Yes, we 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 a 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.• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024).The Laplace Distribution with parameter b > 0, denoted Lap(b), has density ℓ(z) ∝ exp (-|z|/b) .Õ(.) hides logarithmic factors in the problem parameters k, n, τ, α, ζ k , where α is the error probability.More precisely, suppose sup x h(x) -infx h(x) ≤ C.The following subsection modifies the algorithm so that the error depends polylogarithmically in α.Assume for simplicity that n is divisible by q and q is an odd integer.Symmetry testing: Testing the symmetry of the underlying distribution of i.i.d. X 1 , . . . , X n is often used in paired tests.[26] use the test statistic i,j (g(X i -X j ) -g(X i + X j ))/n 2 (which is a U statistic plus a lower-order term), where g is the characteristic function of some distribution symmetric around 0. When the distribution of X i is symmetric, this is degenerate. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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).

The main contributions of the paper are as follows:
1) 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).

2) 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.

3) 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.
strength_weakness: strength_weakness: 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.

2) 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.
questions: questions: In equation A.41/42 is S missing from the subscript? Also what is j here? Do you mean $i^*$?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: The calculation of the privacy budget lacks precision.
questions: 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.

2. Following the first point, could the authors discuss the performance of the proposed method across different values of $\epsilon$?
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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. 
3. 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.
4. There are no experimental results to demonstrate the practical performance of the proposed algorithms, which is a significant omission.
5. 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.
questions: questions: 1. What is the asymptotic results of the private U-statistics?
2. How do you ensure get DP estimators for the variance when doing inference?
limitations: limitations: 1. The paper should discuss the differences and potential advantages of the proposed method compared to directly adding noise to the estimators.
2. The authors should include asymptotic normality results for the DP estimators, similar to those available for non-private U-statistics.
3. The paper would benefit significantly from experiments that validate the theoretical findings and demonstrate the practical applicability of the proposed methods.
4. The author should specify the dimension of $X$ and discuss its impact on the results.
paper_summary: paper_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.

The 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. 

The 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).

The 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.
strength_weakness: strength_weakness: 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:

- 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.
- Theorem 2 is not followed by a pointer to its proof in Appendix. Please reference the proof in Appendix.
- 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.
questions: 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: 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.

Comments: title: Further clarifications
Comparison with Acharya et al.
comment: Dear reviewer 8Ha8,

Thank you very much for raising your score. We are very happy that we were able to address most of your concerns, and we will update the manuscript accordingly.
Thanks for the author's response, which addressed most of my concerns. I decide to raise my score to 5.
Dear Reviewer MPw8,

Thank you very much for your response and for raising your score. We will definitely revise our manuscript to incorporate these remarks.
Thank you for the authors' response. I have no further questions. I trust the authors will revise the manuscript appropriately, taking these remarks into account. The score has been raised to 6.
Dear reviewer MPw8,

We hope that our rebuttal has adequately answered your questions on the privacy budget. If there are any further questions we can answer, please do let us know.
Dear Reviewer 8Ha8, we hope our rebuttal has answered most of your questions about dimensionality, distributional convergence, and variance estimation. 

We realize that we somehow overlooked your question about directly adding Laplace noise in the rebuttal. We wanted to take this opportunity to point out that when $h(X_S)$ has additive range $C$, the sensitivity is $kC/n$. Thus, adding Laplace noise with parameter $\frac{kC}{n\epsilon}$ gives an $\epsilon$-private estimate of $E[h(X_S)]$. However, one cannot compute sensitivity without truncation in the unbounded case. As a baseline, we provide the performance of an adapted version of the Coinpress algorithm (which is a state-of-the-art private mean estimation method) in Lemma 3 (Line 130). The algorithm is in Appendix Section A.3 (Algorithm A.2). Table 1 in Section~3 shows that adding noise in accordance to Coinpress, or Laplace noise with parameter $kC/n\epsilon$, overwhelms the non-private error in the degenerate case. Even for non-degenerate settings, the $\zeta_1$ can be much smaller than $C$. For example, the uniformity testing case (Appendix Lemma A.24) shows that $\zeta_1$ can be much smaller than $C$ when $m$ is large. In these settings, the directly added Laplace noise will dominate the non-private error, whereas the non-private error in our method will dominate the error resulting from privacy.

If we can answer any more of your questions, please let us know.
Dear reviewer B5Tq,

Thank you - we really appreciate your support. We will definitely include the discussion regarding the connection between [1] and our method in the paper.
Thank you for your rebuttal. I appreciate the additional details regarding the connection between [1] and your proposed method, which I believe will enhance the paper. I confirm my positive evaluation of your submission.
Thank you - you are correct. In the rebuttal, we inadvertently compared our sample complexity to that of Cai et al. ([34] in Acharya et al.’s paper) from Table 1 in the arXiv version of the NeurIPS paper. Acharya et al. improved upon this, and indeed they have a $\frac{\sqrt{m}}{\delta\sqrt{\epsilon}}$ in their sample complexity, whereas we have a $\frac{\sqrt{m}}{\delta\epsilon}$ term, which is worse. 

We think this may be because the family of distributions they consider are $p$ such that $||p-U||_1 \ge \delta$, where $U$ is the uniform distribution over $m$ atoms. In contrast, we consider $||p-U||_2 \ge \delta/\sqrt{m}$ and $\max_i |p_i - 1/m| \le 1/m$. It is not immediately clear from looking at the lower bound techniques from Acharya et al., which uses coupling and total variation ($\ell_1$) distance-based arguments, whether their lower bounds are tight in the $\ell_2$ setting.

Another thing that we want to note is that [1] points out that the collision-based tester ([3], the non-private version of our algorithm) provides some tolerance or robustness to model misspecification. By updating the rejection rule to “Reject if $\tilde{U}_n \ge \frac{1+3\delta^2/4}{m}$” in Theorem 5 (line 280), we can distinguish between $||p-U||_2 \geq \frac{\delta}{\sqrt{m}}$ and $||p-U||_2\leq \frac{\delta}{\sqrt{2m}}$. Note that the second family is not exactly uniform but approximately uniform.

We will add the comparison to Acharya et al. to our manuscript and clarify these points. We are grateful for your comment.

[1] Canonne, Clément L. Topics and techniques in distribution testing. Now Publishers, 2022.

[2] Cai, Bryan, Constantinos Daskalakis, and Gautam Kamath. “Priv’it: Private and sample efficient identity testing.” International Conference on Machine Learning. PMLR, 2017.

[3] Diakonikolas, Ilias, et al. “Collision-based testers are optimal for uniformity and closeness.” arXiv preprint arXiv:1611.03579 (2016).
Thanks to the authors for their detailed responses. For the Acharya, Ziteng, Zhang result is the bound not better than the one you state (Theorem 2 in that paper seems to give a better bound than the one you cite and they also have a matching lower bound).