跳转至

Multiple testing with anytime-valid Monte Carlo p-values

作者: Lasse Fischer, Timothy Barry, Aaditya Ramdas
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么： 这个子方向要解决的根本统计问题是：在大规模多重假设检验（如基因组学、神经影像学中同时检验成千上万个假设）场景下，如何在使用计算代价极高的蒙特卡洛（MC）置换检验时，既保证假发现率（FDR）的严格控制，又避免不必要的计算开销。当前该方向的成熟度处于“理论框架已建立，但与自适应计算的结合刚刚破冰”的阶段：经典的 BH 等多重检验程序对 p 值的独立性或特定依赖结构有严格要求，而为了节省计算引入的自适应停止规则会破坏这些结构，从而产生理论与计算之间的张力。本文正是试图在“anytime-valid（随时有效/序贯）”这一新理论框架下缝合这一张力。

发展脉络（history）： 1. 奠基工作（固定 B 的 MC 置换与多重检验）：Besag & Clifford (1991) 提出了经典的序贯 MC 置换检验框架，允许在固定停止规则下提前停止以节省计算；Benjamini & Hochberg (1995) 建立了基于 p 值的 FDR 控制范式。这些工作留下了“计算固定、p 值结构固定”的口子。 2. 主要进展（MC 多重检验的计算优化）：Gandy & Hahn (2012, 2014) 提出了 MMCTest 框架，旨在通过序贯抽样使得 MC 抽样的多重检验决策（拒绝/接受）与使用真实 p 值的决策“以高概率一致”，但该框架的停止规则仍是预设的，且不处理 p 值依赖对 FDR 的影响；Zhang, Zou & Tse (2019) 引入多臂老虎机（MAB）视角的 AMT 方法，将样本复杂度降至 \(\tilde{O}(\sqrt{n}m)\)，但其目标是“以高概率复现固定 B 的结果”，并未从根本上改变 p 值的统计定义。 3. 当前 frontier（Anytime-valid 与 Betting）：Ramdas 等人推动的 Safe/Anytime-valid inference（Howard et al. 2018; Grünwald et al. 2019; Ramdas et al. 2022; Ramdas & Wang 2024）将检验重塑为 test martingale 与 e-value，允许在任意数据驱动的停止时间下保持 I 型误差控制。Fischer & Ramdas (2024) 将此思想具体化到 MC 置换检验，提出了基于 betting 的 anytime-valid MC p-value，解决了“序贯抽样+任意停止”下的有效性问题，但仅限于单重检验。 4. 本文的位置：本文将 Fischer & Ramdas (2024) 的 anytime-valid MC p-value 嵌入到 BH 等通用多重检验程序中，允许每个假设的置换次数完全由数据自适应决定，并在由此产生的 p 值依赖结构下证明了 FDR 控制。

子线索聚类： - 线索 A：MC 多重检验的计算加速（保证决策一致性）。核心工作：Gandy & Hahn (2012, 2014) 的框架与 MMCTest 算法；Zhang et al. (2019) 的 AMT（MAB 方法）。这一簇在做的：如何用最少的 MC 样本使得多重检验的拒绝集与“使用极限 p 值”的拒绝集以高概率相同。 - 线索 B：Anytime-valid / Safe inference（保证序贯有效性）。核心工作：Howard et al. (2018) 的 confidence sequences；Grünwald et al. (2019) 的 s-value；Ramdas et al. (2022) 的 SAVI 框架；Fischer & Ramdas (2024) 的 anytime-valid MC test。这一簇在做的：如何在任意未预设的停止时间下保持 I 型误差与置信序列的有效性，核心工具是 test martingale 与 betting。 - 线索 C：多重检验的 FDR 控制理论（处理 p 值依赖）。核心工作：Benjamini & Yekutieli (2001) 对正依赖条件(PRD)的证明；Finner et al. (2009) 对更宽依赖条件的探讨；Genovese & Wasserman (2006) 的 FDP exceedance control。这一簇在做的：在 p 值不独立时，BH 程序在什么条件下仍能控制 FDR。

