A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
This work provides a practical solution for privacy-preserving data analysis in domains like healthcare or social sciences, where binary data is common, and it is incremental by bridging efficiency and optimality in differential privacy.
The authors tackled the problem of estimating means of binary product distributions under differential privacy with computational efficiency, achieving optimal sample complexity up to polylogarithmic factors. This resolves a gap where prior methods were either efficient but less private or optimal but computationally infeasible.
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.