Abstract: In randomized experiments, we randomly assign the treatment that each experimental subject receives. Randomization can help us accurately estimate the difference in treatment effects with high probability. It also helps ensure that the groups of subjects receiving each treatment are similar. If we have already measured characteristics of our subjects that we think could influence their response to treatment, then we can increase the precision of our estimates of treatment effects by balancing those characteristics between the groups.

We show how to use the recently developed Gram-Schmidt Walk algorithm of Bansal, Dadush, Garg, and Lovett to efficiently assign treatments to subjects in a way that balances known characteristics without sacrificing the benefits of randomization.

These allow us to obtain more accurate estimates of treatment effects to the extent that the measured characteristics are predictive of treatment effects, while also bounding the worst-case behavior when they are not.

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

Bio: 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.

He has received many awards, including 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.