Towards Practical Distribution Testing
0Yash Pote (National University of Singapore)
https://simons.berkeley.edu/talks/yash-pote-national-university-singapore-2024-08-07
Workshop on Local Algorithms (WoLA)
As systems that employ samplers are deployed in safety-critical software, there is a need for tests that can verify the samplers' statistical correctness. This raises the question: given a sampler P and a target distribution Q, can we practically test whether P samples from a distribution close to Q?
In the high-dimensional setting, where the domain is {0,1}^N for a large N, black-box testing (sample access) is well-known to be intractable; hence, richer "grey-box" models, such as conditional sampling, have emerged as promising alternatives for the testing problem. In this talk, I will present our work in developing grey-box algorithms that are fast in theory and practice, and I will focus on the first polynomial query algorithm for TV distance estimation, in the conditional sampling model.