Tight Lower Bounds for Differentially Private Selection

By Thomas Steinke, Jonathan Ullman. 2017

85 citations recorded by the source corpus.

A pervasive task in the differential privacy literature is to select the k items of highest quality out of a set of d items, where the quality of each item depends on a sensitive dataset that must be protected. Variants of this task arise naturally in fundamental problems like feature selection and hypothesis testing, and also as subroutines for many sophisticated differentially private algorithms.The standard approaches to these tasks—repeated use of the exponential mechanism or the sparse vector technique—approximately solve this problem given a dataset of n = O(√{k}\log d) samples. We provide a tight lower bound for some very simple variants of the private selection problem. Our lower bound shows that a sample of size n = Ω(√{k} \log d) is required even to achieve a very minimal accuracy guarantee.Our results are based on an extension of the fingerprinting method to sparse selection problems. Previously, the fingerprinting method has been used to provide tight lower bounds for answering an entire set of d queries, but often only some much smaller set of k queries are relevant. Our extension allows us to prove lower bounds that depend on both the number of relevant queries and the total number of queries.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Management Science and Operations Research

In Privacy & Security

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “The i th user has an input x i ∈ { 0 , 1 } D and the goal is to output an index j ∈ Selection is well-studied in DP (e.g., [17, 40, 41]) and its variants are useful primitives for several statistical and algorithmic problems including feature selection, hypothesis testing and clustering.”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “Selecting a coordinate i such that µ i ≥ max j µ j − α requires Θ ( log d α 2 + log d αε ) samples in the trusted curator model under pure di ﬀ erential privacy [47, 4, 58], and Θ ( d log d α 2 ε 2 ) samples in the local model [61].”
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].”
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, unknown): “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.”
On the Power of Multiple Anonymous Messages (2019, unknown): “The selection problem has been studied in several previous works on diﬀeren-tial privacy, and it has many applications to machine learning, hypothesis testing and approximation algorithms (see [41,90,92] and the references therein).”