Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits

arXiv1902.00197MaRDI QIDQ6313408

Author name not available (Why is that?)

Publication date: 1 February 2019

Abstract: 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 $ildeO(sqrtnm)$ 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.

Has companion code repository: https://github.com/martinjzhang/AMT

This page was built for publication: Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313408)