SAFFRON: an adaptive algorithm for online control of the false discovery rate

1 Introduction

• Testing many hypotheses can produce chance false discoveries, and controlling each test’s false-positive rate separately does not guarantee high precision among discoveries.FDR procedures address this by controlling the expected false-discovery proportion.Source: §1 · p. 1
• Online thresholds must be chosen without future test outcomes, and fixed thresholds such as 0.05 do not control FDR.Future hypotheses may depend on current outcomes.Source: §1 · p. 2
• SAFFRON allocates alpha-wealth using an estimate of the true-null proportion, and simulations show advantages over non-adaptive methods such as LORD and alpha-investing.Figure 1 compares power and FDR versus the fraction of non-null hypotheses at target FDR α = 0.05.Source: §1 · p. 2, Figure 1 · p. 2

2 Deriving the SAFFRON algorithm

• Null p-values are super-uniform, and the derivation also considers conditional super-uniformity as a weaker condition for guarantees.Under the marginal condition, a true-null p-value satisfies Pr{P_i ≤ u} ≤ u.Source: §2 · p. 3

2.1 An oracle estimate of the FDP and a naive overestimate

• The oracle FDP estimate uses the unknown true-null set; bounding it by α at every time implies mFDR control and, under independence and monotonicity, FDR control.The oracle estimate overestimates the FDP, but cannot be calculated directly because the true-null set is unknown.Source: §2.1 · p. 3

2.2 A better estimate of the alpha-wealth spent on testing nulls

• The LORD estimate can be overly conservative when non-nulls are non-negligible, so SAFFRON estimates null-spent alpha using p-values above a threshold λ.The scaled indicator has unit expectation for uniform null p-values and typically smaller expectation for non-nulls.Source: §2.2 · p. 4
• Under conditional super-uniformity, bounding the new estimate by α gives mFDR control; FDR control additionally requires independence and monotonicity conditions.The mFDR guarantees can support use in settings with conditionally super-uniform, dependent p-values, including the cited MAB-FDR framework.Source: §2.2 · pp. 4–5

2.3 The SAFFRON algorithm for constant λ

• For constant λ, SAFFRON allocates thresholds from initial alpha-wealth and a discount sequence, using candidate p-values and past rejections in its updates.The method never spends wealth testing candidate p-values and gains wealth on rejections except the first.Source: §2.3 · p. 5
• SAFFRON’s power depends on λ and the discount sequence; without assumptions on signal frequency, strength, or order, no choice is universally optimal.The paper discusses reasonable default choices in its experimental section.Source: §2.3 · p. 5

2.4 A monotone update rule for SAFFRON with predictable λt

• For predictable time-varying λ_t, the update rule requires thresholds and λ_t to be monotone functions of past rejections and candidacies.Choosing λ_t as a non-decreasing function of α_t that is at least α_t is sufficient for monotonicity, but not necessary.Source: §2.4 · pp. 5–6

3.1 Alpha-investing (AI)

• The monotone SAFFRON-AI variant controls FDR under independence and performs comparably to, or sometimes better than, original AI in simulations.Its monotonicity also yields more stable α_j allocations across tuning choices.Source: §3.1 · p. 6, Figure 2 · p. 7

3.2 Storey-BH

• Storey-BH estimates the unknown null proportion and controls FDR; simulations found it typically more powerful than BH, especially with more non-nulls and stronger signals.This is the offline adaptive-procedure comparison that motivates SAFFRON’s connection to adaptive testing.Source: §3.2 · p. 7
• Storey-BH is to BH as SAFFRON is to LORD: each adaptive method seeks a better estimate than the corresponding procedure’s crude oracle-FDP bound.Offline Storey-BH estimates the null proportion, while SAFFRON estimates alpha-wealth spent testing nulls.Source: §3.2 · p. 7
• With constant λ = 1/2, SAFFRON is more powerful than LORD across varied signal proportions and strengths, and can compete with non-adaptive online methods.The authors describe it as arguably the first adaptive online algorithm to do so.Source: §3.2 · p. 8

3.3 Accumulation tests, like SeqStep

• SAFFRON can also be viewed as an online analogue of adaptive SeqStep, using an accumulation function to estimate FDP and obtain mFDR control.The text notes that alternative non-decreasing accumulation functions are possible, though initial experiments found no advantage over the step function.Source: §3.3 · p. 8

4.1 Testing with Gaussian observations

• As the non-null fraction grows, SAFFRON’s power rises faster than LORD’s and it performs considerably better than LORD and alpha-investing when non-nulls are numerous.The Gaussian comparison uses the highest-performing sequence among six considered for SAFFRON and LORD.Source: §4.1 · p. 9, Figure 5 · p. 10

4.2 Testing with beta alternatives

• With beta alternatives, SAFFRON performs similarly to LORD and alpha-investing at low non-null fractions, then significantly outperforms them in power and uses available wealth more at higher fractions.The alternatives follow Beta(0.5, 5).Source: §4.2 · p. 11, Figure 8 · p. 12

4.3 SAFFRON with constant λ vs SAFFRON alpha-investing

• For Gaussian tests, neither SAFFRON variant is a consistent winner: performance depends on the discount sequence, signal strength, and non-null proportion.The comparison uses λ=1/2 versus λ_j=α_j and Gaussian alternatives with means 2 and 3.Source: §4.3 · p. 13, Figure 11 · p. 13, Figure 12 · p. 14
• For beta alternatives, λ=1/2 uniformly outperforms the alpha-investing variant across the tested discount sequences and non-null proportions.The comparison is shown for beta alternatives in Figure 13.Source: §4.3 · p. 13, Figure 13 · p. 14

5 Proofs

• The section provides proofs of Proposition 1, Theorem 1, and SAFFRON’s monotonicity.Source: §5 · p. 15

5.1 Proof of Proposition 1

• Under the stated assumptions, the proof establishes the proposition’s error bounds, using conditional super-uniformity and, for FDR control, independence and monotone levels.Source: §5.1 · p. 15

5.2 A reverse super-uniformity lemma

• For independent p-values and coordinate-wise non-decreasing test and candidacy levels, Lemma 2 gives a reverse super-uniformity result; its proof sets the tested p-value to one.Source: §5.2 · pp. 15–16

5.3 Proof of Theorem 1

• Theorem 1’s proof establishes mFDR(t) ≤ α and uses independence, monotonicity, and Lemma 2 for its additional claims.Source: §5.3 · p. 17

5.4 Proof of Lemma 1

• The update rule makes αt and λt coordinate-wise non-decreasing in past rejections and candidates when λt = ht(αt) for non-decreasing ht with ht(x) ≥ x.Source: §5.4 · pp. 17–18

• SAFFRON is a new algorithmic framework for online mFDR and FDR control.Source: §6 · p. 18
• Empirically, SAFFRON is more powerful than existing algorithms.Source: §6 · p. 18
• A reverse super-uniformity lemma underlies the derivation and proof, allowing estimation of the alpha-wealth fraction spent testing null hypotheses.Source: §6 · p. 18
• SAFFRON is interpretable as an adaptive version of LORD, and its framework recovers a monotone alpha-investing version that often is more stable and powerful and controls FDR, unlike the original’s mFDR-only control.Source: §6 · p. 18
• The derivation differs from earlier generalized alpha-investing algorithms and provides a template for deriving new algorithms.Source: §6 · p. 18