Online Rules for Control of False Discovery Rate and False Discovery\n Exceedance

Multiple hypothesis testing is a core problem in statistical inference and\narises in almost every scientific field. Given a set of null hypotheses\n$\\mathcal{H}(n) = (H_1,\\dotsc, H_n)$, Benjamini and Hochberg introduced the\nfalse discovery rate (FDR), which is the expected proportion of false positives\namong rejected null hypotheses, and proposed a testing procedure that controls\nFDR below a pre-assigned significance level. Nowadays FDR is the criterion of\nchoice for large scale multiple hypothesis testing. In this paper we consider\nthe problem of controlling FDR in an "online manner". Concretely, we consider\nan ordered --possibly infinite-- sequence of null hypotheses $\\mathcal{H} =\n(H_1,H_2,H_3,\\dots )$ where, at each step $i$, the statistician must decide\nwhether to reject hypothesis $H_i$ having access only to the previous\ndecisions. This model was introduced by Foster and Stine. We study a class of\n"generalized alpha-investing" procedures and prove that any rule in this class\ncontrols online FDR, provided $p$-values corresponding to true nulls are\nindependent from the other $p$-values. (Earlier work only established mFDR\ncontrol.) Next, we obtain conditions under which generalized alpha-investing\ncontrols FDR in the presence of general $p$-values dependencies. Finally, we\ndevelop a modified set of procedures that also allow to control the false\ndiscovery exceedance (the tail of the proportion of false discoveries).\nNumerical simulations and analytical results indicate that online procedures do\nnot incur a large loss in statistical power with respect to offline approaches,\nsuch as Benjamini-Hochberg.\n