DL101 The Representation Capability of Neural Network Models

Fernando BerzalarXiv 2026 · arXiv

TL;DR

This paper provides a rigorous mathematical survey of neural network representation capability, tracing the evolution from the "existence" proofs of the 1980s to modern "efficiency" theorems. It establishes that while shallow networks can theoretically approximate any function, deep architectures are exponentially more expressive, providing the formal justification for the "deep" in deep learning.

What Problem Does This Paper Address?

In the early days of connectionism, researchers needed to know if neural networks were actually powerful enough to solve complex problems. This led to the Universal Approximation Theorems (UATs), which proved that even a simple network with one hidden layer could model any continuous function.

However, "could" is not the same as "should." The paper addresses the gap between theoretical possibility and practical efficiency. It tackles three core questions:

  1. What are the minimal requirements for a neural network to be a universal approximator?
  2. How fast does the approximation error drop as we add more neurons?
  3. Why do we stack layers (depth) instead of just making one layer really wide (width)?

Methods

The paper is a theoretical synthesis, utilizing tools from functional analysis and Fourier analysis to explain the behavior of feed-forward networks.

The author walks through the evolution of UAT proofs:

  • The Sigmoidal Era: Early proofs by Cybenko and Funahashi (1989) relied on the specific properties of sigmoidal (S-shaped) activation functions.
  • The Non-Polynomial Breakthrough: Leshno (1993) provided the "Key Constraint": a network is a universal approximator if and only if its activation function is non-polynomial. This explains why diverse functions like ReLU, Softplus, and Tanh all work, while a network of purely linear (polynomial degree 1) activations fails to gain expressivity.
  • Expressivity Analysis: For modern ReLU networks, the paper uses the concept of "linear regions"—the number of distinct affine pieces a network can create in the input space—to quantify complexity.
A summary of the main results discussed in the report, from shallow existence theorems to the power of depth.

Common activation functions discussed in the paper are summarized in the table below:

Common activation functions, their ranges, and derivatives.

Datasets

Not discussed in the paper. As a theoretical review, it focuses on mathematical function spaces (like $C(K)$, the space of continuous functions on a compact set) rather than empirical benchmarks.

Key Insights and Ideas

  • Polynomials are the Enemy of Universality: If your activation function $\sigma$ is a polynomial of degree $k$, any finite combination of them remains a polynomial of degree $k$. You can never approximate a function outside that specific polynomial class. Non-polynomiality is the "secret sauce" of neural networks.
  • Breaking the Curse of Dimensionality: Andrew Barron (1993) showed that for a specific class of smooth functions (Barron Space), the approximation error decreases at a rate of $O(1/\sqrt{H})$, where $H$ is the number of hidden units. Crucially, this rate is independent of the input dimension $n$, explaining why NNs excel in high-dimensional tasks where other methods fail.
  • Depth vs. Width: While a shallow network can approximate any function, it might require an astronomical number of neurons. Montúfar (2014) showed that depth increases the number of "linear regions" exponentially, whereas width only increases them polynomially.

Key Results

  • Universal Approximation: Confirmed for any continuous, non-polynomial activation function.
  • Barron’s Bound: Quantified the efficiency of shallow networks, showing that error scales with $1/\sqrt{H}$.
  • Montúfar’s Theorem: Proved that a deep ReLU network with $L$ layers and width $n$ can partition the input space into $\Omega((n/n_0)^{(L-1)n_0} n^{n_0})$ linear regions. This exponential growth with $L$ is the mathematical bedrock of deep learning's success.

Limitations and Future Work

The author is careful to note that representation is not learning. The theorems discussed provide "existence" guarantees—they prove a set of weights exists that can solve the problem. They do not guarantee:

  1. Optimization: That gradient descent will actually find those weights.
  2. Generalization: That a network that fits a training set will work on new data.
  3. Efficiency of Training: How long it takes to reach that optimal state.

The paper suggests that while we have mastered the "representation" pillar of deep learning theory, the "optimization" and "generalization" pillars remain areas of intense ongoing research.

Summary updated

Abstract

Universal approximation theorems (Cybenko, Funahashi, Hornik & Leshno) provide the mathematical justification for why neural networks are powerful enough to model complex, nonlinear phenomena. Shallow networks can approximate any continuous function on compact sets. Leshno's theorem clarified that non-polynomial activations are necessary for universality, which explains why ReLU, logistic, hyperbolic tangent, and other common activations work (but pure polynomials do not). However, approximation theorems provide no efficiency, training, nor generalization guarantees. They do not indicate how many neurons are needed for a given accuracy, whether gradient descent will find the right parameters, or whether networks trained on finite data will generalize well. Barron provided quantitative error bounds for particular function classes (approximation rates for functions with bounded Fourier norm), whereas Montúfar was the first to show that expressivity grows exponentially with depth (in terms of the number of linear regions). Deep networks are strictly more expressive than shallow ones with the same number of parameters. Depth is fundamentally more powerful than width, providing a rigorous mathematical explanation for the use of deep learning models.
BibTeX
@misc{berzal2026dl,
  author = {Fernando Berzal},
  title = {{DL101 The Representation Capability of Neural Network Models}},
  year = {2026},
  eprint = {2611.24980},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24980},
}
Figure