<p>For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can't? (for any $k$ and with no restriction on width on any of the two DNNs)  </p>

<p>I am equally happy to know of results which pertain to width restrictions on either side or vary the activation function between the two sides. </p>

<hr>

<p>I am not asking about approximation ability gaps like what have recently been proven by Elden and Shamir between $2-$DNN and $1-$DNN. </p>

CC BY-SA 3.0
2016-12-28T19:31:43.247Z
@ChandraChekuri Now there is this paper, https://arxiv.org/abs/1611.01491
gradstudent
CC BY-SA 3.0
2016-08-21T14:47:40.947Z
Perhaps this is helpful: http://arxiv.org/abs/1602.04485
Chandra Chekuri
CC BY-SA 3.0
2016-08-21T19:36:08.257Z
I'm pretty sure it's a theorem that every real function can be approximated arbitrarily well by a 1-layer network. (I'll try to dig up a reference). But some problems, e.g. PARITY takes exponentially more nodes to do in fewer layers. (That is, as the number of inputs $n$ grows, if you fix $k$, then the number of nodes per layer goes exponentially. If you allow $k$ to grow with $n$ you only need constant nodes per layer.)
Alex Meiburg
CC BY-SA 3.0
2016-08-22T13:43:22.943Z
@ChandraChekuri Thanks! I was looking at that paper by Telgarsky. I was feeling that this is still an approximation bound and it is not a gap between depth $k$ and $k+1$. Its probably a gap between $k$ and $k/\log (k)$.
gradstudent
CC BY-SA 4.0
2018-05-20T19:44:40.230Z
Maybe this? https://arxiv.org/abs/1511.07860 (Kane-Williams '15)
Clement C.
CC BY-SA 4.0
2018-05-23T16:26:29.010Z
@ClementC. Maybe you want to see our paper here, https://eccc.weizmann.ac.il/report/2017/190/ where we extended and modified a lot of this Kane-Williams paper to work for real neural nets. The paper also has many other things which are not related to the Kane-Williams paper.
Student
<circuit-complexity><machine-learning><lg.learning>
What precisely is the extra power afforded by using deeper nets?
gradstudent
# What precisely is the extra power afforded by using deeper nets?

(Asked by: username_0 on 2016-08-20)

For any choice of activation function (fix the choice for all the hidden nodes for both the following DNNs) do we know of functions which some $k$ (hidden layer) DNN can compute but a $(k-1)-$DNN can't? (for any $k$ and with no restriction on width on any of the two DNNs)

I am equally happy to know of results which pertain to width restrictions on either side or vary the activation function between the two sides.

---

I am not asking about approximation ability gaps like what have recently been proven by Elden and Shamir between $2-$DNN and $1-$DNN.

**Tags:** circuit-complexity, machine-learning, lg.learning

> **Comments:**
> **username_1**: Perhaps this is helpful: http://arxiv.org/abs/1602.04485  
> **username_2**: I'm pretty sure it's a theorem that every real function can be approximated arbitrarily well by a 1-layer network. (I'll try to dig up a reference). But some problems, e.g. PARITY takes exponentially more nodes to do in fewer layers. (That is, as the number of inputs $n$ grows, if you fix $k$, then the number of nodes per layer goes exponentially. If you allow $k$ to grow with $n$ you only need constant nodes per layer.)  
> **username_0**: @ChandraChekuri Thanks! I was looking at that paper by Telgarsky. I was feeling that this is still an approximation bound and it is not a gap between depth $k$ and $k+1$. Its probably a gap between $k$ and $k/\log (k)$.  
> **username_0**: @ChandraChekuri Now there is this paper, https://arxiv.org/abs/1611.01491  
> **username_3**: Maybe this? https://arxiv.org/abs/1511.07860 (Kane-Williams '15)  
> **username_4**: @ClementC. Maybe you want to see our paper here, https://eccc.weizmann.ac.il/report/2017/190/ where we extended and modified a lot of this Kane-Williams paper to work for real neural nets. The paper also has many other things which are not related to the Kane-Williams paper.  

---

## 0 answers

