  Energy-Based Models (EBMs) allow for extremely flexible specifications of
probability distributions. However, they do not provide a mechanism for
obtaining exact samples from these distributions. Monte Carlo techniques can
aid us in obtaining samples if some proposal distribution that we can easily
sample from is available. For instance, rejection sampling can provide exact
samples but is often difficult or impossible to apply due to the need to find a
proposal distribution that upper-bounds the target distribution everywhere.
Approximate Markov chain Monte Carlo sampling techniques like
Metropolis-Hastings are usually easier to design, exploiting a local proposal
distribution that performs local edits on an evolving sample. However, these
techniques can be inefficient due to the local nature of the proposal
distribution and do not provide an estimate of the quality of their samples. In
this work, we propose a new approximate sampling technique, Quasi Rejection
Sampling (QRS), that allows for a trade-off between sampling efficiency and
sampling quality, while providing explicit convergence bounds and diagnostics.
QRS capitalizes on the availability of high-quality global proposal
distributions obtained from deep learning models. We demonstrate the
effectiveness of QRS sampling for discrete EBMs over text for the tasks of
controlled text generation with distributional constraints and paraphrase
generation. We show that we can sample from such EBMs with arbitrary precision
at the cost of sampling efficiency.
