Google Research

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Annual Conference on Learning Theory (COLT) (2021) (to appear)


In this work, we study the problem of answering k queries with (ε, δ)-differential privacy, where each query has sensitivity one. We give a mechanism for this task that achieves an error bound of O(sqrt(k ln(1/δ))/ε), which is known to be tight (Steinke and Ullman, 2016).

A parallel work by Dagan and Kur (2020) provides a similar result, albeit via a completely different approach. One difference between our work and theirs is that our guarantee holds even when δ < 2^−Ω(k/(log k)^8) whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the ℓ∞ error bound of O(sqrt(k ln(1/δ))/ε) holds not only in expectation but always (i.e., with probability one) while we can only get a high probability (or expected) guarantee on the error.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work