Multiple testing with anytime-valid Monte-Carlo p-values

In contemporary problems involving genetic or neuroimaging data, thousands of hypotheses need to be tested. Due to their high power, and finite sample guarantees on type-I error under weak assumptions, Monte-Carlo permutation tests are often considered as gold standard for these settings. However, the enormous computational effort required for (thousands of) permutation tests is a major burden. Recently, Fischer and Ramdas (2024) constructed a permutation test for a single hypothesis in which the permutations are drawn sequentially one-by-one and the testing process can be stopped at any point without inflating the type-I error. They showed that the number of permutations can be substantially reduced (under null and alternative) while the power remains similar. We show how their approach can be modified to make it suitable for a broad class of multiple testing procedures and particularly discuss its use with the Benjamini-Hochberg procedure. The resulting method provides valid error rate control and outperforms all existing approaches significantly in terms of power and/or required computational time. We provide fast implementations and illustrate its application on large datasets, both synthetic and real.