On Scalable Testing of Samplers

In this paper we study the problem of testing of constrained samplers over high-dimensional distributions with (\varepsilon,\eta,\delta) guarantees. Samplers are increasingly used in a wide range of safety-critical ML applications, and hence the testing problem has gained importance. For n -dimensional distributions, the existing state-of-the-art algorithm, \mathsf{Barbarik2}, has a worst case query complexity of exponential in n and hence is not ideal for use in practice. Our primary contribution is an exponentially faster algorithm, \mathsf{Barbarik3}, that has a query complexity linear in n and hence can easily scale to larger instances. We demonstrate our claim by implementing our algorithm and then comparing it against \mathsf{Barbarik2} .