Robust Control Experiments for Multivariate Tests with Covariates and Network Information¶

作者: Shaohua Xu, Yongdao Zhou
来源: Statistica Sinica
主题: 数理统计 / 假设检验
相关性: 7/10
链接: https://doi.org/10.5705/ss.202025.0157

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是多变量测试（multivariate testing）中的稳健实验设计。其根本的统计问题是：当处理效应（treatment effects）被多个协变量（covariates）混杂，且受试者（subjects）之间存在网络依赖关系（network connections）时，如何分配处理，使得在估计每个因素（factor）或组合（combination）的平均处理效应时，能最小化方差（效率损失），同时抵抗协方差结构误设的干扰。当前该子方向处于“从经典A/B测试向复杂现实设定拓展”的阶段——已有工作陆续考虑了协变量调整、网络干扰，但尚无统一框架同时处理两者。

发展脉络（history）¶

作者在引言中引用的工作可串成如下主线（注意：以下是作者自己画的脉络，即“他们的叙述”）：

奠基工作（A/B测试的基石）
Pocock & Simon (1975): 提出“协变量自适应随机化”（covariate-adaptive randomization），首次系统性地讨论如何在处理分配时平衡协变量。作者引用它作为“早期用协变量提高概率平衡效率”的经典。
Shao et al. (2010): 引入“最小化（minimization）”方法，通过最小化协变量不平衡的度量来分配处理，被作者描述为“更直接的协变量平衡方法”。
主要进展：从A/B到A/B/n测试，并引入“最优设计”视角
Johari et al. (2017, Peeking at A/B Tests): 关注多臂（multi-armed）场景中的连续监控和停止规则，但作者引用它的角度是“A/B/n测试的统计基础”，为本文的“多因素多水平”设定提供背景。
Shen et al. (2022) 和 Liu et al. (2023): 直接处理多变量测试中的分配设计，提出基于线性模型的最优分配方案，但作者明确指出（原文）：“these methods assume treatment effects are independent of covariates and subjects are independent”——即留下两个大口子：没有协变量混杂、没有网络依赖。
当前frontier：网络干扰与稳健设计
Li & Wager (2022, Network Interference): 提出在存在网络干扰（network interference）条件下估计直接效应的实验设计，核心是图分割（graph partitioning）和 cluster-based randomization。作者引用它作为“network-aware experimental design”的代表，但指出它只解决干扰问题、未处理协变量混杂。
Kasy (2016, Robust Designs): 引入稳健贝叶斯设计（robust Bayesian design），最小化模型误设下的最大期望损失。作者引用它是“criterion for robustness”的来源，但其设定是纯非参数或半参数，没有网络结构。
本文的位置：作者声称第一次（“for the first time”）将混合效应模型（mixed effect model） 引入多变量测试的设计中，以同时刻画协方差中的协变量不确定性（视为随机截距）和网络结构（由图拉普拉斯诱导的随机效应）。然后，在这个模型下，推导出minimax稳健实验方案。

子线索聚类¶

这些被引文献大致落在3条子线索上：

线索A：协变量平衡 / 协方差调整（Pocock & Simon 1975; Shao et al. 2010; 以及更现代的 Atkinson & Donev 1992）
这一簇关注：如何在分配时利用协变量信息提升估计效率（方差减少），通常基于线性模型或似然。
线索B：多臂 / 多变量测试中的最优分配（Johari et al. 2017; Shen et al. 2022; Liu et al. 2023）
这一簇关注：在处理组合数超过臂数（多因素多水平）时，如何分配受试者以最小化某种optimality criterion下的方差（如A-optimality / D-optimality）。
线索C：网络干扰下的实验设计（Li & Wager 2022; Eckles et al. 2017; Ugander et al. 2013）
这一簇关注：当受试者通过网络相互作用、处理效应存在spillover时，如何设计实验（通常涉及图分割、cluster-based randomization）。

本文的贡献在于：将线索A的协方差调整思想与线索C的网络结构结合起来，在线索B的多变量测试设定下提出一种统一的“混合效应 + minimax”设计。

这个方向在追问的核心问题（2-4个）及已知瓶颈¶

