Balancing Covariates In Randomized Experiments Using The Gram–Schmidt Walk

Randomized Controlled Trials (RCTs) are the principal way we estimate the effectiveness of new medications, procedures, policies, and interventions. In a typical medical trial, the subjects are divided into two (or more) groups. One group of subjects is given the new medicine, and the other is given a placebo or old medicine. Randomization is used to ensure that these test and control groups are probably similar and enables us to make statistical statements about the estimated treatment effects. When we know nothing about the experimental subjects, a uniform random assignment of subjects to groups is the best we can do. But, when we know properties of the subjects, called covariates, that we expect could be correlated with the outcome of the trial, we can obtain more accurate estimates of treatment effects by balancing those properties between the groups.

We show how to use the recent Gram-Schmidt Walk algorithm of Bansal, Dadush, Garg, and Lovett to construct balanced RCTs that produce more accurate estimates of treatment effects when treatment outcomes are correlated with linear functions of the covariates, and which can not be much worse than uniformly random RCTs in the worst case.

We will formally explain the experimental design problem we address, the Gram-Schmidt walk algorithm, and the major ideas behind our analyses. This is joint work with Chris Harshaw, Fredrik Sävje, and Peng Zhang.