The Rate-Distortion-Perception Trade-Off with Algorithmic Realism

Response to the “Weaknesses” section of the review:

1. We consider that the theoretical results in the paper, regarding the role of common randomness, are supported by the existing literature on practical generative compression algorithms. Indeed, there exist compression schemes (Agustsson et al.; He et al., 2022; Hoogeboom et al., 2023; Ghouse et al., 2023; Mentzer et al., 2020; Yang & Mandt, 2023), considered as state-of-the-art in terms of the trade-off between rate, distortion, and realism, that do not involve any common randomness.

2. The following is a possible avenue for future research. Our work theoretically shows that the number of samples inspected by a critic greatly influences the trade-off between rate, distortion, and realism. This constitutes a new perspective on the latter. Therefore, our work may inspire investigations of metrics used to quantify realism, where particular attention would be given to the choice of the batch size. This could lead to highlighting specific strengths and weaknesses of existing realism metrics. It may also inspire a critical assessment of the relative performance of existing compression schemes, depending on the choice of realism metric.

Response to the “Questions” section of the review:

1. As the reviewer pointed out, our formulation involves a very strong critic, stronger than can be implemented in practice. This is needed to conclusively show that randomness is not needed to fool critics, which is our main result. Therefore, albeit being tailored to this goal, it is not directly tailored for practical implementation purposes. After careful consideration, we have reached the conclusion that the core concept of our paper, namely the optimality of deterministic codes, cannot be illustrated by examples. Indeed, we are not aware of any experimental method allowing to ascertain the optimality of a given compression algorithm (at a given target rate) for non-trivial choices of source and distortion measure. Moreover, our characterization of this new trade-off in the asymptotic setting applies to a Bernoulli source. However, we are not able to derive further results for such a source, since characterizing the trade-off in a non-asymptotic setting is a challenging problem.

2. We thank the reviewer for this suggestion. However, the question of whether randomization has an adverse effect in terms of rate, or distortion, or universal critic scores, remains an open problem. In this paper, we have only shown that there exist optimal deterministic schemes.

Our work theoretically shows that the number of samples inspected by a critic greatly influences the trade-off between rate, distortion, and realism. This constitutes a new perspective on the latter. Therefore, our work may inspire investigations of metrics used to quantify realism, where particular attention would be given to the choice of the batch size. This could lead to highlighting specific strengths and weaknesses of existing realism metrics. It may also inspire a critical assessment of the relative performance of existing compression schemes, depending on the choice of realism metric.

For the sake of clarity, and since we have identified links between the reviewer’s questions, we will answer the latter in a different order.

Response to questions 2, 3 and 4: These questions pertain to the impact, on visual/perceptual quality and compression rate, of designing compression schemes which do not involve common randomness. We have proved theoretically that such schemes can achieve the optimal trade-off between realism, rate, and distortion. This is supported by the vast literature on practical generative compression algorithms. Indeed, there exist compression schemes (Agustsson et al.; He et al., 2022; Hoogeboom et al., 2023; Ghouse et al., 2023; Mentzer et al., 2020; Yang & Mandt, 2023), considered as state-of-the-art in terms of the trade-off between rate, distortion, and realism, that do not involve any common randomness.

Response to question 1: Our claim is that deterministic schemes can achieve the optimal trade-off between rate, distortion, and realism. To conclusively show that randomness is not needed to fool a critic, it was necessary to consider the strongest critic possible, stronger than can be implemented in practice. Therefore, this framework, albeit being tailored to our theoretical proof, is not directly tailored for integration into a practical compression scheme. The design of practical perceptual quality critics, with adequate batch sizes, is thus out of the scope of this paper, but constitutes an interesting avenue for future work.

Response to the “Weaknesses” section of the review:

Following the reviewer’s advice, we provide more explanatory discussions regarding our proposed formulation, in comparison with the original RDP framework. The main difference with the latter pertains to the realism constraint. In the original formulation of Blau & Michaeli, the realism constraint is $\mathcal{D}(p_X, p_Y) \leq \lambda,$ where $\mathcal{D}$ is some divergence, $p_X$ is the source distribution, and $p_Y$ is the reconstruction distribution. In Definition 3.3, which introduces our proposed framework, we formulate a realism constraint involving a batch of $B$ reconstructions $Y^{(1)}, …, Y^{(B)},$ and a (lower semi-)computable critic $\delta$ inspecting said batch: $E[\delta(Y^{(1)}, …, Y^{(B)})] \leq C.$ Intuitively, the original realism constraint corresponds to the case where the batch size is infinite, since the discrete distributions $p_X$ and $p_Y$ can be approximated arbitrarily well using a large enough number of samples. In that sense, our proposed RDP framework generalizes the original one, through involving elements of practical realism metrics, such as the number $B$ of samples which are inspected, and a scoring function $\delta$ which is required to be approximable via an algorithm. Our results (Theorems 4.1 and 4.4) show that the choice of $B$ greatly impacts the RDP trade-off, especially the role of randomness, thereby questioning the original RDP framework.

The reviewer also advised to provide illustrative examples. After careful consideration, we have reached the conclusion that the core concept of our paper, namely the optimality of deterministic codes, cannot be illustrated by examples. Indeed, we are not aware of any experimental method allowing to ascertain the optimality of a given compression algorithm (at a given target rate) for non-trivial choices of source, critic, and distortion measure. Only a theoretical proof can show the optimality of deterministic schemes. Moreover, to conclusively show that randomness is not necessary to fool critics, one must consider the most powerful critic possible, which cannot be practically implemented.

Response to the “Questions” section of the review:

1. Our results show the existence of optimal schemes which do not involve any randomness at test time, but there may exist other optimal schemes, which rely on randomness at test time, as well as learned schemes relying on randomness at training time. We are not aware of any evidence that randomization in compression or decompression is necessary for optimal stability or robustness, but it is possible that such evidence will be found in the future.

2. Quantifying the dependence of the RDP trade-off on the batch size used by the critic is a difficult problem. While we have obtained results on the role of randomization, we do not yet have results which could guide the choice of the batch size for designing generative compression schemes.