Skip to content
— CH. 1 · INTRODUCTION —

Universal approximation theorem

~5 min read · Ch. 1 of 6
6 sections

  • The universal approximation theorem makes a claim that sounds almost too good to be true: a neural network, given enough size, can approximate any continuous function to any desired degree of accuracy. That single promise sits at the heart of modern machine learning, and it was not handed down from some obvious place. It had to be proved, and proved again, by researchers working independently across the late 1980s and early 1990s.

    The theorem raises questions that are worth sitting with. What does it actually mean to approximate any function? Why does the structure of a network matter? And if the theorem guarantees that a good network exists, why is training one still so hard? Those questions will unspool through the chapters ahead. What matters first is understanding what the theorem says, and what it pointedly does not.

  • Feedforward networks with a single hidden layer are the setting for the best-known version of the theorem. If that layer uses a non-polynomial activation function, the network qualifies as a universal approximator. Common choices like the sigmoid function and ReLU both satisfy that condition.

    Universality, in the arbitrary width case, is achieved by making the network wider. Adding more neurons to the hidden layer pushes the network's approximation closer to any target function. There is a separate, dual version of the result that achieves the same guarantee by going deeper instead, keeping the width fixed while stacking more layers.

    These are existence theorems, and that distinction matters enormously. They confirm that a network with the right structure exists but say nothing about how to find its parameters through training. They also stay silent on exactly how large a network must be for any particular function. The guarantee is real; the recipe is not included.

  • Ken-ichi Funahashi published results in May 1989 showing that Rumelhart-Hinton-Williams type backpropagation networks have universal approximation capability using sigmoidal activation functions, and he extended the finding to multi-output mappings. Two months later, in July 1989, Stinchcombe and Halbert White showed that multilayer feedforward networks with as few as one hidden layer are universal approximators, provided the activation function meets certain conditions.

    George Cybenko arrived at a related result independently in December 1989, working specifically with sigmoid activation functions and using methods drawn from functional analysis, including the Hahn-Banach theorem and the Riesz-Markov-Kakutani representation theorem. Cybenko had actually published the result first as a technical report in 1988 before the formal paper appeared.

    Hornik clarified the picture further in 1991, showing that the power to approximate universally does not come from any particular activation function but from the multilayer feedforward architecture itself. Then Moshe Leshno and colleagues in 1993, and Allan Pinkus in 1999, pinned down the precise condition: universal approximation is equivalent to having a nonpolynomial activation function.

  • Gustaf Gripenberg in 2003 was among the first to study the arbitrary depth case, the setting where width is bounded but the number of layers can grow. Zhou Lu and colleagues in 2017 established that networks of width n plus 4, using ReLU activation, can approximate any Lebesgue-integrable function on n-dimensional input when depth is unconstrained. The same paper showed a hard boundary: if width drops to n or below, that general expressive power disappears.

    Boris Hanin and Mark Sellke focused on ReLU networks in 2018, and in 2020 Patrick Kidger and Terry Lyons extended depth results to general activation functions including tanh and GeLU.

    A striking special case appeared in 2024, when Cai constructed a finite set of mappings he called a vocabulary, from which any continuous function can be approximated by composing a sequence of elements. The parallel to linguistics is deliberate: just as a finite vocabulary of words can be combined through grammar to express an infinite range of meanings, a finite set of mathematical building blocks can compose to cover any continuous function.

  • Maiorov and Pinkus studied the bounded depth and bounded width case first, in 1999. Their result was notable: networks with just two hidden layers, each containing a bounded number of units, can still be universal approximators, given the right activation function.

    In 2018, Guliyev and Ismailov constructed a smooth sigmoidal activation function that provides the universal approximation property for two-hidden-layer feedforward networks with fewer units than earlier bounds required. That same year they also built single-hidden-layer networks with bounded width that serve as universal approximators, though only for functions of a single variable. The result does not extend to multivariable functions.

    In 2022, Shen and collaborators obtained precise quantitative information about the depth and width needed to approximate a target function using deep, wide ReLU networks. The question of the minimum possible width for universality was first studied in 2021 by Park and colleagues, who identified the minimum width for approximating Lp functions with ReLU networks. In 2023, Cai obtained the optimal minimum width bound.

  • The Kolmogorov-Arnold representation theorem runs parallel to the universal approximation theorems in spirit. Robert Hecht-Nielsen showed that a three-layer neural network can approximate any continuous multivariate function using the Kolmogorov-Arnold result, and Vugar Ismailov extended this to discontinuous functions. In 2024, Ziming Liu and co-authors demonstrated a practical application of the framework.

    Reservoir computing offers a different angle. In that approach, a sparse recurrent neural network with fixed weights carries a fading memory and an echo state property, followed by a trainable output layer. Universality has been established separately for networks of rate neurons and for spiking neurons. In 2024, the framework was extended to quantum reservoirs, where the reservoir is built on qubits defined over Hilbert spaces.

    Graph convolutional neural networks also fall within reach of universal approximation results. Work by Bruel-Gabrielsson in 2020 showed that graph representations with certain injective properties are sufficient for universal function approximation on bounded graphs, with an accompanying method that performed at state of the art on a collection of benchmarks.

