[Ml-stat-talks] PACM Colloquium today - The statistical price to pay for computational efficiency

Ramon van Handel rvan at Princeton.EDU
Mon Oct 21 12:58:05 EDT 2013

Dear all, the PACM colloquium this afternoon by our very own Philippe 
Rigollet should be very interesting (see below).  Best, -- Ramon


PACM Colloquium

Title: The statistical price to pay for computational efficiency

Speaker: Philippe Rigollet - Princeton University - ORFE

Date: Oct 21 2013 - 4:30pm

Room: 214 Fine Hall


The ever increasing size of current datasets has made computation an 
essential aspect of the design of statistical procedures. Yet, current 
notions of statistical optimality rely on information theoretic 
considerations that completely ignore the computation question. In this 
work, we develop a new notion of optimality among computationally 
efficient methods. Building on average-case reductions from the planted 
clique problem, we establish optimality of various testing procedures in 
the context of sparse principal component analysis and quantify the 
statistical price to pay for computational efficiency. [Joint work with 
Quentin Berthet]

More information about the Ml-stat-talks mailing list