Lower Bounds for Locally Private Estimation via Communication Complexity

Abstract

We develop lower bounds for estimation under local privacy constraints---including differential privacy and its relaxations to approximate or Rényi 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 $\epsilon \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 \{\epsilon ,{\epsilon }^2\}}$.

To appear in Conference on Learning Theory 2019

References in corpus (6)

• Rényi Divergence and Kullback-Leibler Divergence
• Renyi Differential Privacy
• Protection Against Reconstruction and Its Applications in Private Federated Learning
• On Communication Cost of Distributed Statistical Estimation and Dimensionality
• Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints
• Locally Private Gaussian Estimation

Cited by in corpus (14)

• Protection Against Reconstruction and Its Applications in Private Federated Learning
• Privacy Accounting and Quality Control in the Sage Differentially Private ML Platform
• Distributed Differentially-Private Algorithms for Matrix and Tensor Factorization
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
• Locally Private Gaussian Estimation
• Locally Private Hypothesis Selection
• Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information
• Locally Differentially Private Analysis of Graph Statistics
• Optimal Differential Privacy Composition for Exponential Mechanisms and the Cost of Adaptivity
• Shuffle Private Stochastic Convex Optimization
• Pan-Private Uniformity Testing
• Minimax Bounds for Distributed Logistic Regression
• Universal Private Estimators
• Exponential Separations in Local Differential Privacy