Finite Sample Differentially Private Confidence Intervals

By Vishesh Karwa, Salil P. Vadhan. 2017

224 citations recorded by the source corpus.

We study the problem of estimating finite sample confidence intervals of the mean of a normal population under the constraint of differential privacy. We consider both the known and unknown variance cases and construct differentially private algorithms to estimate confidence intervals. Crucially, our algorithms guarantee a finite sample coverage, as opposed to an asymptotic coverage. Unlike most previous differentially private algorithms, we do not require the domain of the samples to be bounded. We also prove lower bounds on the expected size of any differentially private confidence set showing that our the parameters are optimal up to polylogarithmic factors.

Subfields: Artificial Intelligence, Public Health, Environmental and Occupational Health

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

In Public Health, Environmental and Occupational Health

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “We know there are regimes where statistical problems can be solved privately “for free” asymptotically (e.g. [DMNS06, CMS11, Smi11, KV18]) and others where there is a signiﬁcant cost, even for relaxed deﬁnitions of privacy (e.g. [BUV14, DSS + 15]), and we remain far from a general characterization o”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “(3)These boundedness conditions are also provably necessary to learn even a single univariate Gaussian for pure differential privacy, concentrated differential privacy, or Rényi differential privacy, by the argument of [50].”
Private Mean Estimation of Heavy-Tailed Distributions (2020, unknown): “We do that in a way similar to that of Karwa and Vadhan (2018). To summarize, we use differentially private histograms (Lemma 29) to find the bucket with the largest number of points.”
Private Hypothesis Selection (2019, background): “Then there exists a ( ε, δ ) -diﬀerentially private algorithm which outputs a spherical Gaussian distribution H ∗ such that d TV ( P, H ∗ ) ≤ 7 α with probability ≥ 1 − 2 − d , so long as Karwa and Vadhan [KV18] give an algorithm for estimating a univariate Gaussian with un-bounded mean.”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “Recently, [42] use coupling to prove lower bounds on the sample complexity for differentially private confidence intervals.”
Differentially Private Nonparametric Hypothesis Testing (2019, background): “Karwa and Vadhan [16] study private confidence intervals, which are in a sense equivalent to a t-test.”
Differentially Private Uniformly Most Powerful Tests for Binomial Data (2018, background): “Karwa and Vadhan (2017) develop nearly optimal conﬁdence intervals for normally distributed data with ﬁnite sample guarantees, which could potentially be inverted to give UMP-unbiased tests.”
CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “The most relevant line of work is that initiated by Karwa and Vadhan [27], studying private parameter estimation for Gaussian data focused on important issues for practice like dealing with weak a priori bounds on the parameters.”
Locally Private Gaussian Estimation (2018, background): “Karwa and Vadhan [18] and Kamath et al. [17] consider similar versions of Gaussian estimation under global differential privacy, respectively in the one-dimensional and highdimensional cases.”
Privately Learning High-Dimensional Distributions (2018, methodology): “When κ is a constant, we can obtain such a guarantee in a relatively straightforward way by applying the mean-estimation procedure for univariate Gaussians due to Karwa and Vadhan Karwa and Vadhan (2018) to each coordinate.”
Differentially Private Assouad, Fano, and Le Cam (2020, unknown): “, 2019) and coupling based arguments (Acharya et al., 2018b; Karwa and Vadhan, 2018).”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, background): “Kamath, Li, Singhal, and Ullman [22] extend the work of Karwa and Vadhan to learning multivariate Gaussians.”