Tight Lower Bounds for Locally Differentially Private Selection

By Jonathan Ullman. 2018

35 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “2, achieving LDP while maintaining utility can be difficult [229, 388].”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “Ullman [61] proved that in any ε -di ﬀ erentially private non-interactive protocol in the local model for the selection problem, the number of agents is Ω d log d α 2 ε 2 .”
Distributed Differential Privacy via Shuffling (2018, background): “Subsequently, an even more natural separation arose for the variable-selection problem [12, 31], which we also consider in this work.”
On the Power of Multiple Anonymous Messages (2019, unknown): “In the case of local p ε L , 0 q -DP (i.e., pure) protocols, Ullman [92] proved a lower bound n “ Ω ´ log B p exp p ε L q´ 1 q 2 ¯ There are two diﬀerent reasons why this lower bound is not suﬃcient for our purposes: 1.”
Locally Private Gaussian Estimation (2018, background): “For many problems, a locally private solution requires far more samples than a globally private solution [7, 10, 19, 23].”
Local Differential Privacy for Evolving Data (2018, background): “Unfortunately, the sparse vector technique provably has no local analogue (Kasiviswanathan et al., 2008; Ullman, 2018).”
The Role of Interactivity in Local Differential Privacy (2019, background): “It has been known since [26] that there can be an exponential gap in the sample complexity between noninteractive and interactive protocols in the local model of differential privacy, and that this gap can manifest itself even in natural problems like convex optimization [30, 31].”