Tight Lower Bounds for Locally Differentially Private Selection
arXiv:1802.02638
Abstract
We prove a tight lower bound (up to constant factors) on the sample complexity of any non-interactive local differentially private protocol for optimizing a linear function over the simplex. This lower bound also implies a tight lower bound (again, up to constant factors) on the sample complexity of any non-interactive local differentially private protocol implementing the exponential mechanism. These results reveal that any local protocol for these problems has exponentially worse dependence on the dimension than corresponding algorithms in the central model. Previously, Kasiviswanathan et al. (FOCS 2008) proved an exponential separation between local and central model algorithms for PAC learning the class of parity functions. In contrast, our lower bound are quantitatively tight, apply to a simple and natural class of linear optimization problems, and our techniques are arguably simpler.
The results in this paper have been subsumed by: Alexander Edmonds, Aleksandar Nikolov, Jonathan Ullman. "The Power of Factorization Mechanisms in Local and Central Differential Privacy." STOC 2020 [arXiv:1911.08339]. Please cite that paper for the relevant results
References in corpus (4)
Cited by in corpus (10)
- On the Power of Multiple Anonymous Messages
- SPEED: Secure, PrivatE, and Efficient Deep learning
- Locally Private Gaussian Estimation
- Locally Private Hypothesis Selection
- Differentially Private Clustering: Tight Approximation Ratios
- Aggregating Votes with Local Differential Privacy: Usefulness, Soundness vs. Indistinguishability
- Unsupervised Information Obfuscation for Split Inference of Neural Networks
- Differentially Private High Dimensional Sparse Covariance Matrix Estimation
- Statistical Inference in the Differential Privacy Model
- Multi-Central Differential Privacy