@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@inproceedings{MPC20,
  author={
    Meel, Kuldeep S. and
    Pote, Yash and
    Chakraborty, Sourav
  },
  title={On Testing of Samplers},
  booktitle=NIPS,
  year={2020},
  month=dec,
  nameorder={random},
  bib2html_rescat={Distribution Testing},
  url={https://arxiv.org/abs/2010.12918},
  bib2html_pubtype={Refereed Conference},
  abstract={
    Given a set of items F and a weight function W, the problem of sampling
    seeks to sample an item proportional to its weight. Sampling is a
    fundamental problem in machine learning. The daunting computational
    complexity of sampling with formal guarantees leads designers to propose
    heuristics-based techniques for which no rigorous theoretical analysis
    exists to quantify the quality of generated distributions.
    This poses a challenge in designing a testing methodology to test whether a
    sampler under test generates samples according to a given distribution. Only
    recently, Chakraborty and Meel (2019) designed the first scalable verifier,
    called Barbarik1, for samplers in the special case when the weight function
    W is constant, that is, when the sampler is supposed to sample uniformly
    from F . The techniques in Barbarik1, however, fail to handle general weight
    functions.
    The primary contribution of this paper is an affirmative answer to the above
    challenge: motivated by Barbarik1 but using different techniques and
    analysis, we design Barbarik2 an algorithm to test whether the distribution
    generated by a sampler is $\varepsilon$-close or $\eta$-far from any target
    distribution. In contrast to black-box sampling techniques that require a
    number of samples proportional to |F| , Barbarik2 requires only
    $\mathcal{O}(titl(W,\varphi)2/\eta(\eta-6\varepsilon)3)$ samples, where the
    tilt is the maximum ratio of weights of two satisfying assignments.
    Barbarik2 can handle any arbitrary weight function. We present a prototype
    implementation of Barbarik2 and use it to test three state-of-the-art
    samplers.
  },
}