Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates

By John C. Duchi, Michael I. Jordan, Martin J. Wainwright. 2013

116 citations recorded by the source corpus.

Working under a model of privacy in which data remains private even from the statistician, we study the tradeoff between privacy guarantees and the utility of the resulting statistical estimators. We prove bounds on information-theoretic quantities, including mutual information and Kullback-Leibler divergence, that depend on the privacy guarantees. When combined with standard minimax techniques, including the Le Cam, Fano, and Assouad methods, these inequalities allow for a precise characterization of statistical rates under local privacy constraints. We provide a treatment of several canonical families of problems: mean estimation, parameter estimation in fixed-design regression, multinomial probability estimation, and nonparametric density estimation. For all of these families, we provide lower and upper bounds that match up to constant factors, and exhibit new (optimal) privacy-preserving mechanisms and computationally efficient estimators that achieve the bounds.

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

Citations in the corpus

Discrete Distribution Estimation under Local Privacy (2016, background): “(Duchi et al., 2013a;b) was the ﬁrst to apply differential privacy to the local setting, to study the fundamental trade-off between privacy and minimax distribution estimation in the high privacy regime, and to introduce the core of k -”
Privacy Aware Learning (2012, methodology): “Then, we have the j= following lemma [Duchi et al. 2013, Lemma 6], which applies as long as the channel Q is non-interactive and a-locally differentially private.”
Privacy-Preserving Stochastic Gradual Learning (2018, background): “Recently, Duchi et al. invented a novel strategy called private sampling [23], which imposes stringent local privacy for any d -dimensional mean-estimation problem [39].”
Locally differentially-private distribution estimation (2016, methodology): “In addition, he is constrained to using a memoryless privatization strategy, sometimes referred to as non-interactive mechanism [8], [9].”