Along with the rapid development of deep learning in practice, the theoretical explanations for its success become urgent. Generalization and expressivity are two widely used measurements to quantify theoretical behaviors of deep learning. The expressivity focuses on finding functions expressible by deep nets but cannot be approximated by shallow nets with the similar number of neurons. It usually implies the large capacity. The generalization aims at deriving fast learning rate for deep nets. It usually requires small capacity to reduce the variance. Different from previous studies on deep learning, pursuing either expressivity or generalization, we take both factors into account to explore the theoretical advantages of deep nets. For this purpose, we construct a deep net with two hidden layers possessing excellent expressivity in terms of localized and sparse approximation. Then, utilizing the well known covering number to measure the capacity, we find that deep nets possess excellent expressive power (measured by localized and sparse approximation) without enlarging the capacity of shallow nets. As a consequence, we derive near optimal learning rates for implementing empirical risk minimization (ERM) on the constructed deep nets. These results theoretically exhibit the advantage of deep nets from learning theory viewpoints.
Model complexities of shallow (i.e., one-hidden-layer) networks representing highly varying multivariable - 1 , 1 -valued functions are studied in terms of variational norms tailored to dictionaries of network units. It is shown that bounds on these norms define classes of functions computable by networks with constrained numbers of hidden units and sizes of output weights. Estimates of probabilistic distributions of values of variational norms with respect to typical computational units, such as perceptrons and Gaussian kernel units, are derived via geometric characterization of variational norms combined with the probabilistic Chernoff Bound. It is shown that almost any randomly chosen - 1 , 1 -valued function on a sufficiently large d-dimensional domain has variation with respect to perceptrons depending on d exponentially. Abstract Limitations of approximation capabilities of shallow perceptron networks are investigated. Lower bounds on approximation errors are derived for binary-valued functions on finite domains. It is proven that unless the number of network units is sufficiently large (larger than any polynomial of the logarithm of the size of the domain) a good approximation cannot be achieved for almost any uniformly randomly chosen function on a given domain. The results are obtained by combining probabilistic Chernoff–Hoeffding bounds with estimates of the sizes of sets of functions exactly computable by shallow networks with increasing numbers of units.  Lets≥1 be an integer andW be the class of all functions having integrable partial derivatives on [0, 1] s . We are interested in the minimum number of neurons in a neural network with a single hidden layer required in order to provide a mean approximation order of a preassignede>0 to each function inW. We prove that this number cannot be ( O ( ^ - s log(1 )) ) if a spline-like localization is required. This cannot be improved even if one allows different neurons to evaluate different activation functions, even depending upon the target function. Nevertheless, for anyδ>0, a network with ( O ( ^ - s - ) ) neurons can be constructed to provide this order of approximation, with localization. Analogous results are also valid for otherL p norms. Abstract In this paper, we aim at analyzing the approximation abilities of shallow networks in reproducing kernel Hilbert spaces (RKHSs). We prove that there is a probability measure such that the achievable lower bound for approximating by shallow nets can be realized for all functions in balls of reproducing kernel Hilbert space with high probability, which is different with the classical minimax approximation error estimates. This result together with the existing approximation results for deep nets shows the limitations for shallow nets and provides a theoretical explanation on why deep nets perform better than shallow nets. 