<p>There are a bunch of "no free lunch" theorems in machine learning, roughly stating that there can be no one master learning algorithm that performs uniformly better than all other algorithms (see, e.g., here <a href="http://www.no-free-lunch.org/" rel="noreferrer">http://www.no-free-lunch.org/</a> ). Sure enough, deep learning can be "broken" without much difficulty:
<a href="http://www.evolvingai.org/fooling" rel="noreferrer">http://www.evolvingai.org/fooling</a></p>

<p>Hence, to be provably effective, a learner needs <em>inductive bias</em> --- i.e., some prior assumptions about the data. Examples of inductive bias include assumptions of data sparsity, or low dimensionality, or that the distribution factorizes nicely, or has a large margin, etc. Various successful learning algorithms exploit these assumptions to prove generalization guarantees. For example, (linear) SVM works well when the data is well-separated in space; otherwise -- not so much.</p>

<p>I think the main challenge with deep learning is to understand what its inductive bias is. In other words, it is to prove theorems of the type: If the training data satisfies these assumptions, then I can guarantee something about the generalization performance. (Otherwise, all bets are off.)</p>

<p>Update (Sep-2019): In the two years since my posted answer, there has been a great deal of progress in understanding the inductive bias implicit in various DL and related algorithms. One of the key insights is that the actual optimization algorithm being used is important, since uniform convergence cannot explain why a massively over-parametrized system such as a large ANN manages to learn at all. It turns out that the various optimization methods (such as SGD) are implicitly regularizing with respect to various norms (such as <span class="math-container">$\ell_2$</span>). See this excellent lecture for other examples and much more:
<a href="https://www.youtube.com/watch?v=zK84N6ST9sM" rel="noreferrer">https://www.youtube.com/watch?v=zK84N6ST9sM</a></p>

CC BY-SA 3.0
2016-10-01T10:48:19.127Z
It should be noted that adversarial examples are not unique to deep neural networks. They can also easily be constructed for linear and logistic regression, for example: https://arxiv.org/pdf/1412.6572.pdf
Lenar Hoyt
CC BY-SA 3.0
2016-10-01T16:33:34.357Z
Yes, but linear and logistic regression are much better theoretically understood.
Aryeh
CC BY-SA 3.0
2016-10-01T19:43:08.510Z
It should perhaps also be noted that the NFL theorems [might not play a big role](https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf) in practical machine learning because while NFL is concerned with the class of *all* functions, real world problems are typically constrained to e.g. smooth functions or even more specific functions such as the ones considered in the paper by Lin and Tegmark. It might be possible to find inductive biases that cover all learning problems that we are interested in.
Lenar Hoyt
CC BY-SA 3.0
2016-10-01T19:58:02.780Z
Then we should first formalize this space of "all learning problems that we are interested in".
Aryeh
CC BY-SA 3.0
2016-10-01T20:31:44.903Z
That definitely seems worthwhile, especially with regards to AI safety. We need to be able to reliably specify what a machine learning algorithm is supposed to learn.
Lenar Hoyt
CC BY-SA 4.0
2016-09-27T19:46:04.113Z
2019-09-17T19:09:01.337Z
2019-09-17T19:09:01.337Z
Aryeh
<p>There are two main gaps in our understanding of neural networks: optimization hardness and generalization performance.</p>

<p>Training a neural network requires solving a highly non-convex optimization problem in high dimensions. Current training algorithms are all based on gradient descent, which only guarantees convergence to a critical point (local minimum or saddle). In fact, <a href="http://www.jmlr.org/proceedings/papers/v49/anandkumar16.pdf">Anandkumar &amp; Ge 2016</a> recently proved that finding even a local minimum is NP-hard, which means that (assuming P != NP) there exist "bad", hard to escape, saddle points in the in the error surface.<br>
Yet, these training algorithms are empirically effective for many practical problems, and we don't know why.<br>
There have been theoretical papers such as <a href="http://www.jmlr.org/proceedings/papers/v40/Choromanska15.pdf">Choromanska et al. 2016</a> and <a href="https://arxiv.org/abs/1605.07110">Kawaguchi 2016</a> which prove that, under certain assumptions, the local minima are essentially as good as the global minima, but the assumptions they make are somewhat unrealistic and they don't address the issue of the bad saddle points.</p>

<p>The other main gap in our understanding is generalization performance: how well does the model perform on novel examples not seen during training? It's easy to show that in the limit of an infinite number of training examples (sampled i.i.d. from a stationary distribution), the training error converges to the expected error on novel examples (provided that you could train to the global optimum), but since we don't have infinite training examples, we are interested in how many examples are needed to achieve a given difference between training and generalization error. <a href="https://en.wikipedia.org/wiki/Statistical_learning_theory">Statistical learning theory</a> studies these generalization bounds.<br>
Empirically, training a large modern neural network requires a large number of training examples (Big Data, if you like buzzwords), but not that monumentally large to be practically unfeasible. But if you apply the best known bounds from statistical learning theory (for instance <a href="https://arxiv.org/abs/1402.3811">Gao &amp; Zhou 2014</a>) you typically get these unfeasibly huge numbers. Therefore these bounds are very far from being tight, at least for practical problems.<br>
One of the reason might be that these bounds tend to assume very little about the data generating distribution, hence they reflect the worst-case performance against adversarial environments, while "natural" environments tend to be more "learnable".<br>
It is possible to write distribution-dependent generalization bounds, but we don't know how to formally characterize a distribution over "natural" environments. Approaches such as <a href="https://en.wikipedia.org/wiki/Algorithmic_information_theory">algorithmic information theory</a> are still unsatisfactory.<br>
Therefore we still don't know why neural networks can be trained without overfitting.</p>

<p>Furthermore, it should be noted that these two main issues seem to be related in a still poorly understood way: the generalization bounds from statistical learning theory assume that the model is trained to the global optimum on the training set, but in a practical setting you would never train a neural network until convergence even to a saddle point, as to do so would typically cause overfitting. Instead you stop training when the error on a held-out validation set (which is a proxy for the generalization error) stops improving. This is known as "early stopping".<br>
So in a sense all this theoretical research on bounding the generalization error of the global optimum may be quite irrelevant: not only we can't efficiently find it, but even if we could, we would not want to, since it would perform worse on novel examples than many "sub-optimal" solutions.<br>
It may be the case that optimization hardness is not a flaw of neural network, on the contrary, maybe neural networks can work at all precisely because they are hard to optimize.<br>
All these observations are empirical and there is no good theory that explains them. There is also no theory that explains how to set the hyperparameters of neural networks (hidden layer width and depth, learning rates, architectural details, etc.). Practitioners use their intuition honed by experience and lots of trial and error to come up with effective values, while a theory could allow us to design neural networks in a more systematic way.</p>

CC BY-SA 3.0
2016-10-01T16:36:12.647Z
2016-10-01T16:36:12.647Z
Antonio Valerio Miceli-Barone
<p>Another take on this question, to add to @Aryeh's remarks: For many other models of learning, we know the "shape" of the hypothesis space. SVMs are the best example of this, in that what you're finding is a linear separator in a (possibly-high dimensional) Hilbert space. </p>

<p>For neural networks in general, we don't have any such clear description or even an approximation. And such a description is important for us to understand what exactly a neural network is finding in the data. </p>

CC BY-SA 4.0
2018-05-23T16:13:55.930Z
What would you call as the "shape" of the hypothesis space? :) Does Theorem 2.1 (page 3) of ours answer some of your question : https://eccc.weizmann.ac.il/report/2017/098/ ? :D
Student
CC BY-SA 3.0
2016-09-30T17:05:38.177Z
2016-09-30T17:05:38.177Z
Suresh Venkat
<p>The principle of Information Bottleneck has been proposed to explain the success of deep nueral networks. </p>

