Inference in high-dimensional settings: Trade-offs between computational and statistical efficiency
This talk considers questions of two types concerning high-dimensional inference. First, given a practical (polynomial-time) algorithm, what are the statistical limitations of its performance? Second, how do such practical limitations compare to information-theoretic bounds, which apply to the performance of any algorithm regardless of its computational complexity?
We analyze these issues in high-dimensional versions of two canonical inference problems: (a) subset selection in linear regression; and (b) the sparse PCA or eigenvector problem. For both problems, we begin by analyzing simple polynomial-time methods based on convex relaxations: \ell_1-constrained quadratic programming (Lasso) for sparse regression, and a semidefinite programming (SDP) relaxation, due to Aspremont et al, for sparse PCA. For both methods, we provide precise thresholds on the sample size n that controls their success/failure as a function of the problem size p, and the sparsity index k. We then use information-theoretic methods to prove that these practical methods are order-optimal for sublinear sparsity (vanishing k/p), but highly sub-optimal for linear sparsity (k/p bounded away from zero).
Based on joint works with Arash Amini, Wei Wang, Kannan Ramchandran.
Speaker Bio
Martin Wainwright is currently an assistant professor atUniversity of California at Berkeley, with a joint appointment between the Department of Statistics and the Department of Electrical Engineering and Computer Sciences. He received the Ph.D. degree in Electrical Engineering and Computer Science from Massachusetts Institute of Technology (MIT), for which he was awarded the George M. Sprowls Award for his doctoral dissertation. His research interests include statistical machine learning, high-dimensional statistics, information theory, and statistical signal processing. He has received an NSF CAREER award (2006), an Alfred P. Sloan Foundation Fellowship (2005), an Okawa Foundation Research Fellowship (2005), and a number of outstanding conference paper awards.