Towards Practical Distribution Testing

Abstract:

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; consequently, richer "grey-box" models, such as those allowing conditional sampling, have emerged as promising alternatives.

In this talk, we develop grey-box algorithms that are fast in theory and practice. In the first part, we focus on the decision variant of the problem, where we look at algorithms that can distinguish between close and far distributions. To this end, we developed a technique that uses pairwise conditioning to improve the query complexity from exponential to linear in N. In our experiments we use this algorithm to design a testing tool for combinatorial samplers.

In the second part, we address the estimation variant, where we estimate the distance between distributions. We first tackle this for distributions with tractable representations, such as probabilistic circuits. We then extend our approach to the broad class of self-reducible models, for which we build the first polynomial query distance estimator. Together, these algorithms provide a toolkit for the practical statistical verification of combinatorial samplers.