1 From Renaissance Secret Codes to Modern Data Compression↩︎

Writing systems emerged at least 8,000 years ago. Soon after writing was invented, an urgent need arose that only the desired recipient be able to read the intended message, lest some ill-spirited adversary take advantage of the precious knowledge therein. One proposed solution was steganography, the art of hiding a message in plain sight. One of its most popular renditions was described in the middle of the 16th century by Girolamo Cardano, which is now called the Cardan grille; though the same idea was described decades earlier by Jacopo Silvestri [2], and similar ideas were described centuries earlier by Wujing Zongyao in 11th-century China [3].

The Cardan grille works as follows: take a stiff piece of material, such as cardboard or metal, and cut irregularly sized holes at irregular locations; this is called the grille. To compose a hidden message, place the grille on top of a piece of paper and write the intended secret message in the holes. Then lift the grille and fill the gaps between the hidden message pieces with cover text so they do not stand out. The resulting text should appear innocuous to any unsuspecting reader, while someone with the grille can reveal the hidden message at once.

Naturally, a difficulty in using the Cardan grille is that the hidden message constrains the composition of the cover message; hence, the cover text might sound awkward without proper care. One solution is to compose the cover text first, then create an appropriate grille that reveals the desired hidden message. We call this method the “REverse Cardan” (REC) method and illustrate it in 1. An advantage of the REC method is that the communicating parties may use any text that is available to both of them, such as the Bible or Douglas Adams’ The Hitchhiker’s Guide to the Galaxy. Therefore, so long as both parties have access to the same edition of the same book, the intended recipient only needs the grille to read the hidden message. Of course, the disadvantage now is that the grille might need to be much bigger than before: the sender composing the grille is at the whim of the pre-agreed text as to how often the pieces of the sender’s intended message appear in the cover text; 1 illustrates this phenomenon well.

Due to significant advances in cryptography and steganography over the last century, grilles are no longer used for serious secret communications. However, it is interesting to study the REC method purely as a form of communication, as it underlies an emerging data compression framework called relative entropy coding. Thus, consider the following abstraction of the REC method: we may conceive of the shared “cover text” as an infinitely long string of symbols from some finite (such as the Latin) alphabet. Furthermore, we may describe our grille as the number of symbols between consecutive holes. For example, we can describe the first five holes of the grille in 1 by the sequence \(1, 36, 37, 17, 9\).

At this point, any good information theorist ought to begin pondering the question: if we represent this integer sequence using some appropriate binary code, how efficient is this protocol? It is a beautiful fact that if 1) the symbols we wish to encode arise from a memoryless source, and 2) the symbols of the message and the shared text follow the same distribution, then we can construct a grille whose per-symbol integer description will be given by the Shannon entropy of the source.¹ Of course, the assumption that the symbols of the shared text are independent and identically distributed (i.i.d.)is unreasonable for any book written by a human. However, we can easily generate the “book” by sampling the symbols using a pseudo-random number generator. As such, it is customary to refer to this shared text as shared or common randomness.

However, the real power of the REC method is that it does not require the alphabet to be finite or even discrete. Communicating parties could agree on any time-series data, such as weather forecasts, stock prices, or sensor readings. Assuming this data is real-valued, it is futile to wait for any particular value to appear. The remedy is to sacrifice some precision; the easiest way of achieving this is to agree that if the sender wishes to communicate some real number \(X\), they send a time series index where the value of the time series at that index is, say, \(\delta\) close to \(X\). Once again, it is more convenient to generate a real-valued time series using a pseudo-random number generator than to rely on external data.

While these examples are cute, how is the REC method relevant to modern source coding? In lossy source coding, given a source \(X\), such as an image, the goal is to design some algorithm whose output \(\hat{X}\) is “close” or “similar” to \(X\) in some sense, but we need many fewer bits to encode it. Usually, this mechanism is a function with a discrete (and sometimes finite) range, called a quantiser \(\mathcal{Q}\). This choice of mechanism constrains the conditional distribution of \(\hat{X}\) to be a Dirac measure \({\mathbb{P}[\hat{X} \in A \mid X] = \mathbf{1}[\mathcal{Q}(X) \in A]}\). As we will see, relative entropy coding, a general variant of the REC method, removes this restriction: we may choose (!) any conditional distribution \(\mathbb{P}[\hat{X} \in A \mid X]\) for reconstruction. Indeed, after giving a working definition of relative entropy coding, we dedicate the bulk of 2 to describing coding algorithms for any desired target distribution as well as highly efficient ones for special cases.

A consequence of the freedom to pick any arbitrary conditional distribution for the reconstruction is that we may invert the design process for lossy compression: we choose the lossy mechanism \(\mathbb{P}[\hat{X} \in A \mid X]\) that possesses whatever properties our application requires and then worry about its implementation, rather than choosing the mechanism first and then analysing its properties. In 3, we present three applications of this methodology:

1. The “quantisation error” viewpoint. A central challenge in quantisation is characterising and handling the quantisation error \(\mathcal{Q}(X) - X\). Relative entropy coding turns this around: we may choose distribution \(\hat{X} - X\) as desired. An important class of examples is additive noise mechanisms, where \({\hat{X} = X + \epsilon}\) for some random perturbation \(\epsilon\) independent of \(X\). These mechanisms have significant practical relevance, as they enable learned data compression, in which we use machine learning techniques, typically neural networks trained via gradient descent, to learn the noise mechanism. We illustrate this via a curious nonlinear transform coding method: Bayesian implicit neural representations.

2. Data compression with realism constraints. The standard performance measure of a lossy compressor is how much it distorts the original data, given a fixed bit budget called the rate. Unfortunately, with a very low bit budget, the distortion will inevitably be high. Thus, at such low rates, a new objective emerges: to design a compression mechanism such that its outputs appear “realistic” [4].² As we will explain, when considering the rate-distortion-realism tradeoff, quantisers are demonstrably disadvantaged compared to arbitrary noise mechanisms that relative entropy coding can enable.

3. Data compression with privacy guarantees. A powerful framework for quantifying privacy is differential privacy [5], which provides a formal guarantee on how much information about sensitive user data \(X\) can be inferred from released data. To achieve differential privacy, one employs a carefully designed privacy mechanism that randomises \(X\) to obtain a privatised version \(\hat{X}\). Popular mechanisms include the additive Laplace and Gaussian mechanisms for privatising location data, such as GPS coordinates, to prevent precise tracking of an individual, and for privatising model updates in federated learning to prevent the model from memorising users’ data. As we shall explain, privacy mechanisms naturally lend themselves to relative entropy coding, yielding compression algorithms with privacy guarantees.

These benefits come at a cost: general relative entropy coding algorithms are impractically slow compared with comparable quantisation-based methods. A central question, then, is which conditional distributions admit fast algorithms; a theme we will discuss in the next section.

In summary, this article provides a broad, high-level overview of relative entropy coding and its applications. We recommend [6] for readers interested in further computational aspects and applications to learned compression, and [7] for an excellent, comprehensive exposition.

1.1 Notation↩︎

