Minimax Optimal Procedures for Locally Private Estimation

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

516 citations recorded by the source corpus.

ABSTRACT Working under a model of privacy in which data remain private even from the statistician, we study the tradeoff between privacy guarantees and the risk of the resulting statistical estimators. We develop private versions of classical information-theoretical bounds, in particular those due to Le Cam, Fano, and Assouad. These inequalities allow for a precise characterization of statistical rates under local privacy constraints and the development of provably (minimax) optimal estimation procedures. We provide a treatment of several canonical families of problems: mean estimation and median estimation, generalized linear models, 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. Additionally, we present a variety of experimental results for estimation problems involving sensitive data, including salaries, censored blog posts and articles, and drug abuse; these experiments demonstrate the importance of deriving optimal procedures. Supplementary materials for this article are available online.

Subfields: Artificial Intelligence, Economics and Econometrics, Statistics and Probability, Privacy & Security

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 Economics and Econometrics

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, methodology): “Our proposed mechanism is a combination of the private-mechanism Priv of Duchi et al. [DJW18, Section 4 .”
Differentially Private Meta-Learning (2019, background): “ cannot be trusted, thus requiring a random mechanism to be applied individually on each zbefore training. However, it generally results in worse model performance, suffering from hard minimax rates (Duchi et al., 2018). 4 Published as a conference paper at ICLR 2020 Table 1: Broad categorization of”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, methodology): “Thus, comparing to the earlier guarantees of Duchi et al. [31], we see that this hypercube-cap-based method we present in Algorithm 2 obtains no worse error in all cases of ε , and when ε ≥ log d , the dependence on ε is substantially better.”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, it is well understood theoretically and empirically that utility outcomes are far worse in the LM than in the TCM [11, 16, 22, 27, 38].”
Collecting Telemetry Data Privately (2017, methodology): “BinFlip (equivalently, 32BitFlipPM) has the best accuracy overall.”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, methodology): “[14] show that for close to 0 the minimax risk (5) behaves as r (2)2 ,k,n = k n 2 and r 1 ,k,n = k √ n .”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, methodology): “’s solution [14] for the onedimensional case.”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “1) Encode: Given a current state θ t , apply ε (cid:96)e -DP random-izer from [17] to the gradient at θ t on all (or a subset of) the data samples in D .”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “The other players can choose their channels upon observing these messages (Duchi et al., 2013b; Qin et al., 2016; Duchi et al., 2017).”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, methodology): “In full generality, we allow the channel to be sequentially interactive [21], meaning that at observation i , the channel may depend on the previous (private) observations Z 1 , . . . , Z i − 1 .”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, methodology): “Our non-interactive privacy mechanisms use classical Laplace randomization – see, for example, Duchi et al. [2018].”
The Role of Interactivity in Local Differential Privacy (2019, methodology): “[16] obtained an analogue of Assouad’s method for proving lower bounds for sequentially interactive locally private protocols.”
Asymptotically optimal private estimation under mean square loss (2017, methodology): “In this subsection we illustrate the main ideas that lead to determining the dominant term of r In view of (10)–(12) we need to show that lim n nr Lower bounds on r ǫ,k,n can be derived using Assouad’s method; see [13], [14].”
Local Differential Privacy-Based Federated Learning for Internet of Things (2020, methodology): “’s [22] solution contains two output possibilities, and it outperforms other approaches when the privacy budget is small.”
Differential Privacy for Deep and Federated Learning: A Survey (2022, background): “It is inspired from [135]–[138] with an efﬁcient communication enhancement and stronger protection for repeated data collection.”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, background): “[6, 5] gave the lower bound O( √ d √ n ) and optimal”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “[15], by developing a locally private counterpart of some of the well-known information-theoretic tools for establishing statistical lower bounds (namely, Le Cam, Fano, and Assouad), establish tight or nearly tight bounds for several mean estimation problems in the LDP setting.”
Private Mean Estimation of Heavy-Tailed Distributions (2020, background): “Among other problems, Duchi, Jordan, and Wainwright [DJW13, DJW17] study univariate mean estimation with moment bounds under the stricter constraint of local differential privacy.”
Private Heavy Hitters and Range Queries in the Shuffled Model (2019, background): “Furthermore, motivated by risk bounds under privacy constraints, Duchi et al. [23] provided private versions of information-theoretic bounds for minimax risk of M-estimation of the median.”