Special Seminar in Applied Mathematics

Thursday October 10, 2013 4:00 PM

Statistical and Computational Tradeoffs in High Dimensional Learning

Speaker: Philippe Rigollet, Operations Research and Financial Engineering, California Institute of Technology
Location: Annenberg 105

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.

Series Special Seminars in Applied Mathematics

Contact: Sydney Garstang at x4555 sydney@caltech.edu
For more information visit: www.cms.caltech.edu