The false discovery rate for statistical pattern recognition

Clayton Scott, Gowtham Bellala, Rebecca Willett

Abstract

The false discovery rate (FDR) and false nondiscovery rate (FNDR) have received considerable attention in the literature on multiple testing. These performance measures are also appropriate for classification, and in this work we develop generalization error analyses for FDR and FNDR when learning a classifier from labeled training data. Unlike more conventional classification performance measures, the empirical FDR and FNDR are not binomial random variables but rather a ratio of binomials, which introduces challenges not addressed in conventional analyses. We develop distribution-free uniform deviation bounds and apply these to obtain finite sample bounds and strong universal consistency.

Introduction

In standard statistical classification, the primary objective is typically to minimize the overall probability of error. However, in many high-stakes applications—such as medical diagnostics, landmine detection, or fraud identification—the costs associated with different types of errors are not symmetric. While cost-sensitive learning addresses this by weighting false positives and false negatives differently, it usually evaluates performance on a point-by-point basis.

In practice, we often classify large batches of data simultaneously. If a classifier maintains a 5% false positive rate but is applied to a population where the target event is extremely rare, the vast majority of "discoveries" (positive predictions) may actually be false alarms. In these contexts, the False Discovery Rate (FDR)—the proportion of positive predictions that are incorrect—is a far more critical metric. Despite its prevalence in classical multiple hypothesis testing, FDR has lacked a rigorous theoretical foundation within the machine learning framework. This research bridges that gap by providing the first generalization error analysis for FDR and its counterpart, the False Nondiscovery Rate (FNDR).

The Challenge of Ratio-Based Metrics

The difficulty in analyzing FDR within learning theory stems from its mathematical structure. Standard classification metrics are typically averages of independent random variables, allowing for the direct application of concentration inequalities like Hoeffding’s or McDiarmid’s. In contrast, the empirical FDR is a ratio of two random variables: the number of false positives divided by the total number of positive predictions.

Because the denominator (the total number of discoveries) is itself a random variable that depends on the specific classifier chosen, standard "off-the-shelf" generalization bounds cannot be applied. If the number of discoveries is small, the variance of the FDR estimate becomes extremely high, making it difficult to guarantee that the performance measured on training data will generalize to unseen data.

Methodology and Theoretical Framework

To overcome the ratio-dependency problem, this work introduces several novel theoretical tools:

1. Novel Concentration Inequalities

The authors employ a conditioning argument to stabilize the ratio. By fixing the number of discoveries, they can apply Hoeffding-style bounds to the numerator and then use a union bound over all possible discovery counts. This allows for the derivation of uniform deviation bounds that hold across an entire class of candidate classifiers.

2. Data-Dependent Penalties

The framework introduces a "complexity tax" or penalty term, denoted as $\phi$. Unlike traditional penalties that only consider the complexity of the classifier (e.g., VC-dimension or codelength), these penalties are data-dependent. Specifically, they account for the number of discoveries a classifier makes. A classifier that makes many discoveries is penalized less because the larger denominator provides more statistical evidence to trust the estimated error rate.

3. The "Yield" Requirement

A unique aspect of this framework is the definition of FDR as infinity if a classifier makes zero discoveries. While this seems counterintuitive, it serves a vital mathematical purpose: it prevents the learning algorithm from selecting "trivial" classifiers that predict negative for every instance to avoid false positives. This forces the algorithm to prioritize classifiers that provide a meaningful "yield" of discoveries.

Key Theoretical Results

The paper establishes three primary theorems that provide the foundation for FDR-controlled learning:

  • Theorem 1 (Uniform Deviation Bounds): This provides a mathematical guarantee that, with high probability, the true FDR of a classifier will not deviate from its training-set FDR by more than a calculable margin, even when searching through a large set of potential models.
  • Theorem 2 (Universal Consistency): The authors prove that their proposed learning rule is "strongly universally consistent." This ensures that as the sample size $n$ grows toward infinity, the algorithm is guaranteed to converge to the optimal Bayes performance for any underlying distribution.
  • Theorem 3 (Constrained Learning): The research provides a framework for "Neyman-Pearson" style classification. This allows practitioners to minimize one error (like FNDR) while rigorously guaranteeing that the FDR remains below a pre-specified target (e.g., $\alpha = 0.05$) with high confidence.

Discussion and Implications

This work has significant implications for the use of Precision-Recall curves in industry. Since FDR is essentially $1 - \text{Precision}$ and FNDR is closely related to $1 - \text{Recall}$, these results represent some of the first rigorous generalization bounds for the metrics most commonly used to evaluate information retrieval and detection systems.

However, some limitations remain. The current proofs are optimized for "countable" sets of classifiers, such as decision trees of fixed depth or histogram-based learners. Extending these bounds to "uncountable" classes, such as deep neural networks with continuous weights, remains an open challenge. The standard "ghost sample" trick used in VC-dimension theory is not directly applicable here because the number of discoveries can fluctuate significantly between the training sample and the ghost sample. Additionally, while the paper defines the criteria for optimal classifiers, the resulting optimization problems are non-convex, suggesting a need for specialized algorithmic solvers in future implementations.

Summary updated

Abstract

The false discovery rate (FDR) and false nondiscovery rate (FNDR) have received considerable attention in the literature on multiple testing. These performance measures are also appropriate for classification, and in this work we develop generalization error analyses for FDR and FNDR when learning a classifier from labeled training data. Unlike more conventional classification performance measures, the empirical FDR and FNDR are not binomial random variables but rather a ratio of binomials, which introduces challenges not present in conventional formulations of the classification problem. We develop distribution-free uniform deviation bounds and apply these to obtain finite sample bounds and strong universal consistency. We also present a simulation study demonstrating the merits of variance-based bounds, which we also develop. In the context of multiple testing with FDR/FNDR, our framework may be viewed as a way to leverage training data to achieve distribution free, asymptotically optimal inference under the random effects model.
BibTeX
@inproceedings{scott2009false,
  author = {Clayton Scott and Gowtham Bellala and Rebecca Willett},
  title = {{The false discovery rate for statistical pattern recognition}},
  booktitle = {Electronic},
  year = {2009},
  doi = {10.1214/09-ejs363},
}
Figure