Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: (+) pros / (-) cons
-------------------
(+) well written and developed paper 

(+) topic interesting and important, addressed innovatively

Further questions for clarification/discussion
-----------------------------------------------
Binary 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?

Minor text problems / typos
---------------------------
Page 1, 7 lines from bottom: application -> applications

Page 6, 2 lines from bottom: Q -> Q is a quantizer
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

I 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. 

My 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.

Possible typos:
Page 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_review: The theorems mentioend in this work is insightful. Authors also discussed how to implement compression and restoration jointly by a deep neural network.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.

The 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.


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.

Some 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.

It 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

Technically, 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.
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. 

In 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.

Having 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).

The 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.

Before providing my detailed feedback, I must hence say that I recommend acceptance of this paper.

Now, I have a few questions/remarks that I will list here in no particular order:
* "restoration at once using" simultaneously
* "lower than the case when" lower than when
* what is it exactly you are calling "geometrically representative of X and Y" ? This doesn't make sense to me
* are you sure you want to refer to (2) when you write "The entropy constraint H(^X)<=R in (2) essentially guarantees that"
* 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 ?
* 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). 
Is independence mandatory ?
* 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) ?
*  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 ?
* "compress it lossless" losslessly
* 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. 
* It looks like you wanted to write (c) and not two times (b) in the caption of figure 3, right ?
* 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

* 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 ?

* could you please detail how h is trained exactly ? through adversarial training ? with a WGAN setup ?

* 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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: * Characterize the optimal transport under the distortion and the output probability distribution constraints.
* Provide DNN methods to evaluate the above quantities.
main_review: Strength: Extend the conventional concept of the optimal transport to handle perception (constraint on the output probability distribution).

Weakness:
(1) Relevance of the studied quantities to practical data compression is unclear.
(2) Theorems 1 and 3 seem logically inconsistent with each other.

Detail 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
is Z being DISCRETE. with finite-support. In order for Definitions 2 and 3 to have practical significance, the RVs to be compressed must
be discrete and finite-support, in particular, Z in Definitions 2 and 3 must be finite-support.
The problem formulations do not seem relevant for practical data compression,

Detail of (2): In the problem formulation (Definition 3) and its solution (Theorem 3), there is no condition on the common randomness U.
Taking 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.
There seems to be some unstated minimally required entropy on U, i.e., H(U) must be larger than some unstated constant number.
For example, page 5 states "This is in contrast to the case without common randomness in Theorem 1 where the reconstruction Y
must be generated at the decoder." Is this true even with U of H(U) = 1 / 1,000,000,000??
summary_of_the_review: The relevance of the paper to practical data compression is unclear, and it seems that mathematical quantities without practical relevance
are considered. The stated theorems look false.
review_title: null

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)