Research map / Federated learning and privacy / Differential privacy
Mean Estimation in the Add-Remove Model of Differential Privacy
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 a transformed-noise mean estimator with a new two-dimensional "hourglass" noise distribution that achieves min-max optimal MSE for one-dimensional mean estimation under the add-remove DP model, matching the swap model constant.
Problem
Optimal mean squared error for one-dimensional mean estimation under add-remove differential privacy, where the dataset size is not public, and whether it is inherently harder than under the swap model.
Approach
Apply a linear transformation to the scaled sum and complementary count so that the sensitivity space fits a tight l1 ball, then add a new 2D hourglass noise distribution whose sensitivity set matches the actual non-convex neighboring-dataset sensitivity space, with marginals equal to the univariate staircase mechanism.
Key results
- The hourglass-based algorithm achieves normalized MSE matching the swap-model lower bound sigma^2(epsilon), showing add-remove and swap models have equivalent optimal error up to 1+o(1).
- In the high-privacy regime the transformed Laplace algorithm reduces error by roughly a factor of two over the standard independent-noise algorithm, matching the ratio of upper bounds (4 vs 2).
- The hourglass mechanism continues to match the lower bound as epsilon grows, while the two-dimensional staircase mechanism's error stays larger, outperforming it at large epsilon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use transformed sensitivity coordinates with hourglass noise instead of the two-dimensional staircase mechanism | Transformed noise mean estimator · Add-remove mean estimation, low privacy | MSE | Helped |
| use transformed sensitivity coordinates and Laplace noise instead of shifted independent noise addition | Add-remove mean estimation · High privacy | MSE: roughly a factor of two | Helped |
| replace hourglass noise with independent Laplace noise (ablation) | Transformed noise mean estimator · Add-remove mean estimation, high privacy | MSE: \frac{2(u-l)^2}{|D|^2\varepsilon^2} \left( 1 + o(1)\right) | Hurt |
| replace hourglass noise with the two-dimensional staircase mechanism (ablation) | Transformed noise mean estimator · Add-remove mean estimation, low privacy | MSE | Hurt |
| shift inputs by the range midpoint before independent sum-and-count noise addition (ablation) | Independent noise addition · Add-remove mean estimation | MSE: \frac{4(u-l)^2}{\varepsilon^2} \left( 1 + o(1) \right) | Helped |
| use transformed sum-and-count coordinates rather than shifted sum-and-count noise addition | Add-remove mean estimation, high privacy · Add-remove mean estimation | MSE: roughly a factor of two | Helped |
| use hourglass noise rather than two-dimensional staircase noise | Transformed noise mean estimator · Add-remove mean estimation, ε = 4.0 and μ = 0.01 | MSE | Helped |
Surprising findings
- The add-remove model, which protects dataset size, achieves the same leading-constant error as the swap model, answering that it is not inherently harder.
Limitations
- Results are asymptotic (1+o(1)) in the dataset size and hold for large datasets; small-dataset performance is only checked empirically.
- Experiments are restricted to synthetic i.i.d. data on [0,1] with a single dataset size of 10,000 in the main plots.
Experimental setup
Datasets: synthetic i.i.d. datasets on [0,1] with varying mean
Benchmarks: synthetic mean estimation on [0,1]
Metrics: normalized mean squared error min-max MSE ratio to lower bound
Baselines: Independent noise addition (add-remove standard algorithm) Shifted noise addition Two-dimensional staircase mechanism Laplace mechanism swap-model optimum
Builds on: staircase mechanism Laplace mechanism vector Laplace mechanism
Closest papers by meaning
- Instance-optimal Mean Estimation Under Differential Privacy (NeurIPS 2021 · similarity 0.90)
- A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy (NeurIPS 2024 · similarity 0.87)
- A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy (AAAI 2024 · similarity 0.87)
- Differentially Private Model Merging (NeurIPS 2026 · similarity 0.86)
- Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy (ICML 2024 · similarity 0.86)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · 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.