Ordered $\mathcalV$-information Growth: A Fresh Perspective on Shared Information

AISTATS 2025

TL;DR

This paper introduces "Ordered V-Information Growth" (O-VIG), a novel measure of shared information that addresses the over-estimation bias of existing V-information methods, especially in the presence of noise or limited computational resources. O-VIG offers a more robust and tighter lower bound for true V-information, demonstrating superior performance in both mutual information estimation and dataset complexity assessment.

What Problem Does This Paper Address?

Estimating mutual information (MI) and related measures of shared information between random variables is crucial in many fields, including machine learning. However, traditional MI assumes unbounded computational resources, which is unrealistic in practice. V-information was proposed to address this by incorporating computational constraints through a "predictive family" $\mathcal{V}$. Despite this, the empirical estimation of V-information can suffer from an upward bias, particularly when using neural networks, as they can easily overfit to noisy data. This paper tackles the challenge of accurately estimating shared information under realistic computational constraints, aiming to provide a more reliable and less biased measure than existing V-information approaches.

Methods

The authors propose Ordered V-Information Growth (O-VIG), which builds upon V-information with two key innovations:

  1. V-Information Growth (VI-Growth): To mitigate the noise-fitting bias of empirical V-information, VI-Growth is introduced. It's calculated by subtracting the V-information between independently sampled variables ($X', Y' \sim P_X P_Y$) from the V-information between the original variables ($X, Y \sim P_{XY}$). This effectively debiases the measure by accounting for the information that can be learned from random chance.
  2. Ordered V-Information Growth (O-VIG): To address the under-estimation bias that can occur with very complex predictive families in VI-Growth, O-VIG constructs an ordered sequence of predictive families $\mathcal{V}_1 \subset \mathcal{V}_2 \subset \dots \subset \mathcal{V}_k$. O-VIG is then defined as the maximum VI-Growth across this sequence of families. This approach leverages the fact that VI-Growth is a lower bound for true V-information and aims to find the tightest possible lower bound by exploring a range of complexities.

The paper also introduces theoretical results justifying O-VIG, showing it's a provably tighter lower bound for V-information with stronger convergence properties than empirical V-information.

Datasets

The authors utilize a variety of datasets for their experiments:

  • Real Datasets: MNIST, CIFAR-10, CIFAR-100.
  • Synthetic Datasets: Four configurations (D1-D4) are generated with varying dimensionality and dependency structures, designed to test specific aspects of the proposed measures.
  • OpenML Datasets: 15 tabular datasets from OpenML are used for complexity assessment.

Key Insights and Ideas

  • Noise-fitting bias in V-information: Neural networks, even shallow ones, can easily overfit to independent variables, leading to an overestimation of shared information.
  • VI-Growth as a debiasing mechanism: Subtracting the V-information of independent variables effectively removes the bias introduced by fitting noise.
  • Underestimation with high complexity: While VI-Growth debiases, very complex predictive families can still lead to underestimation.
  • O-VIG as a robust solution: By taking the maximum VI-Growth over an ordered set of predictive families, O-VIG effectively mitigates both over- and under-estimation biases.
  • O-VIG as a better indicator of dataset complexity: O-VIG shows a stronger correlation with test accuracy than V-information and other baseline methods, suggesting its utility in understanding dataset difficulty.

Key Results

  • Improved MI Estimation: O-VIG consistently outperforms state-of-the-art methods in MI estimation accuracy across various datasets, especially in scenarios with limited sample sizes and higher dimensionality. For instance, in Table 1, O-VIG achieves the lowest RMSE and MAE in most cases, and a high Spearman correlation.
  • Robustness to Noise: O-VIG demonstrates superior robustness to both label noise and input noise compared to V-information. While V-information can increase with noise, O-VIG reliably decreases, aligning with the expected behavior of shared information measures.
  • Dataset Complexity: O-VIG shows a significantly stronger correlation with test accuracy on vision and tabular datasets compared to V-information and other benchmark measures, indicating its effectiveness in assessing dataset complexity.
  • Convergence: O-VIG converges to zero much faster than V-information when variables are independent, highlighting its ability to correctly identify the absence of shared information.

Limitations and Future Work

  • Class Imbalance: The authors note that VI-Growth (and by extension O-VIG) can be positively biased by the number of classes in a problem. They suggest that normalization approaches might be needed to address class variations across datasets.
  • Computational Cost: Estimating O-VIG is approximately twice as computationally expensive as estimating V-information due to the need to evaluate multiple predictive families. The authors suggest that "early-stopping" could be explored to speed up estimation.
  • Future Directions: The paper suggests exploring early-stopping for faster estimation and investigating normalization techniques for class imbalance. They believe O-VIG represents a promising new direction for shared information measures.

Summary updated

BibTeX
@inproceedings{2025ordered,
  title = {{Ordered $\textbackslash\{\}mathcalV$-information Growth: A Fresh Perspective on Shared Information}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure