Minimum Entropy Coupling with Bottleneck
Authors: MohammadReza Ebrahimi
Jun Chen
Ashish J Khisti
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Compression
Minimum Entropy Coupling
Log Loss
Markov Coding Games
Primary area: other
TL;DR: We present a novel lossy compression framework under log loss called Minimum Entropy Coupling with Bottleneck.

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.

Minimum Entropy Coupling with Bottleneck
M.Reza Ebrahimi University of Toronto ebr ahimi @mail. uttronto.coo ca
Jun Chen McMaster University jtenmmnnnemet.rrr.co
Ashish Khisti University of Toronto
akhisti rece.. www.ce.utoootoooom
Abstract
This paper investigates novel lossy compression framework operating under loga- rithmic loss, designed to handle situations where the reconstruction distribution diverges from the source distribution. This framework especially relevant for applications that require joint compression and retrieval, and in scenarios involving distributional shifts due to processing.
show that the proposed formulation
extends the classical minimum entropy coupling framework by integrating bot- tleneck, allowing for a controlled 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-Baat Boundddd 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 illustrate the practical application of MEC-B through experiments in Markov Coding Games (MCGs) under rate limits. These games simulate communication scenario within Markov Decision Process, where an agent must transmit a compressed message from a sender to receiver through its actions. Our experiments highlight the trade-offs between MDP rewards and receiver accuracy across various compression rates, showcasing the efficacy of our method compared conventional compression baseline.
Introduction
Consider the following Markov Chain modeling general lossy compression framework
X PTIX, T gy IT, Y. where the input X with a marginal distribution px, is encoded by the proba- bilistic encoder p to generate the code T. Subsequently, the probabilistic decoder reconstructs Y from T. The objective to identify the encoder and decoder that minimize the distortion between X and Y, subject
upper bound constraint the expected code length H(T) S R.
common to measure the sample-wise distortion via direct comparison of (ar, y) pairs through a distortion function d(.; -), and consider the expectation E [d(XX, Y)] as measure of average distortion. Instead, we propose using the logarithmic loss (log-loss) [X YY). or equivalently 1 [(X; Y), as an alternative metric 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 distorted
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

sample point [3]. Consequently, the optimization problem is formulated as follows:
min H(X(Y) P RVIT
s.t. X ++ 7 +T,, H(T) s R
P(X)= = px-
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):
Minimum Entropy Coupling with Bottleneck (MEC-B)
MMEC.(PX.PP' ,
max I(X;Y) PTIX: IY
s.t.
X
H(T) - R.
(2)
P(Y) = Py
P(X) = PX
The addition of an output distribution constraint is a practical necessity, in lossy compression setup the decoder needs to generate outputs following desired distribution. For example, in image restoration, the output consists reconstructed images from the code adhering a certain distribution, possibly the same as the input distribution.
We explore two special cases of (2), where either the encoder 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 > HX).. In this scenario,
X T, and the optimization simplifies to:
Minimum Entropy Coupling (MEC)
Imec(Px,P)) = max I(X;Y)
PYIX
s.t. P(Y) PY: P(X) = px
(3)
This involves identifying the probabilistic mapping Prlx between the marginals px and that maximizes the obtained mutual information. This problem, described in (3), has been extensively studied in the literature as minimum entropy coupling (MEC), with early research conducted by Vidyasagar [4], Painsky al. [5], Kovačević et al. [6], Cicalese al. [7], among others. Thus, we define the original problem presented in (2) as minimum entropy coupling with bottleneck (MEC-B). Next, consider case where the decoder is removed, resulting from the relaxation of the output distribution constraint in (2):
Entropy-Bounded Information Maximization (EBIM)
IEDIM(X,, R) max PTIX
I(X:T)
s.t.
H(T) < R
(4)
P(X) = PX
Similar 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 more flexible entropy constraint on one of the variables. Lemma provides a decomposition
the mutual information between input and output T(X; Y), given the Markov chain X + T ++ Y.

---