We denote the set of integers by \(\mathbb{Z}\) and the set of positive integers as \(\mathbb{N}\), real numbers by \(\mathbb{R}\), and the set of finite-length binary strings as \(\{0, 1\}^*\). For some notation \(\alpha\) and expression \(\beta\), the expression \(\alpha \mathop{\mathrm{\triangleq}}\beta\) means that \(\alpha\) is defined to be \(\beta\). For integers \(a, b\), we denote the set of integers between and including \(a\) and \(b\) as \({[a:b] \mathop{\mathrm{\triangleq}}[a, b] \cap \mathbb{Z}}\). For a finite set \(A\), we denote the number of its elements as \(\abs{A}\), for a string \(s \in \{0, 1\}^*\), its length is given by \(\abs{s}\). We always round real numbers towards \(+\infty\), that is \(\round{x} \mathop{\mathrm{\triangleq}}\lfloor x + 1/2 \rfloor\), where \(\lfloor x \rfloor\) is the floor function. Natural logarithms are denoted by \(\ln\) while binary logarithms are denoted by \(\mathop{\mathrm{\mathrm{lb}}}\). \(\mathbf{1}[\cdot]\) denotes the indicator function. For a random variable \(X\) taking values in some set \(\Omega\), we denote its expectation by \(\mathbb{E}[X]\) and its probability distribution as \(\mathbb{P}[X \in A] \mathop{\mathrm{\triangleq}}\mathbb{E}[\mathbf{1}[X \in A]]\) for some (measurable) set \(A \subseteq \Omega\). For two random variables \(X, Y\) and a probability distribution \(P\), we write \(X \sim P\) to mean that \(X\) has law \(P\), and write \(X \sim Y\) to mean that the variables are equal in distribution. We denote uniform distributions over the interval \((a, b)\) as \(\mathrm{Unif}(a, b)\), geometric distributions with success probability \(p\) as \(\mathrm{Geom}(p)\), exponential distributions with rate \(\lambda\) as \(\mathrm{Exp}(\lambda)\) and normal distributions with mean \(\mu\) and variance \(\sigma^2\) as \(\mathcal{N}(\mu, \sigma^2)\). Furthermore, we write \(X \mathop{\mathrm{\perp}}Y\) to denote the independence of \(X\) and \(Y\). We denote the Shannon entropy (in bits) of a discrete random variable \(X\) as \(\mathbb{H}[X]\). For two probability distributions \(Q\) and \(P\), we denote the relative entropy/Kullback-Leibler divergence of \(Q\) from \(P\) as \(D_{\mathrm{KL}}\infdivx{Q}{P}\) (in bits). For random variables \(X, Y\), we denote their mutual information as \(I\infdivmi{X}{Y}\) (in bits). Finally, \(\mathcal{O}(\cdot)\) is the standard big O notation.

2 Fantastic Stochastic Codes and How to Construct Them↩︎

We now give a precise definition of stochastic and relative entropy codes; the setting is similar to source coding with its usual assumptions. For a given input \(x \in \mathcal{X}\), our goal is to encode the output of some fixed mechanism \(Y \sim P_{Y \mid X = x}\) over space \(\mathcal{Y}\). As is standard, we assume that the input/source follows some distribution \(X \sim P_X\). The case \(Y = X\) corresponds to lossless source coding, and in any other case, we think of \(Y\) as a lossy representation of \(X\). Then, we look for a triplet consisting of 1) a random variable \(Z\) independent of \(X\), 2) an encoder function \(\mathop{\mathrm{\mathtt{enc}}}_z: \mathcal{X}\to \{0, 1\}^*\), and 3) a decoder \(\mathop{\mathrm{\mathtt{dec}}}_z: \{0, 1\}^* \to \mathcal{Y}\). Observe that the encoder and decoder are actually an ensemble of functions parameterised by some variable \(z\). This triplet “implements” the mechanism \(Y \mid X = x\): \[\begin{align} \label{eq:rec95correctness95criterion} \mathop{\mathrm{\mathtt{dec}}}_Z(\mathop{\mathrm{\mathtt{enc}}}_Z(x)) \sim P_{Y \mid X = x} \end{align}\tag{1}\] Note that the randomness in the above equation comes purely from the shared randomness \(Z\). From the perspective of the “reverse Cardan method” in 1, \(X=Y\) is the “secret” message we wish to encode, \(Z\) is the shared “book,” \(\mathop{\mathrm{\mathtt{enc}}}_Z\) corresponds to constructing a grille for a given book \(Z\), and \(\mathop{\mathrm{\mathtt{dec}}}_Z\) corresponds to laying the grille over the text to reveal the hidden message. We now summarise the above discussion in the following definition.

As we are interested in data compression, in addition to the “correctness requirement” in 1 , we also wish to minimise the expected codelength. This desideratum results in a generalisation of Shannon’s source coding theorem, which, letting \(I = I\infdivmi{X}{Y}\), states that [8], [9] \[\begin{align} \label{eq:universal95relative95entropy95code95rate} I \leq \min \mathbb{E}[\abs{\mathop{\mathrm{\mathtt{enc}}}_Z(X)}] \leq I + 2\mathop{\mathrm{\mathrm{lb}}}(I + 1) + \mathcal{O}(1) \end{align}\tag{2}\] where we minimise over stochastic codes \((Z, \mathop{\mathrm{\mathtt{enc}}}_z, \mathop{\mathrm{\mathtt{dec}}}_z)\). Thus, putting everything together, in analogy to entropy codes, we define relative entropy codes³ as

With these definitions in hand, we will spend the rest of this section examining ways of constructing relative entropy codes; that is, how one should pick \(Z\), \(\mathop{\mathrm{\mathtt{enc}}}_z\), and \(\mathop{\mathrm{\mathtt{dec}}}_z\). Although we aimed for simplicity when possible, some parts are necessarily technical. Readers more interested in the potential applications of these codes may take their existence for granted and skip ahead to 3.

2.1 Relative Entropy Codes from Selection Samplers↩︎

The decoder of any stochastic code must yield a sample from some prescribed probability distribution. As such, it should not be surprising that computational statistics is our first port of call for inspiration.

2.1.1 Rejection Sampling↩︎

We begin with the simplest of samplers: the humble rejection sampler. The usual situation in which the rejection sampler is applied is when we wish to simulate samples from a target distribution \(Q\), but only have access to the following computational primitives:

1. A proposal distribution \(P\): we assume we can generate samples with law \(P\).

2. The Radon-Nikodym derivative \(r \mathop{\mathrm{\triangleq}}dQ/dP\), which we assume we can evaluate. Readers unfamiliar with measure-theoretic mumbo-jumbo should note that when \(Q\) and \(P\) admit probability density functions (or mass functions in the discrete case) \(q\) and \(p\), then \(r = q/p\). As this will be the case for the rest of the paper, we refer to \(r\) as the density ratio for simplicity. Furthermore, we will always assume that \(r\) is bounded from above, and that we can compute its least upper bound,⁴ which we denote as \(\norm{r}_\infty\).

Given these capabilities, rejection sampling has a simple geometric interpretation, illustrated in 2: it simulates a point that falls below the scaled graph of \(r\). Concretely, consider a point \((Y, U)\) with \(Y \sim P\) and \(U \sim \mathrm{Unif}(0, 1)\). Now, a simple calculation shows that conditioned on the event that \((Y, U)\) falls under the scaled graph of \(r\), the first coordinate will be \(Q\)-distributed: \[\begin{align} \label{eq:rejection95sampler95output95distribution} Y \,\,\Bigg\vert\, \left\{U \leq \frac{r(Y)}{\norm{r}_\infty}\right\} \sim Q \end{align}\tag{3}\] 3 suggests the following algorithm to simulate \(Q\)-distributed samples. At each step \(k \in \mathbb{N}\):

