Instance-Optimal Uniformity Testing and Tracking

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a polylog(opt)-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.

Authors

• Guy Blanc
• Clément L. Canonne
• Erik Waingarten

Keywords

• Computer science
• Total variance
• Probability distribution
• Complexity theory
• Testing
• Uniform Test
• Uniform Distribution
• Total Distance
• Distance Parameter
• Unknown Distribution
• Competitive Algorithm
• Variation Distance
• Total Variation Distance
• High Probability
• Random Variables
• Poisson Distribution
• Kullback-Leibler
• Identification Test
• Constant Factor
• Probability Of Failure
• Telescope
• Remainder Of This Section
• Testing Algorithm
• Triangle Inequality
• Probability Mass Function
• Hellinger Distance
• Competitive Ratio
• Notion Of Distance
• Collision Probability
• Reference Distribution
• Contraposition
• Uniform Case
• Symmetric Property
• Polylogarithmic
• Proof Of Theorem
• distribution testing
• uniformity testing
• competitive algorithms