Answers.Body: <p>One of the important qualifications of the Universal approximation theorem is that the neural network approximation may be computationally infeasible.</p>
  
  <blockquote>
    <p>"A feedforward network with a single layer is sufficient to represent any function, but <strong>the layer may be infeasibly large and may fail to learn and generalize correctly.</strong>" - Ian Goodfellow, <a href="http://www.deeplearningbook.org/contents/mlp.html" rel="noreferrer">DLB</a></p>
  </blockquote>
  
  <p>I can't think of any function that I would definitively declare as unlearnable, but neural networks have many problems. Consider <a href="https://arxiv.org/abs/1312.6199" rel="noreferrer">adversarial examples</a> and <a href="https://arxiv.org/abs/1712.09665" rel="noreferrer">adversarial patches</a>, which highlight the poor generalization going on under the hood of recent advances in computer vision.</p>
  
  <p>Neural Networks are also inherently limited by the innate priors baked into their architecture and the sample density of their training data. Check out <a href="https://www.youtube.com/watch?v=fKk9KhGRBdI" rel="noreferrer">this recent discussion</a> 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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-07T12:15:28.260Z
Answers.Text: For example X1 * X2, this function can be approximated by feedforward NN but can't be efficiently represented by splitting space with linear hyperplanes, also NN poor with fitures combinations like x1*x2, x1/x2, 1/x1 and so on, because neuron creates only linear hyperplane and it isn't efficient.
Answers.UserDisplayName: user2674414
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-06T18:48:56.720Z
Answers.LastActivityDate: 2018-03-06T18:48:56.720Z
Answers.UserDisplayName: Jackson Waschura
Answers.Body: <p>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,</p>
  <ul>
  <li>Any cryptographic hard-core predicate (related: <a href="https://datascience.stackexchange.com/q/16639/96045">Could Deep Learning be used to crack encryption?</a>).</li>
  <li>Parity learning with noise (related: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.5766&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Cryptographic Primitive Based on Hard Learning Problems</a>).</li>
  <li>Combinatorial examples: planted SAT, planted clique (related: <a href="https://eprint.iacr.org/2017/365.pdf" rel="nofollow noreferrer">Barak's survey</a>).</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-29T14:21:55.400Z
Answers.LastActivityDate: 2022-01-15T00:12:10.840Z
Answers.LastEditDate: 2022-01-15T00:12:10.840Z
Answers.UserDisplayName: Mygod
Answers.Body: <p>This answer depends very much so on the type of neural network and algorithm used for training.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>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.</p>
  <p>** 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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-03-07T05:23:35.633Z
Answers.LastActivityDate: 2022-01-15T00:12:43.607Z
Answers.LastEditDate: 2022-01-15T00:12:43.607Z
Answers.UserDisplayName: Andrew Butler
Body: <p>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. </p>
  
  <p>What are the limitations of neural networks? Which functions can't neural networks learn efficiently (or using gradient-descent)?</p>
  
  <p>I am looking also for links to papers that describe these limitations.</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-03-07T12:27:21.513Z
Comments.Text: I want clarify. For example lets consider feedforfard NN. Yes it can represent anything but for some tasks it could demand too many data or too many computational power or incredible count of neurons and layers. for example X1*X2. It can be represented and this function is very simple and we expect that our cool approximator can do it easy but it actualy can only inefficient proximate it by creation a banch of hypeplane spliting space.
Comments.UserDisplayName: user2674414
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-04-11T13:46:45.450Z
Comments.Text: The fact that you cannot find a paper about limitations... I don't know how that would even happen. It seems almost impossible to get something setup, and not read the warning page.
Comments.UserDisplayName: FreezePhoenix
Tags: <neural-networks><machine-learning><reference-request><function-approximation>
Title: Which functions can't neural networks learn efficiently?
UserDisplayName: user2674414
ThreadText: # Which functions can't neural networks learn efficiently?
  
  (Asked by: username_0 on 2018-03-06)
  
  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.
  
  **Tags:** neural-networks, machine-learning, reference-request, function-approximation
  > **Comments:**
  > **username_0**: I want clarify. For example lets consider feedforfard NN. Yes it can represent anything but for some tasks it could demand too many data or too many computational power or incredible count of neurons and layers. for example X1*X2. It can be represented and this function is very simple and we expect that our cool approximator can do it easy but it actualy can only inefficient proximate it by creation a banch of hypeplane spliting space.  
  > **username_1**: The fact that you cannot find a paper about limitations... I don't know how that would even happen. It seems almost impossible to get something setup, and not read the warning page.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2018-03-06. Score: 6
  
  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](http://www.deeplearningbook.org/contents/mlp.html)
  
  I can't think of any function that I would definitively declare as unlearnable, but neural networks have many problems. Consider [adversarial examples](https://arxiv.org/abs/1312.6199) and [adversarial patches](https://arxiv.org/abs/1712.09665), 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](https://www.youtube.com/watch?v=fKk9KhGRBdI) 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.
  
  > **Comments:**
  > **username_0**: For example X1 * X2, this function can be approximated by feedforward NN but can't be efficiently represented by splitting space with linear hyperplanes, also NN poor with fitures combinations like x1*x2, x1/x2, 1/x1 and so on, because neuron creates only linear hyperplane and it isn't efficient.  
  
  ---
  
  ### Answer by username_3 on 2020-04-29. Score: 2
  
  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,
  
  * Any cryptographic hard-core predicate (related: [Could Deep Learning be used to crack encryption?](https://datascience.stackexchange.com/q/16639/96045)).
  * Parity learning with noise (related: [Cryptographic Primitive Based on Hard Learning Problems](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.5766&rep=rep1&type=pdf)).
  * Combinatorial examples: planted SAT, planted clique (related: [Barak's survey](https://eprint.iacr.org/2017/365.pdf)).
  
  
  ---
  
  ### Answer by username_4 on 2018-03-07. Score: 2
  
  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).
  
  
  ---
  
  