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

Hadrien Montanelli, Haizhao Yang

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.

Introduction: Overcoming the Curse of Dimensionality

In the field of approximation theory, the "curse of dimensionality" presents a formidable barrier. Traditionally, approximating a function of $n$ variables with an error tolerance $\epsilon$ requires a model size that grows exponentially, typically at a rate of $O(\epsilon^{-n})$. As the number of dimensions $n$ increases, the computational resources and parameter counts needed for accurate approximation become prohibitive.

While deep learning has demonstrated remarkable success in high-dimensional tasks in practice, a rigorous theoretical understanding of why deep neural networks (DNNs) can circumvent this exponential growth is still evolving. This paper addresses this gap by identifying a specific class of multivariate continuous functions that deep Rectified Linear Unit (ReLU) networks can approximate with significantly improved efficiency.

Methodology: The Kolmogorov-Arnold Framework

The authors' approach hinges on the integration of two core mathematical concepts: the Kolmogorov–Arnold (KA) Superposition Theorem and advanced ReLU approximation theory.

The Kolmogorov–Arnold Superposition Theorem

The KA theorem posits that any continuous multivariate function can be decomposed into a sum of compositions of univariate functions. Specifically, a function $f(x_1, \dots, x_n)$ can be represented using a set of fixed "inner" functions that are independent of $f$, and "outer" functions that are specific to $f$.

The univariate inner function $\psi(x)$ used in the constructive proof.

The constructive proof utilized in this work employs specific univariate inner functions, such as the staircase-like function $\psi(x)$ shown above. These functions serve as the fundamental building blocks for the high-dimensional representation.

Deep ReLU Network Architecture

By leveraging the KA theorem, the authors conceptualize a neural network architecture where the univariate components—both inner and outer functions—are approximated by deep ReLU networks. Recent theoretical results have shown that "very deep" ReLU networks, where depth scales with the number of weights, are exceptionally efficient at 1D function approximation.

Schematic representation of the network architecture derived from the Kolmogorov-Arnold superposition theorem.

As illustrated in the diagram, the multivariate input $(x_1, \dots, x_n)$ is processed through layers of univariate approximations ($\widetilde{\psi}$) and then aggregated through outer functions ($\widetilde{\phi}_j^r$). This hierarchical structure allows the network to decompose an $n$-dimensional problem into a series of manageable 1D problems.

Key Insights: Efficiency through Depth

The primary breakthrough lies in the definition of a new function class, $K_C$. For functions within this class, the outer functions in the KA decomposition possess properties (specifically, controlled Lipschitz constants) that facilitate efficient approximation.

The "magic" of this approach is that the network's depth allows it to mimic the recursive structure of the KA proof. By breaking down the high-dimensional space into univariate components, the network avoids the standard exponential growth in parameters.

Key Results: Lessening the Curse

The authors prove that for functions in the $K_C$ class, a deep ReLU network of size $W$ can achieve an approximation error $\epsilon$ with a complexity of: $$W = O(\epsilon^{-\log n})$$

This result represents a substantial theoretical improvement over the standard $O(\epsilon^{-n})$ bound. Since $\log n$ grows much more slowly than $n$, the "curse" is significantly lessened for this class of functions. Furthermore, because the proof is constructive, it provides a theoretical blueprint for the design of such networks, moving beyond simple existence proofs.

Discussion and Future Directions

While this work provides a significant step forward, several avenues for future research remain:

  • Smoothness Trade-offs: For functions with high degrees of smoothness (many derivatives), other approximation methods might still outperform the $O(\epsilon^{-\log n})$ bound.
  • Inner Function Properties: The current construction uses inner functions that are Hölder continuous but not Lipschitz. Finding a construction with Lipschitz inner functions could potentially improve the error bound to $O(\epsilon^{-1})$.
  • Activation Functions: Extending this analysis to other activation functions like sigmoid or tanh could yield further insights.
  • Practical Implementation: The paper focuses on the existence of these efficient networks. A major remaining challenge is developing practical training algorithms to find the optimal KA decomposition for real-world datasets.

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},
}
Figure