I read it here 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.

  • $\begingroup$ 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"). $\endgroup$
    – vzn
    Apr 17, 2014 at 1:34
  • $\begingroup$ 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 tcs.se (ps, great to see some question on deep-learning here & the field at least tentatively linking up to TCS) $\endgroup$
    – vzn
    Apr 17, 2014 at 3:55

3 Answers 3


The paper that people usually cite is Almost Optimal Lower Bounds for Small Depth Circuits, 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. This is relevant because threshold gates are commonly used in deep networks.

  • $\begingroup$ 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. $\endgroup$
    – vzn
    Apr 17, 2014 at 1:28
  • $\begingroup$ 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. $\endgroup$ Apr 17, 2014 at 2:30
  • $\begingroup$ @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) $\endgroup$ Oct 14, 2016 at 1:20

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.

  • $\begingroup$ 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? $\endgroup$ Apr 17, 2014 at 10:20
  • $\begingroup$ 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 citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$ Apr 18, 2014 at 4:22
  • $\begingroup$ 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? $\endgroup$ Oct 14, 2016 at 1:09
  • $\begingroup$ 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. $\endgroup$ Oct 14, 2016 at 1:17
  • $\begingroup$ 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? $\endgroup$ Oct 14, 2016 at 1:35

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)

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.