<p>The paper that people usually cite is <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.8571">Almost Optimal Lower Bounds for Small Depth Circuits</a>, which appears in STOC 1986. The main result pertaining to your question is: </p>

<blockquote>
  <p>There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$. </p>
</blockquote>

<p>What's possible even more relevant is the fact that <a href="https://complexityzoo.uwaterloo.ca/Zooref#hmp93">$\mathsf{TC}^0$ admits an exponential separation between depth 3 and depth 2</a>. This is relevant because threshold gates are commonly used in deep networks. </p>

CC BY-SA 3.0
2014-04-17T01:28:11.243Z
it may be this is cited in neural net research by some & see the basic analogy but it has zilch actual/direct ref to neural networks. to fill it in, a ref that formally utilizes this papers results within the framework of neural nets would be valuable, if such a ref even exists.
vzn
CC BY-SA 3.0
2014-04-17T02:30:46.207Z
It's usually cited as intuition for why depth is important. I think that's a legitimate use. However, it's not the only example of larger depth being more powerful.
Suresh Venkat
CC BY-SA 3.0
2016-10-14T01:20:19.560Z
@SureshVenkat Is there a more modern review/exposition of this Hastad's result above? (I can see new writings of the PARITY not in AC^0 proof but not of this particular other result in the paper)
gradstudent
CC BY-SA 3.0
2014-04-16T22:10:43.413Z
2014-04-16T22:37:32.670Z
2014-04-16T22:37:32.670Z
Suresh Venkat
<p>Literally stated, the problem of exponentially separating neural nets of depth d from depth d-1, for all d, is open, to the best of my knowledge. When your "activation functions" are linear threshold functions for example, it is open whether all nets of all depths d can be simulated, with a polynomial increase in size, in depth 3.</p>

CC BY-SA 3.0
2014-04-17T10:20:03.483Z
Do you have a more general model of neural nets in mind than $\mathsf{TC}^0$ or the perceptrons mentioned in the other two answers?
András Salamon
CC BY-SA 3.0
2014-04-18T04:22:40.790Z
Well, I'm speaking about circuits composed of linear threshold functions of constant depth. That isn't more general than $TC^0$ of constant depth, however you need a greater constant depth to simulate linear threshold functions with $TC^0$. See Goldmann, Hastad, Razborov http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1336
Ryan Williams
CC BY-SA 3.0
2016-10-14T01:09:37.867Z
I am a bit confused about the references that have been given here. How are these neural nets at all if these are computing Boolean functions? Aren't we looking for separation results for $\mathbb{R}^n \rightarrow \mathbb{R}$ neural nets with ReLU activation?
gradstudent
CC BY-SA 3.0
2016-10-14T01:17:44.167Z
Read the content linked in the question, there is nothing mentioned about restricting to functions of that form nor are the activation functions restricted to ReLU.
Ryan Williams
CC BY-SA 3.0
2016-10-14T01:35:10.210Z
Yes, I read them. But don't the results quoted here like the ones by Hastad and others only apply to Boolean circuits? The Hastad result or the Goldman-Hastad-Razborov result that you quoted - none of them have any implication on "actual" nets which are $\mathbb{R}^n \rightarrow \mathbb{R}$ functions with ReLU gates. Right?
gradstudent
CC BY-SA 3.0
2016-10-14T02:18:23.927Z
As far as I know, they don't have immediate applications to the regime you are talking about. However if you were to Booleanize the inputs and outputs by taking e.g. the sign of the output of what you call an "actual net" then there is a close relationship again. See for example http://www.igi.tugraz.at/maass/psfiles/62b.pdf and the refs therein
Ryan Williams
CC BY-SA 3.0
2016-11-09T02:55:05.153Z
Now there is this paper, https://arxiv.org/abs/1611.01491
gradstudent
CC BY-SA 3.0
2014-04-17T02:55:49.983Z
2014-04-17T02:55:49.983Z
Ryan Williams
<p>The following paper proves an exponential separation of perceptrons of depth $d$ versus depth $d+1$. A perceptron is a circuit with a single threshold gate at the top, and unbouded fan-in boolean circuits as its inputs:</p>

<p><a href="http://dx.doi.org/10.1006/jcss.1997.1552">Christer Berg, Staffan Ulfberg: A Lower Bound for Perceptrons and an Oracle Separation of the $\mathsf{PP}^{\mathsf{PH}}$ Hierarchy. J. Comput. Syst. Sci. (JCSS) 56(3):263-271 (1998)</a></p>

<p>Perceptrons are often referred to as a model for neural networks. The authors were students of Johan Håstad, so this might be the reference you are looking for. </p>

CC BY-SA 3.0
2014-04-17T09:13:25.497Z
2014-04-17T09:13:25.497Z
Jan Johannsen
<p>I read it <a href="http://www.iro.umontreal.ca/~pift6266/H10/notes/deepintro.html#insufficient-depth-can-hurt">here</a> that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the neural network has at least $d$ layers. It was referring to a paper by Hastad. I didn't find it. Could someone tell me the title of the paper? I think this is a really fascinating theoretical result.</p>

