New DOMT method slashes regret in online hypothesis testing
A regret-based framework unveils a smarter way to balance false positives and negatives.
Online multiple testing (OMT) is critical for sequential decision-making in ML pipelines—like A/B testing or anomaly detection—where false positives and false negatives carry asymmetric costs. Traditional OMT metrics like FDR and statistical power ignore this asymmetry. In a new paper, Hao, Zhou, Kong, and Wei introduce Weighted Regret, a unified metric that properly weights the cost of errors. They prove a Duality of Regret Conservation: any purely deterministic OMT procedure that strictly controls FDR must incur linear Ω(T) regret, because threshold depletion during signal-sparse periods causes massive false negatives.
To solve this, they propose Decoupled-OMT (DOMT), a meta-wrapper that injects a non-negative random perturbation in a history-decoupled manner. This rescues deterministic baselines from threshold depletion without sacrificing asymptotic FDR control. DOMT guarantees zero additional false negatives and achieves order-optimal Ω(√T) regret reduction in bursty signal environments. The paper also derives a "Cold-Start Tax" that characterizes the exact phase transition where DOMT beats deterministic methods. Experiments confirm DOMT consistently reduces empirical weighted regret, navigating the non-stationary Pareto frontier between error types.
- Introduces Weighted Regret metric to unify false positive and false negative costs in online multiple testing.
- Proves deterministic FDR-controlling procedures incur linear Ω(T) regret; DOMT reduces this to sublinear Ω(√T).
- DOMT preserves exact asymptotic safety and includes a rigorous finite-sample bound for cold-start scenarios.
Why It Matters
Better automated decision-making in real-time ML pipelines—fewer costly errors when signals are sparse.