Ordered-information Growth: A Fresh Perspective on Shared Information

Rohan Ghosh, Mehul MotaniAISTATS 2025 · OpenReview

TL;DR

This paper introduces Ordered V-Information Growth (O-VIG), a novel measure of shared information that addresses the limitations of traditional mutual information (MI) and its predecessor, V-information. O-VIG effectively mitigates biases in existing measures, leading to more accurate estimations of shared information and improved performance in tasks like dataset complexity estimation.

What Problem Does This Paper Address?

Estimating shared information between random variables is crucial in many fields, especially machine learning. Mutual Information (MI) is a standard measure, but it assumes unlimited computational resources, which is unrealistic in practice. V-information was proposed to address this by incorporating computational constraints through a "predictive family" $\mathcal{V}$. However, empirical V-information often suffers from an upward bias, overestimating the true shared information, especially with complex predictive models like neural networks. This paper tackles the problem of accurately estimating shared information under realistic computational constraints, aiming for a more robust and less biased measure.

Methods

The authors introduce two key innovations:

  1. V-Information Growth (VI-Growth): To combat the overestimation bias of empirical V-information, they propose VI-Growth. This measure subtracts the V-information estimated between independent variables ($X', Y' \sim P_X P_Y$) from the V-information estimated between the original variables ($X, Y$). This effectively "de-biases" the measure by accounting for the model's ability to find spurious correlations in noisy or independent data.
  2. Ordered V-Information Growth (O-VIG): While VI-Growth reduces overestimation, it can lead to underestimation with highly complex predictive families. To address this, O-VIG constructs a sequence of predictive families $\mathcal{V}_1, \mathcal{V}_2, \ldots, \mathcal{V}$ with increasing complexity. O-VIG is then defined as the maximum VI-Growth computed across this ordered sequence. This approach leverages the idea that the true V-information is bounded by the maximum VI-Growth across these families, providing a tighter lower bound.

The paper also provides theoretical results justifying these approaches, including proofs of properties like non-negativity and convergence rates.

Datasets

The authors evaluate their methods on a variety of datasets:

  • Real Datasets: MNIST, CIFAR-10, CIFAR-100.
  • Synthetic Datasets: Datasets of the form $(X, Y)$ where $X \in \mathbb{R}^d$ and $Y \in \{0, 1\}$, with varying dimensionality ($d=3, 10, 100$) and sample sizes. These are designed to control the ground truth mutual information.

Key Insights and Ideas

  • The "Noise-Fitting Bias": Neural networks, even shallow ones, can easily "overfit" to noise or spurious correlations in data, leading to an overestimation of shared information when using empirical V-information. VI-Growth directly addresses this by comparing the information learned from actual data to information learned from independent, shuffled data.
  • Complexity vs. Accuracy Trade-off: While more complex predictive families can capture more nuanced relationships, they also increase the risk of overfitting and bias. O-VIG elegantly navigates this by considering a range of complexities and taking the maximum VI-Growth, effectively finding a sweet spot.
  • O-VIG as a Tighter Bound: The theoretical results suggest that O-VIG provides a provably tighter lower bound for V-information compared to empirical V-information itself, and exhibits stronger convergence properties.
  • Practical Utility Beyond MI Estimation: O-VIG proves useful not only for estimating shared information but also for assessing dataset complexity, correlating well with test accuracy in vision and tabular tasks.

Key Results

  • Bias Reduction: O-VIG consistently shows significantly less bias than empirical V-information, converging to zero much faster when variables are independent.
  • Improved MI Estimation: In experiments, O-VIG outperforms state-of-the-art MI estimators, particularly in scenarios with higher dimensionality and smaller sample sizes. For instance, in the challenging 100-dimensional D4 dataset, O-VIG achieves a significantly lower RMSE and higher Spearman correlation with ground truth MI compared to other methods.
  • Robustness to Noise: O-VIG demonstrates better robustness to label noise and input noise compared to V-information, maintaining a decreasing trend as noise increases, which is expected for a measure of shared information.
  • Dataset Complexity Correlation: O-VIG shows strong positive Spearman correlations with test accuracy across various vision and tabular datasets, indicating its utility in characterizing dataset difficulty.

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 for datasets with significant class variations.
  • Computational Cost: Estimating O-VIG is more computationally expensive than V-information (approximately twice as costly, depending on the size of the V-ordered set). The authors suggest that "early-stopping" techniques could be explored to speed up estimation.
  • Future Directions: The paper opens up new avenues for research in shared information measures, with O-VIG representing a promising direction for more robust and accurate estimation, especially in the context of complex machine learning models.

Summary updated

Abstract

Mutual information (MI) is widely employed as a measure of shared information between random variables. However, MI assumes unbounded computational resources—a condition rarely met in practice, where predicting a random variable $Y$ from $X$ must rely on finite resources. $\mathcal{V}$-information addresses this limitation by employing a predictive family $\mathcal{V}$ to emulate computational constraints, yielding a directed measure of shared information. Focusing on the mixed setting (continuous $X$ and discrete $Y$), here we highlight the upward bias of empirical $\mathcal{V}$-information, $\hat I_{\mathcal{V}}(X \rightarrow Y)$, even when $\mathcal{V}$ is low-complexity (e.g., shallow neural networks). To mitigate this bias, we introduce $\mathcal{V}$-Information Growth (VI-Growth), defined as $\\hat I_{\mathcal{V}}(X \rightarrow Y) - \hat I_{\mathcal{V}}(X’ \rightarrow Y’)$, where $X’, Y’ \sim P_X P_Y$ represent independent variables. While VI-Growth effectively counters over-estimation, more complex predictive families may lead to under-estimation. To address this, we construct a sequence of predictive families $\mathcal{V}_1, \mathcal{V}_2, \ldots, \mathcal{V}$ of increasing complexity and compute the maximum of VI-Growth across these families, yielding the ordered VI-Growth (O-VIG). We provide theoretical results that justify this approach, showing that O-VIG is a provably tighter lower bound for the true $\mathcal{V}$-Information than empirical $\mathcal{V}$-Information itself, and exhibits stronger convergence properties than $\mathcal{V}$-Information. Empirically, O-VIG alleviates bias and consistently outperforms state-of-the-art methods in both MI estimation and dataset complexity estimation, demonstrating its practical utility.
BibTeX
@inproceedings{ghosh2025ordered,
  author = {Rohan Ghosh and Mehul Motani},
  title = {{Ordered-information Growth: A Fresh Perspective on Shared Information}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=Fmj2VWP8Uc},
}
Figure