Universal Approximation Theory: The basic theory for deep learning-based computer vision models

Wei Wang, Qing LiarXiv 2024 · DOI · arXiv

Modern computer vision (CV) has seen unprecedented success with architectures like ResNet and Vision Transformers (ViTs). However, a rigorous mathematical foundation explaining why these specific designs—particularly residual connections and depth—are so effective has remained elusive. This research introduces Dynamic Universal Approximation Theory (DUAT) to provide a unified theoretical framework for residual-based deep learning models.

The Theoretical Gap in Computer Vision

Despite empirical evidence that deeper networks and skip-connections improve performance, theoretical justifications have often been fragmented, relying on frequency domain analysis or subjective visualizations. The classic Universal Approximation Theorem (UAT) states that a single hidden layer can approximate any continuous function given enough neurons. However, UAT assumes static parameters after training, failing to capture the nuances of modern architectures that seem to adapt to their inputs. This paper addresses three core questions:

  1. Why do CNNs require significant depth?
  2. Why do residual networks (ResNets) consistently outperform fully convolutional ones (like VGG)?
  3. What are the fundamental structural differences between CNNs and ViTs?

Methodology: Standardizing Complexity

To build a unified theory, the researchers developed two primary tools: the Matrix-Vector Method and the Dynamic Universal Approximation Theorem.

The Matrix-Vector Method

The Matrix-Vector Method is a mathematical technique used to standardize disparate CV operations. Whether an architecture uses 2D/3D convolutions, mean-pooling, or Multi-Head Attention (MHA), this method transforms them into a consistent matrix-vector multiplication format: $W'x' = y'$. By mapping these operations onto a common mathematical "ruler," the researchers can compare different architectures directly.

The Matrix-Vector Method standardizes complex operations into a unified format, contrasting with traditional UAT formulas.

Dynamic Universal Approximation Theory (DUAT)

While the classic UAT relies on fixed parameters, DUAT proves that in residual-based models, the parameters effectively become functions of the input itself. In a residual block, the output is not just a transformation of the input, but the input plus a transformation. This structure allows the network's internal bias (and in the case of Transformers, the weights) to adapt dynamically to each specific input image. Using mathematical induction, the authors demonstrate that multi-layer residual networks maintain this dynamic property, significantly increasing their approximation power compared to static networks.

Mapping 2D/3D convolutions into the matrix-vector framework allows for a unified theoretical analysis of diverse architectures.

Key Insights and Structural Comparisons

Static vs. Dynamic Approximation

The theory distinguishes between "static" networks like VGG and "dynamic" networks like ResNet. In VGG, once training is complete, the weights and biases applied to every input are identical. In ResNet, the residual connections allow the network to adjust its internal bias parameters based on the specific features of the input image, leading to superior generalization and efficiency.

The Necessity of Depth

Depth serves two purposes in this framework. First, it allows local receptive fields to aggregate global information over multiple layers. Second, from a DUAT perspective, increasing the number of layers ($N$) directly scales the approximation power of the dynamic function, allowing it to represent more complex mappings.

CNNs vs. Vision Transformers (ViTs)

DUAT provides a rare bridge between CNNs and Transformers. While both are dynamic, they differ in degree. In residual CNNs, the input primarily influences the bias terms. In ViTs, the Multi-Head Attention mechanism ensures that the input influences both the weights and the bias. This makes ViTs theoretically more "dynamic" and flexible than their CNN counterparts.

Conclusion and Future Directions

By proving that almost all modern residual-based CV models are DUAT functions, this research offers a robust mathematical explanation for the current state of the art. The study formally demonstrates that ResNet’s superiority stems from its input-dependent bias adjustment, a capability static models lack.

While DUAT explains why current models work, it also opens doors for future architecture design. Future work may focus on creating models that maximize these dynamic properties or finding specific formulas for optimal depth and width. Furthermore, the authors speculate that human vision may operate as a biological DUAT system, suggesting a path for interdisciplinary research between computer vision and neuroscience.

Summary updated

BibTeX
@misc{wang2024universal,
  author = {Wei Wang and Qing Li},
  title = {{Universal Approximation Theory: The basic theory for deep learning-based computer vision models}},
  year = {2024},
  eprint = {2407.17480},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.17480},
}
Figure