Dan Spielman (Yale University)

Title: Discrepancy Theory and Randomized Controlled Trials

Abstract: Discrepancy theory tells us that it is possible to partition vectors into sets so that each set looks surprisingly similar to every other.  By “surprisingly similar” we mean much more similar than a random partition. I will begin by surveying fundamental results in discrepancy theory, including Spencer’s famous existence proofs and Bansal’s recent algorithmic realizations of them. Randomized Controlled Trials are used to test the effectiveness of interventions, like medical treatments. Randomization is used to ensure that the test and control groups are probably similar.  When we know nothing about the experimental subjects, uniform random assignment is the best we can do. When we know information about the experimental subjects, called covariates, we can combine the strengths of randomization with the promises of discrepancy theory. This should allow us to obtain more accurate estimates of the effectiveness of treatments, or to conduct trials with fewer experimental subjects. I will introduce the Gram-Schmidt Walk algorithm of Bansal, Dadush, Garg, and Lovett, which produces random solutions to discrepancy problems. I will then explain how Chris Harshaw, Fredrik Sävje, Peng Zhang, and I use this algorithm to improve the design of randomized controlled trials. Our Gram-Schmidt Walk Designs have increased accuracy when the experimental outcomes are correlated with linear functions of the covariates, and are comparable to uniform random assignments in the worst case.

Talk chair: Salil Vadhan

Video