Instance Dependent Testing of Samplers using Interval Conditioning
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917131148328960 |
|---|---|
| author | Bhattacharyya, Rishiraj Chakraborty, Sourav Pote, Yash Sarkar, Uddalok Sen, Sayantan |
| author_facet | Bhattacharyya, Rishiraj Chakraborty, Sourav Pote, Yash Sarkar, Uddalok Sen, Sayantan |
| contents | 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 1000x speedup over state-of-the-art testers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06458 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Instance Dependent Testing of Samplers using Interval Conditioning Bhattacharyya, Rishiraj Chakraborty, Sourav Pote, Yash Sarkar, Uddalok Sen, Sayantan Data Structures and Algorithms Artificial Intelligence 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 1000x speedup over state-of-the-art testers. |
| title | Instance Dependent Testing of Samplers using Interval Conditioning |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2512.06458 |