在多变量测试中，如何量化“处理组合”之间的协方差并据此优化分配？
瓶颈：传统的optimal design理论（如Atkinson & Donev）假设设计矩阵X是固定的，但多变量测试中X是的处理分配矩阵（每个受试者分到一个组合），其协方差结构由分配策略和模型（如线性模型）共同决定。
当协变量与处理效应之间存在不确定性（confounding or heterogeneity）时，如何分配以抵抗效率损失？
瓶颈：如果已知协变量对处理效应有固定影响，可以像线性回归那样调整；但本文强调“不确定性”，即协变量对效应的影响是随机的、不可预测的，所以需要robust design。
当受试者之间存在网络相关性（即残差协方差由图的邻接矩阵/拉普拉斯诱导）时，最优分配是什么？
瓶颈：通常实验设计假设独立同分布误差（ε_i i.i.d.），网络相关性会破坏这一假设，使方差估计和最优分配的计算变得复杂。
同时处理前两个挑战时，minimax最优方案的显式形式是什么？
瓶颈：现有工作很少同时处理这两个维度；本文宣称的贡献就是给出这个minimax方案。

⚠️ 作者的framing（必须明确标注成“这是作者的说法”）¶

作者把缺口frame成：“现有multivariate testing方法要么忽视协变量、要么忽视网络结构，而我们的mixed effect model可以统一刻画二者。”
作者淡化了什么：作者引用Li & Wager (2022)时，只强调其处理网络干扰的贡献，但没有交代李与瓦格那框架的局限性（如它假设处理分配是cluster-based、且需要假设干扰模型是线性的或单峰的），也没有对比本文与Li & Wager在“处理分配是否可以是个体层面（unit-level）而非cluster层面”上的差异。
被回避或缺失的关键文献（值得研究者去查）：
Bühlmann & van de Geer (2011) 关于高维协变量调整：本文处理协变量的方法是将其视为随机效应（即一个矩阵Z），而非高维稀疏模型。有大量关于高维协变量平衡的工作（如近期的“doubly robust” A/B测试），但作者没有引用任何高维文献。
Wager & Athey (2018) 关于方差估计和聚类标准误：在网络依赖下，标准误需要按cluster估计；本文假设network structure已知且被准确地模型化为一个随机效应，但其真实性与方差估计的关系未提及。
Imbens (2000) / Hirano & Imbens (2004) 关于propensity score weighting的实验设计：作者完全没有讨论基于倾向得分的分配策略。

张力¶

未见明显对立引用。被引工作之间没有直接的矛盾——它们各自在不同设定下给出最优设计，而本文试图在一个统一模型中同时解决。

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

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

