Testing Self-Reducible Samplers

Rishiraj Bhattacharyya, Sourav Chakraborty, Yash Pote, Uddalok Sarkar, Sayantan Sen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Samplers are the backbone of the implementations of any randomized algorithm. Unfortunately, obtaining an efficient algorithm to test the correctness of samplers is very hard to find. Recently, in a series of works, testers like Barbarik, Teq, Flash for testing of some particular kinds of samplers, like CNF-samplers and Horn-samplers, were obtained. However, their techniques have a significant limitation because one can not expect to use their methods to test for other samplers, such as perfect matching samplers or samplers for sampling linear extensions in posets. In this paper, we present a new testing algorithm that works for such samplers and can estimate the distance of a new sampler from a known sampler (say, the uniform sampler). Testing the identity of distributions is the heart of testing the correctness of samplers. This paper's main technical contribution is developing a new distance estimation algorithm for distributions over high-dimensional cubes using the recently proposed subcube conditioning sampling model. Given subcube conditioning access to an unknown distribution P, and a known distribution Q defined over an n-dimensional Boolean hypercube, our algorithm CubeProbeEst estimates the variation distance between P and Q within additive error using subcube conditional samples from P. Following the testing-via-learning paradigm, we also get a tester that distinguishes between the cases when P and Q are close or far in variation distance with high probability using subcube conditional samples. This estimation algorithm CubeProbeEst in the subcube conditioning sampling model helps us to design the first tester for self-reducible samplers. The correctness of the tester is formally proved. Moreover, we implement CubeProbeEst to test the quality of three samplers for sampling linear extensions in posets.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence
PublisherAAAI Press
Pages7952-7960
Number of pages9
ISBN (Print)9781577358879, 1577358872
DOIs
Publication statusPublished - 24 Mar 2024
EventThe 38th Annual AAAI Conference on Artificial Intelligence - Vancouver Convention Centre – West Building, Vancouver, Canada
Duration: 20 Feb 202427 Feb 2024
https://aaai.org/aaai-conference/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI
Number8
Volume38
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceThe 38th Annual AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-24
Country/TerritoryCanada
CityVancouver
Period20/02/2427/02/24
Internet address

Bibliographical note

Acknowledgments:
Rishiraj Bhattacharyya acknowledges the support of UKRI by EPSRC grant number EP/Y001680/1. Uddalok Sarkar is supported by the Google PhD Fellowship. Sayantan Sen’s research is supported by the National Research Foundation Singapore under its NRF Fellowship Programme (NRFNRFFAI1- 2019-0002). This research is part of the programme DesCartes and is supported by the National Research Foundation, Prime Minister’s Office, Singapore, under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. The computational works of this article were performed on the resources of the National Supercomputing Centre, Singapore www.nscc.sg.

Keywords

  • CSO: Solvers and Tools
  • RU: Other Foundations of Reasoning under Uncertainty

Fingerprint

Dive into the research topics of 'Testing Self-Reducible Samplers'. Together they form a unique fingerprint.

Cite this