On Differentially Private U Statistics

Thank you for mentioning that our work addresses a notable gap in differential privacy research and for your kind words on its wide applicability. In a revision, we will add pointers to the proofs of all theorems immediately after their statements.

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

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

[Re: Limitations]: As per your suggestion, we will compile the limitations of our methods from different parts of the paper to one dedicated section.

[1] J. Ullman and A. Sealfon. Efficiently estimating Erdos-Renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32, 2019.

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 kind words regarding the solid theoretical foundations and wide applicability of our work.

[Re: Asymptotic distribution]: To our knowledge, differential privacy results typically focus on finite sample guarantees.

We show under mild conditions on $n,k,$ and $\epsilon$ that our estimator has the same asymptotic distribution as the non-private U statistic in the degenerate (of order $1$) and non-degenerate cases. Thus, the asymptotic variance doesn’t change.

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

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

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

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

[Re: Private confidence intervals]: Our goal is not to provide a confidence interval but finite sample error guarantees. If desired, the variance of a U-statistic could be computed using our method since it also involves a U-statistic of degree $2k-1$. However, our algorithms require an upper bound on the ratio between $\tau$ and the $\zeta_k = \textup{var}(h(X_S))$, similar to the state-of-the-art algorithms for private mean estimation [1,2]. Lemma A.7 (lines 588-591) shows how to estimate the variance $\zeta_k$ within a multiplicative factor. We will discuss this in more detail.

[Re: Dimension]: First, we do not require $X_i$ to be scalars; rather, $h(X_S)$ is assumed to be a scalar. In fact, for our application to sparse graphs, $X_i$ are latent vectors in $\mathbb{R}^d$ (lines 301-304).

In fact, our techniques easily generalize when $h(X_S)\in \mathbb{R}^d$, as we show next.

Lemma 2.10 in [3] shows that if $Z\sim N(0,I_d)$ is a $d$ dimensional Gaussian and $S(X)$ is a $\beta$-smooth upper bound on the local sensitivity, then adding noise equal to $S(X)/\alpha Z$ achieves $(\epsilon,\delta)$-DP, where $\alpha = \frac{\epsilon}{5\sqrt{2 \log(2/\delta)}}$ and $\beta=\frac{\epsilon}{4(d+\log(2/\delta))}$.

For simplicity, let $\mathcal{S} = I_{n,k}$. Consider $h(X_S)$ lying in an $\ell_2$-ball of radius $C$. In Algorithm 1, the sets in lines 5 and 6 should be modified to have the $\ell_2$ distance $||\hat{h}(i)-A_n||_2$. In line 8, the weights to the indices should be based on the ($\ell_2$) distances from the ball $\mathbb{B}\left(0, \xi+4kCL/n\right)$. Finally, the $\epsilon$ in every step except line 15 should be replaced with $\beta$, the $\epsilon$ in the last step should be replaced with $\alpha$, and $Z \sim \mathcal{N}(0, I_d)$.

We can show that Lemma A.20 (line 831) holds with $\beta$ as above. With probability at least 3/4, $L = 1$ and $S(X) = O\left(\frac{k\xi}{n}+\frac{k^2Cd}{n^2\epsilon}+\frac{k^2Cd}{n^2\epsilon} + \frac{k^3Cd^2}{n^3\epsilon^2}\right).$ The noise added in line 15 is $S(X)/\alpha \cdot Z$.

In all, with constant success probability,

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

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

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

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

[Re: Performance across different $\epsilon$]: We assume $\epsilon=O(1)$. But the dependence of the private error of our algorithm on $\epsilon$ nearly matches our lower bound for both degenerate and non-degenerate settings. See Table 1 (page 4).

[1] K. Nissim, S. Raskhodnikova, and A. Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC '07). Association for Computing Machinery, New York, NY, USA, 75–84.

[2] S. Biswas, Y. Dong, G. Kamath, and J. Ullman. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems, 33:14475–14485, 2020.

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 your valuable feedback and for noting that our estimator based on local Hájek projections (and smooth sensitivity) is technically novel and interesting.

[Re: Comparison of our applications with existing private algorithms]: The setting we consider, where the probabilities of the atoms in the distribution are close to uniform, has not been considered in literature before. However, there are existing private algorithms in the more general setting, which when restricted to our setting lead to suboptimal guarantees in the privacy parameter $\epsilon$.

[2] considers the $\ell_1$ distance between the distributions $(p_1, p_2, \dots, p_m)$ and the uniform distribution $(1/m, 1/m, \dots, 1/m)$ on a set of $m$ atoms. Our assumption of $\sum_i(p_i-1/m)^2\leq \delta^2/m$ implies a bound of $\delta/2$ on the $\ell_1$-distance considered in [2]. The collision-based statistic we consider is simpler than that in [2]. While they consider a broader class of probability distributions over the atoms, their sample complexity $O\left(\frac{\sqrt{m}}{\delta^2} + \frac{\sqrt{m\log m}}{\delta^{3/2}\epsilon} \right )$ has a worse factor in $\delta$ compared the sample complexity $O\left( \frac{\sqrt{m}}{\delta^2} + \frac{\sqrt{m}}{\delta \epsilon} + \frac{\sqrt{m} \log(m/\delta \epsilon)}{\delta \epsilon^{1/2}} \right)$ of our algorithm. We will incorporate this into the revision and elaborate on the comparison.

[Re: Connection between [1] and our algorithm]: We will more clearly describe the connection of our algorithm with the algorithm of [1].

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

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

[Re: Typographical error in Eq A.41/A.42]: Yes, the index $j$ should be $i^*$. In equation A.41, we are summing over $S$ such that $S \in \mathcal{S}_{i, i^*}$. We will correct this and other typographical errors in the final version.

[1] J. Ullman and A. Sealfon. Efficiently estimating erdos-renyi graphs with node differential privacy. Advances in Neural Information Processing Systems, 32, 2019.

[2] J. Acharya, S. Ziteng, and H. Zhang. “Differentially private testing of identity and closeness of discrete distributions.” Advances in Neural Information Processing Systems 31 (2018).

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

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