The Price of Selection in Differential Privacy

By Mitali Bafna, Jonathan Ullman. 2017

35 citations recorded by the source corpus.

In the differentially private top-$k$ selection problem, we are given a dataset $X \in \{\pm 1\}^{n \times d}$, in which each row belongs to an individual and each column corresponds to some binary attribute, and our goal is to find a set of $k \ll d$ columns whose means are approximately as large as possible. Differential privacy requires that our choice of these $k$ columns does not depend too much on any on individual's dataset. This problem can be solved using the well known exponential mechanism and composition properties of differential privacy. In the high-accuracy regime, where we require the error of the selection procedure to be to be smaller than the so-called sampling error $\alpha \approx \sqrt{\ln(d)/n}$, this procedure succeeds given a dataset of size $n \gtrsim k \ln(d)$. We prove a matching lower bound, showing that a dataset of size $n \gtrsim k \ln(d)$ is necessary for private top-$k$ selection in this high-accuracy regime. Our lower bound is the first to show that selecting the $k$ largest columns requires more data than simply estimating the value of those $k$ columns, which can be done using a dataset of size just $n \gtrsim k$.

Subfields: Artificial Intelligence, 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 Privacy & Security

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The select-then-estimate problem is a sub-component of many statistical and data-mining applications [4, 58, 2].”
Distributed Differential Privacy via Shuffling (2018, background): “In the central model, this problem is solved by the exponential mechanism [24] with a dataset of size just n =O(ε logd), and this is optimal [2, 27].”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “(2) This empirical variant of the problem was first studied in a very recent work by Bafna and Ullman [22].”
Scalable Private Learning with PATE (2018, background): “Recent works offer lower bounds on sample complexity of such problem (Steinke & Ullman, 2017; Bafna & Ullman, 2017).”
Composable and versatile privacy via truncated CDP (2018, methodology): “This algorithm readily generalizes to the gap version of the “topm problem” (more commonly called top-k) which has been studied extensively [2, 4, 7, 23]: We simply set f (x , j) = max{l(x , j) − l(x ,σx (m + 1)), 0} instead.”