IC Talk: How hard is it to learn from data generated by a probabilistic model?
Event details
| Date | 05.11.2019 |
| Hour | 11:15 › 12:30 |
| Location | |
| Category | Conferences - Seminars |
By: Florent Krzakala - Sorbonne University
Video of his talk
Abstract:
In many modern applications, large instances of NP-hard problems are routinely solved. While this should be impossible from the worst-case perspective, the behaviour of algorithms on relevant “typical” data is often not captured by the worst case. This motivates the following question: How hard is it to learn from data generated by a probabilistic model?
I will consider several prototypical generative models and learning tasks, e.g. detecting communities in graphs, performing compressed sensing and phase retrieval, or learning a rule with multi-layer neural networks, for which it is possible to obtain closed-form answers to this question. Interestingly, in a wide variety of such problems we find sharp changes --phase transitions-- in statistical and computational performance as some parameters are changed. In particular, there exists a region of parameters where the underlying statistical problem is information-theoretically possible to solve yet no efficient algorithm is known, rendering the problem essentially unsolvable in practice.
In the final part of the talk, I will finally build of the fact that realistic structured data can often be captured via generative adversarial networks or variational auto-encoders, and using them can lead to drastic improvements. I will present a methodology that enables us to extend the analysis of the statistical and computational performance to such data generated by random multi-layer neural networks.
Bio:
Florent Krzakala is a professor at Sorbonne Université and a Researcher at Ecole Normale Superieure in Paris. His research interests include Statistical Physics, Machine Learning, Statistics, Computer Science and Computational Optics. He leads the SPHINX “Statistical PHysics of INformation eXtraction” team in Ecole Normale in Paris, and is the holder of the CFM-ENS Datascience chair and of a PRAIRIE Institute chair. He is also the funder and scientific advisor of the startup Lighton.
More information
Video of his talk
Abstract:
In many modern applications, large instances of NP-hard problems are routinely solved. While this should be impossible from the worst-case perspective, the behaviour of algorithms on relevant “typical” data is often not captured by the worst case. This motivates the following question: How hard is it to learn from data generated by a probabilistic model?
I will consider several prototypical generative models and learning tasks, e.g. detecting communities in graphs, performing compressed sensing and phase retrieval, or learning a rule with multi-layer neural networks, for which it is possible to obtain closed-form answers to this question. Interestingly, in a wide variety of such problems we find sharp changes --phase transitions-- in statistical and computational performance as some parameters are changed. In particular, there exists a region of parameters where the underlying statistical problem is information-theoretically possible to solve yet no efficient algorithm is known, rendering the problem essentially unsolvable in practice.
In the final part of the talk, I will finally build of the fact that realistic structured data can often be captured via generative adversarial networks or variational auto-encoders, and using them can lead to drastic improvements. I will present a methodology that enables us to extend the analysis of the statistical and computational performance to such data generated by random multi-layer neural networks.
Bio:
Florent Krzakala is a professor at Sorbonne Université and a Researcher at Ecole Normale Superieure in Paris. His research interests include Statistical Physics, Machine Learning, Statistics, Computer Science and Computational Optics. He leads the SPHINX “Statistical PHysics of INformation eXtraction” team in Ecole Normale in Paris, and is the holder of the CFM-ENS Datascience chair and of a PRAIRIE Institute chair. He is also the funder and scientific advisor of the startup Lighton.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Rüdiger Urbanke