Minimum Entropy Coupling with Bottleneck

Authors: m reza ebrahimi
jun  chen
ashish  khisti
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 22:25:00

Abstract: This paper investigates a novel lossy compression framework operating under logarithmic loss, designed to handle situations where the reconstruction distribution diverges from the source distribution. This framework is especially relevant for applications that require joint compression and retrieval, and in scenarios involving distributional shifts due to processing. We show that the proposed formulation extends the classical minimum entropy coupling framework by integrating a bottleneck, allowing for controlled variability in the degree of stochasticity in the coupling.
We explore the decomposition of the Minimum Entropy Coupling with Bottleneck (MEC-B) into two distinct optimization problems: Entropy-Bounded Information Maximization (EBIM) for the encoder, and Minimum Entropy Coupling (MEC) for the decoder. Through extensive analysis, we provide a greedy algorithm for EBIM with guaranteed performance, and characterize the optimal solution near functional mappings, yielding significant theoretical insights into the structural complexity of this problem.
Furthermore, we illustrated the practical application of MEC-B through experiments in Markov Coding Games (MCGs) under rate limits. These games simulate a communication scenario within a Markov Decision Process, where an agent must transmit a compressed message from a sender to a receiver through its actions. Our experiments highlighted the trade-offs between MDP rewards and receiver accuracy across various compression rates, showcasing the efficacy of our method compared to conventional compression baseline.

Main paper: 
 introduction: 
 Consider the following Markov Chain modeling a general lossy compression frameworkX p T |X ---→ T q Y |T---→ Y , where the input X with a marginal distribution p X , is encoded by the probabilistic encoder p to generate the code T . Subsequently, the probabilistic decoder q reconstructs Y from T . The objective is to identify the encoder and decoder that minimize the distortion between X and Y , subject to an upper bound constraint on the expected code length H(T ) ≤ R.It is common to measure the sample-wise distortion via direct comparison of (x, y) pairs through a distortion function d(•, •), and consider the expectation E [d(X, Y )] as a measure of average distortion. Instead, we propose using the logarithmic loss (log-loss) H(X|Y ), or equivalently I(X; Y ), as an alternative metric to enforce the distortion constraint. The log-loss distortion measure, commonly employed in learning theory, was first explored within rate-distortion theory by Courtade and Wesel [1] and Courtade and Weissman [2] . This measure is particularly suitable in scenarios where reconstructions can be soft, meaning that the decoder produces a distribution rather than a distorted sample point [3] . Consequently, the optimization problem is formulated as follows:EQUATIONIt 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 ):Minimum Entropy Coupling with Bottleneck (MEC-B)EQUATIONThe addition of an output distribution constraint is a practical necessity, as in a lossy compression setup the decoder needs to generate outputs following a desired distribution. For example, in image restoration, the output consists of reconstructed images from the code adhering to a certain distribution, possibly the same as the input distribution.We explore two special cases of (2) , where either the encoder or decoder is bypassed. This allows us to optimize the encoder and decoder separately using these cases. First, consider the case where the bottleneck is removed, meaning the constraint H(T ) ≤ R is relaxed, or R ≥ H(X). In this scenario, X = T , and the optimization simplifies to:Minimum Entropy Coupling (MEC)EQUATIONThis involves identifying the probabilistic mapping p Y |X between the marginals p X and p Y that maximizes the obtained mutual information. This problem, as described in (3) , has been extensively studied in the literature as minimum entropy coupling (MEC), with early research conducted by Vidyasagar [4] , Painsky et al. [5] , Kovačević et al. [6] , Cicalese et al. [7] , among others. Thus, we define the original problem presented in (2) as minimum entropy coupling with bottleneck (MEC-B).Next, consider the case where the decoder is removed, resulting from the relaxation of the output distribution constraint in (2):Entropy-Bounded Information Maximization (EBIM)EQUATIONSimilar to minimum entropy coupling, this problem identifies the joint distribution between two random variables that maximizes their mutual information. However, rather than imposing a marginal distribution constraint, it enforces a more flexible entropy constraint on one of the variables. Lemma 1 provides a decomposition for the mutual information between input and output I(X; Y ), given the Markov chain X ↔ T ↔ Y . The proof follows multiple applications of the chain rule for mutual information. The following lower bound on the MEC-B objective is attainable based on Lemma 1:EQUATIONIn this work, we consider maximizing the lower bound (6) as a proxy to the main objective. This allows a decomposition of the encoder and decoder for the MEC-B formulation in (2):1. Encoder Optimization: The encoder is first optimized separately, according to Entropy-Bounded Information Maximization in (4), I EBIM (p X , R), resulting in the marginal distribution pT on the code T . 2. Decoder Optimization: The decoder is then optimized by solving a minimum entropy coupling in (3) between the code and output marginals, I MEC (p T , p Y ).Therefore, in terms of problems (2) , (3) , and (4):EQUATION≥ maxEQUATION≥ I EBIM (p X , R)EQUATIONIn this paper, we address the Entropy-Bounded Information Maximization problem in Section 3, providing theoretical insights into the solution structure across the entire spectrum of rate limits. We establish an upper bound on the objective and demonstrate that only deterministic mappings can achieve this bound. Then, in Section 3.1, we introduce a greedy algorithm designed to identify deterministic mappings with a guaranteed input-dependent gap from the optimal solution. Subsequently, in Section 3.2, we describe a method to identify optimal mappings near any deterministic mapping, effectively bridging the gap between discrete deterministic mappings and providing deeper theoretical insights into the problem structure.Following this theoretical groundwork, Section 4 applies the MEC-B framework to extend Markov Coding Games (MCG) with communication bottlenecks between the source and the agent. Experimental results for MCGs with rate limits are detailed in Section 4.2, showcasing the practical implications of our theoretical developments. The appendix sections complement these discussions by including formal proofs for all theorems and lemmas, a concise overview of the original minimum entropy coupling problem, and additional experimental results. 
