Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.19540 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929365841870848 |
|---|---|
| author | Sokota, Samuel Sam, Dylan de Witt, Christian Schroeder Compton, Spencer Foerster, Jakob Kolter, J. Zico |
| author_facet | Sokota, Samuel Sam, Dylan de Witt, Christian Schroeder Compton, Spencer Foerster, Jakob Kolter, J. Zico |
| contents | Minimum-entropy coupling (MEC) -- the process of finding a joint distribution with minimum entropy for given marginals -- has applications in areas such as causality and steganography. However, existing algorithms are either computationally intractable for large-support distributions or limited to specific distribution types and sensitive to hyperparameter choices. This work addresses these limitations by unifying a prior family of iterative MEC (IMEC) approaches into a generalized partition-based formalism. From this framework, we derive a novel IMEC algorithm called ARIMEC, capable of handling arbitrary discrete distributions, and introduce a method to make IMEC robust to suboptimal hyperparameter settings. These innovations facilitate the application of IMEC to high-throughput steganography with language models, among other settings. Our codebase is available at https://github.com/ssokota/mec . |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19540 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Low-Entropy Couplings for Large-Support Distributions Sokota, Samuel Sam, Dylan de Witt, Christian Schroeder Compton, Spencer Foerster, Jakob Kolter, J. Zico Information Theory Cryptography and Security Minimum-entropy coupling (MEC) -- the process of finding a joint distribution with minimum entropy for given marginals -- has applications in areas such as causality and steganography. However, existing algorithms are either computationally intractable for large-support distributions or limited to specific distribution types and sensitive to hyperparameter choices. This work addresses these limitations by unifying a prior family of iterative MEC (IMEC) approaches into a generalized partition-based formalism. From this framework, we derive a novel IMEC algorithm called ARIMEC, capable of handling arbitrary discrete distributions, and introduce a method to make IMEC robust to suboptimal hyperparameter settings. These innovations facilitate the application of IMEC to high-throughput steganography with language models, among other settings. Our codebase is available at https://github.com/ssokota/mec . |
| title | Computing Low-Entropy Couplings for Large-Support Distributions |
| topic | Information Theory Cryptography and Security |
| url | https://arxiv.org/abs/2405.19540 |