Fast confidence bounds for the false discovery proportion over a path of hypotheses

This paper introduces an efficient $O(|\mathcal K|m)$ algorithm that rapidly computes a complete curve of post hoc false discovery proportion bounds along a path of increasing selection sets by leveraging the forest structure of the reference family and the incremental nature of adding single hypotheses.

The Gist

Imagine you are a detective trying to solve a massive crime scene with 10,000 clues (hypotheses). You have a list of suspects, and you want to know which ones are actually guilty. However, you know that if you just pick the "most suspicious" looking clues, you might accidentally accuse some innocent people.

In statistics, this is called Multiple Testing. The "False Discovery Proportion" (FDP) is simply the percentage of innocent people you accidentally accuse among the ones you picked.

The Old Problem: The Slow, Exhaustive Search

Traditionally, statisticians have a tool to say, "I am 95% sure that among the top 100 clues you picked, no more than 10 are innocent." This is a confidence bound.

However, calculating this bound is like trying to count the number of red cars in a parking lot by walking through the lot, stopping at every single car, checking its color, and then starting over from the beginning every time you want to know the count for the next 100 cars.

If you want to see how the "safety guarantee" changes as you pick 1 clue, then 2 clues, then 3, all the way to 10,000, the old method is incredibly slow. It's like doing the same math homework problem 10,000 times, but each time you have to re-solve the first 9,999 problems from scratch. It takes hours or even days.

The New Solution: The "Forest" and the "Fast Tracker"

This paper introduces a new, lightning-fast algorithm that changes the game. The author, Guillermo Durand, uses a clever trick based on how the clues are organized.

1. The Forest Metaphor

Imagine your 10,000 clues aren't just a flat list. They are organized like a family tree or a forest.

• The Leaves: Individual clues (e.g., "Gene A").
• The Branches: Groups of clues (e.g., "All genes in the Liver").
• The Trunks: Huge groups (e.g., "All genes in the Human Body").

The key insight is that these groups are nested. A "Liver" group is inside the "Human" group, but it never overlaps with a "Brain" group in a messy way. They are either separate or one is inside the other. This structure is called a Forest Structure.

2. The "Pruning" Trick (Cutting the Dead Wood)

Before you even start counting, the new algorithm looks at the forest and says, "Hey, this big branch is so huge that it doesn't matter for our safety guarantee; we can ignore it."
It prunes the forest, cutting away unnecessary branches. It's like a gardener trimming a hedge to remove dead wood so the remaining plants are easier to manage. This makes the forest smaller and faster to navigate.

3. The "Inflation" Counter (The Fast Tracker)

Now, imagine you are walking through this trimmed forest, picking clues one by one.

• The Old Way: Every time you pick a new clue, you stop, walk through the entire forest again, and recount everything.
• The New Way: You have a counter for every branch in the forest.
  • When you pick a clue, you just walk up the tree to the branches that contain that clue and add 1 to their counters.
  • If a branch's counter hits a "limit" (a safety threshold), you mark that branch as "full" and stop counting inside it.
  • Because you only update the counters for the specific path the new clue takes, you don't need to re-scan the whole forest. You just update a few numbers.

The Result: From Hours to Seconds

The paper demonstrates that this new method is 33,000 times faster than the old way.

• Old Way: If it took 5 minutes to calculate the safety for 100 clues, calculating it for 10,000 clues would take years.
• New Way: It takes a fraction of a second to calculate the safety for the entire path from 1 clue to 10,000 clues.

Why Does This Matter?

In real life, scientists use this for things like:

• Genomics: Finding which genes cause a disease among thousands of candidates.
• Brain Imaging: Finding which parts of the brain light up during a task.

With the old method, scientists often had to stop halfway through their analysis or guess the results because the computer was too slow. With this new "Fast Confidence Bounds" algorithm, they can see the entire curve of results instantly. They can say, "If I pick the top 50 genes, I'm safe. If I pick the top 500, I'm still safe. If I pick 1,000, I need to be careful."

Summary Analogy

Think of the old method as re-weighing a whole truckload of apples every time you add one new apple to the pile to see if it's too heavy.

The new method is like having a smart scale that knows exactly how much each apple weighs. When you add a new apple, it just adds that apple's weight to the total and updates the display instantly. It's the difference between moving mountains and moving a pebble.

This paper gives statisticians the "smart scale," allowing them to explore massive datasets with confidence, speed, and precision.

Technical Summary

Here is a detailed technical summary of the paper "Fast confidence bounds for the false discovery proportion over a path of hypotheses" by Guillermo Durand.

1. Problem Statement

In multiple hypothesis testing, particularly in exploratory fields like genomics and neuroimaging, researchers often need to control the False Discovery Proportion (FDP) post-hoc. Unlike the False Discovery Rate (FDR), which controls the expected proportion of errors, FDP control provides a confidence upper bound on the actual number of false discoveries ($V(S)$) for any selection set $S$ chosen after observing the data.

The paper addresses a specific computational bottleneck:

