Lower Bounds for Locally Private Estimation via Communication Complexity

By John C. Duchi, Ryan M. Rogers. 2019

107 citations recorded by the source corpus.

We develop lower bounds for estimation under local privacy constraints---including differential privacy and its relaxations to approximate or Renyi differential privacy---by showing an equivalence between private estimation and communication-restricted estimation problems. Our results apply to arbitrarily interactive privacy mechanisms, and they also give sharp lower bounds for all levels of differential privacy protections, that is, privacy mechanisms with privacy levels $\varepsilon \in [0, \infty)$. As a particular consequence of our results, we show that the minimax mean-squared error for estimating the mean of a bounded or Gaussian random vector in $d$ dimensions scales as $\frac{d}{n} \cdot \frac{d}{ \min\{\varepsilon, \varepsilon^2\}}$.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Management Science and Operations Research

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 Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, background): “Note that the best estimator x will be equal to the scaled version of the best estimator from [DR19, Corollary 3] with the same value 1 /d 1 / p .”
Protection Against Reconstruction and Its Applications in Private Federated Learning (2018, background): “An alternative perspective comes via information-theoretic ideas [26]: differential privacy constraints are essentially equivalent to limiting the bits of information it is possible to communicate about individual data Xi, where privacy level ε corresponds to a communication limit of ε bits, so that”
The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information (2018, background): “In response to these challenges, researchers in the statistics, databases, and computer science communities have studied differential privacy [55, 33, 29, 28, 34, 25, 21] as a formalization of disclosure risk limitation.”
The Role of Interactivity in Local Differential Privacy (2019, methodology): “Seen another way, when multiple queries are asked of the same user, there are situations in which the correlation in privatized responses induced by being run on the same 3This simple compositionality applies even if {εt}Tt=1 are chosen adaptively in each round (see Theorem 3.6 in Rogers et al. [29]”
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints (2020, background): “[18] provides lower bounds for sparse Gaussian mean estimation under LDP constraints via communication complexity.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “Another closely-related thread is the locally private estimation problem, which shares many similarities with communication-constrained problems [12].”
Fisher Information Under Local Differential Privacy (2020, methodology): “Other works such as [13], [17], [18] have also noted the connection between communication and privacy constraints in statistical estimation.”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, unknown): “We limit our discussion and study to the central model of differential privacy, though there has also been much work on mean estimation in the local model [21, 19, 11].”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, methodology): “More recently, drawing on machinery from the communication complexity literature, [14] develop a methodology for proving lower bounds under LDP constraints in the blackboard communication model.”
Locally Private Gaussian Estimation (2018, background): “Subsequent work by Duchi and Rogers [9] generalizes the SDPI framework to prove lower bounds for a broader class of problems in local privacy.”
Element Level Differential Privacy: The Right Granularity of Privacy (2019, unknown): “…the relative sample size necessary for private algorithms to achieve similar utility to that of non-private algorithms grows with problem dimension and inversely with the privacy parameter ε [Barber and Duchi 2014, Steinke and Ullman 2017, Duchi, Jordan, and Wainwright 2018, Duchi and Rogers 2019].”
Pan-Private Uniformity Testing (2019, result): “Finally, we note that these results add to lines of work conceptually connecting restricted memory to pan-privacy [26, 36] and connecting restricted communication to local privacy [33, 5, 22, 6, 31].”
Minimax Bounds for Distributed Logistic Regression (2019, methodology): “In particular we will focus on the logistic loss ℓ(θ; (x, y)) = log(1 + exp(−y〈θ, x〉) and show that in this case, a strong convexity argument from Duchi and Rogers (2019) can be used to extend the Fisher information results to this new loss function.”