Instance Dependent Testing of Samplers Using Interval Conditioning
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36618-36626
DOI: 10.1609/aaai.v40i43.40985 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Rishiraj Bhattacharyya und 4 weiteren Autor:innen.
Abstract (Originalsprache)
Sampling algorithms play a pivotal role in probabilistic AI. However, verifying if a sampler program indeed samples from the claimed distribution is a notoriously hard problem. Provably correct testers like Barbarik,Teq,Flash, Cubeprobe for testing of different kinds of samplers were proposed only in the last few years. All these testers focus on the worst-case efficiency, and do not support verification of samplers over infinite domains, a case occurring frequently in Astronomy, Finance, Network Security etc. In this work, we design the first tester of samplers with instance-dependent efficiency, allowing us to test samplers over natural numbers. Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution using an 'interval conditioning' framework. The core technical contribution is a new connection with probability mass estimation of a continuous distribution. The practical gains are also substantial—our experiments establish up to 1000× speedup over state-of-the-art testers.
Zitieren
APA
Bhattacharyya, R., Chakraborty, S., Pote, Y., Sarkar, U., & Sen, S. (2026). Instance Dependent Testing of Samplers Using Interval Conditioning. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36618-36626. https://doi.org/10.1609/aaai.v40i43.40985
Vancouver
Bhattacharyya R, Chakraborty S, Pote Y, Sarkar U, Sen S. Instance Dependent Testing of Samplers Using Interval Conditioning. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36618-36626. doi:10.1609/aaai.v40i43.40985
BibTeX
@article{Bhattacharyya2026,
author = {Bhattacharyya, Rishiraj and Chakraborty, Sourav and Pote, Yash and Sarkar, Uddalok and Sen, Sayantan},
title = {Instance Dependent Testing of Samplers Using Interval Conditioning},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36618--36626},
doi = {10.1609/aaai.v40i43.40985}
}
EUVIMED