Probabilistic lower bounds for approximation by shallow perceptron networks. (July 2017)

• Record Type: Journal Article
• Authors: Kůrková, Věra; Sanguineti, Marcello
• Is Part Of: Neural networks. Volume 91(2017)
• Page Start: 34
• Page End: 41
• Publication Date: 2017-07
• Subjects: Shallow networks -- Perceptrons -- Model complexity -- Lower bounds on approximation rates -- Chernoff–Hoeffding bounds; Neural computers -- Periodicals; Neural networks (Computer science) -- Periodicals; Neural networks (Neurobiology) -- Periodicals; Nervous System -- Periodicals; Ordinateurs neuronaux -- Périodiques; Réseaux neuronaux (Informatique) -- Périodiques; Réseaux neuronaux (Neurobiologie) -- Périodiques; Neural computers; Neural networks (Computer science); Neural networks (Neurobiology); Periodicals; 006.32
• DOI: 10.1016/j.neunet.2017.04.003
• Languages: English
• ISSNs: 0893-6080

Abstract

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. Highlights: Lower bounds on errors in approximation by shallow signum perceptron networks. Probabilistic approach to derivation of lower bounds. Sets of input–output functions of shallow networks with growing numbers of perceptrons.