ADDIS: an adaptive discarding algorithm for online FDR control with conservative nulls
This addresses a practical bottleneck in large-scale sequential A/B testing for internet companies, offering a robust solution for conservative nulls, though it is incremental in improving adaptive algorithms.
The authors tackled the problem of reduced power in online false discovery rate (FDR) control algorithms when null p-values are conservative, introducing ADDIS, which provably controls FDR and achieves appreciable power increase over existing methods in such cases while rarely losing power under ideal uniform nulls.
Major internet companies routinely perform tens of thousands of A/B tests each year. Such large-scale sequential experimentation has resulted in a recent spurt of new algorithms that can provably control the false discovery rate (FDR) in a fully online fashion. However, current state-of-the-art adaptive algorithms can suffer from a significant loss in power if null p-values are conservative (stochastically larger than the uniform distribution), a situation that occurs frequently in practice. In this work, we introduce a new adaptive discarding method called ADDIS that provably controls the FDR and achieves the best of both worlds: it enjoys appreciable power increase over all existing methods if nulls are conservative (the practical case), and rarely loses power if nulls are exactly uniformly distributed (the ideal case). We provide several practical insights on robust choices of tuning parameters, and extend the idea to asynchronous and offline settings as well.