# Mean estimation in the add-remove model of differential privacy

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 20 references that are in the map.
- First posted on arXiv 11 Dec 2023.

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

- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms](https://mlsanity.com/paper/1801.09236/) (2018)
- [Plume: Differential Privacy at Scale](https://mlsanity.com/paper/2201.11603/) (2022)
- [Subset-Based Instance Optimality in Private Estimation](https://mlsanity.com/paper/2303.01262/) (2023)

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

- [DPImageBench: A Unified Benchmark for Differentially Private Image Synthesis](https://mlsanity.com/paper/2503.14681/) (2025)
- [InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy](https://mlsanity.com/paper/2507.02974/) (2025)
- [Differential Privacy Under Class Imbalance: Methods and Empirical Insights](https://mlsanity.com/paper/2411.05733/) (2024)
- [Managing Correlations in Data and Privacy Demand](https://mlsanity.com/paper/2509.02856/) (2025)
- [Optimal Variance and Covariance Estimation under Differential Privacy in the Add-Remove Model and Beyond](https://mlsanity.com/paper/2509.04919/) (2025)
- [Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy](https://mlsanity.com/paper/2511.21804/) (2025)
- [Optimality of Staircase Mechanisms for Vector Queries under Differential Privacy](https://mlsanity.com/paper/2601.14597/) (2026)
- [Refined Differentially Private Linear Regression via Extension of a Free Lunch Result](https://mlsanity.com/paper/2604.11820/) (2026)
- [DPrivBench: Benchmarking LLMs' Reasoning for Differential Privacy](https://mlsanity.com/paper/2604.15851/) (2026)

## Abstract (arXiv)

Differential privacy is often studied under two different models of neighboring datasets: the add-remove model and the swap model. While the swap model is frequently used in the academic literature to simplify analysis, many practical applications rely on the more conservative add-remove model, where obtaining tight results can be difficult. Here, we study the problem of one-dimensional mean estimation under the add-remove model. We propose a new algorithm and show that it is min-max optimal, achieving the best possible constant in the leading term of the mean squared error for all ε, and that this constant is the same as the optimal algorithm under the swap model. These results show that the add-remove and swap models give nearly identical errors for mean estimation, even though the add-remove model cannot treat the size of the dataset as public information. We also demonstrate empirically that our proposed algorithm yields at least a factor of two improvement in mean squared error over algorithms frequently used in practice. One of our main technical contributions is a new hour-glass mechanism, which might be of independent interest in other scenarios.