On the non-universality of deep learning: quantifying the cost of symmetry. (arXiv:2208.03113v2 [cs.LG] UPDATED)

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 …

arxiv cost deep learning symmetry