Statistics Meets Computation: Efficiency Trade-Offs in High Dimensions

• Activity Number: 220
• Type: Invited
• Date/Time: Monday, August 5, 2013 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Martin Wainwright*+
• Companies: UC Berkeley
• Keywords: High-dimensional data ; Structured variable selection ; Low-rank matrices ; Principal component analysis ; Computation

Abstract

High-dimensional data sets present challenges that are both statistical and computational in nature. For a given problem, we typically have a wide array of estimators at our disposal, ranging from very inexpensive methods (e.g., greedy search or thresholding); methods of intermediate complexity (e.g., quadratic programming (LASSO) and other convex relaxations); all the way through to oracle-type methods that may involve exponential-time search. This wide range of choices leads to a number of natural questions. What is the trade-off between computational and statistical efficiency? When does a more computationally intensive scheme lead statistical efficiency? Can we design estimators that achieve statistical minimax rates with minimal computational complexity? In this talk, we present a few vignettes that shed some light on these questions, including discussion of principal component analysis, structured variable selection, and low-rank matrix estimation.