F-divergence bounds derive from simple binary comparisons
A local-to-global principle for $f$-divergence homogenization
Information Theory
Summary
This paper looks at how certain mathematical measures of difference between data distributions behave when many independent experiments are replaced by repeated averages. The authors find that whether this change increases the measure too much depends only on a simple case involving just two outcomes and two possible results. This means complex situations can be understood by checking just a small example. Their findings apply broadly without needing assumptions like smoothness or symmetry.
What this means in practice
- •For data engineers: Improve the evaluation of data similarity measures by verifying divergence bounds through simple binary comparisons.
- •For statistical software developers: Optimize algorithms that approximate divergences in large datasets using local tests on small binary cases.
A theory result. No direct application yet.
Authors
Aryeh Kontorovich
Abstract
We study the effect of replacing a family of independent statistical experiments by independent repetitions of their average. We give a simple, complete characterization of the $f$-divergences for which this operation increases divergence by at most a constant depending only on the generator, uniformly in the number of observations and the underlying measurable space. The characterization is governed by a local-to-global principle: a comparison restricted to two observations on a binary alphabet already determines the validity of the general inequality. It admits an explicit scalar formulation, which simplifies further for symmetric divergences. The result applies to arbitrary convex generators and requires no differentiability or symmetry assumptions. It recovers the homogenization inequality for total variation and identifies exactly the admissible members of the power-divergence family. In particular, whenever uniform homogenization fails, the obstruction is already present in a family of binary experiments with two observations. Moreover, the global comparison constant is controlled uniformly over generators with a common bound in the local inequality.