Research map / Federated learning and privacy / Differential privacy
Optimal Survey Design for Private Mean Estimation
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.
Derives a privacy-aware stratified sampling design that minimizes estimator variance for private mean estimation under Laplace, Discrete Laplace, and TuLap mechanisms, using strong convexity to find integer-optimal subsample sizes efficiently.
Problem
Stratified survey sampling under differential privacy: subsampling amplifies privacy but requires group-specific nominal budgets, so naive allocations inflate estimator variance; the optimal integer subsample sizes per stratum are hard to find by exhaustive search.
Approach
Treat stratified sampling as subsampling that amplifies DP, set group-specific nominal budgets so each individual gets the same central DP guarantee, and formulate the allocation as a convex-constrained integer program whose strong convexity yields a ball-based search range for the integer optimum.
Key results
- Under the Laplace mechanism, naive stratified subsampling variance can be up to 2.5 times the optimal design variance for 1<epsilon<10; under TuLap the ratio reaches about 4.
- Closed-form continuous optimum for population mean under Discrete Laplace and TuLap is x_i proportional to tau_i N_i (Neyman-like with a regularization shift); under pure Laplace it is proportional to N_i.
- Algorithm finds integer-optimal designs with total sample size up to 100,000 in less time than exhaustive search takes for eta=30 (10 groups).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · Population mean, ε=0.1 | variance: 1.828 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · Population mean, ε=10^{-1/2} | variance: 2.095 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · Population mean, ε=1 | variance: 2.269 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · Population mean, ε=10^{1/2} | variance: 2.311 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · Population mean, ε=10 | variance: 1.973 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean, ε=0.1 | variance: 2.405 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean, ε=10^{-1/2} | variance: 3.324 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean, ε=1 | variance: 3.877 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean, ε=10^{1/2} | variance: 4.06 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean, ε=10 | variance: 4.076 | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with Laplace noise · A-optimal design | variance: up to 1.8 times | Helped |
| use DP-aware optimal allocation instead of naive allocation | stratified sampling with TuLap noise · Population mean | variance: up to 4 | Helped |
Surprising findings
- Under pure Laplace noise, the optimal continuous allocation for population mean is independent of epsilon and proportional to group size only.
Limitations
- Assumes known population variances per group; no pilot-study estimation.
- Algorithm becomes inefficient when the search radius r is large or number of groups k is large.
- Analysis limited to epsilon-DP with Laplace, DLap and TuLap mechanisms; fixed total sample size constraint.
Experimental setup
Metrics: estimator variance variance ratio computation time optimality gap
Baselines: naive stratified subsampling no-noise Neyman allocation exhaustive search
Builds on: Laplace mechanism Discrete Laplace mechanism Truncated-Uniform-Laplace mechanism privacy amplification by subsampling Neyman allocation
Closest papers by meaning
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.88)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.88)
- A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy (AAAI 2024 · similarity 0.88)
- A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy (NeurIPS 2024 · similarity 0.88)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.88)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.87)
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.