Online Local Differential Private Quantile Inference via Self-normalization

Yi Liu, Qirui Hu, Lei Ding, Linglong Kong
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:21698-21714, 2023.

Abstract

Based on binary inquiries, we developed an algorithm to estimate population quantiles under Local Differential Privacy (LDP). By self-normalizing, our algorithm provides asymptotically normal estimation with valid inference, resulting in tight confidence intervals without the need for nuisance parameters to be estimated. Our proposed method can be conducted fully online, leading to high computational efficiency and minimal storage requirements with $\mathcal{O}(1)$ space. We also proved an optimality result by an elegant application of one central limit theorem of Gaussian Differential Privacy (GDP) when targeting the frequently encountered median estimation problem. With mathematical proof and extensive numerical testing, we demonstrate the validity of our algorithm both theoretically and experimentally.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-liu23q, title = {Online Local Differential Private Quantile Inference via Self-normalization}, author = {Liu, Yi and Hu, Qirui and Ding, Lei and Kong, Linglong}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {21698--21714}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/liu23q/liu23q.pdf}, url = {https://proceedings.mlr.press/v202/liu23q.html}, abstract = {Based on binary inquiries, we developed an algorithm to estimate population quantiles under Local Differential Privacy (LDP). By self-normalizing, our algorithm provides asymptotically normal estimation with valid inference, resulting in tight confidence intervals without the need for nuisance parameters to be estimated. Our proposed method can be conducted fully online, leading to high computational efficiency and minimal storage requirements with $\mathcal{O}(1)$ space. We also proved an optimality result by an elegant application of one central limit theorem of Gaussian Differential Privacy (GDP) when targeting the frequently encountered median estimation problem. With mathematical proof and extensive numerical testing, we demonstrate the validity of our algorithm both theoretically and experimentally.} }
Endnote
%0 Conference Paper %T Online Local Differential Private Quantile Inference via Self-normalization %A Yi Liu %A Qirui Hu %A Lei Ding %A Linglong Kong %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-liu23q %I PMLR %P 21698--21714 %U https://proceedings.mlr.press/v202/liu23q.html %V 202 %X Based on binary inquiries, we developed an algorithm to estimate population quantiles under Local Differential Privacy (LDP). By self-normalizing, our algorithm provides asymptotically normal estimation with valid inference, resulting in tight confidence intervals without the need for nuisance parameters to be estimated. Our proposed method can be conducted fully online, leading to high computational efficiency and minimal storage requirements with $\mathcal{O}(1)$ space. We also proved an optimality result by an elegant application of one central limit theorem of Gaussian Differential Privacy (GDP) when targeting the frequently encountered median estimation problem. With mathematical proof and extensive numerical testing, we demonstrate the validity of our algorithm both theoretically and experimentally.
APA
Liu, Y., Hu, Q., Ding, L. & Kong, L.. (2023). Online Local Differential Private Quantile Inference via Self-normalization. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:21698-21714 Available from https://proceedings.mlr.press/v202/liu23q.html.

Related Material