Common questions

What does the universal approximation theorem state?

The universal approximation theorem states that neural networks with a certain structure can approximate any continuous function to any desired degree of accuracy. The best-known version applies to feedforward networks with a single hidden layer using a non-polynomial activation function such as sigmoid or ReLU.

Who first proved the universal approximation theorem for neural networks?

Ken-ichi Funahashi published the first results in May 1989, followed by Stinchcombe and Halbert White in July 1989, and George Cybenko independently in December 1989. Cybenko had also published a technical report version in 1988. All three groups worked on the arbitrary-width case.

What is the difference between the arbitrary width and arbitrary depth versions of the universal approximation theorem?

The arbitrary-width version achieves universality by adding more neurons to a single hidden layer, making the network wider. The arbitrary-depth version keeps the width bounded but allows the number of layers to increase, making the network deeper. Zhou Lu and colleagues established in 2017 that width n plus 4 is sufficient for the depth case using ReLU activation.

Does the universal approximation theorem explain how to train a neural network?

No. The universal approximation theorems are existence theorems. They confirm that a network with the right structure exists but do not specify how to find its parameters through training, nor do they state exactly how large the network must be for a given function. Training is a practical challenge typically addressed with optimization algorithms like backpropagation.

What activation function condition is required for universal approximation?

The activation function must be nonpolynomial. Moshe Leshno and colleagues established this equivalence in 1993, and Allan Pinkus confirmed it in 1999. Hornik showed in 1991 that the choice of specific activation function is less important than the multilayer feedforward architecture itself.

How many hidden layers are needed for a bounded-width universal approximator?

Two hidden layers are sufficient, as Maiorov and Pinkus showed in 1999. Guliyev and Ismailov later constructed a smooth sigmoidal activation function in 2018 that achieves universal approximation with two hidden layers using fewer units than previous bounds required.

See all questions about Universal approximation theorem →

All sources

