Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to use ML to establish lower and upper bounds on rate distortion for general sources, thus going beyond the Blahut-Arimoto algorithm (which assumes discrete sources with known PMF, and has complexity exponential in the dimension of the data). Some theoretical results are provided, extending prior results. Some numerical results are provided 
main_review: The paper proposes to use ML to establish lower and upper bounds on rate distortion for general sources, thus going beyond the Blahut-Arimoto algorithm (which assumes discrete sources with known PMF, and has complexity exponential in the dimension of the data). Some theoretical results are provided, extending prior results. Some numerical results are provided.

To construct the upper bound, the paper starts with the unconstrained variational objective of Blahut-Arimoto.  The distributions Q(\hat{x} | x) and Q(\hat{x}) are parametrized by the parameters of a NN; minimizing the objective function provides a point on the upper bound of the R(D) curve. A key insight is the observation that this objective function is similar to NELBO in \beta-VAE.  Based on this a projection to a lower-dimensional space is considered. The paper establishes R_\omega(D) \ge R(D), where \omega is the decoder function. While this seems straightforward, there is no discussion of the complexity in finding each R(D) point, and of course the required sweep over \lambda to find the entire UB curve. There is little discussion on the choice of \omega; in particular what choices are likely to lead to tighter bounds. 
The establishment of the lower bound is less clear. The paper notes that this much harder than the UB case. Again there is little detail on the architecture for computing u_\theta(x). At the end of section 4, we are told that Appendix A has the detailed algorithm, but Appendix A says that an outline will be provided

Numerical section: insufficient details are provided so that it would not be possible for an informed reader to reproduce the results in the paper. . While some detail is provided for the Gaussian sources (results shown in Fig 2), very little detail is provided for the banana sources (Fig 3) or the natural images (Fig 4). 

Section A.5.3 “Natural Images” is a blank section 

Other: 

What does “1 PSNR” (used in the abstract and several other places mean)? Does this mean 1 dB improvement in PSNR? 

I assume a diagonal Gaussian process is a vector Gaussian process in which the components are independent so that the covariance matrix is diagonal? 


summary_of_the_review: The use of ML to address complex problems in information theory is appealing. The authors consider the problem of obtaining upper and lower bounds for the rate distortion curve for source distributions that may be continuous, discrete, or mixed, and may not be known (only data are available). Some theoretical results are provided. Two major issues: insufficient details about the learning architectures are provided, so that an informed reader will not be able to reproduce the results in the paper. Second, there is very little discussion of the complexity of the algorithm.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper aims to provide stronger upper and lower bounds for the RD function of arbitrary sources. The authors handle unknown sources by requiring only i.i.d. samples. Specifically, the authors derive an upper bound to the RD function using a $\beta$-VAE-like generative model, which has some similarities to the Blahut-Arimoto (BA) algorithm with two distinctions: 1) they do not restrict the source to be a low-dimensional discrete data, and 2) they use gradient descent to predict the parameters of the variational distributions $Q_{\hat{X}|X}$ and $Q_{\hat{X}}$. They also derive a lower bound to the RD function using the dual form of the RD function. Finally, the authors provide experimental results to show that the proposed upper bound is, in fact, exact for random Gaussian samples. For more complex data such as banana-shaped sources and their high-dimensional projections, they show that the proposed upper and lower bounds are tight. Furthermore, the proposed upper bounds on the RD function of natural images indicate that the state-of-the-art image compression methods can still be improved by at least one dB PSNR.
main_review: The paper is well-motivated and has valuable results for the lossy compression community. In more detail:

$\textbf{Strenghts:}$ 
- The paper is well-written and summarizes the prior work well for readers from both information theory and generative models backgrounds. 

- The authors provide a tight upper bound on the RD function of arbitrary sources without limiting the sources to discrete data or restricting the dimensions. I believe this is a useful contribution to the lossy compression field. For instance, as the authors pointed out in the paper, we can assess the success of lossy compression algorithms by comparing their performance with tight RD bounds.

-  The authors use the dual formulation of the RD function to find a lower bound, which, to the best of my knowledge, is a novel approach.

