  Relative entropy coding (REC) algorithms encode a sample from a target
distribution $Q$ using a proposal distribution $P$ using as few bits as
possible. Unlike entropy coding, REC does not assume discrete distributions or
require quantisation. As such, it can be naturally integrated into
communication pipelines such as learnt compression and differentially private
federated learning. Unfortunately, despite their practical benefits, REC
algorithms have not seen widespread application, due to their prohibitively
slow runtimes or restrictive assumptions. In this paper, we make progress
towards addressing these issues. We introduce Greedy Rejection Coding (GRC),
which generalises the rejection based-algorithm of Harsha et al. (2007) to
arbitrary probability spaces and partitioning schemes. We first show that GRC
terminates almost surely and returns unbiased samples from $Q$, after which we
focus on two of its variants: GRCS and GRCD. We show that for continuous $Q$
and $P$ over $\mathbb{R}$ with unimodal density ratio $dQ/dP$, the expected
runtime of GRCS is upper bounded by $\beta D_{KL}[Q || P] + O(1)$ where $\beta
\approx 4.82$, and its expected codelength is optimal. This makes GRCS the
first REC algorithm with guaranteed optimal runtime for this class of
distributions, up to the multiplicative constant $\beta$. This significantly
improves upon the previous state-of-the-art method, A* coding (Flamich et al.,
2022). Under the same assumptions, we experimentally observe and conjecture
that the expected runtime and codelength of GRCD are upper bounded by $D_{KL}[Q
|| P] + O(1)$. Finally, we evaluate GRC in a variational autoencoder-based
compression pipeline on MNIST, and show that a modified ELBO and an
index-compression method can further improve compression efficiency.
