Special Seminar in Applied Mathematics
Annenberg 105
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.
For more information, please contact Sydney Garstang by phone at x4555 or by email at [email protected] or visit http://www.cms.caltech.edu.
Event Series
Special Seminars in Applied Mathematics