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

2025/04/18 by Busa-Fekete, Robert, Syed, Umar
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2504.13804

Abstract

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 O((log(1/β))/(α² ε²)) samples for α≤ 1, which improves over previous work by a factor of (1)/(α²). We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by ε using O((1)/(ε²)) 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.

Related

• Collision-based Testers are Optimal for Uniformity and Closeness
• Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms
• Private High-Dimensional Hypothesis Testing
• Locally Private Hypothesis Selection
• Differentially Private Identity and Closeness Testing of Discrete Distributions