这个方向在追问的核心问题： 1. 如何定义 MC p 值使得它在任意数据自适应停止下仍然有效？（当前主流：基于 test martingale / e-value 的 anytime-valid p-value；瓶颈：如何构造针对置换原假设的 test martingale）。 2. 当多重检验中每个 p 值的停止时间不同且依赖于各自数据时，p 值之间产生复杂依赖，BH 等程序如何保证 FDR？（当前主流：假设 PRD 或独立；瓶颈：自适应停止导致的依赖结构既非独立也非标准 PRD）。 3. 计算与统计的 trade-off 是否可以无代价地打破？（即：能否在“零功率损失”与“严格 FDR 控制”的前提下，将计算量从 \(O(Bm)\) 降至接近“只对非拒绝假设做少量抽样”的水平？）。

⚠️ 作者的 framing： - 作者的说法：作者将缺口 frame 为“现有的 MC 加速方法（如 AMT、MMCTest）只能保证与固定 B 决策的‘高概率一致性’，而非统计有效性；且它们不支持完全数据驱动的停止。Anytime-valid p-value 解决了单检验的有效性，但尚未被整合进多重检验的 FDR 控制中”。这使得本文成为“显然的下一步”：把 anytime-valid p-value 填进 BH 的框架。 - 被淡化或回避的竞争路线：作者淡化了 AMT (Zhang et al. 2019) 在“高概率一致性”下的样本复杂度最优性（\(\tilde{O}(\sqrt{n}m)\)），只强调其不能“任意停止”；同时，作者回避了 closed testing / TDP 控制路线（如 Vesely et al. 2021, Goeman & Solari 2011），这条路线在置换检验下也能提供有效推断，且不依赖 p 值的 PRD 假设，但计算代价更高。 - 明显该被引却未出现的：Benjamini & Yekutieli (2001) 是处理 BH 在非独立 p 值下 FDR 控制的最经典工作（引入 PRD 条件），intro 中未直接引用它来定位依赖条件，而是引用了 Finner et al. (2009) 等较边缘的依赖处理工作。此外，针对 MC p 值依赖的早期理论工作（如 Besag & Clifford 的序贯框架在多重检验中的直接理论对接）也未见梳理。值得研究者去查的问题：本文的依赖条件是否实质上弱于或等价于 B&Y (2001) 的 PRD？如果是等价，那本文的 FDR 证明可能只是 PRD 条件的一个特例应用。