CC BY-SA 3.0
2014-04-17T01:34:56.077Z
the ref you cite states it has been proven for logic gates, formal neurons, and RBFs, and seems to be stating Hastad proved this result for _RBFs_ (radial basis fns, "the latter case").
vzn
CC BY-SA 3.0
2014-04-17T03:55:47.790Z
there could be some handwaving going on here, the complexity of NNs seems to be at least as difficult as circuit complexity (but havent seen that proven) which is still full of many open problems. elsewhere this question turned up by se related match is relevant, [computational power of neural networks](http://cstheory.stackexchange.com/questions/2698/computational-power-of-neural-networks) tcs.se (ps, great to see some question on deep-learning here & the field at least tentatively linking up to TCS)
vzn
<cc.complexity-theory><reference-request>
Exponential gap on neural network layers
jakab922
# Exponential gap on neural network layers

(Asked by: username_0 on 2014-04-16)

I read it [here](http://www.iro.umontreal.ca/~pift6266/H10/notes/deepintro.html#insufficient-depth-can-hurt) that there are function families which need $\mathcal{O}(2^n)$ nodes on neural network with at most $d - 1$ layers to represent the function while need only $\mathcal{O}(n)$ if the neural network has at least $d$ layers. It was referring to a paper by Hastad. I didn't find it. Could someone tell me the title of the paper? I think this is a really fascinating theoretical result.

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: the ref you cite states it has been proven for logic gates, formal neurons, and RBFs, and seems to be stating Hastad proved this result for _RBFs_ (radial basis fns, "the latter case").  
> **username_1**: there could be some handwaving going on here, the complexity of NNs seems to be at least as difficult as circuit complexity (but havent seen that proven) which is still full of many open problems. elsewhere this question turned up by se related match is relevant, [computational power of neural networks](http://cstheory.stackexchange.com/questions/2698/computational-power-of-neural-networks) tcs.se (ps, great to see some question on deep-learning here & the field at least tentatively linking up to TCS)  

---

## 3 answers

### Answer by username_2 on 2014-04-16. Score: 9

The paper that people usually cite is [Almost Optimal Lower Bounds for Small Depth Circuits](http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.8571), which appears in STOC 1986. The main result pertaining to your question is:

> There exists a family of functions admitting linear size, depth $k$ circuits (of unbounded fan-in AND/OR and NOT) that requires exponential size at depth $k-1$.

What's possible even more relevant is the fact that [$\mathsf{TC}^0$ admits an exponential separation between depth 3 and depth 2](https://complexityzoo.uwaterloo.ca/Zooref#hmp93). This is relevant because threshold gates are commonly used in deep networks.

> **Comments:**
> **username_1**: it may be this is cited in neural net research by some & see the basic analogy but it has zilch actual/direct ref to neural networks. to fill it in, a ref that formally utilizes this papers results within the framework of neural nets would be valuable, if such a ref even exists.  
> **username_2**: It's usually cited as intuition for why depth is important. I think that's a legitimate use. However, it's not the only example of larger depth being more powerful.  
> **username_3**: @SureshVenkat Is there a more modern review/exposition of this Hastad's result above? (I can see new writings of the PARITY not in AC^0 proof but not of this particular other result in the paper)  

---

### Answer by username_4 on 2014-04-17. Score: 6

Literally stated, the problem of exponentially separating neural nets of depth d from depth d-1, for all d, is open, to the best of my knowledge. When your "activation functions" are linear threshold functions for example, it is open whether all nets of all depths d can be simulated, with a polynomial increase in size, in depth 3.

> **Comments:**
> **username_5**: Do you have a more general model of neural nets in mind than $\mathsf{TC}^0$ or the perceptrons mentioned in the other two answers?  
> **username_4**: Well, I'm speaking about circuits composed of linear threshold functions of constant depth. That isn't more general than $TC^0$ of constant depth, however you need a greater constant depth to simulate linear threshold functions with $TC^0$. See Goldmann, Hastad, Razborov http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1336  
> **username_3**: I am a bit confused about the references that have been given here. How are these neural nets at all if these are computing Boolean functions? Aren't we looking for separation results for $\mathbb{R}^n \rightarrow \mathbb{R}$ neural nets with ReLU activation?  
> **username_4**: Read the content linked in the question, there is nothing mentioned about restricting to functions of that form nor are the activation functions restricted to ReLU.  
> **username_3**: Yes, I read them. But don't the results quoted here like the ones by Hastad and others only apply to Boolean circuits? The Hastad result or the Goldman-Hastad-Razborov result that you quoted - none of them have any implication on "actual" nets which are $\mathbb{R}^n \rightarrow \mathbb{R}$ functions with ReLU gates. Right?  
> **username_4**: As far as I know, they don't have immediate applications to the regime you are talking about. However if you were to Booleanize the inputs and outputs by taking e.g. the sign of the output of what you call an "actual net" then there is a close relationship again. See for example http://www.igi.tugraz.at/maass/psfiles/62b.pdf and the refs therein  
> **username_3**: Now there is this paper, https://arxiv.org/abs/1611.01491  

---

### Answer by username_6 on 2014-04-17. Score: 5

The following paper proves an exponential separation of perceptrons of depth $d$ versus depth $d+1$. A perceptron is a circuit with a single threshold gate at the top, and unbouded fan-in boolean circuits as its inputs:

[Christer Berg, Staffan Ulfberg: A Lower Bound for Perceptrons and an Oracle Separation of the $\mathsf{PP}^{\mathsf{PH}}$ Hierarchy. J. Comput. Syst. Sci. (JCSS) 56(3):263-271 (1998)](http://dx.doi.org/10.1006/jcss.1997.1552)

Perceptrons are often referred to as a model for neural networks. The authors were students of Johan Håstad, so this might be the reference you are looking for.


---

