Randomized experiments are the gold standard for establishing causal effects. To test the effectiveness of a drug, a pharmaceutical company randomizes which participants receive the drug and which receive the placebo. However, completely random designs can lead to imbalance between these groups. For example, the control group may be older than it have more men than the treatment group. These imbalances may be problematic, leading to worse estimates of treatment effect when covariates are informative.
In this work, we introduce a new class of experimental designs which allow experimenters to trade off covariate balancing with complete randomness. Our design builds upon a recently introduced algorithm in discrepancy theory, the Gram—Schmidt Walk. We provide a tight analysis of the algorithm and the design, including variance bounds and non-asymptotic tails bounds of the estimated treatment effect. These results indicate that this new class of experimental designs can lead to higher power experiments with fewer participants.