Memory-optimal neural network approximation


Helmut Bölcskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen


Proc. of SPIE (Wavelets and Sparsity XVII), San Diego, CA, USA, Vol. 10394, pp. 10394-10394-12, Aug. 2017, (invited paper).

DOI: 10.1117/12.2272490

[BibTeX, LaTeX, and HTML Reference]


We summarize the main results of a recent theory—developed by the authors—establishing fundamental lower bounds on the connectivity and memory requirements of deep neural networks as a function of the complexity of the function class to be approximated by the network. These bounds are shown to be achievable. Specifically, all function classes that are optimally approximated by a general class of representation systems—so-called 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, shearlets, ridgelets, alpha-shearlets, and more generally alpha-molecules. This result elucidates a remarkable universality property of deep neural networks and shows that they achieve the optimum approximation properties of all affine systems combined. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm generates deep neural networks which provide close-to-optimal approximation rates at minimal connectivity. Moreover, stochastic gradient descent is found to actually learn approximations that are sparse in the representation system optimally sparsifying the function class the network is trained on.


Deep neural networks, function approximation, optimal sparse approximation, connectivity, shearlets


We recommend to instead read the associated extended manuscript.

Download this document:


Copyright Notice: © 2017 H. Bölcskei, P. Grohs, G. Kutyniok, and P. Petersen.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.