Friday, May 2 2:20 p.m. – Presentation – 253 Rhodes Hall Philippe Rigollet The statistical price to pay for computational efficiency in sparse PCA Computational limitations of statistical problems have largely been ignored or simply overcome by ad hoc relaxations techniques. If optimal methods cannot be computed in reasonable time, what is the best possible statistical performance of a computationally efficient procedure? Building on average case reductions, we establish these fundamental limits in the context of sparse principal component analysis and quantify the statistical price to pay for computational efficiency. Our results can be interpreted as complexity theoretic lower bounds conditionally on the assumptions that some instances of the planted clique problem cannot be solved in randomized polynomial time. Joint work with Quentin Berthet