BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Statistical and computational trade-offs in estimation of sparse p
 rincipal components - Tengyao Wang (University of Cambridge)
DTSTART:20151021T150000Z
DTEND:20151021T160000Z
UID:TALK61313@talks.cam.ac.uk
CONTACT:Adam Kashlak
DESCRIPTION:In recent years\, Sparse Principal Component Analysis has emer
 ged as an extremely popular dimension reduction technique for high-dimensi
 onal data.  The theoretical challenge\, in the simplest case\, is to estim
 ate the leading eigenvector of a population covariance matrix under the as
 sumption that this eigenvector is sparse.  An impressive range of estimato
 rs have been proposed\; some of these are fast to compute\, while others a
 re known to achieve the minimax optimal rate over certain Gaussian or subg
 aussian classes.  In this paper we show that\, under a widely-believed ass
 umption from computational complexity theory\, there is a fundamental trad
 e-off between statistical and computational performance in this problem.  
 More precisely\, working with new\, larger classes satisfying a Restricted
  Covariance Concentration condition\, we show that there is an effective s
 ample size regime in which no randomised polynomial time algorithm can ach
 ieve the minimax optimal rate.  We also study the theoretical performance 
 of a (polynomial time) variant of the well-known semidefinite relaxation e
 stimator\, revealing a subtle interplay between statistical and computatio
 nal efficiency. 
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR