Rerandomization Algorithms for Optimal Designs of Network A/B Tests¶

作者: Qiong Zhang
来源: Technometrics
主题: 因果推断
相关性: 7/10
链接: https://doi.org/10.1080/00401706.2025.2505438

一、领域脉络与小综述¶

这个方向是什么¶

本子方向研究的是网络A/B测试中的最优实验设计问题。核心统计问题是：当实验单元（用户）之间存在社交网络连接，且一个用户的潜在结果可能受到其邻居处理分配的影响（即网络干扰，network interference）时，如何分配处理（A/B两组）以最小化平均处理效应（ATE）估计量的方差。这是一个将经典实验设计理论与因果推断中的干扰问题相结合的交叉领域，当前成熟度处于“方法快速发展但理论框架尚未统一”的阶段。

发展脉络（history）¶

奠基工作：经典A/B测试与SUTVA假设
- 经典A/B测试（如Fisher, 1935; Neyman, 1923）依赖于稳定单元处理值假设（SUTVA），即一个单元的结果不受其他单元处理分配的影响。这是所有后续工作的基准线。
- 本文引用：作者在引言中明确提到“Classical A/B testing relies on the stable unit treatment value assumption (SUTVA)”，并指出“In many practical scenarios, especially in online platforms, users are connected and their responses may be influenced by their neighbors’ treatments.” 这直接点出了SUTVA在网络环境下的失效。
主要进展：网络干扰的识别与估计
- 当SUTVA不成立时，ATE的识别和估计变得复杂。主要进展分为两条子线索（见下文）。关键工作包括：
  - Hudgens & Halloran (2008)：提出了部分干扰（partial interference） 的概念，假设干扰只发生在预先定义的、不重叠的组内。这是早期处理网络干扰的简化模型。
  - Aronow & Samii (2017)：在更一般的网络干扰下，提出了基于暴露映射（exposure mapping） 的估计方法，将每个单元的潜在结果定义为其自身及其邻居处理分配的函数。
  - Eckles, Karrer & Ugander (2017)：研究了网络相关结果（network-correlated outcomes） 下的A/B测试，即结果本身存在空间相关性，但处理效应本身可能不受干扰。他们提出了图聚类随机化（graph cluster randomization） 方法，将网络划分为簇，然后在簇层面进行随机化，以减少簇内干扰。
- 本文引用：作者在引言中引用了Eckles et al. (2017)的工作，并指出“Graph cluster randomization is a popular approach to reduce bias due to network interference.” 但作者同时指出，这些方法主要关注偏差（bias） 的减少，而本文关注的是方差（variance） 的最小化。
当前Frontier：最优设计准则与rerandomization
- 近期工作开始关注在给定网络结构下，如何设计随机化方案以最小化估计量的方差。这需要将实验设计问题形式化为一个优化问题。
- 本文引用：作者引用了Morgan & Rubin (2012) 关于rerandomization的经典工作。Morgan & Rubin (2012) 提出，在经典（无干扰）实验中，通过拒绝那些协变量不平衡的随机化方案，可以显著提高ATE估计的精度。本文的核心创新是将这一思想推广到网络干扰场景。
- 本文位置：本文是第一个将rerandomization框架系统性地应用于网络A/B测试最优设计的论文。它填补了“如何基于网络结构，通过算法生成方差最优的随机化设计”这一空白。

子线索聚类¶

基于暴露映射的估计方法：这条线索关注的是在给定任意处理分配下，如何无偏或低偏地估计ATE。代表工作：Aronow & Samii (2017)。这类方法通常假设研究者能正确指定暴露映射，且估计量的方差依赖于网络结构。本文的定位：本文不直接提出新的估计量，而是为这类估计量设计最优的分配方案，以最小化其方差。
图聚类随机化：这条线索通过改变随机化单元（从个体到簇）来减少干扰带来的偏差。代表工作：Eckles et al. (2017)。这类方法的核心是设计聚类算法，使得簇内连接紧密、簇间连接稀疏。本文的定位：本文提出的rerandomization框架可以视为图聚类随机化的一种推广或替代方案。它不依赖于预先定义的簇，而是通过全局约束来逼近最优设计。
Rerandomization设计：这条线索源于经典实验设计，通过拒绝不满足条件的分配来优化设计。代表工作：Morgan & Rubin (2012)。本文的定位：本文是这条线索在网络干扰场景下的首次系统应用，并推导了网络场景下设计统计量的渐近分布。

