PaperlayerView exact revision on arXiv

Source-linked AI summary

How much does your data exploration overfit? Controlling bias via information usage

Daniel Russo, James Zou

arXiv:1511.05219v3stat.MLcs.LG

TL;DR

Adaptive data exploration can make standard statistical estimates biased because analyses and reported results are chosen using the same data. The paper develops a mutual-information framework to quantify and bound this bias and other errors, analyzes common exploration procedures, and motivates randomization to reduce bias while preserving utility.

  • Problem

    Adaptive exploration can produce false discoveries and biased reported estimates, while standard statistical theory assumes analyses are chosen independently of the data.

  • Method

    The paper measures information usage as mutual information between estimation noise and the selected result, then uses it to bound exploration bias and other error metrics.

  • Results

    The framework gives tight bounds in natural settings and identifies when filtering, rank selection, clustering, and other exploration procedures do or do not produce substantial bias.

  • Takeaways & Limitations

    Information usage can guide analysis of exploration bias and motivate randomization that reduces mutual information and hence bias while preserving analytic utility.

Abstract

from arXiv · show

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 %the adaptive nature of exploration 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 reduces 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.

I. INTRODUCTION

Adaptive exploration can make reported estimates biased because earlier data-dependent choices shape later analyses and the final reported result. The paper formalizes this risk through information usage, bounding exploration bias and related errors while analyzing when common procedures are more or less biased.

  • Adaptive exploration lets observed data influence subsequent tests and reported results, creating researcher degrees of freedom, false discoveries, and biased estimates.
  • Bob’s sequential visualization, filtering, and maximum-correlation selection illustrates why adaptivity complicates standard statistical analysis and can inflate reported correlations.
  • The paper measures bad information usage as mutual information between estimation noise and the choice of reported result.
  • The framework analyzes filtering, visualization, rank selection, and randomization strategies for reducing exploration bias.
  • Information usage bounds bias, absolute error deviation, and squared error, and lower bounds error in broader settings including maximum selection.

V. WHEN IS BIAS LARGE OR SMALL? THE VIEW FROM INFORMATION USAGE

Information usage provides a unified way to assess how common feature-selection and estimation procedures produce substantial or limited selection bias. The analysis focuses on which data structures and selection rules make mutual information smaller than its worst-case value.

  • The framework evaluates common feature-selection and parameter-estimation procedures by measuring their information usage and resulting selection bias.

A. Filtering by marginal statistics

Bias from filtering depends on the information shared between the selection statistics and the reported estimators, not simply on how much the selection uses the dataset. Variance filtering can therefore have no bias when empirical means and variances are independent.

  • Selection based on statistics loosely coupled with reported estimators can have information usage far below the selection entropy and therefore lower bias.
  • Variance filtering chooses markers with the largest empirical variance to identify features with potentially informative mean values.
  • For iid Gaussian samples, empirical means and variances are independent, yielding I(T; φ) = 0 and no bias from variance selection.
  • Filtering selects features using one marginal statistic while estimating bias in another, so data-processing inequalities can bound the relevant information usage.
  • For a k-point subsample from n iid observations, the contraction coefficient is bounded by ηψφ ≤ k/n.

B. Bias due to data visualization

Information usage explains why exploratory selection can be biased and why stronger signal or more selected features can reduce that bias in the studied procedures. The framework also applies beyond simple rank selection to clustering and LARS.

  • Clustering: Clustering can be informative without increasing exploration bias when its selected cluster count is strongly concentrated.In that setting, I(K; φ) is bounded by H(K), which is approximately zero.
  • Rank selection: As signal strength increases, selection entropy and the information bound decrease, while the bias of the selected estimate also decreases.The simulation uses m = 1000 estimates, one with mean µ and the others with mean zero, across µ ∈[1, 4].
  • LARS: LARS provides a more complex selection example because it composes a sequence of maximum selections.The experiments compare low, medium, and high signal-to-noise settings.
  • LARS: For LARS, increasing signal lowers both information usage and bias, while increasing the number of selected features lowers average per-feature information usage and bias monotonically.The study estimates information usage by bootstrapping and computes bias from the known experimental ground truth.

