On Scalable Testing of Samplers

In this paper we study the problem of testing of constrained samplers over highdimensional distributions with (ε, η, δ) 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-theart algorithm, 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 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 Barbarik2. Our experiments on the samplers wUnigen3 and wSTS, find that Barbarik3 requires 10× fewer samples for wUnigen3 and 450× fewer samples for wSTS as compared to Barbarik2. * The accompanying tool, available open source, can be found at https://github.com/meelgroup/barbarik † The authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by r . The publicly verifiable record of the randomization is available at https://www.aeaweb.org/journals/policies/random-author-order/search with confirmation code: Lrr1ecP-xv14. For citations, the authors request that the citation guidelines by AEA for random author ordering be followed. The multiplicative distance of D 2 from D 1 is defined as: d ∞ (D 1 , D 2 ) = 3 A simple modification reveals that in terms of n, η, ε, the bound is Õ 4 n η(η-3ε) 3