Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
By Mark Bun, Thomas Steinke. 2019
88 citations recorded by the source corpus.
The simplest and most widely applied method for guaranteeing differential privacy is to add instance-independent noise to a statistic of interest that is scaled to its global sensitivity. However, global sensitivity is a worst-case notion that is often too conservative for realized dataset instances. We provide methods for scaling noise in an instance-dependent way and demonstrate that they provide greater accuracy under average-case distributional assumptions. Specifically, we consider the basic problem of privately estimating the mean of a real distribution from i.i.d.~samples. The standard empirical mean estimator can have arbitrarily-high global sensitivity. We propose the trimmed mean estimator, which interpolates between the mean and the median, as a way of attaining much lower sensitivity on average while losing very little in terms of statistical accuracy. To privately estimate the trimmed mean, we revisit the smooth sensitivity framework of Nissim, Raskhodnikova, and Smith (STOC 2007), which provides a framework for using instance-dependent sensitivity. We propose three new additive noise distributions which provide concentrated differential privacy when scaled to smooth sensitivity. We provide theoretical and experimental evidence showing that our noise distributions compare favorably to others in the literature, in particular, when applied to the mean estimation problem.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Florian Tramèr
- Nicholas Carlini
- Nicolas Papernot
- Reza Shokri
- Eric Wallace
- Matthew Jagielski
- Milad Nasr
- Abhradeep Thakurta
Citations in the corpus
- The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
- Measuring Forgetting of Memorized Training Examples (2022, methodology): “The analysis in the remainder of this section will use the mean estimation task, a simple task which is frequently used in the theoretical privacy literature to understand the effectiveness of privacy attacks [31, 66, 19] or design differentially private algorithms [6, 40].”
- Improving Deep Learning with Differential Privacy using Gradient Encoding and Denoising (2020, background): “[4] have shown that the Student-t noise distribution can achieve better utility for trimmed mean applications.”
- CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “Later works studied the multivariate setting [24, 9, 25] and estimation under weaker moment assumptions [7, 26], though these investigations are primarily theoretical.”