Differentially Private Approximate Quantiles

Haim Kaplan, Shachar Schnapp, Uri Stemmer
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:10751-10761, 2022.

Abstract

In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call Approximate Quantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-kaplan22a, title = {Differentially Private Approximate Quantiles}, author = {Kaplan, Haim and Schnapp, Shachar and Stemmer, Uri}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {10751--10761}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/kaplan22a/kaplan22a.pdf}, url = {https://proceedings.mlr.press/v162/kaplan22a.html}, abstract = {In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call Approximate Quantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.} }
Endnote
%0 Conference Paper %T Differentially Private Approximate Quantiles %A Haim Kaplan %A Shachar Schnapp %A Uri Stemmer %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-kaplan22a %I PMLR %P 10751--10761 %U https://proceedings.mlr.press/v162/kaplan22a.html %V 162 %X In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, ..., q_m \in [0,1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call Approximate Quantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.
APA
Kaplan, H., Schnapp, S. & Stemmer, U.. (2022). Differentially Private Approximate Quantiles. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:10751-10761 Available from https://proceedings.mlr.press/v162/kaplan22a.html.

Related Material