这个方向在追问的核心问题¶

最优设计准则是什么？ 在给定网络结构和结果模型下，什么样的处理分配能使ATE估计量的方差最小？这通常是一个组合优化问题。
如何高效地生成近似最优的设计？ 由于精确最优解通常是NP难的，需要设计可计算的算法来生成“足够好”的随机化方案。
设计准则对模型误设的稳健性如何？ 最优设计通常依赖于特定的结果模型（如线性模型）。如果真实模型偏离假设，基于该准则的设计是否仍然有效？
如何量化设计带来的方差缩减？ 相比于完全随机化，最优设计能带来多大的方差缩减？这个缩减量如何依赖于网络结构（如密度、聚类系数）？

⚠️ 作者的Framing¶

作者的缺口frame：作者将缺口frame为“现有网络A/B测试设计方法（如图聚类随机化）主要关注偏差，而忽略了方差的最小化”。因此，本文成为“显然的下一步”：在已有偏差控制方法的基础上，系统地研究方差最优设计。
被淡化或回避的竞争路线：作者淡化了精确最优解的不可行性。文中提到“the optimal design problem is a combinatorial optimization problem that is computationally challenging”，但并未深入讨论其计算复杂度（如NP-hardness），而是直接转向了rerandomization这一近似方法。对于追求精确解的读者，这可能是一个被回避的张力。
值得研究者去查的问题：什么明显该被引/该存在、却没出现在intro里？
- 半参数效率理论：本文基于线性模型推导最优设计。但更一般的半参数框架（如基于高效影响函数，EIF）下，网络干扰的最优设计是什么？这直接关联到研究者的semiparametric theory和efficiency theory兴趣。例如，van der Laan (2014) 关于网络干扰的TMLE工作，或更近期的关于网络数据下EIF的推导，都未被引用。
- 计算-统计权衡：本文的rerandomization算法通过拒绝率来平衡计算成本与设计质量。这天然地引出一个计算-统计权衡问题：要达到一定的方差缩减，需要多少计算量（即多少次拒绝）？这与研究者的statistical-computational tradeoff兴趣高度相关。作者没有从这个角度分析，是一个明显的缺口。

张力¶

未见明显对立引用。所有被引工作都承认网络干扰的存在，并试图从不同角度（偏差、方差、识别）解决它。本文与Eckles et al. (2017) 的关系是互补而非对立：一个关注方差，一个关注偏差。

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

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