- The experimental results on random Gaussian samples show the exactness of their upper bound (for this particular source). For the banana-shaped source and its high-dimensional projection, the authors show that upper and lower bounds are tighter than what was proposed in prior work. These two sets of experiments provide empirical support for the theoretical results in the paper. 

- I find the experimental results on natural images interesting as the authors essentially set a (somewhat loose) limit for future work in lossy image compression without actually providing a compression algorithm. 

$\textbf{Weaknesses:}$ 
- Despite the flexibility of the proposed method for finding upper bounds on RD function, the authors restrict the source to have low effective dimension with continuous reproduction alphabet. This makes the current lower bound not applicable to high-dimensional data such as images.

- The lower bound is evaluated only on a banana-shaped source. It would be nice to see the tightness of the upper and lower bounds on a few other sources. 

- I could not access the code in the given link. The google drive folder seems empty.  

- A few minor points:
    - Section 4, Dual Characterization of R(D) paragraph, "..., a variational lower would require..." misses the word "bound"
    - Section 6.1, last sentence of the second paragraph: optional - - > optimal
    - There are a few problems with the Appendix. The text for the last section A.5.3 Natural Images seems missing. The figure number in the last paragraph is also missing.   
summary_of_the_review: Although the proposed method has limitations, I find some of the contributions valuable.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of estimating the rate-distortion function R(D) for arbitrary sources with unknown distribution. An upper bound is established using a variational distribution and is estimated using an iterative coordinate descent algorithm inspired by the Blahut-Arimoto algorithm. A lower bound is established using a parameterization of the dual form of the rate-distortion function by Cisszar. These are then evaluated using neural network encoder/decoders on Gaussian and Banana sources, and tested on natural images suggesting that there is room for improved compression rates achieved by current state-of-the-art image compression algorithms.


main_review: Novelty: The classical Blahut-Arimoto algorithm requires the restrictive assumption of a discrete source as well as a known source distribution. This paper aims to develop a technique for unknown sources with possible continuous support. While there has been some work on extending this in the past (Riegler et al, 2018; Harrison & Kontoyiannis, 2008; Gibson, 2017), none have tackled the problem to the breadth of this paper. The paper is well written and easy to follow.

Significance: On the technical side the main contribution of the paper is on computing lower bound for rate-distortion function, as the upper bound is a rather natural application of the ELBO analysis in VAEs. While the experiments on the Gaussian and Banana sources give credence to the tightness of the bounds, these are rather simple examples. In particular, the variational distribution used for the experiments is Gaussian and contains the source distribution in its family. Although the banana source is a nonlinear transform of a Gaussian source, by visual inspection the underlying inverse transform seems to be easily learnable by an encoder in principle.  Do the authors have examples of synthetic experiment in which the source distribution is significantly different from the variational/latent distributions (Q_{Z|X}, Q_Z) as well? 

The results on image compression suggesting a possible 1 PSNR improvement seem to be significant. 
As the authors have mentioned, it is unclear whether we can actually close this gap due to the nature of it being an overestimate. Furthermore, the lower bound computation, which seem to be the main technical innovation does not scale to such datasets. As a result the reviewer feels that the technical contribution of the paper in realistic image compression applications may be limited due to these reasons. 


summary_of_the_review: Due to the weaknesses in the "significance" part of the main review I am marking the score as a 5.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper claims to propose "upper bound" and "lower bound" on the R-D function in lossy data compression.
main_review: I cannot find any strength. I will outline major weakness, not covering all the waeknesses (as all pages are weak).

(1) The paper claims to propose upper and lower bounds on the R-D function of unknown memoryless information source. There are always nonzero probability of the "upper bound" being lower than the true R-D function, because the data samples are probabilistic. The standard tool for handling such a situation is one-sided confidence interval (see any undergraduate textbook on frequentiest statistics).
There is no reason for not using the standard statistical framework.
If one wants to use the Baysian counterpart of the interval estimation, one must have a prior probability of the unknown memoryless information source, but such a prior probability is not provided in the manuscript.

