How Much Does Your Data Exploration Overfit? Controlling Bias via Information Usage

By Daniel Russo, James Y. Zou. 2015

224 citations recorded by the source corpus.

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. Ultimately, which results are reported can be heavily influenced by the data. It is 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 any data-exploration renders standard statistical theory invalid, experience suggests that different types of exploratory analysis can lead to disparate levels of bias, and the degree of bias also depends on the particulars of the data set. In this paper, we propose a general information usage framework to quantify and provably bound the bias and other error metrics of an arbitrary exploratory analysis. We prove that our mutual information based bound is tight in natural settings, and then use it to give rigorous insights into when commonly used procedures do or do not lead to substantially biased estimation. Through the lens of information usage, we analyze the bias of specific exploration procedures such as filtering, rank selection and clustering. Our general framework also naturally motivates randomization techniques that provably reduce exploration bias while preserving the utility of the data analysis. We discuss the connections between our approach and related ideas from differential privacy and blinded data analysis, and supplement our results with illustrative simulations.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, methodology): “This problem has been studied in computer science [41] and, recently, has been analyzed using tools from information theory by Xu and Raginsky [42] and Russo and Zou [43].”
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation (2018, methodology): “Introduction Originally proposed by Sutton (1988), temporal difference learning (TD) is one of the most widely used reinforcement learning algorithms and a foundational idea onwhichmore complexmethods are built.”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “Building upon [6, 28, 34], we develop bounds for generalization error in terms of disintegrated information-theoretic quantities that extract expectations from concave functions as much as possible.”
Chaining Mutual Information and Tightening Generalization Bounds (2018, background): “This was originally proposed in the key paper of Russo and Zou [6] and then generalized in [16], [17], and in [18] for infinite number of hypotheses: Theorem 2.”
User-friendly introduction to PAC-Bayes bounds (2021, background): “In [171], Russo and Zou introduced generalization error bounds (in expectation) that depend on the mutual information between the predictors and the labels.”