related work: 
 Couplings and Minimum Entropy Coupling A fundamental problem in probability theory, known as coupling, concerns determining the optimal joint distribution of random variables given their marginal distributions. This problem has a long history, with early examples by Fréchet [8] seeking the joint distribution that maximizes correlation subject to marginal constraints. References [9] [10] [11] [12] provide a broader treatment of these problem classes and their applications. Notably, optimal transport (OT) emerges as a significant class within this framework, where optimality is defined as minimizing the expected value of a loss function over the joint distribution. See [13] for an in-depth treatment of the optimal transport problem.The minimum entropy coupling (MEC) focuses on finding the joint distribution with the smallest entropy given the marginal distribution of some random variables. This problem has been first studied in [4] [5] [6] [7] , among others. While it is shown by Vidyasagar [4] , Kovačević et al. [6] that MEC is NP-Hard, the literature contains many approximation algorithms for this problem. One of the earliest greedy algorithms for MEC was introduced by Kocaoglu et al. [14] 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. This bound was further improved in subsequent works [15, 16] .Based on tools from the theory of majorization [17] , Cicalese et al. [18] developed a new greedy algorithm producing solutions 1 bit away from the optimal. Subsequent improvements by Li [19] enabled the construction of a coupling whose entropy is within 2 bits of the optimal value, regardless of the number of random variables involved. Despite these advances, Compton [15] identified a majorization barrier that limits further improvements, while Compton et al. [16] introduced the profile method offering stronger lower bounds for the coupling entropy.Minimum entropy coupling finds innovative applications beyond causal inference [14, 20, 21] . For instance, Sokota et al. [22] utilized it in Markov coding games to enable reinforcement learning agents to communicate via Markov decision process trajectories. This application showcased MEC's utility in enabling efficient information transmission through constrained environments like video game interactions. Similarly, de Witt et al. [23] applied MEC to securely encode secret information in regular text, showing MEC corresponds to the maximally efficient secure procedure.Lossy Source Coding While log-loss is widely used in prediction and learning, its application as a distortion measure in the context of source coding has been less explored, with the earliest examples appearing in [1] and [2] . Log-loss is particularly suited as a distortion measure in soft reconstructions, meaning the decoder outputs a distribution. Shkel and Verdú [3] explored a single-shot lossy source coding setting under logarithmic-loss, using a straightforward encoding scheme. Unlike the EBIM formulation in (4) which imposes a direct entropy constraint on the code, this approach constrained the code by the cardinality of its support.Finally, Blau and Michaeli [24] introduced the Rate-Distortion-Perception (RDP) tradeoff in lossy compression. The RDP framework does not fix the output distribution; instead, it imposes a softer perceptual constraint on the generated outputs. Additionally, our work incorporates an entropy constraint on T as a rate bottleneck, while in the RDP formulation, I(X; Y ) can be interpreted as the rate bottleneck. In this line of research, the work of Liu et al. [25] is closest in spirit to our approach, as the authors studied a lossy compression setting with different source and reconstruction distributions. They demonstrated that their setting could be formulated as a generalization of optimal transport with an entropy bottleneck. However, they used mean squared error (MSE) as the distortion metric, while we consider log-loss. Therefore, the mathematical machinery required for our analysis differs significantly from prior work. 
