The theory behind onlineFDR

LOND

The LOND procedure controls the FDR for independent or positively dependent (PRDS) p-values. Given an overall significance level α, we choose a sequence of non-negative numbers β = (β_i)_{i ∈ ℕ} such that they sum to α. The values of the adjusted significance thresholds α_i are chosen as follows: α_i = β_i(D(i − 1) + 1) where $D(n) = \sum_{i=1}^n R_i$ denotes the number of discoveries (i.e. rejections) in the first n hypotheses tested.

LOND can be adjusted to also control FDR under arbitrarily dependent p-values. To do so, it is modified with β̃_i = β_i/H(i) in place of β_i, where $H(i) = \sum_{j=1}^i \frac{1}{j}$ is the i-th harmonic number. Note that this leads to a substantial loss in power compared to the unadjusted LOND procedure. The correction factor is similar to the classical one used by Benjamini and Yekutieli (2001), except that in this case the i-th hypothesis among N is penalised by a factor of H(i) to give consistent results across time (as compared to a factor H(N) for the Benjamini and Yekutieli method).

The default sequence of β is given by $$\beta_j = C \alpha \frac{\log(\max(j, 2))}{j e^{\sqrt{\log j}}}$$ where C ≈ 0.07720838, as proposed by Javanmard and Montanari (2018) equation 31.

LORD

The LORD procedure controls the FDR for independent p-values. We first fix a sequence of non-negative numbers γ = (γ_i)_{i ∈ ℕ} such that γ_i ≥ γ_j for i ≤ j and $\sum_{i=1}^{\infty} \gamma_i = 1$. At each time i, let τ_i be the last time a discovery was made before i: τ_i = max {l ∈ {1, …, i − 1} : R_l = 1}

LORD depends on constants w₀ and b₀, where w₀ ≥ 0 represents the initial ‘wealth’ of the procedure and b₀ > 0 represents the ‘payout’ for rejecting a hypothesis. We require w₀ + b₀ ≤ α for FDR control to hold.

Javanmard and Montanari (2018) presented three different versions of LORD, which have different definitions of the adjusted significance thresholds α_i. Versions 1 and 2 have since been superseded by the LORD++ procedure of Ramdas et al. (2017), so we do not describe them here.

• LORD++: The significance thresholds for LORD++ are chosen as follows: α_i = γ_iw₀ + (α − w₀)γ_{i − τ1} + α∑_{j : τj < i, τj ≠ τ1}γ_{i − τj}

• LORD 3: The significance thresholds depend on the time of the last discovery time and the wealth accumulated at that time, with α_i = γ_{i − τi}W(τ_i) where τ₁ = 0. Here {W(j)}_j ≥ 0 represents the ‘wealth’ available at time j, and is defined recursively:

$$ \begin{aligned} W(0) &= w_0 \\ W(j) &= W(j-1) - \alpha_{j-1} + b_0 R_j \end{aligned} $$

• D-LORD: This is equivalent to the LORD++ procedure with discarding. Given a discarding threshold τ ∈ (0, 1) and initial wealth w₀ ≤ τα the significance thresholds are chosen as follows: α_t = min {τ, α̃_t} where α̃_t = w₀γ_S^t + (τα − w₀)γ_{S^t − κ1^*} + τα∑_j ≥ 2γ_{S^t − κj^*} and κ_j = min {i ∈ [t − 1] : ∑_k ≤ i1{p_k ≤ α_k} ≥ j}, κ_j^* = ∑_{i ≤ κj}1{p_i ≤ τ}, S^t = ∑_i < t1{p_i ≤ τ}

LORD++ is an instance of a monotone rule, and provably controls the FDR for independent p-values provided w₀ ≤ α. LORD 3 is a non-monotone rule, and FDR control is only demonstrated empirically. In some scenarios with large N, LORD 3 will have a slightly higher power than LORD++ (see Robertson et al., 2018), but since it is a non-monotone rule we would recommend using LORD++ (which is the default), especially since it also has a provable guarantee of FDR control.

In all versions, the default sequence of γ is given by $$\gamma_j = C \frac{\log(\max(j, 2))}{j e^{\sqrt{\log j}}}$$ where C ≈ 0.07720838, as proposed by Javanmard and Montanari (2018) equation 31.

Javanmard and Montanari (2018) also proposed an adjusted version of LORD that is valid for arbitrarily dependent p-values. Similarly to LORD 3, the adjusted significance thresholds are set equal to α_i = ξ_iW(τ_i) where (assuming w₀ ≤ b₀), $\sum_{j=1}^{\infty} \xi_i (1 + \log(j)) \leq \alpha / b_0$

The default sequence of ξ is given by $$ \xi_j = \frac{C \alpha }{b_0 j \log(\max(j, 2))^3}$$ where C ≈ 0.139307.

Note that allowing for dependent p-values can lead to a substantial loss in power compared with the LORD procedures described above.

SAFFRON

The SAFFRON procedure controls the FDR for independent p-values, and was proposed by Ramdas et al. (2018). The algorithm is based on an estimate of the proportion of true null hypotheses. More precisely, SAFFRON sets the adjusted test levels based on an estimate of the amount of alpha-wealth that is allocated to testing the true null hypotheses.

