Research map / Learning theory and algorithms / Prediction and decision losses
Minimum Entropy Coupling with Bottleneck
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Minimum Entropy Coupling with Bottleneck (MEC-B) under log-loss, decomposes it into an entropy-bounded information maximization encoder problem and a minimum entropy coupling decoder problem, and applies the framework to rate-limited Markov Coding Games.
Problem
Lossy compression where the reconstruction distribution must match a target output marginal while the code entropy is bounded; the joint problem of encoder and decoder under log-loss is hard, and the naive optimum collapses to identity decoding without an output marginal constraint.
Approach
Formulate lossy compression under log-loss as maximizing I(X;Y) with a code entropy bottleneck and fixed output marginal; lower-bound it via a Markov-chain decomposition into EBIM (encoder) and MEC (decoder), and give a greedy deterministic EBIM solver with a provable gap of h(p_2) bits plus local optimality results near deterministic mappings.
Key results
- Deterministic EBIM greedy solver guarantees a gap of at most h(p_2) <= 1 bit from the optimal mutual information.
- For p_X=[0.7,0.2,0.1], the transformation-based strategy recovers the brute-force optimal solutions for all rate values R.
- In the rate-limited Grid World MCG (message size 512, 200 episodes), varying beta traces a reward vs. receiver accuracy trade-off, compared against uniform quantization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Max-Seeking Greedy instead of SLA | Minimum Entropy Coupling · Random marginal-distribution pairs (100 simulations) | joint entropy: 3.225 ± 0.141 -> 2.946 ± 0.064 | Helped |
| Use Zero-Seeking Greedy instead of SLA | Minimum Entropy Coupling · Random marginal-distribution pairs (100 simulations) | joint entropy: 3.225 ± 0.141 -> 2.937 ± 0.058 | Helped |
| Use Max-Seeking Greedy instead of Independent Joint | Minimum Entropy Coupling · Random marginal-distribution pairs (100 simulations) | joint entropy: 5.443 ± 0.101 -> 2.946 ± 0.064 | Helped |
| Use Zero-Seeking Greedy instead of Independent Joint | Minimum Entropy Coupling · Random marginal-distribution pairs (100 simulations) | joint entropy: 5.443 ± 0.101 -> 2.937 ± 0.058 | Helped |
| Increase the maximum-entropy RL temperature β | Rate-limited Markov Coding Game · Noisy Grid World | receiver accuracy | Helped |
| Increase the maximum-entropy RL temperature β | Rate-limited Markov Coding Game · Noisy Grid World | MDP reward | Hurt |
| Lower the compression rate | Rate-limited Markov Coding Game · Noisy Grid World | receiver accuracy | Helped |
Limitations
- Optimality of combining deterministic-mapping search with local transformations is only conjectured for general alphabets.
- Separate encoder-decoder optimization is a lower bound proxy; the gap to the joint optimum is not quantified.
- Experiments are limited to a small noisy grid world with a uniform prior.
Experimental setup
Benchmarks: noisy Grid World Markov Coding Game
Metrics: average MDP reward receiver decoding accuracy mutual information joint entropy
Baselines: uniform quantization successive linearization algorithm independent joint coupling
Builds on: minimum entropy coupling maximum-entropy reinforcement learning Markov coding games
Closest papers by meaning
- List-Level Distribution Coupling with Applications to Speculative Decoding and Lossy Compression (NeurIPS 2025 · similarity 0.86)
- Accelerating Relative Entropy Coding with Space Partitioning (NeurIPS 2024 · similarity 0.86)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.84)
- MeLLoC: Lossless Compression with High-order Mechanism Learning (NeurIPS 2024 · similarity 0.84)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.84)
- Entropy-informed Decoding: Adaptive Information-Driven Branching (ICML 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.