Timezone: »

Oral
SAFFRON: an Adaptive Algorithm for Online Control of the False Discovery Rate
Aaditya Ramdas · Tijana Zrnic · Martin Wainwright · Michael Jordan

Thu Jul 12 08:00 AM -- 08:20 AM (PDT) @ A6
In the online false discovery rate (FDR) problem, one observes apossibly infinite sequence of $p$-values $P_1,P_2,\dots$, each testinga different null hypothesis, and an algorithm must pick a sequence ofrejection thresholds $\alpha_1,\alpha_2,\dots$ in an online fashion,effectively rejecting the $k$-th null hypothesis whenever $P_k \leq\alpha_k$. Importantly, $\alpha_k$ must be a function of the past, andcannot depend on $P_k$ or any of the later unseen $p$-values, and mustbe chosen to guarantee that for any time $t$, the FDR up to time $t$is less than some pre-determined quantity $\alpha \in (0,1)$. In thiswork, we present a powerful new framework for online FDR control thatwe refer to as SAFFRON''. Like older alpha-investing algorithms,SAFFRON starts off with an error budget (called alpha-wealth) that itintelligently allocates to different tests over time, earning backsome alpha-wealth whenever it makes a new discovery. However, unlikeolder methods, SAFFRON's threshold sequence is based on a novelestimate of the alpha fraction that it allocates to true nullhypotheses. In the offline setting, algorithms that employ an estimateof the proportion of true nulls are called adaptive'', henceSAFFRON can be seen as an online analogue of the offlineStorey-BH adaptive procedure. Just as Storey-BH is typically morepowerful than the Benjamini-Hochberg (BH) procedure underindependence, we demonstrate that SAFFRON is also more powerful thanits non-adaptive counterparts such as LORD.