LOSSY COMPRESSION WITH DISTRIBUTION SHIFT AS ENTROPY CONSTRAINED OPTIMAL TRANSPORT
Authors: Huan Liu
George Zhang
Jun Chen
Ashish J Khisti
Venue: ICLR 2022 Poster (2022)
Keywords: Image Compression
Image Restoration
Optimal Transport
Deep Learning

Abstract: We study an extension of lossy compression where the reconstruction distribution is different from the source distribution in order to account for distributional shift due to processing. We formulate this as a generalization of optimal transport with an entropy bottleneck to account for the rate constraint due to compression. We provide expressions for the tradeoff between  compression rate and the achievable distortion with and without shared common randomness between the encoder and decoder.  We study the examples of binary, uniform and Gaussian sources (in an asymptotic setting) in detail and  demonstrate that shared randomness can strictly improve the tradeoff. For the case without common randomness and squared-Euclidean distortion, we show that the optimal solution partially decouples into the problem of optimal compression and transport and also characterize the penalty associated with fully decoupling them. We provide experimental results by training deep learning end-to-end compression systems for performing denoising on SVHN and super-resolution on MNIST suggesting consistency with our theoretical results.

Published as a conference paper at ICLR 2022
LOsSY COMPRESSION WITH DISTRIBUTION SHIFT AS ENTROPY CONSTRAINED OPTIMAL TRANSPORT
Huan Liu't, George Zhang" Jun Chen', Ashish Khisti²
MMMMsttr University, UUniversity of Toronto
(1 17, chenjun /emmmmtter...m gq. m3..hhang@mat www.uuttooooooooooo ca, akhist stieece utoronto.ca
ABSTRACT
We study an extension of lossy compression where the reconstruction distribution is different from the source distribution in order account for distributional shift due to processing. We formulate this as generalization of optimal transport with an entropy bottleneck account for the rate constraint due to compression. We provide expressions for the tradeoff between compression rate and the achievable distortion with and without shared common randomness between the encoder and decoder. We study the examples of binary, uniform and Gaussian sources (in an asymptotic setting) in detail and demonstrate that shared randomness can strictly improve the tradeoff.. For the case without common randomness and squared- Euclidean distortion, we show that the optimal solution partially decouples into the problem of optimal compression and transport and also characterize the penalty associated with fully decoupling them. We provide experimental results by training deep learning end-to-end compression systems for performing denoising SVHN and super-resolution on MNIST suggesting consistency with our theoretical results.
INTRODUCTION
Using deep neural networks for lossy image compression has proven to be effective, with rate- distortion performance capable of dominating general-purpose image codecs like JPEG, WehP or BPG (Rippel & Bourdev, 2017; Agustsson et al., 2017; Mentzer al., 2018). More recently, many of these works have included generative aspects within the compression to synthesize realistic elements when the rate is otherwise too low represent fine-grained details (Tschannen al., 2018; Agustsson et al., 2019; Mentzer et al., 2020). Though this has been found to deteriorate rate- distortion performance, it has generally resulted in more pereptuully-pleasiinn image reconstruction by reducing artifacts such as pixelation and blur. Using a distributional constraint as proxy for perceptual measure, several works have subsequently formalized this in mathematical framework known the rate-distortion peresstorriioo-prepttioo tradcoff (Blau & Michaeli, 2018; 2019; Matsumoto, 2018; 2019; Theis Wagner, 2021; Yan et al., 2021; Zhang et al., 2021). 1). As is conventional in lossy compression, these works address the scenario in which both low distortion, whereby each individual image reconstruction resembles the ground truth image, and closeness in distribution in which it not easy to discriminate between image samples from the date-gene distribution and reconstruction distribution, are desirable.
The underlying ideal in conventional compression systems is to have perfect reconstruction with respect to some ground truth input. However this is not the case in applications such as denoising, deblurring, or rusouutcso (SR), which require restoration from a degraded input image. In fact, in these cases ground truth may not even be available. In such applications naturally the reconstruction distribution must match the original source rather than the degraded input distribution. A large body of literature has been devoted to various image restoration tasks, including several methods based on deep learning including both supervised (c.g., (Blau & Michaeli, 2018)) 8)) and unsupervised learning methods (e.g., (Wang et al., 2021b)). Although most of the literature exclusively treats compression
"Equal Contribution

---

Published as a conference paper at ICLR 2022
and restoration separately. in many application they co-oceur. For example, the encoder which records a degraded image may not be co-located with the decoder, but must transmit a compressed version of the image over digital network. In turn, the decoder must perform both decompression and restoration simultaneously.
To that end, we study an extension of lossy compression which the reconstruction distribution is different than the source distribution to account for distributional shift due to processing. The problem can be described as a transformation from some source domain to a new target domain under rate constraint, which generalizes optimal transport. This readily extends other works which view image restoration under the cnnceptionndistortin tradeoff (Blau & Michaeli, 2018) or under optimal transport (Wang et al., 2021b). It also provides generalization of the iite-distortion perrepptonn problem (Blau & Michaeli, 2019) where the reconstruction distribution must be close to the input distribution. Following (Theis & Agustsson, 2021; Theis & Wagner, 2021), we also utilize common randomness as a tool for compression in our setting. Our results are summarized as follows:
We provide formulation of lossy compression with distribution shift a generalization of optimal transport with an entropy constraint and identify the tradeoff between the compression rate and minimum achievable distortion both with and without common randomness at the encoder and decoder. We identify conditions under which the structure of the optimal solution partially decouples the problems of compression and transport, and discuss their architectural implications. We study the examples of binary, uniform and Gaussian sources (in asymptotic regime) in detail and demonstrate the utility of our theoretical bounds.
We train deep learning end-to-end compression systems for performing super-resolution on MNIST and denoising on SVHN. Our setup is unsupervised and to the best of our knowledge the first to integrate both compression and restoration at once using deep learning. We first demonstrate that by having common randomness the encoder and decoder the achievable distortion tradeoffss are lower than when such randomness not present. Furthermore, we provide experimental validation of the architectural principle suggested by our theoretical analysis.
2 THEORETICAL FORMULATION
We consider a setting where an input X ~ px is observed at the encoder, which is a degraded (e.g., noisy, lower resolution, etc) version of the original source. It must be restored to an output Y ~ py at the decoder, where py denotes the target distribution of interest. For example, if X denotes a noise norre-corrupted image and Y denotes the associated clear reconstruction, then py can selected to match the distribution of the original source. We will assume px and py are probability distributions over X, C R. and require X and Y to be close with respect to some fidelity metric, which will be measured using non non-negative cost function d(z, y) over X' y. We will refer to d(.,-) - the distortion measure and assume that it satisfies d(x, y) = 0 and only if y. We further assume that X cannot be directly revealed to the decoder, but instead must be transmitted over a bit interface with average rate constraint. Such scenario occurs naturally in many practical systems when the encoder and decoder are not co-located such as communication systems or storage systems, As one potential application. when aerial photographs are produced for remote sensing purposes, blurs are introduced by atmospheric turbulence, aberrations in the optical system and relative motion between camera and ground. In such scenarios unsupervised restoration is preferred as it often intractable to accurately model such degradation processes and collection of paired training data can be time consuming or require significant human intervention. Unsupervised image restoration has been studied recently in Zhang et al. (2017); Pan et al. (2021); Wang et al. (2021b); Menon et al. (2020). These works also fix the reconstruction distribution ~ py and propose to minimize a distortion metric between the output and the degraded input as in our present work, but do not consider compression.
X
y
Y
Figure 1: Illustration of Theo- rem (no common randomness). Given source distribution px, tar- get reconstruction distribution py and rate Rt we can find quantiza- tions X of X and Y of Y and consider transport between them.
2

---