entropy-bounded information maximization: 
 Consider a discrete random variable X defined over the alphabet X = {1, . . . , n} with a given marginal probability distribution p X . The following problem aims to establish a maximal information coupling between X and another random variable T , defined over the alphabet T = {1, . . . , m}, where the entropy of T is constrained to be no more than R bits. Unlike minimum entropy coupling, the marginal distribution of the second random variable T is not predetermined; the only constraint on T is its entropy.EQUATIONwhere set M consists of all joint distributions p XT that satisfy the following conditions:1. t p XT (x, t) = p X (x), ensuring that the marginal distribution of X is preserved. 2. H(T ) ≤ R ≤ H(X), ensuring the entropy of T is constrained to be no more than R.We call this problem Entropy-Bounded Information Maximization (EBIM). Note that the objective in (10) is upper-bounded by R, since:EQUATIONThe following theorem establishes that only deterministic couplings can achieve this upper-bound. Theorem 1. I EBIM (p X , R) = R if and only if there exists a function g :X → T such that H(g(X)) = R.The formal proof is presented in Section A.2. Note that the mutual information I(X; T ) is invariant to permutations on T . Specifically, for any permutation π : T → T , we have I(X; T ) = I(X, π(T )).Given that problem (10) only constrains the entropy H(T ), the objective is indifferent to such permutations. Let us define the permutation group of a joint distribution p XT as:EQUATION)Remark 1. Each partition of X is associated with a permutation group of a deterministic mapping. Consequently, the total number of potential deterministic mapping groups, independent of the entropy constraint on T , will be the total number of feasible partitions of X . The total number of ways to partition a set of size n corresponds to the n-th Bell number, symbolized by B n . The growth rate of the Bell numbers is O(n n ) [26] , rendering brute force iteration of all deterministic mappings infeasible.In Figure 2 (left), a brute force method is applied to solve EBIM (10) for an input alphabet of size three. As observed, there are five potential partitions on X , each corresponding to a point where I EBIM (p X , R) = R. Given the impracticality of brute force search for large alphabet sizes, in Section 3.1, we introduce a greedy search algorithm to identify deterministic mappings with a guaranteed performance gap from the optimal. Following this, in Section 3.2, we explore optimal mappings close to these deterministic mappings, providing a strategy to narrow the gap between the identified deterministic mappings.Since iterating over all deterministic mappings is not feasible, one should look for carefully constructed search algorithms to find such mappings with resulting H(T ) as close as possible to R.Without the loss of generality, supposep X = [p 1 , p 2 , • • • , p n ]is arranged in a decreasing order. Algorithm 1 presents a search approach for discovering a deterministic mapping T = g(X), resulting in I(X; T ) that is at most h(p 2 ) bits away from the optimal I EBIM (p X , R), where h(•) is the binary entropy function: The deterministic EBIM solver in Algorithm 1 has O(n log n) time complexity, where n is the cardinality of the input alphabet. This is because the main loop of the algorithm runs for at most n steps (as at each step we combine two elements of the input distribution) and finding min/max elements can be done in O(log n) using a heap data structure. Also, the mutual information calculation at each step can be done in constant time by only calculating the decrease in entropy after combining two elements of the distribution. Theorem 2. If the output of Algorithm 1 yields mutual information I, thenh(p) = -p log(p) -(1 -p) log(1 -p).EQUATIONwhere h(•) is the binary entropy function, and p 2 denotes the second largest element of p X .Let n = |p X |. The procedure outlined in Algorithm 1 establishes a series of deterministic mappings ps , pEQUATION, corresponding to a decreasing sequence of mutual information values I . The algorithm then picks the mapping with the highest mutual information that does not exceed R. The proof involves establishing an upper bound on the gap between these successive mutual information values. A formal proof is presented in Section A.3.It is important to highlight that the gap described in Theorem 2 is bounded by one bit, i.e., h(p 2 ) ≤ 1, with equality achieved when p X = [0.5, 0.5]. Although the gap is capped at one bit, the maximal mutual information in the EBIM formulation scales with R. Thus, the most natural interpretation of this gap emerges in higher rate regimes. Furthermore, the gap described in Theorem 2 remains small when p 2 is small, specifically in cases where the input alphabet size is large and the distribution is not heavily skewed toward a few elements.Section 3.1 introduced a greedy search algorithm designed to identify deterministic mappings with a guaranteed and input-dependent gap from the optimal. In this section, we find the optimal couplings close to any deterministic mapping. This method allows us to close the gap between the mappings identified by Algorithm 1, as will be demonstrated later. Theorem 3. Let p XT denoted by a |X | × |T | matrix, defines a deterministic mapping T = g(X), with I(X; T ) = H(T ) = R g . We have I EBIM (p X , R g ) = R g , and for small enough ϵ > 0:1. I EBIM (p X , R g + ϵ) is attained as follows:Normalize the columns by dividing each column by its sum. Then, select the cell with the smallest normalized value and move an infinitesimal probability mass from this cell to a new column of p XT in the same row.2. I EBIM (p X , R gϵ) is achieved as follows: Identify the columns with the smallest and largest sums in p XT . Select the cell with the smallest value in the column with the lowest sum. Transfer an infinitesimal probability mass from this cell to the column with the highest sum in the same row. Figure 1 on the right depicts an example of optimal solutions in the neighborhood of a deterministic mapping. While Algorithm 1 effectively identifies deterministic mappings that produce mutual information close to the budget R, Theorem 3 can help bridge the remaining gap. More specifically, one can begin with a deterministic mapping and use two probability mass transformations outlined in Theorem 3 to navigate across the I-R plane.𝑅 𝑔 𝑅 ! 0.4 +𝜖 0.3-𝜖 0.2 0.1 0.4 0.3 0.2 0.1-𝜖 +𝜖 𝑝 𝑋𝑇 𝑝 𝑋𝑇 + d𝑝 ! 𝑝 𝑋𝑇 + d𝑝 " 0.4 0.3 0.2 0.1 I EBIM (p X , R) I EBIM (p X , R)Figure 2 illustrates this strategy; for p X = [0.7, 0.2, 0.1], identifying all 5 possible deterministic mappings is straightforward. Applying the transformations from Theorem 3 then yields various solutions across the I-R plane (represented by dashed lines). Subsequently, one can select the solution that maximizes mutual information for any given value of R (highlighted with a thick solid line), thus producing a comprehensive solution for every value of R. As demonstrated in Figure 2 , this strategy recovers the optimal solutions, as determined by brute force, for the simple case of an input alphabet of three. However, while effective, the optimality of this approach remains a conjecture.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: The paper focuses on the theoretical analysis of a novel lossy compression framework specifically for discrete alphabets and does not extend to public-facing applications at this stage. As the method developed is a foundational piece of research, it is not yet applicable to scenarios where societal impacts-positive or negative-could be evaluated. Therefore, discussions on societal impacts such as fairness, privacy, or security considerations are not applicable at this point. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