• Context: The bounds are constructed using a Reference Family $\mathcal{R} = \{(R_k, \zeta_k)\}_{k \in K}$, where $R_k$ are regions of hypotheses and $\zeta_k$ are over-estimators of the number of true nulls in those regions.
• Structure: These regions often possess a forest structure (regions are either disjoint or nested), which allows for efficient computation of the bound $V^*_{\mathcal{R}}(S)$ for a single set $S$.
• The Challenge: In practice, users often want to evaluate the bound along a path of increasing selection sets (e.g., $S_t = \{ \text{indices of the } t \text{ smallest p-values} \}$ for $t=1, \dots, m$).
• Current Limitation: The existing algorithm (Durand et al., 2020) computes $V^*_{\mathcal{R}}(S)$ in $O(|K||S|)$ time. Repeatedly applying this to a path of $m$ sets results in a total complexity of $O(|K|m^2)$, which is computationally prohibitive for large-scale simulations or real-time analysis.

2. Methodology

The paper proposes two main algorithmic innovations to reduce the complexity of computing the entire curve of bounds $(V^*_{\mathcal{R}}(S_t))_{t=1}^m$ from quadratic to linear in $m$.

A. Forest Pruning (Algorithm 2)

Before computing bounds, the reference family can be simplified without altering the final bound values.

• Logic: If a region $R_k$ has a bound $\zeta_k$ that is greater than or equal to the sum of the bounds of its immediate sub-regions (children in the forest), $R_k$ is redundant. It never contributes to the minimum calculation in the bound formula.
• Action: The algorithm traverses the forest from the bottom up. If $\zeta_k \geq \sum \zeta_{children}$, the region $k$ is removed (pruned).
• Benefit: This reduces the cardinality of the family $|K|$, speeding up both single evaluations and curve computations. It runs in $O(|K|)$ time.

B. Fast Curve Computation (Algorithms 3 & 4)

The core contribution is a new algorithm that leverages the incremental nature of the selection path ($S_{t+1} = S_t \cup \{i_{t+1}\}$).

• Key Insight: Instead of recomputing the bound from scratch for each $S_t$, the algorithm maintains a state of "saturated" regions.
• Mechanism:
  1. Counters: For each region $R_k$, a counter $\eta_k$ tracks how many selected hypotheses fall within it.
  2. Saturation: As hypotheses are added to the selection set, $\eta_k$ increments. Once $\eta_k$ reaches the region's bound $\zeta_k$, the region is considered "saturated."
  3. Partition Update: When a region saturates, it is moved to a set $K^-$ (regions that no longer contribute to the bound calculation) and the partition $P_t$ (which realizes the minimum in the bound formula) is updated.
  4. Incremental Update: For the next step $t+1$, the algorithm only needs to check if the new hypothesis $i_{t+1}$ falls into a saturated region.
     • If $i_{t+1}$ is in a saturated region, the bound $V^*_{\mathcal{R}}(S_{t+1})$ remains unchanged.
     • If not, the bound increases by exactly 1.
• Complexity: The algorithm processes each of the $m$ steps in $O(H)$ time (where $H$ is the maximum depth of the forest), leading to a total complexity of $O(|K|m)$ (or $O(Hm)$), a significant improvement over $O(|K|m^2)$.

3. Key Contributions

1. Theoretical Proof: The paper provides rigorous proofs (Section 7) that the new incremental algorithm correctly computes the exact same confidence bounds as the original method, utilizing the properties of the forest structure and the Joint Error Rate (JER) control.
2. Algorithmic Efficiency:
   • Introduced a Pruning method to minimize the reference family size.
   • Developed a Fast Curve Algorithm that reduces computational complexity by a factor of $m$ (from quadratic to linear).
3. Implementation: All algorithms are implemented in the R package sanssouci. The paper details the data structures used (lists of lists representing the forest and atoms) and provides R code snippets for usage.
4. Empirical Validation: Numerical experiments demonstrate massive speedups. In Scenario 3 (10,240 hypotheses), the new fast algorithm with pruning was 33,000 times faster than the naive repeated application of the old algorithm.

4. Results

• Complexity Reduction: The complexity dropped from $O(|K|m^2)$ to $O(|K|m)$.
• Performance Gains:
  • Scenario 1 ($m=1024$): Fast algorithm took ~0.001s vs. ~3.8s for naive approach (Speedup $\approx$ 3000x).
  • Scenario 3 ($m=10240$): Fast algorithm took ~0.01s vs. ~337s for naive approach (Speedup $\approx$ 33,000x).
• Pruning Impact: Pruning significantly reduced the number of regions in scenarios with "trivial" bounds (where $\zeta_k = |R_k|$), often reducing the family to just the leaf nodes (atoms).

5. Significance

• Feasibility of Simulation Studies: Previously, simulating multiple testing procedures with full curve evaluation was computationally intractable for large $m$. For example, a previous study (Durand et al., 2020) could only compute 0.078% of the curve for $m=12,800$. This new method makes it possible to compute 100% of the curve with adequate replication numbers, enabling robust power analysis and method validation.
• Practical Application: The method facilitates real-time or interactive analysis in fields like GWAS and fMRI, where researchers need to visualize how the FDP bound evolves as they select more significant features.
• Generalizability: While focused on forest structures, the approach highlights the potential for incremental updates in post-hoc inference, a concept applicable to other hierarchical testing frameworks.

In summary, this paper transforms the computation of post-hoc FDP bounds from a computationally expensive, single-point operation into a highly efficient, continuous process, unlocking new possibilities for large-scale exploratory data analysis.