张力： 未见明显对立引用。各路线（MAB加速 vs. anytime-valid vs. FDR依赖理论）目前是互补而非矛盾，但存在隐含张力：MAB 路线追求“与固定 B 决策一致”，而 anytime-valid 路线追求“与极限 p 值的统计性质一致”，两者在原假设下的 I 型误差保证逻辑不同（前者是近似，后者是精确）。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号与指标：
  • \(m\)：同时检验的假设总数（维数/样本量指标）。
  • \(B\)：蒙特卡洛置换的总次数（若固定抽样）。
  • \(b \in \{1, \dots, B\}\)：置换抽样的序号。
  • \(H_i^0\)：第 \(i\) 个原假设（\(i \in \{1, \dots, m\}\)）。
  • \(\tau_i\)：第 \(i\) 个检验的停止时间（随机变量，表示对该假设停止置换抽样的时刻）。
  • \(\alpha\)：目标 FDR 水平（参数）。
  • \(p_i^{\text{perm}}\)：第 \(i\) 个假设的极限置换 p 值（不可观测的参数/estimand，定义为 \(P(T \geq t_i | \mathcal{X})\)，其中 \(T\) 为置换统计量，\(t_i\) 为观测统计量）。
  • \(\hat{p}_i\)：第 \(i\) 个假设的 anytime-valid MC p 值（随机变量，由序贯抽样过程生成）。
  • \(S_i(b)\)：第 \(i\) 个假设在第 \(b\) 次置换后的 test martingale（非负鞅，初始值为 1）。

  • \(e_i(b)\)：第 \(i\) 个假设在第 \(b\) 次置换后的 e-value（即 \(S_i(b)\) 本身，或其变换）。

  • 模型（数据生成机制）： 对于每个假设 \(H_i^0\)，存在一个观测数据集 \(\mathcal{X}_i\)。在 \(H_i^0\) 下，\(\mathcal{X}_i\) 满足某种置换不变性（exchangeability）。研究者通过置换 \(\mathcal{X}_i\) 生成 \(b\) 个新数据集 \(\mathcal{X}_i^{(1)}, \dots, \mathcal{X}_i^{(b)}\)，计算相应的置换统计量 \(T_i^{(1)}, \dots, T_i^{(b)}\)。这些置换统计量在 \(H_i^0\) 下与观测统计量 \(t_i\) 同分布。单次抽样结果 \(X_{i,b} = \mathbb{I}(T_i^{(b)} \geq t_i)\) 是一个伯努利随机变量，在 \(H_i^0\) 下其期望为 \(p_i^{\text{perm}}\)。

  • 可观测数据： 研究者实际能观测到的是：对每个假设 \(i\)，一个序贯生成的伯努利序列 \((X_{i,1}, X_{i,2}, \dots, X_{i,\tau_i})\)，以及停止规则 \(\tau_i\)（由数据自适应决定，如“当 test martingale 超过阈值 \(1/\alpha\) 时停止”）。不可观测/想要但观测不到的：极限置换 p 值 \(p_i^{\text{perm}}\)（需要无限次置换才能精确获得），以及各假设之间数据的真实联合依赖结构。

第二步：讲最小内核

整篇论文的证明本质上是“在独立假设下，使用 anytime-valid p-value 的自适应停止 BH 程序控制 FDR”这一特例的推广（放宽独立性到特定依赖结构）。因此，最简特例是：\(m\) 个假设的数据完全独立，且每个假设的停止时间 \(\tau_i\) 仅依赖于该假设自己的置换序列。

在这个最简特例下，核心思路如下： 1. 构造 anytime-valid p-value：对每个假设 \(i\)，基于伯努利序列 \(X_{i,1}, \dots\) 构造 test martingale \(S_i(b)\)。例如，使用最简单的 binomial mixture strategy：\(S_i(b) = \sum_{k=0}^b \binom{b}{k} p_i^{\text{perm}}^k (1-p_i^{\text{perm}})^{b-k} \prod_{j=1}^b (1 + \lambda_j (X_{i,j} - p_i^{\text{perm}}))\)（此处简化为：在 \(H_i^0\) 下，\(E[X_{i,b}]=p_i^{\text{perm}}\)，betting strategy 选择 \(\lambda\) 使得 \(S_i(b)\) 是期望为 1 的鞅）。定义 anytime-valid p-value 为 \(\hat{p}_i = \inf_{b \geq 1} S_i(b)^{-1}\)（或类似基于 e-value 的变换）。 2. 自适应停止：设定停止规则 \(\tau_i = \inf\{b : S_i(b) \geq 1/\alpha_i\}\)。在 \(H_i^0\) 下，由鞅的 Markov 不等式，\(P(\inf_{b} S_i(b) \geq 1/\alpha_i) \leq \alpha_i\)，因此 \(\hat{p}_i \leq \alpha_i\) 的概率 \(\leq \alpha_i\)，保证了单检验的 I 型误差。 3. 嵌入 BH 程序：将 \(m\) 个 \(\hat{p}_i\) 排序，寻找阈值 \(k\) 使得 \(\hat{p}_{(k)} \leq \frac{k}{m}\alpha\)。 4. 为什么 FDR 成立（最简特例下的证明内核）：在独立数据且 \(\tau_i\) 仅依赖局部数据的条件下，\(\hat{p}_i\) 之间相互独立。此时，BH 瞬时条件（Simes condition）自然满足。FDR 的证明退化回经典的 BH 证明：\(FDR = E[\frac{V}{R \vee 1}] = \sum_{i \in \mathcal{H}_0} P(\hat{p}_i \leq \frac{k}{m}\alpha) \leq m_0 \frac{k}{m}\alpha / k \leq \frac{m_0}{m}\alpha\)。关键在于，尽管 \(\hat{p}_i\) 不是经典的 \(p_i^{\text{perm}}\)，但 anytime-valid 性质保证了 \(P(\hat{p}_i \leq c) \leq c\) 对任意常数 \(c\) 成立（甚至对随机阈值也成立，这依赖于鞅的 optional stopping theorem），这使得 \(\hat{p}_i\) 在 BH 的 Simes 步骤中扮演了与真实 p 值相同的角色。

