Entropy Equivalence Testing Reduces Distribution Comparison Cost

Comparing two probability distributions is a primitive operation in machine learning -- it underlies model evaluation, detecting distribution shift, and testing whether two learned systems carry equivalent information. The expensive version of this question, closeness testing, asks whether p equals q exactly. A preprint on arXiv by Clément L. Canonne, Yash Pote, Jonathan Scarlett, and Joy Qiping Yang proposes a relaxed alternative: test only whether the two distributions have equivalent Shannon entropy, within some tolerance ε. They show the sample complexity for this weaker question can be, according to the paper, "significantly lower than that of closeness testing."

The most concrete contribution is for Bayesian networks. The approach yields, reportedly, "the first non-trivial testing algorithm for (standard) closeness of low-degree Bayesian networks, which significantly improves on either the sample or time complexity of a baseline based on full learning." Bayesian networks appear throughout probabilistic modeling and causal inference, so a cheaper algorithm for checking whether two such models are informationally similar has real downstream interest.

The honest caveat is that this is a complexity-theoretic result. The algorithm works by "testing both farness in Hellinger distance and a cross-entropy difference term" separately, which is technically elegant but does not arrive as a ready-to-use library. The Bayesian network bounds still carry exponential dependence on the network degree, so high-degree structures remain expensive. Entropy equivalence is also genuinely a weaker test than closeness -- two distributions can share entropy while differing substantially in shape, which matters for practitioners who need more than information-content agreement. What the paper does not provide is empirical benchmarks on realistic distributions.

The matching lower bounds are what give the result its theoretical bite: the paper establishes that any entropy equivalence testing algorithm must use samples of the same asymptotic order as the upper bound (up to logarithmic factors), meaning the algorithm is near-optimal and further improvement is fundamentally limited. For researchers working on distribution testing or probabilistic graphical models, that is the result worth studying.