{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:57:15Z","timestamp":1792072635399,"version":"4.4.0"},"reference-count":59,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Einstein Center for Mathematics Berlin"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["1446\/18"],"award-info":[{"award-number":["1446\/18"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG-SPP 1798"],"award-info":[{"award-number":["DFG-SPP 1798"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KU 1446\/21"],"award-info":[{"award-number":["KU 1446\/21"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KU 1446\/23"],"award-info":[{"award-number":["KU 1446\/23"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006188","name":"Einstein Stiftung Berlin","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006188","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["665044"],"award-info":[{"award-number":["665044"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005492","name":"Stanford University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005492","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM Journal on Mathematics of Data Science"],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>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 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 approximation of functions on low-dimensional immersed manifolds. Finally, we present numerical experiments demonstrating that the standard stochastic gradient descent algorithm yields deep neural networks with close-to-optimal approximation rates. Moreover, these results indicate that stochastic gradient descent can learn approximations that are sparse in the representation systems optimally sparsifying the function class the network is trained on.<\/jats:p>","DOI":"10.1137\/18m118709x","type":"journal-article","created":{"date-parts":[[2019,2,12]],"date-time":"2019-02-12T12:07:50Z","timestamp":1549973270000},"page":"8-45","source":"Crossref","is-referenced-by-count":162,"title":["Optimal Approximation with Sparsely Connected Deep Neural Networks"],"prefix":"10.1137","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3047-5149","authenticated-orcid":true,"given":"Helmut","family":"B\u00f6lcskei","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philipp","family":"Grohs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gitta","family":"Kutyniok","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Philipp","family":"Petersen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,2,12]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"930","DOI":"10.1109\/18.256500","volume":"39","author":"Barron A. R.","year":"1993","journal-title":"IEEE Trans. Inform. Theory"},{"key":"atypb2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1023\/A:1022650905902","volume":"14","author":"Barron A. R.","year":"1994","journal-title":"Mach. Learn."},{"key":"atypb3","unstructured":"J. Berner, P. Grohs, and A. Jentzen,\n                      Analysis of the Generalization Error: Empirical Risk Minimization over Deep Artificial Neural Networks Overcomes the Curse of Dimensionality in the Numerical Approximation of Black-Scholes Partial Differential Equations\n                      , preprint,https:\/\/arxiv.org\/abs\/1809.03062, 2018."},{"key":"atypb4","unstructured":"E. J. Cand\u00e8s,\n                      Ridgelets: Theory and Applications\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 1998."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S003614109936364X"},{"key":"atypb6","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1002\/cpa.10116","volume":"57","author":"Cand\u00e8s E. J.","year":"2002","journal-title":"Comm. Pure Appl. Math."},{"key":"atypb7","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1090\/S0025-5718-1994-1240656-2","volume":"63","author":"Chui C. K.","year":"1994","journal-title":"Math. Comp."},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1006\/acha.2001.0336","volume":"11","author":"Cohen A.","year":"2001","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atypb9","first-page":"698","author":"Cohen N.","year":"2016","journal-title":"NY"},{"key":"atypb10","first-page":"955","author":"Cohen N.","year":"2016","journal-title":"NY"},{"key":"atypb11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-01-00923-5","volume":"39","author":"Cucker F.","year":"2002","journal-title":"Bull. Amer. Math. Soc."},{"key":"atypb12","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF02551274","volume":"2","author":"Cybenko G.","year":"1989","journal-title":"Math. Control Signals Systems"},{"key":"atypb13","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1038\/nature16961","volume":"529","author":"Silver D.","year":"2016","journal-title":"Nature"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"I. Daubechies,\n                      Ten Lectures on Wavelets\n                      , SIAM, Philadelphia, 1992,https:\/\/doi.org\/10.1137\/1.9781611970104.","DOI":"10.1137\/1.9781611970104"},{"key":"atypb15","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1016\/j.acha.2007.03.003","volume":"23","author":"Demanet L.","year":"2007","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atypb16","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1017\/S0962492900002816","volume":"7","author":"DeVore R. A.","year":"1998","journal-title":"Acta Numer."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. A. DeVore and G. G. Lorentz,\n                      Constructive Approximation\n                      , Springer, New York, 1993.","DOI":"10.1007\/978-3-662-02888-9"},{"key":"atypb18","first-page":"261","volume":"4","author":"DeVore R. A.","year":"1996","journal-title":"Ann. Numer. Math."},{"key":"atypb19","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1006\/acha.1993.1008","volume":"1","author":"Donoho D. L.","year":"1993","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atypb20","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s003650010032","volume":"17","author":"Donoho D. L.","year":"2001","journal-title":"Constr. Approx."},{"key":"atypb21","first-page":"907","author":"Eldan R.","year":"2016","journal-title":"NY"},{"key":"atypb22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1017\/S0962492900002439","volume":"3","author":"Ellacott S.","year":"1994","journal-title":"Acta Numer."},{"key":"atypb23","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0893-6080(89)90003-8","volume":"2","author":"Funahashi K.-I.","year":"1989","journal-title":"Neural Networks"},{"key":"atypb24","unstructured":"I. Goodfellow, Y. Bengio, and A. Courville,\n                      Deep Learning\n                      , MIT Press, Cambridge, MA, 2016,http:\/\/www.deeplearningbook.org."},{"key":"atypb25","unstructured":"K. Gr\u00f6chenig,\n                      Foundations of Time-Frequency Analysis\n                      , Springer, New York, 2013."},{"key":"atypb26","first-page":"199","author":"Grohs P.","year":"2015","journal-title":"New York"},{"key":"atypb27","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.acha.2015.10.009","volume":"41","author":"Grohs P.","year":"2016","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atypb28","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1007\/s00041-015-9446-6","volume":"22","author":"Grohs P.","year":"2016","journal-title":"J. Fourier Anal. Appl."},{"key":"atypb29","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10208-013-9170-z","volume":"14","author":"Grohs P.","year":"2014","journal-title":"Found. Comput. Math."},{"key":"atypb30","author":"Grohs P.","journal-title":"IEEE Trans. Inform. Theory, submitted."},{"key":"atypb31","first-page":"189","author":"Guo K.","year":"2006","journal-title":"TN"},{"key":"atypb32","first-page":"770","author":"He K.","year":"2016","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, IEEE, Washington, DC"},{"key":"atypb33","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1109\/MSP.2012.2205597","volume":"29","author":"Hinton G.","year":"2012","journal-title":"IEEE Signal Process. Mag."},{"key":"atypb34","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0893-6080(91)90009-T","volume":"4","author":"Hornik K.","year":"1991","journal-title":"Neural Networks"},{"key":"atypb35","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0893-6080(89)90020-8","volume":"2","author":"Hornik K.","year":"1989","journal-title":"Neural Networks"},{"key":"atypb36","first-page":"1097","author":"Krizhevsky A.","year":"2012","journal-title":"NY"},{"key":"atypb37","doi-asserted-by":"crossref","first-page":"1564","DOI":"10.1016\/j.jat.2011.06.005","volume":"163","author":"Kutyniok G.","year":"2011","journal-title":"J. Approx. Theory"},{"key":"atypb38","unstructured":"Y. LeCun,\n                      Mod\u00e8les connexionnistes de l'apprentissage\n                      , Ph.D. thesis, These de Doctorat, Universit\u00e9 Paris 6, Paris, France, 1987."},{"key":"atypb39","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1038\/nature14539","volume":"521","author":"LeCun Y.","year":"2015","journal-title":"Nature"},{"key":"atypb40","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0925-2312(98)00111-8","volume":"25","author":"Maiorov V.","year":"1999","journal-title":"Neurocomputing"},{"key":"atypb41","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF02478259","volume":"5","author":"McCulloch W.","year":"1943","journal-title":"Bull. Math. Biophys."},{"key":"atypb42","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1006\/aama.1995.1008","volume":"16","author":"Mhaskar H.","year":"1995","journal-title":"Adv. Appl. Math."},{"key":"atypb43","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF02070821","volume":"1","author":"Mhaskar H. N.","year":"1993","journal-title":"Adv. Comput. Math."},{"key":"atypb44","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1162\/neco.1996.8.1.164","volume":"8","author":"Mhaskar H. N.","year":"1996","journal-title":"Neural Comput."},{"key":"atypb45","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/0196-8858(92)90016-P","volume":"13","author":"Mhaskar H. N.","year":"1992","journal-title":"Adv. Appl. Math."},{"key":"atypb46","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1142\/S0219530516400042","volume":"14","author":"Mhaskar H. N.","year":"2016","journal-title":"Anal. Appl. (Singap.)"},{"key":"atypb47","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1016\/S0307-904X(99)00006-2","volume":"23","author":"Nguyen-Thien T.","year":"1999","journal-title":"Appl. Math. Model."},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"E. Ott,\n                      Chaos in Dynamical Systems\n                      , 2nd ed., Cambridge University Press, Cambridge, UK, 2002.","DOI":"10.1017\/CBO9780511803260"},{"key":"atypb49","unstructured":"P. Petersen and F. Voigtlaender,\n                      Equivalence of Approximation by Convolutional Neural Networks and Fully-Connected Networks\n                      , preprint,https:\/\/arxiv.org\/abs\/1809.00973, 2018."},{"key":"atypb50","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.neunet.2018.08.019","volume":"108","author":"Petersen P.","year":"2018","journal-title":"Neural Networks"},{"key":"atypb51","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1017\/S0962492900002919","volume":"8","author":"Pinkus A.","year":"1999","journal-title":"Acta Numer."},{"key":"atypb52","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1038\/323533a0","volume":"323","author":"Rumelhart D. E.","year":"1986","journal-title":"Nature"},{"key":"atypb53","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1016\/j.acha.2016.04.003","volume":"44","author":"Shaham U.","year":"2018","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"I. Steinwart and A. Christmann,\n                      Support Vector Machines\n                      , Information Science and Statistics, Springer, New York, 2008.","DOI":"10.1007\/978-0-387-77242-4"},{"key":"atypb55","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"Tibshirani R.","year":"1996","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"atypb56","unstructured":"F. Voigtlaender and A. Pein,\n                      Analysis vs. Synthesis Sparsity for $\\alpha$-Shearlets\n                      , preprint,https:\/\/arxiv.org\/abs\/1702.03559, 2017."},{"key":"atypb57","unstructured":"D. Yarotsky,\n                      Universal Approximations of Invariant Maps by Neural Networks\n                      , preprint,https:\/\/arxiv.org\/abs\/1804.10306v1, 2018."},{"key":"atypb58","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.neunet.2017.07.002","volume":"94","author":"Yarotsky D.","year":"2017","journal-title":"Neural Netw."},{"key":"atypb59","unstructured":"D.X. Zhou,\n                      Universality of Deep Convolutional Neural Networks\n                      , preprint,https:\/\/arxiv.org\/abs\/1805.10769, 2018."}],"container-title":["SIAM Journal on Mathematics of Data Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M118709X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:11:27Z","timestamp":1787325087000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M118709X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/18M118709X"],"URL":"https:\/\/doi.org\/10.1137\/18m118709x","relation":{},"ISSN":["2577-0187"],"issn-type":[{"value":"2577-0187","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}