Generalization Error Analysis for FDR Controlled Classification

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 bounds for FDR and FNDR from the perspective of statistical learning theory. Unlike more conventional classification performance measures, the empirical FDR and FNDR are not binomial random variables but rather a ratio of binomials, which introduces several challenges not addressed in conventional analyses. We develop distribution-free uniform deviation bounds and apply these, in conjunction with the Borel-Cantelli lemma, to obtain a strongly consistent learning rule.