G. Approximately independent data splitting.

The paper studies how delaying estimation after selection in a stationary, mixing Markov process can control information usage and bias. It also connects post-selection estimation error to the reliability of variable-selection procedures, including FDR control.

  • Data splitting: Selection and estimation are separated by discarding a middle segment of Markov-chain data, with a sufficient delay intended to reduce bias and overfitting.The first segment is used for selection, the third for estimation, and the middle segment is discarded.
  • Data splitting: Under the assumed stationary, time-homogeneous, uniformly mixing process, a sufficient delay between selection and estimation guarantees low bias.The mixing condition controls dependence between observations as the delay increases.
  • FDR control: The framework bounds post-selection estimation bias and error using the false discovery rate and type I and type II error rates.This is formulated for variables selected through multiple-hypothesis testing procedures.
  • FDR control: The selected-variable estimates can be analyzed through E[φ_T − µ_T], E[|φ_T − µ_T|], and E[(φ_T − µ_T)^2].Conditioned on the data, T is drawn uniformly from the selected variables, and information usage I(T; φ) bounds these quantities.
  • FDR control: When false discovery, type I, and type II error rates are small, information usage is low and the resulting estimation-error bounds are small.The bounds grow smoothly as the selection procedure becomes less reliable.

VI. LIMITING INFORMATION USAGE AND BIAS VIA RANDOMIZATION

The paper uses randomization to reduce information usage and exploration bias, including when the analyst’s multi-step procedure is flexible or difficult to characterize. Simulations and adaptive-query analysis show that this reduction trades off against accuracy and that noise can limit bias as exploration continues.

  • A. Regularization via randomized selection: Randomization reduces information usage and bias by making selection more stable, while preserving a useful analysis output.The maximum-entropy or Gibbs distribution is relatively insensitive to small changes in candidate statistics and is also known as exponential weights or the exponential mechanism.
  • A. Regularization via randomized selection: Max-entropy selection significantly decreased bias, but its accuracy depended on signal strength and was lower than rank selection in the intermediate regime.With N1 = 1000, n−N1 = 100000, β = 2, and µ varying from 1 to 5, both methods had low accuracy at µ = 1; for µ ≥4, accuracy was close to one for both.
  • A. Regularization via randomized selection: The Gibbs mechanism does not reduce bias or information usage for every data-generating distribution because randomization can increase H(T).Its information usage is strictly below the worst-case value log(m) when the Gibbs distribution is nondegenerate, but this does not guarantee improvement for all distributions.
  • B. Randomization for a multi-step analyst: For a flexible multi-step analyst, adding noise at each step can keep bad information usage low without requiring the analyst’s selection procedure to be known.Bounding the conditional mutual information of each response and query bounds the information usage and bias after k adaptive rounds.
  • B. Randomization for a multi-step analyst: Adaptive exploration becomes more error-prone over time: later queries have increasing error, whereas nonadaptive noisy-free responses achieve error at most σ/√n.The factor k1/4 represents a worst-case price of adaptivity, and without noise error can reach Ω(σ√(k/n)).

VII. DISCUSSION

The discussion presents mutual information as a general way to quantify exploration bias and motivate randomization, while noting that tighter procedures and practical implementations remain open directions. The framework is intended to complement more specialized post-selection inference and differential privacy methods.

  • VII. DISCUSSION: Mutual information quantifies exploration bias and also bounds other error metrics, including average absolute error.The same information usage appears in lower bounds on error, suggesting a fundamental connection to exploration bias.
  • VII. DISCUSSION: The framework reveals when common analysis procedures produce severe bias and motivates adding randomization to reduce mutual information and bias.The paper specifically notes that signal in the data can reduce selection bias and that mutual-information tools support analysis and computation.
  • VII. DISCUSSION: Information usage complements post-selection inference and differential privacy, combining broader applicability with a different level of specialization.Post-selection inference can exactly characterize bias in specific settings, while the paper positions information usage as a general framework.
  • VII. DISCUSSION: The framework’s bias metric should reflect whether the dataset has high or low signal, and combining its generality with sharper methods remains an open goal.The discussion identifies the development of practical randomization approaches and tighter approximations for broader exploration procedures as future work.

