Controlling Bias in Adaptive Data Analysis Using Information Theory

Daniel Russo, James Zou

TL;DR

This paper introduces an information-theoretic framework to quantify and bound the bias introduced by adaptive data analysis. By leveraging mutual information, they provide a unified way to understand how the process of choosing analyses based on observed data can lead to misleading results, offering insights into when common statistical procedures are more or less susceptible to bias.

What Problem Does This Paper Address?

In modern data analysis, especially with high-dimensional and messy datasets, it's often impossible to know the "right" questions to ask upfront. Analysts typically engage in an "adaptive" process: they explore the data, identify interesting patterns, and then decide which further analyses to perform or hypotheses to test based on these initial findings. This iterative, data-driven approach, while intuitive for extracting insights, is a major contributor to the "reproducibility crisis" in science. Standard statistical theory, which assumes analyses are pre-specified, breaks down in these adaptive scenarios. This leads to "researcher degrees of freedom" and over-fitting, resulting in biased estimates and an increased risk of false discoveries. The paper aims to provide a principled way to measure and control this bias, even for complex, unspecified adaptive procedures.

Methods

The core of the paper's contribution is a general information-theoretic framework. They propose using the mutual information between the choice of analysis (represented by a random variable $T$) and the results of potential analyses (represented by a vector of random variables $\Phi$) as a measure of bias.

Key techniques include:

  • Information-Theoretic Bounds: They derive a central proposition (Proposition 1) that bounds the expected bias of a selected statistic $\phi_\tau$ by a term proportional to $I(T; \Phi)$, the mutual information between the selection process and the potential analysis outcomes. This bound is shown to be tight.
  • Generalization to Sub-Exponential Variables: The framework is extended beyond sub-Gaussian random variables to the broader class of sub-exponential random variables, making it applicable to a wider range of statistical models.
  • Analysis of Specific Protocols: The framework is applied to analyze common procedures like variance-based feature selection and rank selection, providing rigorous explanations for why and when they might introduce bias.
  • Information Budget Concept: They introduce the idea of an "information budget" for adaptive analysis, suggesting that controlling the total mutual information accumulated throughout an analysis process can limit bias.
  • Additive Noise for Bias Control: The paper explores how adding controlled amounts of random noise to intermediate results can effectively reduce mutual information and thus bias, drawing connections to differential privacy.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated examples to illustrate its findings.

Key Insights and Ideas

  • Mutual Information as a Bias Meter: The most significant insight is that mutual information $I(T; \Phi)$ elegantly captures the "price of adaptivity." High mutual information means the selection process is highly dependent on the observed data, leading to greater bias.
  • Signal Reduces Bias: The paper demonstrates that when there's a strong "signal" in the data (i.e., some analyses are genuinely more informative or relevant than others), the selection process becomes less adaptive and more focused, naturally reducing mutual information and bias. This is illustrated with a rank selection example where increasing signal strength decreases bias.
  • Randomization as a Bias Control Mechanism: Adding randomness to the selection process (e.g., through a Gibbs distribution or by adding noise to responses) can increase the mutual information between the selection and the true underlying data, but crucially, it can decrease the mutual information between the selection and the observed, potentially noisy analysis results. This effectively regularizes the process and reduces bias.
  • Unified Framework: The information-theoretic approach provides a single lens to analyze diverse adaptive strategies, from simple feature selection to more complex iterative analysis protocols, unifying disparate observations about bias.

Key Results

  • Tight Information-Theoretic Bound on Bias: The paper establishes a bound on the expected bias of an adaptively selected statistic, $|E[\phi_\tau] - E[\mu_\tau]| \le \sigma\sqrt{2I(T; \Phi)}$, which is proven to be tight.
  • Bias Control via Signal: For rank selection, increasing the signal strength $\mu$ in a simulated scenario led to a decrease in both the entropy of the selection $H(T)$ and the bias.
  • Trade-off with Randomized Selection: In a simulation comparing rank selection and randomized selection, randomized selection significantly decreased bias, especially in intermediate signal regimes, though it sometimes came at the cost of slightly lower accuracy.
  • Bounds on Other Error Measures: The framework can also bound other error metrics like average absolute error $E[|\phi_\tau - \mu_\tau|]$ and mean squared error $E[(\phi_\tau - \mu_\tau)^2]$.
  • Adaptive Analysis with Noise: For adaptive analysis protocols involving noisy responses, the paper shows that adding noise can improve accuracy for later queries, acting as a form of regularization and preventing error from accumulating indefinitely.

Limitations and Future Work

  • Tractability of $I(T; \Phi)$: While the framework is general, computing the mutual information $I(T; \Phi)$ can be challenging for complex, real-world adaptive procedures. The paper focuses on specific protocols and simulated scenarios where this computation is feasible or can be bounded.
  • Practical Implementation: The authors suggest that a key future direction is to explore practical implementations of this information-theoretic approach for designing new analysis protocols with guaranteed low bias.
  • Worst-Case vs. Specific Procedures: The paper contrasts its approach with "max-information," noting that while max-information provides strong worst-case guarantees, it can behave counter-intuitively for specific, well-behaved selection procedures (e.g., increasing with signal strength). The mutual information approach offers a more nuanced view for analyzing specific protocols.
  • Generalizing Noise Models: The analysis of additive noise is primarily done for Gaussian noise. Future work could explore other noise distributions and their impact on bias and accuracy.

Summary updated

Abstract

Modern data is messy and high-dimensional, and it is often not clear a priori what are the right questions to ask. Instead, the analyst typically needs to use the data to search for interesting analyses to perform and hypotheses to test. This is an adaptive process, where the choice of analysis to be performed next depends on the results of the previous analyses on the same data. It's widely recognized that this process, even if well-intentioned, can lead to biases and false discoveries, contributing to the crisis of reproducibility in science. But while adaptivity renders standard statistical theory invalid, folklore and experience suggest that not all types of adaptive analysis are equally at risk for false discoveries. In this paper, we propose a general information-theoretic framework to quantify and provably bound the bias and other statistics of an arbitrary adaptive analysis process. We prove that our mutual information based bound is tight in natural models, and then use it to give rigorous insights into when commonly used procedures do or do not lead to substantially biased estimation. We first consider several popular feature selection protocols, like rank selection or variance-based selection. We then consider the practice of adding random noise to the observations or to the reported statistics, which is advocated by related ideas from differential privacy and blinded data analysis. We discuss the connections between these techniques and our framework, and supplement our results with illustrative simulations.
BibTeX
@inproceedings{russo2016controlling,
  author = {Daniel Russo and James Zou},
  title = {{Controlling Bias in Adaptive Data Analysis Using Information Theory}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
}
Figure