Computing Low-Entropy Couplings for Large-Support Distributions
<|reference_start|>Computing Low-Entropy Couplings for Large-Support Distributions: 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 .<|reference_end|>
@article{sokota2024computing,
    title={Computing Low-Entropy Couplings for Large-Support Distributions},
    author={Samuel Sokota, Dylan Sam, Christian Schroeder de Witt, Spencer
  Compton, Jakob Foerster, J. Zico Kolter},
    journal={arXiv preprint arXiv:2405.19540},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.19540},
    primaryClass={cs.IT cs.CR math.IT}
}