  For any positive integer $k$, there exist neural networks with $\Theta(k^3)$
layers, $\Theta(1)$ nodes per layer, and $\Theta(1)$ distinct parameters which
can not be approximated by networks with $\mathcal{O}(k)$ layers unless they
are exponentially large --- they must possess $\Omega(2^k)$ nodes. This result
is proved here for a class of nodes termed "semi-algebraic gates" which
includes the common choices of ReLU, maximum, indicator, and piecewise
polynomial functions, therefore establishing benefits of depth against not just
standard networks with ReLU gates, but also convolutional networks with ReLU
and maximization gates, sum-product networks, and boosted decision trees (in
this last case with a stronger separation: $\Omega(2^{k^3})$ total tree nodes
are required).
