On Scalable Testing of Samplers

06/24/2023

∙

by   Yash Pote, et al.

∙

0

∙

share

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 n-dimensional distributions, the existing state-of-the-art algorithm, 𝖡𝖺𝗋𝖻𝖺𝗋𝗂𝗄2, 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 𝖡𝖺𝗋𝖻𝖺𝗋𝗂𝗄2. Our experiments on the samplers 𝗐𝖴𝗇𝗂𝗀𝖾𝗇3 and 𝗐𝖲𝖳𝖲, find that 𝖡𝖺𝗋𝖻𝖺𝗋𝗂𝗄3 requires 10× fewer samples for 𝗐𝖴𝗇𝗂𝗀𝖾𝗇3 and 450× fewer samples for 𝗐𝖲𝖳𝖲 as compared to 𝖡𝖺𝗋𝖻𝖺𝗋𝗂𝗄2.