<p>Here is a quote from <a href="https://www.quantamagazine.org/new-theory-cracks-open-the-black-box-of-deep-learning-20170921/" rel="nofollow noreferrer">Quanta magazine</a></p>

<blockquote>
  <p>Last month, a YouTube video of a conference talk in Berlin, shared widely among artificial-intelligence researchers, offered a possible answer. In the talk, Naftali Tishby, a computer scientist and neuroscientist from the Hebrew University of Jerusalem, presented evidence in support of a new theory explaining how deep learning works. Tishby argues that deep neural networks learn according to a procedure called the “information bottleneck,” which he and two collaborators first described in purely theoretical terms in 1999. The idea is that a network rids noisy input data of extraneous details as if by squeezing the information through a bottleneck, retaining only the features most relevant to general concepts. Striking new computer experiments by Tishby and his student Ravid Shwartz-Ziv reveal how this squeezing procedure happens during deep learning, at least in the cases they studied.</p>
</blockquote>

<p>References:</p>

<p>1- <a href="http://ieeexplore.ieee.org/document/7133169/" rel="nofollow noreferrer">Deep learning and the information bottleneck principle</a>, Naftali Tishby and Noga Zaslavsky </p>

<p>2- <a href="https://arxiv.org/abs/1703.00810" rel="nofollow noreferrer">Opening the Black Box of Deep Neural Networks via Information</a>, Ravid Shwartz-Ziv and Naftali Tishby</p>

