Minimum Entropy Coupling with Bottleneck
Authors: name: M. Reza Ebrahimi, name: Jun Chen, name: Ashish Khisti

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 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-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 illustrate 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 highlight the trade-offs between MDP rewards and
receiver accuracy across various compression rates, showcasing the efficacy of
our method compared to conventional compression baseline.