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

1. Problem Statement

The paper addresses the computational bottleneck in constructing exact confidence intervals (CIs) for the Average Treatment Effect (ATE) in randomized experiments with binary outcomes.

• Context: In finite populations, exact CIs are preferred over asymptotic approximations (like the Central Limit Theorem) because they provide valid coverage guarantees for any sample size, regardless of skewness or heterogeneity.
• Methodology: Exact CIs are typically constructed by inverting randomization tests. This involves checking a candidate ATE value $\tau_0$ against the "sharp null" hypothesis ($Y_{true} = \tilde{Y}$) for all possible completions of the unobserved potential outcomes.
• The Bottleneck: The search space for unobserved potential outcomes grows exponentially ($2^n$). Even when reduced to counts of potential outcome types, the space is $O(n^4)$. Naive enumeration requires testing every configuration, making exact inference computationally prohibitive for moderate-to-large sample sizes.
• Goal: Develop algorithms that significantly reduce the number of randomization tests required to construct these exact intervals, specifically for Bernoulli designs and matched-pairs designs.

2. Methodology

The author proposes a framework that leverages the specific independence structures of Bernoulli and matched-pairs designs to reduce the optimization problem of finding the "worst-case" p-value to a constant number of tests.

A. Core Algorithmic Strategy

The construction of the confidence set $I_\alpha$ involves finding the set of $\tau_0$ values where the maximum p-value over all compatible potential outcome completions is $\geq \alpha$.

1. Binary Search: Due to the monotonicity of the maximum p-value function ($p_{max}$) around the observed test statistic, the authors use a binary search over the candidate set of ATEs. This reduces the number of $\tau_0$ evaluations to $O(\log n)$.
2. Optimization of $p_{max}$: For a fixed $\tau_0$, the challenge is to find the potential outcome completion that maximizes the p-value (i.e., makes the observed statistic look least extreme).
   • Key Insight: Under balanced Bernoulli and matched-pairs designs, the distribution of the centered test statistic can be expressed as a sum of independent Rademacher (values $\pm 1$) and half-Rademacher (values $\pm 1/2$) random variables.
   • Unimodality & Monotonicity: The authors prove that the tail probability (p-value) of this sum is unimodal and monotone with respect to the counts of these random variables.
   • Reduction: Consequently, the maximum p-value is not found by searching the entire space of counts. Instead, it is attained at one of two boundary points (lexicographically largest feasible count vectors) of the feasible region.
   • Result: Computing $p_{max}(\tau_0)$ requires evaluating the p-value for at most two specific configurations.

B. Computational Implementation

• Poisson Binomial Distribution: The p-value calculation reduces to computing the tail probability of a Poisson binomial distribution (a sum of independent non-identical Bernoulli trials).
• Fast Fourier Transform (FFT): To compute these tail probabilities exactly and efficiently, the authors utilize the FFT algorithm, which computes the Cumulative Distribution Function (CDF) in $O(n \log n)$ time. This avoids the need for slow Monte Carlo simulations.
• Integer Linear Programming (ILP): For the matched-pairs design, finding the lexicographically largest feasible count vector involves solving small Integer Linear Programs (with constant dimensions), which can be done in $O(1)$ time.

3. Key Contributions & Theoretical Results

Theorem 1.1: Exponential Speedup

Under balanced Bernoulli or matched-pairs designs, the exact confidence set can be constructed using at most $O(\log n)$ randomization tests.

• Comparison: This is an exponential improvement over brute-force ($O(n^4)$) and a significant improvement over the best-known methods for balanced complete randomization, which require $O(n \log n)$ tests (Aronow et al., 2023).
• Significance: This establishes a sharp separation between designs with independent unit assignments (Bernoulli/Matched) and those with dependent assignments (Complete Randomization).

Theorem 1.2: Information-Theoretic Lower Bound

The authors prove that $\Omega(\log n)$ randomization tests are necessary in the worst case for any deterministic algorithm. This confirms that their $O(\log n)$ upper bound is optimal.

Theorem 1.3: Total Time Complexity

The total time complexity to construct the confidence set is $O(n \log^2 n)$.

• This is achieved by combining $O(\log n)$ binary search steps with $O(n \log n)$ FFT-based p-value evaluations.
• This is deterministic and avoids the variance and computational cost of Monte Carlo approximations.

Theorem 1.4: General Bernoulli Design

For unbalanced Bernoulli designs (where $p \neq 0.5$), the authors extend the method to require $O(n^2)$ randomization tests and $O(n^3 \log n)$ time, matching the efficiency of the best-known procedures for general complete randomization.

4. Results & Simulations

The paper validates the theoretical findings through simulations:

• Accuracy: The exact intervals constructed by the algorithm achieve uniform coverage guarantees across all potential outcome settings, unlike Wald intervals which can undercover in sparse or skewed data scenarios.
• Efficiency:
  • Bernoulli Design: For $n=1000$, the algorithm constructs the interval in under 1.5 minutes (10,000 simulations), whereas brute-force is infeasible.
  • Matched-Pairs Design: The algorithm is significantly faster than brute-force, though slightly slower than the Bernoulli case due to the need to solve small ILPs for each step.
• Interval Width: The exact intervals are slightly wider than asymptotic Wald intervals in sparse settings (due to the discrete nature of the exact distribution), reflecting a more conservative and accurate coverage guarantee.

5. Significance

• Practicality: The paper makes exact finite-sample inference feasible for large-scale randomized experiments (e.g., online A/B tests, clinical trials) where binary outcomes are common.
• Design Comparison: It highlights a fundamental computational advantage of Bernoulli and matched-pairs designs over complete randomization. While complete randomization induces dependence that complicates the optimization landscape, the independence in Bernoulli/Matched designs allows for a drastic reduction in computational complexity.
• Open Question Resolution: The work answers an open question posed by Aronow et al. (2023) regarding how to generalize fast randomization-based constructions to matched-pairs designs.
• Software: A Python implementation is provided, making these advanced exact methods accessible to practitioners.

In summary, this paper bridges the gap between the theoretical desirability of exact inference and the practical constraints of computational complexity, providing optimal algorithms for the most common experimental designs in binary outcome settings.