In the field of machine learning, the universal approximation theorems (UATs) state that neural networks with a certain structure can, in principle, approximate any continuous function to any desired degree of accuracy. These theorems provide a mathematical justification for using neural networks, assuring researchers that a sufficiently large or deep network can model the complex, non-linear relationships often found in real-world data.Balázs Csanád Csáji (2001) Approximation with Artificial Neural Networks; Faculty of Sciences; Eötvös Loránd University, Hungary
The best-known version of the theorem applies to feedforward networks with a single hidden layer. It states that if the layer's activation function is non-polynomial (which is true for common choices like the sigmoid function or ReLU), then the network can act as a "universal approximator." Universality is achieved by increasing the number of neurons in the hidden layer, making the network "wider." Other versions of the theorem show that universality can also be achieved by keeping the network's width fixed but increasing its number of layers, making it "deeper."
These are existence theorems. They guarantee that a network with the right structure exists, but they do not provide a method for finding the network's parameters (training it), nor do they specify exactly how large the network must be for a given function. Finding a suitable network remains a practical challenge that is typically addressed with optimization algorithms like backpropagation.
Setup Artificial neural networks are combinations of multiple simple mathematical functions that implement more complicated functions from (typically) real-valued vectors to real-valued vectors. The spaces of multivariate functions that can be implemented by a network are determined by the structure of the network, the set of simple functions, and its multiplicative parameters. A great deal of theoretical work has gone into characterizing these function spaces.
Most universal approximation theorems are in one of two classes. The first quantifies the approximation capabilities of neural networks with an arbitrary number of artificial neurons ("arbitrary width" case) and the second focuses on the case with an arbitrary number of hidden layers, each containing a limited number of artificial neurons ("arbitrary depth" case). In addition to these two classes, there are also universal approximation theorems for neural networks with bounded number of hidden layers and a limited number of neurons in each layer ("bounded depth and bounded width" case).
History
Arbitrary width The first results concerned the arbitrary width case.
In March 1988, George Cybenko gave a rigorous mathematical proof of the approximation properties of sigmoidal networks.
Later that year in May 1988, Ken-ichi Funahashi published the ATR Technical Report On the Approximate Realization of Continuous Mappings by Neural Networks . In this report, he reinterpreted the Kolmogorov–Arnold–Sprecher theorem from the perspective of neural networks and showed that the four-layer neural network proposed by Rumelhart, Hinton, and Williams , with sigmoid activation functions in its hidden layers, can approximate arbitrary continuous mappings to any desired degree of accuracy. He further introduced the concept of sigmoid-like functions, a generalization of sigmoid activation functions, and proved that the same approximation property holds for this broader class. The result was also extended to multi-output mappings. The report additionally cited the speech-recognition work of Waibel et al. as a contemporary application of neural networks.
In May 1989, starting from the integral representation formula proposed by Irie and Miyake , Funahashi proved that a three-layer feedforward neural network (i.e., a network with a single hidden layer), using sigmoid activation functions in the hidden layer and linear activation functions in the input and output layers, can approximate arbitrary continuous mappings with arbitrary accuracy in the topology of uniform convergence . He further proved by mathematical induction that the same approximation property holds for arbitrary (k)-layer feedforward neural networks . He also noted that, although a single hidden layer is theoretically sufficient for universal approximation, deeper networks may realize the same mappings with fewer hidden units, identifying this as an important topic for future investigation.
In July 1989, , Maxwell Stinchcombe, and Halbert White
generalized the class of activation functions considered by Funahashi to include unbounded, non-monotonic, discontinuous, and measurable activation functions, and presented an alternative proof based on the Stone–Weierstrass theorem.
In December 1989, George Cybenko referred to the works of Funahashi and Hornik and presented a general proof based on the Hahn–Banach theorem and the Riesz representation theorem. He also introduced the concept of a discriminatory function, providing a broader theoretical framework for sigmoid-type activation functions.
Collectively, these results established the universal approximation capability of feedforward neural networks.
Hornik also showed in 1991 that it is not the specific choice of the activation function but rather the multilayer feed-forward architecture itself that gives neural networks the potential of being universal approximators. Moshe Leshno et al in 1993 and later Allan Pinkus in 1999 showed that the universal approximation property is equivalent to having a nonpolynomial activation function.
Arbitrary depth The arbitrary depth case was also studied by a number of authors such as Gustaf Gripenberg in 2003, Dmitry Yarotsky, Zhou Lu et al in 2017, Boris Hanin and Mark Sellke in 2018 who focused on neural networks with ReLU activation function. In 2020, Patrick Kidger and Terry Lyons extended those results to neural networks with general activation functions such, e.g. tanh or GeLU.
One special case of arbitrary depth is that each composition component comes from a finite set of mappings. In 2024, Cai constructed a finite set of mappings, named a vocabulary, such that any continuous function can be approximated by compositing a sequence from the vocabulary. This is similar to the concept of compositionality in linguistics, which is the idea that a finite vocabulary of basic elements can be combined via grammar to express an infinite range of meanings.
Bounded depth and bounded width The bounded depth and bounded width case was first studied by Maiorov and Pinkus in 1999. They showed that there exists an analytic sigmoidal activation function such that two hidden layer neural networks with bounded number of units in hidden layers are universal approximators.
In 2018, Guliyev and Ismailov constructed a smooth sigmoidal activation function providing universal approximation property for two hidden layer feedforward neural networks with fewer units in hidden layers. In 2018, they also constructed single hidden layer networks with bounded width that are still universal approximators for univariate functions. However, this does not apply for multivariable functions.
In 2022, Shen et al. obtained precise quantitative information on the depth and width required to approximate a target function by deep and wide ReLU neural networks.
Quantitative bounds The question of minimal possible width for universality was first studied in 2021, Park et al obtained the minimum width required for the universal approximation of Lp functions using feed-forward neural networks with ReLU as activation functions. Similar results that can be directly applied to residual neural networks were also obtained in the same year by Paulo Tabuada and Bahman Gharesifard using control-theoretic arguments. In 2023, Cai obtained the optimal minimum width bound for the universal approximation.
For the arbitrary depth case, Leonie Papon and Anastasis Kratsios derived explicit depth estimates depending on the regularity of the target function and of the activation function.
Kolmogorov network The Kolmogorov–Arnold representation theorem is similar in spirit. Indeed, certain neural network families can directly apply the Kolmogorov–Arnold theorem to yield a universal approximation theorem. Robert Hecht-Nielsen showed that a three-layer neural network can approximate any continuous multivariate function. This was extended to the discontinuous case by Vugar Ismailov.
Reservoir computing and quantum reservoir computing In reservoir computing a sparse recurrent neural network with fixed weights equipped of fading memory and echo state property is followed by a trainable output layer. Its universality has been demonstrated separately for what concerns networks of rate neurons and spiking neurons, respectively. In 2024, the framework has been generalized and extended to quantum reservoirs where the reservoir is based on qubits defined over Hilbert spaces.
Variants Variants include discontinuous activation functions, noncompact domains, certifiable networks, random neural networks, and alternative network architectures and topologies.
The universal approximation property of width-bounded networks has been studied as a dual of classical universal approximation results on depth-bounded networks. For input dimension and output dimension the minimum width required for the universal approximation of the Lp functions is exactly (for a ReLU network). More generally this also holds if both ReLU and a threshold activation function are used.
Universal function approximation on graphs (or rather on graph isomorphism classes) by popular graph convolutional neural networks (GCNs or GNNs) can be made as discriminative as the Weisfeiler–Leman graph isomorphism test. In 2020, a universal approximation theorem result was established by Brüel-Gabrielsson, showing that graph representation with certain injective properties is sufficient for universal function approximation on bounded graphs and restricted universal function approximation on unbounded graphs, with an accompanying -runtime method that performed at state of the art on a collection of benchmarks (where and are the sets of nodes and edges of the graph respectively).
There are also a variety of results between non-Euclidean spaces and other commonly used architectures and, more generally, algorithmically generated sets of functions, such as the convolutional neural network (CNN) architecture, radial basis functions, or neural networks with specific properties.
Arbitrary-width case A universal approximation theorem formally states that a family of neural network functions is a dense set within a larger space of functions they are intended to approximate. In more direct terms, for any function from a given function space, there exists a sequence of neural networks from the family, such that according to some criterion.
A spate of papers in the 1980s—1990s, from George Cybenko and etc, established several universal approximation theorems for arbitrary width and bounded depth. SeeHaykin, Simon (1998). Neural Networks: A Comprehensive Foundation, Volume 2, Prentice Hall. .Hassoun, M. (1995) Fundamentals of Artificial Neural Networks MIT Press, p. 48 for reviews. The following is the most often quoted:
Also, certain non-continuous activation functions such as the step function can be approximated by continuous activation functions, which then allows the approximation result to apply to those functions. In particular, this shows that a perceptron network with a single infinitely wide hidden layer can approximate arbitrary functions.
Such an can also be approximated by a network of greater depth by using the same construction for the first layer and approximating the identity function with later layers.