# What precisely is the extra power afforded by using deeper nets?

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.

• Perhaps this is helpful: arxiv.org/abs/1602.04485 – Chandra Chekuri Aug 21 '16 at 14:47
• 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 Aug 21 '16 at 19:36
• @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 Aug 22 '16 at 13:43
• @ChandraChekuri Now there is this paper, arxiv.org/abs/1611.01491 – gradstudent Dec 28 '16 at 19:31
• Maybe this? arxiv.org/abs/1511.07860 (Kane-Williams '15) – Clement C. May 20 '18 at 19:44