49 references cited across the entry

  1. 1tech reportOn the approximate realization of continuous mappings by neural networksKen-ichi Funahashi — May 1988
  2. 2conferencePhoneme recognition: neural networks vs. hidden Markov modelsA. Waibel et al. — 1988
  3. 3conferenceCapabilities of three-layered Perceptrons.B. Irie et al. — 1988
  4. 4journalOn the approximate realization of continuous mappings by neural networksKen-ichi Funahashi — May 1989
  5. 5journalMultilayer feedforward networks are universal approximatorsKurt Hornik et al. — January 1989
  6. 6journalApproximation by superpositions of a sigmoidal functionG. Cybenko — 1989
  7. 7journalApproximation capabilities of multilayer feedforward networksKurt Hornik — 1991
  8. 8journalMultilayer feedforward networks with a nonpolynomial activation function can approximate any functionMoshe Leshno et al. — January 1993
  9. 9journalApproximation theory of the MLP model in neural networksAllan Pinkus — January 1999
  10. 10journalApproximation by neural networks with a bounded number of nodes at each levelGustaf Gripenberg — June 2003
  11. 11journalError bounds for approximations with deep ReLU networksDmitry Yarotsky — October 2017
  12. 12journalThe Expressive Power of Neural Networks: A View from the WidthZhou Lu et al. — Curran Associates — 2017
  13. 13arxivApproximating Continuous Functions by ReLU Nets of Minimal WidthBoris Hanin et al. — 2018
  14. 14conferenceUniversal Approximation with Deep Narrow NetworksPatrick Kidger et al. — July 2020
  15. 15journalVocabulary for Universal Approximation: A Linguistic Perspective of Mapping CompositionsCai Yongqiang — 2024
  16. 16journalLower bounds for approximation by MLP neural networksVitaly Maiorov et al. — April 1999
  17. 17journalApproximation capability of two hidden layer feedforward neural networks with fixed weightsNamig Guliyev et al. — November 2018
  18. 18journalOn the approximation by single hidden layer feedforward neural networks with fixed weightsNamig Guliyev et al. — February 2018
  19. 19journalOptimal approximation rate of ReLU networks in terms of width and depthZuowei Shen et al. — January 2022
  20. 20conferenceMinimum Width for Universal ApproximationSejun Park et al. — 2021
  21. 21conferenceUniversal approximation power of deep residual neural networks via nonlinear control theoryPaulo Tabuada et al. — 2021
  22. 22journalUniversal Approximation Power of Deep Residual Neural Networks Through the Lens of ControlPaulo Tabuada et al. — May 2023
  23. 23journalAchieve the Minimum Width of Neural Networks for Universal ApproximationYongqiang Cai — 2023-02-01
  24. 24journalUniversal Approximation Theorems for Differentiable Geometric Deep LearningAnastasis Kratsios et al. — 2022
  25. 25journalKolmogorov's mapping neural network existence theoremRobert Hecht-Nielsen — 1987
  26. 26journalA three layer neural network can represent any multivariate functionVugar E. Ismailov — July 2023
  27. 27arxivKAN: Kolmogorov-Arnold NetworksZiming Liu et al. — 2024-05-24
  28. 28journalEcho state networks are universalL. Grigoryeva et al. — 2018
  29. 29journalOn the computational power of circuits of spiking neuronsWolfgang Maass et al. — 2004
  30. 30arxivUniversality conditions of unified classical and quantum reservoir computingFrancesco Monzani et al. — 2024
  31. 31journalNoncompact uniform universal approximationTeun van Nuland — 2024
  32. 32conferenceUniversal Approximation with Certified NetworksMaximilian Baader et al. — 2020
  33. 33journalFunction approximation with spiked random networksErol Gelenbe et al. — 1999
  34. 34conferenceResNet with one-neuron hidden layers is a Universal ApproximatorHongzhou Lin et al. — Curran Associates — 2018
  35. 35conferenceHow Powerful are Graph Neural Networks?Keyulu Xu et al. — 2019
  36. 36conferenceUniversal Function Approximation on GraphsRickard Brüel-Gabrielsson — Curran Associates — 2020
  37. 37conferenceNon-Euclidean Universal ApproximationAnastasis Kratsios et al. — Curran Associates — 2020
  38. 38journalUniversality of deep convolutional neural networksDing-Xuan Zhou — 2020
  39. 39journalRefinement and Universal Approximation via Sparsely Connected ReLU Convolution NetsAndreas Heinecke et al. — 2020
  40. 40journalUniversal Approximation Using Radial-Basis-Function NetworksJ. Park et al. — 1991
  41. 41journalUniversal Approximations of Invariant Maps by Neural NetworksDmitry Yarotsky — 2021
  42. 42journalUniversal Approximation Property of Hamiltonian Deep Neural NetworksMuhammad Zakwan et al. — 2023
  43. 43journalOn the approximate realization of continuous mappings by neural networksKen-Ichi Funahashi — May 1989
  44. 44bookNeural Networks and Deep LearningMichael A. Nielsen — 2015
  45. 45journalMinimum Width for Universal ApproximationSejun, Chulhee, Jaeho, Jinwoo Park, Yun, Lee, Shin — 2020-09-28
  46. 46journalDeep Network Approximation for Smooth FunctionsJianfeng Lu et al. — January 2021
  47. 47journalNonparametric estimation of composite functionsAnatoli B. Juditsky et al. — 2009-06-01
  48. 48journalWhy and when can deep-but not shallow-networks avoid the curse of dimensionality: A reviewTomaso Poggio et al. — 2017-03-14
  49. 49conferenceDeep, Skinny Neural Networks are not Universal ApproximatorsJesse Johnson — 2019