Near-Optimal Algorithms for Private Estimation and Sequential Testing of Collision Probability
Abstract
We present new algorithms for estimating and testing \emph{collision probability}, a fundamental measure of the spread of a discrete distribution that is widely used in many scientific fields. We describe an algorithm that satisfies $(\alpha, \beta)$-local differential privacy and estimates collision probability with error at most $\epsilon$ using $\tilde{O}\left(\frac{\log(1/\beta)}{\alpha^2 \epsilon^2}\right)$ samples for $\alpha \le 1$, which improves over previous work by a factor of $\frac{1}{\alpha^2}$. We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by $\epsilon$ using $\tilde{O}(\frac{1}{\epsilon^2})$ samples, even when $\epsilon$ is unknown. Our algorithms have nearly the optimal sample complexity, and in experiments we show that they require significantly fewer samples than previous methods.
Cite
Text
Busa-Fekete and Syed. "Near-Optimal Algorithms for Private Estimation and Sequential Testing of Collision Probability." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Busa-Fekete and Syed. "Near-Optimal Algorithms for Private Estimation and Sequential Testing of Collision Probability." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/busafekete2025aistats-nearoptimal/)BibTeX
@inproceedings{busafekete2025aistats-nearoptimal,
title = {{Near-Optimal Algorithms for Private Estimation and Sequential Testing of Collision Probability}},
author = {Busa-Fekete, Robert Istvan and Syed, Umar},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {892-900},
volume = {258},
url = {https://mlanthology.org/aistats/2025/busafekete2025aistats-nearoptimal/}
}