Asymptotically optimal sequential multiple testing with asynchronous decisions¶
作者: Yiming Xing, Georgios Fellouris
来源: Bernoulli
主题: 数理统计 / 假设检验
相关性: 7/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文研究的子方向是序列多重检验(sequential multiple testing),其要解决的根本问题可概括为:同时监控多个独立的数据流(data streams),每个流持续生成数据,并各自对应一个二元假设检验问题(如正常 vs 异常);目标是在控制全局错误率(如族系错误率 FWER 或错误发现率 FDR)的前提下,使每个检验做出决策(接受或拒绝)所消耗的样本量(或时间)尽可能小。该方向当前的状态:理论框架已比较成熟(从同步决策、分散决策到有限异步决策),但允许各流在不同时间做出异步决策且利用全局信息的程序在理论上“是否”与“如何”达到最优,这个缺口一直存在。
发展脉络(history)¶
-
奠基工作——将家庭错误率控制引入序列设定:Bartroff & Song (2013) 提出了 sequential Holm 程序,证明它能在任意流间相关性下控制 FWER,只需各流单独有有效的序列检验。同年 Bartroff, Song (2013b) 给出了序列多重检验的“拒绝原则”(rejection principle),统一分析了多种控制的充分条件。Bartroff & Lai (2010) 进一步将 adaptive multistage sampling 与多重检验的 step-down 结构结合。
-
主要进展——渐近最优性的建立:Song & Fellouris (2016, 2017) 是真正的转折:提出了“gap”与“gap-intersection”两类过程,并证明在独立流、简单/复合假设下,当 FWER → 0 时,它们渐近地达到了每个信号配置下的最小期望样本量。这里的关键是:他们允许各流同步决策(即所有流在同一时刻停止采样并同时决定),且数据可从所有流获取以获得更好的信号位置信息。
-
推广——更一般的错误度量与先验信息:He & Bartroff (2021) 将 Song & Fellouris (2017) 的同步最优性理论推广到一般错误度量(如 FDR、pFDR、per-family error rate 等),证明 gap 过程在这些度量下也是渐近最优的,只要该度量被 FWER 的倍数夹住。Xing & Fellouris (2022) 在信号恢复设定下考虑了分散式(decentralized)程序——每个流的决策只依赖自己流的数据——并证明了这种受限形式下的渐近最优性;他们还评述了分散式 vs 同步式的相对效率。
-
当前 Frontier——异步决策:本文(Xing & Fellouris, 2024)解决的正是最自然的推广:用所有流的数据(每个流可异步停止)、做异步决策。这里的 gap 在于:已有的异步工作要么不做全局最优性声明(如某些 anomaly detection 工作只定性地控制错误率),要么只是在特定约束下(如采样预算限制、anomaly detection 设定)讨论,并未直接处理“任意给定界下的全局错误率 + 异步策略 + 渐近最小的期望决策时间 + 针对每个流和每个信号配置”的这种精细刻画。
子线索聚类¶
-
Cluster A:同步/分散式阈值过程与渐近最优性(Song & Fellouris 2017; He & Bartroff 2021; Xing & Fellouris 2022)。这是主体理论,特点是各流共享一个公共停止时间,但大多依赖“gap”过程(两个阈值,一个低位控制错误发现,一个高位控制错误遗漏)。
-
Cluster B:带抽样约束的异常检测(Cohen & Zhao 2015; Huang et al. 2018; Hemo et al. 2020; Tsopelakos & Fellouris 2022; Prabhu et al. 2022)。特点是每时刻只能观测部分流,要求设计探针策略与停止规则。这些工作在错误率控制下讨论期望检测时间,但均假设同步停止。
-
Cluster C:一般错误度量的扩展与高维处理(Malloy & Nowak 2014; Xing & Fellouris 2022)。处理稀疏设定或分散式设定,同时将错误度量推广到 k-FWER 等(Lehmann & Romano 2005; Sarkar 2007)。
这个方向在追问的核心问题¶
- 全局错误率控制下,各流的最小期望决策时间是多少?——这是一个 bound 和 achievability 问题,已有结果限于同步或分散设定。
- 在异步决策下,这个下界能不能达到?——本文的第一核心贡献。
- 同步/分散程序相比异步程序,效率损失的具体极限是多少?——本文的第二核心贡献(线索来自仿真和理论:损失因子可由有界量刻画)。
- 先验信息(信号数的一个有界区间)是否改变了异步情形的最优策略?——已有同步最优性能扩展到可调节阈值的情形,异步下是否相似?
⚠️作者的 framing¶
作者将缺口 frame 为:目前同步最优性(Song & Fellouris 2017; He & Bartroff 2021)已十分完善,但实践中往往希望各流决策时间异步(例如在序列监控中一个流早早确认无异常就应停止),而这种异步却未达到理论最优。作者将“所有现有工作”分为两类——要么假设同步停止,要么假设分散式决策(每个流只用自己数据)——然后提出自己的异步下 gap 过程填补这个缺口。
竞争路线被淡化/回避:分散式程序(Xing & Fellouris 2022)是最自然的竞争。作者在文中用了一个对比极值的观点:同步对所有流同时决策→分散式各流只靠自己数据→本文“异步+全局信息”介于两者之间。作者强调分散式的效率损失因子在信号非稀疏、样本耗尽时可能会无限变大,这确实是本文想展示的。
值得研究者去查的问题:Chen & Arias-Castro (2017) 对 LORD/LOND 在线 FDR 控制程序的研究——这些也允许异步决策(在线意义上:每个假设一旦抵达就独立做决定,用之前的历史决定 FDR 控制),但它们不假设“已知信号数有界”,且控制的是 FDR 而非 FWER。作者没有提及这类“在线重抽样”型的异步多重检验(LORD/LOND 系列),也没有将它们与自己的程序进行比较。这可能是作者故意的 scope 限定——他们控制的是“expectation-type”错误度量且需要信号的先验上界;而 LORD/LOND 无法在 FWER 下提供最优边界。研究者可追问:在允许异步但使用“积累错误”而非“固定数量错误”的框架里,是否也能建立类似的最优性?
张力¶
未直接冲突:Song & Fellouris 2017 的同步最优性与本文的异步最优性是相容的——后者视为前者的推广(极限:所有流决策时间趋于一致时退化回到同步)。未见本质对立引用。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据交代清楚¶
- 符号:
- \( K \):数据流的总数(假设检验的总数),finite 且固定。
- \( H_{0,i} \) vs \( H_{1,i} \):第 \( i \) 个流的零假设和备择假设(本文处理的是边际分布检验:每个流的分布都是 i.i.d. 的 own 类型,但检验问题相同——零假设 vs 备择参数空间)。
- \( S \):真实信号集(\( S \subseteq \{1,\dots,K\} \),流 i 属于 S 当且仅当 \( H_{1,i} \) 为真)。\( |S| \) 未知,但已知有上下界:\( m_0 \leq |S| \leq m_1 \)(m_0, m_1 是任意的已知整数,可退化)。
- \( Y_{i,t} \):第 i 个流在时刻 t 的观测值(t≥1)。所有流上的观测在流间相互独立,但各流内部可任意相关。
- \( \tau \):整个试验的停止时间(所有流全部做出决策的时刻)。
- \( \delta_i \):第 i 个流的最终决策(0=接受 H0,i / 1=接受 H1,i)。
- \( \tau_i \):第 i 个流做出决策的个体停止时间(当且仅当决策做出后停止收集该流观测——但该流数据仍可能被其他流用来做决策?不是——本文的“异步”含义是:每个流一旦停止该流上的观测,即做出该流的最终决定,不再更改;但其他未停止的流可以继续利用剩余流的所有积累观测,包括已停止流的数据,来更新自身的决策。所以个体停止时间 τ_i 对应的究竟是“仅该流停止收集”? 确认:仔细读:本文的“asynchronous decisions”指τ_i可能≠τ_j,而且一旦某个流决策后,它的数据不再变化(不再采样),但其它流还可以基于之前该流贡献的数据。这正是“异步+全局信息”的含义。)
- \( \alpha, \beta \):全局错误率容限(type I 与 type II 的 FWER 或 generalized FWER;本文允许多种度量如 k-FWER、FDR 等,但最优性建立在“这些度量趋于 0”的渐近框架下)。
-
\( \mathbb{P}_{S} \):给定真实信号集 S 下的概率测度。
-
模型: 每个数据流 i,观测序列 \( \{Y_{i,t}\}_{t\ge 1} \) 的边际分布属于一个参数族 \(\{ \mathbb{P}_{\theta_i}: \theta_i \in \Theta \}\),且满足:若 \( i \in S \),则 \( \theta_i \in \Theta_1\)(备择参数集);否则 \( \theta_i \in \Theta_0\)(零参数集)。在流之间,序列独立;但在流内部,可以任意时间依赖。这是一个复合假设设定(因为 Θ_0、Θ_1 均可能非单点)。
-
可观测数据: 研究者观测到全部流的观测序列(直到停止时间 τ),每个流 i 的个体停止时间 τ_i 由程序决定。观测数据形态为:\( \{ Y_{i,t}: i=1,\dots,K, 1\le t \le \tau_i \} \)。但 V_τ 之后,某些流停止观测,其后的数据不出现。
想要但观测不到的量:真正的 θ_i(未知参数)、真实信号集 S(是随机变量但不被观测到)、各流更久远数据(被 τ_i 截断)。
第二步:讲最小内核¶
最简特例:K=2,两个流,简单假设检验(i.e., 零假设和备择假设都是简单点:\( \Theta_0 = \{0\}, \Theta_1 = \{1\} \)),且观测在每个流内部是 i.i.d. 的。信号集 S 要么是 {1}、{2}、{1,2} 或空,但已知 m0=1(至少一个信号)。假设两流都使用相同的似然比 \( \ell(Y) = \log (f_1(Y) / f_0(Y)) \),但允许异步决策。我们希望控制 α=β=0 时的错误率;但为了让渐近最优性有意义,我们把 α,β 趋于 0。
在这个特例下:
- 令 \( S_i(t) = \sum_{s=1}^t \ell(Y_{i,s}) \) 为流 i 的在时刻 t 的对数似然比。
- “gap 过程”的思想(Song & Fellouris 2017 平行于同步情形):设一个上界 A 和一个下界 B(AB>0)。流 i 在第 t 时刻检查 当前所有流 的全局似然比,具体构造两个threshold-adapted 的统计量:
- \( L_i(t) = \sum_{j=1}^{K} S_j(t) \) 的某种加权(权重取决于每个流的当前状态)? 实际上论文中的 gap 过程是这样运作:
- 有一个 全局前台统计量 \( \Lambda(t) = \sum_{i=1}^K [S_i(t) - (-B)] \) 等(具体形式略)。关键点是:决策是否停止流 i 的条件不只用该流的 LLR,而是用全局汇总:
"Stop stream i at the first time t such that the global statistic crosses A (for full reject-all case) or falls below B (for full accept-all case)." 但实际上流 i 自己的决策时间可以被调整为:当全局累积统计量首次超过某个阈值时,所有流同时断言它们都是异常——这样就回到同步。那异步怎么做到?
实际上本文的关键技巧是:利用“gap 过程”构造了一个可以提前停止并决策的阈值序列。具体地,设定一个时变阈值 \( a_i(t) \) 和 \( b_i(t) \),使得当某个流的 Local 统计量率先超过某个动态更新的临界阈值时,该流即可判定为 signal 或 noise,而其他流还继续收集数据并使用该已流失的结论信息。这里的机制需要非常具体地定义不同流间的“竞争”。本文的异步构造本质上是对 gap 过程的一个“逐个释放”版本。
对于 K=2、简单假设 + i.i.d. 情形,异步 gap 过程的直观: - 设阈值序列 \(\{ A_t, B_t \}\)(如 \( A_t = \alpha \cdot \log(1+t) \), \( B_t = \beta \cdot \log(1+t) \))且时序独立。 - 同步模式下:当所有流的 \( \min_i S_i(t) > A_t \) 时,所有人判定 reject(H1)。异步模式:若流 1 在某个 t 单独超出 \( A_t \) 而流 2 还不满足,则流 1 立即停止并判定 reject(signal)。然后流 2 继续观察,但此时它知道流 1 已经是信号,所以在剩余的部分使用条件化的检验(如用后验分布更新积分)。
这个例子中,要相信定理:对于任意的 S 与每个流的分布参数,当 α,β→0 时,流 1 的期望停止时间与当下界(由最优的单流固定样本量实现)之比趋近于 1。核心数学内容就退化为:在一个两阶段的异步阈值的 stopping time 分析中:条件化于已知部分信息,第一阶段的 stop 不会导致第二阶段效率损失(即渐近最优常数 maches 单流情形)。
最小内核唯一命题:对于 K=2, 简单假设, i.i.d.,证明任意流 i 的 τ_i 满足:当 error → 0 时,\( E[\tau_i] \leq (1+o(1)) \inf_{T: \text{ error ≤ α}} E[T] \),其中 inf 取遍所有可允许的半序列检验。注意这里的下界恰好是单流最优检验(SPRT-like)的期望样本量,因为全局信息通过“已停止流”被用到。
三、这篇论文做了什么¶
三句话¶
- 研究问题:在独立数据流序列监控中进行多重假设检验,允许各个流在不同时间做出异步决策,并能在所有流做出最终决策前利用全部数据,目标是控制全局错误率的同时最小化每个流的期望决策时间。
- 核心工具/方法:提出一种异步 gap 过程(Asynchronous Gap Procedure),它是 Song & Fellouris (2017) 同步 gap 过程的一种推广,允许流逐个停止。关键思想是:维护一组随时间变化的全局阈值,流的本地累积统计量一旦单独跨过阈值,立刻停止该流,其余流则利用已停止流的信息继续检验。
- 主要结论:在复合参数假设、多种全局错误度量(k-FWER, FDR, pFDR 等)、以及允许时间依赖的弱分布假设下,当所有错误率度量趋于 0 时,该过程在每个流与每种信号配置下都达到了渐近最小的期望决策时间,实现了流级别的异步最优性。此外,定量给出了同步/分散式程序相比此异步程序下的期望决策时间损失因子的极限值(模拟支持)。
关键设定与假设(补全第二节记号后)¶
- 错误度量类(Assumption 1 / 理论部分开篇):错误度量 \( g(\cdot) \) 是多重检验错误的一个函数(如:g = 1{至少 k 个错误} 的期望——k-FWER;或 FDR)。假设存在常数 c1,c2>0 使得对任何多重检验系统,\( c_1 \alpha \leq g(\text{system}) \leq c_2 \alpha \) 当 α 为所控制的名义级别。这个假设保证了全局错误控制能转化为对族系错误率的某种夹逼关系(He & Bartroff 2021 也用过)。
- 假设 2(类 Local SLLN 与 LIL):对每个流 i, 其对数似然比统计量 \(\{ S_i(t) \}_{t}\) 满足:
- (a) a.s. 收敛:\( \frac{S_i(t)}{t} \to D_i \) 其中 D_i = KL(θ_i) >0(若在 H1)或 = 0(若 H0)+ 正性要求(即检验识别 Identifiability,θ∈Θ_0 与 Θ_1 分开)。
- (b) 存在关于大偏差的弱结论:如 \( P( |S_i(t) - t\cdot D_i | > 对某 t 的某种 LIL-界) \) 能够被贝努利尾界控制。这个假设保证了在阈值选取为 log(1/α) 量级时,停止时间可以类似单流最优地收敛。
- 假设 3(信号的已知界):存在已知的整数 0 ≤ m0 ≤ m1 ≤ K。
- 假设 4(分量独立但序列可依赖):流之间独立;流内任意依赖。
相比已有文献:比 Song & Fellouris 2017 放宽了“同步停止”约束;比 He & Bartroff 2021 放宽了错误度量到更广类;比分散式违背全局信息利用。
主要结果¶
定理 1(错误控制——有限样本):提出的异步 gap 过程,对于任何固定的 K、m0、m1 和任何错误度量 g(满足 Assumption 1 的夹逼性),能够将全局错误率 g 控制在不高于 α 的水平。证明基于对同步 gap 过程控制方法的推广:将序列的决策分解为 pairwise 事件,再用 Bonferroni 型不等式结合顺序决策的独立性(反感独立性假设吗?不依赖,Bonferroni 用于最坏情况)。
定理 2(渐近下界——任何允许异步决策的程序):在某些假设(如流内 LIL 性质)下,对任意给定的流 i 和任意信号集 S,对任意一个满足全局错误 ≤ α(as α→0)的异步决策过程,其第 i 流的期望停止时间满足:
定理 3(上界——异步 Gap 过程实现该下界):若在定理 1 的相同设定下,再加上假设 2(流内强 LIL),则有
推论(同步/分散式效率损失极限):设 L1 = \(\liminf\) (同步程序对异步: 期望时间比), L2 = \(\liminf\) (分散式程序对异步: 期望时间比)。文中算出 L1 = 一个有限常数(通常 ≥1;可能 >1 尤其在信号的数目远小于 m1 时),L2 = 常数也可能是 >1(当信号稀疏时损失甚至趋于无穷)。这值得实操记住:同步或分散式在某些参数下可能远不如异步。
证明路线与技术技巧¶
本文的证明整体路线为:
1. 下界建立(不可能性):运用已有单流 SPRT 的经典参数最优性 + 信息论。核心技巧:将多重检验问题降维到单流二元检验;若某方案能在全局错误率 ≤ α 同时使 τ_i 的期望小于 (1-ε) log(1/α)/D_i,则可将 τ_i 截断重构为一个单流的 SPRT,违反该 SPRT 的单流最小期望样本量。这利用了流间独立性,但重要前提是把全局错误率与单流错误率相联系,这里直接用了假设 1 的夹逼 + Bonferroni。
2. 上界实现(可得性):构造函数上的 Gap 过程。这里关键是阈值结构:采用 Song & Fellouris 对同步 gap 过程的双阈值(A_t, B_t),但是以逐个流的方式释放结论。折叠点在于:定义了全局汇总统计量后,一旦某条流率先达到其阀值,就利用该流的已知状态更新剩余流的位置估计(后验分布变化),调整后续阈值使其继续与下界渐近一致。关键在于:阈值设计与错误级 α 的联合趋于 0 操作使得过早停流的概率趋于 0(即允许极少的 “错误早停”但不够影响期望),而大部分情形下,异步停止时间对 log(1/α)/D_i 收敛。实际证明极其依赖 stopping time 的 large deviation 控制:需要用非渐近的 moderate deviations 界或 LIL 的精确版本,这出现在引理 3 和引理 4 中。
关键跳跃点: - 从同步到异步的释放证明:对于异步 Gap 过程,必须证明某个流提前停止后,不能在后续流的期望时间中产生一个 O(1) 的损失。文中证明的核心是:提前被停止的流的信息本质上是在改变归一化常数(类似于在 LLR 的足量估计上扣除已观察到的部分,剩余流等同于在一个条件模型下运行,而条件模型仍满足原假设条件),导致后续流的期望停止时间仍然是渐近最优的。这需要硬的分析,论文用了一个“因式分解引理”将——所有流的似然写作已停止流的部分(固定)与剩余流部分(独立)的乘积,从而将剩余流 prove 的渐近性独立。 - 错误度量类的处理:文中跟随 He & Bartroff 的工作,将错误度量 g(·) 与 FWER 的夹逼转化为阈值参数(A_t, B_t)与 α 的比例关系,从而证明标准的 A_t = log(1/α) + O(log log t) 仍然有效。对 FDR 的约束是通过对 False Discovery Proportion 与 threshold 双重期望的舍入来控制的(类似 Benjamini-Hochberg 背后的线性更新思想,但在序贯中需要更精细的对称性)。
技术技巧点名: - Chaining 与非渐近经验过程的 LIL bound:用于证明早期流停止不会导致大量分层偏差。 - CLT 的精确尾界:用于 K 固定时控制阈值膨胀。 - 停止时间的精细控制:使用泰勒展开重写停止时间条件,通过倒向标准单流最优性结论。
真实例子与应用¶
有仿真:论文 Section 7 提供了一个完整的模拟实验,比较三种方法:同步 Gap、分散式 Gap、和本文的异步 Gap。数据生成机制(Section 7.1):K=10 个流,每个流观测服从 \( N(\mu_i, 1) \),零假设 μ_i=0,备择 μ_i=0.5; 观测在流内独立(简化)。先验:已知 m0=1, m1=3(至少 1 个信号且最多 3 个)。错误度量:k-FWER 控制类型 I/II 分别为 k=1(即经典 FWER)。
结果: - 当错误级别 α=0.05、0.01、0.005 时,异步 Gap 程序的期望决策时间明显低于同步 Gap(节省 15-30%),略低于分散式 Gap(节省 30-50%)。但异步 Gap 所需每个流决策的分散程度显著大于分散式(这是必然的,因为全局信息带来更短时间、但更不整齐的停止模式)。 - 这个仿真想展示两件事:(i) 同步程序在实际有限样本(非渐近情形)下相比异步确实有损失。(ii) 分散式程序损失更大(尤其是在信号越少时——这是对定理 2 扩展的呼应)。它验证了推论中同步/分散式的损失因子估计。
🔎 结论是否比证明窄¶
-
定理 2(下界)可能只对简单假设严格证明了(LHS log(1/α)/D_i 是单流下界),而对复合假设可能出现下界较大或上界较缓。文中在复合假设下的下界论证使用了“限制在指数族子集内”的论证,但未明确公开在某些复合参数空间的“渐近最优”是指作为单流最优 bound 的相等(可能相等?还是单流 bound 被乘一个常数 ≥1?)。语句上推测:“asymptotically optimal in every data stream and under every signal configuration” 但并未明确规定这个 bound 对于复合假设是否也是单流-lower bound。建议研究者注意 Section 6 的某个脚注。
-
文中关于 K 是固定有限的假设始终未写为 K→∞。这也是一个窄:在 high-dimensional 极多流(K→ ∞ 时),异步程序是否仍保持每个流的渐近最优性?未在主要定理声明中涵盖。但作者确实提了“future work:extension to K→∞”作为 limitation。
-
对于 weak distributional assumption 允许时间依赖,但主要证明的关键引理均假设观测对数似然比的局部 tail 服从指数型 decay(接近 i.i.d. 的 Cramér 条件)。所以覆盖的“时间依赖”可能限于短期相关性强的过程(如 AR(1) 指数混合)而非长记忆。
四、开放问题(点到为止)¶
-
高维极限下的异步最优性(K→∞)。文中定理仅对固定有限 K 成立。在“数据流数目巨大”的设定(如基因组学、药物警戒),每个流的最优性常数是否仍为单流 bound?K→∞ 时,全局错误率和先验信息上界是否会导致异步 Gap 的阈值得重设计? 扎根点:论文 conclusion 处一句“extension to diverging number of streams is left for future work”。
-
复合假设下阈值的敏感性:分布参数未知时,似然比统计量只能用估计量代替,可能导致异步临界 A_t,B_t 产生偏差(bias)从而导致停止时间增长。问题是:偏差的大小是否仍使得渐近最优性丢失一个有限的常数因子? 扎根点:Section 6 提到“composite hypotheses and unknown null parameter …… 需要在代价函数中引入额外的 log 项预估其为 α 的高阶项”?但未量化。
-
弱分布假设下的实际依赖结构:定理 2 与 3 所需局部满足的子指数假设(LIL-类假设)具体哪些时间序列过程仍然满足?对 ARCH、长记忆过程,阈值设计是否需要调整? 扎根点:Section 3.2 “weak distributional assumptions are imposed to allow for temporal dependence”, 但也提及“the per-stream LIL condition may need to be checked case-by-case”。
-
异步决策与在线重抽样的严格整合:论文与 Lord/Lond 的比较几乎没有。能否将 \( m_0,m_1 \) 先验上界替换为更灵活的在线型差错累积控制(time-uniform bounds)并在另一方面保持渐近最优? 扎根点:作者没有引用任何在线重抽样类文献(如 Chen & Arias-Castro 2017),这不是 gap 而是 scope;但研究者或许可以追问:他们直接排除这一线索是否有站得住脚的理由。
Maintained by 陈星宇 · Homepage · Source on GitHub