一般情形的“加壳”：当假设间数据存在依赖，且停止时间 \(\tau_i\) 可能依赖于其他假设的数据时，\(\hat{p}_i\) 之间不再独立，甚至不满足 PRD。本文的技术难点在于：证明在一种特定的“条件独立/混合依赖”结构下，基于 anytime-valid p-value 的 BH 程序仍然满足 Simes 瞬时条件（或其变体），从而控制 FDR。

三、这篇论文做了什么

三句话： ①研究了在大规模多重检验中，如何使用 anytime-valid MC p-value 替代经典置换 p-value 以实现数据自适应停止，从而大幅降低计算量；②核心工具是基于 test martingale 构造的 anytime-valid p-value 以及对 BH 程序在自适应停止下依赖结构的重新刻画；③主要结论是：在温和的依赖假设下，该自适应停止的多重检验程序能严格控制 FDR，且在真实基因组数据上将计算时间从三天以上降至不到四分钟，同时拒绝了更多假设。

关键设定与假设： 在第二节最小记号的基础上补全： - Anytime-valid MC p-value 的定义：\(\hat{p}_i = \inf_{b \geq 1} \frac{1}{e_i(b)}\)，其中 \(e_i(b)\) 是第 \(i\) 个假设在第 \(b\) 步的 e-value（即 test martingale \(S_i(b)\)）。作者主要考虑了两种 betting strategy 生成的 \(S_i(b)\)： 1. Binomial mixture strategy：\(S_i(b) = \sum_{k=0}^b \binom{b}{k} (\alpha)^k (1-\alpha)^{b-k} \prod_{j=1}^b (1 + \lambda_j (X_{i,j} - p_i^{\text{perm}}))\)（此处 \(\lambda_j\) 为预设的 betting 比例，依赖于 \(\alpha\)）。 2. BC strategy (Besag & Clifford)：一种特殊的序贯策略，仅在预设的 \(B\) 步后检查是否拒绝，但允许在中间步骤提前停止。 - 假设 1 (Validity under null)：在 \(H_i^0\) 下，\(S_i(b)\) 是一个非负鞅，初始值为 1。这保证了 \(\hat{p}_i\) 是一个 anytime-valid p-value，即对任意停止时间 \(\tau_i\)，\(P(\hat{p}_i \leq \alpha) \leq \alpha\)。 - 假设 2 (Conditional independence / Dependency structure)：这是本文最关键的假设。作者假设存在一组潜在变量（如观测数据集 \(\mathcal{X}\)），使得在给定 \(\mathcal{X}\) 的条件下，各假设的置换序列是独立的，且停止时间 \(\tau_i\) 仅依赖于 \(\mathcal{X}\) 和第 \(i\) 个假设的置换序列。统计含义：这放宽了 BH 的经典 PRD 假设，允许原假设与备择假设的 p 值之间存在任意依赖，只要置换过程的随机化是条件独立的。相比已有文献（如 B&Y 2001 的 PRD），该假设更贴合 MC 置换的数据生成机制（置换是在各假设内部独立进行的），但更严格地限制了停止时间的跨假设依赖（\(\tau_i\) 不能依赖于其他假设的 p 值）。