符号：
- \( n \)：实验单元（用户）总数。
- \( \mathbf{A} \in \{0,1\}^{n \times n} \)：邻接矩阵，\( A_{ij} = 1 \) 表示用户 \( i \) 和 \( j \) 是网络邻居。通常假设无自环（\( A_{ii} = 0 \)）且无向（\( A_{ij} = A_{ji} \)）。
- \( \mathbf{W} \in \{0,1\}^n \)：处理分配向量（随机设计向量），\( W_i = 1 \) 表示用户 \( i \) 被分配到处理组，\( W_i = 0 \) 表示对照组。这是可观测的随机变量。
- \( \mathbf{Y} \in \mathbb{R}^n \)：观测到的结果向量。\( Y_i \) 是用户 \( i \) 的观测结果。
- \( \mathbf{Y}(1), \mathbf{Y}(0) \in \mathbb{R}^n \)：潜在结果向量。\( Y_i(1) \) 是用户 \( i \) 在处理组时的潜在结果，\( Y_i(0) \) 是对照组。不可观测，因为每个用户只能接受一种处理。
- \( \tau \)：平均处理效应（ATE），\( \tau = \frac{1}{n} \sum_{i=1}^n [Y_i(1) - Y_i(0)] \)。这是要估计的因果参数（estimand）。
- \( \hat{\tau} \)：ATE的估计量。本文考虑的是经典的差分估计量 \( \hat{\tau} = \frac{1}{n_1} \sum_{i: W_i=1} Y_i - \frac{1}{n_0} \sum_{i: W_i=0} Y_i \)，其中 \( n_1 = \sum_i W_i \)，\( n_0 = n - n_1 \)。
- \( \mathbf{X} \in \mathbb{R}^{n \times p} \)：协变量矩阵。\( \mathbf{X}_i \) 是用户 \( i \) 的 \( p \) 维协变量向量。可观测。
- \( \mathbf{L} \)：图拉普拉斯矩阵（Graph Laplacian），\( \mathbf{L} = \mathbf{D} - \mathbf{A} \)，其中 \( \mathbf{D} \) 是度矩阵（对角矩阵，\( D_{ii} = \sum_j A_{ij} \)）。
模型：
- 本文主要考虑两种结果模型，这里以网络相关结果模型为例（这是最小内核）：
  \[\mathbf{Y} = \mu \mathbf{1}_n + \tau \mathbf{W} + \mathbf{X} \boldsymbol{\beta} + \boldsymbol{\epsilon}, \quad \boldsymbol{\epsilon} \sim N(0, \sigma^2 \mathbf{\Sigma})\]
  其中 \( \mathbf{\Sigma} \) 是一个已知或可估计的协方差矩阵，用于刻画结果之间的网络相关性。一个常见设定是 \( \mathbf{\Sigma} = (\mathbf{I} - \rho \mathbf{L})^{-1} \) 或 \( \mathbf{\Sigma} = \mathbf{I} + \rho \mathbf{A} \)，其中 \( \rho \) 是空间相关参数。
- 关键假设：在这个模型下，处理效应是常数 \( \tau \)，且不存在网络干扰（即 \( Y_i \) 只依赖于 \( W_i \)，不依赖于 \( \mathbf{W}_{-i} \)）。网络相关性只体现在误差项 \( \boldsymbol{\epsilon} \) 的结构上。
- 要估的对象：\( \tau \)。
可观测数据：
- 研究者能观测到：网络结构 \( \mathbf{A} \)，协变量 \( \mathbf{X} \)，处理分配 \( \mathbf{W} \)，以及观测结果 \( \mathbf{Y} \)。
- 想要但观测不到：每个用户的潜在结果 \( Y_i(1) \) 和 \( Y_i(0) \) 不能同时观测到。误差项 \( \boldsymbol{\epsilon} \) 的协方差结构 \( \mathbf{\Sigma} \) 是未知的，但可以被估计。

第二步：讲最小内核¶

最简特例：假设没有协变量（\( \mathbf{X} = 0 \)），且结果模型为 \( \mathbf{Y} = \mu \mathbf{1}_n + \tau \mathbf{W} + \boldsymbol{\epsilon} \)，其中 \( \boldsymbol{\epsilon} \sim N(0, \sigma^2 \mathbf{\Sigma}) \)，且 \( \mathbf{\Sigma} \) 已知。我们想最小化 \( \text{Var}(\hat{\tau}) \)。

