Abstract
We investigate experimental design for randomized controlled trials (RCTs) with both equal and unequal treatment-control assignment probabilities. Our work makes progress on the connection between the distributional discrepancy minimization (DDM) problem introduced by Harshaw et al. (2024) and the design of RCTs. We make two main contributions: First, we prove that approximating the optimal solution of the DDM problem within a certain constant error is NP-hard. Second, we introduce a new Multiplicative Weights Update (MWU) algorithm for the DDM problem, which improves the Gram-Schmidt walk algorithm used by Harshaw et al. (2024) when assignment probabilities are unequal. Building on the framework of Harshaw et al. (2024) and our MWU algorithm, we then develop the MWU design, which reduces the worst-case mean-squared error in estimating the average treatment effect. Finally, we present a comprehensive simulation study comparing our design with commonly used designs.
Introduction
Randomized Controlled Trials (RCTs) are the gold standard for causal inference. While a 50/50 split between treatment and control groups is common, real-world constraints—such as high treatment costs, ethical considerations, or varying group variances—often necessitate unequal assignment probabilities. The challenge lies in achieving covariate balance (ensuring treatment and control groups have similar observed characteristics) while maintaining robustness to unobserved factors.
Existing methods like the Gram-Schmidt Walk (GSW) design provide strong trade-offs for equal splits but falter when probabilities are unequal. In extreme cases, GSW can even underperform a simple Bernoulli (coin-flip) design. This paper addresses these limitations by formalizing the Distributional Discrepancy Minimization (DDM) problem and proposing a novel Multiplicative Weights Update (MWU) approach.
The MWU Algorithm and Design
The authors first establish the computational complexity of the DDM problem, proving that finding an approximate optimal solution within a constant error is NP-hard. This result motivates the development of efficient heuristic algorithms rather than exact solvers.
The core contribution is the MWU Algorithm, which departs from the pure random walk strategy of GSW. Instead, it leverages the Matrix Multiplicative Weights Update framework. The algorithm maintains a weight matrix that identifies directions of significant covariate imbalance and employs a "random walk oracle" to generate assignments that specifically target these imbalances.
By incorporating an augmented covariate matrix governed by a trade-off parameter $\phi$, the resulting MWU Design allows researchers to balance known covariates against unknown confounders. This flexibility ensures the design remains robust across the entire spectrum of assignment probabilities, effectively establishing a "Bernoulli floor" that prevents the design from performing worse than simple randomization.
Experimental Evaluation
The MWU design was evaluated using both synthetic data and the classic Lalonde dataset (NSW and CPS). Key findings include:
- Superior Balance: Across assignment probabilities ranging from 0.025 to 0.975, MWU consistently achieved lower distributional discrepancy than GSW, Rerandomization, and Randomized Block designs.
- Error Reduction: In estimating the Average Treatment Effect (ATE), the MWU design reduced Mean-Squared Error (MSE) by a factor of 2.6x to 3x in linear or near-linear scenarios.
- Statistical Consistency: The authors proved that the MWU estimator is consistent, with the error converging at the standard $O(n^{-1/2})$ rate.
Conclusion and Future Directions
The MWU design represents a significant advancement for RCTs with unequal allocation. While computationally more intensive than GSW, its polynomial-time complexity makes it practical for most clinical and social science applications. Future work may explore incorporating kernel methods to handle non-linear covariate-outcome relationships and further refining the random walk oracle to improve theoretical bounds.
Summary updated