Fast Algorithms for Exact Confidence Intervals in Randomized Experiments with Binary Outcomes

这是一篇关于随机化实验中二值结果（Binary Outcomes）平均处理效应（ATE）精确置信区间构建的学术论文。作者 Peng Zhang（罗格斯大学）提出了一种基于随机化检验（Randomization Tests）的快速算法，解决了传统精确推断方法计算成本过高的问题。

以下是对该论文的详细技术总结：

1. 研究背景与问题 (Problem Statement)

• 背景：随机化实验是因果推断的金标准。许多实验（如医学、教育、A/B 测试）的结果是二值的（0 或 1）。
• 挑战：
  • 传统的置信区间构建通常依赖大样本渐近近似（如中心极限定理），在小样本、结果分布偏斜或处理效应异质时可能不准确。
  • 精确置信区间（Exact Confidence Intervals）基于随机化推断，不依赖渐近假设，对所有样本量均有效。
  • 计算瓶颈：构建精确置信区间需要“反转”随机化检验。由于潜在结果（Potential Outcomes）的缺失配置空间随样本量 $n$ 呈指数级增长（$2^n$ 或 $O(n^4)$ 种计数配置），暴力枚举所有可能配置进行检验在计算上是不可行的。
• 目标：开发一种快速算法，在**伯努利设计（Bernoulli Design）和配对设计（Matched-Pairs Design）**下，以极低的计算成本构建精确置信区间。

2. 核心方法论 (Methodology)

论文的核心思想是利用特定实验设计的对称性和独立性，将寻找最大 $p$ 值（$p_{\max}$）的优化问题简化为仅需检查极少数边界点的问题。

2.1 基本框架：反转随机化检验

• 对于给定的候选 ATE 值 $\tau_0$，构建一个与观测数据兼容的潜在结果表 $\tilde{Y}$。
• 计算在该配置下的随机化检验 $p$ 值。
• 置信集 $I_\alpha$ 包含所有满足 $\max_{\tilde{Y}} p(\tilde{Y}) \ge \alpha$ 的 $\tau_0$。
• 难点在于计算 $p_{\max}(\tau_0) = \max_{\tilde{Y} \in \mathcal{Y}(\tau_0)} p(\tilde{Y})$。

2.2 关键算法突破

作者发现，在平衡伯努利设计和配对设计下，$p_{\max}(\tau_0)$ 的优化具有特殊的单调性：

1. 统计量的分布特性：
   • 在平衡伯努利设计中，中心化的 Horvitz-Thompson (HT) 估计量可以表示为独立 Rademacher 变量和半 Rademacher 变量的和（即泊松二项分布的特例）。
   • 在配对设计中，统计量可表示为独立加权的 Rademacher 变量之和。
2. 单峰性与单调性 (Unimodality & Monotonicity)：
   • 证明了 $p$ 值关于潜在结果计数向量（Outcome Count Vectors）具有单调性。
   • 关键结论：为了最大化 $p$ 值（即使得统计量看起来最不极端），只需在可行域内选择**字典序最大（Lexicographically Largest）**的计数向量。
   • 对于给定的 $\tau_0$，满足条件的“最分散”分布（对应最大 $p$ 值）仅出现在可行计数向量集合的至多两个边界点上。
3. 二分搜索 (Binary Search)：
   • 利用 $p_{\max}(\tau_0)$ 在观测统计量 $T^{obs}$ 两侧的单调性，可以在候选 ATE 集合 $\mathcal{T}$ 上执行二分搜索，从而确定置信区间的上下界。

2.3 计算实现

• FFT 加速：计算特定计数配置下的 $p$ 值等价于计算泊松二项分布的尾部概率。作者利用快速傅里叶变换 (FFT) 在 $O(n \log n)$ 时间内精确计算这些概率，避免了蒙特卡洛模拟。
• 整数线性规划 (ILP)：在配对设计中，寻找字典序最大的计数向量被转化为具有常数变量和约束的整数线性规划问题，可在 $O(1)$ 时间内求解。

3. 主要贡献与结果 (Key Contributions & Results)

3.1 理论贡献

• 算法复杂度突破：
  • 平衡伯努利设计 & 配对设计：构建精确置信区间仅需 $O(\log n)$ 次随机化检验（具体为 $8 \log_2 n$ 次）。相比暴力枚举的 $O(n^4)$ 或之前的 $O(n^2)$，实现了指数级加速。
  • 一般伯努利设计：扩展至非平衡情况，需要 $O(n^2)$ 次检验，与完全随机化设计的最新最优结果一致。
• 信息论下界：证明了在最坏情况下，任何确定性算法构建精确置信集至少需要 $\Omega(\log n)$ 次检验，表明上述 $O(\log n)$ 的算法是最优的。
• 设计间的分离：揭示了不同实验设计在计算效率上的本质差异。平衡伯努利和配对设计比平衡完全随机化设计（Balanced Complete Randomization，需 $O(n \log n)$ 次检验）具有更强的计算优势，源于其单元间或单元对间的独立性结构。

3.2 具体定理

• 定理 1.1：在平衡伯努利或配对设计下，置信集 $I_\alpha$ 可通过至多 $8 \log_2 n$ 次随机化检验构建。
• 定理 1.2：信息论下界为 $\Omega(\log n)$，证明上述速率是最优的。
• 定理 1.3：总计算时间为 $O(n \log^2 n)$（包含 $O(\log n)$ 次检验，每次检验耗时 $O(n \log n)$）。
• 定理 1.4：对于一般伯努利设计（$p \in (0,1)$），可在 $O(n^2)$ 次检验和 $O(n^3 \log n)$ 时间内构建。

3.3 实证结果

• 模拟实验：
  • 与暴力枚举相比，算法将检验次数从数千次降低至个位数（例如 $n=100$ 时，从 32032 次降至 9 次）。
  • 与 Wald 渐近区间相比，提出的精确方法在小样本或稀疏结果（Sparse outcomes）场景下具有更好的覆盖率（Coverage），避免了渐近近似导致的覆盖率不足（Under-coverage）。
  • 虽然精确区间在某些稀疏场景下略保守（区间稍宽），但保证了严格的有限样本覆盖保证。
• 运行时间：在 $n=1000$ 时，平衡伯努利设计的 10,000 次模拟总耗时小于 1.5 分钟；配对设计因涉及 ILP 求解，耗时约 2 小时，但在实际应用中仍具可行性。

4. 意义与影响 (Significance)

1. 使大规模精确推断成为可能：将精确置信区间的构建从“仅适用于极小样本”推进到“适用于中等规模甚至大规模实验”，填补了理论精确性与计算可行性之间的鸿沟。
2. 解决开放问题：回答了 Aronow et al. [2023] 提出的关于如何将快速随机化构建方法推广到配对设计的开放性问题。
3. 设计选择的新视角：揭示了实验设计（如伯努利设计 vs 完全随机化）不仅影响统计效率，还显著影响因果推断的计算复杂度。独立性结构（伯努利/配对）能带来计算上的巨大红利。
4. 工具可用性：作者提供了 Python 实现（GitHub 链接），促进了该方法的实际应用。

总结

该论文通过深入分析随机化检验的数学结构，利用单调性和FFT 加速，成功将二值结果下精确置信区间的构建复杂度从多项式级降低到对数级（针对特定设计）。这不仅是一个算法上的突破，也为在小样本或高可靠性要求场景下的因果推断提供了坚实的理论基础和实用工具。