Computing Low-Entropy Couplings for Large-Support Distributions

Samuel Sokota, Dylan Sam, Christian Schroeder de Witt, Spencer Compton, Jakob Foerster, J. Zico Kolter
Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, PMLR 244:3279-3298, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v244-sokota24a, title = {Computing Low-Entropy Couplings for Large-Support Distributions}, author = {Sokota, Samuel and Sam, Dylan and Schroeder de Witt, Christian and Compton, Spencer and Foerster, Jakob and Kolter, J. Zico}, booktitle = {Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence}, pages = {3279--3298}, year = {2024}, editor = {Kiyavash, Negar and Mooij, Joris M.}, volume = {244}, series = {Proceedings of Machine Learning Research}, month = {15--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v244/main/assets/sokota24a/sokota24a.pdf}, url = {https://proceedings.mlr.press/v244/sokota24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Computing Low-Entropy Couplings for Large-Support Distributions %A Samuel Sokota %A Dylan Sam %A Christian Schroeder de Witt %A Spencer Compton %A Jakob Foerster %A J. Zico Kolter %B Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2024 %E Negar Kiyavash %E Joris M. Mooij %F pmlr-v244-sokota24a %I PMLR %P 3279--3298 %U https://proceedings.mlr.press/v244/sokota24a.html %V 244 %X 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.
APA
Sokota, S., Sam, D., Schroeder de Witt, C., Compton, S., Foerster, J. & Kolter, J.Z.. (2024). Computing Low-Entropy Couplings for Large-Support Distributions. Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 244:3279-3298 Available from https://proceedings.mlr.press/v244/sokota24a.html.

Related Material