On Scalable Testing of Samplers
arXiv:2306.13958
Abstract
In this paper we study the problem of testing of constrained samplers over high-dimensional 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 -dimensional distributions, the existing state-of-the-art algorithm, , has a worst case query complexity of exponential in and hence is not ideal for use in practice. Our primary contribution is an exponentially faster algorithm that has a query complexity linear in and hence can easily scale to larger instances. We demonstrate our claim by implementing our algorithm and then comparing it against . Our experiments on the samplers and , find that requires fewer samples for and fewer samples for as compared to .
arXiv commentAppeared at NeurIPS 2022
References in corpus (8)
- MCMC using Hamiltonian dynamics
- End to End Learning for Self-Driving Cars
- Deep Neural Network Compression for Aircraft Collision Avoidance Systems
- Reversible Jump MCMC Simulated Annealing for Neural Networks
- Uniform Solution Sampling Using a Constraint Solver As an Oracle
- Property Testing of Joint Distributions using Conditional Samples
- A Chasm Between Identity and Equivalence Testing with Conditional Queries
- Learning and Testing Junta Distributions with Subcube Conditioning