There are a lot of papers that show that neural networks can approximate a wide variety of functions. However, I can't find papers that show the limitations of NNs.
What are the limitations of neural networks? Which functions can't neural networks learn efficiently (or using gradient-descent)?
I am looking also for links to papers that describe these limitations.
One of the important qualifications of the Universal approximation theorem is that the neural network approximation may be computationally infeasible.
"A feedforward network with a single layer is sufficient to represent any function, but the layer may be infeasibly large and may fail to learn and generalize correctly." - Ian Goodfellow, DLB
I can't think of any function that I would definitively declare as unlearnable, but neural networks have many problems. Consider adversarial examples and adversarial patches, which highlight the poor generalization going on under the hood of recent advances in computer vision.
Neural Networks are also inherently limited by the innate priors baked into their architecture and the sample density of their training data. Check out this recent discussion at Stanford's AI Salon between Yann LeCun and Christopher Manning on innate priors if that is the kind of limitation you are talking about.
A random function cannot be learned efficiently by any algorithm, in particular, neural networks. However, if you are looking for a function with (exponentially) smaller description size, I do not know but any function that is conjectured to be average-case hard probably cannot be learned efficiently by neural networks, for example,
This answer depends very much so on the type of neural network and algorithm used for training.
If you are using gradient descent on a neural network of one input layer, one output layer, and no hidden layers there are many functions that you can't learn. One simple one is the XOR function. Due to the fact that XOR is not linearly separable, it can not be represented by a neural network with no hidden layers.
If you are using NEAT to build recurrent neural networks then all functions(**) can be represented given enough time and data. This is due in part to the fact that recurrent neural networks are Turing Complete.
One of the biggest causes for limitations when using neural networks is based on the difficulty of interpretation as to what the network is doing. The network is gradually building up an understanding of the function as it goes from the input layer to the output layer, but it is very difficult for us to understand this building up process and interpret what the neural network is attempting to do. This makes it very hard if not impossible to manually tweak your neural network in a meaningful way.
Another limitation is the need for training (in large amounts) in order to have a meaningful representation of your data. Neural networks have a tendency to need large amounts of data before converging to a meaningful hypothesis space. This has resulted in clever algorithms to generate training data without needing human interaction, such as Generative Adversarial Networks, but the underlying problem remains.
** Not all functions can be computed by neural networks, however, all computable functions can be. An example of an uncomputable function is the mapping of all programs from the program to whether or not this program will halt (The Halting Problem).