主要结果： - 定理 1 (FDR control under adaptive stopping)：在假设 1 和假设 2 下，将 anytime-valid MC p-values \(\hat{p}_1, \dots, \hat{p}_m\) 输入 BH 程序，即使每个 \(\hat{p}_i\) 的停止时间 \(\tau_i\) 是数据自适应的，该程序仍控制 FDR 在 \(\frac{m_0}{m}\alpha\) 水平以下。 - 直觉：Anytime-valid 性质保证了 \(\hat{p}_i\) 在原假设下是 super-uniform 的（即使停止时间是随机的），而条件独立假设保证了 Simes 瞬时条件在给定 \(\mathcal{X}\) 下成立，从而通过期望的迭代律（iterated expectation）将 FDR 控制从条件情形推广到边际情形。 - 必要条件：停止时间 \(\tau_i\) 必须是 \(\mathcal{X}\) 和第 \(i\) 个假设置换序列的函数，不能是其他假设 p 值的函数（这排除了“根据 BH 的当前拒绝数来决定是否继续抽样”这种全局自适应停止）。 - 解决的技术难点：解决了“自适应停止导致 p 值依赖破坏 BH 假设”的问题，通过 iterated expectation 将鞅的局部有效性转化为多重检验的全局 FDR 控制。 - 定理 2 (Computational saving)：在原假设下，binomial mixture strategy 的预期停止时间 \(E[\tau_i]\) 是 \(O(1/\alpha)\) 的常数级别，而非 \(O(B)\)（\(B\) 通常为 \(10^3\) 到 \(10^6\)）。在备择假设下，预期停止时间与信号强度成反比，信号越强停止越早。 - 直觉：Betting strategy 在原假设下“保守下注”，使得鞅增长缓慢，需要较少的抽样即可确认无法达到 \(1/\alpha\)；在备择假设下“激进下注”，鞅快速增长，迅速达到 \(1/\alpha\) 并停止。

证明路线与技术技巧： - 整体路线： 1. 构造 anytime-valid p-value：基于 betting strategy 定义 test martingale \(S_i(b)\)，并定义 \(\hat{p}_i = \inf_{b} 1/S_i(b)\)。 2. 建立 super-uniformity：利用 test martingale 的 Markov 不等式与 optional stopping theorem，证明在 \(H_i^0\) 下，对任意停止时间 \(\tau_i\)，\(P(\hat{p}_i \leq c | \mathcal{X}) \leq c\)。 3. 建立 Simes condition：在给定 \(\mathcal{X}\) 的条件下，利用置换序列的条件独立性，证明 anytime-valid p-values 满足 Simes 瞬时条件（即 \(P(\exists k: \hat{p}_{(k)} \leq \frac{k}{m}\alpha | \mathcal{X}) \leq \alpha\)）。 4. FDR 证明：通过 iterated expectation（先对置换序列求期望，再对 \(\mathcal{X}\) 求期望），将条件 Simes condition 转化为边际 FDR 控制。 - 关键跳跃点： - 跳跃点 1：从单检验的 anytime-valid 到多重检验的 Simes condition。难点在于：Simes condition 要求 p 值的联合分布满足特定不等式，而 anytime-valid p-value 的联合分布由鞅的交互决定。作者通过“给定 \(\mathcal{X}\) 下独立性”的假设，将联合分布分解为边际 super-uniformity 的乘积，从而直接套用独立下的 Simes condition。 - 跳跃点 2：处理停止时间 \(\tau_i\) 的随机性。经典 BH 证明中 p 值是固定的统计量，而此处 \(\hat{p}_i\) 的定义依赖于随机停止时间 \(\tau_i\)。作者利用鞅的 optional stopping theorem，证明了即使 \(\tau_i\) 是数据驱动的，\(\hat{p}_i\) 的 super-uniformity 仍然成立，这是整个证明的枢纽。 - 技术技巧点名： - Test martingale / Betting strategy：用于构造 anytime-valid p-value，保证在任意停止时间下的 I 型误差控制（用在定理 1 的步骤 1-2）。 - Optional stopping theorem：用于证明 \(\hat{p}_i\) 在随机停止下的 super-uniformity（用在跳跃点 2）。 - Iterated expectation (Tower property)：用于从条件（给定 \(\mathcal{X}\)）FDR 控制推导边际 FDR 控制，绕过了 p 值间复杂边际依赖的直接处理（用在步骤 4）。 - Super-uniformity：作为连接 anytime-valid p-value 与 BH 程序的桥梁，保证了 p 嵌入 BH 阈值时的概率界（用在步骤 2）。

