On Scalable Testing of Samplers

Abstract

In this paper we study the problem of testing of constrained samplers over high-dimensional distributions with $(\epsilon ,\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, $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 $\mathsf{wSTS}$, find that $Barbarik3$ requires $10\times$ fewer samples for $wUnigen3$ and $450\times$ fewer samples for $\mathsf{wSTS}$ as compared to $Barbarik2$.

Appeared at NeurIPS 2022

References in corpus (3)

• Reversible Jump MCMC Simulated Annealing for Neural Networks
• Uniform Solution Sampling Using a Constraint Solver As an Oracle
• Learning and Testing Junta Distributions with Subcube Conditioning