Skip to content
Last Dictionary
Plane
Deep LearningMathematics & Statistics

universal approximation theorem

nounAlso: universal approximation, universal approximator, Cybenko's theorem

In plain wordsA mathematical result showing that a neural network with enough neurons can imitate essentially any smooth input-to-output relationship as closely as you like, though it does not say how to find that network.

  1. Any of a family of results guaranteeing that neural networksneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain. are expressive enough in principle: given a continuous function on a compact (closed and bounded) domain and a tolerance ε > 0, a suitably large network matches the function to within ε at every point. In the classic versions the network has one hidden layerhidden layer, n.: Any layer of a neural network between the input and the output. Its values are never shown to the user; they are the network's internal working-out. whose width may grow without limit, and Moshe Leshno and colleagues (1993) showed that this works exactly when the activation functionactivation function, n.: The simple rule each artificial neuron applies to its total input to decide its output, such as 'keep positive values, turn negatives into zero'. Without it, a deep network would be no smarter than a single layer. is not a polynomial, which covers sigmoidssigmoid function, n.: An S-shaped curve that squeezes any number into a value between 0 and 1, so the result can be read as a probability or as how far a switch is turned on. and ReLUReLU, abbr.: The most common rule a neuron uses to produce its output: keep the number if it is positive, replace it with zero if it is negative. Simple, fast and surprisingly effective.. Other versions fix the width and let depth grow: for n-dimensional inputs, ReLU networks of width n + 1 suffice (Boris Hanin and Mark Sellke). What the theorems promise is only that a good network exists; they do not say how large it must be in practice, whether gradient descentgradient descent, n.: A method for training models by repeatedly nudging every setting a small step in whichever direction most reduces the error, like a hiker who cannot see the valley but keeps stepping wherever the ground tilts down. would reach its weights, or how well it would generalizegeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers. from finite data.

    The universal approximation theorem tells you a solution exists, not that gradient descent will find it.

sup⁡x∈K∣f(x)−∑i=1Nvi σ(wi⊤x+bi)∣<ε\sup_{x \in K} \Big| f(x) - \sum_{i=1}^{N} v_i\, \sigma(w_i^{\top} x + b_i) \Big| < \varepsilon

Origin

Proved for sigmoidal networks by George Cybenko ('Approximation by Superpositions of a Sigmoidal Function', 1989) and, more generally, by Kurt Hornik, Maxwell Stinchcombe and Halbert White ('Multilayer Feedforward Networks Are Universal Approximators', 1989) and by Ken-Ichi Funahashi (1989); Hornik (1991) showed that the layered architecture, not the particular activation, is what confers universality. Robert Hecht-Nielsen had related the Kolmogorov–Arnold representation theorem to networks in 1987.

Usage note

Often over-read as explaining why deep learning works. Width alone suffices in principle, but other results show that some functions need exponentially more units in shallow networks than in deep ones.

Related

See also
  • multilayer perceptronmultilayer perceptron, n.: A neural network made of several layers of artificial neurons, each connected to every neuron in the next layer. It is the simplest kind of deep network and a component of almost every modern model.
  • hidden layerhidden layer, n.: Any layer of a neural network between the input and the output. Its values are never shown to the user; they are the network's internal working-out.
  • activation functionactivation function, n.: The simple rule each artificial neuron applies to its total input to decide its output, such as 'keep positive values, turn negatives into zero'. Without it, a deep network would be no smarter than a single layer.
  • Kolmogorov–Arnold networkKolmogorov–Arnold network, n.: A 2024 alternative to the standard neural network: instead of fixed rules inside neurons, every connection learns its own small curve, which can make the result easier to read as a formula.
  • generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers.
  • inductive biasinductive bias, n.: The assumptions built into a learning method that decide how it fills the gaps between the examples it was shown, such as that similar inputs get similar answers. Every learner needs some to cope with new cases.

Sources

  1. Cybenko, G. (1989). Approximation by Superpositions of a Sigmoidal Function. Mathematics of Control, Signals and Systems, 2(4), 303–314.
  2. Hornik, K., Stinchcombe, M. & White, H. (1989). Multilayer Feedforward Networks Are Universal Approximators. Neural Networks, 2(5), 359–366.
  3. Hornik, K. (1991). Approximation Capabilities of Multilayer Feedforward Networks. Neural Networks, 4(2), 251–257.

Mentioned in

neural networkneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain., hidden layerhidden layer, n.: Any layer of a neural network between the input and the output. Its values are never shown to the user; they are the network's internal working-out., multilayer perceptronmultilayer perceptron, n.: A neural network made of several layers of artificial neurons, each connected to every neuron in the next layer. It is the simplest kind of deep network and a component of almost every modern model., Kolmogorov–Arnold networkKolmogorov–Arnold network, n.: A 2024 alternative to the standard neural network: instead of fixed rules inside neurons, every connection learns its own small curve, which can make the result easier to read as a formula., radial basis function networkradial basis function network, n.: A three-layer network whose hidden neurons each respond to inputs near a particular reference point, like bells placed across the data; the output is a weighted mix of the bells.