Published as a conference paper at ICLR 2022
2.1 OPTIMAL TRANSPORT AND EXTENSIONS
Definition 1 (Optimal Transport), Let T'pxx, py-) be the set of all joint distributions px, with marginals px and py. The classical optimal transport problem is defined
inf D(px.PY) Px,yET(xxxrr)
(iddXX)Y)
(1)
where we refer to each px, E TPxx.py) as a transport plan.
Operationally the optimal transport plan in (1) minimizes the average distortion between the input and output while keeping the output distribution fixed to py. This may generate transport plan with potentially unbounded entropy. which may not be amenable in rate-constrained setting. We therefore suggest a generalization to Definition which constrains the entropy of the transport plan. It turns out that having common randomness the encoder and decoder can help in this setting, so we will distinguish between when it is available and unavailable.
Definition 2 (Optimal Transport with Entropy Bottleneck - no Common Randomness). Let Maer(Px (px Py) denote the of joint distributions Px.z, compatible with the given marginal distributions px, py satisfying Px. PxPz|xPyIz- The optimal transport from px to py with an entropy bottleneck of R and without common randomness is defined as
inf Dncr (px. PY, E (p).
E[d(X,
(2)
s.t. 41)2$10
where H() denotes the Shannon entropy random variable.
We note that when the rate constraint R is sufficiently large such that one can select = or in (2), then Ducr (px, py, , R) D(px, Py) in (1). More generally, D(px, serves lower bound for (Px, py, , R) for any R > Definition also has a natural operational interpretation in our setting. We view the encoder implementing the conditional distribution Pz|x to output a representation Z given the input X, and the decoder as implementing the conditional distribution Zyiz to output the reconstruction Y given the representation Z. The entropy constraint essentially guarantees that the representation Z can be losslessly transmitted at rate close to R.
(Z)) & R
Of particular interest to is the squared Euclidean distance d(X, Y) ||X - Yll. As it turns out, when we specialize to this distance function we can without loss of optimality also impose a more structured architecture for implementing the encoder and the decoder. Let W2 be the squared quadratic Wasserstein distance, by using the squared loss in Definition 1.
Theorem 1. Lei
D Dusce (Px (Px.Py, Py,
inf
E|||X
11 + W2(px.Pp)
x PPiy
(3)
E
E
=
B| = Y, H(X) S R. H(M) < R.
and
Dmoe (px:
A inf E|||X 11 pRi
(4)
s.l. H(X)= < R.
Moreover. let
Dnx PY, R) A Disse (px, (px. (px. PY: R) A Dinse (px, R) + D Dusse R).
R) + Dmse (py, R) + W.2 (p Pp.))
(5)
(6)
'The source coding theorem guarantees that any discrete random variable can losslessly compressed using a variable length code with average length of no more than (2) + bits. We also note some differences between this formulation and the distortion rate function from information theory here the target distribution Py is fixed, and we impose a constraint on entropy rather than mutual information reflect that perform compression a per-sample hasis (i.e. the one-shot scenario) rather than on asymptotically long blocks.
3

---

Published as a conference paper at ICLR 2022
where Px- and py- are the marginal distributions induced by the minimizers PX-xx and Py that attain Duse(Px: R) and D (pse R), respectively (assuming the existence of such minimizers). Then under the squared Eucledian distortion measure,
Duce (px, py, R) Duse (px, ,Y, RR.
In addition, we have
PY, R) 2 (ner(px,P PY, R) 2 R), Decr (P and both inequalities are tight when px = py-
(8)
Theorem 1 deconstructs Z into the quantizations X of X and Y Y, and decomposes the overall distortion in (2) in terms of the losses due to quantization, transport, and dequantization (3). also suggests natural architecture that partially decouples compression and transport without loss of optimality, First, the sender uses the distribution P produce the compressed representation X from X. This is then passed through "converter" Py x to transform X to optimal representation Y of Y. Finally, the receiver maps Y back to Y using the conditional distribution Pylý- This is illustrated in Figure 1. The entropy constraint H(X) S R in (2) essentially guarantees that X can be losslessly transmitted to the decoder where the converter can be applied to map X to Y before outputting Y. Alternately the constraint H (Y) R guarantees that the converter could also be implemented the encoder and then Y can be compressed and transmitted the decoder. Finally note that our proposed architecture is symmetric" with respect to the encoder and the decoder and in particular the procedure to transport Y to X would simply be the inverse of transporting X to Y, and indeed the distortion incurred by dequantizing Pyjý is the same as the distortion incurred by quantizing PîIx
For the special case of same source and target distribution, we have Dmse Px. R) = 2D (px, R), implying that the rate required to achieve distortion D under no output distribution constraint (and with the output alphabet relaxed to R') achieves distortion 2D under the constraint that Y equals X in distribution. This recovers the result of Theorem 2 in Yan et al. (2021) for the one-shot setting. More generally, (8) shows that we may lower bound Diss (Px, PY, It) by the distortion incurred when compressing X and Y individually, each at rate R. through ignoring the cost of transport. On the other hand, the upper bound corresponds to choosing the optimal rate-distortion representations X", y for X, Y, then considering transport between them. The advantage of this approach is that knowledge of the other respective distribution is not necessary for design. Although not optimal in general, we will, in fact, provide example where this is optimal in Section 2.2.
Finally, the following result implies that under mild regularity conditions, the optimal converter Py LX can be realized as (deterministic) bijection, and in the scalar case it can basically only take the form as illustrated in Figure
Theorem 2. Assume that (per(px,Py PY, R) is a strictly decreasing function in a neighborhood of R R and Ducr (Px, R²) is attained by px,z,y. Let X & [[X|Z] and y 2 E| 21. Then
H(X) H()) Rt,
E||| - --11 = W2(Px-Pp),
(10)
and there is a bijection between x and V.
We remark that in general computing the optimal transport map is not straightforward. For the case of binary sources we can compute exact characterization for Dnar as discussed in Section 2.2. Furthermore as discussed in Appendix A.6, W 8PPx-Pp Py-) can be computed in closed form when X and Y are scalar valued, which can be used to obtain upper bounds on D In our experimental results in Section 3 we deep learning based methods to learn approximately optimal mappings.
We say that the problem is symmetric if it is invariant under reversing px, Py with new distortion measure defined by reversing the arguments of d(-,-).
4

---

Published as a conference paper at ICLR 2022
No
randormnes
With randomaess
Paax
Pri2
X
PEINU
Y
U
X P
8
Poys
Prpp
X
U
Figure 2: Architectures. Top left: Definition Bottom left: Theorem Top right: Definition 3.
Bottom right: Theorem 3. Entropy coding of intermediate representations Z, X, Y is not shown. For
Theorem 3, the division between sender and receiver is across an encoder C = f(X, U) and decoder
Y = g performing entropy coding along PY|X,U-
So far have focused on the setting when there is shared common randomness between the encoder and the decoder. We will now consider the setting when shared random variable denoted by U is present at the encoder and decoder. We assume that the variable U is independent of the input X so that the decoder has no apriori information of the input. In practice the sender and receiver can agree on a pseudo-random number generator ahead of time and some kind of seed could be transmitted, after which both sides can generate the same U. We further discuss how shared randomness used practice in the experimental section.
Definition 3 (Optimal Transport with Entropy Bottleneck with Common Randomness), Let (ax, (P) denote the set of joint distributions PU,X,Z,Y compatible with the given marginal distributions px, py and satisfying PU,X.Z,Y = distribution of shared randomness. The optimal transport from px to py with entropy bottleneck R and common randomness is defined as
where py represents the
Dor R)
inf P..X M...x.E S.t. ((ZU)S R.
A
E[d(X,Y)
(11)
Note that we optimize over py (the distribution associated with shared randomness), in addition to Pzzxx X,U and PYIZ,U in (11). Furthermore, (Px, 10x.Pr Py: R) S (ncr(Px.Py: Py, R) general, as we do not have access to shared randomness in Definition 2. Also from the same argument that was made following Definition 2, we have that Der (pxx py: It) 2 D(px, in Definition 1. As with also provide natural operational interpretation. In particular, given the input X and common randomness the encoder can output a compressed representation Z using the conditional distribution pz X.U- The representation Z can be losslessly compressed approximately to an average rate of R again by exploiting the shared randomness U. Finally the decoder, given Z and U can output the reconstruction using the conditional distribution PY|Z.U. An interesting difference with Definition 2 is that the setup is no longer symmetric between encoder and decoder, as X is independent of U but Y is not. The following result provides a simplification to the architecture in Definition 3.
Definition 2,
Theorem 3. Let Qer(px, py) denote the set of joint distributions Pu.X.Y compatible with the given marginals px, py satisfying PU,X,Y PUPxPYIU,x well HYUU, 0. Then
inf (id(X,Y))
EQ. .Y) S.I. H(Y R.
(12)
Before discussing the implications of Theorem remark on a technical point. Because the Shannon entropy is defined only for discrete random variables, U must be chosen a way such that Y discrete for each u, even for continuous (X, Y). This is known to be possible. e.g., Li & El Gamal (2018) have provided a general construction for U with this property, with additional quantitative guarantees ensure that U is informative of Y. In the finite alphabet case we show in Appendix A.3 that optimization of U can be formulated as a linear program.
We next discuss the implication of Theorem 3. First note that the problem can be modelled with only Pylu.x producing reconstruction Y without the need for the intermediate representation Z, much like the conventional optimal transport in Definition 1. The condition H (Y 0 also implies that the transport plan is deterministic when conditioned on the shared randomness, which plays the role of stochasticity. Furthermore in this architecture the encoder should compute the representation
5

---

Published as a conference paper at ICLR 2022
03
63
040
102-
02
030
04
04 60
38 68
22
04
6.6
06
(a)
(b)
(c)
Figure 3: Binary case distortion-rate tradeoffs. (a) qx = QY = 0.3, where ne B(qr)) R)
and Ducr (B(qx), ((gy), R) coincide with Duer (B(gx): ((y)). R); (b) qx 0.3, qγ 0.5, where
Derr (B((x) ), ((gv), It) is tight but (B(x)) B( ). It) is loose; (c) gx 0.3, qy - 0.6, where
both bounds are loose. Moreover, it can be seen from all these examples that common randomness can indeed help improve the distortion-raie tradeoff.
Y given the source X and the shared random-variable U (which corresponds to the transport problem) and then compress it losslessly at a rate close to (YU) (which corresponds to the compression problem). The receiver only needs to decompress and reconstruct Y. This is in contrast to the without common randomness in Theorem where the Y must be generated at the decoder.
2.2 NUMERICAL EXAMPLES
We present how the results in Theorem 1 & 3 can be evaluated for some specific source models. We first consider the example of Binary sources. Let X ~ B(gx) and Y ((qy) be two Bernoulli random variables with 9x Qy (0, 1), and let d(;,)) be the Hamming distortion measure dy(:;) (i.e., (x, y) = 0 if æ = and d 3) = 1 otherwise), which coincides with the squared error distortion in Theorem for binary variables. The explicit expressions of Der (B(gx), B(gy), R). D Duer (B(xx); (B(r) ), R) as well as ner (B(gx), (.,B(yy) ), Rt and Dacr (Bexx B(gy) ) R) are pro- vided by Theorem 4 in Appendix A.4, from which the following observations can be made. In general, we have Dacr (B(gx). B(gr), RR) > Der (eex () ) R). i.c., common randomness strictly improves the distortion-rate tradeoff (except at some extreme point(s)). Moreover, as long as B(qx) and B(qr) are biased toward the same symbol (namely, 9x, QY S 1/2 or qx.0y 2 1/22,, the upper bound Duer (B(gx) ). B(gx) ), R) is tight, which implies that blindly using optimal quantizer and dequantizer in the conventional rate-distortion sense incurs no penalty. Some illustrative examples are shown Figure 3.
In Appendix A.6 consider the case when X and Y are continuous valued sources from uniform distribution and establish an upper bound on Ducr that is shown to be tight as the rate R - co. For Gaussian distributions in the asymptotic optimal transport setting (see Appendix A.7 for relevant definitions and results) we present results qualitatively similar to the binary case in Appendix A.8.
EXPERIMENTAL RESULTS
We use two sets of results to illustrate that the principles derived from our theoretical results are applicable to practical compression with deep learning. Importantly, we assume an unsupervised setting in which we have only unpaired noisy and clean images available to us, as in Wang et al. (2021b). Our first experiment is, to the best of our knowledge, the first in which restoration and compression are performed jointly using deep learning. We will furthermore demonstrate the utility of common randomness this setting. The second set of experiments are designed on the principle of Theorem 1. In addition to the generator trained from first experiment, we will construct helper network to allow us to estimate the decomposition (3). This is then compared with the direct loss between the noisy image and constrantd denoising reconstruction. If the losses close, this would suggest that the decomposition is not only without loss of optimality but also effective.
3.1 RATE-DISTORTION COMPARISON WITH COMMON RANDOMNESS
Let px be a degraded source distribution that we wish to restore and py be the target distribution. Our goal is to compress X so that the reconstruction semantically resembles X within target distribution py. For our application, we will use MSE loss as a fidelity criterion. Let f be an encoder, Q a quantizer, and g decoder. For given rate R with common randomness U/ available, we have

---

Published as a conference paper at ICLR 2022
9
92
5
5 V/
h
5
91 81
K0
W5)
V/
(b)
Figure 4: Illustration of our experimental setup. (a) shows the end-to-end learning system with common randomness, where the encoder and decoder have access the same randomness u. (b) presents the network setup for verifying the architecture principle given in Theorem 1.
problem of the form
min S.Q
X ((-0(Q(((XX)))
(13)
s.t. PO(QU((,UU)) = PY, H(QUF(X R,
which parameterized neural networks to implement (11). We also fix Q such that hard constraint on the rate is satisfied and assume f and are sufficiently expressive to map to these fixed quantization points. Let - g(Q(((XXU))) U))). We will use a penalty on the Wasserstein- I distance between py and py in accordance with the Wasserstein GAN (Arjovsky et al., 2017) framework, so that our system is a stochastic constrrnnd autoencoder with GAN regularization. Specifically, we follow the network shown in Figure 4(a) which in addition to Q. and g contains critic h.
For the realization of common randomness in Definition 3, we adopt the universal quantization scheme of Ziv (1985); Theis & Agustsson (2021). Given trained f and & and degraded image X, we generate restored image Y through
Y= x=s(Q((X)+UU)
(14)
where U is the stochastic noise shared by the sender and receiver. Details about the quantization are provided in Appendix B.2. To find appropriate f and 9, use the relaxed objective
L = E|| Y [ AWi
(15)
which is the sum of the MSE and Wasserstein-1 losses weighted by By optimizing our network using this objective, we see two favorable properties. First, the Wasserstein-1 loss ensures the distribution of output is close to that of target images, i.c. py R3 Py for sufficiently large Moreover, the MSE loss that pushes the output Ý to input X ensures that the output structurally resembles X. Consequently, the training objective allows the output to be clear and preserves content from input.
To generate rate-distortion trade-off curve, we modify the encoder produce a different number of symbols ranging from low bit rate to high bit rate and record the MSE distortion loss between noisy inputs and denoised outputs. Figure 5(a) and Figure 5(c) show the curves for image super-resolution and image denoising. We also show some qualitative results in Figure 5(b) and 5(d). As the rate increases, the generated high-quality images are clearer.
As exemplified by the numerical results in Section 2.2, common randomness help reduce the rate that is needed for reconstruction given specific distortion. Equivalently, given fixed rate, a system with common randomness can perform better than one without common randomness. To demonstrate this in practice, we conduct the following experiment. We remove the common randomness setup from the framework in Section 3.1 and alternatively add two independent noises Un and U2 to the encoder and decoder sides. Concretely, under the new setting, (14) becomes
Ý g(Q(((X) + U1) U2)
(16)
Then conduct training using the objective (15) as in the common randomness. The tradeoff curve without common randomness for both tasks are shown Figure 5(a) and 5(c) with orange dots. Performance of the framework is better when there is common randomness.
7

---

Published as a conference paper at ICLR 2022
5
3
6
O
5
8 5
O
3335
6
5
9
8
6
3350
4
6 7 2
0
4
G
2
7
B
8
8
Low-Res
R-8
R-12
2350
8 5
O S 8 5
O S 6
8 8
5
O
5
8 9
0.05
7
6 8
6
0 1 4
/ L 4 7
0
0
6
4
0
6
4
9
7
7
7
7
7
0
A
8
8
A
GT
R= 16
R=20
R-
(a)
(b)
16
16
Z
8 16
2
6N 25
250
6.02
74RA
2
P.
999
3
333
Noisy
R=0
R=
R-
8
Z
8 16
2
16
2
17
6.04
8
24
2
8
2
61
6
240 15
21612
25
240
94
7.7.
94
9
3
30 330
Clear
(d)
Figure 5: (a)(b) The experimental results of times image super-resolution. (c)(d) The experimental results of image denoising. The noise pattern is synthesized by additive Gaussian noise with standard deviation set to 20. (a)(c) Rate-distortion trade-offs. Blue points are the MSE distortion loss for particular rate under the setting of using common randomness, while orange points illustrate the same trade-off without using common randomness. For both tasks, any rate, the performance of using common randomness is better than the case without common randomness. (b)(d) Examples for outputs from several models with different rates. As the rate increases, the outputs become clearer.
3.2 ARCHITECTURAL PRINCIPLE
In the case without common randomness, Theorem implies that (under the rate constraint) the overall distortion B[||X - Y| can be decomposed to the summation of the three distortion terms
B||X - Y = [I| - X11 + E[JYY &1 + W2
(17)
where X and Y are some representations of X and Y under MSE distortion. The chosen rate- distortion representations X for X and Ý for Y must not only be representative of X and Y, but also enjoy low cost of transport between one another. We now seek estimate the overhead of this decomposition in practice.
However, due to the nature of the deep learning framework, the distortion measure between images and compressed representations cannot be explicitly measured. Thus, alternatively develop a two- wwo-branch network to compare the summation of the three distortion components (17) to the overall distortion. First, we take trained f and g from the previous experiment and freeze their weights. Given noisy input X, we encode it through f. then decoder J1 is trained to minimize the distortion with X, and decoder is trained to minimize the distortion with Ý = f((()) which distributionally approximates a clean restoration (we use Y instead of ground truth because we assume an unsupervised setting). Let
Y 9)(((x)), Y2 == -2((()))))
The idea here is that Y, rate-constrained reconstruction of X and Y, is a rate-constrained reconstruction of Y, both of which are produced from compressing X using f. We assume this reasonable as in light of Thcorem 2, there is no loss of optimality doing so given sufficiently expressive neural networks. The overall decomposed loss is then given by
L2 E 1111 +
E|| Y21l +
E|
Y1 12
(18)
(b)
8

---

Published as a conference paper at ICLR 2022
Table I: Results of architecture principle in Theorem 1. The end-to-end loss and decomposed loss are very close for different rates.
Super-resolution
Denoising
Rate
10
20
30
12
30
60
90
End-to-end Loss
0.0558
0.0435
0.0351
0.0308
0.0230
0.0175
0.0140
0.0123
Decomposed Loss
0.0586
0.0453
0.0349
0.0309
0.0243
0.0192
0.0158
0.0139
in which Y approximates X and Y/2 approximates Y. Training is performed jointly over 91 and 92-
One additional point is that 91 and 92 can also be trained separately, although in this case we can no longer assume that f can be reused without loss of optimality, as this objective would not be equivalent to minimizing (18) (there is no control over (c)). We develop an additional experiment in which we optimize encoder-decoder pairs 91 to minimize (a) and f2, 92 to minimize (b), where now Y1 produced using fi. 91 and Y2 using f2. 92. In this setting, we aim to approximate the rate-distortion optimal X and Y corresponding to Duer (px. :) from Theorem using V7 and Y2, and in doing this separate optimization is clear that we will drive down (a) and (b) but increase (c). As it turns out, the resultant values (a) and (b) obtained during joint optimization are not much worse than the values from separate optimization. This provides evidence that in practice, the optimal mnte-distortion representations (i.c. under objective (4)) can be leveraged for the general objective (18) without much loss of optimality, which further suggests that the encoder f1 can be potentially trained without knowledge of py without much performance loss. These can be viewed in Table 2.
Table 2: Comparison of separate vs. joint training for (18). See the above paragraph for explanation. Super-resoluton
Rate Method
4
10
20
30
Joint
Sepurate
Joint
Sepurate
Joint
Separute
Joint
Separate
B X
Y
0.0355 0.0227
0.0356
0.0223
0,0214
0.0136
0.0113
0.0092
0,0083
0.0216
0.0222
0.0206
0.0191
0.0191
0,0172
0.0155
Denoising
Rate
12
30
60
90
Method
Joint
Sepurate
Joint
Sepurate
Joint
Separate
Joint
Separate
B|
X
V1
0.0191 0.0050
0.0190
0.0146
0.0145
0.0117
0.0123
0.0104
0.0107
Yall
0.0046
0.0044
0,0040
0.0038
0.0035
0.0032
0,0030
4 RELATED WORKS
Sinkhorn distances (Cuturi, 2013) are a formulation of optimal transport with a penalty term cor- responding to the mutual information between the source and target distributions. This has been studied in information theory literature (c.g. (Bai et al., 2020; Wang et al., 2021a)). For source coding in particular, Saldi et al. (2015a;b) consider common randomness with constrained output distribution. Blau & Michaeli (2018) evaluated a number of deep image restoration techniques and somewhat counter-intuitively demonstrated a tradeoff between optimizing for distortion and "percep- tual quality", i.e. realism. Wang et al. (2021b) model the shift in distribution due to degradation as an optimal transport problem. However this work does not consider compression and their results are qualitatively different from ours. Meanwhile, output-constrained lossy compression has also been shown improve perceptual quality (Tschannen et al., 2018), leading to the distortionnperreppee framework (Blau & Michaeli, 2019). An analysis of the one-shot distortion rate function was studied recently by (Flkayam & Feder, 2020). Our problem formulation is different as we assume the output distribution is fixed.
5 CONCLUSION AND FUTURE WORK
We consider the setting of lossy compression in which we compress across different source and target distributions. We formulate this as an entroyy-constraine optimal transport problem and provide expressions for characterizing the tradeoff' between compression rate and the minimum achievable distortion with and without shared common randomness. We also develop a number of architectural principles through our theoretical results and provide experimental validations by training deep learning models for super-resolution and denoising tasks over compressed representations. On the theory side it will be interesting to consider the case where there are either rate constraints on the amount of shared common randomness between the encoder and decoder or consider the case when the shared randomness is correlated with the source input, which can arise in many practical applications. On the practical side it will be interesting to experimentally study the a broader set of tasks under distribution shift where our theory could be applicable.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Eirikur Agustsson, Fabian Mentzer, Michael Tschannen, Lukas Cavigelli, Radu Timofte, Luca Benini, and Luc Van Gool. Soft-to-hard vector quantization for end-to-end learning compressible representations. pp. 1142-1152, 2017.
Eirikur Agustsson, Michael Tschannen, Fabian Mentzer, Radu Timofte, and Luc Van Gool. Gener- ative adversarial networks for extreme learned image compression. In Proceedings of the IEEE International Conference Computer Vision, pp. 22 221-231, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214 223, 2017.
Yikun Bai, Xiugang Wu, and Ayfer Özgür. Information constrained optimal transport: From talagrand, to marton, to cover. In 2020 IEEE International Symposium on Information Theory (ISFT), pp- 2210-2215. IEEE, 2020.
Yochai Blau and Tomer Michaeli. The perception-distortion tradeoff. In Proceedings of the IEEE Conference Computer Vision and Putlern Recognition, pp. 6228-6233 2018.
Yochai Blau and Tomer Michaeli. Rethinking lossy compression: The rate-distortion-perrppiii tradeoff. In International Conference on Machine Learning, pp. 675-685, 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
Abbas El Gamal and Young-Han Kim. Network information theory. Cambridge university press, 2011.
Nir Elkayam and Meir Feder. One shot approach to lossy source coding under average distortion constraints. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2389-2393. IEEE, 2020.
Robert Gray and Thomas G Stockham. Dithered quantizers. IEEE Transactions on Information Theory, 805-)880--81,, 1993.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. Advances in neural information processing systems, pp. 5767-5777, 2017. 2017.
Andras Gyorgy and Tamás Linder. Optimal entropy-constrrinne scalar quantization of uniform source. IEEE Transactions on Information Theory, 46(7):200--2711, 2000.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--3324 1998.
Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions Information Theory, 64(11))6967--6778 2018.
Ryutaroh Matsumoto. Introducing the perception-ddisootion tradeoff into the rate-distortion theory of general information sources. IEICE Communications Express, 7(11):427-431, 2018
Ryutaroh Matsumoto. Rate-distortion perceetion tradcoff of variable-length source coding for general information sources. IEICE Communications Express, 8(2):38 42, 2019.
Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self-supervised photo upsampling via latent space exploration of generative models. In Proceedings of the ieee/cyf conference on computer vision and pattern recognition, pp. 2437-2445, 2020.
Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Condi- tional probability models for deep image compression. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4394 4402, 2018
10

---

Published as a conference paper at ICLR 2022
Fabian Mentzer, George D Toderici, Michael Tschannen, and Eirikur Agustsson. High-fidelity generative image compression. In Advances in Neural Information Processing Systems, volume 33, 2020.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2.11.
Xingang Pan, Xiaohang Zhan, Bo Dai, Dahua Lin, Chen Change Loy, and Ping Luo. Exploiting deep generative prior for versatile image restoration and manipulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 11(5-6), 2019.
Oren Rippel and Lubomir Bourdev. Real-time adaptive image compression. In International Conference on Machine Learning, pp. 2922-2930, 2017.
Naci Saldi, Tamás Linder, and Serdar Yüksel. Randomized quantization and source coding with constrained output distribution. JEEE Transactions on Information Theory, 61(1)991-10, 2015a.
Naci Saldi, Tamás Linder, and Serdar Yüksel. Output constrained lossy source coding with limited common randomness. IEEE Transactions on Information Theory, 61(9):4984 4998, 2015b.
Shibani Santurkar, David Budden, and Nir Shavit. Generative compression. In 2018 Picture Coding Symposium (PCS), pp. 258-262. IEEE, 2018.
Lucas Theis and Eirikur Agustsson. On the advantages of stochastic encoders. arXiv preprint arXiv:2102.09270, 2021.
Lucas Theis and Aaron B Wagner. A coding theorem for the rute-distortion-perrepppe function. arXiv preprint arXiv:2104.1366 2021.
Michael Tschannen, Eirikur Agustsson, and Mario Lucic. Deep generative models for distribution- preserving lossy compression. In Advances in Neural Information Processing Systems, pp. 5929- 5940, 2018.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Shuchan Wang, Photios A Stavrou, and Mikael Skoglund. Generalized talagrand inequality for sinkhorn distance using entropy power inequality. arXiv preprint 2tt:::2000004330. 2021a.
Wei Wang, Fei Wen, Zeyu Yan, Rendong Ying, and Peilin Liu. Optimal transport for unsupervised restoration learning. arXiv preprint arXiv:2 025442 2021b.
Zeyu Yan, Fei Wen, Rendong Ying, Chao Ma, and Peilin Liu. On perceptual lossy compression: The cost of perceptual reconstruction and an optimal training framework. In International Conference on Machine Learning, 2021.
George Zhang, Jingjing Qian, Jun Chen, and Ashish Khisti. Universal ate-distortionnperrettoo representations for lossy compression. arXiv preprint arXiv:2106.10311 2021.
Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang. Learning deep enn denoiser prior for image restoration. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3929-3938, 2017.
Jacob Ziv. On universal quantization. IEEE Transactions on Information Theory, 31(3):344 347, 1985.
11

---

Published as a conference paper at ICLR 2022
A THEORETICAL RESULTS
A.1 DISTORTION-RATE vs
FORMULATION
In addition Definitions 2 and 3, equivalently define
Rner(px,Pys D) -
inf
H(Z)
Px.ZYEE M
(19)
s.t.
BId(X, Dr
Ree(px PY, A
inf P (2
(20)
s.t. Y)
Duerfer(Pa (Px,Py R) and Rnarfer(p (px./er ,y, D) are monotonically decreasing in R and D, respectively, so they are the inverse of each other. Sometimes is more convenient to work with this ristodiito formulation.
A.2 PROOFS OF THEORETICAL RESULTS
Proof of Theorem I. For any Px,Z,Y E Muer(px. PY) with H(Z) Σ R.
E ||| -11 [[| X
E[X Z]]]] B[JlY ||| E |
2 (Px, Py, R),
where the last inequality follows from the definition of D muse (pxx PY, R) and the fact that
HE 21} < H (Z) S R.
As consequence, we must have Decr (px. Rt) 2 D (px,py py, R). On the other hand, for any Pxxx Prly with [[ = X, [ Y, H() < R. and H(Y) < R, we can construct
joint distribution Px, y such that X ++ X ++ & <> Y form a Markov chain, Px, = PxPxxxx Py. = prPr'r and Px,y satisfying E||l Y | = W3 (Px.Pt) Note that
|||| r| E|||
X ||3 + BillY - 81 BIJ - 11
X
{1 + Billy - 1 W (Px.
(21)
Let Z A X. It be verified that px,z, (px, pv) and ( H(X) < R. which, together with (21), implies Dncr (px, Py, R) < Dise (Px, PY, R). This completes the proof of (7).
Dropping the term (p in (3) yields
D D (Px, R) D (px: R) Dmse (pY, R),
where
Disse (px, R) inf Bi[| X X11
Pxix
E = X, H(X) S R.
s.t.
and Diso (py, R) is definely analogously. On the other hand, choosing PxIx = Px-x and PplY = Ppny in (3) gives
(px, Py, R) (px, R) + Dmse (py, , R) + (P
where Px and Py.y are the minimizers that attain D (px. R) and D Duse (pr, R) respectively while px and py, are their induced marginal distributions. It is clear that P and pe-py coincide
12

---

Published as a conference paper at ICLR 2022
with PX-Ix and Pg-1y respectively as the constraints [[X[X] = X and B| [ matically satisfied by PX-Ix and Py-ly- This proves (8). For the special case px py, have PX-IX- - Pp-1y and consequently the upper bound and the lower bound in (8) coincide.
Y are auto-
Note that due to the involvement of conditional expectation, X is not necessarily defined over X if X a strict subset of IR= (for the same reason, Y not necessarily defined over y). In other words, the output of the quantizer is not consrained to the input alphabet and needs to be relaxed to IR". As such, Dase (px, R) should be interpreted as the one-shot distortion-rate function with the reconstruction alphabet being R which is in general strictly below its counterpart with the reconstruction alphabet being X' (also known as the distortion-rate- paterrrtttonooo function with an inactive perception constraint) if X is strictly subset of R", This subtle issue, which is often overlooked in the literature, arises when one deals with discrete X and Y (see the binary example in Section 2.2 and Appendix A.4). D
Proof of Theorem 2. than R. this will lead to contradiction by the following argument. Note that
We have that ()x(((X), H{)) S R'. one them, say H HY),, is less
D = E|||X =1 = E]| - + + - 8 + E[J 811)
which depends on Px, y only through Px,x, px,y, and py.g. We can construct a new joint distribution P', such that Px.x' Px.x- 8 = PP = Py,. and X <> X' Y ++ Y form a Markov chain. Denote X' by Z'. It is clear that the induced px,z',y belongs to Maer (px. ). preserves B[|X- - Y1 and H(")) < RR, which is contradictory with the fact that Duer (px: Px: R) is strictly decreasing function in a neighborhood of R = R since R can be set slightly below Ht without violating the constraint (Z') < R. This proves (9), which futher implies the existence of bijection between X and Y
It remains to prove (10). If (10) does not hold, then we can find some Px",""" with Px" PP and - Leverage this px" yn to construct a new joint distribution Px,x", such that Px, = xx Pr, pr,y. and X + X" t P + Y form a Markov chain. Denote A by Z" It is clear that the induced 2x.z",y belongs to Ma (Px.Pr). H("")= = Rt,, and
Pyn = Py such that B"J|X" - [[[[X""""11]]] <
E = E||| -
+ 811
< E||| - 1 BIIY - أ EIJ - 11
= D
which is contradictory with the fact that (px, D) is a strictly decreasing function in neighborhood of D D* & Dncr (Px, Pxx, R*) since D can be set slightly below D* without violating the constraint E[||X - Y $ D. So in conclusion, the converter is a one-to-one mapping. which induces an optimal coupling that attains (p Pg).
Proof of Theorem 3. Choosing PU.X,Y from W2 (px. pr) and setting Z = Y shows that
Dalpx PY, R) S inf Eld(X, Y)]
ELX.YEW(XXPP
s.t. H(YU)) R.
So it remains to prove that this upper bound is tight. In the light of the functional representation lemma, for any (U, X, Z, Y' with pU,X,Z,Y E Mer (px, there exist V1, independent of (U, X). and Vz, independent of (U, X, V1), as well as determintic mappings Φ1 and 62 such that Z O (Z, V2). Let U & (U. Vi, V2). Clearly, ,o", = Pu and
(2(U, X, Vi) and Y (Y X)= O. Moreover, we have
H(Z 2 H(ZUU))
H(YIU))
13

---

Published as a conference paper at ICLR 2022
where the last inequality is due to the fact that Y is determined by (Z, U"). Therefore,
Der R) 2
inf Po' x.Y (W(x-.P))) (PX-PY)
E[d(X, (,0XXYX Y)]
s.t. H(Y - R.
This completes the proof of (12).
Note that each realization of U is associated with deterministic function from X' V. As consequence, the problem boils down to optimizing the probablity distribution defined over this collection of functions. For the finite alphabet case, there are totally |||| such functions. In fact, simple application of the support lemma shows that only [>] + functions need to be assigned with positive probability.
A.3 LINEAR PROGRAM FORMULATION FOR COMMON RANDOMNESS
In the finite alphabet case, we can formulate Theorem as follows:
Dex R)
min
Σ ((
DU
uEll
Σ (u))(((fu(X) S R.
s.t.
wEM
Σ Pc( = (t), y E WELl
where is defined over 4 2 (1,2, | and {S= E (t) is the set of all distinct functions
from X' y. By the support lemma (Appendix C on page 631 El Gamal Kim (201 ()), only |V] +1 functions need to be assigned with a positive probability.
A.4 BINARY CASE
Let (BB) 1gx - qyl and (( A qx + qr - qy Note that D(B) min
min the total variation distance between B(gx) and B(gy). which is the minimum Eld (X, Y)] achievable by coupling X and Y. On the other hand, we have B(dæ (X, Y)] D for X, independent. is clear that ((B) and DB the infimum and supremum of D (B(gx), B(gy) R) (as well as Der(B(ax), B(gy) R)), respectively.
Theorem 4. Assume Hamminn distortion measure. Under common vandomness, have
Qx + qy $ 1 2(1-9x)(1-0r> +2 2--4x 4x -Y, 1-1,, (R)
D (B)) =
(22)
2qxar
1 ( + qy
Qx qy >
for [0, min (olli((())),,(q and (B) for R min(Ha(gx). (g Moreover,
Dncr ( B(
2(1-9N 1(1 qrl
2 9x qr
qx. qr S 3'
1-H1 (It)
24x0y
+ qx + QY,
qy 2 2
1-H, (R)
[2-gx]=-g0 -gy- gx (1))²
2qy (1- (11-1xx)H,,100 (())
1 1-H, (R)
+ H (R)
(1 (1-11, (1))2
4x < 2: 2:
> 1
2
+11-gy)
(ax - H (R))
H1 (
2qx (1 (1-9y HH, (R)
qx 2. <
1- 1-H, (R)
(1- H (R))²
(23)
14

---

Published as a conference paper at ICLR 2022
for E (0, ()) Hyy H. and
(1 (11 +2 9x -y,, 9x, q8 2'
1-H, (1t)
93 toy + 9x +g,
qx, 1X 1/2
Dner ((q))
1-H, (R)
(24)
11 (1 + 11 -9x + qr:
Qx 2 q >
1- H (R)
6x +11- + +1+ qx qr,
9x 2. < 1
1- (I)
for R E [0, min (Ho(gx), Hb( Here, (R) denotes the inverse of the binary entropy function [0, 1/2]. With common randomness,
2(1 9x)xxRR D
Dec (B(()))).
(25)
Hx((x)
for Re pH.(())) and = for R > pHolax). Here, p a haxngg//xx,00 ((11)))(11-9))
Proof (25). There are totally distinct functions from (0. 1} to (0, 1}:
f1(x)= = fa(x)= = 11-2- x, fa(z)= = 0. fa(x) = 1, I (0.
Therefore, we have
Σ (x))) = Hoxx (4) pu (2)),
Nell
Σ [x qxpu + (1 gx)pu (4),
uEll
Σ (u( = p1) + (1 qx0 (2) (4).
NEl
In light of Theorem
R,, ((())) (e(() (1( + Pv(2))
min
s.t. + (1- < D,
(26)
= qy,
(27)
(c(1) (x()
(28)
(29)
Note that
(2( + ( (1 9x (4)
Pu (2) + (xPu (3) + (1 9x (x - Pu PU - Pu (2) - (3))
(30)
-1 9x )o (1) 9xPo (2) + (2qx 1)pu (3) 9x,
(31)
where (30) is due to (28). Moreover, it follows by (27) and (28) that
Pu (3) (1 (1-4x)pp ) (1) Pu (2) -y qY
(32)
Substituting (32) into (31) and invoking the fact that pu (2) gives
Pt (2) + (xPr (3) + (1 qx (4r)
--2(1 - 4x)4x (pu (1) + Pu (2)) + 4(1 - qx gx (xx (
2 2 - 4x (pe (1) + Pt (2)) + D (B)
which, together with (26), implies
(1) (2) 2 2(1 qx )9x
(D(B) D).
15

---

Published as a conference paper at ICLR 2022
As consequence, we must have
Hx(xx)
Rar (.(B((x),B(gx))
(D
-D).
2(1 9x 4x
max
One can readily verify that this lower bound is tight as it is attained by pú with
(1) 2(1 9x 9x)xx
(D max D),
(2) = 0,
(D
D) + -9:
2qx
max
Pú 2(1 qx)
(D - D) gr. max
which satisfies (26)-(29) for D E [D obtained by taking the inverse of Rar (B((x) ) B(gr),
min' Dinkk The expression of Der (e:((()x), R) can be
Proof (22). We will rely on some results which will come after this proof.
Note that Hamming distortion coincides with squared error distortion when = = 10, So Theorem 1, Lemma 1, and Lemma 2 are applicable here. In particular, in light of Lemmas I and 2, for any R 0 and 0, there exists joint distribution Pxλÿy compatible with the given marginal distributions px and py such that X and Y are deterministically related finite-support random variables with H (X) = H(Y) I R and X + X + γ + Y form a Markov chain; moreover, X = [[[ y [Y]] and
E[| X 1 + B[J|Y - - + BII 8119 S
Dner (B B(yr), Ri + e.
(33)
Without loss of generality, we assume X and Ý take value from { and { jim respectively, and ý (X)) where v is a bijection from { to 1 with ÿ = (2,)) = 1, ... .N. Let
0, - p (&z). or equivalently, 0g _ py (ū:), 1, ... N. Note that X = [[ X and Y = B| and only if Px1x (1|&)) &. and Pylÿ (1)::) Dt for 02 0, 1, ,N So the constraints
P (x:))x (1)2,) 9x and Σ Py (0 (1 qy can be written equivalently as MN 0 qx and Ein 0.0: qy- Moreover, it easy to verify that
B||| X x {|] Billy + +
11
N
Σ
0,(1 2.)a Σ 0,(1 - -1-10))0 + Σ 0 - 02)²
1=1
N
Σ
0,( + 01 - 2..0))-
In light of Theorem 1 and (33), the following optimization problem (P) yields an upper bound on D Ducr (px. PY, R) with gap at most C:
N
min (
Σ
01; + - -2ū;0:)
(P)
1m1
s.t.
0 log
< R.
Σ 0, 1
Σ
0
4x
Σ 0:0 qr,
8,
i=1
0 z 0,
t E [0,
i e [0,
i= 1, N.
Given (9;, V... (P) degenerates to a linear programming problem with respect (+: N,, over hyper-
rectangle [0, 1| subject the constraint ΣN 0,4: gx, for which the minimum is attained at
16

---

Published as a conference paper at ICLR 2022
point on edge of [0. 11 Therefore, it suffices to consider (2,) with at most one element different from O and 1. By a similar argument, it can be shown that there is no loss of optimality in assuming that at most one of ft. i 1. .N, takes value other than 0 or 1. Due to the merge of different elements, the one-to-one relationship might not be preserved. Nevertheless, by Lemma 2, we just need to consider deterministically related X and Y with support size at most 3. Applying the linear programming argument (P) with N 3 shows that, the cost of potentially compromising the one-to-one relationship, at most one element the support of X as well the support of Y need to take value different from and 1. In the case that the bijection is lost, X or Y must have a reduced support size. One can restore the bijection by invoking Lemma 2, then use the linear programming argument to assign extreme values to all but at most one element the support. Following this line of reasoning, we can conclude that the attention can be restricted to deterministically related X and ý with support size at most 3 and at most element in the support different from 0 and 1. Moreover, the following configurations can be excluded.
1. Support size 3 and the existence of pairs (f, ii and (ø', ,') for some a > I' and 1 < i/ ((t; 5) is said be a pair if X a <> V û): Since
(i - 0))² + (i' 01)²² ( 1/)² (t' - 0)
22g - 22'' + 25 + 24'9
= 2( - +''(0'' - 9) 0,
it follows that E|| - []]] can be strictly reduced by moving the same amount of probability
from {x = ê, y = ÿ} to {X = a, Ý = j/} and from {x = 3 ,. = //) to {8
H' 8 = ú). This modification does not affect px and py. and consequently (X)), H²)).
E||| X 1 BlJlY [[] remain the same. So the distortion-rate performance of this configuration is strictly suboptimal.
2. Support size = 2 and the existence of pairs (&, 9) and (i', (') for some & > a' and g < f/: Same configuration 1).
3. Support size = 2 and existence of pairs (é, 1) and (0, 9) for some à E (0, 1) and و E (0. 1):
It follows by E[X[ = X and E[y]ý] Y that
Px,y (#. 1) 9x
9x
Px,r Px,r((0,0) (0,0)
5
0 1 1 qr
9x
Clearly, H(X) = H()) = Hx(())) ). Since E (0, and ÿ E (0. 1), we must have qx 98 < ςy, which implies H(X) H()) min HY)). Furthermore, it can be verified that
E|||X - + 11 + E1|I 1
9x ((1 + (1 2
9x
0(1 1)
+ Qx
(1 11-281 2)2
(1
Qx i
Σ qy qx
z
However, this end-to-end distortion obviously achievable when min ( (X), (Y)). So the rate-distortion performance of this configuration is strictly suboptimal.
4. Support size = 2 and the existence of pairs (0, 0) and (1, () for some â E (0, and á E (0, 1): Same as configuration 3).
17

---

Published as a conference paper at ICLR 2022
In view of the excluded configurations, we are left with the case where PXY assigns all probabilitiees
to {X 0, Y 0). {X 1, Y = 1), and {x  Y (}} for some E E [0. 1] and 인 E [0. 11. So
it suffices consider the N = 3 version of (P) with $1
0, ft3 1/a 1, 22 E, and f/2
The constraints Σx=1 0g = 1, Σi=1 0,4² = 4x. and Σ 0.0r = Qy imply
01 = 1 -
(1 8)
03 qx i00
ÿ qy qx
+ 2.
0
In this way, we get a simplified optimization problem (P"):
min 28(1 0 + (1 2 9xx
(P")
0
s.t. qx (1 - 2)0) log 1- (1 - 21- + 0 Olog 1
0 + (ax - =00 1
S
R.
30
& 1], 0 10,
(1- 2)0 E 1or - ex qxl, 20 E [9x - - qx].
Note that (P") does not depend on and consequently yields the exact characterization of Daer (B(gx); B(gy), ), R). Therefore, Rucr (Ber(B()x), B(qy): ), D) is characterized by the following opti-
mization problem (P"):
1
+ 0 log δ + [gx - =0) log 1
min (1 qx - (1 - -))0 log 1- qx - (1 5)
(P")
0,5
qx 30
s.t. 2:(1 2)0 + 122)((yy - 9x) < D,
à E 1], 0 [0,1] 1],
(1 - 2)0 E lay qx 1 - qxl. 20 E lax qy, qx]
Given ă. the objective function of (P") is concave in and consequently its minimum is attained an endpoint of [0, 8), where
A max
Qy
9x
qx Q4
i
1 qx
qx D (1 2t 2gx 9x)
0 A min
1,
1
25 8)
Without loss of generality, we assume gr gx and qx gr S 1. The following statements can be easily verified.
1. For è E [0, D-4x -y
2(1-gr)
QY
1 4
1 QX
2. For & E D+gx- -y qx t
2(1-qv)
24y
0 ςY qX
f
0 D (1 26 qr qx)
24 1)
3. For & E (2 (2x D 9x
24y
gv
qY qX
qx
i
18

---

Published as a conference paper at ICLR 2022
4. For 2
gx_ or |0.0 is empty.
Note that when & E [0, 2x and = !.
(1 - qx - (1- -)) log
+ flogg + (ax - -20) log
1 qx (1 -1-
9x 50
(1 (1-rr) qr
@ log
+ (gx x0) log
qx - if
Holgr)
H(Y).
So it suffices to consider the case å E [0, [x] and 0 = 0, for which (P") is reduced to the following form:
min 7(t),
$c(0,
2x ey
where
1- log
1-E + 4x-2
log 1-2
i E [0,
D+ox ].
1-
ax
2(1-0r)
28 2x-4x 4x + (1 11-22 22 -D
log 28
24
9x 22)ry
n22) A
+ D- (1 28 [gy 9x
log
28
-R)
22
[gr 4
+ 4x + - 28)
log
2(1
A D+9x-9y 9X - 2(1-9y)
2(1
0x
28) DD D
20y
-- log --タx
2x log
[2x tor 2x.1
#
2gr
Note that (2) is continuous function over [0, 2x Moreover, n1)) decreases monotonically from (x(xx) to H/
gy
2-
-g D 2x it follows that
as & varies from 0 to
D+
Since n(ă) is a concave function of 2(-
4x for à E 12x toy
2gv
qy
min
( min { 17(
qx + gy D
QX ) min H₂ ),7)
4x + qr D) Holar))
29
EE ex
ray
4x 'vy
29r
9r
20y
So we have
min
()()
2E|0, 21--yy)
Piax oy
Ju]
tuy D. Xx
20y
-min
Ho( 2
D(B)
D
H
9X qy Hb(ar)
2x
94 D
nuax
D
2qxaY
min
Ho( 2 qx 94 D
Hol
(34)
QX qY
min
17(
+ qx qB
),m
9x
+ q4 -
2(1
qr)
2qy
min
11(}),
2el 2(1
Digg
9X ay
20y
D
where (34) due to the fact that Holgy) 2 Holgx) 2 Hol
2-9x -r- - (with the first inequality
being a consequence of qx S qy and qx + Qr S 1). So the problem boils down to solving
min
(T))
OV lux 21-
Luy
20y
can be verified that the minimum is attained D+ax-9y. This completes the proof of (22). graphical illustration the entropy-constrained optimal transport plan for the binary case can be found in Figure 6.
2(--rr
19

---

Published as a conference paper at ICLR 2022
Proof of (23). Note that
1 mmse (B(gx),
D (B(xx), (B(x)),B((xx),
(1-9x12
9x, qx S 1
H (R)
Re [0, Ho (qx));
qx 1
(R)
9x:
1
Dase (B(g));R)
Ducr (B(qx). ),(()))(()))))))))))))))
2
(1-qy 12
+ qr
qy }
1 1-H
(())
RE [0, H)(
+ Q4
gy 2
H (R)
Moreover, we have
Px- ( 9x (R) H-,,, '1)
HR)(
Re Ho,xx)) S 1
Px- (1) = H (R),
Px- (0) H (R),
R Ho( 2
Px- 1- H (R)
qx
= - H (R),
Pp. Q8 - H (1))
= 1 H²" (R),
1
H- (H)
RE (0, Ho(ov)) S 2
Pp. (1) H (R),
Py. (0) H (R),
1
1 H1 (R), RE Holg))). 2
Pp- 1- H1 (R)
So
W PPp.)
(4x -4
Py S _ or 9x.99 qr 2
H, (I))
(gy - (R))
Hy (R) 20y (1-9x)), (R)
qx < 1/2 qr > 1
1-H, (R)
(1-H, (R))²
(xx qy (B))
H (R)
2 (1 (1 H,, (R)
1x > 1 4 < 1
M,," (R) (R)
(1-11 (R))²
Based on the above expressions, one can easily verify (23) and (24). In particular, it is worth noting that when gx, qy < 1 qx, 9r
2.2
Duer (Bex( B(yr), R) Daer (((()) R)) R [0, min (g(xx)) Ho(gy)]] ie., there is no penalty for using optimal quantizer and dequantizer in the conventional rate-distortion sense.
Remark: It is easy to verify that
(B.(x()x); R)
min (B(((()))B((x)) R) E/0,111
R Ho(gx]
R E [0, Ho(gx)) ax 2
xx
(1 qx)
1 Holgx))
R E [0, Holgx)] qx > }.
Dacr (B(xx) R)
min Dice (B(gx),B() ((9y).R)
E/0,01
1x - H (R), [1- qx -H, (R),
e [0, Ho(ax)) ax <
RE [0, Hs(xx)] qx > 21
which are respectively the conventional one-shot distortion-distortionn function (or equivalently, one- shot distortion-rate-perii pereppeeeeenonnnnn function with inactive perception constraint) for B(gx) with and without common randomness. In general, Duee( (B(gx). R) is different from Duse (Blgx). ), R) (the former is strictly above the latter). The reason is follows: even though the output distribution constraint is removed in the definition of D Dncr (B(gx). ), R), the output alphabet remains to be {0, 1}: in contrast, for D (mse( (B(gx), R). the output alphabet relaxed to IR.
20

---

Published as a conference paper at ICLR 2022
A.5 AUXILIARY RESULTS
Lemma (Finite Support Approximation). For any R 2 0 and > O, there exists joint distribution P compatible with the given marginal distributions px and py such that X +> X t y + Y
form a Markov chain and X is finite-support random variable with H (X) I R (or Y is finite- support random variable with (Y) s R); moreover, [ X. E Y = Y, and
B||| xI] + B YIll + Fl| 811 - Duer (px PY, R) +
Proof. In light of Theorem 1, we can find Px,x, P, such that X + 8 + y + form Markov chain, H(X) R. [[ X, [Y]] and
E||X 1 BiJlY 1ll + EIIX 11 S Ducr (px. R) 2'
(35)
The proof is complete if X is a finite-support random variable. So it suffices to consider the case where X takes value from some countably infinite set { Since E[||X|| < and [B|| e||||||3] < co. it follows that there exists positive integer N such that
P(X ( X + |||| (8:) 4
Let X & if & E ( and X - B E (2 if E ( Note that
E||
17]
= =P{A |EII - X' 81PI8 E (al
PP( ( | & (
= =P(X x||=== 8 (4
+ +P(X E ([]]]=//[[1X-X"""+-""""" 81 (
< <P(S [01"=)))[||XX-X|--------17 (4
< <P(S -
+P(A e
[
+ +P(& E
E [
< B[J|X - 2P ( |B XII + | e [+:]22]]
S B[||X - - B1| - 9119++ 2
(36)
Now define a new joint distribution Px. such that 8x. Px.8 P = P Py: = pr,v. and X <> X" <> 8" <> Y form a Markov chain. is clear that X" is a finite- support random variable with H(")) = H(*') & HXX) S R, X X", E Y". and
B[|X - X"1 11 + ElIyY - 111 + X" - 9"11
< B[||X X'1 Blfly -ll E - 811
< B[||X x1 BIIlY YI1 + B - 2
(37)
< Ducr (px,Pr pY, R) + e,
(38)
where (37) and (38) are due to (35) and (36), respectively. This completes the proof of Lemma 1.
Lemma 2 (Deterministic on Finite Support). Let X <> & +> & t Y be Markov chain with ||X| X, E| Y, and assume that X (or Y) is finite-support random variable. There size
exist deterministically related random variables X' and Ý", with the support size no greater than that of
21

---

Published as a conference paper at ICLR 2022
X
X
Y
Y
0
9
Figure 6: Illustration of the cntropy-constraine optimal transport plan for the binary case (assuming
qx + qy S 1), where P& (0) Py (0) -1,"" (R) with 2 2x Hx- (R) and g qy - H (R)
1-H, (R)
1-H, (R)
It is interesting to note that the quantizer P does not depend on py while the dequantizer Py y
does not depend on px. So they are decoupled in certain sense. Moreover, P Pxix and Pyιε coincide
respectively with optimal quantizer Px. and dequantizer py in the conventional rate-distortion sense when qx ςy < 1/2.
X and H(X)) = H(²')) < (X) (or H(X) = H(")) S H())), such that X + &
form a Markov chain, [ = X [[ = Y", and
E|| - X'11 + B - Y'1l + EIIl 1'1
E|||X X 12 + Billy YIll + EII 11..).
Proof. Let Y & [[ Since Y + Y + Y form Markov chain and [ Ý. we have Y |Ep|X) Construct a new joint distribution , such that xx,x = Px,x Pxi. = "t.i-Py.Y'' = Py, and X ++ X' 8 + form Markov chain. It clear that X X', B|yi` = Y", and and
BIIX -
- - -111
E|| 811 + E[llY f E|Jl F17
EIIX - 811 + E - 81 EIJl - 81 X - 811
F x + B 1T + B|J -P11),
where the last equality is due y E [X]. If the function that maps X' to G (or equivalently. maps X Y) invertible, then X. X', Y' have the same support size and H(X) = H(X)= = H(Y",, which completes the proof. Otherwise, the support size of ÿ" must be strictly smaller than that of X' (which is the same as that of X) and HÝ')) < H(X') = H()). We can alternately reduce the support sizes of X' and Y' using this argument until they are deterministically related (and consequently have the same support size and the same entropy). This can be accomplished in finite number of steps because the reduction in support size cannot continue forever.
A.6 UNIFORM DISTRIBUTION
Let X ~ Unif a) and Y ~ Unif(0, bj be uniformly distributed random variables, where a, b 0. Note that the density functions are given as: px (z) 1.0 < x & a and (y) = J. < S and px (xr) and pv (v) outside these intervals. The cumulative density functions of X and Y are
22

---

Published as a conference paper at ICLR 2022
given follows:
0, X S 0,
0, S
Cx(x)=
a' 0 05asa
Cy(
b 0 0 μ
1, z2a.
1, y 2
Following Peyré & Cuturi (2019, Remark 2.30) have that the optimal transport (without rate constraint) is given by:
Wa = - (b (b-a)²
(39)
where Cx (-) and Cp (-) are the pseudo-inverse of the CDF functions for and as defined in Peyré & Cuturi (2019, Remark 2.30).
We will next develop an upper bound on (ncr Py, R) using Theorem I when the rate is of the
form R = (Ng for any N E (1,2,...}, by considering the following choice for X and y:
3a
5a
(2N
1)a
e &
(40)
2N''
2N
2N
2N
b
3b
5b
(2.N
1)b
Y y
(41)
2N
2N'
2N
2NN
To compute the upper bound we select Pxxx to correspond to scalar quantization of X i.e., given X we select X as point in A' closest to X. The distribution Pýjr is defined in an analogous manner'. Our upper bound can be computed as:
Dtt ner (Px, PY, R) II(X - x) BI( - 8) +
(42)
Note that with A need to compute the third term. Following Peyré & Cuturi (2019, Remark 2.28) we have that:
N we have that FE((X 8) = n and E y
62
12 Thus we only
12
(2(P (b-a)²A² 2²
(2i 1)2
a) (1
1
A
(43)
4N
3
4
Thus using = 2-28 we have that
(b (b=a)²
ttt
2-22
(44)
Note that the upper bound approaches the lower bound in (39) as R + co. with exponential rate of convergence.
For the case of general R, we let N [2 and following Gyorgy & Linder (2000, Theorem 1), select
c'
a
c
a
c 2
....a
c+ (2N 3) 2
2
#1
ds
(45)
bc
b
c
c
c
c
3 c') ....,b 2
c+ (2N 3) 2
2
2
'Please note that we do not claim that the proposed choice is optimal with respect to Dmse in (4) although is known to be optimal solution for a related problem the entropy constrained scalar quantization (Gyorgy & Linder (2000). As result cannot claim to compute the upper bound Dace stated Theorem but provide another upper bound.
23

---

Published as a conference paper at ICLR 2022
RP
4,00
Witex
1.4
1.2
1.0
3,50
0.8
3.00
2,50
2
Rate
Rate
Figure 7: Example of Uniform sources with = 2 and 6 = 5. The left plot shows the lower bound W (px-py) in (39) and the upper bound side in (46), (47) and (50). For comparison we also show the value of (P2xx.P0 Py-). xppPP.) The right plot shows the distortions associated with the quantization and dequantization steps.
py, R) which is the sum of of the right hand
where is the unique solution in the interval (0, 1/N] the equation:
(1 1--6) e)
-c log c c) log
R
N
and d' (1-c) N-1 holds. Note that the length of the first interval is and the length of all other intervals c'. In the special case where R = loga N we will have that == c' = N and our construction for
X and Y is consistent with the previous case.
As before we use Pxxx and Prrr to be the distributions associated with scalar quantization. Thus we have that:
a²c²
c2
BI(X - 8131 = + +(1 - c)
(46)
12
12
6²c2
6²cd2
EI - أ
+ (1 c)
(47)
12
12
Furthermore using the result stated in Peyré & Cuturi (2019, Remark 2.30) have that
N Σ
WT(P = c( -11)2 +
(5. - 0;)²
(48)
j=2
N-1
c+ 2j-18 1 2
=bb (b-o)) aaa + (b 10)a2²
Σ
c)
(49)
j=l
3 ob- + Ed(N
1
cσ (N co 1)2 + (2N 1)(2N)3)))))))) 12
- 3)(N 1)
(50)
Finally, the upper bound Dit (px,P% Py, R) can obtained by summing the right hand side of (46), (47) and (50). We provide a numerical evaluation of this upper bound in Fig. 7.
A.7 ASYMPTOTIC OPTIMAL TRANSPORT
Let X,, X2, and Y,, Yg... ... be i.idd processes with marginal distributions px and py, respec- tively.
24

---

Published as a conference paper at ICLR 2022
Definition 4 (Asymptotic Optimal Transport with Entropy Bottleneck common randomness). The asymptotic optimal transport from Px to py with an entropy bottleneck of R and without common randomness is defined as
D hor PP PY, R)
inf D (px, PY, R),
n21
where
1
Rt) a
inf
Bid(X,, YJ)
px=,z.Yn ( Px 00 PY)
m
s.t. H(Z) S.
Remark: It is clear that Deet (px, R) D Pner(px,yy, R). Moreover, can readily show that [nD (nd (px, pv, R) ] subadditive sequence and consequently Dioe (px.pr; R) =
lim,-+oo D (px. Py, R).
Theorem 5. We have
D (px: Pr, R)
inf Ex.x..MMarnxxx.pv
E[d(X,Y) max IY; Z)) - R.
s.t.
Proof. This result can be specialized from Theorem 1 in Saldi et al. (2015b).
The following result is the counterpart of Theorem in the asymptotic setting.
Theorem 6. Let
D moe (px,Py, R))
inf
B[J|X + 811 W3(px.pp))
PRIX
(51)
s.t. E[X|A] = X, B = Ý, 1(x;8) s R. 1(;;8) SR
and
(px; R) A inf B|J|X 811 pxix
(52)
I(X;8) - R.
Moreover, let
D(0e) ner
(px,py, Py, R) A ( mise (px, R) + D(oo) (pv. R) + (P
(53)
D (px, R) & D(oc) (px, R) + D(oe) (pv R).
(54)
where P and Py- are the marginal distributions induced by the minimizers Px-Ix and Py that attain ((so) (px, R) and ((xe) (py, R). respectively (assuming the existence and uniqueness of such minimizers). Then under the squared Eucledian distortion measure,
((0e) ner
(px,PY, R) = D(oo) (px. PY, R).
(55)
In addition, we have
(20) ner
PY. R) 2 ((00) (px. PY, R) > (px. R),
(56)
and both inequalities are light when px PY.
Proof. For any px,z,Y E Manr (px. with (xx{ < R. E ||
E|||X y11 = El| X
E X |
25

---

Published as a conference paper at ICLR 2022
2 D (px.Pr- Py, R),
where the last inequality follows from the definition of Dlase (px, py, R) and the fact that
max{T(XX; E|X
[Z] (X) I(;
max [(Y; Z)) S R.
In view of Theorem 5, we must have Dierl (px. py. R) 2 D Py..Py,H. PY, R). On the other hand, for any Pxxx Paiy with [| = X. | = Y, ( I R, and ,(Y;Y) & R, we can construct a joint distribution y y such that
X + y + form a Markov chain, Px. PxPX py, = py and Px,s satisfying B||| Y ||
(2 Note that
X | = E||| x | + Billy - r + ||| - 11
E[I|X - x + Bi|ly - Y + W (px py).
(57)
Let Z A X. It can be verified that Px.z,Y E Ma (px pr) and ( max T(X; X), I(; X)) IY D (px, Py, R) I Dod (px.pr, R). This completes the proof of (55).
= I R, which, together with (57), implies
Dropping the term (p in (51) yields
D ((0r) (px, py, R)
(py, Dloo) (px, R) + Dooo (pr, R),
where
1(00) (px, R) inf Bi||X 1
X] = 8, 1(X:8) s R.
s.t.
and D Duse (py, RR) is definely analogously. On the other hand, choosing PxIx = Px and pply" = Pyny in (51) gives
D (px.Py, ( (px, R) mse (py, R)) + (2
where P P and Pr the minimizers that attain Dlsed (px, R) and Dloo (py, R) respectively while pg, and pý, are their induced marginal distributions. It clear that Px-xx and Pyrjy coincide
with Px-xx and Py respectively the constraints [[X X and [[ Ý automat- ically satisfied by P and Pý- This proves (56). For the special case px = py, we have PX-1x- = Py-jj and consequently the upper bound and the lower bound in (56) coincide.
Definition 5 (Asymptotic Optimal Transport with Entropy Bottleneck - with Common Randomness). The asymptotic optimal transport from px to py with entropy bottleneck R and common randomness is defined as
( (px, R)
inf D (px. R),
n21
where
1
D(") (px, R) po,x",2,0 EM (8
inf
E Bid(X,, Xi]
1 S.t. -H(ZUU) R.
Remark: It is clear that D (px,pr, R) Der R). Moreover, one can readily show that (nD(r) (px,Py Py, 1 a subadditive sequence and consequently (80) (px. Pv, R) =
limp-too (8) (px, py, R).
26

---

Published as a conference paper at ICLR 2022
Theorem 7. We have
inf D (px.Pr, px.EE(px.pr)
s.t. I
Proof. This result is known (see Theorem 7 in Saldi et al. (2015a)). is possible to give a simpler proof of the achievability part by leveraging Theorem 3 and the strong data processing inequality Li & El Gamal (2018). The converse is based on standard information-theoretic arguments.
A.8 GAUSSIAN CASE
Let X ~ M(xx, and Y ~ NNur o be two Gaussian random variables, and let d(:: be the squared distortion measure (i.e., d(x, v) = (xr - y)²). Let D(G) - (μx yyy)² + (ax - oy )² and D & (ux 2x) + +ox o². Note that Dici is the squared W distance between M(ux, and ((uy,ay) which is the minimum IE[(X - Y) achievable by coupling X and Y. On the other hand, we have B[(X - Yy = D for X, Y independent. clear that D(C) and Diak are the infimum and supremum of Diee) (N(xx, ( (f Rt) (as well as D (W(xx, Nux,, ,y), R)), respectively.
Theorem 8. Assume squared distortion measure. Under no common randomness, we have
Dlo (N(xx, of), Ri) =D(C) 20xoy2-2R,
R (0)
(58)
Moreover,
((0)) (N(xx, xx),,N(Hy ( D
Re (0,00),
(59)
D (N(xx, Nx),N((H,, ob), = =oxx + ox 22-28,
2R
Re {
(60)
With common randomness.
(N(x, ,.), R) D(G) 20xxx 20 2222R 2-28 10)
(61)
Proof. Consider Px and Pyjr such that E[X (2) ((x;)) s R. and 1(Y; 8) < R. Denote the mean and the variance of X by px and xx respectively. Similarly, denote the mean and the variance of Ý by My and oz. respectively. Clearly, Mx px. My uy, = E((x X ) and of of B((Y ry.]. Moreover,
w2(px 2 W2(N(( o² (. of))
=(1x 11y12 + (ox )
(ux 2x)2 (0 0z)²
So we have
E((X X) + ElflY 81 W (2(
2 x 2 x oの - -0 (μx - px) + (ax - 02
D()) 20 08.
(62)
can be verified that
R x(X;8)
log (og(2 - h(x18)
2
2 2 log(2 - 1(x - X)
27

---

Published as a conference paper at ICLR 2022
1
1
2
log (TTEX}
1og(2reL3((X- -X)9))
2
log
x
0 gx
which implies
0x S 50 2-2R
(63)
Similarly,
By S σy V 2222R 2R.
(64)
Substituting (63) and (64) into (62) and invoking (55) Theorem 6 shows
D (x)) ner
(N(xx N ,yy), R) 2 [ + 20 2R
To see that this lower bound tight, we can let
X Y Y= N
(65)
(66)
where X NNuxx - )-) is independent of N 030
2n) while y
(uy, of 2)2 is independent of Ñ ~ 22 ) This completes the proof of (58).
To prove (59) and (60), suffices to note the well-known fact that Pxix and Pyly associated with (65) and (66) attain D ((Xx xx
2),R R) and ( (N(Hy, .8), R), respectively.
Now we proceed to prove (61). Consider px, E (x)(uxx,,x),,Nuxxxx, with T(X;Y) s R.
Let & A E(( (x - My)]. )}. We have
E[(X - Y) D(G) 25.
(67)
Moreover,
R I(X;Y)
2 log(2Tee0
log(2 (2TTTo) - h(X,Y)
2 2
Log(2Tee 2 )
+
log (og(2Teo?) loge(2Te) ( 2f - +))
2
log ox
2 oz
which implies
sxaxx v 2-22
(68)
Substituting (68) into (67) and invoking Theorem shows
(N(xx, N Rt) 2 D(G) 20x V1-
To see that this lower bound is tight, we can let X and Y be jointly Gaussian with & ax v 2-28 This completes the proof of Theorem We acknowledge that the expres- sion of D (N N, for the special case when the Gaussian distributions have zero mean. However, to the best of our understanding, they only provided an upper bound for the case of no common randomness.
Rt) was established in (Saldi et al., 2015b, Section IV-B)
In Figure 8, We plot D (N(px, (, D( (N( ((u,, o7), R), and D o3) oz), R) for two illustrative ex-
D(oo) amples.
28

---

Published as a conference paper at ICLR 2022
2.00
of Al, 08,
02 tolla ob..Mon of)
wil wft. ol), R)
1.75
5-
D tap of waa o8) R)
DiNAA 08),
Mi off. Alpr. 0B),
Oo off. Matr. oft. R)
Ditorton
Dierortion
1.00
0.75
0.50
1-
0.25
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
(a)
(b)
(a) μx = by 0, ox or 1, where D(oO) (x)x (u)),,t.))) R) and ((00) ox Dioek (N(ux, xx) (uy,, , R)); (b) = 0,0x = 1, by σy = 2. where D (oo) (N(xx,o)); ( o²), It) is tight but ner o ()) Rt) is loose. More- over, it can be from both examples that common randomness indeed help improve the distortion-ral rate tradeoff.
Figure 8:
Gaussian case distortion-rate tradeoffs.
coincide with
B EXPERIMENTAL RESULTS
B. DATASET
Image super-resolution is conducted on MNIST (LeCun et al., 1998). For synthesizing low-resolution images, we perform bilinear downsampling on the original image from 28 x to 7 The samples in Figure 5(b) show that the low resolution digits are blurry and some of them are hard to recognize. Image denoising conducted on SVHN (Netzer et al., 2011). 1). our experiments, we synthesize the noisy image with additive Gaussian noise. The standard deviation is set to 20.
B.2 UNIVERSAL QUANTIZATION
Let be our codebook for quantization. Recall that the encoder uses tanh activation so its output lies in 1-1, Given dimension d and quantization levels per dimension as parameters. will consist of L uniformly spaced intervals across all dimensions. The upper bound of model rate is given by (L.) With this codebook, universal quantization (Ziv, 1985; Gray & Stockham, 1993; Theis & Agustsson, 2021) is implemented as follows. We assume the sender and receiver have access the same u 1[-1/(T 1), +1/(L 1)]d. The sender computes
arg min [I(()) su-cl ell
oEC
and sends = to the receiver. The receiver decodes the image by passing w through the decoder. This is also known as subtractive dither in literature (Gray Stockham, 1993). For super-resolution and image denoising, the interval L is respectively fixed at 4 and 8.
B.3 TRAINING DETAILS
To induce distributional shift, we use the Wasserstein GAN for our experiments. alternate between training the encoder/decoder S. and the critic h. By Kantorovich-Rubinsteinn duality (Villani, 2009), the critic is used to approximate
W1 (P(p.
sup E[h(Y)] E[h(ý)), [VlliS
(69)
29

---

Published as a conference paper at ICLR 2022
where Y with gradient penalty (Gulrajani et al., 2017) in practice.
for U as in Appendix B.2. The Lipschitz constraint is implemented
Super-resolution. The training for end-to-end network lasts for 50 epochs. in (15) fixed at le 3 across all rates. The learning rate initialized to be 0.0001 and is decayed by a factor of after 30 epochs. The Adam (Kingma detailed training setting. For the helper two-branch network at a specific rate constraint, we load the pre-trained encoder weight of the corresponding end-to-end network, as well as two randomly initialized decoders 91, .2. Note that only theese two decoders are trainable. During training, use the Adam optimizer with the learning rate initialized at 0.0001. There are a total of 100 epochs until the convergence of the two decoders. The learning rate is decayed once at 50 epochs by factor of 5. Detailed training settings are shown in Table 4.
Ba, 2014) optimizer is used. Table illustrates the
Image Denoising. The experiments for image denoising share many settings with image super- resolution. Tables 3 and 4 can be reused reproduce the experiments on image denoising. Here, we list the difference between them. For denoising, the end-to-end model trained for 100 epochs with À fixed 3e 3 across all rates. The learning rate is decayed by factor of 5 after 40 epochs. The two-branch model is trained for total 200 epochs and we decay the learning rate at 100 epochs by factor of 5.
Table 3: Hyperparameters used for training end-to-end model in Fig. 4(a). is the learning rate, (81, B2) are the parameters for Adam, and AGP is the gradient penalty coefficient.
B2
AGP
Encoder 10-1
0.5
0.999
Decoder 10-1
0.5
0.999
Critic 10-4
0.5
0.999
10
Table 4: Hyperparameters used for training two-branch model in Fig. 4(b). is the learning rate, (3,, 52) are the parameters for Adam, and AGp is the gradient penalty coefficient.
B1
B2
AGP
Encoder
Decoder-1
10
0.5
0.999
Decoder-2
10 10-4
0.5
0.999
Critic
10 4
0.5
0.999
10
B.4 DETAILED RESULTS FIGURE.
In Fig. 5(a)(c), have provided comparison between the with without common randomness the form of a seatter chart. Here, we present detailed quantities of each point in Fig. 5(a)(). Table 5 shows the number of each dot for super-resolution experiments, and Table 6 present the value of each dot for image denoising. From the two tables, we can further see the utility of common randomness quantitatively.
B.5 COMPARISON WITH BASELINE
To illustrate the effectiveness of our system, we compare with a baseline method that separately deal with the tasks of image restoration and compression. For the restoration (image super-resolution and denoising), we respectively build two U-Nets with skip connections and train them in the unsupervised manner by adopting the Eq. 15 objective i.c.,
L = E|| Y W
(70)
After the restoration networks are trained to converge, we fix their weights and use them to pro- duce restored images Y given degraded one X. Afterwards, we adopt our end-to-end network as compression network by minimizing the following loss different rates:
30

---

Published as a conference paper at ICLR 2022
Table The detailed number of MSE distortion loss in Fig. 5(a).
Super-resolution with Common Randomness
Rate
4
8
10
12
14
16
18
MSE
0.0515
0.0457
0.0420
0.0394
0.0372
0.0353
0.0339
0.0324
Rate
20
22
24
26
28
30
32
MSE
0.0313
0.0300
0.0297
0.0285
0.0280
0.0277
0.0269
Super-resolution without Common Randomness
Rate
8
10
12
14
16
18
MSE
0.0558
0.0506
0.0463
0.0435
0.0415
0.0396
0.0383
0.0367
Rate
20
22
24
26
28
30
32
MSE
0.0351
0.0337
0.0331
0.0328
0.0315
0.0308
0.0300
Table 6: The detailed number of MSE distortion loss in Fig. 5(c).
Image Denoising with Common Randomness
Rate
12
18
24
30
36
42
48
54
60
MSE
0.0219
0.0195
0.0175
0.01634
0.0154
0.0147
0.0138
0.0135
0.0129
Rate
66
72
78
84
90
96
102
108
114
MSE
0.0126
0.0123
0.0118
0.0117
0.0115
0.0112
0.0109
0.0107
0.0106
Image Denoising without Common Randomness
Rate
12
18
24
30
36
42
48
54
60
MSR
0.0230
0.0208
0,0189
0.0175
0,0165
0.0157
0.0151
0.0145
0.014
Rate
66
72
78
84
90
96
102
108
114
MSE
0.0137
0.0133
0.0130
0.0127
0.0123
0.0120
0.0118
0.0116
0.0114
L = B - y+ + (PY,
(71)
where Y+ is the outputs of compression network. Note that, to guarantee the distribution of reconstructed Y+ is close to that of target images, we implement a penalty on the Wasserstein-1 distance in (70) and (71). For the image super-resolution, we experimentally selected A = 0.05 and experimentally selected \ 0.03 and x 0.005. Once
Ag = 0.01. For the image denoising, the compression network is converged, we report the final MSE distortion between Y+ and X using E|||X - 1|..
The detailed results for entropy-constrained image super-resolution and denoising are respectively shown in Table and Table 8. It can easily check throughout the tables that our end-to-end systems outperform the baselines.
B.6 COMPARISON WITH GROUND TRUTH
In order to illustrate the rate-distortion trade-offs, we report the MSE distortion that is measured between degraded input images and decoder outputs in Figure Since the input and output distribu- tions are different, we do not expect MSE + 0 as the rate increases. The MSE distortion between degraded input and restored output is still able to reveal how much content information of the input is preserved in output (lower is better).
We now additionally show the MSE distortion between ground truth and decoder outputs in Tables and 10. Concretely, we measure MSE distortion E[|lY Y [2], where is ground truth and Y is the network output. Note that for training, the ground truth is only used in unsupervised fashion
31

---

Published as a conference paper at ICLR 2022
Table 7: Comparison between our end-to-end system with the baseline method for image super- resolution. Numbers are the MSE distortion loss for particular rate. Best results are in bold.
Super-resolution with Common Randomness
Rate 4
10
12
14
16
18
Baseline
0.0603
0.0568
0.0544
0.0530
0.0523
0,0511
0.0503
0.0498
Ours
0.0515
0.0457
0.0420
0.0394
0.0372
0.0353
0.0339
0.0342
Rate
20
22
24
26
28
30
32
Baseline
0.0489
0.0485
0.0484
0.0482
0.0478
0.0476
0.0471
Ours
0.0313
0.0300
0.0297
0.0285
0.0280
0.0277
0.0269
Super-resolution without Common Randomness
Rate
4
10
12
14
16
18
Baseline
0.0620
0.0585
0.0573
0.0555
0.0543
0.0535
0.0532
0.0520
Ours
0.0558
0.0506
0.0463
0.0435
0.0415
0.0396
0.0383
0.0367
Rate
20
22
24
26
28
30
32
Baseline
0.0517
0.0512
0.0506
0.0505
0.0497
0.0495
0.0490
Ours
0.0351
0.0337
0.0331
0.0328
0.0315
0.0308
0.0300
Table 8: Comparison between our end-to-end system with the baseline method for image denoising. Numbers are the MSE distortion loss for a particular rate. Best results are in bold.
Image Denoising with Common Randomness
Rate 12
18
24
30
36
42
48
54
60
Baseline
0.0242
0.0213
0.0189
0.0173
0.0162
0.0154
0.0148
0.0142
0.0136
Ours
0.0219
0.0195
0,0175
0.0163
0.0154
0,0147
0.0138
0.0135
0,0129
Rate
66
72
78
84
90
96
102
108
114
Baseline
0.0134
0.0130
0.0127
0.0124
0.0120
0.0118
0.0116
0.0111
0.0110
Ours
0.0126
0.0123
0.0118
0.0117
0.0115
0.0112
0.0109
0.0107
0.0106
Image Denoising without Common Randomness
Rate
12
18
24
30
36
42
48
54
60
Baseline
0.0252
0.0216
0.0202
0.0185
0.0178
0.0164
0.0158
0.0154
0.0149
Ours
0.0230
0.0208
0,0189
0.0175
0.0165
0.0157
0.0151
0.0145
0,014
Rate
66
78
84
90
96
108
114
Baseline
0.0147
0.0144
0.0140
0.0135
0.0133
0.0129
0.0126
0.0120
0.0117
Ours
0.0137
0.0133
0.0130
0.0127
0.0123
0.0120
0.0118
0.0116
0.0114
with umpaired noisy images, and here the ground rutth image pairs only used for test time evaluation. Note also that the MSE distortion is correspondingyy lower common randomness is adopted.
Table 9: Illustration of MSE distortion between network outputs and ground truth for super-resolution.
Super-resolution with Common Randomness
Rate MSE
12
16
20
24
28
32 0.0343
0.0582
0.0464
0.0408
0.0380
0.0360
0.0353
0.0348
Super-resolution without Common Randomness
Rate
4
8
12
16
20
24
28
32 0.0345
MSE
0.0646
0.0492
0.0426
0.0390
0.0375
0.0362
0.0353
32

---

Published as a conference paper at ICLR 2022
Table 10: denoising.
Illustration of MSE distortion between network outputs and ground truth for image
Image Denoising with Common Randomness
Rate 12
24
36
48
60
72
84
96
108
MSE
0.0157
0.0114
0.0092
0.0077
0.0069
0.0062
0.0056
0.0052
0.0047
Image Denoising without Common Randomness
Rate
24
36
60
72
84
96
108
MSE
0.0169
0.0128
0.0104
0.0090
0.0080
0.0072
0.0066
0.0060
0.0057
B.7 BREAKDOWN OF THE TABLE
is worth reminding that the each number in Table is the total distortion 18. Here, we provide a breakdown of total distortion in each of the three term for joint training, i.e, E[[ y 19). ElJl 2] and B| - {.
B.8 NETWORK ARCHITECTURE
Super-resolution.
The detailed network structure for end-to-end model and two-branch model respectively presented in Table 12 and Table 13. The last linear layer of the encoder controls the number of output symbols.
The detailed network structure for end-to-end model and two-branch model are respec- tively presented Table 14 and Table 15. The last linear layer of the encoder controls the number of output symbols.
Denoising.
Table 11: Breakdown of the Table 1. At any rate, it can be observed that the total losses of our approximation system (Lz) are very close to that of end-to-end learning system under the setting without common randomness [EE X Y I
Image Super-resolution Using Joint Training
Rate
[[|| Ý, [|]]
E|jly
11
Eijly 1
L2
E |||
4
0.0355
0.0227
0.0004
0.0586
0.0558
10
0.0223
0.0222
0.0008
0.0453
0.0435
20
0.0136
0.0191
0.00013
0.0349
0.0351
30
0.00122
0.0172
0.0015
0.0309
0.0308
Image Denoising Using Joint Training
Rate
E[| Y [1]
E|ll 12
Eijli; 12
L2
E[ Y
12
0.01911
0.00497
0.00020
0.02428
0.02302
30
0.01458
0.00435
0.00026
0.01919
0.01746
60
0.01168
0.00378
0.00032
0.01578
0.01401
90
0.01035
0.00323
0.00028
0.01386
0.01229
33

---

Published as a conference paper at ICLR 2022
Table 12: Model architectures of end-to-end network used in super-resolution.
Encoder
Decoder
Critic
Input
Input
Input
Conv2D, R-ReLU
Linear, BatchNorm ID, I-ReLU
Conv2D, I-ReLU
Conv2D, I-ReLU
Linear, BatchNorm I-ReL.U
Conv2D, I-ReLU
Flatten
Unflatten
Conv2D, I-ReLU
Linear, I-ReLU
ConvT2D, BatchNorm22, I-ReLU
Linear
Linear, I-ReLUU
ConvT2DD, BatchNorm2D,, I-ReLU
Linear, Tanh
ConvT2D, BatchNorm22, Sigmoid
Quantizer
Table 13: Model architectures of two-branch network used in super-resolution.
Encoder
Decoderl and 2
Input
Input
Conv2D, I-ReLU
Linear, BatchNorm ID. I-ReLU
Conv2D, R-ReLU
Linear, BatchNorm I-ReLU
Flatten
Unflatten
Linear, I-ReLU
ConvT2D, BatchNorm211, I-ReLU
Linear, I-ReLU
ConvT2D, BatchNorm22,, I-ReLU
Linear, Tanh
ConyT2D, Sigmoid
Quantizer
Table 14: Model architectures of end-to-end network used in image denoising.
Encoder
Decoder
Critic
Input
Input
Input
Conv2D, R-ReLU
Linear, BatchNorm I-ReI.U
Conv2D, I-ReLU
Conv21), [-RLLU
Linear, BatchNorm I-ReL.U
Conv2l), RelLLU
Conv2D, 1-ReLU
Unilatten
Conv2D, I-ReLU
Flatten
ConyT2D, BatchNorm22, I-ReLU
Linear
Linear, Tanh
Conv I2D, BatchNorm2D, I-ReLU
Quantizer
ConvT2D, BatchNorm22, 1-ReLU
ConvT2D, BatchNorm21), Sigmoid
Table 15: Model architectures of two-branch network used in image denoising. ResBlock is formed using two Conv2D and skip connection.
Encoder
Decoder1 and 2
Input
Input
Conv2D, R-RLLU
Linear, BatchNorm ID. 1-ReLU
Conv2D, 1-ReLU
Linear, BatchNorm ID, I-ReLU
Conv2D, I-ReLU
Unflatten
Flatten
ConvT2D, I-ReLU
Linear, Tanh
ResBlock, ConvT2D: I-ReLU
Quantizer
ResBlock, ConvT2D, I-ReLUU
ResBlock, ConvT2D, Sigmoid
34


Reviews:
[{"review_id": "yg35HJ0gy_s", "reviewer": "Reviewer_GKce", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors consider a scenario where an encoder observes some signal X and transmits it to a decoder as a quantized version ^X. At the decoder, this signal is transported into another signal called ^Y, from which the reconstruction Y is computed. The key point is that X and Y are not distributed wrt the same distributions: basically, X~Px is a degraded version of Y~Py. \n\nIn this setup, the very nice contribution of the paper is to express the whole problem as a particular instance of optimal transport, that indeed appears as the right framework to modify X~Py so that it becomes representative of Py. With this in mind, the \"compression\" part comes into the picture as the introduction of a latent variable ^X with limited entropy.\n\nHaving some personal background in source coding, I personally found the whole story very appealing and the derivations look very well grounded. Although of course the introduction of optimal transport in the picture reads exotic to my eyes, it sounds perfectly natural and everything is provided to allow the reader to understand (at least almost).\n\nThe experiment look rather weak in my opinion, and I would definitely have liked a much stronger support for the theory, possibly showing me the applicability of the method on real-life problems/scales. Still, the few experiments that are provided are ok and look promising already.\n\nBefore providing my detailed feedback, I must hence say that I recommend acceptance of this paper.\n\nNow, I have a few questions/remarks that I will list here in no particular order:\n* \"restoration at once using\" simultaneously\n* \"lower than the case when\" lower than when\n* what is it exactly you are calling \"geometrically representative of X and Y\" ? This doesn't make sense to me\n* are you sure you want to refer to (2) when you write \"The entropy constraint H(^X)<=R in (2) essentially guarantees that\"\n* When you write \"Finally, it is worth noting that under mild regularity conditions, the optimal converter can be realized as a (deterministic) bijection)\", it looks to me you are having the scalar case in mind, which indeed looks easy as an increasing rearrangement. However, how would you proceed when your code ^X is multidimensional ? My understanding is that optimal transport in this case is not trivial at all. I see two main ways to circumvent the problem: 1. Applying transport independently in each dimension after assuming they are independent (are they?) 2. Assuming the dictionary for ^X is finite so that some histogram transporting method like sinkhorn etc could be used. Could you please be clearer on these points, or tell me if I'm mistaken somewhere ?\n* I understand that it makes sense to assume that U and X are independent. However, I would be curious at what happens when they are not. It turns out I worked in such cases of \"informed coding\" where both coder and decoder were sharing information that is dependent on the signal to convey, and I kind of feel that the framework you propose could be compatible with this kind of ideas still. (Think for instance of the case where you want to transmit ^X, but where both the encoder and the decoder know some additional statistics that depend on X). \nIs independence mandatory ?\n* what do you mean exactly by \"settiong U to be a constant\" ? you wean that Pu is a dirac centered on some unique value ? I am asking because that sentence had me confused: do we agree that even if we assume it is random, we do assume that U is available at both coder and decoder (in the shared noise setting) ?\n*  When you assume that H(Y|U,X)=0, are you basically assuming that if you have U and X, then you would perfectly know Y ? What is the meaning of this assumption ?\n* \"compress it lossless\" losslessly\n* I am sorry to say that section 2.2 is really not \"reader friendly\" enough for me and that I couldn't follow that one. I would really recommend putting some technical content to the appendix and rather spend space explaining what happens. \n* It looks like you wanted to write (c) and not two times (b) in the caption of figure 3, right ?\n* After theorem 3, you mention you need Y|U to be discrete. Is there no way to relax this to delve into the domains of differential entropy ? I would be curious about what you think would be the next steps in a direction that would relax this discretization assumption\n\n* importantly, I can see that \"in practice, we do not impose a hard equality constraint\" on entropy. So actually, it looks to me that you are *not* implementing your \"entropy constrained\" OT, but rather some entropy-penalty. Although I understand it goes it the same direction, all your previous derivations seem to be violated by these practical choices. I guess it would be very important to at least hint at how this particular choice is under-optimal in the rate-distortion setups you developed ? I guess that this fact makes previous work about Sinkhorn distances more related to your work than explained in the paper, right ?\n\n* could you please detail how h is trained exactly ? through adversarial training ? with a WGAN setup ?\n\n* So, after all these developments, it looks like it is almost optimal already to just train separate encoders and decoders rather than a joint optimization ? Do you see scenarios where the derived theory would prove essential ?", "summary_of_the_paper": "The paper focuses on a very particular kind of lossy compression, which they call \"cross-domain lossy compression\". It basically amounts to encode a degraded version of the signal at the encoder while being able to reconstruct some better version at the decoder, while maintaining interesting rate constraints. As such, this scenario puts together signal compression and denoising/super-resolution, so that I can definitely say it comes with interesting applications.\n\nTechnically, the authors show that the problem can be nicely formulated as a special kind of optimal transport under entropy constraints, which gives an interesting flavour to their contribution and much theoretical grounding for their proposed method.", "summary_of_the_review": "original scenario for source coding that may be of interest to some specific applications. The connection with optimal transport is definitely interesting. There is much to do regarding validating the proposed approach in real large scale applications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ubdRbi3iwUF", "reviewer": "Reviewer_YvyS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(+) pros / (-) cons\n-------------------\n(+) well written and developed paper \n\n(+) topic interesting and important, addressed innovatively\n\nFurther questions for clarification/discussion\n-----------------------------------------------\nBinary example is hepful but the use case is for more complex (continuous) X and Y distributions. Would it be possible to find an illustrative example in the continuous space?\n\nMinor text problems / typos\n---------------------------\nPage 1, 7 lines from bottom: application -> applications\n\nPage 6, 2 lines from bottom: Q -> Q is a quantizer", "summary_of_the_paper": "The paper explores the problem of learned compression scheme for the specific setup where the source and target distributions are not the same (such as in restoring a degraded image). The authors formulate the problem as an optimal transport problem with entropy constraints to control the compression rate. They further argue that the use of common randomness in the encoder and decoder improves the rate-distortion tradeoff and dcoument it on denoising and super-resolution experiments.", "summary_of_the_review": "I find the paper contributes innovatively to the field nds is worth the attention of the community. Hence I recommnend it for acceptance for the conference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p0f79uRLbwt", "reviewer": "Reviewer_LfvG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: Extend the conventional concept of the optimal transport to handle perception (constraint on the output probability distribution).\n\nWeakness:\n(1) Relevance of the studied quantities to practical data compression is unclear.\n(2) Theorems 1 and 3 seem logically inconsistent with each other.\n\nDetail of (1): in the footnote of page 3 says that any DISCRETE RV Z can be losslessly compressed to at most H(Z)+1 bits. The point\nis Z being DISCRETE. with finite-support. In order for Definitions 2 and 3 to have practical significance, the RVs to be compressed must\nbe discrete and finite-support, in particular, Z in Definitions 2 and 3 must be finite-support.\nThe problem formulations do not seem relevant for practical data compression,\n\nDetail of (2): In the problem formulation (Definition 3) and its solution (Theorem 3), there is no condition on the common randomness U.\nTaking H(U)=0, i.e., U=0 always should reduce Definition 3 to Definition 2 and Theorem 3 to Theorem 2, but it does not.\nThere seems to be some unstated minimally required entropy on U, i.e., H(U) must be larger than some unstated constant number.\nFor example, page 5 states \"This is in contrast to the case without common randomness in Theorem 1 where the reconstruction Y\nmust be generated at the decoder.\" Is this true even with U of H(U) = 1 / 1,000,000,000??", "summary_of_the_paper": "* Characterize the optimal transport under the distortion and the output probability distribution constraints.\n* Provide DNN methods to evaluate the above quantities.", "summary_of_the_review": "The relevance of the paper to practical data compression is unclear, and it seems that mathematical quantities without practical relevance\nare considered. The stated theorems look false.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "k__9SVcBYGM", "reviewer": "Reviewer_SKN1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theorems shown in this work look interesting. For example, Theorem 1 indicates that, without common randomness, the optimal solution can be decomposed with compression (quantization and dequantization) and transport. Authors also demonstrate that common randomness is helpful at reducing the rate for a given distortion. Experimental results can corroborate the theorems. \n\nI am just a bit confused by the term \"cross domain\". I was thought it means different data sources with distinct spatial structure and appearance. But it seems authors refer to distributional shift due to noise and blurring. \n\nMy only suggestion is that, it seems Wang et al. (2021b) also model the shift in distribution due to degradation as an optimal transport problem. It would be much better if authors can specify more differences with respect to this work.\n\nPossible typos:\nPage 6, second last line, \"f be an encoder, Q, and g be a decoder\", do you want to mention \"Q be a quantizer\"? ", "summary_of_the_paper": "This work considers compression and restoration of degraded input in a joint framework, and formulated this problem as an oprimal transport with a constraint on the rate. Authors systematically analyzed the scenarios with and without common randomness at the encoder and decoder, and provide a few new insights both theoretically and empirically. ", "summary_of_the_review": "The theorems mentioend in this work is insightful. Authors also discussed how to implement compression and restoration jointly by a deep neural network.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KlaB62Sry0", "reviewer": "Reviewer_mTA9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I don't see any issues with the Theorems 1-3, but I did not work through the derivation provided in the appendix. The motivation also makes sense to me since there may be benefits to treating restoration (denoising, deblurring, super-resolution, etc.) and compression jointly. In some sense this seems like the typical case, rather than a rare one, since many sensors will include some kind of signal degradation and only store / transmit a compressed representation of the captured data (e.g. the camera in a mobile phone). That said, it shouldn't be to difficult to get paired data from such a device meaning that a supervised approach can be used.\n\nSome additional information on how shared randomness works would be helpful, though presumably this is covered in the references. I assume the sender and receiver agree on a pseudo-random number generator ahead of time and some kind of seed is transmitted, after which both sides can generate the same U.\n\nIt was not clear from the paper how the results compare to a baseline method that does *not* model restoration and compression jointly. I think this would look something like: learn to upscale low-res mnist images without a rate constraint (in an unsupervised fashion), and then separately learn to compress the high-res reconstructions.", "summary_of_the_paper": "This paper addresses the problem of lossy compression when the source and target distributions differ. As example domains, the authors look at denoising (the distribution of noisy images and \"clean\" images are not the same) and super-resolution (again, the distribution of low-res and high-res images are different) both addressed as unsupervised learning problems, i.e. the noisy/clean and low/high-res training data are unpaired.\n\nThe problem is treated as optimal transport (to account for the domain shift) with an entropy bottleneck (to account for the rate constraint needed to achieve compression). The authors derive theoretical bounds for the achievable distortion in two scenarios (with and without a source of shared randomness between the sender and the receiver), and they show that a shared source of randomness strictly improves rate-distortion performance. The Wasserstein distance used in a Wasserstein GAN framework accounts for the distribution difference between the input and output domains.\n\n", "summary_of_the_review": "The paper addresses a difficult and interesting problem, and I see no problems with the math. It's not clear to me how impactful these results are, however, which leads to my positive but low-confidence score.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper discusses the problem of cross-domain lossy compression on the basis of its reformulation as an entropy-constrained optimal transport. Two average distortion measures (without and with common randomness) are defined (Definitions 2 and 3), and some of their properties are investigated, as summarized in Theorems 1-3. The authors also demonstrated in Section 2.2 that in the Bernoulli-Hamming case the common randomness can indeed improve the performance under some conditions. Results of the numerical experiments on super-resolution and denoising are presented to illustrate the principles derived from the theoretical considerations.

This paper received 5 reviews, with score/confidence being 8/3, 6/3, 6/2, 8/3, 3/4, which exhibit a relatively large spread across the borderline. Upon reading the reviews and the author responses, as well as the paper itself, I think that this paper proposes an interesting framework of optimal transport with entropy bottleneck, as well as architectural designs supported by the theoretical development, with potential image-processing applications. The authors have provided further numerical results in their response.

My main concern is that the arguments in this paper are somehow confusing in that they borrow several notions and terms from the context of lossy compression and rate-distortion theory in the field of information theory, and use them in quite different meanings without explicitly stating so. (It seems to me that this would have been one major reason for the negative evaluation by Reviewer LfvG.) Examples are:
1. **Target distribution:** In rate-distortion theory the target distribution $p_Y$ is not fixed, whereas it is fixed in this paper.
2. **Rate constraint:** In rate-distortion theory the rate constraint is imposed in terms of the mutual information $I(X;Y)$ between the source $X$ and the target $Y$, in a form $I(X;Y)\le R$. The justification of this particular form of the rate constraint rather than any other forms is that it is compatible with the operational achievability/converse arguments via explicit construction of encoder/decoder pairs. In this paper, on the other hand, the authors consider a Markov chain $X\to Z\to Y$ and impose the rate constraint on the entropy $H(Z)$ of the intermediate random variable $Z$. Under the Markov assumption one has $I(X;Y)\le H(Z)$, so that the rate constraint in this paper is stronger than that in rate-distortion theory, and one would have no control over how tight/loose the adopted constraint $H(Z)\le R$ is against $I(X;Y)\le R$. In relation to this, the expression "identify the tradeoff between the compression rate and minimum achievable distortion" (page 2, line 12) would be at best misleading, as the arguments in this paper might be suboptimal, not necessarily providing the theoretically best achievable results.
3. **Extension versus single-shot:** In rate-distortion theory one usually considers $n$th extension of a source and a block encoder/decoder pair with blocklength $n$. On the other hand, this paper considers what is called the "single-shot" setting, in which one does not consider extension of sources. There are some pieces of work on lossy compression in the single-shot setting [C1][C2], so that I would be interested in how such pieces of work and the development in this paper will be related, an issue not explored at all in this paper.

As a result, although the quantities $D_{\mathrm{ncr}}$ and $D_{\mathrm{cr}}$ defined in Definitions 2 and 3 would look quite like the distortion-rate functions in rate-distortion theory, they are actually not the distortion-rate functions at all. Although the authors, perhaps carefully, did not call them distortion-rate functions, there should still be some explicit explanation on the difference of their framework from the standard one in information theory.

[C1] Nir Elkayam and Meir Feder, "One shot approach to lossy source coding under average distortion constraints," IEEE International Symposium on Information Theory, 2389-2393, 2020. [link](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9173943)

[C2] ibid., "One shot approach to lossy source coding under average distortion constraints," [Online]. Available: https://arxiv.org/abs/2001.03983

Another concern of mine, from the viewpoint of the theory of optimal transport, is regarding the optimal transport map. It is known that under fairly general conditions the optimal transport *plan* exists. However the optimal transport *map* is not guaranteed to exist, and even if it exists it can be highly irregular. (See, e.g., Villani, 2009) The descriptions in this paper, such as "computing the optimal transport map is not straightforward" and "learn approximately optimal mappings" on page 4 would be too naive in that they would assume existence and approximability of the optimal mapping.

Despite these concerns, most reviewers agree that this paper presents an interesting piece of work. I would therefore like to recommend acceptance of this paper, and would appreciate it if the authors consider addressing appropriately the above concerns of mine in the final version.
Decision: Accept (Poster)