In modern data science, from large-scale A/B testing at tech companies to real-time genomic monitoring, we rarely have the luxury of waiting for all data to arrive before making a decision. Instead, we face a stream of hypotheses that must be accepted or rejected immediately. This "online" setting breaks the assumptions of classical multiple testing procedures like the Benjamini-Hochberg (BH) or Bonferroni corrections, which require a fixed, pre-defined set of tests.
The challenge is to maintain a strict limit on false positives—specifically the False Discovery Rate (FDR)—while maximizing the "power" to detect real effects. The breakthrough in this field, led by researchers like Aaditya Ramdas and Tijana Zrnic, involves treating the significance level ($\alpha$) as a form of "wealth" that can be spent, earned, and adaptively reallocated based on the results of previous tests.
The Alpha-Wealth Metaphor
The foundational intuition for online testing is the concept of an error budget. As described by D. S. Robertson and James Wason in Online multiple hypothesis testing, a researcher starts with an initial "alpha-wealth."
Every time a hypothesis is tested, a small amount of this wealth is "spent" by setting a significance threshold. If the test results in a rejection (a discovery), the researcher "earns" back some wealth, which can then be used to fund future tests. If the test fails to reject, the wealth is lost. This mechanism ensures that the FDR is controlled over an infinite horizon, even if the researcher doesn't know how many tests they will eventually perform.
Overcoming Conservatism through Adaptivity
Early online algorithms were often too conservative because they assumed a "worst-case" scenario: that every single hypothesis being tested is a true null (i.e., there is no real effect to find). In practice, many hypotheses in a stream might be true signals.
The core innovation in recent work is adaptive null-proportion estimation. By dynamically estimating the proportion of true null hypotheses ($\pi_0$) during the testing process, algorithms can become more aggressive when they detect a high density of signals. As Djalel Eddine Meskaldji and colleagues argue in A comprehensive error rate for multiple testing, integrating these estimates into threshold "shape functions" bridges the gap between overly cautious corrections and permissive procedures.
SAFFRON and the Power of Discarding
A landmark algorithm in this space is SAFFRON, introduced by Aaditya Ramdas, Tijana Zrnic, and others in SAFFRON: an Adaptive Algorithm for Online Control of the False Discovery Rate.
SAFFRON’s intuition is simple: if a p-value is very large (e.g., $p > 0.5$), it is almost certainly a "null" result. Rather than spending a full portion of the alpha-budget on these obvious duds, SAFFRON uses a discarding mechanism. By identifying and "ignoring" these conservative nulls, the algorithm reclaims the error budget that would have been wasted. This allows it to set higher thresholds for more promising candidates later in the stream, significantly increasing discovery power.
This concept was further refined in the ADDIS algorithm (ADDIS: an adaptive discarding algorithm for online FDR control with conservative nulls), where Jinjin Tian and Aaditya Ramdas showed that discarding p-values above a certain threshold prevents "conservative nulls" from inflating the error estimate, allowing for even more efficient budget allocation.
Robustness via E-values
While p-values are the traditional currency of testing, they struggle with complex data dependencies. To solve this, researchers have moved toward e-values—a more robust alternative that measures the evidence against a null hypothesis.
In Online multiple testing with e-values, Aaditya Ramdas and Ziyu Xu introduced e-LOND, which controls FDR under any dependency structure without the need for conservative "reshaping" penalties. This evolution continued with the e-GAI framework (e-GAI: e-value-based Generalized $\alpha$-Investing for Online False Discovery Rate Control), which combines e-values with "Risk Aversion Investing" to achieve high discovery power in real-world scenarios where data points are often correlated.
Why It Works
The success of these methods lies in their ability to learn the environment. By treating the stream of hypotheses not as a sequence of isolated events, but as a distribution that can be modeled, these algorithms:
- Preserve Budget: They avoid spending significance on "obvious" nulls.
- Reinvest Success: They use discoveries to fuel further exploration.
- Adapt to Signal Density: They increase their sensitivity when they find themselves in a "target-rich" environment.
As summarized in The Power of Batching in Multiple Hypothesis Testing by Tijana Zrnic and colleagues, this adaptive approach allows modern researchers to maintain the rigorous error control of classical statistics while operating at the speed and scale of the digital age.