APPENDIX A OVERVIEW OF THE APPENDIX

The appendix supplies proofs and extensions for information-usage bounds on selection bias. It generalizes the framework to unequal variances and sub-exponential estimators, while noting cases where the mutual-information bound can be loose.

  • Proof strategy: Proposition 1’s proof uses a variational characterization of Kullback–Leibler divergence to bound selection bias through information usage.The argument applies the characterization conditionally to each selected estimator and aggregates over the selection rule.
  • Proof strategy: The information-processing inequality can make the mutual-information upper bound loose when the selection rule depends on one estimator but selects among independent others.In that setting, I(T; φ) can be positive even though the selected estimator’s conditional distribution is unchanged and the bias is zero.
  • Extensions: Proposition 8 extends the selection-bias bound to estimators with unequal sub-Gaussian scales σ_i.The appendix replaces a common noise scale with estimator-specific parameters.
  • Extensions: Proposition 9 extends information-usage bounds from sub-Gaussian to sub-exponential estimation errors.The appendix gives an additional bound when the estimators have sub-exponential parameters (σ, b), including a second form when b < 1.

D. Extension to Other Metrics of Exploration Error

This section extends information-usage analysis beyond mean bias to other exploration-error metrics. It treats absolute error, squared error, and distributional change between selection on common data and an independent replication.

  • Proof strategy: The extension relies on showing that centered absolute deviations of sub-Gaussian variables remain sub-Gaussian.The proof applies this property together with Proposition 1 and the data-processing inequality.
  • Error metrics: The same framework controls mean squared distance between the reported estimate φ_T and its true value μ_T.The argument applies sub-exponential control to squared sub-Gaussian deviations.
  • Replication error: Proposition 10 bounds the KL divergence between a selected estimate computed on common data and the corresponding estimate drawn independently from its marginal distribution.This divergence captures distributional change caused by selecting and estimating on the same dataset.

APPENDIX C INFORMATION USAGE ALSO LOWER BOUNDS BIAS

This appendix establishes lower bounds showing that information usage is not merely an upper-bound device for exploration bias. For Gaussian maximum selection, entropy and selection structure characterize settings where squared error grows with information usage.

  • Lower-bound tightness: A randomized grouped-max policy has expected selected value no greater than ordinary maximum selection and converges to σ√(2 log(m/m0)).The policy partitions m estimates into m0 groups, selects each group maximum, then randomly chooses one group leader.
  • Gaussian max selection: Proposition 3 gives Gaussian max-selection bounds with universal constants c1 = 1/8, c2 < 2.5, c3 = 10, and c4 = 1.5.The result considers T = arg max1≤i≤m φ_i for φ ∼ N(μ, I).
  • Gaussian max selection: For natural Gaussian max-selection problems, E[(φ_T − μ_T)^2] = Θ(1 + H(T)).The intuition is that selecting a rare maximum requires the selected estimate to exceed the typical maximum of the alternatives.
  • Proof strategy: The proof decomposes the entropy of the maximizing index according to whether competing maxima are separated from an estimator’s mean by at least one standard deviation.This decomposition supports the lower bound while the corresponding upper bound follows from Proposition 2.

C. Threshold Selection with Gaussian Random Variables

The section studies threshold-based selection for Gaussian estimates and shows that information usage can lower-bound squared-loss bias. The result applies when thresholds are sufficiently high relative to competing exceedances and mean differences.

  • Bias lower bound: Unless the Gaussian estimates are very highly correlated, the expected number of competing threshold exceedances decreases as M increases, allowing H(T) to dominate the lower-bound relation.The dependence structure affects how quickly competing exceedances disappear.
  • Threshold policy: The Gaussian threshold policy reports a uniformly random estimate above M when one exists, and otherwise reports a fixed estimate.The analysis tracks the number of competing estimates that exceed the threshold.
  • Bias lower bound: For sufficiently high thresholds, entropy H(T) lower-bounds the square-loss bias E[(Z_T − μ_T)^2].The threshold must be high enough that only a few estimates are expected to pass it.
  • Exponential extension: The framework also extends the threshold-selection argument to shifted exponential estimates under the condition M − max λ_i ≥ 4 + 2 log(1 + N̂(M)).The exponential case uses tail probabilities of the form P(φ_i > M) = e^−(M−λ_i).

