Error bounds for deep ReLU networks using the Kolmogorov-Arnold superposition theorem

Hadrien Montanelli, Haizhao Yang

TL;DR

This paper provides a theoretical breakthrough in understanding how deep neural networks can overcome the "curse of dimensionality." By applying a constructive version of the Kolmogorov–Arnold superposition theorem, the authors prove that deep ReLU networks can approximate a specific class of multivariate functions with a network size that grows much more slowly ($O(\epsilon^{-\log n})$) than the standard exponential rate ($O(\epsilon^{-n})$).

What Problem Does This Paper Address?

In approximation theory, researchers often run into the curse of dimensionality. Essentially, if you want to approximate a function of $n$ variables with an error of $\epsilon$, the number of parameters (or "size") of your model usually needs to grow as $O(\epsilon^{-n})$. As the number of dimensions $n$ increases, the required model size explodes, making high-dimensional problems computationally intractable.

While deep learning works remarkably well in high dimensions in practice, theoretical explanations for why it avoids this curse are still being developed. This paper seeks to bridge that gap by identifying a specific subset of continuous functions that deep ReLU networks can approximate much more efficiently than previously thought.

Methods

The authors combine two powerful mathematical frameworks:

  1. The Kolmogorov–Arnold (KA) Superposition Theorem: This theorem states that any continuous multivariate function can be decomposed into a sum of compositions of univariate (one-variable) functions. Specifically, it uses "inner" functions (which are fixed and independent of the target function) and "outer" functions (which depend on the target function).
  2. Deep ReLU Approximation Theory: The authors leverage recent work (notably by Yarotsky) showing that "very deep" ReLU networks—where the depth is proportional to the total number of weights—are exceptionally good at approximating univariate functions.

By representing the univariate components of the KA decomposition using deep ReLU networks, the authors construct a massive composite network and calculate the total error bounds for the entire system.

Datasets

Not discussed in the paper. This is a theoretical mathematics paper focused on proving existence theorems and error bounds; it does not include empirical experiments or benchmarking on specific datasets.

Key Insights and Ideas

  • KA Theorem as a Network Architecture: The KA theorem essentially describes a specific neural network architecture. The authors show that if we can approximate the "building blocks" (the univariate inner and outer functions) efficiently, we can approximate the whole multivariate function efficiently.
  • Univariate Efficiency: The "magic" happens because deep networks are incredibly efficient at 1D approximation. By breaking an $n$-dimensional problem into several 1D problems, the network avoids the exponential growth usually associated with high dimensions.
  • The $K_C$ Function Class: The authors define a new subset of continuous functions, denoted as $K_C$. For functions in this class, the "outer" functions in the KA decomposition behave well enough (specifically, their Lipschitz constants don't grow too fast) to allow for efficient approximation.
  • Depth is the Key: The results rely on "very deep" networks. The depth allows the network to "mimic" the recursive structure of the constructive KA proof.

Key Results

  • Lessening the Curse: For functions in the $K_C$ class, the authors prove that a deep ReLU network of size $W$ can achieve an error $\epsilon$ where $W = O(\epsilon^{-\log n})$.
  • Comparison: In the standard "cursed" scenario, the size is $O(\epsilon^{-n})$. Since $\log n$ grows much slower than $n$, this represents a significant theoretical improvement in efficiency for high-dimensional functions.
  • Constructive Proof: Unlike some existence proofs, this work uses a constructive version of the KA theorem, providing a theoretical blueprint for how such a network would be structured.

Limitations and Future Work

  • Smoothness Trade-offs: The authors note that for functions that are extremely smooth (having many derivatives), other approximation methods might still be more efficient than the $O(\epsilon^{-\log n})$ bound provided here.
  • Non-Lipschitz Inner Functions: The inner functions used in this specific KA construction are Hölder continuous but not Lipschitz continuous. The authors suggest that if a construction using Lipschitz inner functions were found, the error bound could potentially be improved even further to $O(\epsilon^{-1})$.
  • Activation Functions: This study focuses exclusively on ReLU. The authors suggest that investigating other smooth activation functions (like sigmoid or tanh) could yield similar or better results.
  • Practical Training: While the paper proves these networks exist, it doesn't address how to train them. Finding the specific KA decomposition for a given dataset remains a significant practical challenge.

Summary updated

Abstract

We prove a theorem concerning the approximation of multivariate functions by deep ReLU networks, for which the curse of the dimensionality is lessened. Our theorem is based on a constructive proof of the Kolmogorov–Arnold superposition theorem, and on a subset of multivariate continuous functions whose outer superposition functions can be efficiently approximated by deep ReLU networks.
BibTeX
@inproceedings{montanelli2020error,
  author = {Hadrien Montanelli and Haizhao Yang},
  title = {{Error bounds for deep ReLU networks using the Kolmogorov-Arnold superposition theorem}},
  booktitle = {Neural Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=Qvk0Vzj43f},
}

Loading related content...

Figure