Research map / Federated learning and privacy / Differential privacy
On Differentially Private U Statistics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a computationally efficient differentially private estimator for U-statistics (including degenerate kernels) that preserves statistical efficiency, with subsampling reducing runtime from O(n choose k) to O(n^2) in some regimes.
Problem
Private estimation of E[h(X_1,...,X_k)] via U-statistics, where the standard estimators are costly to privatize and lose efficiency under naive approaches, especially for degenerate kernels.
Approach
Privatizes U-statistics by exploiting the conditional variance structure of the kernel (monotonicity of conditional variances), using subsampling of tuples and a weight function so that the private error matches the non-private variance up to privacy-dependent terms; extended to non-degenerate kernels with a near-matching lower bound.
Key results
- Subsampling with m = Omega(n^2/(k^3 eps^2)) tuples incurs the same error as the all-tuples algorithm while running in O(n^2) time instead of O(n choose k).
- A lower bound of Omega(k/(n eps)) is derived for the non-degenerate case when eps = Omega(k/n), nearly matched by Algorithm 3.
Limitations
- Non-degenerate lower bound holds only for eps = Omega(k/n) and is nearly (not exactly) matched.
- Relaxing boundedness of h requires a coarse private mean estimate and projection, adding complexity.
Experimental setup
Metrics: estimation error
Baselines: naive estimator all-tuples algorithm
Builds on: Kamath et al. (2019) private lower bounds
Closest papers by meaning
- Dimension-free Private Mean Estimation for Anisotropic Distributions (NeurIPS 2024 · similarity 0.86)
- Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy (ICML 2024 · similarity 0.86)
- Privately Learning Smooth Distributions on the Hypercube by Projections (ICML 2024 · similarity 0.86)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.86)
- Instance-Optimality for Private KL Distribution Estimation (NeurIPS 2025 · similarity 0.85)
- Private Statistical Estimation via Truncation (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.