1. Generate \(Y_k \sim P\) and \(U_k \sim \mathrm{Unif}(0, 1)\).

2. If \(U_k / r(Y_k) \leq \norm{r}_\infty^{-1}\), return \(Y_k\); else go to step \(k + 1\).

If we let \(K\) denote the step at which rejection sampling terminates, then 3 ensures that \(Y_K \sim Q\).

2.1.2 The Basic Rejection Code↩︎

We now construct a stochastic code \((Z, \mathop{\mathrm{\mathtt{enc}}}_z, \mathop{\mathrm{\mathtt{dec}}}_z)\) from rejection sampling. Since, according to 1 , the goal is to encode a sample from \(P_{Y \mid X = x}\), it stands to reason that we set the rejection sampler’s target distribution \({Q \gets P_{Y \mid X = x}}\). What proposal distribution should we pick? We may pick essentially any distribution whose density ratio with \(P_{Y \mid X = x}\) is bounded for all \(x\). However, Definition [def:relative_entropy_code] provides us with a canonical choice: the marginal \(P_Y\); thus, we set \(P \gets P_Y\). Finally, we set \({r_x(y) \mathop{\mathrm{\triangleq}}\frac{dP_{Y \mid X}}{dP_Y}(y \mid x)}\), which we shall assume to be bounded in \(y\) for all \(x\).

Next, what should we choose for the common randomness \(Z\)? With rejection sampling, the only candidates we could pick are the generated points \((Y_k, U_k)\). Since, by our choice for \(P\), all of them are independent of \(X\), there is no harm in assuming all of them are shared. As such, let us set \(Z^{\mathrm{RS}} \gets \{(Y_k, U_k)\}_{k = 1}^\infty\). There are no practical issues with this choice: if we assume the communicating parties share the same pseudo-random number generator (PRNG) and use the same seed, they can both simulate \(Z^\mathrm{RS}\).

Given what we have so far, the choice for the encoder and the decoder should also be almost clear: for the encoder, we pick the rejection sampling selection rule \[\begin{align} \label{eq:rejection95sampler95selection95rule} K(x, Z^\mathrm{RS}) \mathop{\mathrm{\triangleq}}\min\{k \in \mathbb{N}\mid U_k / r_x(Y_k) \leq \norm{r_x}_\infty^{-1} \} \end{align}\tag{4}\] and for the decoder, we pick \[\begin{align} \label{eq:rejection95sampler95decoder95rule} Y(k, Z^\mathrm{RS}) \mathop{\mathrm{\triangleq}}Y_k \quad \text{where }(Y_k, U_k) \in Z^\mathrm{RS} \end{align}\tag{5}\] We can see that \(Y(K(x, Z^\mathrm{RS}), Z^\mathrm{RS}) \sim P_{Y \mid X = x}\) as required by 1 . There remains one small problem: \(K\) is an integer, not a bit string. We can remedy the issue by using a universal code, such as the Elias \(\delta\)-code [14]. While the \(\delta\) code is quite simple, its precise details are not important for our present discussion; the reader only needs to know that the \(\delta\) code is an invertible function \(\delta: \mathbb{N}\to \{0, 1\}^*\) that encodes a positive integer \(k\) using at most \[\begin{align} \label{eq:delta95code95length} \abs{\delta(k)} \leq \mathop{\mathrm{\mathrm{lb}}}k + 2\mathop{\mathrm{\mathrm{lb}}}(1 + \mathop{\mathrm{\mathrm{lb}}}k) + 1~\text{bits.} \end{align}\tag{6}\] Finally, we construct the rejection code as follows:

2.1.3 Is our construction a relative entropy code?↩︎

The triplet \((Z^\mathrm{RS}, \mathop{\mathrm{\mathtt{enc}}}_z^\mathrm{RS}, \mathop{\mathrm{\mathtt{dec}}}_z^\mathrm{RS})\) is a stochastic code, but what about its expected codelength? The first thing to note is that the samples and rejection decisions at each step of rejection sampling are independent of other steps and identically distributed. Hence, the number of steps \(K(x, Z^\mathrm{RS})\) until the first acceptance is by definition a geometric random variable with mean \(\norm{r_x}_\infty\). An application of Jensen’s inequality shows that \(\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}K(x, Z^\mathrm{RS})] \leq \mathop{\mathrm{\mathrm{lb}}}\norm{r_x}_\infty\). Putting this fact together with 6 and another application of Jensen’s inequality shows that the expected codelength of the rejection code is \[\begin{align} \mathbb{E}[\abs{\mathop{\mathrm{\mathtt{enc}}}^\mathrm{RS}_{Z^\mathrm{RS}}(X)}] &= \mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] + \mathcal{O}(\,\mathop{\mathrm{\mathrm{lb}}}(\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] + 1)\,) \end{align}\] Thus, if \({\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] \approx I\infdivmi{X}{Y}}\), 2 shows that the rejection code is a relative entropy code. This is indeed sometimes the case:

• If \(P_{Y \mid X = x}\) is a uniform distribution for all \(x\), then \[\begin{align} \mathop{\mathrm{\mathrm{lb}}}\norm{r_x}_\infty = D_{\mathrm{KL}}\infdivx{P_{Y \mid X = x}}{P_Y} \end{align}\] and hence \[\begin{align} \mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] = I\infdivmi{X}{Y} \end{align}\] regardless of \(P_X\). A popular example of this is the uniform additive setting, where \(Y = X + U\) with \(U \sim \mathrm{Unif}(-1/2, 1/2)\). However, dithered quantisation is preferable to the rejection code in this case, see 2.2.

• When \(P_X = \mathcal{N}(0, \sigma^2)\) and \(P_{Y \mid X = x} = \mathcal{N}(x, \rho^2)\), we have \(\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] = I\infdivmi{X}{Y} + \frac{1}{2}\mathop{\mathrm{\mathrm{lb}}}(e)\). However, while the average codelength is technically optimal, the algorithm is of little use, since its expected runtime is infinite [6], [15].

• If \(\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty] < C\) for some constant \(C > 0\), the rejection sampler-based code is a relative entropy code according to our definition, though the constants involved might be large [6].

Ideally, we would like a scheme for constructing stochastic codes that are always relative entropy codes. At present, there are two known approaches: 1) to reorder the points the rejection sampler simulates, and 2) to slightly alter the rejection criterion to allow non-uniform scaling of the density ratio \(r\), as opposed to scaling it uniformly with \(\norm{r}_\infty^{-1}\). The reordering approach leads to the so-called Poisson functional representation [9], which is a special case of A* coding [16], [17]. On the other hand, the non-uniform scaling approach yields a class of algorithms known as greedy rejection samplers [8], [15], [18]. Although there is a powerful geometric intuition behind the greedy approaches (especially [18]), their proper construction is too technical for the present paper, and we refer the interested reader to the original material and Chapter 4 of [6]. We present the reordering approach below.

2.1.4 Reordered rejection sampling and the Poisson functional representation↩︎

It is insightful to consider why the rejection code does not always yield a relative entropy code. As we saw in its codelength analysis, the expected rate depends on the selected index \(K\): the smaller \(K\) is, the better the expected rate. However, rejection sampling makes no attempt to minimise the accepted index. To see this, consider that at step \(k\), the rejection sampler proposes a sample \(Y_k\) from some set \(A\) and rejects it. Now, it is perfectly possible that the next step \(Y_{k + 1}\) also falls in \(A\) but is accepted; see 2 for an illustration. Indeed, at the extreme, we could even have \(r(Y_k) = r(Y_{k + 1})\), yet \(Y_k\) is rejected while \(Y_{k + 1}\) is accepted.