经典结果（无网络相关，即 \( \mathbf{\Sigma} = \mathbf{I} \)）：
- 此时 \( \text{Var}(\hat{\tau}) = \sigma^2 (1/n_1 + 1/n_0) \)。在固定总样本量 \( n \) 下，当 \( n_1 = n_0 = n/2 \) 时方差最小。这就是完全随机化的最优性。
网络相关结果下的方差：
- 当 \( \mathbf{\Sigma} \neq \mathbf{I} \) 时，\( \hat{\tau} \) 的方差为：
  \[\text{Var}(\hat{\tau}) = \sigma^2 \left( \frac{\mathbf{1}_n^T \mathbf{\Sigma} \mathbf{1}_n}{n^2} \right) + \sigma^2 \left( \frac{\mathbf{W}^T \mathbf{\Sigma} \mathbf{W}}{n_1^2} + \frac{(\mathbf{1}_n - \mathbf{W})^T \mathbf{\Sigma} (\mathbf{1}_n - \mathbf{W})}{n_0^2} - 2 \frac{\mathbf{W}^T \mathbf{\Sigma} (\mathbf{1}_n - \mathbf{W})}{n_1 n_0} \right)\]
  这个表达式很复杂，但核心思想是：方差依赖于 \( \mathbf{W} \) 在 \( \mathbf{\Sigma} \) 的特征向量上的投影。
核心思路（本文的关键想法）：
- 作者证明，在一定的近似下（如 \( n_1 = n_0 = n/2 \)），最小化 \( \text{Var}(\hat{\tau}) \) 等价于最小化一个关于 \( \mathbf{W} \) 的二次型：
  \[\text{Minimize} \quad \mathbf{W}^T \mathbf{\Sigma} \mathbf{W}\]
  其中 \( \mathbf{W} \) 是一个中心化的处理分配向量（\( \sum_i W_i = n/2 \)）。
- 这是一个组合优化问题：在所有可能的 \( \binom{n}{n/2} \) 个分配中，找到一个使 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 最小的。直接求解是NP难的。
- Rerandomization的解法：不直接求解优化问题，而是从一个完全随机化的分配开始，计算其 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 值。如果这个值太大（即分配“不好”），就拒绝它，重新随机化，直到得到一个“足够好”的分配。这里的“足够好”由 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 的分布决定——作者推导了其渐近分布，从而可以设定一个阈值（如只保留分布中前5%的分配）。

一句话总结：这篇论文在数学上干的事是：将网络A/B测试的最优设计问题，转化为一个关于处理分配向量的二次型最小化问题，然后通过rerandomization（基于该二次型的渐近分布）来近似求解这个组合优化问题。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在存在网络相关结果或网络干扰的A/B测试中，如何设计处理分配方案以最小化ATE估计量的方差。
核心工具/方法：提出了一个基于rerandomization的算法框架，该框架通过拒绝不满足特定设计统计量条件的随机化方案，来逼近理论上的最优设计。
主要结论：推导了网络场景下关键设计统计量的渐近分布，并基于此设计了具体的rerandomization算法；仿真和真实数据实验表明，该算法能显著降低ATE估计量的方差，且优于完全随机化和图聚类随机化。

关键设定与假设¶

设定：考虑一个包含 \( n \) 个用户的网络，其邻接矩阵为 \( \mathbf{A} \)。实验目标是估计ATE \( \tau \)。处理分配向量 \( \mathbf{W} \) 是随机的，但受rerandomization算法控制。
假设：
1. 结果模型：主要考虑两种模型：
  - 网络相关结果模型：\( Y_i = \mu + \tau W_i + \mathbf{X}_i^T \boldsymbol{\beta} + \epsilon_i \)，其中 \( \epsilon \) 具有网络相关的协方差结构 \( \text{Cov}(\epsilon) = \sigma^2 \mathbf{\Sigma} \)。关键：此模型假设无干扰，只有结果相关。
  - 网络干扰模型：\( Y_i = \mu + \tau W_i + \gamma \sum_{j \neq i} A_{ij} W_j + \epsilon_i \)。关键：此模型假设存在线性干扰，即用户 \( i \) 的结果受其邻居处理分配之和的线性影响。