<p>3- <a href="https://www.youtube.com/watch?v=bLqJHjXihK8&amp;feature=youtu.be" rel="nofollow noreferrer">Conference talk video: Information Theory of Deep Learning</a> by Naftali Tishby</p>

CC BY-SA 3.0
2017-10-08T19:51:27.153Z
2017-10-08T19:51:27.153Z
Mohammad Al-Turkistany
<p>I would say that we still need to discover an efficient algorithm for training deep neural networks. Yes, SGD does work well in practice but finding a better algorithm that has guarantees to converge to global minimum would be very nice. </p>

CC BY-SA 3.0
2016-10-01T15:31:13.787Z
2016-10-01T15:31:13.787Z
didymus
<p>My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to machine learning, stumbled across statements such as "No one understands why neural networks work well," which I found interesting. </p>

<p>My question, essentially, is what kinds of answers do researchers want?  Here's what I've found in my brief search on the topic:</p>

<ul>
<li>The algorithms implementing simple neural networks are pretty
straightforward. </li>
<li>The process of SGD is well-understood mathematically, as is the statistical theory. </li>
<li>The universal approximation theorem is powerful and proven. </li>
<li>There's a nice recent paper <a href="https://arxiv.org/abs/1608.08225">https://arxiv.org/abs/1608.08225</a> which essentially gives the answer that universal approximation is much
more than we actually need in practice because we can make strong
simplifying assumptions about the functions we are trying to model
with the neural network.</li>
</ul>

<p>In the aforementioned paper, they state (paraphrasing) "GOFAI algorithms are fully understood analytically, but many ANN algorithms are only heuristically understood." Convergence theorems for the implemented algorithms are an example of analytic understanding that it seems we DO have about neural networks, so a statement at this level of generality doesn't tell me much about what's known vs. unknown or what would be considered "an answer." </p>

<p>The authors do suggest in the conclusion that questions such as effective bounds on the size of the neural network needed to approximate a given polynomial are open and interesting. What are other examples of mathematically specific analytical questions that would need to be answered to say that we "understand" neural networks? Are there questions that may be answered in more pure mathematical language? </p>

<p>(I am specifically thinking of methods in representation theory due to the use of physics in this paper --- and, selfishly, because it is my field of study. However, I can also imagine areas such as combinatorics/graph theory, algebraic geometry, and topology providing viable tools.)</p>

