TITLE:  Computationally tractable and near optimal design of experiments

ABSTRACT:

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.

BIO:  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. Her research interests lie at the intersection of machine learning, statistics and signal processing, and focus on designing statistically and computationally efficient algorithms that can leverage inherent structure of the data in the form of clusters, graphs, subspaces and manifold using direct, compressive and active queries. Her work is recognized by an NSF Career Award, a United States Air Force Young Investigator Award, A. Nico Habermann Faculty Chair Award, Harold A. Peterson Best Dissertation Award, and a best student paper award at Allerton.