SAFFRON depends on constants w₀ and λ, where w₀ satisfies 0 ≤ w₀ ≤ α and represents the initial ‘wealth’ of the procedure, and λ ∈ (0, 1) represents the threshold for a ‘candidate’ hypothesis. A ‘candidate’ refers to p-values smaller than λ, since SAFFRON will never reject a p-value larger than λ. These candidates can be thought of as the hypotheses that are a-priori more likely to be non-null.

The SAFFRON procedure runs as follows:

1. At each time t, define the number of candidates after the j-th rejection as $$ C_{j+} = C_{j+}(t) = \sum_{i = \tau_j + 1}^{t-1} C_i$$ where C_t = 1{p_t ≤ λ} is the indicator for candidacy.

2. SAFFRON starts with α₁ = min {(1 − λ)γ₁w₀, λ}. Subsequent test levels are chosen as α_t = min {λ, α̃_t}, where α̃_t = (1 − λ)[w₀γ_{t − C0+} + (α − w₀)γ_{t − τ1 − C1+} + α∑_j ≥ 2γ_{t − τj − Cj+}]

The default sequence of γ for SAFFRON is given by γ_j ∝ j^−1.6.

Alpha-investing

Ramdas et al. (2018) proposed a variant of the Alpha-investing algorithm of Foster and Stine (2008) that guarantees FDR control for independent p-values. This procedure uses SAFFRON’s update rule with the constant λ replaced by a sequence λ_i = α_i. This is also equivalent to using the ADDIS algorithm (see below) with τ = 1 and λ_i = α_i.

ADDIS

The ADDIS procedure controls the FDR for independent p-values, and was proposed by Tian & Ramdas (2019). The algorithm compensates for the power loss of SAFFRON with conservative nulls, by including both adaptivity in the fraction of null hypotheses (like SAFFRON) and the conservativeness of nulls (unlike SAFFRON).

ADDIS depends on constants w₀, λ and τ. w₀ represents the initial `wealth’ of the procedure and satisfies 0 ≤ w₀ ≤ α. τ ∈ (0, 1] represents the threshold for a hypothesis to be selected for testing: p-values greater than τ are implicitly ‘discarded’ by the procedure. Finally, λ ∈ [0, τ) sets the threshold for a p-value to be a candidate for rejection: ADDIS will never reject a p-value larger than λ.

The significance thresholds for ADDIS are chosen as follows: α_t = min {λ, α̃_t} where α̃_t = (τ − λ)[w₀γ_{S^t − C0+} + (α − w₀)γ_{S^t − κ1^* − C1+} + α∑_j ≥ 2γ_{S^t − κj^* − Cj+} and $$ \kappa_j = \min\{i \in [t-1] : \sum_{k \leq i} 1 \{p_k \leq \alpha_k\} \geq j\}, \; \kappa_j^* = \sum_{i \leq \kappa_j} 1 \{p_i \leq \tau \}, \; S^t = \sum_{i < t} 1 \{p_i \leq \tau \}, \; C_{j+} = \sum_{i = \kappa_j + 1}^{t-1} 1\{p_i \leq \lambda\} $$

The default sequence of γ for ADDIS is the same as for SAFFRON given here.

Alpha-spending

The Alpha-spending procedure controls the FWER for a potentially infinite stream of p-values using a Bonferroni-like test. Given an overall significance level α, the significance thresholds are chosen as α_i = αγ_i where $\sum_{i=1}^{\infty} \gamma_i = 1$ and γ_i ≥ 0. The procedure strongly controls the FWER for arbitrarily dependent p-values.

Note that the procedure also controls the generalised familywise error rate (k-FWER) for k > 1 if α is replaced by min (1, kα).

The default sequence of γ is the same as that for ξ for LORD given here.

Online Fallback

The online fallback procedure of Tian & Ramdas (2019b) provides a uniformly more powerful method than Alpha-spending, by saving the significance level of a previous rejection. More specifically, online fallback tests hypothesis H_i at level α_i = αγ_i + R_i − 1α_i − 1 where R_i = 1{p_i ≤ α_i} denotes a rejected hypothesis. The procedure strongly controls the FWER for arbitrarily dependent p-values.

The default sequence of γ is the same as that for ξ for LORD given here.

ADDIS-spending

The ADDIS-spending procedure strongly controls the FWER for independent p-values, and was proposed by Tian & Ramdas (2021). The procedure compensates for the power loss of Alpha-spending, by including both adapativity in the fraction of null hypotheses and the conservativeness of nulls.

ADDIS depends on constants λ and τ, where λ < τ. Here τ ∈ (0, 1) represents the threshold for a hypothesis to be selected for testing: p-values greater than τ are implicitly `discarded’ by the procedure, while λ ∈ (0, 1) sets the threshold for a p-value to be a candidate for rejection: ADDIS-spending will never reject a p-value larger than λ.

Note that the procedure controls the generalised familywise error rate (k-FWER) for k > 1 if α is replaced by min (1, kα). Tian and Ramdas (2019b) also presented a version for handling local dependence, see the Section on Asynchronous testing below.

The default sequence of γ for ADDIS-spending is the same as for SAFFRON given here.