Some Notes on the Sample Complexity of Approximate Channel Simulation

Channel simulation algorithms can efficiently encode random samples from a prescribed target distribution
$Q$
and find applications in machine learning-based lossy data compression. However, algorithms that encode exact samples usually have random runtime, limiting their applicability when a consistent encoding time is desirable. Thus, this paper considers approximate schemes with a fixed runtime instead. First, we strengthen a result of Agustsson and Theis [1] and show that there is a class of pairs of target distribution
$Q$
and coding distribution
$P$
, for which the runtime of any approximate scheme scales at least super-polynomially in
$D_{\infty}[Q\Vert P]$
. We then show, by contrast, that if we have access to an unnormalised Radon-Nikodym derivative
$r\propto dQ/dP$
and knowledge of
$D_{\text{KL}}[Q\Vert P]$
, we can exploit global-bound, depth-limited A* coding [2] to ensure
$D_{TV}[Q\Vert P]\leq\epsilon$
and maintain optimal coding performance with a sample complexity of only
$\exp_{2}((D_{\text{KL}}[Q\Vert P]+o(1))/\epsilon)$
.