application: markov coding game with rate limit: 
 Markov Coding Games (MCGs), as introduced by Sokota et al. [22] , represent a specialized type of multi-player decentralized Markov Decision Processes (MDPs) involving several key components: a source, an agent (sender), a Markov decision process, and a receiver. An MCG episode unfolds in three stages: initially, the agent receives a private message from the source, which it must then indirectly convey to the receiver. Next, the agent participates in an episode of the Markov decision application of the transformations from Theorem 3 to each deterministic mapping (dashed lines) and selection of solutions with maximal mutual information for each R value (thick solid line). This strategy effectively recovers optimal solutions, aligning with those found by brute force in this case. process. Finally, the receiver attempts to decode the original message based on the observed MDP trajectory. The overall reward is a combination of the MDP payoff and the accuracy with which the receiver decodes the message. MCGs are particularly interesting due to their ability to generalize frameworks like referential games [27] and source coding [28] .We will consider a natural extension to Markov Coding Games, where the link from the source to the agent is rate-limited. This means, contrary to the original setting of Sokota et al. [22] , the agent does not fully observe the message at each MDP round, but will receive a compressed version of the message iteratively, and in turn, encodes information about the message in the MDP trajectory for the receiver.Following Sokota et al. [22] , we define a rate-limited MCG as a tuple ⟨(S, A, T , R), M, µ, ζ, R⟩, where (S, A, T , R) is an MDP denoted by state and action spaces, and reward and transition functions, respectively. M is a set of messages, µ is the prior distribution over messages M, ζ is a non-negative real number we call the message priority, and finally, R is the communication rate limit between the source and the agent. An MCG episode proceeds in the following steps:1. Message M ∼ µ is sampled from the prior over messages at the source. 2. Based on the selected message M and the history of the MDP episode, the source generates and transmits signal T to the agent, adhering to the rate limit R. 3. The Agent uses a conditional policy π |T , which takes current state s ∈ S and received signal T as input and outputs distributions over MDP actions A, to generate the next action a. 4. After repeating steps 2 and 3, the agent's terminal MDP trajectory Z is given to the receiver as an observation. 5. The receiver uses the terminal MDP trajectory Z to output a distribution over messages M, estimating the decoded message M .The objective of the agents is to maximize the expected weighted sum of the MDP reward and the accuracy of the receiver's estimateE[R(Z) + ζI[M = M ]] [22]. Optionally, If a suitable distance function exists, instead, the objective can also be adjusted to minimize the difference between the actual message and the guess. A diagram of the structure MCG with rate limit is shown in Figure 3 . pMT ← compress(pM , R) 7:t ∼ p T |M (m) 8:Send t to the agent. 9:pT← m ′ pMT (m ′ , •) 10: pT A ← min_ent_coupling(pT , π(s)) 11: pMA ← t ′ pMT (•, t ′ ) p A|T (t ′ ) 12:a, s ← Observe action and next state 13:pM← p M |A (a) Algorithm 3 Agent 1: Input: π, µ, R, s 0 2: Initialize message belief pM ← µ 3: Initialize state s ← s 0 4: while Agent's turn do 5: pMT ← compress(pM , R) 6:Receive t from the source. 7:pT← m ′ pMT (m ′ , •) 8: pT A ← min_ent_coupling(pT , π(s)) 9: π |T ← p A|T (t) 10: a ∼ π |T 11:s ← Commit action a to MDP. 12:pMA ← t ′ pMT (•, t ′ ) p A|T (t ′ ) 13: pM ← p M |A (a) Algorithm 4 Receiver 1: Input: z, π, µ, R, s 0 2: Initialize message belief pM ← µ 3: Initialize state s ← s 0 4: for s, a ∈ z do 5: pMT ← compress(pM , R) 6: pT ← m ′ pMT (m ′ , •) 7: pT A ← min_ent_coupling(pT , π(s)) 8: pMA ← t ′ pMT (•, t ′ ) p A|T (t ′ ) 9: pM ← p M |A (a) 10: return arg max m ′ pM (m ′ )Marginal Policy Following Sokota et al. [22] , before execution we first derive a marginal policy π for the MDP, based on the Maximum-Entropy reinforcement learning objective:EQUATION)The value of β in (14) needs to be determined in accordance with the message priority ζ of the MCG. Note that this marginal policy does not depend on the choice of message. By introducing stochasticity into this policy, we can encode information about the message into the selection of actions at each step during runtime. For more details, see Section C.1.Step 1 -Source: Message Compression At the beginning of each round, given the updated message belief p M , the source compresses the message to generate the signal T , adhering to the sourceagent rate limit R, by solving EBIM in (10) . The source then transmits the signal T to the agent. Subsequently, after observing the action taken by the agent, the source updates the message belief for the next round. Algorithm 2 outlines the steps taken by the source.Step 2 -Agent: Minimum Entropy Coupling As illustrated in Algorithm 3, at each round, upon receiving the signal T , the agent constructs a conditional policy π |T by performing minimum entropy coupling between the action distribution from the marginal policy π(s) with the signal distribution p T . Subsequently, the next action is sampled from the conditional policy, a ∼ π |T . Finally, the agent updates the message belief based on the chosen action.Receiver: Decoding the Message Given the agent's final MDP trajectory, the receiver mirrors the actions of the source and agent to update the message belief at each step. As outlined in Algorithm 4, the process begins with the receiver compressing the message based on the current message belief. This is followed by performing minimum entropy coupling between the marginal policy and the distribution of the compressed message. The final message belief is used to estimate the decoded message.This section presents the experimental results of the method described in Section 4.1, applied to Markov Coding Games. For our experiments, we utilize a noisy Grid World environment for the Markov Decision Process. Section C.2 provides more detail on the environment setup used in this experiment.The marginal policy is learned through Soft Q-Value iteration, as described in Algorithm 8. By increasing the value of β in Equation ( 14), we induce more randomness into the marginal policy. Consequently, higher values of β lead to an increase in the total number of steps taken by the agent to reach the goal, resulting in a more heavily discounted reward. Conversely, as the entropy of actions at each state is increased, there is an increase in the mutual information between the actions and the compressed message during the minimum entropy coupling at each step. This dynamic establishes a fundamental trade-off between the MDP reward and the receiver's decoding accuracy, through the adjustment of β. Figure 8 We compare our proposed compression method in Algorithm 1 with a baseline of uniform quantization. As detailed in Algorithm 5, given an entropy budget R, the input symbols are uniformly partitioned into ⌊2 R ⌋ bins, and each bin is encoded with the same code.Figure 4 illustrates the trade-off between the average MDP reward and the receiver's decoding accuracy by varying β, using our deterministic EBIM solver in Algorithm 1, and the uniform quantization encoder in Algorithm 5. Here, the compression rate is defined by the ratio of the message entropy to the allowed code budget H(T ). A marginal policy optimized with a higher β prioritizes message accuracy over MDP payoff, as higher entropy of actions at each state provides more room for the agent to encode information about the message. Consequently, as observed, this leads to improved receiver accuracy in fewer steps. In addition, a lower compression rate permits the agent to retain more information about the message, enabling more effective encoding of information in the selected trajectory.  