This undesirable behaviour occurs because it is possible that \(U_{k + 1} < U_k\). This observation motivates the following idea: once the rejection sampler terminates at step \(K\), we take the simulated random variables \((Y_1, U_1), \dotsc, (Y_K, U_K)\) and sort them in ascending order of the \(U_k\)s. To this end, we define the index sorting function for common randomness \(Z^\mathrm{RS}\), termination time \(K\), and for an index \(k \in [1:K]\) as follows: \[\begin{align} \mathtt{sort}_{Z^\mathrm{RS}}(k \mid K) \,\,\mathop{\mathrm{\triangleq}}\,\, \abs{\{(Y_i, U_i) \in Z^\mathrm{RS}\mid i \leq K, U_i \leq U_k\}} \end{align}\] What happens when we apply this function to the index \(K\) of the accepted sample? Letting \(N \mathop{\mathrm{\triangleq}}\mathtt{sort}_{Z^\mathrm{RS}}(K \mid K)\), we see by the definition of the index sorting function that \(N \leq K\), which makes \(N\) a good candidate for the index to be encoded. Moreover, since the receiver knows \(Z^\mathrm{RS}\), they “only” need to know \(K\) to compute \(N\). Of course, encoding \(K\) just so we can send \(N\) does not make sense, since that is what we wanted to avoid in the first place! Fortunately, there are two direct fixes to this issue that were developed almost at the same time: one approach [6] is to encode \(K\)’s order of magnitude, \(\lfloor \mathop{\mathrm{\mathrm{lb}}}K \rfloor\), and then encode \(N' = \mathtt{sort}_{Z^\mathrm{RS}}(K \mid 2^{\lfloor \mathop{\mathrm{\mathrm{lb}}}K \rfloor + 1})\); the second approach [19] is to assume some additional knowledge about \(K\), such as its expectation, and use this extra information to be able to encode \(N\) without having to encode \(K\). Both approaches yield relative entropy codes; thus, with a bit of “post-processing,” we can use rejection sampling to construct efficient stochastic codes after all.

However, there is a third approach, which is even more elegant: what if we could directly simulate the points \((Y_i, U_i)\) in ascending order of the \(U_i\)s instead of simulating them in a random order and then sorting? This approach is precisely what the Poisson functional representation [9], also known as global-bound A* sampling [16], [17], [20], is and does. Unfortunately, the full exposition of this algorithm requires Poisson process theory. Hence, we only sketch the basic arguments and refer the interested reader to [9], Chapters 4 and 5 of [6], and Chapter 3 of [7].

To reiterate, our goal is to derive a stochastic code that “behaves” as if we ran a rejection sampler and reordered the simulated uniform random variables. At the heart of it all is a distributional identity involving Poisson processes. For the purposes of this paper, we will call a sequence of random variables \((T_1, T_2, \dotsc)\) a Poisson process if the difference between any two consecutive elements is exponentially distributed with rate \(1\), that is, for all \(k \in \mathbb{N}\): \[\begin{align} T_{k} - T_{k - 1} \sim \mathrm{Exp}(1) \end{align}\] By convention, \(T_0 \mathop{\mathrm{\triangleq}}0\). Now, we have the following identity:

For example, when \(k = 2\), for \({U_1, U_2 \sim \mathrm{Unif}(0, 1)}\): \[\begin{align} (\min\{U_1, U_2\}, \max\{U_1, U_2\}) \sim \left(\frac{T_1}{T_3}, \frac{T_2}{T_3}\right) \,\,\Big\vert\,\, T_3 \end{align}\]

But, how can we obtain \(N\) and \(K\) from this? First, to obtain the number of simulated samples \(K\), we look at the acceptance criterion: rejection sampling terminates as soon as it samples a point \((Y, U)\) such that \(U / r(Y) \leq \norm{r}_\infty^{-1}\). By Theorem [thm:order_stat_identity], \(U\) must be equal to \(T_j / T_{K + 1}\) for some \(j\) and likewise \(Y\) corresponds to some \(Y_j\). Rearranging, we see that the algorithm terminates if \({T_j / r(Y_j) \leq T_{K + 1} / \norm{r}_\infty}\). Sadly, we do not know which \(T_j / T_{K + 1}\) corresponds to \(U\). However, serendipitously, it turns out this does not matter: observe that if at some step \(k\) it holds that \[\begin{align} \min_{j \in [1:k]}\frac{T_j}{r(Y_j)} \leq \frac{T_{k + 1}}{\norm{r}_\infty} \end{align}\] we can be certain that there is a \(j \in [1:k]\) such that for \(U = T_j / T_{k + 1}\) the acceptance criterion will hold. The beauty of this observation is that we can check the above criterion sequentially: letting \(\tau_k = \min_{j \in [1:k]}T_j/r(Y_j)\) be the running minimum at step \(k\), the algorithm stops when \(\tau_k \leq T_{k + 1}/ \norm{r}_\infty\). Thus, we define \[\begin{align} K \mathop{\mathrm{\triangleq}}\min\left\{k \in \mathbb{N}\,\,\middle\vert\,\, \tau_k \leq \frac{T_{k + 1}}{\norm{r}_\infty} \right\} \end{align}\] We emphasise that since all we are doing under the hood is “simulating rejection sampling in \(U_k\) order,” the \(K\) above and the runtime of standard rejection sampling are equal in distribution. We use a similar technique to find which point satisfies the acceptance criterion. Letting \({N(k) = \mathop{\mathrm{arg\,min}}_{j \in [1:k]}\{\,T_j/r(Y_j)}\,\}\), the returned index is \(N = N(K)\). Now, although we redefined the algorithm using a Poisson process, our argument above shows that \[\begin{align} N \sim \mathtt{sort}_{Z^\mathrm{RS}}(K \mid K) \end{align}\] To summarise, the Poisson functional representation / A* sampling works as follows. Set \(T_0 \gets 0, \tau \gets \infty\) and \(N \gets 0\). Then, at each step \(k\):

• Simulate \(Y_k \sim P\) and \(\Delta_k \sim \mathrm{Exp}(1)\).

• Put \(T_k \gets T_{k - 1} + \Delta_k\).

• If \(\tau < T_k / \norm{r}_\infty\), terminate and return \(Y_{N}, N\).

• If \(T_k / r(Y_k) < \tau\), set \(\tau \gets T_k/r(Y_k)\) and \(N \gets k\).

• Go to step \(k + 1\)

We can turn this sampling algorithm into a stochastic code analogously to how we constructed the code from the original rejection sampler. For input \(x\), set the target distribution to \(Q \gets P_{Y \mid X = x}\), the proposal to \(P \gets P_Y\) and \({r_x(y) \mathop{\mathrm{\triangleq}}\frac{dP_{Y \mid X}}{dP_Y}(y \mid x)}\). Now, put \(Z^\mathrm{AS}\gets \{(Y_n, T_n)\}_{n = 1}^\infty\) for the common randomness and define \[\begin{align} K(x, Z^\mathrm{AS}) &\mathop{\mathrm{\triangleq}}\min\left\{k \in \mathbb{N}\,\,\middle\vert\,\, \min_{j \in [1:k]}\left\{\frac{T_j}{r_x(Y_j)}\right\} < \frac{T_{k + 1}}{\norm{r_x}_\infty}\right\}\nonumber\\ \label{eq:a95star95sampler95selection95rule} N(x, Z^\mathrm{AS}) &\mathop{\mathrm{\triangleq}}\mathop{\mathrm{arg\,min}}_{n \in [1:K(x, Z^\mathrm{AS})]}\left\{\frac{T_n}{r_x(Y_n)}\right\}\\ Y(n, Z^\mathrm{AS}) &\mathop{\mathrm{\triangleq}}Y_n, \quad \text{where } (Y_n, T_n) \in Z^\mathrm{AS}\nonumber \end{align}\tag{7}\] Then, using the Elias \(\delta\)-code as before, we obtain the A* code / Poisson functional representation triplet.

It is a beautiful theorem of Li and El Gamal [9] that the A* code above is always a relative entropy code.

2.1.5 Selection Samplers↩︎

It is insightful to take stock of the pattern of constructing general-purpose stochastic codes. To this end, we consider selection samplers [6]:

We see that both the rejection sampler and the Poisson functional representation are selection samplers. Given a selection sampler, we can follow the recipe we used before to construct a stochastic code: given an input \(x\), set the target distribution as \(Q \gets P_{Y \mid X = x}\), and the proposal as \(P \gets P_Y\). Then, we set a sequence of i.i.d.samples from \(P_Y\) as the common randomness \(Z^{\mathrm{SS}} \gets \{Y_i\}_{i = 1}^\infty\), where \(Y_i \sim P_Y\). Next, let \(N(x, Z^{\mathrm{SS}})\) and \(K(x, Z^{\mathrm{SS}})\) be the selection rule and runtime of the sampler for \(P_{Y \mid X = x}\) using the proposal sequence \(Z^\mathrm{SS}\), respectively. Finally, let \(Y(n, Z^{\mathrm{SS}})\) denote the \(n\)th element of \(Z^\mathrm{SS}\). Then, we obtain the selection code; see 3 for an illustration.

To demonstrate the utility of the selection sampler abstraction, we turn to an important practical aspect of relative entropy coding algorithms: their runtime. As we saw, the runtime of both rejection sampling and the Poisson functional representation given input \(X = x\) is geometrically distributed with mean \(\norm{r_x}_\infty\). Hence, using the fact that \({\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}r_x(Y)] \leq \mathop{\mathrm{\mathrm{lb}}}\norm{r_x}_\infty}\) and Jensen’s inequality, we find that \[\begin{align} \label{eq:general95rec95exponential95runtime} 2^{I\infdivmi{X}{Y}} \leq \mathbb{E}[\norm{r_X}_\infty] \end{align}\tag{8}\] 8 is bad news: it shows that the average number of samples the algorithm needs to generate scales at least (!) exponentially in the information content. For comparison, entropy coding algorithms such as arithmetic coding scale linearly in the information content.

