Consistency of the Maximal Information Coefficient Estimator

John Lazarsfeld, Aaron JohnsonarXiv 2021 · OpenReview

Abstract: The Maximal Information Coefficient (MIC) of Reshef et al. (Science, 2011) is a statistic for measuring dependence between variable pairs in large datasets. In this note, we prove that MIC is a consistent estimator of the corresponding population statistic MIC$_*$. This corrects an error in an argument of Reshef et al. (JMLR, 2016), which we describe.

Introduction

In modern data science, identifying relationships between variables is a fundamental task. While Pearson’s correlation coefficient is the standard for linear dependencies, it fails to capture complex, non-linear patterns such as periodic oscillations or functional "clouds." The Maximal Information Coefficient (MIC) was introduced to address this gap, providing a measure of dependence that is robust across a wide variety of relationship types.

For any statistical estimator to be considered reliable, it must demonstrate consistency. Mathematically, this means that as the sample size $n$ increases toward infinity, the estimator should converge in probability to the true population value. While a proof of consistency for MIC was proposed in 2016, subsequent analysis revealed a critical flaw in the underlying logic. This paper provides a rigorous correction to that proof, establishing a new, mathematically sound foundation for MIC, albeit under more specific parameter constraints.

The Problem: A Flaw in Probability Bounds

The original attempt to prove MIC's consistency relied on a multiplicative Chernoff bound to estimate the error between sample data and the true underlying distribution. MIC operates by partitioning data into increasingly fine grids as the sample size grows. The original proof, however, failed to account for the shrinking probability mass of these individual grid cells.

In the original derivation, a term representing the probability mass was essentially treated as a constant. However, because the number of cells in the grid increases with $n$, the probability mass within any single cell approaches zero. By "dropping" this dependence, the original error bound was made to appear as though it vanished, when in reality, the bound exploded. This left the consistency of MIC—a statistic used widely in genomic and social science research—technically unproven.

Methodology: A New Proof Strategy

To rectify this, the authors moved away from the problematic multiplicative Chernoff bound and adopted a strategy centered on Total Variation (TV) distance. The core challenge in proving consistency for MIC lies in bounding the difference between the sample mutual information and the population mutual information across all possible grids simultaneously.

Handling Grid Cell Variance

The authors employed a "split" analysis technique to manage the behavior of the grid cells:

  1. Large Cells: For cells with significant probability mass, standard concentration inequalities can be applied effectively.
  2. Small Cells: For cells where the probability mass is infinitesimally small, the authors used different bounding techniques to ensure that the cumulative error from these cells did not destabilize the estimator.

By treating these two regimes separately, the authors were able to show that the total variation between the sample and population distributions remains controlled, allowing the sample MIC to converge to the population MIC$_*$.

Key Results and the "Alpha Gap"

The primary result of this work is the formal proof that the sample MIC is indeed a consistent estimator. Specifically, the paper demonstrates that the difference between the sample and population statistics is $o(1)$ with a probability of at least $1 - O(n^{-1.5})$.

However, this mathematical rigor comes with a trade-off in the range of applicable parameters. The original (flawed) proof claimed consistency for grid sizes growing at a rate of $O(n^\alpha)$ for any $\alpha < 1$. The new, corrected proof establishes consistency for:

$$0 < \alpha < 0.5$$

This creates what researchers call the "alpha gap." While the statistic is now proven consistent for $\alpha < 0.5$, many practitioners currently use MIC with $\alpha$ values between $0.5$ and $1.0$.

Conclusion and Future Work

This paper restores the theoretical standing of the Maximal Information Coefficient by providing the first rigorous proof of its consistency. While the result is more restrictive than the original claim, it provides a necessary and solid foundation for the use of MIC in scientific discovery.

The question of whether consistency holds for the range $0.5 \leq \alpha < 1$ remains an open problem. The authors suggest that while the claim is likely true, proving it will require more sophisticated tools from information theory or empirical process theory than those currently employed in the literature. For now, this work serves as a vital correction and a reminder of the importance of rigorous verification in statistical theory.

Summary updated

Abstract

The Maximal Information Coefficient (MIC) of Reshef et al. (Science, 2011) is a statistic for measuring dependence between variable pairs in large datasets. In this note, we prove that MIC is a consistent estimator of the corresponding population statistic MIC$_*$. This corrects an error in an argument of Reshef et al. (JMLR, 2016), which we describe.
BibTeX
@misc{lazarsfeld2021consistency,
  author = {John Lazarsfeld and Aaron Johnson},
  title = {{Consistency of the Maximal Information Coefficient Estimator}},
  year = {2021},
  eprint = {2107.03836},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2107.03836},
}
Figure