Near-optimal algorithms for private estimation and sequential testing of collision probability

We present new algorithms for estimating and testing 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 (α, β)-local differential privacy and estimates collision probability with error at most ε using tildeOleft(fraclog(1/β)α2 ε2right) samples for α ≤ 1, which improves over previous work by a factor of frac1α2. We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by ε using tildeO(frac1ε2) samples, even when ε is unknown. Our algorithms have nearly the optimal sample complexity, and in experiments we show that they require significantly fewer samples than previous methods.