Algorithmic Discrepancy Theory for Randomized Controlled Trials

EECS Colloquium

Wednesday, March 31, 2021

4:00 - 5:00 pm

Zoom webinar:

Dan Spielman

Professor of Computer Science, Statistics and Data Science, and Mathematics
Yale University

Dan Spielman speaks on "Balancing covariates in randomized experiments using the Gram–Schmidt walk," 03/31/21


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.

This is joint work with Chris Harshaw, Fredrik Sävje, and Peng Zhang.


Daniel Alan Spielman is the Sterling Professor of Computer Science, and Professor of Statistics and Data Science, and of Mathematics at Yale. He received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. After spending a year as an NSF Mathematical Sciences Postdoctoral Fellow in the Computer Science Department at U.C. Berkeley, he became a professor in the Applied Mathematics Department at M.I.T. He moved to Yale in 2005.

The awards he has received include the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2015 Godel Prizes, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, the 2021 NAS Held Prize, a Simons Investigator Award, and a MacArthur Fellowship.  He is a Fellow of the Association for Computing Machinery and a member of the National Academy of Sciences and the Connecticut Academy of Science and Engineering.  His main research interests include the design and analysis of algorithms, network science, machine learning, digital communications and scientific computing.


Video of this Presentation

Dan Spielman: Algorithmic Discrepancy Theory for Randomized Controlled Trials