CAQ: Clustered Asymptotically Anytime-Valid Quantile Treatment Effects for Online Experiments¶
作者: Diane Lu, Eric J. Oh
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://arxiv.org/abs/2610.30019
一、领域脉络与小综述¶
这个方向是什么¶
本文所处的子方向是在线实验(A/B 测试)中的序贯假设检验与置信序列(confidence sequences, CS)构造,其根本统计问题是:在允许"随时查看数据、随时停止实验"的连续监测场景下,如何构造对任意停止时间都有效的推断——即控制累积一类错误(cumulative type I error),避免"偷看数据"(peeking)导致的假阳性膨胀。该方向当前处于"方法已较成熟、但向复杂数据结构推广"的阶段:经典置信序列理论(如 [2, 3])已解决独立同分布(i.i.d.)采样下的均值与分位数推断,但在线实验的实际数据结构——用户被随机分配、每个用户贡献多个相关事件(聚类数据)——尚未被序贯推断框架覆盖。本文试图填补的正是这一缺口。
发展脉络(history)¶
- 奠基工作:固定时窗下的聚类稳健推断。Deng et al. (2018) [1] 将 Delta 方法系统引入在线实验指标分析,处理了聚类数据下均值类指标的方差估计问题,但其推断是固定样本量的,不适用于连续监测。Liu et al. (2019) [5] 进一步将分位数指标纳入固定时窗框架,但同样缺乏序贯有效性保证。这两篇构成了"聚类 + 分位数"在固定时窗下的标准做法。
- 主要进展:任意时点有效的置信序列。Howard & Ramdas (2022) [2] 给出了分位数的非渐近置信序列,其宽度以最优的 \(\sqrt{t^{-1}\log\log t}\) 速率收缩(由重对数律决定),但严格假设观测 i.i.d.。Waudby-Smith et al. (2024) [6] 将置信序列推广到渐近版本(AsympCS),放宽了非渐近有效性对分布的具体要求,使 CLT 类型的工具可以用于序贯推断——这是本文直接依赖的理论基石。
- 当前 frontier:处理数据结构与序贯推断的结合。Lindon et al. (2022) [4] 将序贯检验用于软件部署的回归检测,但针对的是分布相等性而非分位数处理效应。Wang & Zhang (2021) [CONQ] 提出了连续的分位数处理效应估计,但未涉及序贯停止。本文的位置:首次将三条线索——聚类稳健方差估计([1] 的 Delta 方法思想)、渐近置信序列([6] 的 AsympCS 框架)、分位数处理效应([2, 5] 的估计对象)——合并为一个方法,即 CAQ。
子线索聚类¶
- 聚类数据的稳健推断([1, 5]):处理组内相关性导致的方差低估问题,方法为 Delta 方法或聚类稳健方差估计,但限于固定时窗。
- 序贯推断与置信序列([2, 3, 6]):构造对任意停止时间有效的置信区间,方法包括非渐近(基于重对数律的显式界)与渐近(基于 CLT 的 AsympCS)两条路线,但假设 i.i.d. 采样。
- 分位数处理效应估计([2, 5]):以分位数而非均值为目标,处理重尾分布下的稳健推断,但未与聚类结构结合。
这个方向在追问的核心问题¶
- Q1:如何在聚类数据下构造任意时点有效的置信序列?——本文直接回答。
- Q2:分位数估计的渐近线性展开(Bahadur 表示)在聚类数据下是否仍然成立?——本文在 Appendix A 中给出了聚类版本的 Bahadur 表示。
- Q3:聚类稳健的方差估计能否嵌入 AsympCS 框架而不破坏其时间一致性?——本文通过将聚类 CDF 估计视为比率型估计量并验证其渐近线性来解决。
- 已知瓶颈:非渐近置信序列(如 [2])在聚类数据下难以构造,因为其依赖的浓度不等式(DKW 型)在相关数据下失效;而固定时窗方法(如 [1])在连续监测下累积一类错误膨胀(本文 Table 1 中 Deng et al. 的 miscoverage 高达 0.32–0.36,远超 α=0.05)。
⚠️ 作者的 framing(这是作者的说法)¶
作者将缺口 frame 为"三个维度(聚类、分位数、序贯)两两组合已被解决,但三者同时成立的方法缺失"——即引言中明确写的 "Prior work covers only pairs: clustered quantiles at a fixed horizon [1, 4, 5], sequential quantiles only under i.i.d. sampling [2, 3]"。这一 framing 将本文定位为"显然的下一步":既然每对组合都有解,三者合一是自然推广。被淡化或回避的竞争路线:作者未讨论贝叶斯序贯方法(如贝叶斯因子或后验概率阈值)在聚类分位数下的表现,也未讨论非渐近置信序列在聚类数据下是否有构造可能(可能因为技术上极难)。值得研究者去查的问题:是否存在其他处理聚类数据的序贯方法(如基于 bootstrap 的序贯检验)?作者未引用任何 bootstrap 序贯方法,这可能是一个被忽略的竞争路线。
张力¶
未见明显对立引用。各被引工作之间是互补关系而非矛盾关系:Deng et al. 处理聚类但非序贯,Howard-Ramdas 处理序贯但非聚类,二者在各自假设下均正确,不存在结论冲突。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
符号(逐个点名):
| 记号 | 含义 | 类型 |
|---|---|---|
| \(i = 1, \dots, K\) | 用户(单元/聚类)下标 | 样本索引 |
| \(j = 1, \dots, N_i\) | 用户 \(i\) 的第 \(j\) 个事件 | 样本索引 |
| \(X_{ij}\) | 用户 \(i\) 的第 \(j\) 个事件的观测值(如延迟时间) | 随机变量(可观测) |
| \(N_i\) | 用户 \(i\) 的事件总数 | 随机变量(可观测) |
| \(n = \sum_{i=1}^K N_i\) | 总事件数 | 派生量 |
| \(F\) | 事件 \(X_{ij}\) 的边缘分布 | 未知分布(目标) |
| \(Q(p) = F^{-1}(p)\) | 事件分布的 \(p\) 分位数 | 参数 / estimand |
| \(\hat{\theta}_p = X_{(\lceil np \rceil)}\) | 合并样本的 \(p\) 分位数(第 \(\lceil np \rceil\) 个顺序统计量) | 估计量 |
| \(S_i = \#\{j : X_{ij} \le Q(p)\}\) | 用户 \(i\) 中不超过 \(p\) 分位数的事件数 | 潜在量(依赖未知 \(Q(p)\)) |
| \(\bar{S} = \frac{1}{K}\sum_i S_i\),\(\bar{N} = \frac{1}{K}\sum_i N_i\) | 每用户平均事件数、平均低于分位数事件数 | 样本均值 |
| \(\hat{p} = \bar{S}/\bar{N}\) | 聚类 CDF 在 \(Q(p)\) 处的估计 | 估计量 |
| \(\phi_i = (S_i - p N_i)/\mu_N\) | 每用户影响函数(influence function) | 潜在量 |
| \(\hat{V}\) | \(\phi_i\) 的样本方差估计 | 估计量 |
| \(\Delta_p = Q_t(p) - Q_c(p)\) | 处理组与对照组的 \(p\) 分位数之差 | estimand(因果目标) |
| \(c, t\) | 对照组(control)、处理组(treatment) | 分组标签 |
| \(K_c, K_t\) | 两组各自的用户数 | 样本量 |
| \(m = K_c + K_t\) | 总用户数 | 样本量 |
| \(\rho\) | 调谐参数,控制置信序列的紧度 | 用户设定 |
| \(\alpha\) | 显著性水平 | 用户设定 |
模型(数据生成机制):
- 单元层:用户 \(i\) 独立同分布地进入实验(随机分配),每个用户贡献 \(N_i\) 个事件,\(N_i\) 是随机变量,满足 \(\mu_N = \mathbb{E}[N_i] \in (0, \infty)\),\(\mathbb{E}[N_i^2] < \infty\)。
- 事件层:给定用户 \(i\),其 \(N_i\) 个事件 \(X_{i1}, \dots, X_{iN_i}\) 可以任意相关(组内相关),但不同用户之间独立。每个事件的边缘分布为 \(F\)。
- 平滑性:\(F\) 在 \(Q(p)\) 附近二次连续可微,且密度 \(f = F'(Q(p)) > 0\)。
- 因果识别:随机化分配,\(A_i \sim \text{Bernoulli}(\pi_t)\) 独立于潜在结果,\(\pi_t\) 已知且固定。因此 \(\Delta_p = Q_t(p) - Q_c(p)\) 由观测数据可识别,无需额外假设(如 SUTVA 在用户层面自然满足,因为用户独立)。
可观测数据:研究者按顺序看到用户逐个进入实验,每个用户到达后观测到其 \((N_i, \{X_{ij}\}_{j=1}^{N_i})\) 以及分配组别 \(A_i\)。在任意时刻 \(K\)(用户数),可以计算合并样本分位数 \(\hat{\theta}_p\) 和聚类 CDF 估计 \(\hat{p}\)。
关键区分——可观测 vs 潜在:
- 可观测:\(N_i\)、\(X_{ij}\)、\(A_i\)、\(K\)、\(n\)。
- 潜在(不可直接观测,只能估计):\(F\)、\(Q(p)\)、\(\Delta_p\)、\(\phi_i\)(因为 \(S_i\) 依赖未知的 \(Q(p)\))、\(f\)(密度值)。
第二步:最小内核¶
核心问题:我们逐个看到用户的数据,想在任意时刻 \(K\) 都能给出 \(\Delta_p\) 的置信区间,使得"在某个时刻区间没覆盖真值"的概率不超过 \(\alpha\)——即 \(\mathbb{P}(\exists K: \Delta_p \notin \text{CI}_K) \le \alpha\)。
最小内核(单组、单分位数):先看一个臂(比如对照组),估计 \(Q(p)\)。
剥掉所有一般性假设后,剩下的核心数学问题是:
设 \((S_i, N_i)\) 是 \(K\) 个 i.i.d. 的二维随机向量,\(\mathbb{E}[S_i] = p \mu_N\)。定义比率估计量 \(\hat{p} = \bar{S}/\bar{N}\)。问:\(\hat{p}\) 能否作为 \(p\) 的渐近线性、时间一致的估计量,使得 \(\hat{p} \pm b(K)\sqrt{\hat{V}/K}\) 构成一个渐近置信序列?
为什么这是核心:因为分位数 \(Q(p)\) 的推断可以完全归约到 CDF 值 \(p\) 的推断——通过单调变换 \(F\),\(Q(p)\) 的置信区间就是 \(\{Q : \hat{p}(Q) \in [p - \beta_K, p + \beta_K]\}\) 的逆像,即 \([X_{(\lceil n(p-\beta_K)\rceil)}, X_{(\lceil n(p+\beta_K)\rceil)}]\)。所以只要解决了 \(\hat{p}\) 的置信序列,就解决了分位数的置信序列。
在这个特例下,命题退化成什么:
-
要证的命题:\(\hat{p}\) 是 \(p\) 的渐近线性估计量,即
\[\hat{p} - p = \frac{1}{K}\sum_{i=1}^K \frac{S_i - p N_i}{\mu_N} + R_K,\]其中 \(R_K = o(\sqrt{\log K / K})\) a.s.,且影响函数 \(\phi_i = (S_i - pN_i)/\mu_N\) 是 i.i.d. 零均值随机变量。 -
证明怎么走:
- Taylor 展开:\(\hat{p} - p = \frac{\bar{S} - p\bar{N}}{\bar{N}} = \frac{1}{\bar{N}}\left(\frac{1}{K}\sum_i (S_i - pN_i)\right)\)。当 \(\bar{N} \to \mu_N\)(强相合),分母可以用 \(\mu_N\) 替换,余项为 \(\frac{(\bar{S} - p\bar{N})(\mu_N - \bar{N})}{\mu_N \bar{N}}\)。
- 余项估计:\(\bar{S} - p\bar{N} = O(\sqrt{\log\log K/K})\) a.s.(由重对数律),\(\mu_N - \bar{N} = O(\sqrt{\log\log K/K})\) a.s.,所以余项 \(R_K = O(\log\log K / K)\) a.s.。
- 关键比较:需要 \(R_K = o(\sqrt{\log K / K})\)。因为 \(\log\log K / K \ll \sqrt{\log K / K}\)(当 \(K \to \infty\)),所以成立。这一步是整个证明的命门——它保证了余项相对于置信序列的边界是可忽略的,从而时间一致性不被破坏。
-
应用 AsympCS 定理 [6]:一旦 \(\hat{p}\) 是渐近线性的,且影响函数方差可估(用 \(\hat{V}\)),则 \(\hat{p} \pm b(K)\sqrt{\hat{V}/K}\) 是渐近置信序列。
-
为什么难:难在同时处理三个约束——(i) 分位数而非均值(需要顺序统计量,其渐近分布涉及局部密度);(ii) 组内相关(经典 Bahadur 表示假设 i.i.d. 观测,这里每个用户贡献多个相关事件,需要重新推导);(iii) 时间一致性(余项必须比 \(\sqrt{\log K/K}\) 小,这比固定样本 CLT 要求的 \(o(1/\sqrt{K})\) 更严格)。
两组的推广:两组独立,各自有渐近线性表示 \(\hat{\theta}^{(a)}_p - Q_a(p) = \frac{1}{K_a}\sum_i \psi^{(a)}_i + o(\sqrt{\log K_a/K_a})\)。用逆概率加权(IPW)将两个不同样本量的平均融合到总样本量 \(m = K_c + K_t\) 上,得到单一估计量 \(\hat{\Delta} - \Delta_p = \frac{1}{m}\sum_{i=1}^m \varphi(W_i) + o(\sqrt{\log m/m})\),其中 \(\varphi\) 是融合后的影响函数,方差为 \(\Sigma^2 = V_t/f_t^2\pi_t + V_c/f_c^2\pi_c\)。然后直接套用 AsympCS 定理。
一句话总结本文的数学贡献:证明了聚类数据下的分位数估计量满足渐近线性表示(聚类 Bahadur 表示),且余项以 \(O(\log\log K/K)\) 的速度几乎必然收敛,从而可以嵌入 AsympCS 框架,得到对聚类数据稳健、对任意停止时间有效的分位数置信序列与 QTE 检验。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在线实验中,当数据以"用户-事件"两层结构(聚类数据)呈现、且实验需要连续监测时,如何构造分位数处理效应(QTE)的任意时点有效(anytime-valid)置信序列与序贯检验。
- 核心工具/方法:将聚类 CDF 估计量 \(\hat{p} = \bar{S}/\bar{N}\) 建立为渐近线性估计量(推导聚类版本的 Bahadur 表示),结合 Waudby-Smith et al. [6] 的渐近置信序列(AsympCS)框架,通过顺序统计量逆变换得到分位数置信序列;两组比较时用逆概率加权(IPW)融合为单一估计量。
- 主要结论:CAQ 是第一个同时处理"聚类 + 分位数 + 序贯"三个维度的 QTE 推断方法;模拟表明,在聚类强度变化和重尾分布下,CAQ 是唯一将累积误覆盖率和假阳性率控制在名义水平(≤α=0.05)的方法,而固定时窗基线(Deng et al.)因偷看数据而失效(误覆盖率 0.32–0.36),i.i.d. 序贯基线(Howard-Ramdas)因忽略聚类而失效(误覆盖率随 ICC 增至 0.45)。
关键设定与假设¶
在第二节最小记号的基础上,补全完整设定:
- (A1)单元 i.i.d.:用户 \(i\) 独立同分布进入实验,\(N_i\) 的分布固定,\(\mu_N = \mathbb{E}[N_i] \in (0,\infty)\),\(\mathbb{E}[N_i^2] < \infty\)。这是聚类稳健推断的标准假设,比 [2] 的"观测 i.i.d."更弱——允许组内任意相关。
- (A2)边缘分布平滑:\(F\) 在 \(Q(p)\) 附近二次连续可微,\(f = F'(Q(p)) > 0\)。这是分位数渐近理论的标准假设,用于控制顺序统计量的余项。
- (A3)随机化分配:\(A_i \sim \text{Bernoulli}(\pi_t)\) 独立于潜在结果,\(\pi_t \in (0,1)\) 已知且固定。这使得 QTE 的因果识别无需额外假设(无混杂)。
- (A4)影响函数方差有限:\(\text{var}(\phi_i) \in (0,\infty)\)。这是 AsympCS 定理 [6] 的输入条件。
- 相比已有文献的放宽/强化:相比 [2](Howard-Ramdas),放宽了 i.i.d. 观测假设至"单元 i.i.d.、组内相关";相比 [1](Deng et al.),增加了序贯有效性要求;相比 [3](Waudby-Smith et al.),将 AsympCS 从均值推广到分位数,并处理了聚类结构。
主要结果¶
定理层面(Appendix A 的推导):
- 聚类 CDF 估计的渐近线性:\(\hat{p} - p = \frac{1}{K}\sum_{i=1}^K \phi_i + R_K\),其中 \(\phi_i = (S_i - pN_i)/\mu_N\),\(R_K = O(\log\log K/K)\) a.s.。这个余项速率是关键——它比 AsympCS 边界 \(\sqrt{\log K/K}\) 小一个 \(\sqrt{\log K/\log\log K}\) 因子,保证了时间一致性。
- 聚类 Bahadur 表示:\(\hat{\theta}_p - Q(p) = -\frac{1}{f}(\hat{p} - p) + o(\sqrt{\log K/K})\) a.s.。这把分位数的推断完全归约到 CDF 值的推断。
- QTE 融合:\(\hat{\Delta} - \Delta_p = \frac{1}{m}\sum_{i=1}^m \varphi(W_i) + o(\sqrt{\log m/m})\) a.s.,其中 \(\varphi\) 的方差为 \(\Sigma^2 = V_t/f_t^2\pi_t + V_c/f_c^2\pi_c\)。IPW 融合是精确的(无额外余项),因为 \(\pi_a\) 已知且固定。
- 推论:\(\hat{\Delta} \pm b(m)\sqrt{\hat{\Sigma}^2/m}\) 是 \(\Delta_p\) 的 \((1-\alpha)\)-渐近置信序列,其中 \(b(m) = \sqrt{\frac{2(m\rho^2+1)}{m\rho^2}\log\frac{\sqrt{m\rho^2+1}}{\alpha}}\)。
模拟层面(Table 1, 2, Figure 1–3):
- 数据:\(p=0.90\),\(\alpha=0.05\),\(N_i \sim \text{Uniform}\{5,\dots,15\}\),\(K\) 从 50 到 1000,\(M=500\) 次模拟。正态 DGP 通过 ICC 控制组内相关(0, 0.5, 0.9),对数正态 DGP 检验重尾。
- 单组结果(Table 1):CAQ 的累积误覆盖率在所有 ICC 下均 ≤0.036(目标 α=0.05);Deng et al.(偷看)误覆盖率 0.32–0.36,与 ICC 无关(其误差来自偷看而非聚类);Howard-Ramdas(忽略聚类)误覆盖率从 ICC=0 时的 0.000 增至 ICC=0.9 时的 0.448,与 ICC 强相关。
- 双组结果(Table 2, Figure 1):CAQ 的 FPR 为 0.012(≤α);Deng et al. 和 Howard-Ramdas 的 FPR 分别为 0.356 和 0.342,均严重膨胀。功率方面,CAQ 在 \(\Delta_p = 0.283\) 时达到 0.900,虽低于两个基线(0.774/0.760 在 FPR 膨胀下不可比),但随样本量增加而趋近。
- 宽度自适应(Figure 2–3):CAQ 的区间宽度随 ICC 增大而变宽(反映聚类设计效应),在 ICC=0 时甚至比 Howard-Ramdas 更窄——说明其宽度不是保守地"一律加宽",而是自适应于实际存在的相关性。
真实例子与应用¶
本文为纯模拟验证,无真实数据案例。 模拟设计本身是"半真实"的:正态 DGP 模拟了在线延迟指标(如页面加载时间)的常见分布形态,对数正态 DGP 模拟了重尾场景。但作者未使用任何真实平台数据(如 LaunchDarkly 自身的实验数据)来展示 CAQ 的实际部署效果。这一点限制了对其实际效用的直接评估——模拟中的 ICC 是人为设定的,而真实在线实验中 ICC 的估计本身可能带有不确定性,本文未讨论 ICC 估计误差对 CAQ 有效性的影响。
🔎 结论是否比证明窄¶
- 明确证明的:聚类 CDF 估计的渐近线性(Appendix A 的 Taylor 展开 + 重对数律余项界);聚类 Bahadur 表示;IPW 融合的精确性;由此继承的 AsympCS 性质。
- 被泛化声称但未严格证明的:
- "任意分配比例":文中假设 \(\pi_t\) 已知且固定,但未讨论 \(\pi_t\) 随时间变化(如自适应实验中的动态分配)的情形。若分配比例随时间变化,IPW 融合的"精确性"不再成立,需要额外的余项控制。
- "重尾数据下的有效性":Table 1 显示对数正态 DGP 下 CAQ 的误覆盖率 ≤0.036,但证明中假设 \(F\) 在 \(Q(p)\) 附近二次连续可微且 \(f > 0\)——对数正态分布满足此条件,但更重的尾(如 Cauchy 型,\(f\) 在尾部趋于 0)是否仍成立未讨论。
- "任意停止时间":AsympCS 性质是渐近的,即"在大样本极限下对任意停止时间有效"。模拟中 \(K\) 最大到 1000,但未给出 \(K\) 多小的时候渐近近似开始失效。文中也未讨论"提前停止"(如 \(K=10\) 时就做出决策)的有限样本表现。
- ICC 估计的误差:算法中 \(\hat{V}\) 是样本方差估计,但未讨论 \(\hat{V}\) 的估计误差对置信序列宽度的影响——在 \(K\) 较小时,\(\hat{V}\) 的不确定性可能使区间过窄。
四、开放问题¶
以下问题均扎根于本文的具体语句或证明中的具体步骤,供研究者自行判断价值:
-
有限样本下的有效性边界(扎根于 Appendix A 的"渐近"限定):AsympCS 性质是渐近的,模拟中 \(K\) 最小为 50。要证明/刻画的问题:在 \(K\) 较小(如 \(K < 30\))时,CAQ 的累积误覆盖率是否仍能控制在 α 附近?能否给出一个有限样本的 Berry-Esseen 型界,将 \(K\) 与 ICC、分布尾部联系起来?
-
动态分配比例下的推广(扎根于 Step 2 的"\(\pi_a\) 已知且固定"假设):若实验采用自适应设计(如多臂老虎机或动态流量分配),\(\pi_t\) 随时间变化,IPW 融合的精确性不再成立。要证明/估计的问题:在 \(\pi_t\) 随时间缓慢变化时,CAQ 的额外余项是多少?是否存在一个可容忍的变化速率阈值?
-
ICC 估计不确定性对宽度的影响(扎根于 Algorithm 1 中 \(\hat{V}\) 的使用):\(\hat{V}\) 是样本方差,其估计误差在 \(K\) 较小时不可忽略。要计算/模拟的问题:\(\hat{V}\) 的置信上界能否替代点估计,以构造对 ICC 估计误差稳健的置信序列?这会付出多少宽度代价?
-
重尾分布的极限行为(扎根于假设 A2 的"\(F\) 二次连续可微"):对数正态分布满足假设,但真实在线指标可能具有更重的尾(如延迟数据的 Pareto 型尾部)。要证明/模拟的问题:当 \(f\) 在 \(Q(p)\) 附近趋于 0 或无穷时,聚类 Bahadur 表示的余项速率是否退化?CAQ 是否仍能控制误覆盖率?
-
与 bootstrap 序贯方法的比较(扎根于引言中未提及的空白):作者未引用任何基于 bootstrap 的序贯检验方法。要调查/比较的问题:是否存在聚类 bootstrap 的序贯版本?如果有,其与 CAQ 在有限样本下的误覆盖率和功率对比如何?如果没有,能否构造一个?
-
多分位数联合推断(扎根于 Algorithm 2 的单一分位数检验):本文只处理单一 \(p\) 值(如 \(p=0.90\))。要构造/证明的问题:若同时监测多个分位数(如 \(p=0.50, 0.90, 0.99\)),如何构造联合置信序列以控制整体误覆盖率?这需要处理多重比较与分位数估计量之间的相关性。
提示:要确认上述某条是否是真 gap,建议去读同一子领域(在线实验的序贯推断、聚类数据的置信序列)近期约 5 篇论文的引言——如果多篇都指向同一缺口,说明是共识(真 gap);如果各篇说法互相打架,则可能是机会所在。
Maintained by 陈星宇 · Homepage · Source on GitHub