Title: Curses and Blessings: Which Problems Can Neural Networks Learn?
Abstract:
Supervised learning is the problem of estimating a function from input and output samples. But how many samples are needed to achieve a prescribed accuracy?
This question can be answered only by restricting the class of problems—for example, considering functions that don’t vary much. But in even this case, we find that the number of needed samples depends exponentially on the dimensions of each input—the so-called curse of dimensionality.
Since neural nets seem to learn well with much less data, it is natural to postulate that the underlying problems (functions) have more structure beyond bounded variations. The search for the right notion of “structure” has been quite elusive thus far, and I will discuss some recent results that emphasize the role of sparsity and compositions.
Bio: Lorenzo Rosasco is a professor at the University of Genova. He is a research affiliate at the Massachusetts Institute of Technology (MIT) and a visiting scientist at the Italian Technological Institute (IIT). He is a founder and serves as a coordinator of the Machine Learning Genova center (MaLGa) and the Laboratory for Computational and Statistical Learning, focusing on the theory, algorithms, and applications of machine learning. He obtained his PhD in 2006 from the University of Genova and was a visiting student at the Center for Biological and Computational Learning at MIT, the Toyota Technological Institute at Chicago (TTI-Chicago), and the Johann Radon Institute for Computational and Applied Mathematics. From 2006 to 2013, he worked as a postdoc and research scientist at the Brain and Cognitive Sciences Department at MIT. He is a fellow at Ellis and serves as the co-director of the "Theory, Algorithms and Computations of Modern Learning Systems" program as well as the Ellis Genoa unit. Lorenzo has received several awards, including an ERC consolidator grant.