Monday, March 01, 2021
Zoom Meeting ID: 962 7101 4680
Efficient Algorithms for Fundamental Problems in Data Science
Two important components of data science are data and computation. Sometimes, data is cheap but computation is expensive. Sometimes, data can be expensive (for example, when data are collected from experiments with human subjects). In this talk, I will discuss efficient algorithms addressing fundamental problems in computation and data.
In the first part of the talk, I will discuss structured linear equations and structured linear programs, which are central tools in data analysis. Solving arbitrary linear equations and linear programs can be time-consuming. However, many linear equations and linear programs arising commonly in practice have additional structures that enable faster solvers. I will discuss linear equations with spectral properties, such as Laplacians and their generalizations, and linear equations whose nonzeros have additional geometric structures. Then, I will briefly discuss linear programs that have non-negative variables, coefficients and constants.
In the second part of the talk, I will present an algorithm that improves the design of randomized controlled trials, which are widely used to test the effectiveness of interventions. In a trial, we randomly partition all subjects to a treatment group and a control group. We want the two groups to be similar in covariates — features that we know about the subjects. By exploiting ideas from discrepancy theory, we obtain random partitions with a nearly optimal tradeoff between the gain we have when covariates are correlated with treatment outcomes and the loss we suffer when they are not.
Peng Zhang is a Postdoctoral Associate in Computer Science at Yale University, under the supervision of Daniel Spielman. She obtained her Ph.D. from Georgia Tech, advised by Richard Peng. Her research lies broadly in the design of efficient algorithms. She has worked on structured linear equations and linear programs, discrepancy theory and its application in the design of randomized controlled trials. Her work received the best student paper award at FOCS 2017, and Georgia Tech College of Computing Dissertation Award in 2019.