CC BY-SA 3.0
2016-09-27T20:42:34.180Z
Is  GOFAI really that well understood? A lot of GOFAI seems to boild down to SAT solving, the archetypical NP-complete problem. Modern
SAT solvers work remarkably well in practise, even though they
should not according to the extant theory. Why?
Martin Berger
CC BY-SA 3.0
2016-09-28T15:49:27.230Z
there is really pre-deep learning and post-deep learning study/ change/ history in this area and its a major paradigm shift in the field. deep learning took off only within last half decade. the simple answer is that neural networks can represent arbitrarily complex functions and that complexity is now at very advanced levels with deep neural networks. another answer is that the problems that are studied, and maybe even "reality in general,", are "built out of features" and ANNs are now adept at learning very complex features.
vzn
CC BY-SA 3.0
2016-10-08T20:54:19.547Z
I don't think people are really searching for "an answer" here. They seek to use neural networks to solve problems, and if the problem is indeed solved then it's fine. Knowing how the networks reached that solution isn't necessarily of interest here. Nobody cares much if it's a black/opaque box as long as it solves the issue.
xji
<machine-learning>
What kind of answer does TCS want to the question "Why do neural networks work so well?"
Neuling
# What kind of answer does TCS want to the question "Why do neural networks work so well?"

(Asked by: username_0 on 2016-09-27)

My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to machine learning, stumbled across statements such as "No one understands why neural networks work well," which I found interesting.

My question, essentially, is what kinds of answers do researchers want? Here's what I've found in my brief search on the topic:

* The algorithms implementing simple neural networks are pretty
  straightforward.
* The process of SGD is well-understood mathematically, as is the statistical theory.
* The universal approximation theorem is powerful and proven.
* There's a nice recent paper <https://arxiv.org/abs/1608.08225> which essentially gives the answer that universal approximation is much
  more than we actually need in practice because we can make strong
  simplifying assumptions about the functions we are trying to model
  with the neural network.

In the aforementioned paper, they state (paraphrasing) "GOFAI algorithms are fully understood analytically, but many ANN algorithms are only heuristically understood." Convergence theorems for the implemented algorithms are an example of analytic understanding that it seems we DO have about neural networks, so a statement at this level of generality doesn't tell me much about what's known vs. unknown or what would be considered "an answer."

The authors do suggest in the conclusion that questions such as effective bounds on the size of the neural network needed to approximate a given polynomial are open and interesting. What are other examples of mathematically specific analytical questions that would need to be answered to say that we "understand" neural networks? Are there questions that may be answered in more pure mathematical language?

(I am specifically thinking of methods in representation theory due to the use of physics in this paper --- and, selfishly, because it is my field of study. However, I can also imagine areas such as combinatorics/graph theory, algebraic geometry, and topology providing viable tools.)

**Tags:** machine-learning
> **Comments:**
> **username_1**: Is  GOFAI really that well understood? A lot of GOFAI seems to boild down to SAT solving, the archetypical NP-complete problem. Modern SAT solvers work remarkably well in practise, even though they should not according to the extant theory. Why?  
> **username_2**: there is really pre-deep learning and post-deep learning study/ change/ history in this area and its a major paradigm shift in the field. deep learning took off only within last half decade. the simple answer is that neural networks can represent arbitrarily complex functions and that complexity is now at very advanced levels with deep neural networks. another answer is that the problems that are studied, and maybe even "reality in general,", are "built out of features" and ANNs are now adept at learning very complex features.  
> **username_3**: I don't think people are really searching for "an answer" here. They seek to use neural networks to solve problems, and if the problem is indeed solved then it's fine. Knowing how the networks reached that solution isn't necessarily of interest here. Nobody cares much if it's a black/opaque box as long as it solves the issue.  

---

## 5 answers

### Answer by username_4 on 2016-09-27. Score: 42

