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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.