The Kolmogorov-Arnold representation theorem revisited

Johannes Schmidt-Hieber

Abstract

The Kolmogorov-Arnold (KA) representation theorem, which states that any multivariate continuous function can be represented as a superposition of univariate functions, has historically been used to argue against the necessity of depth in neural networks. This paper by Johannes Schmidt-Hieber reconciles the KA theorem with modern deep learning by demonstrating that the complex interior functions of the theorem are most efficiently represented through deep ReLU networks. By employing space-filling curves and a bit-extraction mechanism, the author shows that deep architectures can achieve minimax optimal approximation rates, providing a fresh theoretical foundation for the power of depth.

Introduction

For decades, a tension has existed between the Kolmogorov–Arnold (KA) representation theorem and the practice of deep learning. The KA theorem (1957) states that any multivariate continuous function can be represented as a sum of univariate functions—essentially a network with just two hidden layers. On the surface, this suggests that depth is unnecessary. However, the univariate functions produced by the theorem are often "wild"—highly non-smooth and fractal-like—making them impossible to represent with standard activation functions like ReLU in a shallow setting. Johannes Schmidt-Hieber's work, published in Neural Networks, addresses this by showing how these functions are compatible with deep ReLU networks.

The Depth Paradox in the KA Theorem

The primary criticism of the KA theorem's relevance, notably by Girosi and Poggio, was the non-smooth nature of the interior functions. These functions map high-dimensional inputs to a one-dimensional space but are typically highly non-smooth. Schmidt-Hieber tackles the question: Can we modify the KA representation so that it is compatible with smooth functions and deep ReLU networks?

Methodology: Bit Extraction and Space-Filling Curves

The author moves away from traditional non-constructive proofs and employs a construction based on Lebesgue space-filling curves. The method relies on three core components:

  1. Smoothness Transfer: By mapping the input space onto the Cantor set, the author proves a version of the KA theorem where the smoothness of the target multivariate function $f$ is preserved in the outer univariate function. This prevents small changes in input from causing wild oscillations.
  2. Bit Extraction via Depth: The interior function is viewed as a process of extracting binary digits from the input. While a shallow network struggles with this mapping, a deep network can perform it elegantly through iterative bit-extraction.
  3. Deep ReLU Construction: The paper constructs a specific deep ReLU network architecture where each layer essentially "peels off" the next digit of the input's binary representation.
Deep ReLU architectures for bit-extraction and summation.

Key Insights: Depth as a Decoder

The most striking insight is that the interior function of the KA theorem is essentially a coordinate decoder. A deep network acts as a decoder, iteratively processing the input to approximate the required univariate mappings. This construction achieves the minimax optimal approximation rate: for a $\beta$-smooth function, the error decreases at a rate of $m^{-\beta/d}$ relative to the number of parameters $m$.

Furthermore, the use of the Cantor set overcomes "Netto’s theorem," which usually prevents continuous mappings between different dimensions from being injective. This allows for a more stable and efficient representation.

Theoretical Results

The paper formalizes these insights through several key results:

  • Theorem 3: For any $\beta$-smooth function, there exists a deep ReLU network with $2K+3$ layers that achieves an approximation error of $O(2^{-\beta K})$.
  • Parameter Efficiency: The total number of non-zero parameters required is of the order $Kd$ (where $K$ is the number of bits and $d$ is the dimension), matching the efficiency of the best possible approximation schemes.
  • Architecture Specification: The proof defines a network with a constant width (around $4d$) but increasing depth, providing a theoretical blueprint for "thin and deep" networks.

Limitations and Future Work

While the paper provides a strong theoretical basis for depth, it has limitations. The results are primarily derived for functions with smoothness $\beta \le 1$. It remains unclear if this construction generalizes easily to higher-order smoothness. Additionally, the paper proves the existence of such a network but does not guarantee that standard training algorithms like Stochastic Gradient Descent (SGD) will actually find this "bit-extraction" solution. Future work could also explore anisotropic smoothness, where functions are smoother in some dimensions than others.

Summary updated

Abstract

There is a longstanding debate whether the Kolmogorov–Arnold representation theorem can explain the use of more than one hidden layer in neural networks. The Kolmogorov–Arnold representation decomposes a multivariate function into an interior and an outer function and therefore has indeed a similar structure as a neural network with two hidden layers. But there are distinctive differences. One of the main obstacles is that the outer function depends on the represented function and can be wildly varying even if the represented function is smooth. We derive modifications of the Kolmogorov–Arnold representation that transfer smoothness properties of the represented function to the outer function and can be well approximated by ReLU networks. It appears that instead of two hidden layers, a more natural interpretation of the Kolmogorov–Arnold representation is that of a deep neural network where most of the layers are required to approximate the interior function.
BibTeX
@article{schmidthieber2021kolmogorov,
  author = {Johannes Schmidt-Hieber},
  title = {{The Kolmogorov-Arnold representation theorem revisited}},
  journal = {Neural Networks},
  year = {2021},
  doi = {10.1016/j.neunet.2021.01.020},
}
Figure