IC Colloquium : Statistical and Computational Tradeoffs in High Dimensional Learning
Event details
| Date | 13.03.2014 |
| Hour | 16:15 › 17:30 |
| Location | |
| Category | Conferences - Seminars |
By : Philippe Rigollet, Princeton University
IC Faculty candidate
Abstract
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]
Biography
Philippe Rigollet is an assistant professor in the department of Operations Research and Financial Engineering at Princeton University. His research interests focus on optimality of statistical methods and algorithms in the context of high-dimensional statistical learning. His results draws connections between optimization, probability, theoretical computer science and information theory. His work is funded by several NSF grants including a CAREER award from the Division of Mathematical Sciences. He is also the recipient of the Wentz award for outstanding research and teaching at Princeton and of the Best Paper Award at the last Conference on Learning Theory (COLT) for his work on statistical and computational tradeoffs.
More information
IC Faculty candidate
Abstract
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]
Biography
Philippe Rigollet is an assistant professor in the department of Operations Research and Financial Engineering at Princeton University. His research interests focus on optimality of statistical methods and algorithms in the context of high-dimensional statistical learning. His results draws connections between optimization, probability, theoretical computer science and information theory. His work is funded by several NSF grants including a CAREER award from the Division of Mathematical Sciences. He is also the recipient of the Wentz award for outstanding research and teaching at Princeton and of the Best Paper Award at the last Conference on Learning Theory (COLT) for his work on statistical and computational tradeoffs.
More information
Practical information
- Informed public
- Free
- This event is internal
Contact
- Tania Epars