Sharp multiple testing boundary for sparse sequences

Abstract

This work investigates multiple testing by considering minimax separation rates in the sparse sequence model, when the testing risk is measured as the sum FDR+FNR (False Discovery Rate plus False Negative Rate). First using the popular beta-min separation condition, with all nonzero signals separated from $0$ by at least some amount, we determine the sharp minimax testing risk asymptotically and thereby explicitly describe the transition from "achievable multiple testing with vanishing risk" to "impossible multiple testing". Adaptive multiple testing procedures achieving the corresponding optimal boundary are provided: the Benjamini--Hochberg procedure with a properly tuned level, and an empirical Bayes $\ell$-value (`local FDR') procedure. We prove that the FDR and FNR make non-symmetric contributions to the testing risk for most optimal procedures, the FNR part being dominant at the boundary. The multiple testing hardness is then investigated for classes of arbitrary sparse signals. A number of extensions, including results for classification losses and convergence rates in the case of large signals, are also investigated.

arXiv commentRevision extending the noise models permitted and allowing for "strong signal" settings. 33 pages (main body) or 86 (including supplement). 4 figures

References in corpus (11)

• Higher criticism for detecting sparse heterogeneous mixtures
• Needles and straw in haystacks: Empirical Bayes estimates of possibly sparse sequences
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Confidence sets in sparse regression
• Properties of higher criticism under strong dependence
• Covariate powered cross-weighted multiple testing
• Optimal weighting for false discovery rate control
• Type I error rate control for testing many hypotheses: a survey with proofs
• Lower bounds in multiple testing: A framework based on derandomized proxies
• Empirical Bayes cumulative $\ell$-value multiple testing procedure for sparse sequences
• Optimality of the max test for detecting sparse signals with Gaussian or heavier tail