It is thus natural to wonder whether we could find a selection sampler with a faster average runtime. Unfortunately, this is not so, as Theorem 3.2.1 of [6] shows: the expected runtime of any selection sampler is at least \(\mathbb{E}[\norm{r_X}_\infty]\). This result means that the runtime of the Poisson functional representation is optimal. Readers familiar with computational statistics should not find the above result surprising: sampling is generally a computationally hard problem. One may also view selection sampling-based relative entropy coding as randomised vector quantisation. This view provides some intuition for the necessarily slow runtime: general vector quantisation is known to be a hard computational problem.

However, not all hope is lost: the theorem merely precludes the existence of a universal, fast relative entropy coding algorithm. When \(P_{X, Y}\) admits some structure, it is in some cases possible to utilise it to construct fast relative entropy coding algorithms, as we shall do next.

2.2 Relative Entropy Codes from Dithered Quantisers↩︎

We now take the opposite approach to the previous section: we develop a relative entropy code for additive uniform channels of the form \(Y = X + U\) only, where \(U \sim \mathrm{Unif}(-1/2, 1/2)\). Though this might first appear to be a significant restriction, we will use it as a stepping stone to construct codes for a wider variety of channels.

The basic building block is the following identity:

Since \(N = \round{x + U}\) is discrete, the dithering identity suggests a straightforward way to construct a relative entropy code for additive uniform channels. We set the common randomness as \(Z^\mathrm{DQ}\gets U\) and \(N(x, u) = \round{x + u}\). Similar to the stochastic codes of the previous section, the final step is to turn \(N(x, Z^\mathrm{DQ})\) into bits using some code. While we could use the \(\delta\)-code again, it turns out we can use something much better in this case: we can construct an entropy code \(C_u: \mathbb{Z}\to \{0, 1\}^*\), such as a Huffman code, to encode \(N(x, u)\). As with the \(\delta\)-code, the precise details of entropy codes are not important for the present discussion; the reader only needs to know the following. First, to construct an entropy code \(C_u\) for \(N(X, u)\), we need to be able to compute its distribution. Second, the expected codelength of an entropy code \(C_u\) for \(N(X, u)\) is, well, the Shannon entropy \(\mathbb{H}[N(X, U)]\): \[\begin{align} \mathbb{E}[\abs{C_U(X)}] = \mathbb{H}[N(X, U)] + \mathcal{O}(1) \end{align}\] Fortunately, in the case of dithered quantisation, we can indeed work out the distribution of \(N(X, u)\) by expressing it in terms of the distribution of \(X\) (see Chapter 5 of [21]): \[\begin{align} \mathbb{P}[N \leq n \mid U = u] = \mathbb{P}\left[X \leq n - u + \frac{1}{2}\right] \end{align}\] Thus, let \(C_{u}(n)\) be some entropy code (such as a Huffman code) using the above distribution for \(N\). Then, we can construct the dithered quantisation-based stochastic code:

This code turns out to be very efficient: it can be shown (see, for example, 5.2.1 of [21]) that \[\begin{align} \label{eq:dithered95quantiser95rate} \mathbb{E}[\abs{\mathop{\mathrm{\mathtt{enc}}}_{Z^\mathrm{DQ}}^\mathrm{DQ}(X)}] = I\infdivmi{X}{Y} + \mathcal{O}(1) \end{align}\tag{9}\] Furthermore, a significant advantage of dithered quantisation is that it is blazingly fast: computing \(N(x, u)\) involves only a few basic arithmetic operations, and the average time it takes to encode it with any one of the common entropy codes scales linearly in \(\mathbb{H}[N(X, U)]\)!

2.2.1 Channels are like onions: layered quantisation↩︎

The fact that dithered quantisation is only applicable to additive uniform perturbations might seem quite limiting at first. However, Hegazy and Li [22] showed that we can use dithered quantisation to construct a relative entropy code for any one-dimensional additive unimodal mechanism. The main idea is to find a scale mixture of shifted uniforms (SMSU) representation for the additive noise:

It can be shown that the conditions on \(\epsilon\) in Definition [def:smsu] ensure that \(\epsilon\) always admits an SMSU representation. Taking Gaussians as an example, one can show that letting the scale be twice a \(\chi\)-distributed variable with 3 degrees of freedom \(S \sim 2 \cdot \chi(3)\) and setting \(b(s) = 0\), we have \(S \cdot U \sim \mathcal{N}(0, 1)\).