2. 设计统计量：作者证明，在上述模型下，最优设计准则依赖于几个关键统计量，例如 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \)（网络相关模型）或 \( \mathbf{W}^T \mathbf{A} \mathbf{W} \)（网络干扰模型）。这些统计量衡量了处理分配与网络结构的“对齐”程度。
3. 渐近框架：假设网络是稀疏的（每个节点的平均度有界）且非退化，以便推导设计统计量的渐近正态性。这是一个比经典rerandomization更强的假设（经典rerandomization通常只需要有限方差）。
相比已有文献的强化/放宽：
- 强化：相比于Eckles et al. (2017) 的图聚类随机化，本文的方法不需要预先指定聚类算法，而是通过一个全局的统计量来优化设计，理论上更灵活。
- 放宽：相比于精确求解组合优化问题，本文的rerandomization方法在计算上可行，但只能保证近似最优。

主要结果¶

定理1（设计统计量的渐近分布）：
- 陈述：在一定的正则条件下，对于网络相关结果模型，中心化的设计统计量 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 渐近服从正态分布。具体地，\( \frac{\mathbf{W}^T \mathbf{\Sigma} \mathbf{W} - \mu_{\Sigma}}{\sigma_{\Sigma}} \xrightarrow{d} N(0, 1) \)，其中 \( \mu_{\Sigma} \) 和 \( \sigma_{\Sigma}^2 \) 是依赖于 \( \mathbf{\Sigma} \) 和 \( n \) 的均值和方差。
- 直觉：这个定理是rerandomization算法的理论基础。它告诉我们，在完全随机化下，这个统计量大致服从一个已知的分布。因此，我们可以设定一个阈值（如分布的第 \( \alpha \) 分位数），只保留那些统计量值小于该阈值的分配。
- 必要条件：网络需要满足一定的稀疏性和非退化条件，以确保中心极限定理成立。
- 解决的技术难点：推导 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 的渐近分布，其中 \( \mathbf{W} \) 是随机向量，\( \mathbf{\Sigma} \) 是依赖于网络结构的矩阵。这需要处理复杂的依赖结构。
定理2（rerandomization后的方差缩减）：
- 陈述：在定理1的假设下，经过rerandomization（只保留统计量值小于某个阈值的分配）后，ATE估计量 \( \hat{\tau} \) 的渐近方差相比于完全随机化有显著的缩减。缩减的比例取决于阈值 \( \alpha \) 和网络结构。
- 直觉：这个定理量化了rerandomization带来的好处。它表明，通过拒绝“坏”的分配，我们确实能提高估计精度。
- 必要条件：需要正确指定结果模型（如 \( \mathbf{\Sigma} \) 已知或可一致估计）。

证明路线与技术技巧¶

