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 $(\hat{I}\pm ,{\hat{I}}^2)$-local differential privacy and estimates collision probability with error at most $\hat{I}\mu$ using $\tilde{O}\left(\frac{\log (1/{\hat{I}}^2)}{\hat{I}{\pm }^2\hat{I}{\mu }^2}\right)$ samples for $\hat{I}\pm \le 1$, which improves over previous work by a factor of $\frac{1}{\hat{I}{\pm }^2}$. We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by $\hat{I}\mu$ using $\tilde{O}(\frac{1}{\hat{I}{\mu }^2})$ samples, even when $\hat{I}\mu$ is unknown. Our algorithms have nearly the optimal sample complexity, and in experiments we show that they require significantly fewer samples than previous methods.