To construct a relative entropy code, we combine the above with the dithering identity: for any \(x \in \mathbb{R}\), and \(U, U' \sim \mathrm{Unif}(-1/2, 1/2)\) conditioned on \(S\), we have \[\begin{align} \round*{\frac{x}{S} + b(S)+ U} \!- U\,\, \sim \,\,\frac{x}{S} + b(S) + U' } \end{align}\] Multiplying both sides by \(S\), 10 guarantees \[\begin{align} \label{eq:layered95quantiser95identity} S \left(\round*{\frac{x}{S} + b(S)+ U} - U \right) \sim x + \epsilon \end{align}\tag{11}\] From a quantisation perspective, 11 corresponds to randomly scaling and shifting the quantisation grid to achieve the desired distribution. This way, we can also extend the dithered quantiser code to any one-dimensional, unimodal additive noise mechanism \(\epsilon\). First, we set the common randomness to \(Z^\mathrm{LQ}\gets (U, S)\), where \((U, S)\) are the pair of random variables from the SMSU representation in 10 . As before, we are interested in encoding \({N \mathop{\mathrm{\triangleq}}\round*{\frac{x}{S} + b(S)+ U}}\). As with the original dithered quantiser, we can express the distribution of \(N\) in terms of the distribution of \(X\):\[\begin{align} \mathbb{P}[N \leq n \mid U = u, S= s] =\mathbb{P}\left[X \leq s \left(n - b(s) - u + \frac{1}{2}\right)\right] \end{align}\] Now, let \(C_{u, s}(n)\) be some entropy code over the integers, such as a Huffman code, constructed using the above distribution. Then, we can construct the following layered dithered quantiser-based stochastic code:

Arguments analogous to the ones leading to 9 show that \[\begin{align} \mathbb{E}[\abs{\mathop{\mathrm{\mathtt{enc}}}_{Z^\mathrm{LQ}}^\mathrm{LQ}(X)}] = I\infdivmi{X}{Y \mid S} + \mathcal{O}(1) \end{align}\] While the above is a clean expression, it is not immediately clear that it qualifies the layered quantiser code as a relative entropy code, since \(I\infdivmi{X}{Y} \leq I\infdivmi{X}{Y \mid S}\). However, using ideas from [22], it is possible to show that \[\begin{align} I\infdivmi{X}{Y \mid S} \leq I\infdivmi{X}{Y} + \mathop{\mathrm{\mathrm{lb}}}(I\infdivmi{X}{Y} + 1) + \mathcal{O}(1) \end{align}\] which shows that it is indeed a relative entropy code. Furthermore, like dithered quantiser codes, layered quantiser codes are also optimally fast. Thus, layered quantisers provide a complete solution for one-dimensional unimodal additive noise distributions. However, to apply them, we must be able to derive the SMSU representation for the perturbation, which might be difficult in practice.

2.3 Advanced Aspects↩︎

We now touch on a few more advanced features of relative entropy codes and outline some more sophisticated constructions, which lie beyond the scope of this paper.

2.3.1 Considerations regarding common randomness↩︎

First, note that we put no restriction on the common randomness other than that it be independent of the input. An important question is whether common randomness is necessary at all, and if so, how much is required. On the first point: yes, it is necessary. It is possible to construct stochastic codes without common randomness; however, such codes necessarily have significantly higher rates than relative entropy codes. Several works have analysed the amount of common randomness required to construct relative entropy codes. However, the practical relevance of limiting the amount of common randomness remains an open question. Essentially, our experience has been that once we share a pseudo-random number generator seed, generating as many samples as needed has no noticeable impact on the data compressor’s performance. Hence, in practice, we usually treat the cost of shared randomness as a small, constant number of bits that the encoder must use to share its random number generator seed. We refer readers interested in a more in-depth analysis of common randomness to the monograph [7], which provides an excellent survey on the topic.

2.3.2 Fixed-length stochastic codes↩︎

We have discussed only variable-length relative entropy codes and made no mention of fixed-length codes, i.e., those in which every codeword has the same number of bits. For finite, discrete channels, it is possible to construct fixed-length stochastic codes. However, once again, the rate of such codes will be much higher than that of a relative entropy code [7]. Alternatively, we may require only that the code’s output distribution be approximately \(P_{Y \mid X = x}\), as measured by an appropriate statistical distance, such as total variation. We discuss this in the upcoming 2.3.6.

2.3.3 Multidimensional layered quantisers↩︎

As we saw in 2.2.1, layered quantisation essentially solves the relative entropy coding problem for one-dimensional, unimodal distributions almost as conclusively as one can hope for: layered quantiser codes are fast and achieve optimal codelengths. However, while we can apply dithered quantisation to multiple dimensions without any loss of efficiency, extending any layered quantiser is highly non-trivial and, in most cases, appears hopeless. At the heart of the matter is that the dithering identity and the SMSU representation generalise “differently” to higher dimensions. Concretely, the dithering identity in higher dimensions generalises using uniform distributions over very special sets arising from lattice theory, called Voronoi cells (of a lattice). On the other hand, the SMSU identity extends to higher dimensions through the superlevel sets of the density function of the additive perturbation. Thus, layered quantisation generalises straightforwardly only to cases where the superlevel sets of the additive perturbation are the Voronoi cells of a lattice. Unfortunately, aside from the two-dimensional Laplace distribution, we are not aware of any well-known multivariate distribution in which this coincidence occurs. An interesting approach specifically targeted at multivariate Gaussian relative entropy coding was investigated by Kobus et al. [23], who proposed randomly rotating the Voronoi cells to make the additive noise spherical symmetric. While their approach has a better rate than applying Gaussian layered quantisation dimensionwise, it only produces approximate samples.

2.3.4 Sampling-as-search and branch-and-bound samplers↩︎

In 2016, Chris Maddison observed that one could use the theory of Poisson processes to systematically construct selection samplers, such as rejection sampling and A* sampling [16]. [6] extended his observation by introducing two new selection samplers based on Poisson processes. Basically, Maddison observed that random variate simulation can be recast as a search problem over a Poisson process, leading to the sampling-as-search paradigm.

From this lens, the samplers in 2.1 correspond to the most basic search algorithm: linear search. However, the advantage of the sampling-as-search paradigm is that, when the problem at hand has a special structure, we have the vast literature on search problems at our disposal to develop more efficient sampling algorithms.

One powerful idea that carries over is branch-and-bound (BnB) search, an instance of the divide-and-conquer paradigm. At a high level, BnB search recursively partitions the search space and quickly eliminates regions that are provably not containing the object we are looking for. Lifting BnB search to the sampling-as-search domain gives rise to branch-and-bound samplers. Akin to selection samplers, we may also use BnB samplers to construct relative entropy codes. Furthermore, it can be shown that for one-dimensional, unimodal distributions, there exist BnB relative entropy codes, such as a BnB variant of A* coding, whose expected runtime scales as \(\mathbb{E}[\mathop{\mathrm{\mathrm{lb}}}\norm{r_X}_\infty]\), an exponential improvement over selection samplers; see Chapter 5 of [6]. As such, BnB A* coding provides an essentially optimal alternative to layered quantisation for one-dimensional, unimodal distributions at the cost of a small, constant increase of the average codelength. However, unlike layered quantisers, BnB A* coding is much more widely applicable: it only requires that we can evaluate the perturbation’s distribution function, and we do not need to compute an SMSU representation.

2.3.5 The gap between the minimum and achievable rate↩︎

2.3.6 Approximate stochastic codes↩︎

