On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
This work provides an improved error bound for differentially private query answering, which is crucial for researchers and practitioners working with sensitive data.
This paper addresses the challenge of answering k differentially private queries, each with sensitivity one, and proposes an algorithm that achieves an expected L-infinity error bound of O(1/epsilon * sqrt(k * log(1/delta))). This result is known to be tight and improves upon prior work by extending the guarantee to cases where delta < 2^(-Omega(k/(log k)^8)).
In this work, we study the problem of answering $k$ queries with $(ε, δ)$-differential privacy, where each query has sensitivity one. We give an algorithm for this task that achieves an expected $\ell_\infty$ error bound of $O(\frac{1}ε\sqrt{k \log \frac{1}δ})$, which is known to be tight (Steinke and Ullman, 2016). A very recent 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 $\ell_{\infty}$ error bound of $O(\frac{1}ε\sqrt{k \log \frac{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.