Aarti Singh, PhD:
Computationally tractable and near optimal design of experiments
In many applications, we have access to large datasets (such as location of major road intersections in a state, healthcare records, database of building profiles, and visual stimuli), but are limited in how many labels (such as traffic or wind speed at the intersections, customer satisfaction, energy usage, and brain response, respectively) can be collected under budget constraints. Classical experimental design in statistics addresses this problem, however the solutions tend to be combinatorial. We consider computationally tractable methods for the experimental design problem, where k out of n design points of dimension p are selected so that certain optimality criteria are approximately satisfied. We prove a constant approximation ratio under a very weak condition that k > 2p, and a (1 + eps) relative approximation ratio under slightly stronger conditions in which k is still a linear function of p. Our results are based on a convex relaxation of the combinatorial problem, followed by different sampling strategies. We also present numerical results on both synthetic and real-world design problems that verify the practical effectiveness of the proposed algorithm.
Aarti Singh received her B.E. in Electronics and Communication Engineering from the University of Delhi in 2001, and M.S. and Ph.D. degrees in Electrical and Computer Engineering from the University of Wisconsin-Madison in 2003 and 2008, respectively. She was a Postdoctoral Research Associate at the Program in Applied and Computational Mathematics at Princeton University from 2008 to 2009, before joining the School of Computer Science at Carnegie Mellon in 2009 where she is currently an Associate Professor in the Machine Learning Department.
Location and Address
1811 Wesley W. Posvar Hall
230 South Bouquet Street
Pittsburgh, PA 15260