  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).
