On the non-universality of deep learning: quantifying the cost of symmetry
This work addresses the problem of understanding the fundamental capabilities and limitations of deep learning for researchers in machine learning theory, providing theoretical insights into symmetry constraints.
The paper proves limitations on what neural networks trained by noisy gradient descent can efficiently learn, showing that depth-2 fully-connected networks are as powerful as any depth for weak-learning on the binary hypercube and unit sphere, and extends necessity results for learning with latent low-dimensional structure beyond the mean-field regime.
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).