Strong Overall Error Analysis for the Training of Artificial Neural Networks Via Random Initializations

Abstract

Although deep learning-based approximation algorithms have been applied very successfully to numerous problems, at the moment the reasons for their performance are not entirely understood from a mathematical point of view. Recently, estimates for the convergence of the overall error have been obtained in the situation of deep supervised learning, but with an extremely slow rate of convergence. In this note, we partially improve on these estimates. More specifically, we show that the depth of the neural network only needs to increase much slower in order to obtain the same rate of approximation. The results hold in the case of an arbitrary stochastic optimization algorithm with i.i.d. random initializations.

Keywords

Deep learning / Artificial intelligence / Empirical risk minimization / Optimization

References

[1.] Bach F, Moulines E. Burges CJC , Bottou L, Welling M, Ghahramani Z, Weinberger KQ. Non-strongly-convex smooth stochastic approximation with convergence rate O ( 1 / n ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(1/n)$$\end{document}. Advances in Neural Information Processing Systems, 2013 Red Hook Curran Associates, Inc. 773-781

[2.] Barron AR. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Trans. Inf. Theory, 1993, 39(3): 930-945,

[3.] Bartlett PL, Bousquet O, Mendelson S. Local Rademacher complexities. Ann. Stat., 2005, 33(4): 1497-1537,

[4.] Beck, C., Jentzen, A., Kuckuck, B.: Full error analysis for the training of deep neural networks. Infin. Dimens. Anal. Quantum Probab. Relat. Top. 25 (2022), no. 2, Paper No. 2150020, 76 pp. 0219–0257, 65G99 (68T07), 4440215

[5.] Bercu B , Fort J-C. . Generic Stochastic Gradient Methods, 2013 New York American Cancer Society 1-8

[6.] Berner J, Grohs P, Jentzen A. 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. SIAM J. Math. Data Sci., 2020, 2(3): 631-657,

[7.] Cucker F, Smale S. On the mathematical foundations of learning. Bull. Am. Math. Soc. (N.S.), 2002, 39(1): 1-49,

[8.] Cybenko G. Approximation by superpositions of a sigmoidal function. Math. Control Signals Syst., 1989, 2(4): 303-314,

[9.] Du, S.S., Zhai, X., Poczós, B., Singh, A.: Gradient descent provably optimizes over-parameterized neural networks (2018). arXiv:1810.02054

[10.] E W, Ma C, Wu L. A priori estimates of the population risk for two-layer neural networks. Commun. Math. Sci., 2019, 17(5): 1407-1425,

[11.] E W, Ma C, Wu L. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Sci. China Math., 2020, 63: 1235-1258,

[12.] Funahashi K-I. On the approximate realization of continuous mappings by neural networks. Neural Netw., 1989, 2(3): 183-192,

[13.] Goodfellow I, Bengio Y, Courville A. . Deep Learning. Adaptive Computation and Machine Learning, 2016 Cambridge, MA MIT Press

[14.] Grohs, P., Hornung, F., Jentzen, A., von Wurstemberger, P.: A proof that artificial neural networks overcome the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations (2018). arXiv:1809.02362 (Accepted in Mem. Am. Math. Soc.)

[15.] Grohs, P., Hornung, F., Jentzen, A., Zimmermann, P.: Space-time error estimates for deep neural network approximations for differential equations. Adv. Comput. Math. 49 (2023), no. 1, Paper No. 4. 1019-7168, 65M99 (65M15 68T07), 4534487

[16.] Grohs, P., Jentzen, A., Salimova, D.: Deep neural network approximations for solutions of PDEs based on Monte Carlo algorithms. Partial Differ. Equ. Appl. 3 (2022), no. 4, Paper No. 45, 41 pp. 2662–2963, 65C05 (35-04), 4437476

[17.] Györfi L, Kohler M, Krzyżak A, Walk H. . A Distribution-Free Theory of Nonparametric Regression. Springer Series in Statistics, 2002 New York Springer,

[18.] Hartman EJ, Keeler JD, Kowalski JM. Layered neural networks with Gaussian hidden units as universal approximations. Neural Comput., 1990, 2(2): 210-215,

[19.] Hornik K. Approximation capabilities of multilayer feedforward networks. Neural Netw., 1991, 4(2): 251-257,

[20.] Hornik K, Stinchcombe M, White H. Multilayer feedforward networks are universal approximators. Neural Netw., 1989, 2(5): 359-366,

[21.] Jentzen, A., Welti, T.: Overall error analysis for the training of deep neural networks via stochastic gradient descent with random initialisation (2020). arXiv:2003.01291

[22.] Lu, J., Shen, Z., Yang, H., Zhang, S.: Deep network approximation for smooth functions (2020). arXiv:2001.03040

[23.] Massart, P.: Concentration Inequalities and Model Selection. Vol. 1896 of Lecture Notes in Mathematics, vol. 1896. Springer, Berlin (2007). (Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23 (2003))

[24.] Rio E. Moment inequalities for sums of dependent random variables under projective conditions. J. Theor. Probab., 2009, 22: 146-163,

[25.] Shen, Z., Yang, H., Zhang, S.: Deep network approximation characterized by number of neurons (2020). arXiv:1906.05497

[26.] van de Geer SA. . Applications of Empirical Process Theory. Cambridge Series in Statistical and Probabilistic Mathematics, 2000 Cambridge Cambridge University Press

[27.] Yarotsky D. Error bounds for approximations with deep ReLU networks. Neural Netw., 2017, 94: 103-114,

[28.] Zhou D-X. Universality of deep convolutional neural networks. Appl. Comput. Harmon. Anal., 2020, 48(2): 787-794,

[29.] Zou D, Cao Y, Zhou D, Gu Q. Gradient descent optimizes over-parameterized deep ReLU networks. Mach. Learn., 2019, 109: 467-492,

Funding

Deutsche Forschungsgemeinschaft(EXC 2044-390685587)