Convergence Rates for Differentially Private Statistical Estimation

By Kamalika Chaudhuri, Daniel J. Hsu. 2012

52 citations recorded by the source corpus.

Differential privacy is a cryptographically-motivated definition of privacy which has gained significant attention over the past few years. Differentially private solutions enforce privacy by adding random noise to a function computed over the data, and the challenge in designing such algorithms is to control the added noise in order to optimize the privacy-accuracy-sample size tradeoff. This work studies differentially-private statistical estimation, and shows upper and lower bounds on the convergence rates of differentially private approximations to statistical estimators. Our results reveal a formal connection between differential privacy and the notion of Gross Error Sensitivity (GES) in robust statistics, by showing that the convergence rate of any differentially private approximation to an estimator that is accurate over a large class of distributions has to grow with the GES of the estimator. We then provide an upper bound on the convergence rate of a differentially private approximation to an estimator with bounded range and bounded GES. We show that the bounded range condition is necessary if we wish to ensure a strict form of differential privacy.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science

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 Computer Science Applications

In Sociology and Political Science

Citations in the corpus

Extremal Mechanisms for Local Differential Privacy (2014, neutral): “These results follow from our main theorems and are of independent interest in other applications where lower bounds in statistical analysis are studied [3, 21, 6, 9].”
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (2014, methodology): “Sample complexity of more general problems in statistics was investigated in a number of works starting with the work of Dwork and Lei [2009] (measured alternatively via convergence rates of statistical estimators) [Smith, 2011, Chaudhuri and Hsu, 2012, Duchi et al., 2013a,b].”
A rate-disortion perspective on local differential privacy (2014, background): “Extending the framework to continuous sources may be challenging due to to range issues [20].”
A ug 2 01 4 Local Privacy , Data Processing Inequalities , and Minimax Rates (2018, background): “Chaudhuri and Hsu [15] provide lower bounds for estimation of certain one-dimensional statistics based on a twopoint family of problems.”
Statistical Approximating Distributions Under Differential Privacy (2018, background): “The ability to use differential privacy to protect data has raised the question of how useful would the data be in statistical applications [Wasserman and Zhou, 2010, Fienberg et al., 2010, Dwork and Lei, 2009, Vu and Slavkovic, 2009, Smith, 2011, Chaudhuri and Hsu, 2012].”
Local Privacy and Statistical Minimax Rates (2013, background): “[3], Hardt and Talwar [17], and De [6]; Chaudhuri and Hsu [4] also provide a type of lower bound for certain one-dimensional (population) statistics based on two-point families of estimators.”
Differential Privacy and Machine Learning: a Survey and Review (2014, unknown): “[4] explores robust estimators in another way.”
The Large Margin Mechanism for Differentially Private Maximization (2014, result): “Lower bounds for approximate differential privacy have been shown by [7, 16, 11, 9], and the proof of our Theorem 1 borrows some techniques from [11].”
Differential privacy for functions and functional data (2012, background): “(2010), Chaudhuri and Monteleoni (2008), Smith (2011), Chaudhuri and Monteleoni (2011), Nissim et al.”
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals (2018, background): “Several works have studied the intersection of differential privacy and statistics (Dwork and Lei, 2009; Smith, 2011; Chaudhuri and Hsu, 2012; Duchi et al., 2013a,b; Dwork et al., 2015) mostly focusing on robust statistics; but only a handful of works study rigorously the significance and power of h”
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso (2013, background): “The output of f̂(D) is the mode (most frequently occurring value) in the list F = (f(D̂1), ..., f(D̂m)) where the D̂i’s are random subsamples of size about n/ log(1/δ).”
Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates (2013, background): “Chaudhuri and Hsu [14] provide lower bounds for estimation of certain one-dimensional statistics based on a twopoint family of problems.”
Revisiting Differentially Private Hypothesis Tests for Categorical Data (2015, methodology): “Chaudhuri and Hsu (2012) established a formal connection between differential privacy and robust statistics by deriving convergence rates in terms of a concept called gross error sensitivity. Dwork et al. (2015) presented a framework for controlling the false discovery rate of a large sequence of hy”