Technical Summary: A Regret Perspective on Online Multiple Testing

1. Problem Statement

Online Multiple Testing (OMT) addresses the sequential inference problem where hypotheses arrive exogenously over time, requiring immediate, irrevocable decisions to reject or retain null hypotheses. Traditional OMT literature focuses on maintaining the False Discovery Rate (FDR) below a target level $\alpha$ while maximizing statistical power. However, the paper argues that evaluating FDR and power in isolation obscures the highly asymmetric costs of false positives (Type I errors) and false negatives (Type II errors) in modern automated pipelines.

The core issue identified is threshold depletion. In signal-sparse environments (e.g., "cold starts" or periods of pure noise), deterministic algorithms that strictly control FDR often deplete their testing capacity ($\alpha$-wealth), causing their decision thresholds to decay monotonically toward zero. This renders the algorithm "blind" to subsequent bursts of true signals, leading to massive missed discoveries. Conversely, algorithms attempting to maintain constant power risk incurring linear false positive penalties. The paper posits that existing paradigms fail to navigate the non-stationary Pareto frontier between these two error types.

2. Methodology

2.1 The Weighted Regret Metric

To unify the evaluation of FDR and power, the authors introduce Weighted Regret. Unlike traditional metrics that treat FDR (a conditional rate) and Power (a marginal probability) separately, Weighted Regret maps both error types into a single cumulative loss currency:
$$\text{Regret}_T(a, b) = a \cdot V_T + b \cdot M_T$$
where $V_T$ is the total number of false positives, $M_T$ is the total number of false negatives, and $a, b > 0$ are domain-specific penalty weights. The objective is to minimize the expected Weighted Regret relative to an omniscient Oracle.

2.2 The Duality of Regret Conservation

The paper establishes a fundamental theoretical limit termed the Duality of Regret Conservation. It proves that purely deterministic, history-dependent OMT procedures inevitably incur a linear regret penalty of $\Omega(T)$. This occurs via two distinct mechanisms:

1. The Power Barrier: Maintaining a minimum detection power requires a strictly positive threshold lower bound, which inevitably triggers a linear accumulation of false positives in stationary environments.
2. The FDR Barrier: Strictly controlling FDR via deterministic wealth management leads to threshold decay. In bursty environments (long periods of nulls followed by signals), this decay causes the threshold to vanish, resulting in a linear accumulation of false negatives.

Consequently, no purely deterministic algorithm can simultaneously achieve sublinear regrets for both error types.

2.3 The Decoupled-OMT (DOMT) Algorithm

To overcome the structural limits of deterministic mechanisms, the authors propose Decoupled-OMT (DOMT), a meta-wrapper algorithm designed to rescue deterministic baselines (e.g., LOND, LORD, SAFFRON) from threshold depletion.

Key Mechanism:
DOMT introduces a history-decoupled, strictly non-negative random perturbation to the decision threshold at each step $t$:
$$\lambda_t = \min(1, \lambda_t^{\text{base}} + \xi_t)$$
where $\lambda_t^{\text{base}}$ is the threshold dictated by the underlying deterministic procedure, and $\xi_t = \epsilon_t Z_t$ is the exploration term.

• Exploration Amplitude: $\epsilon_t = \kappa \frac{\alpha}{\sqrt{t}}$, decaying at an $O(t^{-1/2})$ rate.
• Randomness: $Z_t \sim \text{Uniform}[0, 1]$ is i.i.d.
• Causal Decoupling: Crucially, the internal state (wealth) of the base procedure is updated only using the virtual threshold $\lambda_t^{\text{base}}$ and the corresponding virtual decision. The actual decision uses $\lambda_t$, but the "noise" $\xi_t$ is mathematically quarantined from the base procedure's state updates.

Properties:

• Zero Additional False Negatives: Since $\xi_t \ge 0$, the rejection set of DOMT always subsumes that of the baseline ($R_t^{\text{DOMT}} \supseteq R_t^{\text{base}}$), guaranteeing no missed discoveries relative to the baseline.
• Asymptotic Safety: In stationary environments, the exploration noise is diluted by the accumulation of true discoveries, preserving the exact asymptotic FDR control of the base procedure.
• Finite-Sample Bounds: In extreme cold-starts (pure nulls), DOMT bounds the absolute number of additional false positives to $O(\sqrt{T})$, preventing catastrophic linear error accumulation.

