A bounded-noise mechanism for differential privacy

Yuval Dagan, Gil Kur
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:625-661, 2022.

Abstract

We present an asymptotically optimal $(\epsilon,\delta)$ differentially private mechanism for answering multiple, adaptively asked, $\Delta$-sensitive queries, settling the conjecture of Steinke and Ullman [2020]. Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound. Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample. Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-dagan22a, title = {A bounded-noise mechanism for differential privacy}, author = {Dagan, Yuval and Kur, Gil}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {625--661}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/dagan22a/dagan22a.pdf}, url = {https://proceedings.mlr.press/v178/dagan22a.html}, abstract = {We present an asymptotically optimal $(\epsilon,\delta)$ differentially private mechanism for answering multiple, adaptively asked, $\Delta$-sensitive queries, settling the conjecture of Steinke and Ullman [2020]. Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound. Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample. Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.} }
Endnote
%0 Conference Paper %T A bounded-noise mechanism for differential privacy %A Yuval Dagan %A Gil Kur %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-dagan22a %I PMLR %P 625--661 %U https://proceedings.mlr.press/v178/dagan22a.html %V 178 %X We present an asymptotically optimal $(\epsilon,\delta)$ differentially private mechanism for answering multiple, adaptively asked, $\Delta$-sensitive queries, settling the conjecture of Steinke and Ullman [2020]. Our algorithm has a significant advantage that it adds independent bounded noise to each query, thus providing an absolute error bound. Additionally, we apply our algorithm in adaptive data analysis, obtaining an improved guarantee for answering multiple queries regarding some underlying distribution using a finite sample. Numerical computations show that the bounded-noise mechanism outperforms the Gaussian mechanism in many standard settings.
APA
Dagan, Y. & Kur, G.. (2022). A bounded-noise mechanism for differential privacy. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:625-661 Available from https://proceedings.mlr.press/v178/dagan22a.html.

Related Material