Structure–Adaptive Sequential Testing for Online False Discovery Rate Control

Abstract

Consider the online testing of a stream of hypotheses where a real-time decision must be made before the next data point arrives. The error rate is required to be controlled at all decision points. Conventional simultaneous testing rules are no longer applicable due to the more stringent error constraints and absence of future data. Moreover, the online decision-making process may come to a halt when the total error budget, or alpha-wealth, is exhausted. This work develops a new class of structure-adaptive sequential testing (SAST) rules for online false discovery rate (FDR) control. A key element in our proposal is a new alpha-investing algorithm that precisely characterizes the gains and losses in sequential decision making. SAST captures time varying structures of the data stream, learns the optimal threshold adaptively in an ongoing manner and optimizes the alpha-wealth allocation across different time periods. We present theory and numerical results to show that SAST is asymptotically valid for online FDR control and achieves substantial power gain over existing online testing rules.

Keywords:

• Alpha–investing
• Conditional local false discovery rate
• Covariate–assisted inference
• Structured multiple testing
• Time series anomaly detection

Supplementary material

The supplementary material contains the proofs of main theorems, other theoretical results and additional numerical results.

Notes

1 $\mathbb{T}$ may be taken either as $\{1,2,\dots ,T\}$ on a growing domain or a set of points that lie on a fixed-domain regular grid: $\{1/T,2/T,\dots ,(T-1)/T,1\}$ with $T\to \infty$.

2 As pointed out by a referee, (2) should be understood as the “average” FDR under the random mixture model (1); the expectation $\mathbb{E}$ is taken over both ${\mathit{\theta }}^t$ and ${\mathit{X}}^t$. Therefore, the “average” FDR is the correct understanding through which our theory may be properly conceptualized.

3 The asymptotic equivalence can be shown by following similar lines as done in Basu et al. (2018) for proving the equivalence between the marginal FDR and FDR. Empirically the two power measures yield almost identical patterns in our simulations.

4 In situations where the empirical null is more appropriate (Efron 2004), f₀ can be first estimated using the method in Jin and Cai (2007) and then treated as known.

5 In situations where the online FDR analysis must start without prior data, we suggest applying existing methods such as LOND first and then switch to SAST as more data are acquired.

6 Let T be a prespecified large integer denoting the number of tests we tentatively plan to conduct. The bandwidth h_T will be determined by T and fixed throughout the entire period, which is allowed to go beyond T. The choice of h_T is discussed in detail in Section 4.1. We recommend using the same h_T in both Equations (1)(1) $${\theta }_t\sim \text{Bernoulli}({\pi }_t),\hspace{1em}{X}_t|{\theta }_t\sim F_t=(1-{\theta }_t)F_0+{\theta }_t{F}_{1t},$$(1) and (2)(2) $${\text{FDR}}^t({\mathit{\delta }}^t)=\mathbb{E}\left\{\frac{\sum _{i\le t;i\in \mathbb{T}}(1-{\theta }_i){\delta }_i}{(\sum _{i\le t;i\in \mathbb{T}}{\delta }_i)\vee 1}\right\},$$(2) to stabilize the performance.

7 These prespecified regions serve as the proxies of the interested signals that we wish to discover.

Additional information

Funding

The research of Wenguang Sun was supported in part by NSF grant DMS-2015339.