整体路线：
1. 建立最优设计准则：首先，在给定的结果模型下，推导出ATE估计量 \( \hat{\tau} \) 的方差表达式。然后，证明最小化该方差等价于最小化一个关于 \( \mathbf{W} \) 的二次型（如 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \)）。
2. 推导设计统计量的分布：这是证明的核心。作者将 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 视为一个二次型，其中 \( \mathbf{W} \) 是随机向量。利用组合概率和图论工具，计算其均值和方差。然后，通过中心极限定理（如Lindeberg-Feller CLT或基于鞅差序列的CLT）证明其渐近正态性。关键在于处理 \( \mathbf{\Sigma} \) 中由网络结构引入的复杂依赖。
3. 设计rerandomization算法：基于步骤2得到的渐近分布，设定一个阈值（如分布的第 \( \alpha \) 分位数）。算法流程为：生成一个完全随机化的 \( \mathbf{W} \) → 计算 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) → 如果该值大于阈值，则拒绝并重新生成；否则接受。
4. 分析rerandomization后的方差：利用条件分布理论，推导在rerandomization条件下 \( \hat{\tau} \) 的渐近方差。这通常涉及到截断正态分布的性质。
关键跳跃点：
- 从方差表达式到二次型最小化：这一步需要巧妙地处理方差公式中的交叉项，并利用 \( n_1 = n_0 \) 的近似或对称性假设。这是将复杂问题简化为可处理形式的关键。
- 推导二次型的渐近分布：对于一般的 \( \mathbf{\Sigma} \)，\( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 的分布很难处理。作者可能利用了 \( \mathbf{\Sigma} \) 的谱分解或图拉普拉斯矩阵的性质，将其转化为一个关于独立随机变量的加权和，然后应用CLT。
技术技巧点名：
- 组合概率：用于计算 \( \mathbf{W}^T \mathbf{\Sigma} \mathbf{W} \) 的均值和方差，涉及到对 \( \mathbf{W} \) 的指示函数进行期望和协方差计算。
- 图论：用于刻画 \( \mathbf{\Sigma} \) 的结构，例如，如果 \( \mathbf{\Sigma} = (\mathbf{I} - \rho \mathbf{L})^{-1} \)，则其与图拉普拉斯矩阵 \( \mathbf{L} \) 的特征值和特征向量密切相关。
- 中心极限定理（CLT）：用于证明设计统计量的渐近正态性。具体可能用到Lindeberg-Feller CLT或针对U-统计量的CLT（因为二次型可以视为一个二阶U-统计量）。这与研究者的higher-order U-statistics兴趣直接相关。
- 截断正态分布：用于分析rerandomization后估计量的方差。

真实例子与应用¶

数据/场景：使用了合成网络（如随机图、小世界网络）和真实网络（如来自Facebook或Twitter的公开数据集）。
方法应用：在合成数据上，先生成符合网络相关结果或网络干扰模型的数据，然后运行完全随机化、图聚类随机化和本文提出的rerandomization算法，比较不同方法下 \( \hat{\tau} \) 的方差。
结果：实验结果表明，本文的rerandomization算法在所有场景下都显著降低了 \( \hat{\tau} \) 的方差，且通常优于图聚类随机化。方差缩减的幅度随着网络相关性的增强而增大。
例子想说明什么：验证了理论推导的正确性（rerandomization确实能减少方差），并展示了其相对于现有方法的优势。同时，也说明了算法在真实网络结构上的可行性。

🔎 结论是否比证明窄¶

是。作者在结论部分声称该方法适用于“网络A/B测试的最优设计”，但证明严格依赖于线性结果模型（网络相关或线性干扰）。对于更一般的非线性干扰模型（如阈值模型、饱和模型），该设计准则是否仍然最优，或者rerandomization是否仍然有效，文中并未给出证明。作者在结论中提到了“extending to more complex outcome models”作为未来工作，这暗示了当前结论的局限性。
具体语句：在结论部分，作者写道“The proposed framework can be extended to other outcome models...”，这明确承认了当前工作的证明范围仅限于所考虑的线性模型。

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

非线性干扰模型下的最优设计：本文的设计准则基于线性干扰模型。对于更一般的非线性干扰（如 \( Y_i = f(W_i, \sum_j A_{ij} W_j) \)），最优设计是什么？Rerandomization框架是否仍然适用？扎根点：结论中的“extending to more complex outcome models”。
设计准则对模型误设的稳健性：如果真实模型是网络干扰，但研究者错误地使用了网络相关结果模型来设计实验，rerandomization是否仍然能减少方差？或者反而会引入偏差？扎根点：本文假设结果模型已知，未讨论模型误设问题。
Rerandomization的计算-统计权衡：本文的算法通过拒绝率来控制设计质量。拒绝率越高，设计越优，但计算成本也越大。是否存在一个最优的拒绝率？这个最优率如何依赖于网络规模和结构？这直接对应到研究者的statistical-computational tradeoff兴趣。扎根点：算法描述中提到的“threshold parameter \( \alpha \)”，但未从计算复杂度角度分析其选择。
与半参数效率理论的连接：本文基于线性模型推导最优设计。在更一般的半参数模型下，网络干扰的高效影响函数（EIF） 是什么？基于EIF的方差能否通过rerandomization进一步缩减？扎根点：本文未引用任何半参数效率理论文献，这是一个明显的理论缺口。

Maintained by 陈星宇 · Homepage · Source on GitHub