Lemma 1. Given a Markov chain X ++ ++ ++ Y: T(X:V) [(X;T) TY: ( [(T;
The proof follows multiple applications of the chain rule for mutual information. The following lower bound on the MEC-B objective attainable based Lemma 1:
T(X;)) T(X; 7) + I(Y; R.
In this work, we consider maximizing the lower bound (6) as a proxy to the main objective. This allows 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), TEBIM R), resulting in the marginal distribu- tion Pr 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, Imuc(pr (fr, Py)
Therefore, in terms of problems (2), (3), and (4):
IMEC-B Py, R))
max
I(X;Y)
(7)
prix:
max
(T(X;T) + I(Y:T) R)
(8)
2YiT
IEXM((XX R) + IMEC py) R.
In this paper, we address the Entropy-Boumne Bounded Information Maximization problem in Section 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 greedy algorithm designed to identify deter- ministic mappings with guaranteed input-dependent gap from the optimal solution. Subsequently, in Section 3.2, we describe 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. Ex- perimental 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, concise overview of the original minimum entropy coupling problem, and additional experimental results.
2
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 long history, with early examples by Fréchet [8] seeking joint distribution that maximizes correlation subject to marginal constraints. References [9-12] provide 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 some random variables. This problem has been first studied in [4-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 local minimum with a gap of + log n bits from the optimum, where n represents the size of the alphabet. This bound was further improved in subsequent works [15, 16].
3

---

Based on tools from the theory of majorization [17], Cicalese et al. [18] developed new greedy algorithm producing solutions 1 bit away from the optimal. Subsequent improvements by Li [19] enabled the construction of 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, 21J. 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 [I] and [2]. Log-loss is particularly suited as distortion measure in soft reconstructions, meaning the decoder outputs a distribution. Shkel and Verdú [3] explored 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 Dww.--ottoooon-ereeeee 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 7" as a rate bottleneck, while in the RDP formulation, [(X; Y) can be interpreted as the rate bottleneck. In this line of research, the work of Liu 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.
(RDP) tradeoff in lossy
3 Entropy-Boundee Information Maximization
Consider a discrete random variable defined over the alphabet X' = (1,..., n) with a given marginal probability distribution px- The following problem aims to establish maximal information coupling between X and another random variable 7', defined over the alphabet T = {l,..., m]. where the entropy of I' is constrained 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.
LEBIM (px, R)
max I(X;T), PXTEM
(10)
where set M consists all joint distributions pXT that satisfy the following conditions:
1. Σ, pxT(x, 1) = px(x), ensuring that the marginal distribution of X is preserved.
2. H(T) < R HX)., ensuring the entropy of is constrained to be no more than R.
We call this problem Entropy- Boundee Information Maximization (EBIM). Note that the objective in (10) upper- by R, since:
TEAM (px, R)
max
I(X;T)
PXTEM
max
H(T) < R.
(1I)
PXTEM
The following theorem establishes that only deterministic couplings can achieve this upper-bound Theorem 1. (Px, R) R if and only if there exists function X + T such that (g(x)) R.
The formal proof is presented Section A.2. Note that the mutual information T(X:T) invariant to permutations on T. Specifically, for any permutation π T + T, we have I(X:T) I(X, (TT)).

---

Given that problem (10) only constrains the entropy HT"), the objective is indifferent to such permutations. Let define the permutation group of a joint distribution pxt as:
P(pxT) (P P(z, (t)) (x, : - TT
(12)
Remark 1. Each partition of X is associated with permutation group of deterministic mapping. Consequently, the total number of potential deterministic mapping groups, independent of the entropy constraint on T, will be the total number 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,, The growth rate of the Bell numbers is O(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 LEBIM Rt) R. Given the impracticality of brute force search for large alphabet sizes, in Section 3.1, we introduce greedy search algorithm to identify deterministic mappings with guaranteed performance gap from the optimal. Following this, in Section 3.2, we explore optimal mappings close to these deterministic mappings, providing strategy to narrow the gap between the identified deterministic mappings.
3.1 Proposed Search Algorithm for Deterministic Mappings
Since iterating over all deterministic mappings is not feasible, one should look for carefully con- structed search algorithms find such mappings with resulting H (T) as close as possible R. Without the loss of generality, suppose Algorithm 1 presents search approach for discovering deterministic mapping T g(X). resulting in T(X; 7) that is at most (1(2) bits away from the optimal TEmm((xx R), where h(-) is the binary entropy function: h(p) = -opo:-plloooooe log(p) - (1 pp) log(1 p)-
= [PI, ... Pal is arranged in decreasing order.
Algorithm Deterministic EBIM Solver
Input: px. Output: Pxt
1: pxT + diag(px)
2: if R H(X) then
3:
return PXT
4: for i f- to [px| 1 do
5:
(9]
Merge the two columns with the smallest sum in pxr-
6:
7 < Mutual Information imposed by p!
7:
[9]
<
Merge the two columns with the largest sum in pxt.
8:
(0) < Mutual Information imposed by pi
(8)
9:
if T < I then
10:
return p!"'
((59 < 1 then
12:
return
13:
else
14:
PXT Pi ())
The deterministic EBIM solver Algorithm has O(n logn) 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 steps (as at each step we combine two elements of the imput distribution) and finding min/max elements can be done in Olog n) using heap data structure. Also, the mutual information calculation at each step can done in constant time by only calculating the decrease in entropy after combining two elements of the distribution.
Theorem 2. If the oulput of Algorithm I yields mutual information I, then TERIM(Xx, R) - î h(p2),
(13)
where fu(-) is the binary entropy function, and p2 denotes the second largest element of px.
5

---

Let = l The procedure outlined in Algorithm establishes series of deterministic mappings (1) (1) Pa (n- (n-1) corresponding to decreasing sequence of mutual information values Ps Pt
Pi
1.0h 110
10 (--1) 1 11-1)_ 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,
is important to highlight that the gap described in Theorem 2 bounded by one bit, i.e. h(p2) - with equality achieved when px = [0.5, 0.5). Although the gap is capped at one bit, the maximal mutual information 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 p2 is small, specifically cases where the input alphabet size large and the distribution not heavily skewed toward few elements.
3.2 Optimal Coupling Around Deterministic Mappings
Section 3.1 introduced a greedy search algorithm designed to identify deterministic mappings with 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 PXT denoted by a |X| x [T] matrix, defines a deterministic mapping T (X),,
with ; T) HT") Ry. We have [px Rgg) Rg. and for small enough >>
1. TEnIM(Px: Rg + c) 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 pxT in the same row.
2. TEBIM(Xx Rg c) is achieved as follows:
Identify the columns with the smallest and largest sums in PXT. 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 I on the right depicts an example of optimal lutions in the neighborhood of deterministic mapping. While Algorithm effectively identifies deterministic map- pings 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.
Iganna (px: R)
Pxr
+ dps
Rg
Per + dpy
Figure 2 illustrates this strategy; for px [0.7, 0.2, 0.1], identifying all 5 possible deterministic mappings is straightforward. Applying the transformations from The- orem 3 then yields various solutions across the 1-R plane (represented by dashed lines). Subsequently, one can se- lect 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 conjecture.
E2
R
Rg
Figure 1: An example for Theorem 3.
4 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: source, an agent (sender), a Markov decision process, and receiver. An MCG episode unfolds in three stages: initially, the agent receives a private message from the source, which must then indirectly convey to the receiver. Next, the agent participates in an episode of the Markov decision

---

Brute Force
Theorem 3
0.8
0.7
0.6
LEDIM (px. R)
0.1
0.2
0.0
0.0
0.1
0.2
0.3
0.1
0.5
0.6
0.7
0.8
0.0
0.1
0.2
0.3
0.1
0.5
0.6
0.7
0.8
R
R
Figure 2: Solutions to the EBIM problem for px [0.7, 0.2, 0.1]. Left: brute force solution. Right: application of the transformations from Theorem to each deterministic mapping (dashed lines) and selection of solutions with maximal mutual information for each value (thick solid line). This strategy effectively recovers optimal solutions, aligning with those found by brute force this case.
process. Finally, the receiver attempts to decode the original message based on the observed MDP trajectory. The overall reward is 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 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 rate-limited MCG as a tuple (S M, C, R). where (S, A,, T, R.) is an MDP denoted by state and action spaces, and reward and transition functions, respectively. M is set of messages, μ is the prior distribution over messages M, is 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 f4 sampled from the prior over messages the source.
2. Based on the selected message M and the history of the MDP episode, the source generates and transmits signal to the agent, adhering the rate limit R.
3. The Agent uses conditional policy Tyr, which takes current state E 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 '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 to maximize the expected weighted sum of the MDP reward and the accuracy of the receiver's s estimate ([R(2)= + Cu[M M] [22]. Optionally, If a suitable distance function exists, instead, the objective can also be adjusted minimize the difference between the actual message and the guess. A diagram of the structure MCG with rate limit is shown in Figure 3.
T
Z
M
Source
Agent
MDP
Receiver
M
A.S
Figure 3: The structure of a Markov Coding Game with Rate Limit.
7

---

4.1 Method Description
Marginal Policy Following Sokota al. [22], be- fore execution we first derive a marginal policy for the MDP, based on the Maximum-Enne -ntrrop reinforcement learning objective:
Algorithm 2 Source
1: Input: n, jt, 8
2: Observe message m ~ 1
3: Initialize message belicf pMr f-
max Ex Σ R(S (H(AI))) (14)
4: Initialize stale <- 5
5: while Source's turn do
6: PMr <- compress(pM- Rt)
The value of 33 in (14) needs to be determined in ac- cordance with the message priority [ of the MCG. Note that this marginal policy does not depend the choice of message. By introducing stochas-
7:
t ~ PT) M (m)
8:
Send to the agent.
9:
pT >m, Parr(',,
10:
PTA min_ent cot.eeennoouplnpprr..... (()))
11:
PMA + Ee Parr(,, t') Pa
ticity into this policy, we can encode information
12:
0,8 & Observe action and next state
about the message into the selection of actions at each step during runtime. For more details, see Section C.I.
13:
PM PM]a(a)
Algorithm 3 Agent
Step 1 Source:
Message Compression At the beginning of each round, given the updated mes- sage belief pM, the source compresses the message
1:
Input: 14, R, 8
2: Initialize message belicf pa f- μ
to generate the signal T, adhering to the source-
3: Initialize state f 5"
agent rate limit R, by solving EBIM in (10). The
4:
while Agent's turn do
source then transmits the signal T to the agent. Sub- sequently, after observing the action taken by the agent, the source updates the message belief for the next round. Algorithm outlines the steps taken by the source.
5:
PMT 4- comрress(pи- It)
6: Receive & from the source.
7:
Pr Σ.. Parr(,,
8:
PTA miin miin_ent_couplinggrrr a(s))
9: T[T f -PAIr(t)
10:
a ~ RiT
Step 2 - Agent: Minimum Entropy Coupling
11:
+ Commit action MDP.
12: PMA Eg pur(, (f)r(t))
As illustrated in Algorithm 3, at each round, upon receiving the signal T, the agent constructs condi- tional policy T/r by performing minimum entropy coupling between the action distribution from the marginal policy π (s) with the signal distribution pr. Subsequently, the next action is sampled from the conditional policy, a ~ Tyr. Finally, the agent updates the message belief based on the chosen action.
13: PM < (M)
Algorithm 4 Receiver
1: Input: 2, RT, μ4, 8
2: Initialize message belicf par + P
3: Initialize state &- S
4: for s,a E do
5: PMT <- cоmрreas(pM, R)
Receiver: Decoding the Message Given the agent's s final MDP trajectory, the receiver mirrors
6: pr + En Parr''m''
7:
PTA t min_ent couut_couulinggpp a(s)
the actions of the source and agent to update the message belief at each step. As outlined in Algo- rithm the process begins with the receiver com- pressing 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.
8:
PMA + Ev pur(: t') PA)T(t')
9:
PM (M]A(a)
10: return arg max,, pm (mn)
4.2 Experimental Results
This section presents the experimental results of the method described in Section 4.1, applied to Markov Coding Games. For our experiments, we utilize noisy Grid World environment for the Markov Decision Process. Section C.2 provides more detail on the environment setup used this experiment.
The marginal policy is learned through Soft Q- Qaluue iteration, as described Algorithm By increasing the value of (3 in Equation (14), we induce more randomness into the marginal policy. Consequently, higher values of 3 lead to an increase in the total number of steps taken by the agent to reach the goal, resulting in more heavily discounted reward. Conversely, as the entropy of actions at
8

---

each state is increased, there is an increase in the mutual information between the actions and the compressed message during the minimum entropy coupling each step. This dynamic establishes fundamental trade-off between the MDP reward and the receiver's decoding accuracy, through the adjustment of B. Figure shows policies learned by high and low values of B3.
We compare our proposed compression method Algorithm with baseline of uniform quan- tization. As detailed in Algorithm 5, given an entropy budget R. the input symbols are uni- formly partitioned into 2 bins, and each bin encoded with the same code.
Algorithm 5 Uniform Quantizer Encoder
Input: px; R
Output: PXT
1: <- length px
2: [2a]
partition size <- [n/m]]]
Figure illustrates the trade-off between the av- erage MDP reward and the receiver's s decoding
4: Initialize pxt as an n x m zero matrix
5:
for i + 0 m do
accuracy by varying B, using our deterministic EBIM solver in Algorithm I, and the uniform quantization encoder in Algorithm 5. Here, the compression is defined by the ratio of the message entropy to the allowed code budget (T)..
6: start +- partition_size
7: end min(start + partition size,
8: Pxr[start end, i] +- px [start end)
9:
return pxT
Deterministic EBIM Solver (Ours)
Uniform Quantizer
0.30
Average MDP Payoff
0.25
0.20
Compression Rate 1.00
Compression Rate
0.15
1.25
1.25
1.67
1.67
2.50
2.50
0.10
5.00
10.00
10.00
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Receiver Accuracy
Receiver Accuracy
Figure 4: The trade-off between average MDP reward receiver's accuracy, navigated by varying the value of B. Left: using our search algorithm for compression (Algorithm 1), Right: using uniform quantization in Algorithm 5. The message size is 512 with uniform prior, and each data point is averaged over 200 episodes.
Figure illustrates the evolution of message belief over time for various values of 8 and rate budgets. A marginal policy optimized with 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, lower compression rate permits the agent to retain more information about the message, enabling more effective encoding of information in the selected trajectory.

---

log
log
Deterministic EBIM Solver (Ours)
Uniform Quantizer
Deterministic EBIM Solver (Ours)
Unilorm Quantizer
1.0
1.0
0.8
Roceiver Accurney
Receiver Acturacs
0.6
0.6
0.4
0.4
0.0
6.0
Agent Step
Agent Step
Agent Step
Agent Stop
log
log 3
Deterministic EBIM Solver (Ours)
Uniform Quantizer
Deterministic EBIM Solver (Ours)
Uniform Quantizer
0.8
0,8
Receiver Accuraicy
Receiver
0.4
0.4
0.0
0.0
Agent Stop
Agont Step
Agont Stop
Agent Stop
Compression
Rate
10.00
5.00
2.50
1.67
1.25
1.00
Figure 5: Evolution of message belief over time, for various values of 3 and rate budget, using search algorithm for compression Algorithm vs. uniform quantization in Algorithm
5
Conclusion
We investigated lossy compression framework under logarithmic loss, where the reconstruction distribution differs from the source distribution. This framework supports joint compression and retrieval applications,
generally, cases where distributional shifts occur due to processing. We demonstrated that this framework effectively extends the classical minimum entropy coupling by incorporating bottleneck, which regulates the degree of stochasticity in the coupling.
Furthermore, we showed that separately optimizing the encoder and decoder decomposes the Min- imum Entropy Coupling with Bottleneck (MEC-B) into two distinct problems: Entropy-Boundee Information Maximization (EBIM) for the encoder, followed by Minimum Entropy Coupling (MEC) for the decoder. We conducted extensive study of the EBIM problem, provided 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 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 quantifying the gap between the separate optimization of the encoder and decoder and the optimal joint setting. Also, enabling aneeggraned control over the entropy spread in the coupling can be key in some applications. Additionally, the application of Entropy-Bounde Information Maximization (EBIM) in watermarking language models [29] suggests a valuable intersection with state-of-the- -fetttt-rtt AI applications. Moreover, extending this framework to continuous cases could lead to the design neural network architectures based on the proposed framework theoretic insights into broad spectrum of deep learning problems. These include unpaired sample-to-sample translation [30-32], joint compression and upscaling [25, 33], and the InfoMax framework [34, 35], among others.
and provide information -nformation-theorettie
10

---

References
[1] Thomas Courtade and Richard Wesel. Multiterminal source coding with an entropy-basee distortion measure. In 2011 IEEE International Symposium Information Theory Proceedings, pages 2040-2044. IEEE, 2011.
[2] Thomas A Courtade and Tsachy Weissman. Multiterminal source coding under logarithmic loss. IEEE Transactions on Information Theory, 60(1):740-761, 2013.
[3] Yanina Y Shkel and Sergio Verdú. A single-shot approach lossy source coding under logarithmic loss. IEEE Transactions on Information Theory, 64(1):129-147, 2017.
[4] Mathukumalli Vidyasagar. metric between probability distributions on finite sets different cardinalities and applications to order reduction. IEEE Transactions Automatic Control, 57 (10):2444-2477, 2012.
[5] Amichai Painsky, Saharon Rosset, and Meir Feder. Memoryless representation of markov processes. In 2013 IEEE International Symposium Information Theory, pages 2294-298. IEEE, 2013.
[6] Mladen Kovačević, Ivan Stanojević, and Vojin Šenk. On the entropy of couplings. Information and Computation, 242:369-338 -3029 2015.
[7] Ferdinando Cicalese, Luisa Gargano, and Ugo Vaccaro. How to find joint probability distribu- tion of minimum entropy (almost) given the marginals. 2017 IEEE International Symposium on Information Theory (ISIT), pages 2173-2177. IEEE, 2017.
[8] Maurice Fréchet. Sur les tableaux de corrélation dont les marges sont données. Ann. Univ. Lyon, 3 serie, Sciences, Sect. A, 14:53-77, 1951.
[9] Frank Den Hollander. Probability theory: The coupling method. Lecture notes available online (http://websites. math. leidenuniv. hllrobailttyllttueet/////ugglill CeetreeeeeeeCllnnnneeeeeeessssse pdf), 2012.
[10] Gwo Dong Lin, Xiaoling Dou, Satoshi Kuriki, and Jin-Sheng Huang. Recent developments on the construction of bivariate distributions with fixed marginals. Journal of Statistical Distributions and Applications, 1:1-23. 2014.
[11] Viktor Benes and Josef Stepán. Distributions with given marginals and moment problems. Springer Science & Business Media, 2012.
[12] Lei Yu and Vincent YF Tan. Asymptotic coupling and its applications in information theory. IEEE Transactions on Information Theory, 65(3): 1321-1344,,, 2018.
[13] Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
[14] Murat Kocaoglu, Alexandros Dimakis, Sriram Vishwanath, and Babak Hassibi. Entropic causal inference. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
[15] Spencer Compton. A tighter approximation guarantee for greedy minimum entropy coupling. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 168-173. IEEE,
2022.
[16] Spencer Compton, Dmitriy Katz, Benjamin Qi, Kristjan Greenewald, and Murat Kocaoglu. Minimum-entrre centrupy coupling approximation guarantees beyond the majorization barrier. In International Conference Artificial Intelligence and Statistics, pages 10445-10469, PMLR. 2023.
[17] Albert W Marshall, Ingram Olkin, and Barry C Amold. Inequalities: theory of majorization and its applications. 1979.
[18] Ferdinando Cicalese, Luisa Gargano, and Ugo Vaccaro. Minimum-entropy couplings and their applications. IEEE Transactions on Information Theory, 656)):3436-341,, 2019.
[19] Cheuk Ting Li. Efficient approximate minimum entropy coupling of multiple probability distributions. IEEE Transactions Information Theory, 526655995,, 2021.
11

---

[20] Spencer Compton, Murat Kocaoglu, Kristjan Greenewald, and Dmitriy Katz. Entropic causal inference: Identifiability and finite sample results. Advances in Neural Information Processing Systems, 13711477-4478, 2020.
[21] Mohammad Ali Javidian, Vaneet Aggarwal, Fanglin Bao, and Zubin Jacob. Quantum entropic causal inference. In Quantum Information and Measurement, pages F2C-3. Optica Publishing Group, 2021.
[22] Samuel Sokota, Christian A Schroeder De Witt, Maximilian Igl. Luisa M Zintgraf, Philip Torr, Martin Strohmeier, Zico Kolter, Shimon Whiteson, and Jakob Foerster. Communicating via markov decision processes. In International Conference on Machine Learning, pages 20314-20322 PMLR. 2022.
[23] Christian Schroeder de Witt, Samuel Sokota, Zico Kolter, Jakob Foerster, and Martin Strohmeier. Perfectly secure steganography using minimum entropy coupling. arXiv preprint arXiv:2210. 14889, 2022.
[24] Yochai Blau and Tomer Michaeli. Rethinking lossy compression:
The iueeddistortion-percetiinn tradeoff. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 675-685. PMLR, 09-15 Jun 2019. URL https://proceeddngg
mlr. pwwps///e/bleeeeeeeepeetee hwwp////llllaaaa 9a. html.
[25] Huan Liu, George Zhang, Jun Chen, and Ashish J Khisti. Lossy compression with distribu- tion shift as entropy constrained optimal transport. In International Conference on Learning Representations, 2022.
[26] Nicolaas Govert De Bruijn. Asymptotic methods in analysis, volume 4. Courier Corporation, 1981.
[27] Brian Skyrms. Signals: Evolution, learning, and information. OUP Oxford, 2010.
[28] Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
[29] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. watermark for large language models. In International Conference on Machine Learning, pages 17061-17084. PMLR, 2023.
[30] Phillip Isola, Jun- Yan Zhu Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. arxiv e-prints. arXiv preprint arXiv:1611.07000 1611, 2016.
[31] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexci A Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. In Proceedings of the IEEE international conference on computer vision, pages 2223-2233 2017.
[32] Judy Hoffman, Eric Tzeng, Taesung Park, Jun- Yan Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In International conference on machine learning, pages 1989-1998. Pmlr, 2018.
[33] Byeongkeun Kang, Subarna Tripathi, and Truong Q Nguyen. Toward joint image generation and compression using generative adversarial networks. arXiv preprint 1rXiv:1901.0788 2019.
[34] Michael Tschannen, Josip Djolonga, Paul Rubenstein. Sylvain Gelly, and Mario Lucie. On mutual information maximization for representation learning, arXiv preprint 17X.v:1907.13625. 2019.
[35] R Devon Hjelm, Alex Fedorov, Samuel Aavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 1808. 066700 2018.
[36] O. L. Mangasarian. Machine Learning via Polyhedral Concuve Minimization, pages 175- 188. Physica- Verlag HDD, Heidelberg, 1996. ISBN 142-9-642-9978--1. 978- 978-3-642-99789- 13. URL https::///eee wdw.i.org/o..... 1007 /
doi: 10.1007/
/978-378883 787--88-80 3-642- 642-99988-1113
12

---

[37] Michel X Goemans, Spectral graph theory and numerical linear algebra. URL http:///ww.g.g.eeoooo////////aaa
http://weer cs emu edu odt//afs/cs/uss///gllti. F-11 Btr///lllttttloooo//ooeaaa--a--e notes. .pf
Computing/
[38] F Palacios-Gomez, L Lasdon, and M Engquist. Nonlinear optimization by successive linear programming. Management science, 28(10):1106-1) 1120, 1982.
[39] Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1434 Chicago, IL. USA, 2008.
[40] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press. 2018.
[41] Kevin Hanselman. grid-world-rl, 2023.
gorl-world-r.
https://github..omm
[42] David Barber and Felix Agakov. The im algorithm: a variational approach to information maximization. Advances in neural information processing systems, 16(320):201, 2004.
[43] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. Advances in neural information processing systems, 29, 2016.
[44] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. http://yammleecu.comm htw.l//e..o/ee////meeeee 2, 2010.
[45] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, et al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop on deep learning and unsupervised feature learning, volume 201 1, page 4. Granada, 2011.
13

---

A Mathematical Proofs
A.1 Proof of Lemma 1
Lemma 1. Given a Markov chain X <+ ++
= I(x;T) (X37))-((377-777771110010
(5)
Proof. By multiple applications of the chain rule for mutual information, i.c. (A I(; CBB) we have:
I(X:Y) = ((X;
(15)
(16)
=(X;T) -
(17)
Note that from the Markov chain property, we have [(X; = 0.
A.2 Proof of Theorem
Theorem 1. TEMM (px, R) R if and only there exists function X + T such that H(g(X)) = R.
Proof. If such exists, let
(x, 1) (x((x) t= ((x)
otherwise
This joint distribution effectively sets 7 -XX). Note that pxr E M and we have ((:7)) H XT) H(g(X)) R. Since (Px, R) < R, conclude that [p R) R for pXT = Pxr Conversely, if (px, Rt) R, then there exists pxT E .M such that ((X;T) = R. Therefore
H(T) I(x;7) + X) = R + H(T)X) < R
XT) 0
As result, H(T 0 and (T) R, which means pxT defines function g such that = g(X), and (g())) = (T) = R.
A.3 Proof of Theorem
Before providing the formal proof, it is helpful to gain some insight into the structure of the solution first.
Remark 2. Let pxl- The procedure outlined in Algorithm establishes a series of deterministic Ps (n-1) (n-1) corresponding to decreasing sequence of mutual 1111 (!n-1) f(n-1)) The algorithm then picks the mapping with
(0) -2
mappings Pi
information values (1)), 1!
the maximum mutual information that does not exceed R. Therefore
R - I(X:T) & max {I(0) - 1()) (()) - ((1)
(n-1) 1) -I(0 f(a-1)]
< max (0) 10)) ( (2) (n I ((n-1))
(18)
Example. For px 10.4 0.3 0.2 0.1), Algorithm I traverses through the following deterministic mappings. from left to right:
14

---

(0)
(1)
(2)
(2)
Pi
Pi
Ps
Pt
00.4
0
0
0
T0.4
0
0
00.4
0
T0.4
0
0044
0
T0.47
T0.47
0
0.3
0
0.3
0.3
0
0.3
0.3
0
0.3
0.3
PxT
0.2
0
0.2
0.2
0
0.2
0.2
0.2
0.2
0.1
0.1
0
0.1
0
0.1
0.1
[0.1]
0.1
((X:))
H (px)
([4
3
3)
H
(17 .2
II)
H (17 3))
H (1.9
.1)
0
Definition 1. Let P' be probability distribution resulted from merging two elements > 0 and q > 0 in an original distribution P. i.e. P = -
q ...] and P I p + ..... Then,
the amount of decrease in the entropy from this merge operation is characterized by:
Au (p, 9) = (P) H (P')
(19)
1
1
log 1 p+ q 1
= =plog p
ggoog
(p
(20)
q
1 ! p
= =plog
+
+ log
(21)
Lemma 2. The following properties hold for the function Ah:
1. Aи (t -) is monotonically increasing in both arguments.
2. Аи (t, :) is concuve.
3. Ah (p, p) h(p).
Proof. The properties derived through straightforward derivative calculations:
8 AH = log(1 + q/p) 2 0, and
8
AH = + p/q) 2 0.
Bp
By
2. The Hessian of A и is negative semidefinite:
q/p 1
HA,
(22)
p p+0 q
-p/g
with eigenvalues A 0 and X2 - + P) ) <0.
3. Ah (p. 1 - p) = -plogp - (1 - p) log(1 - p) = h(p).
Theorem 2. If the output of Algorithm I yields mutual information I, then
PE R) -Ī h(p2),
(13)
where fu(-) is the binary entropy function, and p2 denotes the second largest element of px.
15

---

Proof. For the gap to the optimal objective, TEBIM (pxx R)
we have:
[PXI R) - - R-
Equation (1I)
1 (6-1) - -1000
Remark
iE(1,-,m- n-11
Algorithm Line
H Σ pt ((-1))
H Σ Σpl
(0)
rEf1,-ma-1
Definition
max
Ah
Σ
Pk Pi+1
1E(1,- n-1)
"
Lemma 2.1
max iE(I,-.,m- m-1
Ah
Σ
Pk +
E
pko P++1
k=1
k=i+2
max
Ah (1 (1-pi+1, Pi+1)
pi+l,
#E(1,"..-- a-
Lemma 2.3
h (pi+1)
(E(1,-.a-1)
Ps: Ps. Ps. 0.5
h((2))
Note that the above bound the optimality of the proposed algorithm is by means tight, does not account for the intermediate distributions ps
(e)
A.4 Proof of Theorem
Theorem 3. Let pXT denoted by |X| x IT] matrix, defines deterministic mapping T = ((X),
with (X;7) (T) Rg. We have Pxx Rgy) = Rg. and for small enough >>
1. (px Rg + +) 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 pxt in the same row.
2. LEBIM(XX: Rg c) is achieved as follows:
Identify the columns with the smallest and largest sums in PXT- Select the cell with the smallest value in the column with the lowest sum. Transfer infinitesimal probability mass from this cell to the column with the highest sum the same row.
Example. Figure 6 depicts an example of optimal solutions in the neighborhood of a deterministic mapping.
TEBINA (px. R)
Pxr
03
0.1
Pxy
dp:
Rg
dp2
Q3
83
0.1-4
R
Rg
Figure Optimal solutions in the neighborhood of deterministic mapping.
16

---

Proof. Let us view the joint distribution as a n X m matrix PXT. Note that:
px(x)
t= g(x)
(x,
(23)
0
otherwise
For example:
T0.4
0
1, I 1,2
0.3
0
0
Pxt
0
0.2
0
((x)
2,
I = 3
(24)
0
0.1
0_
3, 4
Consider a perturbation dP E IRax to PXT. need:
For PxT + dP to be valid distribution in M, we
1. d) = Vx E
2. dP(z, 20, Va,t s.t. t + g(z)
3. dP(x,t) 5), 0, Ve,t st. t == gxx)
We define the set of all such perturbations as C I Next, let us define basis perturbations Az, for # g(z) as:
- E, if x, j-= g(x) te, if x, =
(25)
0,
otherwise
Note that Ag,t represents moving a probability mass of e from non-zero cell (I. g(:)) to empty cell (x, t). For the example in equation (24):
0
0
0
0
2
-8
0
0
0
The significance of these bases is that any perturbation in Ω can be represented as:
dP
Σ
az,t Az.t:
(26)
ttg(()
with coefficients Og,t 2 0. For example:
35
+2
+5
0
2 x AI,1 + A1,2
0
0
Realizing IXT, HxT, and Hy as functions a joint distribution, we are interested in calculating the ratio dlxr/dH, with respect perturbation dP E Z as pxr. Note that since for any dP E Ωt d/ix = 0, we have:
dxx.r dHp
dHx + dHr dHx
dHx
dHç
dHp
17

---

Therefore
dlx.r
dHx, (pxt. dP)
dHf
= dHf (pxt, ddP
dHx.r
PXT. Σ
Cggt Dz,t
dllr
pXT, ΣE Oggt Az,t
E E Ond dHx, (PXT, Ax,1)
= 1 ((taaa))
(27)
ΣΣ Oxgt dHT (pXT, Ans))
x.T, (pxT, Az,1) represents the amount of change in the joint entropy, when an infinitesimal mass of is moved from (z, gz))) (z, t). More precisely, from (23) and (25):
dHx (PXT, Ae.)) = Hx.r (pxT + 22,) - Hx,r (PXT)
= =[-(px(x) =) log (x) E) - E lloge - [-px (x) log (1)
(x + +llog (x -
=px(z)log px(x) -
a
px (x))
= + O(=²) + log 8
(28)
=x The last line uses the fact that for small enough x. f(x) = a log =x= 0(29) Similarly:
dHr (PxT, Aus) = HT (pXT + Az.e) - Hr (PXT)
(pr(p((( -s) log (pr(s(x)) -s) - (pr(()) + +5) log (pr(1) + +z)
log pT (o(x)) pr (t) (tg
= (g(x)()) log pr(((x))
(t(
Pr (r(x)) - pr(l) +
pr pr(((z)) - (T( log (t +
+elog
Pr (g(x))
= e + + - - + 0 + & log
(t +e
pr (g(x))
log
PT(() +e + (
(29)
Plugging (28) and (29) back to (27), we will get:
Px(x)
ΣΣ Ozzt
E + elog
E +0(22)
dxxT
ttfa(z)
d/l
pr (g(x))
ΣΣ ant ttsta)
log (t) +
+ 0
Px(x)
ΣΣ an. log
(30)
Σ Σ az, log pr(g(z))
pr(t) +
2. 14fp(o)
18

---

where az,t is normalized by:
Outtt Σ Σ Cxrr,t In tpfa(x)
Let's focus on the limit of (30) when E + O: If there is any t E T with pr(t) = 0 and az,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:
x
if Ozzt = 0 17 s.t. pr(() = 0
dxx. dHt
lim
(31)
CE )es)) PT
if 3t ag and pr 0
For dHr O, we need to find a perturbation (i.e. coefficients az,1) that maximizes dixt/ / /dHr. From (31), this means št T with az,t > 0 and pr(t) 0.
dlx,f dHr
Σ I (t)
a = argmax
argmax a
argmaa
azit
Therefore, ΣΣ oz = which means az,t = if (1) > O. other words, we should only
PT (1)-0
consider perturbations where masses are moved to all-zero columns. Continuing (30):
dxx,r
a = argmax
dHr
(x(x) Px (x)
ΣΣ Tz,t log 2 po
E
argmax
pr (g(x))
Σ Σ Cr,t log (t))=0
-log + Σ Σ Te, lxg
argmax
1
-log + Σ Σ az log PT (g(z))
pr((0)
az,t log Pr(g(z)) px (x(x)
ΣΣ Σ
argmax
log E
(t)+)
Thet log Px(x) pr (g(z))
ΣΣ
argmin
This is achieved by selecting
1. argmin Px(x')
and pr (t)
pr pr(g)())
(32)
0,
otherwise
In other words, first, normalize columns in pxT by their sum, then move infinitesimal probability mass from the cell with the smallest normalized value to an all-zero column. It easy to confirm that dHr > 0 for such perturbation. For the example distribution in (24):
0.4
0.3
0
0
PXT + dP
(33)
0.2
0
0
0.1
0_
19

---

On the other hand, for dHr < O, we need to find perturbation (i.e. coefficients az,tt) that minimizes dlxt /rr/ From (31), this means az,t for all t T that pr(t) 0. Therefore, as (30):
dlx.r dHr
a argmin
Px (x
Σ
Σ Unet log
argmin
PT (g(x))
Σ Σ ag, log
(T(()
txg((n)
llog + ΣΣ axt (xg
argmin
(gg(a)
Pr (g(x))
EE Oz, log
(t
ttt(())
Oz,t log pr(g(z)) Pt
ΣΣ (ta(s)
argmin
This is achieved by selecting
1, x = argmin prgmainp(ggz"))) and = argmax pr
Ozz,
(34)
0,
otherwise
In other words, moving an infinitesimal probability mass from the smallest column to the largest column of pxr. It is easy to confirm that dH1 0 for such perturbation. For the example distribution (24):
00.4
0.3
0
0
Pxt + dP
(35)
0
0.2
3
0
0.1
-
0
B Minimum Entropy Coupling
Consider two discrete random variables X and Y, over alphabets X' and y with probability mass functions px and py, respectively. The goal of minimum entropy coupling is find the joint distribution pxy that minimizes the joint entropy H(X,Y)
min H(X;Y) pxy
Σ Cxx (2, =xxx))px(x) Vr e X,
s.t.
(36)
yEy
= Σ Pxy (x) (v) Vy xEX
This is a concave minimization problem over standard polyhedron [36]. Therefore, every vertex of the polyhedron is local minimum and the global minimum happens at subset of the vertices.
Note that an standard polyhedron defined as P (ar R. Ax b, x 2 0), where E mRmx zero elements
with linearly independent rows. A point xt E P is vertex if and only if it has and columns of corresponding to other m non-zero elements are linearly independent. Hence, to exhaustively iterate all the vertices:
20

---

1. Choose m linearly independent columns Ar(1)." Ar(m)-
2. Let a; 0 for all =((), (m)
3. Solve the system of equations Ax - b= O for the unknowns 2x (1), "n (m)
Therefore a crude upper-bound on the number of vertices would be (*) This can be enhanced to (mm/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 NP-Hard. Given an optimization problem, a decision version whether or not any target value & is achievable. Without the loss of generality, assume |x| > [3%]_ We set t = HY),, i.e. to decide if there exists function f Deterministic Matching.
y such that Y f(X). Let's call this problem
Next, we show any instance of the k-Subset-Sum problem can be reduced an instance of Determin- istic Matching, by a polynomial-ting procedure (denoted by the notation <p). Consider a general instance of the k-Subset-Sum problem: Given set S of integers and target values {4:[1
S k). decide if there exists a partition {S < s k} of size i on S such that Σ S; t; for all 1 S S k. Now, set px (i) st/ E(s). Vs, E S and (i) t t [tz). Then, clearly solving Deterministic Matching for Px, Py will solve the original k-Subset- Sum problem. Therefore, k-Subset-Sump <p Deterministic Matching and hence, Deterministic Matching 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 cou- pling problem, and numerically compare their achieved minima to a general approximate algorithm.
Algorithm 6 Max Mlxx-Seeking Minimum Entropy Coupling
Input: marginal distributions px, PY Output: joint distribution pxy
1: pxy v) +- O, Va,y E N,
2: while Py * do
3:
argmax, px (x(x)
4:
V" + argmax, py (v)
5:
pxy(=', ,y") min (xx" (, pr (y²))
6:
px(x") -xi==))min(pxx (2) (y"r
7:
py("") < py py (px (x ). (3"
8: return pXy
Algorithm Zero-Seeking Minimum Entropy Coupling
Input: marginal distributions px, PY Output: joint distribution pxy
pxy(2,)) v) +- 0, Ve,y y E X
2: while px * 0 do
3:
(w","") )² t- argmin,, (x) py(v)
4: Pxy (x",") yy)
min(pxx (x ), py (y²))
5:
px (x") <- px px(x") min (ox(pxxx"))) (x"), (y"))
6:
py("") <- (y min(px (x py
7:
return PXY
At each step, each algorithm selects 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-sceking version targets the symbols with the largest remaining probability mass
21

---

at each step, whereas the zero-seeking version pairs symbols with the most similar probability mass. Furthermore, the greedy algorithm described by Kocaoglu et [14] resembles the max-seeking version outlined in Algorithm 6.
As simple baseline, randomly generated 100 pairs of joint distributions and fed them greedy solvers. We also used general concave minimization method, Successive Linearization Algorithm (SLA) [38], and compared the achieved joint entropy. Table summarizes the average joint entropy over 100 trials for each method.
Table Minimum Entropy Coupling: average achieved joint entropy of 100 simulations of marginal distributions.
Name
Entropy
Independent Joint
5.443 + 0.101
SLA
3.225 + 0.141
Max- Max-Seeking Greedy
2.946 + 0.064
Zero-Seeking Greedy
2.937 0.058
C Markov Coding Games
C.1 Backgrounds and Notations
Markov Decision Process MDPs represented by the tuple notation (S,A, T), where S is the state space, A denoteds the action space, R : S x A + IR defines the reward function, and S A + P(S) represents the transition function. The way agent interacts with an MDP is determined by its policy π S + ((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 2 = (su. .g...., The notation R(2) Σ: 7 R(s at) is used represent the total rewards accrued throughout sequence. The primary aim of an MDP is to devise policy that maximizes the expected cumulative reward [=]
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 objective
max E Σ R(S., A.) (H.(.)).)
(37)
serves as 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 3. A generalization of the Q-value iteration method for maximum-entrop RL objective (also known as soft Bellman equation [40]) shown Algorithm
Algorithm 8 Soft Q-Value Iteration
1: Input: MDP, 9
2: Initialize: To any policy
3:
4: repeat
5:
Qit1 (s,a) R(s,a) a) + E., Pr(s'(s, iaax Qin aa)
6: i i+i+1
7:
until a)) 2 a) Se
8: Extract policy: Tgrenty (.1s) softmax (Qintss, 1V3)
The soft maximum operator defined as max Q(s,a) = Blog E. exp (lian)
22

---

C.2 Environment Setup
For our experiments, we utilize simple environment known as Grid World, for the Markov Decision Process. In this setup, the agent is placed on an 8 x 8 grid and, at each step, can move left, right, up, navigate from the starting cell the goal cell
and down. The primary objective for the agent to receive a reward of 1, while avoiding trap cell with reward of -1. Also, the environment is noisy; even if the agent decides to move a specific direction, the environment might, with certain noise probability, force move in direction 90º off the intended path. The rewards received are discounted by factor of 0.95. Finally, the receiver has decode a message, uniformly chosen from an alphabet of size 1024, given the final trajectory of the agent. Figure 7 illustrates the Grid World used this experiment and depicts a trajectory taken by the agent. The environment used in the experiments is forked from the implementation of Hanselman [41].
0.000
0.00
51.01
-0.00-0000000000000
9.00
1.00
0.00
15.00
[0:00
00:00
[6.00
0.00
0.07
0.17
1000
0.00
0.00
[6.00
6.000
6.90
5.00
6400
[5.9
0.00
0.00
1:000
[5.00
0.:00
0.00
[0.00]
0.000
[0.00
0.00
[6:00]
68:57
+00.00
0.00
0.000
[0:48
[0.00]
0.00
(0.00)
|0.00
0.00
0.00
[E:7
0.00
[6.00
8:83
0.00
[6.00
10:00
0.01
6.69
9.00
100
0.00
0.00
[0:00]
0.00
0.00
[0.00]
0.00
[0.00]
88
[6.00]
[5:46]
0.00
[0.00]
[0.21]
-0.00-
[0.00
11:00
0.00
0.00
0.00
0.01
|0.00]
[.54
0.00
0.00
0.000
0.00
0.00
6.00
0.00
[..00
(..22)
0.00
10:00
0.12
[0.00]
[.000]
8088
[6:48]
[125]
6.STT
10:0
0.00
[0.00
0.08
0.00
0.32
00.00
0.55
0.00
0:80
0..00
0.00
0.00]
0.00
0.03
0::00
0.00
0.00
0.00
0.50
6.00
1000
0:87
0.57
[0.38
0.21]
[0.00
0.01
0.00
[6.00
8.18
0.00
0.43
0.00
3.64
0.00
6.78
6.00
08
0.00
0.90
0.00
[0.00]
10:00
0.00
[0.00]
0.000
[0.00
0.01
Figure 7: The Grid World Setup used in the experiments. The starting cell depicted by red circle, while the goal, trap, and obstacle cells are colored green, red, and grey, respectively. Additionally, non-deterministic policy is demonstrated through the probabilities of actions each direction within each cell. The path taken by the agent is traced in black. Note that due to the noisy environment, the agent may move directions not explicitly suggested by the policy.
The marginal policy is learned through Soft Valuu iteration, described in Algorithm 8. By increasing the value of in Equation (14), we induce more randomness into the marginal policy. Figure shows two policies learned by high and low values of B.
23

---

log | 6
log 9
5,00
5.00
5.00
8.28
0.:5
5.00
8.17
5:00
1394
1356
8.96
0336
0.94
0.20 KLCB
0.00 808
10.59 8888
0.00 1025
10.59 0.95
8100 K0E5
B29 8:9
1:28 0:33
0228 1222
1311 818
6388 B00
108 800
2.00
2.00
2.00
2.00
8.00
2.00
0:26
0.25
0.28
0.26
0.98
0.00
0.28
0.38
B:4
5:00
B08
100
5.0
1335
8:91
13:55
0336
0.99
8.177
0.66
0.20 KLCS
8858 0.95
8188 K0.53
0.02 K0C1
10.59 0.30
0.22 KLCS
1100 0.35
1:29 1:29
0.29 E25
1:29 1:29
1:28 834
0.28 6222
530 8:21
0.21 1034
2.00
8.00
2.000
2.00
8.00
2.00
5.00
0.26
0.28
0.25
0.36
0.96
0.39
0.86
8.28
18.85
8:8
B158
8:99
5-00
B00
888
1336
8.91
1335
8.91
0335
0.99
0.99
0.20 K0C5
8012 0.30
0448 10:3
0028 0.33
0100 K0ES
0.02 10:3
1027 0.30
1229 129
0:29 E25
1229 1:29
029 E25
529 1:29
529 829
029 122
2.00
8.00
2.00
8.00
2.00
7.00
8.00
0.25
0.98
0.25
0.98
0.25
0.26
0.20
8.28
13.88
100
BM0
8:88
5:21
5.88
5:01
1336
8.91
0336
8.91
0356
0.91
0.35
0.25 K055
0.13
0.35
0443
10:3
838
0.35
1023
821
0.35
088
10:5
5:2
829
0229 E25
522 122
0.29
E25
529 029
029 B25
529 1:29
2.00
8.00
2.00
8.00
2.00
5.00
2.011
0.26
0.98
0.26
0.20
0.25
0.28
0.25
2
Figure 8: The Maximum Entropy policy learned through Soft Q-Value iteration of Algorithm 8, for log 3 -6 (left) and log 3 -3 (right).
D Additional Experimental Results
D.1 Deterministic EBIM Solver Shkel et al. (2017)
As discussed in Section 2, our proposed search method in Algorithm is compared with the encoder from Shkel and Verdá [3]. Our formulation directly imposes entropy constraint 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 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].
(n = 200, p = 0.5)
TruneatedGeom(1 100, p 0.1)
Ours
Ours
Shkel, et al. (2017)
Shkel, (2017)
Mutual Information
Mutual Information
2
0
2
0
2
Rate
Rate
Figure 9: Obtained I(X:T) vs. maximum allowed (T') for Binomial (left) and Truncated Geomet- ric (right) input distributions.
24

---

D.2 Visualizing Couplings from MEC-B
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-Bounder Information Maximization (EBIM) in (10). This 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 size 30. For EBIM, we only search for deterministic map- pings using Algorithm I, while for MEC, we employ the max-secking 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 (X) to the allowed code budget H (T)) Greater compression rates observed lead to larger entropy couplings; moving from completely deterministic mappings to increasingly stochastic ones.
Compression
Compression 1.10
Compression
Compression Rate:
0.080
10
20
25
0.025
Compression Rate: 1.40
Compression Rate: 1.50
Compression Rate: 2.00
Compression Rate: 3.00
40
01.000
10
X
12
0.015
Compression Rate: 4.00
Compression Rate: 5.00
Compression Rate: 10.00
Compression Rate:
00.010
10
00.05
30
25
30
01.000
10
15
20
25
30
5
10
15
20
25
30
15
20
25
30
25
Figure 10: Generated couplings in MEC-B formulation (2), for uniform input and output distributions. The compression is defined as H (X)/R. Higher compression rates lead more stochastic couplings with increased entropy.
25

---

E Unsupervised Image Restoration
This section introduces a preliminary formulation and initial results for a joint image compression and upscaling task, intended to illustrate practical application of our proposed MEC-B framework and to suggest potential avenues for future research.
We consider two unpaired datasets, Dx and Dy, which contain low-resolution and high-resolution images, respectively. Because the datasets are unpaired, there is no direct correspondence between specific low-re oow-resolution image in Dx and high-resolution image in Dy. In this setup, the task requires compressing a low-resolution image X into a compressed representation T,, and then reconstructing 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]:
I(X (X) H(
(38)
(X(X) Eynoy
E Ex- [xogxx [xle)]]
(39)
= -X(X) + Byroy
E (x-pxir( [log 9, (x1g)) + DeL. (19)
(40)
2 H(X) Eyror
(xppxIv [log (
(41)
Using the Lemma 5.1 from Chen et al. [43], we have:
I(X;Y) 2 ((X) + E Eyypr (Empxir [log gr (+lw))
(42)
= ((X + E Ex-px (xprix [log g, (x]())
(43)
In practical terms, by training the network to model the degradation process Y + X and recon- structing from ÿ. we maximize lower bound the mutual information [(X; Y). Simultancously, we enforce the output distribution constraint py via an adversarial loss from a discriminator dp- The total loss is therefore composed of an information loss and adversarial loss, L Linto XLadv- Figure 11 illustrates a block diagram this framework. Note that we use deterministic encoder fo that outputs the quantized code T, while the generator remains stochastic due the addition of noise z.
~
Discriminator
adv
dp
X Px
Encoder fo
T
Generator 94
Z (..0).0))
Reconstructor
Linfo
Figure 11: Block diagram of the unsupervised image restoration framework.
Figures 12 and 13 present sample output results after training the networks achieve 4 4x-ussaliing 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. YY = l(X; f())). This implies that the objective function invariant 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.
26

---

code bits/dim
16
C
D. 0 0 00
0
000000000 0 000 0 00000000
0
L
3 S 2 23233333
3
23233 3343331
3 3
33333333320
9 9
$ 006666666660
4 6660
666666666
17227727
8 14088792
1088899/183810 18588822 0015837888900 58852827
3888888888
187881880
88888888
17117877
899189988888
OO 0 2
code dimension
0000000
OO 000000032
00000000
11
f L LZ
I
L
L L
2 2 2 2
22 2 A ARAAA222T
A 2 4 3
2
2 4. 222242222
4.
3 333333333 3333333
3333333333
3 333333333
# #
9 W
5. (
65 0546144660 5 S 5
1211 1177111177777777770007
19368180 PMP888T2 1
198888898888111
38178372 199991922 117777 9 9 19918994
R 999999999
19117999
00630013
8 é
O 0OOD0O
DODD
O 0O00000
11/1/
//
/ / /
/
I //
I / / I
1 1224222
2 2.
A 4
2 2
2 2 2
2351333
4 S 33
3 3 3
3
3 5 3
S 3 3 3
3
M775999 3 V
4
4
A L 4
4
4
S
S
6 6.666 6 1
6 4666660
6
8 27
8 17477997
9 9
8
Figure 12: Output samples from the MNIST dataset, for different number of code dimensions and the number of bits per dimension of the code.
Y
Y
30
20
0
0
004
0
30
X
10
10
10
1
2
2
23
2
2
2
2
27
2
75
3
2
3
5
34
3
6
3
2
3
3
4
04
4
4
8
4
4
4
8
5
15
15
X
5
5
5
5
5
5
06
6
66
6
6
4
6
06
6
66
6
6
7
7
17
70
7
5C
7
70
74
08
8
18
88
8
98
8
18
367
88
8
9
69
9
9
Figure 13: Input and output samples from the SVHN dataset.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately reflect the paper's contributions: the development of novel lossy compression framework, its decomposition into two problems, and an extensive theoretical study alongside experiments with Markov Coding Games.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors encouraged to create 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 few datasets with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tex system might not be used reliably provide closed captions for online lectures because it fails 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 fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
28

---

Answer: [Yes]
Justification: Complete proofs of theorems and lemmas are provided in the Appendix, Section A.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Algorithms for all methods clearly presented in the manuscript, ensuring readers can understand and implement the processes discussed. Furthermore, all codes required to reproduce the results are included with this submission.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
29

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The submission includes the codes used generate the results presented in the paper. Additionnlly, a README. md file accompanies these codes, offering detailed instructions how execute them, along with an example guide users.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
ioc for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https: cnips.cc/public// wwwpc//ggg///e/eeee /CoeeSubmmbbm ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The Appendix Section C.2 provides detailed information and examples on setup used for the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Figure compares the average MDP reward and receiver accuracy, averaged over 200 episodes. The experiment demonstrates the trade-off between the two factors by varying the parameter B. Since the focus is on illustrating this specific relationship. variations due to exogenous parameters such as train/test splits, initialization, or random parameter settings are not relevant and thus not displayed.
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall 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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments performed in the paper are not computationally demanding. The runtime for the experiments on Markov Coding Games is mentioned in the Appendix Section C.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't ' make it into the paper).
paper (e.g., preliminary or failed experiments that NeurlPS Code of Ethics https https://meet /ttp://///eeiip/eeeeeee hwtpp///llc...ccccccceeeeeeeleee
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification:
The research conducted in the paper conforms with the NeurIPS Code of
Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
31

---

Justification: The paper focuses on the theoretical analysis of novel lossy compression framework specifically for discrete alphabets and does not extend to public-facing appli- cations at this stage. As the method developed is foundational piece of research, it is not yet applicable to scenarios where societal impacts poiissvve or pegative-coute 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 No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymenn 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
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)?
Question:
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 models that carry 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 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators 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]
32

---

The paper properly credits the creators and original owners of all assets used, including codes.
Justification:
Guidelines:
The answer NA means that the paper does 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 used and, possible, include 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.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithce twhoode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- e-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 's creators.
13. 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 release new assets.
Researchers should communicate the details 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. 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 details about compensation (if any)?
Answer: [NA]
Justification: This research did not involve any crowdsourcing experiments studies with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion 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 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
33

---

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 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 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 the institution conducting the review.
34


Reviews:
[{"review_id": "sCQRhUM2dK", "reviewer": "Reviewer_vk4R", "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.", "questions": "* In terms of real-world impact, could the authors further elaborate how their EBIM algorithm would contribute to robust watermarking approaches?", "limitations": "The authors discuss limitations adequately.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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. \n\n## Minor\n\n* in equation (1), R is not yet defined", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">in equation (1), R is not yet defined\n\nThank you for pointing this out. We have fixed this and introduced R before presenting equation (1).\n\n>In terms of real-world impact, could the authors further elaborate how their EBIM algorithm would contribute to robust watermarking approaches?\n\nWe consider the proposed formulation of MEC-B as a general setting that extends and encompasses multiple frameworks:\n\n- Minimum Entropy Coupling: The framework can be viewed as an extension of the well-known minimum entropy coupling framework, incorporating a bottleneck. This involves generating couplings with minimized entropy greater than a certain lower-bound, allowing for controlled entropy in the generated couplings.\n\n- Lossy Compression Setup: Another perspective on this framework is a general lossy compression setup with distributional shift and log-loss as the distortion measure. From this viewpoint, the framework can encompass applications such as joint compression and retrieval.\n\n- Markov Coding Games (MCG): We discussed an extension of  Markov coding games with bottleneck, which involves sequentially embedding a coded message in the choice of actions of an agent interacting with an MDP. MCG is a general framework that includes scenarios like referential games.\n\n- Watermarking: Similar to Markov Coding Games, where a message is embedded sequentially in the actions of an agent, watermarking involves embedding a message in tokens sampled autoregressively from a language model. Thus another potential application is watermarking LLM-generated text by generating couplings between the output token distribution of the language model and the information message.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BveKSLeLZ6", "reviewer": "Reviewer_Enxp", "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.", "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": "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.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">the full MEC-B problem is left open, while special cases of it have been solved\n\nOur approach involves decomposing the full MEC-B problem into two subproblems: EBIM and MEC. By optimizing the encoder and decoder separately, we can reconstruct a solution to the full MEC-B problem. First, we optimize the encoder by solving EBIM between the input and the code. Then, given the resulting marginal distribution $p_T$​ on the code, we optimize the decoder by solving a minimum entropy coupling between the code and the output marginals. We acknowledge that joint optimization of the encoder and decoder presents an important direction for future research.\n\n>The restriction to discrete alphabet settings is also a limitation of the approach\n\nThe current work focuses on the case of discrete alphabets to establish foundational grounds and provide insight into this problem. Formulating the continuous case involves additional considerations, which is a direction for future research. We will briefly discuss why the continuous setting requires a revised formulation:\n\nFirst, note that under the current formulation, we need to keep the code discrete. We cannot simply replace entropy with differential entropy since, in general, we will have $I(X;Y)=\\infty$. On the other hand, for the case where $X$ and $Y$ are continuous but $T$ is discrete, the optimal solution can be easily found as follows:\n\nGiven the rate constraint $R$, we fix any (discrete) marginal distribution on $T$ with $H(T) = R$. Next, since $X$ is continuous, a deterministic conditional $p_{T|X}$ can be trivially found by partitioning the domain of $X$ according to $p_T$, i.e., finding $(-\\infty, x_1), [x_1, x_2), \\cdots, [x_n, \\infty)$ such that $P(X \\in [x_{i-1}, x_{i}]) = P(T = i)$. (A similar argument can be inferred from Theorem 2, where in this case we have $h(p_2)=0$.) Similarly, the conditional $p_{T|Y}$ can be found in the same way, allowing $p_{Y|T}$ to be computed. It is easy to see (from Lemma 1) that $I(X; Y) = R$, which is the optimal value for the MEC-B objective.\n\nA potential approach to address these challenges is to replace information measures $I(X;Y)$ and $H(T)$ by information dimension measures so that the relevant quantities do not equal infinity. In this new formulation, compression takes the form of dimension reduction. We will include a discussion on this topic in the updated version of the paper.\n\n>(1) provide some orders of magnitude assessments for the mutual information relative to the gap...\n\nWe would like to point out that the gap stated in Theorem 2 does not exceed one bit, i.e., $h(p_2) \\leq 1$, with equality occurring with $p_X = [0.5, 0.5]$. While the gap is capped at one bit, the maximal mutual information in the EBIM formulation will be on the order of magnitude of $R$. Therefore, the most natural interpretation of the gap occurs in the higher rate regimes. Additionally, the gap in Theorem 2 will be small when $p_2$​ is small, i.e., in scenarios where the input alphabet size is large and the distribution is not skewed towards a few elements.\n\n>(2) The receiver receives a full trajectory of the MDP. This means that the algorithm is an offline MDP setting. Is this correct?\n\nTo clarify, before the execution of the Markov Coding Game, the marginal policy is learned using Maximum-Entropy RL objective. Beyond this, there is no limitation on the type of RL used; it can be conducted either online or offline. In the execution phase, as mentioned, the receiver needs access to the full trajectory of the episode. This can be achieved offline, where the receiver obtains the full trajectory at the end of the episode, or online, where the receiver observes the current action and state at each step along with the agent, and updates its belief on the message accordingly. In this regard, we consider the MDP to be fully observable. An extension based on partially observable MDPs could be considered, though it is outside the scope of this paper.\n\n>(3) What are the computational costs of the algorithm proposed?\n\nAlgorithm 1 has $\\mathcal{O}(n\\log n)$ time complexity, where $n$ is the cardinality of the input alphabet.\nThis is because the main loop of the algorithm runs for at most $n$ steps, and finding min/max elements can be done in $\\mathcal{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.\n\n>(4) distributional shift is motivated in the Introduction but received little discussion later on...\n\nWe would like to clarify that the notion of distributional shift is mathematically treated in the formulation of our main problem, MEC-B. As stated in Eq. (2), we allow input and output distributions to differ, accommodating the distributional shift. On the other hand, the proposed EBIM problem in Equation (4) is intended as a subproblem and special case of the main proposed formulation, designed to optimize the encoder within the MEC-B framework.\n\n>a recent line of work on rate-perception-distortion (Blau and Michaeli) ...\n\nWe thank the reviewer for their insightful suggestion. We'd like to highlight the following points to draw a high-level comparison between the two frameworks:\n\n1. The RDP framework of Blau and Michaeli does not fix the output distribution but instead imposes a softer perceptual constraint on the generated outputs. Additionally, our work incorporates an entropy constraint on $T$ as a rate bottleneck, whereas in Blau and Michaeli’s formulation, $I(X; Y)$ can be interpreted as the rate bottleneck.\n\n2. In this line of work, [25] is the closest to our approach in spirit, as the authors consider a hard output distribution constraint while incorporating a bottleneck. However, that work mainly considered squared error distortion, and their mathematical machinery is quite different from our work.\n\nWe will include a discussion in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CxMvtucyH4", "reviewer": "Reviewer_mDET", "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.", "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 )\n\nIs decoder collapse actually an issue? If (1) is actually the problem of interest, what makes the identity decoder undesirable?", "limitations": "Have the authors adequately addressed the limitations\n\nYes.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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.\n\nThe 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.\n\n---\n\nAs a general comment, using number citations as proper nouns is bad practice: \"[30] explores a single-shot lossy source coding setting\nunder 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.\"\n\n---\n\nThe 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.\n\n---\n\nI 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)$.\n\n---\n\nWriting:\n\nLet pXT denoted by a |X | × |T | matrix, defines a deterministic mapping T = g(X), with I(X; T) = H(T) = Rg.\n\n---\n\n> 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 .\n\nBoth 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.\n\n---\n\n> Marginal Policy Before execution, we first derive a marginal policy π for the MDP, based on the Maximum-Entropy reinforcement learning objective\n\nThe submission should probably attribute this high level approach to [32].\n\nThe submission should probably also explain more generally how Algorithm 2, 3, 4 extend the approach of [32].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">paper … [6] shows that [21]'s algorithm achieves within 𝑙𝑜𝑔2(𝑒)≈1.44  bits of optimal entropy for n variable coupling and  𝑙𝑜𝑔2(𝑒)/𝑒≈0.53  bits of optimal entropy for 2 variable coupling, which are stronger guarantees than that stated above.\n\nWe thank the reviewer for pointing this out. Upon further review, it appears that in [4] this bound is improved to $\\log_2(e) ≈ 1.44$ bits, while in [6] it is further refined to $\\log_2(e)/e ≈ 0.53$ bits for two distributions and $(1 + \\log_2(e)) / 2 ≈ 1.22$ bits for any number of distributions. We will incorporate these updates into the related work section.\n\n>As a general comment, using number citations as proper nouns is bad practice…\n\nThank you for the feedback. We will correct this in the final version of the paper.\n\n>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.\n\nWe appreciate the connection to this work and will include a discussion of this paper in the related work section of our revised manuscript.\n\nThe deterministic EBIM solver in Algorithm 1 addresses a more general version of the problem discussed in the referenced work.  Specifically, while the referenced work aims at finding $\\max_f H(f(X))$, the deterministic EBIM solver in Algorithm 1 provides a greedy approximation for $\\max_f H(f(X))$ with $H(f(X)) \\leq R$. Additionally, the NP-hardness proof provided in this work can help demonstrate the NP-hardness of the EBIM problem.\n\n>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 𝑝𝑠(1) when we would prefer it to return diag(𝑝𝑋).\n\nThank you. We fixed this in the manuscript by adding the following check before the main for loop:\n\nif $R \\geq H(X)$ then   \n$\\quad$ return diag($p_X$)\n\n\n>Both this statement and the subsequent statement (2) [in thm 3] 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.\n\nWe have revised the statements in Theorem 3 for increased clarity:\n\n1. $I_{EBIM} (p_X, R_g + \\epsilon)$ is attained as follows:\nNormalize 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.\n\n2. $I_{EBIM}(p_X, R_g - \\epsilon)$ is achieved as follows:\nIdentify 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.\n\nTo clarify, in (1) we select the cell with the smallest column-normalized value among all cells. \n\n>”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].\n\nWe updated the manuscript throughout Section 4 to clarify that the high-level approach presented in Section 4.1 follows the work of [32], where MCG is introduced. We would like to point out that we have extended the method in [32] by adding a bottleneck between the source and the agent. In [32], the agent fully observes the message, while in our extension, the source first compresses the message using the EBIM formulation, and the agent only observes this compressed message. The agent and receiver’s algorithms have been updated accordingly to encode and decode the compressed message.\n\n>Is decoder collapse actually an issue? If (1) is actually the problem of interest, what makes the identity decoder undesirable?\n\nThe 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. Additionally, we would like to point out that the special case of an identity decoder is essentially the EBIM problem, which has been thoroughly investigated in the paper as a subproblem of the general framework.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for their positive evaluation of our paper. We appreciate their thoughtful and constructive feedback. We have addressed their comments in detail in the responses provided below.

Meta-review: 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.
Decision: Accept (spotlight)