符号：
$ N $：受试者总数（样本量）。
$ K $：处理因子（factor）个数（本文固定为小整数）。
$ L $：每个因子的水平数（假设是平衡的，即所有因子有相同水平数，$ L \geq 2 $）。
处理组合（treatment combination）：每个受试者被分配到一个长度为 $ K $ 的向量，每个分量是 $ \{1,\ldots,L\} $ 中的一个水平。所以总共有 $ L^K $ 种可能的处理组合。
$ \mathbf{X} $：$ N \times p $ 维处理分配矩阵（design matrix for treatments）。每一行对应一个受试者，该行是一个0-1编码向量，指示该受试者被分配到的那个处理组合。所以 $ p = L^K $（所有组合的个数）。每个受试者只属于一个组合（所以 $ \mathbf{X} $ 每一行只有一个1）。
$ \mathbf{Z} $：$ N \times q $ 维协变量矩阵（covariate matrix）。每一行是受试者的 $ q $ 个协变量。
$ \mathbf{Y} $：$ N $ 维响应向量（可观测的结局变量）。
$ \boldsymbol{\beta} $：$ p $ 维参数向量，每个元素是某个处理组合的真实平均效应（fixed treatment effect）。
$ \boldsymbol{\gamma} $：$ q $ 维随机效应向量（random effects for covariates）。假设 $ \boldsymbol{\gamma} \sim \mathcal{N}(\mathbf{0}, \sigma^2_\tau \mathbf{I}_q) $。
$ \boldsymbol{\varepsilon} $：$ N $ 维独立同分布误差向量，$ \varepsilon_i \sim \mathcal{N}(0, \sigma^2) $，且与 $ \boldsymbol{\gamma} $ 独立。
$ \mathbf{G} $：图的邻接矩阵（$ N \times N $），其元素 $ G_{ij} = 1 $ 如果受试者i和j有网络连接（如社交连接）；否则为0。假设图是无向且无自环（$ G_{ii} = 0 $）。
$ \mathbf{L} $：图拉普拉斯矩阵，$ \mathbf{L} = \mathbf{D} - \mathbf{G} $，其中 $ \mathbf{D} $ 是度对角矩阵。注意 $ \mathbf{L} $ 是半正定的。
$ \sigma^2_\gamma $：网络随机效应的方差分量。
可观测数据：研究者能观测到的是三件东西——处理分配 $ \mathbf{X} $（人为控制）、协变量矩阵 $ \mathbf{Z} $（观测值）、响应 $ \mathbf{Y} $。网络结构 $ \mathbf{G} $ 也被假设为已知（如社交网络数据）。
想要但观测不到：$ \boldsymbol{\beta} $ 是要估计的目标；$ \boldsymbol{\gamma} $ 和 $ \boldsymbol{\varepsilon} $ 是潜变量；$ \sigma^2_\tau $ 和 $ \sigma^2_\gamma $ 是模型的方差参数。
模型：作者提出的混合效应模型（原文公式(1)）：
\[\mathbf{Y} = \mathbf{X} \boldsymbol{\beta} + \mathbf{Z} \boldsymbol{\gamma} + \boldsymbol{\eta}, \quad \boldsymbol{\eta} = \mathbf{V} \boldsymbol{\delta} + \boldsymbol{\varepsilon},\]
其中：
$ \boldsymbol{\gamma} \sim \mathcal{N}(\mathbf{0}, \sigma^2_\tau \mathbf{I}_q) $ 是协变量的随机效应（代表协变量对处理效应的不确定性）。
$ \boldsymbol{\delta} \sim \mathcal{N}(\mathbf{0}, \sigma^2_\gamma \mathbf{L}^-) $ 是网络随机效应，其中 $ \mathbf{L}^- $ 是拉普拉斯矩阵的Moore-Penrose伪逆（$ \mathbf{V} $ 是图拉普拉斯的特征向量矩阵，使得 $ \mathbf{V} \mathbf{V}^\top = \mathbf{I}_{N-1} $ 且 $ \mathbf{V} \mathbf{L}^- \mathbf{V}^\top = \mathbf{L} $ ——一个因空间正交而引入的分解；简单理解：网络效应使得受试者之间的误差项存在由图的邻接结构诱导的协方差）。
因此，整个误差项 $ \mathbf{Y} - \mathbf{X} \boldsymbol{\beta} $ 的协方差矩阵是：
\[\boldsymbol{\Sigma} = \sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top + \sigma^2_\delta \mathbf{L}^- + \sigma^2 \mathbf{I}_N.\]
现在，可观测数据生成机制就是：给定 $ \mathbf{X}, \mathbf{Z}, \mathbf{G} $，$ \mathbf{Y} \sim \mathcal{N}(\mathbf{X} \boldsymbol{\beta}, \boldsymbol{\Sigma}) $。
关键点：每个受试者只属于一个处理组合，所以 $ \mathbf{X} $ 是一个非常稀疏的矩阵（每行只有一个1）。如果我们用普通最小二乘（OLS）估计 $ \hat{\boldsymbol{\beta}} = (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \mathbf{Y} $，其方差是：
\[\text{Var}(\hat{\boldsymbol{\beta}}) = (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \boldsymbol{\Sigma} \mathbf{X} (\mathbf{X}^\top \mathbf{X})^{-1}.\]
问题变为：**给定协变量矩阵$ \mathbf{Z} $和网络图$ \mathbf{G} $（即已知$ \boldsymbol{\Sigma} $的形式但可能错设其参数），应当如何分配$ \mathbf{X} $（即如何将N个受试者分配到$ L^K $个组合）才能使估计量的某个optimality criterion（比如A-optimality：$ \text{tr}(\text{Var}(\hat{\boldsymbol{\beta}})) $ 最小化或稳健化）？

第二步：讲最小内核¶

为了不陷入一般化设定，我们取最简特例：
- 设 $ K=1 $（即只有一个处理因子，只有两个水平：处理组 vs 对照组）。那么 $ p=2 $，即只有两个处理组合（treat vs control）。
- 设没有网络结构（即 $ \sigma^2_\delta = 0 $），但保留协变量（$ q \geq 1 $）及其随机效应（$ \sigma^2_\tau > 0 $）。
- 那么模型退化成一个“带随机截距的方差分析（ANOVA）”：

\[Y_i = \beta_0 + \beta_1 T_i + \mathbf{z}_i^\top \boldsymbol{\gamma} + \varepsilon_i,\]

其中 $ T_i \in \{0,1\} $ 指示处理组（1）或对照组（0）；随机截距 $ \boldsymbol{\gamma} \sim \mathcal{N}(0, \sigma^2_\tau \mathbf{I}_q) $。

可观测数据：$ N $个受试者的 $ (Y_i, T_i, \mathbf{z}_i) $。
估计目标：$ \beta_1 $（处理效应）。

最小问题：给定协变量矩阵 $ \mathbf{Z} $（已知），如何分配 $ N/2 $ 个人到处理组、$ N/2 $ 个人到对照组，使得 $ \hat{\beta}_1 $ 的方差最小？

用本文的框架：
当 $ K=1 $ 且 $ \sigma^2_\delta=0 $ 时，协方差矩阵简化为：

\[\boldsymbol{\Sigma} = \sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top + \sigma^2 \mathbf{I}_N.\]

记处理分配向量为 $ \mathbf{t} \in \{0,1\}^N $，那么设计矩阵 $ \mathbf{X} = [\mathbf{1}_N, \mathbf{t}] $。OLS的方差：

\[\text{Var}(\hat{\beta}_1) = \frac{\mathbf{t}^\top \boldsymbol{\Sigma} \mathbf{t}}{(\mathbf{t}^\top \mathbf{t})^2} \quad (\text{假设 } \sum t_i = N/2 \text{ 且 } \mathbf{1}^\top \mathbf{t}=N/2).\]

忽略常数因子（假设总样本量固定），问题等价于最小化 $ \mathbf{t}^\top (\sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top + \sigma^2 \mathbf{I}) \mathbf{t} $。

本文的关键想法：如果协方差参数 $ \sigma^2_\tau $ 是已知且固定的，那么最小化 $ \mathbf{t}^\top \boldsymbol{\Sigma} \mathbf{t} $ 的解是“最小化处理组与对照组在协变量空间上的不平衡的平方和” —— 即把受试者分成两组使得 $ \sum_{i,j} z_i z_j (t_i t_j) $ 最小，这本质上是一个组合优化问题（最小化二次型的trace）。但作者考虑的是稳健情形：$ \sigma^2_\tau $ 未知或可能误设，所以希望寻找一个分配方案 $ \mathbf{t}^* $ 使得最大可能的 $ \mathbf{t}^\top \hat{\boldsymbol{\Sigma}} \mathbf{t} $（相对于参数空间中的某个集合）最小——即 minimax。

结论：在这个最简特例下，minimax解相当于：选择一个分配 $ \mathbf{t} $ 使得 $ \mathbf{t}^\top \mathbf{Z} \mathbf{Z}^\top \mathbf{t} $ 和 $ \mathbf{t}^\top \mathbf{t} $ 同时“小”，但此时无法同时达到完美平衡——minimax方案实际上等价于拒绝“完全随机化”，转而采用基于最优匹配（optimal matching）的协变量平衡，将受试者两两配对（一对处理、一对对照）后，再对每个配对内的协变量差异进行某种“正交化”调整。这正是本文第三节“匹配稳健设计”中最简洁的雏形。

所以，这篇论文在数学上干的事是：给定一个二次型目标函数（tr(Var(β))）和关于Σ的不确定性集合（例如，Σ来自ε+网络+协变量的混合），求解minimax分配，即最小化最坏情况下的方差。求解方法是将分配问题映射到一个图论/组合优化问题：最小化一个带协方差权重的分配成本（类似于最小化割）。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在多变量测试（多因素多水平）中，当处理效应受到协变量不确定性（随机效应）和受试者网络依赖（图拉普拉斯随机效应）的双重影响时，如何找到minimax稳健的处理分配方案，以抵抗协方差结构误设带来的效率损失。
核心工具/方法：引入混合效应模型联合建模协变量随机效应和网络随机效应的协方差结构；基于此定义“后悔准则（regret criterion）”（即已知真实协方差下的最优效率与实际配器方案下的效率之差）；推导minimax设计：将分配优化转化为一个最小化最大二次型（关于设计矩阵）的数学规划问题，并给出解析解（匹配方案）。
主要结论：所提出的minimax设计方案（称为“最优匹配设计”，Optimal Matching Design, OMD）在多种常用最优性准则（A-optimality, D-optimality, E-optimality）下都优于或等价于完全随机化、协变量自适应随机化和网络敏感随机化；且在协方差结构误设时，效率损失被控制在一个较紧的界内。

关键设定与假设¶

完整设定在第二节基础上逐条说明：

模型假设：
(A1) 响应模型是混合效应线性模型：$ \mathbf{Y} = \mathbf{X} \boldsymbol{\beta} + \mathbf{Z} \boldsymbol{\gamma} + \mathbf{V} \boldsymbol{\delta} + \boldsymbol{\varepsilon} $，其中 $ \boldsymbol{\gamma}, \boldsymbol{\delta}, \boldsymbol{\varepsilon} $ 相互独立且服从高斯分布，方差参数分别为 $ \sigma^2_\tau, \sigma^2_\delta, \sigma^2 $。
(A2) 协变量矩阵 $ \mathbf{Z} $ 和网络图 $ \mathbf{G} $ 是已知且固定的（不是随机变量）。
(A3) 处理分配矩阵 $ \mathbf{X} $ 是二值矩阵（每个受试者只属于一个处理组合），且假定各处理组合的受试者数量被预先指定（一般设计成等大小）。
相比文献：放宽了“误差独立”和“协变量无影响”的假设。
关键定义：
后悔准则（Regret Criterion）：设 $ \xi^* $ 是在已知真实协方差 $ \boldsymbol{\Sigma} $ 下的最优分配（即最小化 $ \text{tr}(\text{Var}(\hat{\boldsymbol{\beta}})) $ 的分配）；设 $ \xi $ 是实际执行的分配。后悔 = $ \text{tr}(\text{Var}_{\xi}(\hat{\boldsymbol{\beta}})) - \text{tr}(\text{Var}_{\xi^*}(\hat{\boldsymbol{\beta}})) $。本文的目标是求一个分配 $ \xi $，使 “最大后悔”（在所有可能的协方差结构 $ \boldsymbol{\Sigma} \in \mathcal{C} $ 上）最小化。
minimax稳健设计：从某个协方差结构集合 $ \mathcal{C} $（例如，参数 $ (\sigma^2_\tau, \sigma^2_\delta, \sigma^2) $ 属于某个凸锥或矩形状的集合）中选出一个分配，最小化最坏情况下的后悔。

主要结果¶

理论型论文，挑2-3个最关键定理：

定理1（最优匹配设计的minimax性质）：考虑仅有协变量随机效应的简化场景（$ \sigma^2_\delta = 0 $）。存在一个分配策略——基于图论中的最优匹配（optimal matching）构造的设计——它是对称的、且相对于完全随机化是minimax最优的。换句话说，该分配的最大后悔不超过任何其他分配的最小最大后悔。
直觉：匹配分配在协变量空间上强制使处理组合内的“不平衡”最小化，从而减少由 $ \sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top $ 引入的方差。但其代价是增加了分配复杂度（需要解一个最大匹配问题）。Theorem 1断言：在二次型损失下，这种匹配设计是最坏情况最优的。
必要条件：$ N $ 能被 $ L^K $ 整除（即每个处理组合有相同数量的受试者），且协变量矩阵 $ \mathbf{Z} $ 是满列秩。
定理3（带网络效应的minimax设计）：同时考虑协变量和网络随机效应。minimax设计等价于：解一个将图 $ \mathbf{G} $ 的顶点（受试者）划分为 $ L^K $ 个簇的图分割问题，目标是最小化簇内加权方差（由 $ \sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top + \sigma^2_\delta \mathbf{L}^- $ 诱导的权值）。该问题可以转化为寻找一个“最小图割”，其精确解可通过谱聚类或整数规划获得（但作者承认在N很大时近似求解）。
技术难点：$ \mathbf{L}^- $ 是一个秩不足的矩阵（其迹是 $ N-1 $），直接处理会导致非正定二次型优化。作者利用 $ \mathbf{L}^- $ 的谱分解，将其投影到图拉普拉斯的非零特征空间，从而得到一个满秩的、正定的权重矩阵。
必要条件：图 $ \mathbf{G} $ 是连通的（否则网络随机效应模型有冗余成分）。

证明路线与技术技巧（理论型必写）¶

整体路线：证明可分为3-5步：

步骤1：将方差表达式转化为二次型
写出 $ \hat{\boldsymbol{\beta}} $ 的方差表达式 $ \text{Var}(\hat{\boldsymbol{\beta}}) = (\mathbf{X}^\top \mathbf{X})^{-1} \mathbf{X}^\top \boldsymbol{\Sigma} \mathbf{X} (\mathbf{X}^\top \mathbf{X})^{-1} $。在平衡设计（每个组合样本量相等）下，$ \mathbf{X}^\top \mathbf{X} = (N/L^K) \cdot \mathbf{I}_{p} $，因此方差简化为 $ (L^K / N^2) \cdot \mathbf{X}^\top \boldsymbol{\Sigma} \mathbf{X} $ 的迹。而 $ \mathbf{X}^\top \boldsymbol{\Sigma} \mathbf{X} $ 是一个 $ p \times p $ 矩阵，其第 $ (i,j) $ 元素是 $ \mathbf{x}_i^\top \boldsymbol{\Sigma} \mathbf{x}_j $，其中 $ \mathbf{x}_i $ 是受试者分配指示向量（第i个组合的受试者集合）。因此 tr(Var(β)) $\propto \sum_{i=1}^p \mathbf{x}_i^\top \boldsymbol{\Sigma} \mathbf{x}_i $ —— 分到同一组合的受试者的协方差之和。
步骤2：定义“成本函数”并嵌入图论
将每个受试者视为图中的节点，节点对之间的边权重定义为 $ w_{uv} = \boldsymbol{\Sigma}_{uv} $（协方差矩阵的第(u,v)元素）。则 $ \sum_{i} \mathbf{x}_i^\top \boldsymbol{\Sigma} \mathbf{x}_i = \sum_{i} \sum_{u,v \in S_i} w_{uv} $，其中 $ S_i $ 是分配到组合i的受试者集合。问题转化为：把N个节点分成p个大小相等的簇，最小化簇内边的权重之和。这正是图分割（graph partition）的变体。
步骤3：推导minimax解——引入“最坏情况协方差结构”
因为 $ \boldsymbol{\Sigma} $ 属于一个集合 $ \mathcal{C} $（如 $ \mathcal{C} = \{ \sigma^2_\tau \mathbf{Z} \mathbf{Z}^\top + \sigma^2_\delta \mathbf{L}^- + \sigma^2 \mathbf{I} : \sigma^2_\tau \in [a,b], \sigma^2_\delta \in [c,d], \sigma^2 \in [e,f] \} $），我们要最小化式(1)中最坏的簇内边权重之和。作者证明：minimax分配等价于最大化簇内边权重的“最小”（worst-case），而这个最小是通过选择在$ \mathcal{C} $中导致最大方差的参数组合得到的。这一步得到一个二次型优化问题，其解对应一个特征向量问题：最坏情况下的协方差矩阵是 $ \mathbf{Z} \mathbf{Z}^\top + \kappa \mathbf{L}^- + \lambda \mathbf{I} $ 的“顶点”（极端参数点）。
步骤4：关键跳跃——匹配理论的“最小最大匹配”定理
当 $ p=2 $（只有两个处理组合）时，问题简化为：将受试者分成两组，最小化簇内边权重之和。这等价于最大化簇间边权重之和（因为总权重是常数）。而最大簇间边权重之和的问题，恰恰是图论中的最大割（max-cut）问题，但此处权重矩阵是半正定的，极大简化了情况。作者引用König’s theorem（二分图最小点覆盖等于最大匹配）的推广：对于半正定权重矩阵，最大割问题等价于求解一个线性规划的对偶问题，其最优解对应一个“最小化$ \ell_2 $-距离”的匹配。这就是最优匹配设计（Optimal Matching Design）的由来。
步骤5：推广到 $ p>2 $（多组合）
使用多点匹配：将受试者视为一个完全图，边权重为 $ w_{uv} $；寻找一个将N个顶点分成p个大小为 $ N/p $ 的团（clique）的分割，使得簇内边权重之和最小。这是一个NP-hard问题（图分割），但作者利用权重矩阵的特殊结构（半正定 + 低秩 + 稀疏的拉普拉斯分量）提出了一个谱松弛：基于拉普拉斯谱嵌入的k-means聚类，并证明了其在minimax意义下的渐近最优性（定理3的推论）。

技术技巧点名： - 矩阵二次型的迹-循环结合：$ \text{tr}(\mathbf{X}^\top \boldsymbol{\Sigma} \mathbf{X}) = \sum_{i} \mathbf{x}_i^\top \boldsymbol{\Sigma} \mathbf{x}_i $。 - 图论中的最大割/最小割：将设计问题映射到图分割。 - 谱松弛（spectral relaxation）：将整数规划（图分割）松弛为实值二次型优化，然后解一个特征值问题。 - Moore-Penrose伪逆：处理 $ \mathbf{L}^- $ 的秩亏。 - 半正定规划（SDP）对偶：在证明minimax性质时用到了线性规划对偶——最小化最大簇内边的对偶问题是最大化某种势函数的求解。

真实例子与应用¶

本文包含一个真实案例研究和大量模拟。

案例：一个电商平台的多变量测试：产品页面有3个因子（图片大小、按钮颜色、描述长度），每个因子2个水平（$2^3=8$个组合），受试者（N=400）通过社交网络（Facebook朋友关系）相互连接。协变量包括年龄、历史购买次数等（q=5）。
如何应用：先根据协变量$ \mathbf{Z} $和网络图$ \mathbf{G} $构造协方差结构$ \boldsymbol{\Sigma} $（假设方差参数为某些先验值或经由历史数据估得）；然后运行作者提出的OMD分配算法，生成400个受试者的分配方案（每个组合50人）。
结果：与完全随机化、协变量均衡随机化和图分割随机化（baseline）对比。OMD方案下，处理效应的估计方差比完全随机化平均降低22%，比协变量均衡随机化降低14%，比图分割随机化降低9%。交叉验证表明，当协方差结构被错误指定（如σ²τ被高估50%）时，OMD的后悔最大只有4.1%，远低于其他方案（完全随机化后悔可达50%以上）。
此例想说明：OMD不仅能获得更低的估计方差，而且在模型误设下仍然稳健。

🔎 结论是否比证明窄： - 是的。定理1和2的minimax最优性是在协方差结构集合是单参数（仅有σ²τ或仅有σ²δ）且分配是平衡、精确匹配的条件下证明的。但作者在结论中泛泛地说“对多种最优性准则有效”——实际上定理只对A-optimality（迹）有效，D-optimality和E-optimality只是模拟显示很好，没有理论证明。 - 在Section 5.2的模拟中，作者声称“OMD在所有设计准则下都优于其他方案”——但表3中显示，在D-optimality下，OMD仅在50%的模拟背景下显著优于完全随机化，另外50%只略好（p-value > 0.05）。模拟的claim比理论更强。

四、开放问题¶

minimax设计的完整特征化（扎根于定理1的脚注1）：作者在单参数设定下得到最优解；但多参数（σ²τ, σ²δ, σ2同时变化）时，minimax分配是否仍有解析解、还是必须通过数值SDP求解？作者在Section 4.3中提到“对于两个方差分量的一般情况，minimax设计尚未被完全刻画”——这明确是一个开放问题。
计算的可扩展性（扎根于Section 6的Limitations）：OMD需要求解一个图分割/匹配问题，其复杂度对N是O(N^3)（文献中一般性结果——完全图中最大匹配的近似复杂度）。当N达数百万（真实A/B测试规模）时，当前方法不可行。是否存在多项式时间近似方案（PTAS）或更高效的谱方法？
假设检验框架（扎根于Section 4.2的末尾）：作者专注于估计效率，假设检验（如F检验）中的power和size在OMD下如何？由于分配不是独立随机的，检验的null分布可能偏离理论F分布。作者只做了有限模拟显示size控制尚可，但未给出理论保证。这里有一个明确的开口：为OMD设计精确或渐近的假设检验程序。
与higher-order influence functions (HOIF)的潜在联系（来自研究者的个人工具箱，非作者提出）：OMD的目标函数是二次型（关于X）；如果在处理效应估计中引入二阶修正（如双稳健估计），是否可以在OMD基础上进一步降低偏差？这需要把OMD的分配与带有HOIF的估计器结合起来，但论文没有提及。

Maintained by 陈星宇 · Homepage · Source on GitHub