Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits
Adaptive Monte Carlo Multiple Testing via Multi-Armed Bandits
复制标题
DOI：
--
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Martin Jinye Zhang;James Y. Zou;David Tse
中科院分区：
文献类型：
--
作者：
Martin Jinye Zhang;James Y. Zou;David Tse
蒙特卡罗（MC）排列检验被认为是统计假设检验的黄金标准，特别是当标准参数假设不明确或可能失败时。然而，在需要同时执行大量假设检验的现代数据科学环境中，由于其高昂的计算成本，很少使用它。例如，在全基因组关联研究中，假设检验的数量$m$约为$10^6$，而每个检验的MC样本数量$n$可能大于$10^8$，总计超过$nm$=$10^{14}$个样本。在本文中，我们提出了自适应MC多重测试（AMT）估计MC的p值和控制错误发现率在多重测试。该算法输出相同的结果作为标准的全MC方法具有很高的概率，而只需要$\tilde{O}（\sqrt{n}m）$样本。该样本复杂度被证明是最佳的。在Parkinson GWAS数据集上，该算法将完整MC的运行时间从2个月减少到1个小时。基于多臂强盗理论推导了AMT算法。
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.