Breaking the Finite-Sample Barrier in Entropy Coupling
Shahab Asoodeh † and Jun Chen ‡ · 2026
Read Breaking the Finite-Sample Barrier in Entropy Coupling by Shahab Asoodeh † and Jun Chen ‡ (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16229.txt.
Introduction
Li, Chen, and Asoodeh tackle unsupervised classification from totally unpaired data, where each dataset holds unordered samples of only one variable. The problem is highly underdetermined, yet if a predictor with small cross-entropy loss exists, coupling the marginal distributions to minimize conditional entropy finds a good predictor. Their minimum conditional entropy coupling generalizes minimum entropy coupling to many variables. Though NP-hard, their algorithm runs in time polynomial in N and lands within order log log N of optimal conditional entropy.
Catalog record
| CREATOR | Shahab Asoodeh † and Jun Chen ‡ |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111801 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16229
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Breaking the Finite-Sample Barrier in Entropy Coupling Shahab Asoodeh † and Jun Chen ‡ Abstract Dependence among marginally constrained observations can break a finite-sample barrier. To formalize this phenomenon, we introduce the minimum list entropy coupling H ( P ∥ Q 1 , … , Q m ) H(P\|Q_{1},\dots,Q_{m}) , the minimum conditional entropy H ( X | Y 1 , … , Y m ) H(X|Y_{1},\dots,Y_{m}) over all joint distributions with prescribed discrete marginals X ∼ P X\sim P and Y i ∼ Q i Y_{i}\sim Q_{i} . Unlike classical formulations based on independent observations, our model allows Y 1 , … , Y m Y_{1},\dots,Y_{m} to be arbitrarily dependent while keeping each marginal fixed. This enlarged coupling space reveals a sharp dichotomy: independent observations reduce residual uncertainty exponentially, whereas dependent observations can eliminate it exactly after finitely many samples. We characterize this zero-entropy regime through necessary and sufficient conditions and give concrete structural criteria under which it occurs. In particular, under mild support assumptions, zero entropy is achieved with O ( log ( 1 / P min ) ) O(\log(1/P_{\min})) observations, where P min P_{\min} is the minimum nonzero mass of P P . We also develop a greedy algorithm with monotone approximation guarantees for computing H ( P ∥ Q 1 , … , Q m ) H(P\|Q_{1},\dots,Q_{m}) . Finally, we show that the same framework formalizes finite-sample limits in distribution-matching representation learning and randomness extraction, where zero entropy corresponds to exact recovery and exact extraction. I Introduction Marginal constraints often appear to impose an intrinsic limit on recovery: even with many observations, one expects uncertainty about the source to decay gradually rather than vanish exactly. This paper shows that this intuition is incomplete. When observations are allowed to be dependently coupled while preserving their prescribed marginals, uncertainty can collapse to zero after finitely many coordinates. We study this phenomenon through statistical coupling, whose central goal is to construct joint distributions with prescribed marginals that optimize an information-theoretic objective. Classical formulations, such as maximal coupling [ 15 ] and minimum entropy coupling (MEC) [ 24 , 3 , 5 ] , focus on pairwise couplings and characterize fundamental limits of agreement and uncertainty reduction, respectively. MEC, in particular, minimizes H(X,Y) or equivalently H(X|Y) , and has been extensively studied in information theory [ 23 , 21 , 8 , 16 , 26 , 18 , 13 ] . It also underlies a broad range of applications, including causal inference [ 11 , 12 , 10 ] , generative modeling [ 1 ] , concept erasure [ 2 ] , steganography [ 19 ] , dimensionality reduction [ 4 ] , communication [ 22 ] , and random number generation [ 14 ] . In these classical settings, exact recovery is highly restrictive: even when approximate reconstruction is possible, eliminating all uncertainty typically requires strong structural conditions. We show that this limitation disappears in the multi-observation setting. Allowing multiple observations with fixed marginals fundamentally enlarges the space of admissible couplings and enables finite-sample exact recovery , where uncertainty about X vanishes after finitely many observations. This reveals a phase transition with no analogue in classical coupling theory. Formally, given distributions P and \{Q_{i}\}_{i=1}^{m} on a finite alphabet {\mathcal{X}} , we define H(P\|Q_{1},\ldots,Q_{m})\coloneqq\inf H(X|Y_{1},\ldots,Y_{m}), where the infimum is over all joint distributions with X\sim P and Y_{i}\sim Q_{i} , allowing arbitrary dependence across (Y_{1},\dots,Y_{m}) . In the homogeneous case Q_{i}=Q , we write H_{m}(P\|Q) . We say that finite-sample exact recovery holds if there exists a finite integer m such that H(P\|Q_{1},\ldots,Q_{m})=0 , i.e., X is a deterministic function of Y^{m}\coloneqq(Y_{1},\dots,Y_{m}) under an admissible coupling. The smallest such m is the corresponding exact-recovery sample complexity and denoted by m_{0}(P\|Q_{1},\dots,Q_{m}) . A useful baseline is the product-law restriction on the observation tuple: Y^{m}\sim Q_{1}\otimes\cdots\otimes Q_{m} . This factorizes only the marginal law of Y^{m} , while leaving the conditional law P_{Y^{m}|X} unrestricted. Under this restriction, we show that a quantile construction yields exponential decay of the residual uncertainty H(P\|Q_{1},\ldots,Q_{m}) in m . Our main finding is that dependence across (Y_{1},\dots,Y_{m}) induces a phase transition: the residual uncertainty collapses to zero after finitely many observations. That is, rather than merely decaying, the conditional entropy can become exactly zero at a finite m . We demonstrate this phenomenon in canonical examples by explicitly computing H_{m}(P\|Q) (including the uniform and Bernoulli cases) and showing that finite-sample exact recovery occurs. Inspired by these examples, we identify sharp structural conditions under which finite-sample exact recovery occurs. We remark that recent work extends MEC to multiple variables by minimizing H(X,Y^{m}) subject to X\sim P and Y_{i}\sim Q_{i} [ 5 , 14 , 7 , 6 ] . In contrast, we minimize H(X|Y^{m}) . While the two formulations coincide for m=1 , they diverge fundamentally for m\geq 2 . Joint entropy minimization favors globally compact couplings, whereas our objective isolates the residual uncertainty about X . Summary of Contributions. Our main contributions are as follows: • We compute H_{m}(P\|Q) explicitly in the uniform and Bernoulli cases and demonstrate finite-sample exact recovery. In particular, for any P on [r] , H_{m}(P\|\mathsf{Unif}([r]))=0 for all m\geq 2 , while H_{1}(P\|\mathsf{Unif}([r]))=0 holds if and only if P is a deterministic pushforward of \mathsf{Unif}([r]) (Proposition 1 ). In the Bernoulli case (for p,q\leq\tfrac{1}{2} ), H_{m}(\mathsf{Ber}(p)\|\mathsf{Ber}(q))=0 whenever p\leq mq , whereas H_{1}(\mathsf{Ber}(p)\|\mathsf{Ber}(q))=0 only in degenerate cases (Proposition 2 ). These results exhibit a sharp separation between the m=1 and m\geq 2 regimes. • We prove that if \|Q_{i}\|_{\infty}\leq M<1 uniformly, then H(P\|Q_{1},\dots,Q_{m})=O(e^{-cm}) for some c>0 depending only on M (Theorem 4 ). The proof is based on a quantile coupling over product distributions and does not exploit dependence across (Y_{1},\dots,Y_{m}) . • We establish that finite-sample exact recovery holds for a broad class of distributions. In the homogeneous case, if Q^{*\ell} , the \ell -fold convolution of Q , is fully supported for some \ell , then H_{m}(P\|Q)=0 for all sufficiently large m , with sample complexity m_{0}(P\|Q)=O(\log(1/P_{\min})) , where P_{\min}\coloneqq\min_{x}P(x) (Theorem 2 and Corollary 3 ). We extend this result to the heterogeneous setting (Theorem 5 ) and derive necessary conditions showing that exact recovery requires entropy and support-size compatibility (Theorem 7 ). In the appendix, we then provide a characterization of finite-sample exact recovery (Theorem 6 ), which subsumes both Theorems 2 and 5 but under significantly weaker assumptions. • We propose a greedy LP-based algorithm to approximate H_{m}(P\|Q) . The method produces a sequence of upper bounds converging to a limit no smaller than H_{m}(P\|Q) . While the worst-case complexity is O(|{\mathcal{X}}|^{m}) , it performs accurately in small-scale regimes. Our results have direct implications in settings where marginal constraints are intrinsic. We highlight two applications where allowing dependence yields guarantees that are impossible under classical constructions. Application 1: Distribution-matching representation learning. Consider a representation Y^{m}=(Y_{1},\ldots,Y_{m}) of a source X\sim P , produced by a stochastic encoder W=P_{Y^{m}\mid X} , under the marginal constraints Y_{i}\sim Q_{i} . A decoder f then attempts to reconstruct X from Y^{m} . This captures a common requirement in representation learning: the learned coordinates must match prescribed target marginals while retaining as much information about the source as possible. The central question is