The statistical price to pay for computational efficiency

Monday, October 21, 2013 -
4:30pm to 5:30pm
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]
Speaker: 
Philippe Rigollet
Princeton University - ORFE
Event Location: 
Fine Hall 214