  We study the interpolation power of deep ReLU neural networks. Specifically,
we consider the question of how efficiently, in terms of the number of
parameters, deep ReLU networks can interpolate values at $N$ datapoints in the
unit ball which are separated by a distance $\delta$. We show that $\Omega(N)$
parameters are required in the regime where $\delta$ is exponentially small in
$N$, which gives the sharp result in this regime since $O(N)$ parameters are
always sufficient. This also shows that the bit-extraction technique used to
prove lower bounds on the VC dimension cannot be applied to irregularly spaced
datapoints. Finally, as an application we give a lower bound on the
approximation rates that deep ReLU neural networks can achieve for Sobolev
spaces at the embedding endpoint.
