Timezone: »
Poster
On the non-universality of deep learning: quantifying the cost of symmetry
Emmanuel Abbe · Enric Boix-Adsera
We prove limitations on what neural networks trained by noisy gradient descent (GD) can efficiently learn. Our results apply whenever GD training is equivariant, which holds for many standard architectures and initializations. As applications, (i) we characterize the functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere, demonstrating that depth-2 is as powerful as any other depth for this task; (ii) we extend the merged-staircase necessity result for learning with latent low-dimensional structure [ABM22] to beyond the mean-field regime. Under cryptographic assumptions, we also show hardness results for learning with fully-connected networks trained by stochastic gradient descent (SGD).
Author Information
Emmanuel Abbe (Swiss Federal Institute of Technology Lausanne)
Enric Boix-Adsera (MIT)
More from the Same Authors
-
2021 Spotlight: On the Power of Differentiable Learning versus PAC and SQ Learning »
Emmanuel Abbe · Pritish Kamath · Eran Malach · Colin Sandon · Nathan Srebro -
2023 Poster: Transformers learn through gradual rank increase »
Emmanuel Abbe · Samy Bengio · Enric Boix-Adsera · Etai Littwin · Joshua Susskind -
2023 Poster: Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs »
Emmanuel Abbe · Elisabetta Cornacchia · Aryo Lotfi -
2022 Poster: GULP: a prediction-based metric between representations »
Enric Boix-Adsera · Hannah Lawrence · George Stepaniants · Philippe Rigollet -
2022 Poster: Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures »
Emmanuel Abbe · Samy Bengio · Elisabetta Cornacchia · Jon Kleinberg · Aryo Lotfi · Maithra Raghu · Chiyuan Zhang -
2021 Poster: On the Power of Differentiable Learning versus PAC and SQ Learning »
Emmanuel Abbe · Pritish Kamath · Eran Malach · Colin Sandon · Nathan Srebro -
2021 Poster: The staircase property: How hierarchical structure can guide deep learning »
Emmanuel Abbe · Enric Boix-Adsera · Matthew S Brennan · Guy Bresler · Dheeraj Nagaraj -
2019 Poster: Sample Efficient Active Learning of Causal Trees »
Kristjan Greenewald · Dmitriy Katz · Karthikeyan Shanmugam · Sara Magliacane · Murat Kocaoglu · Enric Boix-Adsera · Guy Bresler