What are the learning limitations of neural networks trained with backpropagation? In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function.
This was solved by the backpropagation network with at least one hidden layer. This type of network can learn the XOR function.
I believe I was once taught that every problem that could be learned by a backpropagation neural network with multiple hidden layers, could also be learned by a backpropagation neural network with a single hidden layer. (Although possibly a nonlinear activation function was required).
However, it is unclear to me what the limits are to backpropagation neural networks themselves. Which patterns cannot be learned by a neural network trained with gradient descent and backpropagation?
Multilayer Perceptron (MLP) can theoretically approximate any bounded, continuous function. There's no guarantee for a discontinuous function. There are plenty of important discontinuous functions, like, say, the prime counting function.
The prime counting function $\pi(n)$ is simply equal to the number of primes less than or equal to $n$. It has a discontinuity about each prime $p$, so good luck trying to approximate this with a neural network!
However, this function is extensively studied and extremely important in number theory. See the Riemann hypothesis.