Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling
Abstract
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,…,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,…,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,…,Ym in a manner that minimizes the conditional entropy H(X|Y1,…,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.
Related
- DisKO: Deep Koopman Learning in Distribution Space from Unpaired Snapshots
- Learning hidden-state dynamics from unpaired snapshots with lift-project SDEs
- The Frohmanian Symplectic Tether: Canonical Uniqueness on Coadjoint Orbits of SDiff(T3), Non-Degenerate Casimir Coupling, and Conditional Global Regularity via Quartic Young Absorption in Lean 4
- Learning Transition Kernels of Jump-Diffusion Processes with Conditional Diffusion Models
- Learning Conditional Expectation Operators via Functional Newton Updates
BibTeX
@misc{li2026learning,
title = {{Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling}},
author = {Cheuk Ting Li and Jun Chen and Shahab Asoodeh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.16229},
eprint = {2605.16229},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.16229},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning from Totally Unpaired Data via Minimum Conditional Entropy Coupling
AU - Cheuk Ting Li
AU - Jun Chen
AU - Shahab Asoodeh
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2605.16229
UR - https://arxiv.org/abs/2605.16229
AB - Consider an "unsupervised classification" setting, where the goal is to learn a predictor of the categorical class variable X using the categorical feature variables Y_1,…,Y_m, 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,Y_1,…,Y_m. 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,Y_1,…,Y_m in a manner that minimizes the conditional entropy H(X|Y_1,…,Y_m). 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.
ER -