conclusion: 
 We investigated a lossy compression framework under logarithmic loss, where the reconstruction distribution differs from the source distribution. This framework supports joint compression and retrieval applications, or more generally, cases where distributional shifts occur due to processing. We demonstrated that this framework effectively extends the classical minimum entropy coupling by incorporating a bottleneck, which regulates the degree of stochasticity in the coupling.Furthermore, we showed that separately optimizing the encoder and decoder decomposes the Minimum Entropy Coupling with Bottleneck (MEC-B) into two distinct problems: Entropy-Bounded Information Maximization (EBIM) for the encoder, followed by Minimum Entropy Coupling (MEC) for the decoder. We conducted an extensive study of the EBIM problem, provided a functional mapping search algorithm with guaranteed performance, and characterized the optimal solution adjacent to functional mappings, offering valuable theoretical insights into the problem structure. To illustrate an application of MEC-B, we presented experiments on Markov Coding Games (MCGs) with rate limits. The results demonstrated the trade-off between MDP reward and receiver accuracy, with varying compression rates, compared to baseline compression schemes.Future research could focus on quantifying the gap between the separate optimization of the encoder and decoder and the optimal joint setting. Also, enabling fine-grained control over the entropy spread in the coupling can be key in some applications. Additionally, the application of Entropy-Bounded Information Maximization (EBIM) in watermarking language models [29] suggests a valuable intersection with state-of-the-art AI applications. Moreover, extending this framework to continuous cases could lead to the design of neural network architectures based on the proposed framework and provide information-theoretic insights into a broad spectrum of deep learning problems. These include unpaired sample-to-sample translation [30] [31] [32] , joint compression and upscaling [25, 33] , and the InfoMax framework [34, 35] , among others. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper is focused on the theoretical aspects of a novel lossy compression framework and does not involve the release of data or models that carry a high risk for misuse. There are no pretrained models, image generators, or scraped datasets associated with this research that would necessitate safeguards for responsible release. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The paper properly credits the creators and original owners of all assets used, including codes.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The submission includes the codes that implement the methods presented in the paper. Instructions on how to use the codes are also provided.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This research did not involve any crowdsourcing experiments or studies with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: This research did not involve studies with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: A.1 Proof of Lemma 1 Lemma 1. Given a Markov chain X ↔ T ↔ Y :EQUATIONProof. By multiple applications of the chain rule for mutual information, i.e. I(A; B, C) = I(A; B)+ I(A; C|B), we have:EQUATION)Note that from the Markov chain property, we have I(X; Y |T ) = 0.A.2 Proof of Theorem 1Theorem 1. I EBIM (p X , R) = R if and only if there exists a function g : X → T such that H(g(X)) = R.Proof. If such g exists, letp * XT (x, t) = p X (x) t = g(x) 0 otherwiseThis joint distribution effectively sets T = g(X). Note that p * XT ∈ M and we haveI(X; T ) = H(T )-H(T |X) = H(g(X)) = R. Since I EBIM (p X , R) ≤ R, we conclude that I EBIM (p X , R) = R for p XT = p * XT . Conversely, if I EBIM (p X , R) = R, then there exists p * XT ∈ M such that I(X; T ) = R. Therefore H(T ) = I(X; T ) + H(T |X) = R + H(T |X) ≤ R ⇒ H(T |X) ≤ 0As a result, H(T |X) = 0 and H(T ) = R, which means p * XT defines a function g such that T = g(X), and H(g(X)) = H(T ) = R.Before providing the formal proof, it is helpful to gain some insight into the structure of the solution first. Remark 2. Let n = |p X |. The procedure outlined in Algorithm 1 establishes a series of deterministic mappings pEQUATIONEQUATIONl , • • • , p (n-1) s , p (n-1) l, corresponding to a decreasing sequence of mutual information valuesEQUATIONEQUATIONl , • • • , I (n-1) s , I (n-1) l. The algorithm then picks the mapping with the maximum mutual information that does not exceed R. ThereforeR -I(X; T ) ≤ max I (0) l -I (1)s , I (1) s -IEQUATIONl , IEQUATIONExample. For p X = [0.4 0.3 0.2 0.1], Algorithm 1 traverses through the following deterministic mappings, from left to right:p (0) l p (1) s p (1) l p (2) s p (2) l p (3) s p (3) l p XT    0.4 0 0 0 0 0.3 0 0 0 0 0.2 0 0 0 0 0.1       0.4 0 0 0 0.3 0 0 0 0.2 0 0 0.1       0.4 0 0 0.3 0 0 0 0.2 0 0 0 0.1       0.4 0 0.3 0 0 0.2 0 0.1       0.4 0 0.3 0 0.2 0 0 0.1       0.4 0.3 0.2 0.1       0.4 0.3 0.2 0.1    I (X; T ) H (p X ) H ([.4 .3 .3]) H ([.7 .2 .1]) H ([.7 .3]) H ([.9 .1]) 0 0Definition 1. Let P ′ be a probability distribution resulted from merging two elements p > 0 and q > 0 in an original distribution P , i.e.P = [• • • p • • • q • • •] and P ′ = [• • • p + q • • •].Then, the amount of decrease in the entropy from this merge operation is characterized by:EQUATIONEQUATION)Lemma 2. The following properties hold for the function ∆ H :1. ∆ H (• , •) is monotonically increasing in both arguments. 2. ∆ H (• , •) is concave. 3. ∆ H (p , 1 -p) = h(p).Proof. The properties are derived through straightforward derivative calculations:1. ∂ ∂p ∆ H = log(1 + q/p) ≥ 0, and ∂ ∂q ∆ H = log(1 + p/q) ≥ 0.2. The Hessian of ∆ H is negative semidefinite:EQUATION)with eigenvalues λ 1 = 0 and λ 2 = -( q p + p q )( 1 p+q ) < 0.3. ∆ H (p , 1 -p) = -p log p -(1 -p) log(1 -p) = h(p).Theorem 2. If the output of Algorithm 1 yields mutual information I, thenEQUATIONwhere h(•) is the binary entropy function, and p 2 denotes the second largest element of p X .Proof. For the gap to the optimal objective, I EBIM (p X , R) -I, we have:▷ Equation (11) I EBIM (p X , R) -I ≤ R -I ▷ Remark 2 ≤ max i∈{1,••• ,n-1} I (i-1) l -I (i) l ▷ Algorithm 1, Line 8 = max i∈{1,••• ,n-1} H x p (i-1) l -H x p (i) l ▷ Definition 1 = max i∈{1,••• ,n-1} ∆ H i k=1 p k , p i+1 ▷ Lemma 2.1 ≤ max i∈{1,••• ,n-1} ∆ H i k=1 p k + n k=i+2 p k , p i+1 = max i∈{1,••• ,n-1} ∆ H (1 -p i+1 , p i+1 ) ▷ Lemma 2.3 = max i∈{1,••• ,n-1} h (p i+1 ) ▷ p 2 , p 3 , • • • , p n ≤ 0.5 = h(p 2 ).Note that the above bound on the optimality of the proposed algorithm is by no means tight, as it does not account for the intermediate distributions p , with I(X; T ) = H(T ) = R g . We have I EBIM (p X , R g ) = R g , and for small enough ϵ > 0:1. I EBIM (p X , R g + ϵ) is attained as follows: Normalize the columns by dividing each column by its sum. Then, select the cell with the smallest normalized value and move an infinitesimal probability mass from this cell to a new column of p XT in the same row.2. I EBIM (p X , R gϵ) is achieved as follows: Identify the columns with the smallest and largest sums in p XT . Select the cell with the smallest value in the column with the lowest sum. Transfer an infinitesimal probability mass from this cell to the column with the highest sum in the same row.Example. Figure 6 depicts an example of optimal solutions in the neighborhood of a deterministic mapping. Proof. Let us view the joint distribution as a n × m matrix p XT . Note that:𝑅 𝑔 𝑅 ! 0.4 +𝜖 0.3-𝜖 0.2 0.1 0.4 0.3 0.2 0.1-𝜖 +𝜖 𝑝 𝑋𝑇 𝑝 𝑋𝑇 + d𝑝 ! 𝑝 𝑋𝑇 + d𝑝 " 0.4 0.3 0.2 0.1 I EBIM (p X , R) I EBIM (p X , R)EQUATIONFor example:EQUATIONConsider a perturbation dP ∈ R n×m to p XT . For p XT + dP to be a valid distribution in M, we need:1. t dP (x, t) = 0, ∀x ∈ X 2. dP (x, t) ≥ 0, ∀x, t s.t. t ̸ = g(x) 3. dP (x, t) ≤ 0, ∀x, t s.t. t = g(x)We define the set of all such perturbations as Ω ⊂ R n×m . Next, let us define basis perturbations ∆ x,t for t ̸ = g(x) as:EQUATIONNote that ∆ x,t represents moving a probability mass of ε from non-zero cell (x, g(x)) to empty cell (x, t). For the example in equation ( 24):∆ 2,3 =    0 0 0 0 -ε 0 +ε 0 0 0 0 0 0 0 0 0   The significance of these bases is that any perturbation in Ω can be represented as:EQUATIONwith coefficients α x,t ≥ 0. For example:   0 0 0 0 -3ε +2ε +ε 0 0 0 0 0 0 0 0 0    = 2 × ∆ 1,1 + ∆ 1,2 .Realizing I XT , H XT , and H T as functions of a joint distribution, we are interested in calculating the ratio dI XT /dH T with respect to a perturbation dP ∈ Ω as ε → 0 at p XT . Note that since for any dP ∈ Ω, dH X = 0, we have:EQUATION)dH X,T (p XT , ∆ x,t ) represents the amount of change in the joint entropy, when an infinitesimal mass of ε is moved from (x, g(x)) to (x, t). More precisely, from ( 23) and ( 25):EQUATIONThe last line uses the fact that for small enough x, f (x) = a log a a-x = x + O(x 2 ). Similarly:EQUATIONPlugging ( 28) and ( 29) back to ( 27), we will get:EQUATIONwhere α x,t is normalized by:α x,t = α x,t x t̸ =g(x) α x,t .Let's focus on the limit of (30) when ε → 0: If there is any t ∈ T with p T (t) = 0 and α x,t > 0, the denominator of the second term will grow without bound, otherwise the denominator remains bounded. Therefore, for the limit of (30) we have:EQUATIONFor dH T > 0, we need to find a perturbation (i.e. coefficients α x,t ) that maximizes dI XT /dH T . From (31) , this means ∃t ∈ T with α x,t > 0 and p T (t) = 0.α = argmax α dI X,T dH T = argmax α 1 - x p T (t)=0 α x,t -1 = argmax α x p T (t)=0 α x,tTherefore,x p T (t)=0 α x,t = 1 which means α x,t = 0 if p T (t) > 0.In other words, we should only consider perturbations where masses are moved to all-zero columns. Continuing (30) :α = argmax α dI X,T dH T = argmax α 1 - x p T (t)=0 α x,t log p X (x) ε x p T (t)=0 α x,t log p T g(x) ε = argmax α 1 - -log ε + x p T (t)=0 α x,t log p X (x) -log ε + x p T (t)=0 α x,t log p T g(x) = argmax α -1 log ε   x p T (t)=0 α x,t log p T g(x) p X (x)   = argmin α x p T (t)=0 α x,t log p X (x) p T g(x).This is achieved by selectingEQUATIONIn other words, first, normalize columns in p XT by their sum, then move an infinitesimal probability mass from the cell with the smallest normalized value to an all-zero column. It is easy to confirm that dH T > 0 for such a perturbation. For the example distribution in (24) :EQUATIONOn the other hand, for dH T < 0, we need to find a perturbation (i.e. coefficients α x,t ) that minimizes dI XT /dH T . From (31) , this means α x,t = 0 for all t ∈ T that p T (t) = 0. Therefore, as in (30) :α = argmin α dI X,T dH T = argmin α 1 - x t̸ =g(x) α x,t log p X (x) ε x t̸ =g(x) α x,t log p T g(x) p T (t) = argmin α 1 - -log ε + x t̸ =g(x)α x,t log p X (x)x t̸ =g(x) α x,t log p T g(x) p T (t) = argmin α x t̸ =g(x) α x,t log p T g(x) p T (t) .This is achieved by selectingEQUATIONIn other words, moving an infinitesimal probability mass from the smallest column to the largest column of p XT . It is easy to confirm that dH T < 0 for such a perturbation. For the example distribution of (24):EQUATIONConsider two discrete random variables X and Y , over alphabets X and Y with probability mass functions p X and p Y , respectively. The goal of minimum entropy coupling is to find the joint distribution p XY that minimizes the joint entropy H(X, Y ):EQUATIONThis is a concave minimization problem over a standard polyhedron [36] . Therefore, every vertex of the polyhedron is a local minimum and the global minimum happens at a subset of the vertices.Note that an standard polyhedron is defined asP = {x ∈ R n | Ax = b, x ≥ 0}, where A ∈ R m×n with linearly independent rows. A point x * ∈ P is a vertex if and only if it has nm zero elements and columns of A corresponding to other m non-zero elements are linearly independent. Hence, to exhaustively iterate all the vertices:1. Choose m linearly independent columns A π(1) , • • • , A π(m) .2. Let x i = 0 for all i ∈ π(1), ..., π(m)3. Solve the system of m equations Axb = 0 for the unknowns x π (1),• • • , x π (m)Therefore a crude upper-bound on the number of vertices would be n m . This can be enhanced to n-m/2 m/2 [37] which is still exponential in m. Next, we will show that the minimum entropy coupling problem as defined in ( 36) is essentially NP-Hard. This is done by reduction from another NP-complete problem, the k-Subset-Sum (see [6] for more details). Remark 3. The minimum entropy coupling problem in ( 36) is NP-Hard [6] .Proof. To show an optimization problem is NP-Hard, we need to show the corresponding decision problem is NP-Hard. Given an optimization problem, a decision version is whether or not any target value t is achievable. Without the loss of generality, assume |X | > |Y|. We set t = H(Y ), i.e. to decide if there exists a function f : X → Y such that Y = f (X). Let's call this problem Deterministic Matching.Next, we show any instance of the k-Subset-Sum problem can be reduced to an instance of Deterministic Matching, by a polynomial-time procedure (denoted by the notation < p ). Consider a general instance of the k-Subset-Sum problem: Given set S of integers and target values {t i |1 ≤ i ≤ k}, decide if there exists a partition {S i |1 ≤ i ≤ k} of size k on S such that S i = t i for all 1 ≤ i ≤ k. Now, set p X (i) = s i / (S), ∀s i ∈ S and p Y (i) = t i / (t j ). Then, clearly solving Deterministic Matching for p X , p Y will solve the original k-Subset-Sum problem. Therefore, k-Subset-Sum < p Deterministic Matching and hence, Deterministic Matching is NP-Hard. Consequently, Minimum Entropy Coupling is an NP-Hard optimization problem.Finally, we introduce two linear-time approximate greedy algorithms for the minimum entropy coupling problem, and numerically compare their achieved minima to a general approximate algorithm. pY (y * ) ← pY (y * ) -min{pX (x * ), pY (y * )} 7: return pXY At each step, each algorithm selects a symbol from each random variable and connects them in the joint distribution by assigning the higher probability of the two symbols, updating the marginals accordingly. The max-seeking version targets the symbols with the largest remaining probability mass at each step, whereas the zero-seeking version pairs symbols with the most similar probability mass. Furthermore, the greedy algorithm described by Kocaoglu et al. [14] resembles the max-seeking version outlined in Algorithm 6.As a simple baseline, we randomly generated 100 pairs of joint distributions and fed them to our greedy solvers. We also used a general concave minimization method, Successive Linearization Algorithm (SLA) [38] , and compared the achieved joint entropy. Table 1 summarizes the average joint entropy over 100 trials for each method. Markov Decision Process MDPs are represented by the tuple notation (S, A, R, T ), where S is the state space, A denoteds the action space, R : S × A → R defines the reward function, and T : S × A → P(S) represents the transition function. The way an agent interacts with an MDP is determined by its policy π : S → P(A), which assigns distributions over actions for each state. Our main focus is on episodic MDPs, which terminate after a limited sequence of transitions. The sequence of states and actions, called a trajectory, is recorded as z = (s 0 , a 0 , . . . , s T ). The notation R(z) = t γ t R(s t , a t ) is used to represent the total rewards accrued throughout a sequence. The primary aim of an MDP is to devise a policy that maximizes the expected cumulative rewardE[R(Z)|π].Maximum Entropy Reinforcement Learning a policy that exhibits a high degree of randomness is preferred in certain situations. Under these circumstances, the maximum-entropy RL objectiveEQUATIONserves as a compelling substitute to the conventional goal of maximizing expected aggregate rewards [39] . This objective trades off expected returns with conditional entropy of the selected policy, modulated by the temperature hyperparameter β. A generalization of the Q-value iteration method for maximum-entropy RL objective (also known as soft Bellman equation [40] ) is shown in Algorithm 8.Algorithm 8 Soft Q-Value Iteration 1: Input: MDP, β 2: Initialize: π0 to any policy 3: i ← 0 4: repeat 5:Q i+1 soft (s, a) ← R(s, a) + γ s ′ Pr(s ′ |s, a) max β a ′ Q i soft (s ′ , a ′ ) 6: i ← i + 1 7: until ∥Q i soft (s, a) -Q i-1 soft (s, a)∥∞ ≤ ϵ 8: Extract policy: πgreedy(•|s) = softmax Q i soft (s, •) /βThe soft maximum operator is defined as max β a Q(s, a) = β log a exp Q(s,As discussed in Section 2, our proposed search method in Algorithm 1 is compared with the encoder from Shkel and Verdú [3] . Our formulation directly imposes an entropy constraint on the code, whereas the encoding scheme by Shkel et al. limits the code by its alphabet size. In their approach, the encoder iterates over all input symbols, assigning each one to a message that has accumulated the smallest total probability up to that point.Figure 9 displays the mutual information obtained for each maximum allowed code rate value, considering two different input distributions. As observed, the two methods yield comparable mutual information in the high-rate regime. However, in the low-rate regime, our proposed algorithm identifies more mappings and thus significantly outperforms the encoder described in [3] . As discussed in Section 1, optimizing the encoder and decoder separately for the Minimum Entropy Coupling with Bottleneck (MEC-B) problem, as outlined in (2), involves first designing the encoder by solving the Entropy-Bounded Information Maximization (EBIM) in (10) . This is followed by optimizing the decoder using Minimum Entropy Coupling (MEC) between the code distribution (derived from the previous step) with the output distribution.To illustrate the couplings generated, we apply the MEC-B framework to inputs and outputs that are uniformly distributed across an alphabet of size 30. For EBIM, we only search for deterministic mappings using Algorithm 1, while for MEC, we employ the max-seeking method outlined in Algorithm 6. Figure 10 illustrates the generated couplings for varying encoder compression rates, defined by the ratio of the entropy of the input H(X) to the allowed code budget H(T ). Greater compression rates are observed to lead to larger entropy couplings; moving from completely deterministic mappings to increasingly stochastic ones. The compression rate is defined as H(X)/R. Higher compression rates lead to more stochastic couplings with increased entropy.This section introduces a preliminary formulation and initial results for a joint image compression and upscaling task, intended to illustrate a practical application of our proposed MEC-B framework and to suggest potential avenues for future research.We consider two unpaired datasets, D X and D Y , which contain low-resolution and high-resolution images, respectively. Because the datasets are unpaired, there is no direct correspondence between a specific low-resolution image in D X and a high-resolution image in D Y . In this setup, the task requires compressing a low-resolution image X into a compressed representation T , and then reconstructing an upscaled version Y from T .In applying our MEC-B framework in Eq. ( 2), we leverage the Variational Information Maximization approach of Barber and Agakov [42] :EQUATIONEQUATIONEQUATIONUsing the Lemma 5.1 from Chen et al. [43] , we have:EQUATIONEQUATIONIn practical terms, by training the network q γ to model the degradation process Y → X and reconstructing x from ŷ, we maximize a lower bound on the mutual information I(X; Y ). Simultaneously, we enforce the output distribution constraint p Y via an adversarial loss from a discriminator d ρ . The total loss is therefore composed of an information loss and an adversarial loss, L = L info + λL adv . Figure 11 illustrates a block diagram of this framework. Note that we use a deterministic encoder f θ that outputs the quantized code T , while the generator remains stochastic due to the addition of noise z. Figures 12 and 13 present sample output results after training the networks to achieve 4×-upscaling of the input images, using the MNIST [44] and SVHN [45] datasets. Observing Figure 13 , we notice some color discrepancies between the original and upscaled images. This discrepancy highlights an inherent property of mutual information: for any invertible function f , I(X; Y ) = I(X; f (Y )). This implies that the objective function is invariant to feature permutations, including transformations like color rotations in image channels, which can manifest as color distortions in the output. To mitigate such artifacts, careful architectural or design constraints are required to properly address feature permutations.𝑋 ~ 𝑝 ! 𝑌 & 𝑇 𝑌 ~ 𝑝 " ℒ #$% 𝑍 ~𝒩(0, 𝐼) ℒ &'() Encoder 𝑓 ! Discriminator 𝑑 " Generator 𝑔 # Reconstructor 𝑞 $code dimension code bits/dim Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 


