A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
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
Text
Singhal. "A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.Markdown
[Singhal. "A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions." Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.](https://mlanthology.org/alt/2024/singhal2024alt-polynomial/)BibTeX
@inproceedings{singhal2024alt-polynomial,
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},
year = {2024},
pages = {1030-1054},
volume = {237},
url = {https://mlanthology.org/alt/2024/singhal2024alt-polynomial/}
}