2.3.7 Relative entropy codes from channel codes↩︎

Finally, we briefly mention the recent work of Sriramu et al. [24]. They start from the well-known duality between source coding and channel coding and ask a natural question: whether channel codes can also be used to construct relative entropy codes. They answer this question positively: they use polar codes to construct relative entropy codes for high-dimensional i.i.d. Bernoulli channels, with essentially optimal runtime. Thus, their pioneering work represents an exciting avenue for future research.

3 The proof of the pudding is in the applications↩︎

As we have already hinted, relative entropy is best thought of as an alternative to quantisation for lossy source coding. But what concrete benefits does it offer compared to quantisation? In this section, we collect some of its most salient applications to date.

3.1 Learned lossy data compression↩︎

In lossy data compression, we are given some data \(X \sim P_X\) and a distance measure \(d\), called the distortion. The goal is to design a lossy compression mechanism that outputs some \(\hat{X}\) that is cheap to encode and minimises \(d(X, \hat{X})\) at the same time.

We can employ relative entropy coding to obtain such a mechanism: we design a conditional distribution \(P_{\hat{X} \mid X}\) such that encoding a sample \(\hat{X} \sim P_{\hat{X} \mid X}\) has low distortion. For example, we can require that on average the distortion does not exceed some pre-specified level \(D\), that is, \(\mathbb{E}_{X}[\mathbb{E}_{\hat{X} \mid X}[d(X, \hat{X})]] \leq D\). What is the best we can do under this setup? For a fixed source distribution \(P_X\) and conditional distribution \(P_{\hat{X}\mid X}\), relative entropy coding requires approximately \(I\infdivmi{X}{\hat{X}}\) bits to encode a sample. Thus, the best we can do is \[\label{eq:source95coding95rate95distortion95function} \begin{align} R(D) &= \inf_{P_{\hat{X} \mid X} \in \mathcal{F}} I\infdivmi{X}{\hat{X}} \\ &\text{subject to}\quad \mathbb{E}_{X}[\mathbb{E}_{\hat{X} \mid X}[d(X, \hat{X})]] \leq D. \end{align}\tag{12}\] When \(\mathcal{F}\) contains all possible conditional distributions, \(R(D)\) is known as the rate-distortion function. Note also that \(R(D)\) is closely related to, but not equivalent to, the information rate-distortion function from classical information theory. The two differences are that in learned compression, 1) we do not assume that the joint distribution factorises dimensionwise as \(P_{\hat{X}, X} = P_{\hat{X}_1, X_1}^{\otimes \dim(X)}\) in the definition of \(R(D)\), and as such 2) we do not (and cannot) analyse the asymptotic behaviour as \(\dim(X) \to \infty\).

While the connection to the rate-distortion function is a nice theoretical property, relative entropy coding also offers a practical benefit: we can directly optimise the objective in 12 ; this is called “end-to-end training” in machine learning parlance. Concretely, let \(\mathcal{F}\) be a family of parametric, reparameterisable distributions: we assume that for every distribution \(P_{\hat{X} \mid X} \in \mathcal{D}\), we can write \(\hat{X} = \phi(\theta, X, \epsilon)\) for a deterministic function \(\phi\) with parameters \(\theta\) and independent noise \(\epsilon \perp X\). Furthermore, we assume that \(\phi\) is differentiable in its argument \(\theta\); by far the most popular example of this are the additive Gaussian channels \(P_{\hat{X} \mid X = x} = \mathcal{N}(\theta \cdot x, I)\), which admit the representation \(\hat{X} = \theta \cdot x + \epsilon\), where \(\epsilon \sim \mathcal{N}(0, I)\). Now, borrowing a standard trick from optimisation, we write down the Lagrange dual of the objective in 12 : \[\begin{align} \label{eq:source95coding95rate95distortion95objective} \mathcal{L}(\theta, \beta) = I\infdivmi{X}{\phi(\theta, X, \epsilon)} + \beta \cdot \mathbb{E}[d(X, \phi(\theta, X, \epsilon))] + \mathcal{O}(1) \end{align}\tag{13}\] The relevance of the Lagrange dual is that a minimiser of \(\mathcal{L}(\theta, \beta)\) for each \(\beta\) corresponds to \(R(D(\beta))\) from 12 for some distortion level \(D(\beta)\). With an initial guess for \(\theta_0\), we can directly apply gradient descent, together with the reparameterisation trick, to optimise 13 , using Monte Carlo estimates of expectations where appropriate. Here, we ignore some practical details, such as computing the coding distribution \(P_{\hat{X}}\) and the mutual information term in 13 ; for these, we refer the reader to the excellent monograph [25].

We cannot directly optimise 13 when quantisation is our lossy mechanism, because it does not admit a differentiable reparameterisation. Hence, contemporary learned compression methods that do not use relative entropy coding must resort to approximations. The two most popular approaches are 1) to perform straight-through estimation (STE) for gradient descent, and 2) to use an additive noise approximation. STE-based approaches make the “approximation” during training that the gradient of the quantiser \(\mathcal{Q}\) is the identity instead of being zero almost everywhere: they “set” \(\nabla_x \mathcal{Q}(x) = 1\) during backpropagation. Additive noise-based approaches resort to scalar quantisation and, during training only, approximate \(\round{x} \approx x + U\), where \(U \sim \mathrm{Unif}(-1/2, 1/2)\). Once trained, they switch to hard quantisation for compression.

3.1.1 Case Study: Implicit Neural Representations (INRs)↩︎

The motivation for INRs is simple: virtually all data can be thought of as a function mapping some coordinates to signal values. For example, we may conceive of colour images as functions taking \((x, y)\) pixel coordinates to \((r, g, b)\) colour intensity triplets. An INR approximates this function using a small neural network \(g(x, y \mid \theta)\), effectively “memorising” the data coordinate-by-coordinate.

INRs give rise to a compelling approach to data compression: first fit a model to data \(X\), then encode the model parameters \(\theta\). Direct quantisation, however, poses a challenge, since running gradient descent on quantised parameters is not straightforward. This motivates the use of relative entropy coding. Rather than learning deterministic parameters, we learn a parametric posterior distribution \(P_{\theta \mid X}\). For example, the typical choice is the humble Gaussian: \(P_{\theta \mid X} = \mathcal{N}(\mu, \Sigma)\). We use 13 as the loss function to learn the distribution parameters, such as \(\mu\) and \(\Sigma\) in the Gaussian case, via gradient descent and the reparameterisation trick. Finally, we encode a sample from \(P_{\theta \mid X}\) using relative entropy coding [26].

Note that Bayesian INRs are an unusual form of transform coding: the representation of \(X\) is a draw \(\theta\) from the neural network weight distribution, which we learn with gradient descent and encode using relative entropy coding!

3.1.2 Case Study: Model Compression for Communication-Efficient Federated Learning↩︎

Federated learning enables collaborative model training without centralising clients’ raw data, but suffers from high communication costs as clients repeatedly transmit model updates to a central server. A particularly elegant application of relative entropy coding arises in federated probabilistic mask training (FedPM) [27]. Rather than training all network parameters, clients identify a high-performing subnetwork within a shared, randomly initialised network. The random initialisation is generated from a common seed known to both server and clients. At each iteration, each client trains a local probability mask specifying which parameters to retain, then communicates a sample from this mask distribution to the server, rather than sending the probabilities themselves or the locally sampled mask. Using relative entropy coding, the communication cost decreases from approximately one bit per parameter (for sending a locally sampled mask) to the relative entropy between the client’s local mask distribution and the server’s global mask distribution. More strikingly, as training progresses, local and global distributions converge, progressively reducing communication costs. Experiments demonstrate up to 82-fold bitrate reductions compared to direct mask transmission, corresponding to over 2,600-fold overall compression [27].

