On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Badih Ghazi, Ravi Kumar, Pasin Manurangsi
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2133-2146, 2021.

Abstract

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 ℓ∞ error bound of O(1ϵ√klog1δ), 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/(logk)8) whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur (2020) has a remarkable advantage that the ℓ∞ error bound of O(1ϵ√klog1δ) 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-ghazi21a, title = {On Avoiding the Union Bound When Answering Multiple Differentially Private Queries}, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {2133--2146}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/ghazi21a/ghazi21a.pdf}, url = {https://proceedings.mlr.press/v134/ghazi21a.html}, abstract = {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 $\ell_\infty$ error bound of $O(\frac{1}{\epsilon}\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^{-\Omega(k/(\log k)^8)}$ whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur (2020) has a remarkable advantage that the $\ell_{\infty}$ error bound of $O(\frac{1}{\epsilon}\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.} }
Endnote
%0 Conference Paper %T On Avoiding the Union Bound When Answering Multiple Differentially Private Queries %A Badih Ghazi %A Ravi Kumar %A Pasin Manurangsi %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-ghazi21a %I PMLR %P 2133--2146 %U https://proceedings.mlr.press/v134/ghazi21a.html %V 134 %X 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 $\ell_\infty$ error bound of $O(\frac{1}{\epsilon}\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^{-\Omega(k/(\log k)^8)}$ whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur (2020) has a remarkable advantage that the $\ell_{\infty}$ error bound of $O(\frac{1}{\epsilon}\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.
APA
Ghazi, B., Kumar, R. & Manurangsi, P.. (2021). On Avoiding the Union Bound When Answering Multiple Differentially Private Queries. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:2133-2146 Available from https://proceedings.mlr.press/v134/ghazi21a.html.

Related Material