Nonparametric Extensions of Randomized Response for Private Confidence Sets

Ian Waudby-Smith, Steven Wu, Aaditya Ramdas
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:36748-36789, 2023.

Abstract

This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP). Given bounded observations $(X_1, …, X_n)$ with mean $\mu^\star$ that are privatized into $(Z_1, …, Z_n)$, we present confidence intervals (CI) and time-uniform confidence sequences (CS) for $\mu^\star$ when only given access to the privatized data. To achieve this, we introduce a nonparametric and sequentially interactive generalization of Warner’s famous “randomized response” mechanism, satisfying LDP for arbitrary bounded random variables, and then provide CIs and CSs for their means given access to the resulting privatized observations. For example, our results yield private analogues of Hoeffding’s inequality in both fixed-time and time-uniform regimes. We extend these Hoeffding-type CSs to capture time-varying (non-stationary) means, and conclude by illustrating how these methods can be used to conduct private online A/B tests.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-waudby-smith23a, title = {Nonparametric Extensions of Randomized Response for Private Confidence Sets}, author = {Waudby-Smith, Ian and Wu, Steven and Ramdas, Aaditya}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {36748--36789}, 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/waudby-smith23a/waudby-smith23a.pdf}, url = {https://proceedings.mlr.press/v202/waudby-smith23a.html}, abstract = {This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP). Given bounded observations $(X_1, …, X_n)$ with mean $\mu^\star$ that are privatized into $(Z_1, …, Z_n)$, we present confidence intervals (CI) and time-uniform confidence sequences (CS) for $\mu^\star$ when only given access to the privatized data. To achieve this, we introduce a nonparametric and sequentially interactive generalization of Warner’s famous “randomized response” mechanism, satisfying LDP for arbitrary bounded random variables, and then provide CIs and CSs for their means given access to the resulting privatized observations. For example, our results yield private analogues of Hoeffding’s inequality in both fixed-time and time-uniform regimes. We extend these Hoeffding-type CSs to capture time-varying (non-stationary) means, and conclude by illustrating how these methods can be used to conduct private online A/B tests.} }
Endnote
%0 Conference Paper %T Nonparametric Extensions of Randomized Response for Private Confidence Sets %A Ian Waudby-Smith %A Steven Wu %A Aaditya Ramdas %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-waudby-smith23a %I PMLR %P 36748--36789 %U https://proceedings.mlr.press/v202/waudby-smith23a.html %V 202 %X This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP). Given bounded observations $(X_1, …, X_n)$ with mean $\mu^\star$ that are privatized into $(Z_1, …, Z_n)$, we present confidence intervals (CI) and time-uniform confidence sequences (CS) for $\mu^\star$ when only given access to the privatized data. To achieve this, we introduce a nonparametric and sequentially interactive generalization of Warner’s famous “randomized response” mechanism, satisfying LDP for arbitrary bounded random variables, and then provide CIs and CSs for their means given access to the resulting privatized observations. For example, our results yield private analogues of Hoeffding’s inequality in both fixed-time and time-uniform regimes. We extend these Hoeffding-type CSs to capture time-varying (non-stationary) means, and conclude by illustrating how these methods can be used to conduct private online A/B tests.
APA
Waudby-Smith, I., Wu, S. & Ramdas, A.. (2023). Nonparametric Extensions of Randomized Response for Private Confidence Sets. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:36748-36789 Available from https://proceedings.mlr.press/v202/waudby-smith23a.html.

Related Material