Approximation Theory of Shallow Neural Networks and Deep Convolutional Neural Networks

Abstract

Deep learning performs excellently in various real-world problems but suffers from the lack of theoretical explanation for this efficiency. This thesis concentrates on a theory of deep neural networks, demonstrating how to deduce a function that approximates the target function by computer algorithms based on data samples, and how to estimate the difference between the two functions. Estimating this distance by the sample size is the core in theoretical machine learning and the key to measuring the efficiency of the machine learning algorithms in theory.

Chapter 1 introduces some classical machine learning problems and methods to derive approximators by samples via computer algorithms. Then an explanation of the classical statistical method in machine learning theory follows, which suggests one pay attention to the approximability of neural networks. Although approximation theory in machine learning has been studied in a large literature, there are many more unsolved problems in this area.

Chapter 2 is a work on shallow neural networks induced by the rectified linear unit (ReLU) activation function. It solves an open problem of whether shallow ReLU neural networks can achieve similar approximation rates as shallow neural networks induced by the classical C^∞ sigmoid-type activation functions. We show the rate O(n^{−r/d d+2/d+4}) for approximating functions from the Holder space W^r_∞([-1,1]^d). This rate is asymptotically identical to the optimal one O(n^−r/d) given by shallow sigmoid neural networks.

Chapter 3 considers the approximability of deep convolutional neural networks (DCNNs). In this part, the target functions are considered to be of the form f◦Q(x) = f(Q(x)) with a polynomial Q on Rd and a univariate function f, both unknown. We prove the approximation rate is the same as the one approximating the univariable function f by shallow sigmoid networks, which means DCNNs work very powerfully on such problems. As a direct consequence, radial functions can be approximated by DCNNs excellently, whereas shallow neural networks are not capable to approximate radial functions well in the case of a large dimension d, which shows the superiority of DCNNs.

Chapter 4 is a work about the approximation theory of DCNNs and Korobov spaces. The Korobov spaces contain the functions which satisfy

∂^2df/∂x²₁. . . ∂x²_d ∈ L_p([0,1]^d).

Recently it is proved by Montanelli and Du that DNNs can approximate functions from Korobov spaces optimally. In this work, we prove an optimal approximation rate for DCNNs. This work suggests the great capability of DCNNs and the great efficiency of approximating special functions.

Date of Award	13 Jun 2022
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)