Make Up Your Mind: The Price of Online Queries in Differential Privacy

By Mark Bun, Thomas Steinke, Jonathan Ullman. 2016

66 citations recorded by the source corpus.

We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set $Q$ of allowable queries in one of three ways, which we list in order from easiest to hardest to answer:Offline: The queries are chosen all at once and the differentially private mechanism answers the queries in a single batch. Online: The queries are chosen all at once, but the mechanism only receives the queries in a streaming fashion and must answer each query before seeing the next query. Adaptive: The queries are chosen one at a time and the mechanism must answer each query before the next query is chosen. In particular, each query may depend on the answers given to previous queries.Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models may be equivalent. We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that exponentially more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries like threshold queries over the real line.

Subfields: Artificial Intelligence, Computer Science Applications, Privacy & Security, Algorithms & Complexity

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 Computer Science Applications

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, methodology): “Techniques Our techniques build on the recent line of work proving lower bounds in differential privacy and related problems via either fingerprinting codes or techniques inspired by fingerprinting codes [16], [24], [25], [17], [18], [26].”
Scalable Private Learning with PATE (2018, background): “Closer to our work, Bun et al. (2017) consider a setting where the answer to a query of interest is often either very large or very small.”
Advanced Probabilistic Couplings for Differential Privacy (2016, methodology): “We also introduce a novel coupling technique called optimal subset coupling that may be of independent interest.”
Differentially Private Assouad, Fano, and Le Cam (2020, methodology): “It has been used to prove lower bounds for several problems, including attribute mean estimation in databases (Steinke and Ullman, 2017a), lower bounds on the number of online statistical queries (Bun et al., 2017), and private selection problem (Steinke and Ullman, 2017b).”