Research map / Federated learning and privacy / Differential privacy
Improving the Variance of Differentially Private Randomized Experiments through Clustering
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.
Proposes Cluster-DP, a label-differentially-private mechanism that privatizes user-level outcomes in randomized experiments by resampling from cluster-specific transformed empirical distributions, so that higher-homogeneity clusters reduce the variance penalty at the same privacy level.
Problem
Differential privacy for outcomes in randomized experiments inflates estimator variance when estimating average treatment effects, creating a privacy-variance trade-off; non-sensitive cluster structure is available but unused by existing mechanisms.
Approach
Privatize outcomes per cluster using a truncated, Laplace-noised empirical response distribution (adapted from a label-DP technique) mixed with resampling, and debias via inverse response randomization matrices, so the variance gap depends on cluster homogeneity while the privacy guarantee does not.
Key results
- Cluster-DP achieves lower estimator variance than Cluster-Free-DP and Uniform-Prior-DP at the same privacy loss (epsilon=0.2, delta=1e-4) in the Gaussian mixture simulation.
- The variance reduction from clustering grows as cluster homogeneity increases (larger beta) and is stronger at smaller resampling probability lambda.
- On the YouTube subset, Cluster-DP gives a better privacy-variance trade-off than Cluster-Free-DP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Cluster-DP with cluster information instead of Cluster-Free-DP | Cluster-DP · Gaussian mixture simulation | variance | Helped |
| use Cluster-DP instead of stratified or unstratified Uniform-Prior-DP at small gamma | Cluster-DP · Gaussian mixture simulation, ε = 0.2 and δ = 10^-4 | variance | Helped |
| set gamma to 1/K with sigma = 10 (ablation) | Cluster-DP · Gaussian mixture simulation | variance | Hurt |
| optimize sigma and gamma (ablation) | Cluster-DP · Gaussian mixture simulation, δ = 10^-4 | privacy-variance trade-off | Helped |
| use Cluster-DP instead of Cluster-Free-DP | Cluster-DP · Gaussian mixture simulation, δ = 10^-4 | privacy-variance trade-off | Helped |
| increase cluster quality by increasing beta (ablation) | Cluster-DP · Gaussian mixture simulation | variance relative to Cluster-Free-DP | Helped |
| use a smaller resampling probability lambda (ablation) | Cluster-DP · Gaussian mixture simulation | variance relative to Cluster-Free-DP | Helped |
| use Cluster-DP with natural cluster information instead of Cluster-Free-DP | Cluster-DP · YouTube social network simulation | privacy-variance trade-off | Helped |
| use more homogeneous clusters | Cluster-DP · Randomized experiments | variance gap | Helped |
Surprising findings
- For the simulated setting with sigma=10, Uniform-Prior-DP at gamma=1/K has lower variance than the other mechanisms, i.e. the data-dependent prior does not always win.
Limitations
- Variance gap bound includes a clustering-agnostic term A(x) that can dominate; privacy guarantee does not depend on cluster quality so gains are only via variance.
- Assumes non-sensitive cluster structure; privatizing clusters requires extra privacy budget via composition.
- Experiments are on simulated and semi-synthetic data only, with finite discrete outcome spaces (outcomes must be binned).
Experimental setup
Datasets: YouTube social network (SNAP/com-YouTube communities)
Benchmarks: YouTube social network subset (50 largest communities)
Metrics: variance of the ATE estimator privacy loss epsilon variance ratio to non-private estimator
Baselines: Uniform-Prior-DP Cluster-Free-DP Noisy Horvitz-Thompson Noisy Histogram
Builds on: label differential privacy randomized response Horvitz-Thompson estimator
Closest papers by meaning
- A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy (AAAI 2024 · similarity 0.87)
- Making Old Things New: A Unified Algorithm for Differentially Private Clustering (ICML 2024 · similarity 0.87)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.87)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.87)
- Privacy Profiles for Private Selection (ICML 2024 · similarity 0.86)
- Differentially Private Analysis for Binary Response Models: Optimality, Estimation, and Inference (ICML 2025 · similarity 0.86)
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.