Timezone: »

On the non-universality of deep learning: quantifying the cost of symmetry
Emmanuel Abbe · Enric Boix-Adsera

Thu Dec 01 09:00 AM -- 11:00 AM (PST) @ Hall J #723

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