  Monte Carlo (MC) permutation test is considered the gold standard for
statistical hypothesis testing, especially when standard parametric assumptions
are not clear or likely to fail. However, in modern data science settings where
a large number of hypothesis tests need to be performed simultaneously, it is
rarely used due to its prohibitive computational cost. In genome-wide
association studies, for example, the number of hypothesis tests $m$ is around
$10^6$ while the number of MC samples $n$ for each test could be greater than
$10^8$, totaling more than $nm$=$10^{14}$ samples. In this paper, we propose
Adaptive MC multiple Testing (AMT) to estimate MC p-values and control false
discovery rate in multiple testing. The algorithm outputs the same result as
the standard full MC approach with high probability while requiring only
$\tilde{O}(\sqrt{n}m)$ samples. This sample complexity is shown to be optimal.
On a Parkinson GWAS dataset, the algorithm reduces the running time from 2
months for full MC to an hour. The AMT algorithm is derived based on the theory
of multi-armed bandits.