(2) The paper gives the big claim in the first page that "bounding the R-D function of a general (i.e. discrete, absolutely continuous or neither), unknown memoryless source". There are several subtleties, for example: The expectations of random variables do not
always exist, for example the Cauchy distribution. What is the definition of the R-D function for such probability distributions?
The expectation is used in almost every displayed equations of the manuscript. What if the expectation is undefined, like the case of the
Cauchy distribution? If the authors assume the existence of expectation in every mathematical expression of the manuscript,
what kind of the memoryless information source can be handled by the proposal? It is clear that the discrete and Gaussian sources
are OK, but they can be handled by the Arimoto-Bluhat algorithm in 1970s, after estimating the probability distribution by standard
statistical methods.

(3-1) The manuscript uses mathematical theorems that have not been proved for "general" memoryless information source.
For example, Lemma A.1 cites Csiszar and Gray, which proved Lemma A.1 for discrete and Gaussian sources.
The manuscript must prove Lemma A.1 for the class of information source that are considered.

(3-2) Similar for Theorem A.2. Please provide a proof of Theorem A.2 for the "general" information source.

(4) With any conficence interval estimation algorithm, there always exists a positive probability of the event that the true parameter does not belong
to the confidence interval generated by the algorithm with data samples obtained. The confidence level is one minus such a "failure"
probability. Thus, every practical interval estimation algorithm accompanies with (desirably theoretical) derivation of the confidence level.
The manuscript does provide confidence levels that can handle "general" memoryless information source.
It is acceptable that confidence levels of the proposed "upper" and "lower" bounds are also algorithmically produced given
data samples.

(5) Confidence levels should be evaluated with the finite number n of data samples, otherwise one cannot know what is the probabilities
of the proposed "lower" and "upper" bounds fail in a practical situation.

(6) If the authors want to retain their claim that their proposed algorithm can handle any probability distribution, please provide
the results of running their proposed lower and upper bounds algorithms on the Cauchy distribution as defined at 
https://en.wikipedia.org/wiki/Cauchy_distribution

(7) Related to (6), it is unclear what kind of random variables/probability distributions can be handled by the proposed algorithms.
It must be clearly stated. Experiments are only conducted for the Gaussian distribution and so-called the "banana" source.
Are the proposed algorithms can be applied to other classes of probability distributions? If the authors claim wider applicability
of their proposed algorithm, it must be supported by experimental or theoretical evidences. If the proposals are only applicable
to a limited class of distributions, it is unsuitable for ICLR.
summary_of_the_review: Mathematical reasoning in the paper is doubtful, and what kind of situations can be handled by the proposed
algorithm is unclear, see "main review" for the detail.
review_title: null

Meta-review: This paper proposes an algorithmic approach to estimating upper and lower bounds of the rate-distortion (R-D) function of a data source on the basis of samples drawn from it. The proposed upper bound is based on the variational objective employed in the Blahut-Arimoto algorithm, whereas the proposed lower bound is based on the dual characterization of the R-D function. In both bounds neural networks trained with samples are utilized. Experimental results on four sources (Gaussian, banana-shaped, GAN-generated images, and natural images) are provided.

The four review scores were initially two positives and two negatives. Some reviewers evaluated positively the argument on the lower bound of the R-D function. On the other hand, one reviewer showed his/her concern about lack of the argument on statistical confidence of the obtained bounds. In response, the authors have addressed it in Section A.6 in the Supplementary Materials (SM) of the revised manuscript with the experiment using GAN-generated images (high-dimensional data with low intrinsic dimension), and the results are summarized in Tables 1-4 and Figure 10 in SM. The authors have in their revision also provided a specification for the range of the sources to which the proposal would be applicable. Description of the experiments on images, which was missing in the initial version as pointed out by some reviewers, has been added in the revised manuscript. Still, as some reviewers mentioned, the main weakness is that the proposal failed to demonstrate its usefulness to estimate the lower bound in settings where the data dimension is truly high, as in the experiment with natural images, where statistical confidence analysis was not conducted either. Three reviewers have revised their respective scores upward after the author response.

Despite some weaknesses I think that this paper provides a novel and interesting algorithmic approach to estimating the rate-distortion function. I would therefore like to recommend acceptance of this paper, and would like to encourage the authors to perform confidence analysis also for the experiments on natural images.
Decision: Accept (Poster)