Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy

Yi Liu, Qirui Hu, Linglong Kong
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:31147-31164, 2024.

Abstract

We introduce a novel algorithm for estimating Cumulative Distribution Function (CDF) values under Local Differential Privacy (LDP) by exploiting an unexpected connection between LDP and the current status problem, a classical survival data problem in statistics. This connection leads to the development of tools for constrained isotonic estimation based on binary queries. Through mathematical proofs and extensive numerical testing, we demonstrate that our method achieves uniform and $L_2$ error bounds when estimating the entire CDF curve. By employing increasingly dense grids, the error bound can be improved, exhibiting an asymptotic normal distribution of the proposed estimator. Theoretically, we show that the error bound smoothly changes as the number of grids increases relative to the sample size $n$. Computationally, we demonstrate that our constrained isotonic estimator can be efficiently computed deterministically, eliminating the need for hyperparameters or random optimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-liu24z, title = {Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy}, author = {Liu, Yi and Hu, Qirui and Kong, Linglong}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {31147--31164}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/liu24z/liu24z.pdf}, url = {https://proceedings.mlr.press/v235/liu24z.html}, abstract = {We introduce a novel algorithm for estimating Cumulative Distribution Function (CDF) values under Local Differential Privacy (LDP) by exploiting an unexpected connection between LDP and the current status problem, a classical survival data problem in statistics. This connection leads to the development of tools for constrained isotonic estimation based on binary queries. Through mathematical proofs and extensive numerical testing, we demonstrate that our method achieves uniform and $L_2$ error bounds when estimating the entire CDF curve. By employing increasingly dense grids, the error bound can be improved, exhibiting an asymptotic normal distribution of the proposed estimator. Theoretically, we show that the error bound smoothly changes as the number of grids increases relative to the sample size $n$. Computationally, we demonstrate that our constrained isotonic estimator can be efficiently computed deterministically, eliminating the need for hyperparameters or random optimization.} }
Endnote
%0 Conference Paper %T Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy %A Yi Liu %A Qirui Hu %A Linglong Kong %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-liu24z %I PMLR %P 31147--31164 %U https://proceedings.mlr.press/v235/liu24z.html %V 235 %X We introduce a novel algorithm for estimating Cumulative Distribution Function (CDF) values under Local Differential Privacy (LDP) by exploiting an unexpected connection between LDP and the current status problem, a classical survival data problem in statistics. This connection leads to the development of tools for constrained isotonic estimation based on binary queries. Through mathematical proofs and extensive numerical testing, we demonstrate that our method achieves uniform and $L_2$ error bounds when estimating the entire CDF curve. By employing increasingly dense grids, the error bound can be improved, exhibiting an asymptotic normal distribution of the proposed estimator. Theoretically, we show that the error bound smoothly changes as the number of grids increases relative to the sample size $n$. Computationally, we demonstrate that our constrained isotonic estimator can be efficiently computed deterministically, eliminating the need for hyperparameters or random optimization.
APA
Liu, Y., Hu, Q. & Kong, L.. (2024). Tuning-free Estimation and Inference of Cumulative Distribution Function under Local Differential Privacy. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:31147-31164 Available from https://proceedings.mlr.press/v235/liu24z.html.

Related Material