3.2 Compression with realism constraints↩︎

In lossy image or video compression, in addition to reconstructing the semantic details of the original data, we also want it to look good at all bit rates. At high rates, this is usually not an issue, but what about low rates? The key insight is that high distortion does not preclude the reconstruction from looking good. A landmark insight came from [28], which introduced the notion of realism. A compressor’s realism depends solely on its output distribution \(P_{\hat{X}}\), and we call any sample from the data distribution \(P_X\) perfectly realistic. However, requiring that our compressor be perfectly realistic is generally unrealistic. Thus, to relax perfect realism, we quantify it with a statistical distance \(\Delta(P_X, P_{\hat{X}})\), and extend the rate-distortion function to include this constraint: \[\begin{align} R(D, \delta) &= \inf_{P_{\hat{X} \mid X} \in \mathcal{D}} I\infdivmi{X}{\hat{X}} \\ &\text{s.t.}\,\,\, \mathbb{E}_{X}[\mathbb{E}_{\hat{X} \mid X}[d(X, \hat{X})]] \leq D \text{ and } \Delta(P_{X}, P_{\hat{X}}) \leq \delta \end{align}\] Here, relative entropy coding provides another benefit over quantisation: there are cases where \(R(D, \delta)\) is strictly lower if we use relative entropy coding than if we quantise. We refer readers interested in the theory of realism to Hamdi and Gündüz’s article [4] appearing in the same issue.

3.3 Variable-rate data compression with diffusion models↩︎

⁵\[\begin{align} \label{eq:perturbed95data} Y_t \mathop{\mathrm{\triangleq}}\sqrt{1 - \sigma_t^2}\, X + \sigma_t \epsilon_t \end{align}\tag{14}\]

3.4 Compressing differential privacy mechanisms↩︎

A pressing concern in data science and machine learning is protecting users’ data privacy. Local differential privacy provides a formal framework for this: each user independently perturbs their own data \(X\) to produce a noisy version \(Y\) before transmission, ensuring that the recipient learns little about the true value. Formally, a mechanism \(M\) mapping \(X\) to \(Y\) is \(\varepsilon\)-locally differentially private if for all pairs of possible inputs \(x, x'\) and all events \(S\): \[\begin{align} \mathbb{P}[M(x) \in S] \leq e^\varepsilon \cdot \mathbb{P}[M(x') \in S] \end{align}\] This guarantees plausible deniability: an adversary observing \(Y\) cannot confidently distinguish the true input value.

A prominent application is federated learning, in which a central server trains a model using distributed gradient descent. Clients compute gradient updates from local data and must transmit them to the server without revealing sensitive information. Popular mechanisms include the additive Gaussian mechanism, \(Y = X + \epsilon\) with \(\epsilon \sim \mathcal{N}(0, \sigma^2)\).

Since users send a noisy version \(Y\) of their data \(X\), this provides another natural application for relative entropy coding: we can express the privacy mechanism as \(P_{Y \mid X}\), and encode efficiently. However, we cannot naively apply any relative entropy coding algorithm to the privacy mechanism; we must ensure that the code (not just the sample it encodes) does not reveal too much about the user’s data. This issue was recently solved by [29], which developed the first privatised relative entropy coding algorithm capable of encoding exact samples from any privacy mechanism.

3.5 Communication-efficient reinforcement learning↩︎

In many reinforcement learning scenarios, the agent executing actions lacks direct access to the reward signal (see 4 for an illustration). This situation arises in human-in-the-loop systems where rewards require human evaluation, in multi-agent settings where rewards depend on collective performance unavailable to individual actors, or when reward computation requires resources (such as large vision-language models) that edge devices lack. These scenarios motivate remote reinforcement learning [30]: a controller observes states and rewards, learns an optimal policy, and must guide remote actors that observe only the state to take appropriate actions over a communication-constrained channel (e.g., a wireless link).

A naive approach is to transmit either the reward or the desired action directly, but both are generally real-valued, which requires costly quantisation. Relative entropy coding offers a more efficient alternative. The key insight is that the actor does not need a specific action, but rather any sample from the controller’s policy. Using relative entropy coding, the actor generates candidate actions from its own policy, and the controller transmits only a short index identifying which candidate to select, thereby enabling exact sampling from the controller’s policy. Crucially, the actor simultaneously learns the controller’s policy via behavioural cloning from the communicated actions. As the actor’s policy converges to the controller’s, the two distributions become more aligned, progressively reducing communication costs. Experiments demonstrate 12-fold reductions compared to transmitting actions directly and 41-fold reductions compared to transmitting rewards.

4 Limitations and Future Directions↩︎

This article provided a brief overview of the theory and applications of stochastic codes and relative entropy coding. However, if relative entropy coding really is the cat’s pyjamas, with so many advantages over quantisation, why is it not used in practice? This question is somewhat unfair, as its applicability to practical data compression was only recognised a few years ago. Nonetheless, relative entropy coding currently possesses two significant disadvantages: speed and synchronisation.

All currently known relative entropy coding algorithms applicable to practical problems are either too slow or too limited, making the design of fast, special-purpose relative entropy codes a major open problem.

The second issue is engineering complexity: REC relies on shared randomness, typically implemented with a shared PRNG seed, which requires the encoder and decoder states to remain perfectly synchronised; desynchronisation leads to catastrophic decoding errors. While this is “only” a matter of rigorous bookkeeping, it remains a monumental underinvestigated engineering challenge.

5 Acknowledgements↩︎

The authors acknowledge financial support from Imperial College London through an Imperial College Research Fellowship grant awarded to GF, and from the UKRI for projects AI-R (ERC Consolidator Grant, EP/X030806/1) and INFORMED-AI (EP/Y028732/1). We thank Jiajun He for his helpful comments, which helped improve 3.3.

References↩︎

---

1. Indeed, this result can be extended to stationary, ergodic sources using Kac’s lemma.↩︎

2. Indeed, this objective is meaningful at high bitrates as well, though it does not matter as much.↩︎

3. As conditional distributions are often thought of as channels in information theory, and \((Z, \mathop{\mathrm{\mathtt{enc}}}_z, \mathop{\mathrm{\mathtt{dec}}}_z)\) simulates a conditional distribution, this concept is also known as channel simulation[7], [10], channel synthesis [11], coordinated sampling [12], or reverse channel code [13] in the literature. Following [6], we distinguish these from relative entropy codes (Definition [def:relative_entropy_code]) by identifying them with stochastic codes (Definition [def:stochastic_code]). This distinction is analogous to lossless source codes versus entropy codes: the former requires only reconstructibility, while the latter also requires a short codelength.↩︎

4. Any upper bound on \(r\) is sufficient to run rejection sampling, but using the least one \(\norm{r}_\infty\) will minimise the runtime and codelength.↩︎

5. It is more common in practice to use the more general formula \(Y_t = \alpha_t X + \beta_t \epsilon_t\), where the interpolants \(\alpha_t\) and \(\beta_t\) are positive functions subject to mild conditions, but here we use \(\sigma_t\) for simplicity.↩︎