Universal Approximation and the Learnability Gap in Deep Learning

This direction is merged into another direction: expressivity-learnability gap. Its last version stays readable and citable here.

Version 1 of 121 papers21 conceptsfrozen 2026-10-04

For decades, the Universal Approximation Theorem (UAT) has served as the mathematical "permission slip" for deep learning. It tells us that, given enough parameters, a neural network can approximate any continuous function. However, as architectures have evolved from simple multi-layer perceptrons to complex, structured models like Transformers and Graph Neural Networks, the focus of research has shifted.

Recent work demonstrates that while we can prove almost any modern architecture is a "universal approximator," there remains a persistent, fundamental gap between what a network can theoretically represent and what gradient-based optimization can actually discover.

Expanding the Scope of Universality

The original UAT focused on simple feed-forward networks. Modern research has extended these proofs to the specialized architectures that drive current AI. For instance, Yifang Chen, Xiaoyu Li, and colleagues proved in Universal Approximation of Visual Autoregressive Transformers that even minimalist Visual Autoregressive (VAR) models can approximate any complex image-to-image function. Similarly, Joshua Hanson showed that Temporal Convolutional Nets (TCNs) possess the same representational power as Recurrent Neural Networks (RNNs) for sequence mapping.

This expansion covers highly structured data as well. Marco Pacini and Robin Walters have established the universality of deep equivariant networks, which respect physical symmetries, in On Universality of Deep Equivariant Networks. Even in the realm of discrete mathematics, Ryoma Sato and Makoto Yamada have mapped the approximation ratios of Graph Neural Networks (GNNs) for NP-hard combinatorial problems, proving that specific architectural tweaks like port numbering can push these models toward theoretical optimality.

Efficiency and the Rate of Convergence

Proving that a model can represent a function is only half the battle; the other half is determining how many parameters it needs to do so efficiently. Research shows that certain architectures are exponentially more efficient than others for specific function classes.

Qingcan Wang demonstrated that for analytic functions, the approximation error of deep networks decays exponentially with depth, even if the width remains fixed. This efficiency is further explored by Tim De Ryck and Samuel Lanthaler, who found that networks using the hyperbolic tangent (tanh) activation function can outperform ReLU-based models when approximating smooth functions, achieving superior convergence rates in On the approximation of functions by tanh neural networks.

Bypassing the Curse of Dimensionality

One of the most significant triumphs of modern approximation theory is explaining why deep networks excel in high-dimensional spaces—such as solving Partial Differential Equations (PDEs)—where traditional numerical methods fail.

Researchers like Arnulf Jentzen and Pierfrancesco Beneventano have shown that deep ReLU networks can approximate solutions to high-dimensional heat equations and transport equations without the "curse of dimensionality." As detailed in Deep neural network approximation theory for high-dimensional functions, these networks succeed because they can exploit the intrinsic low-dimensional structures (or "reduced bases") of complex problems, allowing the number of parameters to grow polynomially rather than exponentially with the input dimension.

The Fundamental Gap: Expressivity vs. Learnability

Despite these robust proofs of representational power, a recurring theme across the literature is a cautionary note: existence does not imply reachability.

Every major study in this area—from Asja Fischer’s work on Deep Belief Networks to Zimeng Li’s analysis of low-rank networks—highlights a "significant gap" between approximation theory and optimization theory.

  1. Expressivity (The "Can"): A mathematical proof that a specific set of weights exists such that the network approximates the target function.
  2. Learnability (The "Will"): The probability that a standard algorithm, like Stochastic Gradient Descent (SGD), will actually find those weights starting from a random initialization.

As Satwik Bhattamishra and Michael Hahn point out in their comparison of Transformers and RNNs, a model might be mathematically capable of solving a task (like hierarchical balancing) while being practically unable to learn it via gradient descent. This distinction suggests that the future of neural network theory lies not just in proving what models can represent, but in understanding the "loss landscapes" that determine whether those ideal configurations are actually discoverable in practice.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_universal_approximation_and_the_learnabi_f9983220,
  title = {Universal Approximation and the Learnability Gap in Deep Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/universal-approximation-and-the-learnability-gap-in-deep-learning/rdr_f9983220c63249e7bdaf29ae10d1dd65},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_universal_approximation_and_the_learnabi_f9983220_v1,
  title = {Universal Approximation and the Learnability Gap in Deep Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/universal-approximation-and-the-learnability-gap-in-deep-learning/rdr_f9983220c63249e7bdaf29ae10d1dd65/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}