Abstract

In the online false discovery rate (FDR) problem, one observes a possibly infinite sequence of pvalues P1 , P2 , . . . , each testing a different n pothesis, and an algorithm must pick a sequence of rejection thresholds , . . . in an onlin fashion, effectively rejecting the k-th null hypoth esis whenever . Importantly, must be a function of the past, and cannot depend on Pk or any of the later unseen p-values, and must be chosen to guarantee that for any time t, the FDR up to time t is less than some pre-determined quantity . In this work, we present a powerful new framework for online FDR control that we refer to as “SAFFRON”. Like older alphainvesting algorithms, SAFFRON starts off with an error budget (called alpha-wealth) that it intel ligently allocates to different tests over time, ea ing back some alpha-wealth whenever it makes a new discovery. However, unlike older methods, SAFFRON’s threshold sequence is based on a novel estimate of the alpha fraction that it allocates to true null hypotheses. In the offline setti algorithms that employ an estimate of the proportion of true nulls are called “adaptive”, hence SAFFRON can be seen as an online analogue of the offline Storey-BH adaptive procedure. Just as Storey-BH is typically more powerful than the Benjamini-Hochberg (BH) procedure under independence, we demonstrate that SAFFRON is also more powerful than its non-adaptive counterparts such as LORD. 1 Departments of Statistics and Electrical EngineerinComputer Sciences, University of California, Berkeley, Beley, USA 2 Department of Electrical Engineering and CompuSciences, University of California, Berkeley, Berkeley, Urespondence to: Aaditya Ramdas<aramdas@eecs.berkeley.eduTijana Zrnic