真实例子与应用： - 用的什么数据/场景：真实基因组学数据集（GTEx 项目中的基因表达数据，涉及成千上万个基因的差异性表达检验）。 - 怎么把本文方法用上去：对每个基因，使用 binomial mixture strategy 的 anytime-valid MC 置换检验，设定目标 FDR \(\alpha=0.05\)，根据数据自适应决定每个基因的置换次数，然后将得到的 \(\hat{p}_i\) 输入 BH 程序。 - 得到什么结果：计算时间从经典固定 \(B=10^4\) 置换检验所需的“三天以上”降至“不到四分钟”；同时，由于 anytime-valid 方法在强信号假设下能更早停止并集中计算资源于弱信号假设，最终 BH 程序拒绝的假设数量比固定 \(B\) 方法更多。 - 这个例子想说明什么：验证理论结论（FDR 控制与计算节省），并展示相对于 baseline（固定 B 置换检验）在功率与计算效率上的双重优势。

🔎 结论是否比证明窄： - 作者在定理 1 中严格证明了“在 \(\tau_i\) 仅依赖 \(\mathcal{X}\) 和第 \(i\) 个假设置换序列的条件下，FDR 控制”。但在引言和讨论中，作者泛泛 claim 该方法“allows to fully adapt the number of permutations to the underlying data and thus, for example, to the number of rejections made by the multiple testing procedure”。这是一个比证明窄的 claim：如果 \(\tau_i\) 依赖于 BH 的当前拒绝数（即依赖于其他假设的 p 值），则违反了定理 1 的必要条件，此时 FDR 控制并未被证明。作者在文中并未明确指出这一限制，而是用“for example”将其淡化，研究者需特别注意这一 gap。

四、开放问题（点到为止，扎根具体语句）

  1. 全局自适应停止下的 FDR 控制：定理 1 要求 \(\tau_i\) 仅依赖局部数据（\(\mathcal{X}\) 和第 \(i\) 个置换序列），但引言中 claim 可适应于“the number of rejections made by the multiple testing procedure”（引言第 2 段）。若 \(\tau_i\) 依赖于全局拒绝数（跨假设依赖），FDR 是否仍能控制？需证在此更宽依赖下 Simes condition 或 FDP 的期望界。
  2. 与 PRD 条件的等价性或强弱关系：本文的“条件独立假设”是否弱于 B&Y (2001) 的 PRD？若等价，则本文 FDR 证明只是 PRD 的特例；若更强，则存在更宽的依赖空间未被覆盖。需查 B&Y (2001) 及 Finner et al. (2009) 的条件，与本文假设 2 对比。
  3. 其他多重检验程序的嵌入：本文仅证明了 BH 算法的 FDR 控制。对于 closed testing (Goeman & Solari 2011) 或 TDP 控制 (Vesely et al. 2021)，anytime-valid p-value 是否能提供类似的计算加速与有效推断？这需要重新推导 closed testing 在随机 p 值下的 shortcut 性质。
  4. 计算与统计的 trade-off 下界：定理 2 给出了预期停止时间的 \(O(1/\alpha)\) 上界，但未给出在保证 FDR 与功率前提下的样本复杂度下界。与 AMT (Zhang et al. 2019) 的 \(\tilde{O}(\sqrt{n}m)\) 下界相比，anytime-valid 路线是否存在更优的计算-统计 trade-off？需证一个 minimax computational lower bound。

提醒：要确认某条是不是真 gap，去读同子领域近期约 5 篇的 intro——都指向它 = 共识（真 gap），互相打架 = 机会。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论