There are a bunch of "no free lunch" theorems in machine learning, roughly stating that there can be no one master learning algorithm that performs uniformly better than all other algorithms (see, e.g., here <http://www.no-free-lunch.org/> ). Sure enough, deep learning can be "broken" without much difficulty:
<http://www.evolvingai.org/fooling>

Hence, to be provably effective, a learner needs *inductive bias* --- i.e., some prior assumptions about the data. Examples of inductive bias include assumptions of data sparsity, or low dimensionality, or that the distribution factorizes nicely, or has a large margin, etc. Various successful learning algorithms exploit these assumptions to prove generalization guarantees. For example, (linear) SVM works well when the data is well-separated in space; otherwise -- not so much.

I think the main challenge with deep learning is to understand what its inductive bias is. In other words, it is to prove theorems of the type: If the training data satisfies these assumptions, then I can guarantee something about the generalization performance. (Otherwise, all bets are off.)

Update (Sep-2019): In the two years since my posted answer, there has been a great deal of progress in understanding the inductive bias implicit in various DL and related algorithms. One of the key insights is that the actual optimization algorithm being used is important, since uniform convergence cannot explain why a massively over-parametrized system such as a large ANN manages to learn at all. It turns out that the various optimization methods (such as SGD) are implicitly regularizing with respect to various norms (such as $\ell\_2$). See this excellent lecture for other examples and much more:
<https://www.youtube.com/watch?v=zK84N6ST9sM>

> **Comments:**
> **username_5**: It should be noted that adversarial examples are not unique to deep neural networks. They can also easily be constructed for linear and logistic regression, for example: https://arxiv.org/pdf/1412.6572.pdf  
> **username_4**: Yes, but linear and logistic regression are much better theoretically understood.  
> **username_5**: It should perhaps also be noted that the NFL theorems [might not play a big role](https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf) in practical machine learning because while NFL is concerned with the class of *all* functions, real world problems are typically constrained to e.g. smooth functions or even more specific functions such as the ones considered in the paper by Lin and Tegmark. It might be possible to find inductive biases that cover all learning problems that we are interested in.  
> **username_4**: Then we should first formalize this space of "all learning problems that we are interested in".  
> **username_5**: That definitely seems worthwhile, especially with regards to AI safety. We need to be able to reliably specify what a machine learning algorithm is supposed to learn.  

---

### Answer by username_6 on 2016-10-01. Score: 27

There are two main gaps in our understanding of neural networks: optimization hardness and generalization performance.

Training a neural network requires solving a highly non-convex optimization problem in high dimensions. Current training algorithms are all based on gradient descent, which only guarantees convergence to a critical point (local minimum or saddle). In fact, [Anandkumar & Ge 2016](http://www.jmlr.org/proceedings/papers/v49/anandkumar16.pdf) recently proved that finding even a local minimum is NP-hard, which means that (assuming P != NP) there exist "bad", hard to escape, saddle points in the in the error surface.  
Yet, these training algorithms are empirically effective for many practical problems, and we don't know why.  
There have been theoretical papers such as [Choromanska et al. 2016](http://www.jmlr.org/proceedings/papers/v40/Choromanska15.pdf) and [Kawaguchi 2016](https://arxiv.org/abs/1605.07110) which prove that, under certain assumptions, the local minima are essentially as good as the global minima, but the assumptions they make are somewhat unrealistic and they don't address the issue of the bad saddle points.

The other main gap in our understanding is generalization performance: how well does the model perform on novel examples not seen during training? It's easy to show that in the limit of an infinite number of training examples (sampled i.i.d. from a stationary distribution), the training error converges to the expected error on novel examples (provided that you could train to the global optimum), but since we don't have infinite training examples, we are interested in how many examples are needed to achieve a given difference between training and generalization error. [Statistical learning theory](https://en.wikipedia.org/wiki/Statistical_learning_theory) studies these generalization bounds.  
Empirically, training a large modern neural network requires a large number of training examples (Big Data, if you like buzzwords), but not that monumentally large to be practically unfeasible. But if you apply the best known bounds from statistical learning theory (for instance [Gao & Zhou 2014](https://arxiv.org/abs/1402.3811)) you typically get these unfeasibly huge numbers. Therefore these bounds are very far from being tight, at least for practical problems.  
One of the reason might be that these bounds tend to assume very little about the data generating distribution, hence they reflect the worst-case performance against adversarial environments, while "natural" environments tend to be more "learnable".  
It is possible to write distribution-dependent generalization bounds, but we don't know how to formally characterize a distribution over "natural" environments. Approaches such as [algorithmic information theory](https://en.wikipedia.org/wiki/Algorithmic_information_theory) are still unsatisfactory.  
Therefore we still don't know why neural networks can be trained without overfitting.

Furthermore, it should be noted that these two main issues seem to be related in a still poorly understood way: the generalization bounds from statistical learning theory assume that the model is trained to the global optimum on the training set, but in a practical setting you would never train a neural network until convergence even to a saddle point, as to do so would typically cause overfitting. Instead you stop training when the error on a held-out validation set (which is a proxy for the generalization error) stops improving. This is known as "early stopping".  
So in a sense all this theoretical research on bounding the generalization error of the global optimum may be quite irrelevant: not only we can't efficiently find it, but even if we could, we would not want to, since it would perform worse on novel examples than many "sub-optimal" solutions.  
It may be the case that optimization hardness is not a flaw of neural network, on the contrary, maybe neural networks can work at all precisely because they are hard to optimize.  
All these observations are empirical and there is no good theory that explains them. There is also no theory that explains how to set the hyperparameters of neural networks (hidden layer width and depth, learning rates, architectural details, etc.). Practitioners use their intuition honed by experience and lots of trial and error to come up with effective values, while a theory could allow us to design neural networks in a more systematic way.


---

### Answer by username_7 on 2016-09-30. Score: 11

Another take on this question, to add to @Aryeh's remarks: For many other models of learning, we know the "shape" of the hypothesis space. SVMs are the best example of this, in that what you're finding is a linear separator in a (possibly-high dimensional) Hilbert space.

For neural networks in general, we don't have any such clear description or even an approximation. And such a description is important for us to understand what exactly a neural network is finding in the data.

> **Comments:**
> **username_8**: What would you call as the "shape" of the hypothesis space? :) Does Theorem 2.1 (page 3) of ours answer some of your question : https://eccc.weizmann.ac.il/report/2017/098/ ? :D  

---

### Answer by username_9 on 2017-10-08. Score: 4

The principle of Information Bottleneck has been proposed to explain the success of deep nueral networks.

Here is a quote from [Quanta magazine](https://www.quantamagazine.org/new-theory-cracks-open-the-black-box-of-deep-learning-20170921/)

> Last month, a YouTube video of a conference talk in Berlin, shared widely among artificial-intelligence researchers, offered a possible answer. In the talk, Naftali Tishby, a computer scientist and neuroscientist from the Hebrew University of Jerusalem, presented evidence in support of a new theory explaining how deep learning works. Tishby argues that deep neural networks learn according to a procedure called the “information bottleneck,” which he and two collaborators first described in purely theoretical terms in 1999. The idea is that a network rids noisy input data of extraneous details as if by squeezing the information through a bottleneck, retaining only the features most relevant to general concepts. Striking new computer experiments by Tishby and his student Ravid Shwartz-Ziv reveal how this squeezing procedure happens during deep learning, at least in the cases they studied.

References:

1- [Deep learning and the information bottleneck principle](http://ieeexplore.ieee.org/document/7133169/), Naftali Tishby and Noga Zaslavsky

2- [Opening the Black Box of Deep Neural Networks via Information](https://arxiv.org/abs/1703.00810), Ravid Shwartz-Ziv and Naftali Tishby

3- [Conference talk video: Information Theory of Deep Learning](https://www.youtube.com/watch?v=bLqJHjXihK8&feature=youtu.be) by Naftali Tishby


---

### Answer by username_10 on 2016-10-01. Score: 1

I would say that we still need to discover an efficient algorithm for training deep neural networks. Yes, SGD does work well in practice but finding a better algorithm that has guarantees to converge to global minimum would be very nice.


---

