  Let $\Omega = [0,1]^d$ be the unit cube in $\mathbb{R}^d$. We study the
problem of how efficiently, in terms of the number of parameters, deep neural
networks with the ReLU activation function can approximate functions in the
Sobolev spaces $W^s(L_q(\Omega))$ and Besov spaces $B^s_r(L_q(\Omega))$, with
error measured in the $L_p(\Omega)$ norm. This problem is important when
studying the application of neural networks in a variety of fields, including
scientific computing and signal processing, and has previously been solved only
when $p=q=\infty$. Our contribution is to provide a complete solution for all
$1\leq p,q\leq \infty$ and $s > 0$ for which the corresponding Sobolev or Besov
space compactly embeds into $L_p$. The key technical tool is a novel
bit-extraction technique which gives an optimal encoding of sparse vectors.
This enables us to obtain sharp upper bounds in the non-linear regime where $p
> q$. We also provide a novel method for deriving $L_p$-approximation lower
bounds based upon VC-dimension when $p < \infty$. Our results show that very
deep ReLU networks significantly outperform classical methods of approximation
in terms of the number of parameters, but that this comes at the cost of
parameters which are not encodable.
