KL Divergence Estimation with Multi-group Attribution

Parikshit Gopalan, Nina Narodytska, Omer Reingold, Vatsal Sharan, Udi WiederarXiv 2022 · arXiv

Introduction

In machine learning and statistical analysis, the Kullback-Leibler (KL) divergence is a fundamental metric used to quantify the difference between two probability distributions. It is widely applied in detecting data drift, evaluating generative models, and comparing outcomes across different populations. However, standard KL divergence estimation typically yields a single global value that summarizes the shift across the entire dataset.

This "big picture" approach can be misleading in high-stakes scenarios, such as algorithmic fairness or public health. A global average may obscure significant shifts within specific sub-populations or, conversely, attribute a global shift to a group that has remained stable. The paper "KL Divergence Estimation with Multi-group Attribution" addresses this gap by introducing a framework that ensures KL divergence estimates are accurate and fair across a vast collection of potentially overlapping sub-groups.

The Multi-group Attribution Framework

The authors propose "multi-group attribution" as a rigorous standard for density ratio estimation. For an estimation model to be considered effective across sub-populations, it must satisfy two primary criteria for every sub-group $C$:

  1. Soundness: The model’s estimated divergence for group $C$ should not exceed the true divergence. This property prevents "false alarms," ensuring that the model does not claim a sub-population is experiencing a distribution shift that does not exist in reality.
  2. Improvement: The model must provide a more accurate representation of the target distribution than the baseline for every single sub-group of interest.

By satisfying these properties, the framework ensures that the resulting divergence estimates provide a reliable lower bound on the true shift for any demographic or category defined by the researcher.

Methodology: The Role of Multi-calibration

The core technical contribution of the paper is the application of multi-calibration to density ratio estimation. While traditional methods like Maximum Entropy (MaxEnt) or Log-linear KLIEP focus on "multi-accuracy" (being correct on average), they often fail to maintain accuracy when zooming in on specific data partitions.

The authors adapt an algorithm known as "Boosting by branching programs" to estimate importance weights—the ratio between the two distributions. By ensuring these weights are multi-calibrated, the model becomes unbiased across all defined sub-groups. This approach leverages the Pythagorean property of KL divergence, a geometric concept that allows the researchers to relax the goal of perfect attribution into a computationally feasible task that still yields meaningful, conservative lower bounds.

Experimental Evaluation

The researchers evaluated the multi-calibration (MC) approach against standard benchmarks using both synthetic and real-world datasets:

  • Mixtures of Gaussians: Using a synthetic setup with 15 distinct clusters, the authors introduced known mean shifts. The MC approach consistently stayed close to the true divergence (approximately 9) for every cluster. In contrast, competing methods like KLIEP and uLSIF exhibited high variance, often underestimating the divergence of specific groups by more than 50%.
  • MNIST (Handwritten Digits): Distribution shifts were simulated by biasing the probability of odd versus even digits. The MC model successfully attributed the divergence to specific digit pairs (e.g., identifying how much "4"s and "8"s contributed to the shift), demonstrating its utility in high-dimensional data.

Key Insights and Results

  • Failure of Existing Methods: A significant finding is that popular methods like MaxEnt and Log-linear KLIEP do not satisfy multi-group attribution. Despite their popularity, they can be highly "unsound" for specific sub-groups, leading to unreliable local estimates.
  • Robustness: The multi-calibration approach proved robust even when using simple "base learners," such as decision trees of depth 1. While the performance of log-linear models collapsed under these conditions, the MC framework maintained its accuracy.
  • Theoretical Guarantees: The paper provides formal proofs that any $\alpha$-approximately multi-calibrated partition results in a model that satisfies $(\alpha, \beta)$ multi-group attribution, grounding the empirical success in rigorous theory.

Limitations and Future Directions

While the framework offers significant improvements in fairness and local accuracy, it faces certain trade-offs:

  • Sample Complexity: Multi-calibration is data-intensive; protecting smaller sub-populations requires a larger number of samples.
  • Computational Cost: The boosting-based algorithm is slower than simple regression-based methods like uLSIF, moving from millisecond to second-scale processing times.
  • Small Group Sensitivity: Mathematical bounds for the Pythagorean property tend to degrade for very small groups where the group's measure is close to the error parameter $\alpha$.

Future research may extend these attribution guarantees to other statistical distances, such as Rényi divergence or Total Variation distance, further broadening the toolkit for fair and granular distribution analysis.

Summary updated

Abstract

Estimating the Kullback-Leibler (KL) divergence between two distributions given samples from them is well-studied in machine learning and information theory. Motivated by considerations of multi-group fairness, we seek KL divergence estimates that accurately reflect the contributions of sub-populations to the overall divergence. We model the sub-populations coming from a rich (possibly infinite) family $\mathcal{C}$ of overlapping subsets of the domain. We propose the notion of multi-group attribution for $\mathcal{C}$, which requires that the estimated divergence conditioned on every sub-population in $\mathcal{C}$ satisfies some natural accuracy and fairness desiderata, such as ensuring that sub-populations where the model predicts significant divergence do diverge significantly in the two distributions. Our main technical contribution is to show that multi-group attribution can be derived from the recently introduced notion of multi-calibration for importance weights [HKRR18, GRSW21]. We provide experimental evidence to support our theoretical results, and show that multi-group attribution provides better KL divergence estimates when conditioned on sub-populations than other popular algorithms.
BibTeX
@misc{gopalan2022kl,
  author = {Parikshit Gopalan and Nina Narodytska and Omer Reingold and Vatsal Sharan and Udi Wieder},
  title = {{KL Divergence Estimation with Multi-group Attribution}},
  year = {2022},
  eprint = {2202.13576},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.13576},
}
Figure