# On Differentially Private U Statistics

arXiv: https://arxiv.org/abs/2407.04945 · HTML: https://mlsanity.com/paper/2407.04945/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 61 references that are in the map.
- First posted on arXiv 6 Jul 2024.

## Builds on (most cited first, 17 of 17)

- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing](https://mlsanity.com/paper/1602.03090/) (2016)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Asymptotic Distributions and Rates of Convergence for Random Forests via Generalized U-statistics](https://mlsanity.com/paper/1905.10651/) (2019)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacy](https://mlsanity.com/paper/1905.10477/) (2019)
- [Randomized incomplete U-statistics in high dimensions](https://mlsanity.com/paper/1712.00771/) (2017)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [A Fast Algorithm for Adaptive Private Mean Estimation](https://mlsanity.com/paper/2301.07078/) (2023)
- [Private Protocols for U-Statistics in the Local Model and Beyond](https://mlsanity.com/paper/1910.03861/) (2019)
- [Approximating high-dimensional infinite-order U-statistics: statistical and computational guarantees](https://mlsanity.com/paper/1901.01163/) (2019)
- [On Computing Pairwise Statistics with Local Differential Privacy](https://mlsanity.com/paper/2406.16305/) (2024)

## Built on by (most cited first, 2 of 2)

- [Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA](https://mlsanity.com/paper/2506.12655/) (2025)
- [Learning U-Statistics with Active Inference](https://mlsanity.com/paper/2605.11638/) (2026)

## Abstract (arXiv)

We consider the problem of privately estimating a parameter mathbbE[h(X1,dots,Xk)], where X1, X2, dots, Xk are i.i.d. data from some distribution and h is a permutation-invariant function. Without privacy constraints, standard estimators 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 can be shown to be 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 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/n2) in degenerate settings. To remedy this, we propose a new thresholding-based approach using local H'ajek projections to reweight different subsets of the data. This leads to nearly optimal private error for non-degenerate U-statistics and a strong indication of near-optimality for degenerate U-statistics.