Minimum Entropy Coupling with Bottleneck

Summary

The submission formulates and provides an approximate solution for the entropy-bounded information maximization problem. The submission extends Markov coding games to a rate limited setting and illustrates how its entropy-bounded information maximization approach can be to address such settings.

Strengths

There are a number of nice contributions in the submission. The submission formulates a very natural problem (entropy-bounded information maximization) and provides a solution with provable approximation guarantees. It further shows how entropy-bounded information maximization can be used to address an interesting extension of Markov coding games to rate limits.

Weaknesses

> One of the earliest greedy algorithms for MEC was introduced by [21] in the context of causal inference, achieving a local minimum with a gap of 1 + log n bits from the optimum, where n represents the size of the alphabet. The paper *Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier* (i.e., [6]) shows that [21]'s algorithm achieves within $log_2(e) \approx 1.44$ bits of optimal entropy for n variable coupling and $log_2(e)/e \approx 0.53$ bits of optimal entropy for 2 variable coupling, which are stronger guarantees than that stated above. --- As a general comment, using number citations as proper nouns is bad practice: "[30] explores a single-shot lossy source coding setting under logarithmic-loss, using a straightforward encoding scheme." This should instead be "Shkel and Verdú (2017) explore a single-shot lossy source coding setting under logarithmic-loss, using a straightforward encoding scheme." --- The submission's Theorem 1 evokes the paper *Bounds on the Entropy of a Function of a Random Variable and their Applications* to me. It would be worth discussing as related work. --- I was walking through Algorithm 1 and it seems not to handle the following edge case appropriately: Take the case where R = H(X). Then Algorithm 1 will return $p_{s}^{(1)}$ when we would prefer it to return $\text{diag}(p_X)$. --- Writing: Let pXT denoted by a |X | × |T | matrix, defines a deterministic mapping T = g(X), with I(X; T) = H(T) = Rg. --- > 1. I_EBIM(pX, Rg + ϵ) is attained by transferring an infinitesimal probability mass from the cell with the lowest value in a column, after normalizing each column by dividing by its sum, to a new column of pXT . Both this statement and the subsequent statement (2) should be stated more clearly. The way the statement currently reads, it's not clear why normalization changes anything (the cell with the lowest value in a column is invariant to column normalization). It would also be good to be more clear about the fact that the mass is being transferred to a column in the same row. --- > Marginal Policy Before execution, we first derive a marginal policy π for the MDP, based on the Maximum-Entropy reinforcement learning objective The submission should probably attribute this high level approach to [32]. The submission should probably also explain more generally how Algorithm 2, 3, 4 extend the approach of [32].

Questions

> It is straightforward to check that the optimal solution of (1) is achieved when T = Y, with the identity decoder. To address this issue of decoder collapse, we introduce a constraint on the output marginal distribution, P(Y ) Is decoder collapse actually an issue? If (1) is actually the problem of interest, what makes the identity decoder undesirable?

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

Have the authors adequately addressed the limitations Yes.

Summary

The paper develops a lossy compression framework that uses logarithmic loss (using conditional entropy or mutual information). This framework is designed to handle scenarios where the reconstruction distribution diverges from the source distribution, making it particularly relevant for applications requiring joint compression and retrieval under distributional shifts. The work introduces the Minimum Entropy Coupling with Bottleneck (MEC-B) framework, and considers two decomposition strategies based on fixing either the encoder (MEC) or the decoder (EBIM). Since the general solution to the problem is intractable, the authors propose a greedy algorithm for EBIM with guaranteed performance and a study of the performance near the optimal deterministic solutions. The theoretical work is followed by a demonstration of its applicability to a Markov game setting with communication bottleneck, demonstrating its practical applicability, and quantifying the tradeoff between reward and decoding accuracy.

Strengths

The general problem of lossy compression under logarithmic loss (MEC-B) is interesting, and worthy of study. Relating the quality measure of MEC-B to two related problems, MEC and EBIM, in Lemma 1, is interesting, even if not very surprising. For the EBIM problem it is shown that the optimal encoder is deterministic, an interesting result in itself. The greedy algorithm suggested is novel to the best of my knowledge, and proved to be optimal up to a constant related to the source distribution. These results, with the added characterization of Theorem 3 provide a good characterization of the problem and its space of solutions, especially in situations of distribution shift between input and output.

Weaknesses

The main weakness, as noted by the authors, is that the full MEC-B problem is left open, while special cases of it have been solved. The restriction to discrete alphabet settings is also a limitation of the approach. Extending to more general cases is expected to lead to very challenging analysis.

Questions

(1) To help the reader assess the quality of the gap in Theorem 2, please provide some orders of magnitude assessments for the mutual information relative to the gap in terms of the problems attributes (e.g., size of alphabet). (2) Section 4: The receiver receives a full trajectory of the MDP. This means that the algorithm is an offline MDP setting. Is this correct? (3) What are the computational costs of the algorithm proposed? (4) The notion of distributional shift is motivated in the Introductions, but received little discussion later on. Especially as Algorithm 1 is for the EBIM problem where the output distribution is only constrained in terms of entropy.

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

3

Limitations

The results are limited to discrete alphabets, and sub-problems of the full MEC-B problem. There is a recent line of work dealing with rate-perception-distortion setups (starting from the work of Blau and Michaeli titled “Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff”, ICML 2019, with many follow-ups). While they do not use logarithmic distortions, it would be interesting to discuss this line of work in a comparative setting, since many of the problems, and particularly the tradeoffs, are similar.

Summary

The authors introduce a novel lossy compression framework which introduces a bottleneck to the canonical minimum entropy coupling framework. The authors show that the encoder task can be solved approximately by a novel greedy algorithm with guaranteed performance, while the decoder problem reduced to a canonical minimum entropy coupling problem. The authors test their approach on a novel Markov Coding Game variant that admits rate limits and find that it outperforms a quantization baseline.

Strengths

The paper is well-structured, well-written, and defines a new - and potentially very powerful - framework. The authors' theoretical contributions are strong; particularly the novel greedy algorithm for solving the EBIM problem is impressive. The authors deliver a solid empirical evaluation of their proposed algorithm.

Weaknesses

A substantial weakness of the paper is its lack of evaluation on tasks with clear real-world applications. The authors allude to a number of possible real-world applications in the conclusion, but the MCG setting is fairly removed from real-world impact. ## Minor * in equation (1), R is not yet defined

Questions

* In terms of real-world impact, could the authors further elaborate how their EBIM algorithm would contribute to robust watermarking approaches?

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors discuss limitations adequately.

Response

Thanks for your response! It could be helpful to readers to give more concrete specifics about the necessity of the output distribution constraint in the text. --- Enjoyed the paper! Nice job.

Thanks for Your Response

I thank the authors for their response. While I agree that the authors discuss various real-world applications, I would not consider any of them as moderate or high impact. I struggle to see how MCGs would be useful in the real world, and using the authors' approach in watermarking would run into severe robustness issues. The most exciting avenue for real-world application seems to be that of lossy compression; however here the authors haven't supplied any convincing empirical evidence for any high impact settings (say e.g. image compression vs, JPEG). Given I am already advocating for acceptance, I will maintain my current score. For a higher score, the authors would need to demonstrate more tangible real-world impact.