A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions

Vikrant Singhal
Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:1030-1054, 2024.

Abstract

We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.

Cite this Paper

BibTeX
@InProceedings{pmlr-v237-singhal24a, title = {A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions}, author = {Singhal, Vikrant}, booktitle = {Proceedings of The 35th International Conference on Algorithmic Learning Theory}, pages = {1030--1054}, year = {2024}, editor = {Vernade, Claire and Hsu, Daniel}, volume = {237}, series = {Proceedings of Machine Learning Research}, month = {25--28 Feb}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v237/singhal24a/singhal24a.pdf}, url = {https://proceedings.mlr.press/v237/singhal24a.html}, abstract = {We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.} }
Endnote
%0 Conference Paper %T A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions %A Vikrant Singhal %B Proceedings of The 35th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Claire Vernade %E Daniel Hsu %F pmlr-v237-singhal24a %I PMLR %P 1030--1054 %U https://proceedings.mlr.press/v237/singhal24a.html %V 237 %X We present the first $\varepsilon$-differentially private, computationally efficient algorithm that estimates the means of product distributions over $\{0,1\}^d$ accurately in total-variation distance, whilst attaining the optimal sample complexity to within polylogarithmic factors. The prior work had either solved this problem efficiently and optimally under weaker notions of privacy, or had solved it optimally while having exponential running times.
APA
Singhal, V.. (2024). A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:1030-1054 Available from https://proceedings.mlr.press/v237/singhal24a.html.

Related Material