• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
A scalable tester for samplers.
Yash Pote ⓡ Kuldeep S. Meel.
In Proceedings of Advances in Neural Information Processing Systems(NeurIPS), November 2022.
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 wSTS, find that Pacoco requires 10X fewer samples for wUniGen3 and 450X fewer samples for wSTS as compared to Barbarik2.
@inproceedings{PM22,
title={A scalable tester for samplers},
author={Pote, Yash and Meel, Kuldeep S.},
nameorder={random},
bib2html_pubtype={Refereed Conference},
booktitle=NIPS,
month=nov,
bib2html_dl_pdf={../Papers/neurips22.pdf},
bib2html_rescat={Sampling,Distribution Testing},
year={2022},
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 wSTS, find that Pacoco requires 10X fewer samples for wUniGen3 and 450X fewer samples for wSTS as compared to Barbarik2.},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51