On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

In this work, we study the problem of answering $k$ queries with $(\epsilon, \delta)$-differential privacy, where each query has sensitivity one. We give an algorithm for this task that achieves an expected ${\mathrm{\ell }}_{\mathrm{\infty }}$ error bound of $O(\frac{1}{ϵ}\sqrt{k\log \frac{1}{\delta }})$, 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 $\delta <2^{-\mathrm{\Omega }(k\mathrm{/}(\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 ${\mathrm{\ell }}_{\mathrm{\infty }}$ error bound of $O(\frac{1}{ϵ}\sqrt{k\log \frac{1}{\delta }})$ 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.