Neural Network Learning and Leap Complexity

Abstract

It was recently shown that SGD trained neural networks are universal learners: with sufficient freedom in the architecture design, they can learn any function class that is efficiently learnable. However these results rely on impractical architectures. Is the same statement true for more regular architectures like MLPs or Transformers? We show results suggesting that the answer is no. Namely, more regular architectures seem bounded to learn functions having low “leap”, a new complexity measure that captures how hierarchical target functions are. In particular, for Boolean functions, the leap is a measure of the nestedness of its Fourier transform. We further discuss how this implies some challenges for regular models to learn reasoning tasks with the generalization on the unseen (GOTU) framework. 

Bio

Emmanuel Abbe received his Ph.D. degree from the EECS Department at MIT in 2008, and his M.S. degree from the Mathematics Department at EPFL in 2003. He was at Princeton University as an assistant professor in 2012-2016 and an associate professor in 2016-2019, jointly in the Program for Applied and Computational Mathematics and the Electrical and Computer Engineering Department, as well as an associate faculty in the Mathematics Department in 2016-2019. He joined EPFL in 2018 as a full professor, jointly in the Mathematics Institute and the School of Computer and Communication Sciences, where he holds the Chair of Mathematical Data Science. He is co-director of the EPFL Bernoulli Center for Fundamental Studies and a Senior Research Scientist at Apple AIML-MLR. He is the recipient of the Foundation Latsis International Prize, the Bell Labs Prize, the von Neumann Fellowship from the Institute for Advanced Study, the Simons-NSF Mathematics of Deep Learning Collaborative Research Award, the IEEE Information Theory Society Paper Award, the Frontiers of Science Award, the ICML Outstanding Paper Award.