# Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling

arXiv: https://arxiv.org/abs/2605.16229 · HTML: https://mlsanity.com/paper/2605.16229/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 20 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 11 of 11)

- [Perfectly Secure Steganography Using Minimum Entropy Coupling](https://mlsanity.com/paper/2210.14889/) (2022)
- [Entropic Causal Inference](https://mlsanity.com/paper/1611.04035/) (2016)
- [Communicating via Markov Decision Processes](https://mlsanity.com/paper/2107.08295/) (2021)
- [Minimum-Entropy Coupling Approximation Guarantees Beyond the Majorization Barrier](https://mlsanity.com/paper/2302.11838/) (2023)
- [How to Find a Joint Probability Distribution of Minimum Entropy (almost) given the Marginals](https://mlsanity.com/paper/1701.05243/) (2017)
- [Fundamental Limits of Perfect Concept Erasure](https://mlsanity.com/paper/2503.20098/) (2025)
- [Minimum Entropy Coupling with Bottleneck](https://mlsanity.com/paper/2410.21666/) (2024)
- [Asymptotic Coupling and Its Applications in Information Theory](https://mlsanity.com/paper/1712.06804/) (2017)
- [A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling](https://mlsanity.com/paper/2203.05108/) (2022)
- [Learning to Match Unpaired Data with Minimum Entropy Coupling](https://mlsanity.com/paper/2503.08501/) (2025)
- [Computing Low-Entropy Couplings for Large-Support Distributions](https://mlsanity.com/paper/2405.19540/) (2024)

## Abstract (arXiv)

Consider an "unsupervised classification" setting, where the goal is to learn a predictor of the categorical class variable X using the categorical feature variables Y1,ldots,Ym, but we can only train the predictor on m+1 totally unpaired datasets, where each dataset only consists of unordered samples of one of the variables X,Y1,ldots,Ym. Although this problem is highly underdetermined, we demonstrate that, under the assumption that a predictor with small cross entropy loss exists, we can find a good predictor by coupling the marginal distributions of X,Y1,ldots,Ym in a manner that minimizes the conditional entropy H(X|Y1,ldots,Ym). This problem, which we call minimum conditional entropy coupling (MCEC), is a generalization of the widely studied minimum entropy coupling problem (where m=1). Although the MCEC problem is NP-hard, we give an algorithm with a time complexity that is polynomial in N, which gives a coupling with conditional entropy within O(log log N) from the optimum, where N is the dimension of the output coupling. We also evaluate the performance of the MCEC predictor on synthetic and real-world datasets.