APPENDIX D INFORMATION USAGE AND CLASSIFICATION

The appendix applies information usage to classification overfitting and adaptive hypothesis selection. It shows how mutual information quantifies selection-dependent error and the risk of reporting unusually small p-values.

  • Classification: The classification overfitting problem is represented by selecting among distinct training predictions and bounding the expected gap between empirical and expected loss.The framework indexes candidate classifiers by their predictions on the training examples and analyzes the selected classifier through information usage.
  • Small p-values: Adaptive selection among hypotheses can produce extremely small reported p-values even when all null hypotheses are true.The paper uses this setting to quantify false-discovery risk under data-dependent hypothesis selection.
  • Small p-values: Selecting the smallest of m independent uniform p-values yields E[φT] = 1/(m + 1), so the expected reported value decreases as the number of hypotheses grows.The reported minimum p-value is therefore of order 1/m.
  • Information usage: For m ≈e^B hypotheses, p-values around ϵ ≈e^-B are expected, while mutual information replaces log(m) with a data-dependent measure of selection usage.The bound extends this reasoning to arbitrary adaptive selection procedures.
  • Information usage: I(T; Zϵ) measures dependence between selection and extremely small p-values, and can be substantially smaller than I(T; φ) when hypotheses are correlated.Here Zϵ records whether each p-value falls below ϵ.

B. Regret Analysis and the Value of Information

This section studies regret from choosing actions without knowing an uncertain parameter and relates adaptive fitting to information usage. It also describes a Gaussian simulation framework for measuring selection bias in LARS.

  • Regret Analysis: The value of perfect information is the expected improvement from resolving uncertainty about the unknown parameter before choosing an action.The corresponding decision problem selects an action from a finite set to maximize an uncertain function.
  • Regret Analysis: The paper bounds Bayes risk using mutual information between the unknown parameter and the action that maximizes the uncertain objective.The true maximizer is random because it depends on the random parameter.
  • LARS Experiments: In the LARS experiments, increasing the signal level changes the signal-to-noise setting while the selected feature sequence is measured along the full LARS path.The design uses 100 observations, 1000 features, and signals in the first 20 coefficients.
  • LARS Experiments: LARS overfitting is quantified as the difference between noisy and true univariate regression coefficients for each feature entering the selected sequence.The true coefficients use noiseless outcomes, whereas the noisy coefficients use the observed outcomes.
  • Adaptive Fitting: Under a zero-mean Gaussian distribution, adaptive measurements can reveal the sample mean and enable choosing a unit vector aligned with it despite zero population correlation.This illustrates how adaptive fitting can create a large observed inner product from noise.

APPENDIX I MUTUAL-INFORMATION VS MAX-INFORMATION

The appendix contrasts mutual information with max-information for adaptive selection. It argues that mutual information tracks selection bias in the rank-selection example, whereas max-information can scale oppositely from bias.

  • Comparison: Max-information controls error for worst-case adaptive analysts, but can behave counter-intuitively for specific selection procedures.The appendix revisits rank selection to compare the two information measures.
  • Mutual Information: As signal strength increases, rank-selection bias decreases because the selected index concentrates on the true signal and becomes less adaptive.The mutual-information bound decreases with this concentration.
  • Max-information: Max-information can increase as signal strength increases even while selection bias decreases.This opposite scaling limits its interpretability as a direct measure of bias in this setting.
  • Max-information: With no signal, max-information is minimized under inappropriate rank selection; as the analyst increasingly identifies the true signal, max-information grows toward infinity.The appendix attributes this behavior to the increasing probability of selecting the true-signal index.
  • Approximate Max-information: Approximate max-information can also become large when selection probabilities depart from uniformity, including for indices corresponding to true nulls.The behavior depends on the selection-probability distribution and the chosen level β.
Loading 1511.05219v3…