The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information

By John C. Duchi, Feng Ruan. 2018

59 citations recorded by the source corpus.

We identify fundamental tradeoffs between statistical utility and privacy under local models of privacy in which data is kept private even from the statistician, providing instance-specific bounds for private estimation and learning problems by developing the \emph{local minimax risk}. In contrast to approaches based on worst-case (minimax) error, which are conservative, this allows us to evaluate the difficulty of individual problem instances and delineate the possibilities for adaptation in private estimation and inference. Our main results show that the local modulus of continuity of the estimand with respect to the variation distance---as opposed to the Hellinger distance central to classical statistics---characterizes rates of convergence under locally private estimation for many notions of privacy, including differential privacy and its relaxations. As consequences of these results, we identify an alternative to the Fisher information for private estimation, giving a more nuanced understanding of the challenges of adaptivity and optimality, and provide new minimax bounds for high-dimensional estimation showing that even interactive locally private procedures suffer poor performance under weak notions of privacy.

Subfields: Privacy & Security, Information Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

In Information Theory

Citations in the corpus

Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, background): “In the case of local diﬀerential privacy, however, as Duchi and Ruan [27] demonstrate, (optimal) locally private estimators typically have the form where W i is a noise term that must be taken so that ψ ( x ) and ψ ( x (cid:48) ) are indistinguishable for all x, x (cid:48) .”
The structure of optimal private tests for simple hypotheses (2018, methodology): “Our characterization of private testing implies similar lower bounds for estimation (along the lines of lower bounds of Duchi and Ruan [27] in the local model of differential privacy).”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “, 2019) and challenges of high-dimensional problems (Duchi et al., 2018; Duchi and Ruan, 2018), it is important to address limits in the case that ε 1.”
Private Hypothesis Selection (2019, background): “There has also been a great deal of work on distribution learning in the local model of diﬀerential privacy [DJW13, WHW + 16, KBR16, ASZ19, DR18, JKMW18, YB18, GRS19].”
Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data (2019, background): “We note that these assumptions are quite common in related work such as (Wang and Xu, 2019; Duchi and Ruan, 2018).”