  We study expressive power of shallow and deep neural networks with piece-wise
linear activation functions. We establish new rigorous upper and lower bounds
for the network complexity in the setting of approximations in Sobolev spaces.
In particular, we prove that deep ReLU networks more efficiently approximate
smooth functions than shallow networks. In the case of approximations of 1D
Lipschitz functions we describe adaptive depth-6 network architectures more
efficient than the standard shallow architecture.
