The most important research advances made by this project have been the development of faster algorithms for solving systems of linear equations and the improvement of the design of randomized controlled trials (RCTs).

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.  However, when we have information about the subjects that could potentially be correlated with the outcome of the trial, we usually want to balance those properties of the subjects between the two groups.

We began working on RCTs when a colleague requested our help in designing a trial to evaluate interventions to improve maternal health outcomes. Our initial solution, which was used in the trial, built upon the expected characteristic polynomial techniques we developed to solve Weaver's problem. But, a better technique with stronger guarantees is required in general.

In our paper, "Balancing covariates in randomized experiments using the Gram-Schmidt walk," we show how to use the recent Gram-Schmidt Walk algorithm of Bansal, Dadush, Garg, and Lovett, to create balanced partitions for RCTs. We begin by cleanly formulating exactly what we require of the partition into test and control groups, and show that what is really required is a random partition that balances subject covariates on average. We then show that the Gram-Schmidt Walk provides a nearly optimal solution to the design of RCTs that compensate for linear influences of covariates on treatment outcomes. This involves developing an optimal analysis of the Gram-Schmidt Walk algorithm, as well as techniques for computing confidence intervals after the experiment has been performed and estimates of the sizes of those confidence intervals.

The problem of solving systems of linear equations arises in many scientific disciplines, including engineering, scientific simulation, and machine learning. Many of the systems of linear equations that must be solved in practice have special structure that can enable us to solve them quickly. In this project, we developed algorithms that can solve a large family of these, called Block Diagonally Dominant Matrices, in nearly optimal time.

This project also supported teaching, mentoring, and outreach activities. 16 undergraduate students worked on research related to this project, as did one postdoc and 3 graduate students. Three new courses were developed as part of this project, and the material of a fourth was incorporated into a 400 page draft of a textbook. The PI gave numerous talks to audiences in the field, to general audiences in mathematics, computer science, and statistics, to general scientific audiences, and a few to the general public.

Last Modified: 12/29/2021
Modified by: Daniel A Spielman