Optimal Approximation with Sparsely Connected Deep Neural Networks
  We derive fundamental lower bounds on the connectivity and the memory
requirements of deep neural networks guaranteeing uniform approximation rates
for arbitrary function classes in $L^2(\mathbb R^d)$. In other words, we
establish a connection between the complexity of a function class and the
complexity of deep neural networks approximating functions from this class to
within a prescribed accuracy. Additionally, we prove that our lower bounds are
achievable for a broad family of function classes. Specifically, all function
classes that are optimally approximated by a general class of representation
systems---so-called \emph{affine systems}---can be approximated by deep neural
networks with minimal connectivity and memory requirements. Affine systems
encompass a wealth of representation systems from applied harmonic analysis
such as wavelets, ridgelets, curvelets, shearlets, $\alpha$-shearlets, and more
generally $\alpha$-molecules. Our central result elucidates a remarkable
universality property of neural networks and shows that they achieve the
optimum approximation properties of all affine systems combined. As a specific
example, we consider the class of $\alpha^{-1}$-cartoon-like functions, which
is approximated optimally by $\alpha$-shearlets. We also explain how our
results can be extended to the case of functions on low-dimensional immersed
manifolds. Finally, we present numerical experiments demonstrating that the
standard stochastic gradient descent algorithm generates deep neural networks
providing close-to-optimal approximation rates. Moreover, these results
indicate that stochastic gradient descent can actually learn approximations
that are sparse in the representation systems optimally sparsifying the
function class the network is trained on.