3. Key Contributions

1. Metric Innovation: Introduction of Weighted Regret to explicitly balance asymmetric Type I and Type II errors, moving beyond isolated FDR/Power evaluation.
2. Theoretical Lower Bound: Proof of the Duality of Regret Conservation, establishing that purely deterministic algorithms incur an inevitable $\Omega(T)$ linear regret penalty due to the trade-off between constant vigilance (false positives) and threshold depletion (false negatives).
3. Algorithmic Solution: Proposal of DOMT, a plug-and-play meta-wrapper that uses strictly non-negative, history-decoupled stochastic exploration to mitigate threshold depletion without compromising asymptotic safety.
4. Regret Analysis: Proof that DOMT achieves an order-optimal $\Omega(\sqrt{T})$ reduction in Weighted Regret compared to deterministic baselines in bursty environments.
5. Phase Transition Characterization: Derivation of a closed-form "Cold-Start Tax" ($M^*$), a critical threshold for the penalty ratio $b/a$ that dictates when stochastic exploration becomes theoretically advantageous. This tax quantifies the cost of exploring during pure-noise periods.

4. Results

Theoretical Results

• Linear Regret of Determinism: Theorems 1 and 2 demonstrate that any deterministic algorithm either suffers linear false positive regret (if maintaining power) or linear false negative regret (if controlling FDR strictly) in non-stationary settings.
• Sublinear Regret of DOMT: Theorem 6 proves that under bursty signal models, DOMT reduces the expected Weighted Regret by $\Omega(\sqrt{T})$ compared to the baseline.
• Safety Guarantees: Theorem 3 confirms that DOMT inherits the asymptotic FDR control of its base procedure. Theorem 4 provides a finite-sample high-probability bound on False Discovery Proportion (FDP) inflation, showing it scales gracefully as $O(1/\sqrt{t})$ in stationary regimes and is strictly bounded in adversarial cold-starts.
• Optimality of Decay Rate: The paper argues that the $O(t^{-1/2})$ decay rate is structurally necessary. Faster decay (e.g., $O(t^{-1})$) would compress the exploration cost to $O(\log T)$ but would simultaneously choke discovery recovery to $O(\log T)$, failing to counter the baseline's $\Omega(T)$ deficit.

Empirical Results

Experiments were conducted on synthetic data and three real-world datasets (RNA-Seq microarrays, S&P 500 financial anomalies, and IMPC mouse phenotype data).

• Stationary Environments: DOMT maintains strict FDR control while consistently outperforming baselines in statistical power.
• Bursty/Cold-Start Environments: Deterministic baselines suffer from absolute threshold depletion, leading to near-zero power when signals finally arrive. DOMT successfully bridges these "mini-droughts," capturing delayed signal bursts and achieving a macroscopic reduction in false negatives.
• Pareto Frontier: Empirical results confirm that DOMT navigates the non-stationary Pareto frontier, achieving a macroscopic vertical reduction in false negatives by paying a strictly bounded horizontal tax in false discoveries.

5. Significance and Claims

The paper claims that the Weighted Regret perspective fundamentally shifts the optimization objective of OMT from constrained error control to unconstrained risk minimization. By proving the inevitability of linear regret in deterministic frameworks, the authors argue that stochastic exploration is not merely a heuristic but a mathematical necessity for navigating non-stationary environments.

The significance of DOMT lies in its ability to act as a universal meta-wrapper. It does not replace existing p-value or e-value procedures (like LOND, LORD, SAFFRON, or SCORE) but encapsulates them, rescuing them from the "zero-threshold deadlock" without violating their underlying super-martingale safety properties. The paper emphasizes that this approach allows for the "order-optimal" traversal of the Pareto frontier, securing a discovery dividend in high-stakes, asymmetric cost scenarios (e.g., medical screening, fraud detection) where missing a signal is catastrophic.

The authors conclude that while DOMT introduces a "Cold-Start Tax" (a temporary inflation of errors during pure-noise phases), this is a deliberate and bounded trade-off that prevents the systemic failure of deterministic algorithms, offering a robust solution for online inference in real-world, non-stationary data streams.