Thursday, October 10, 2013
4:00 pm
Annenberg 105

Special Seminar in Applied Mathematics

Statistical and Computational Tradeoffs in High Dimensional Learning
Philippe Rigollet, Assistant Professor, Operations Research and Financial Engineering, California Institute of Technology

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 viewed 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.

Contact Sydney Garstang sydney@caltech.edu at x4555
For more information see http://www.cms.caltech.edu
Add this event to my calendar