Decision: The paper presents an interesting lossy compression framework under log loss, Minimum Entropy Coupling with Bottleneck. The reviewers all agree with the contribution and novelty of the paper. Please include the promised changes in the camera ready version.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: * In terms of real-world impact, could the authors further elaborate how their EBIM algorithm would contribute to robust watermarking approaches?
limitations: limitations: The authors discuss limitations adequately.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: >  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: 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?
limitations: limitations: Have the authors adequately addressed the limitations

Yes.

Comments: title: Thanks for Addressing my Concern
Thank you for your comment!
Thanks for Your Response
Response
comment: Given the authors' willingness to test their intriguing method on a more tangible application domain, I have decided to increase my score.
Dear Reviewer,

Thank you for your comments and the constructive feedback on our work.

Our primary goal with this paper was to introduce and lay the foundational groundwork for this general problem and its potential applications. We note that broader applicability might require additional problem-specific adaptations, which are beyond the scope of this initial study.

To address the practical application aspect, we are working on including preliminary formulation and results for a joint image compression and upscaling task in the appendix of our paper. This inclusion is intended to illustrate a practical application and suggest possible future research directions based on our framework.

We appreciate your feedback and hope that this addition addresses some of your concerns.
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.
Thank you for your response. This is a good paper with solid theory and interesting potential uses. I have raised my score by 1 point.
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.