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.
Introduction
In 1957, Kolmogorov and Arnold proved a landmark result in approximation theory: any continuous multivariate function can be represented as a superposition of a small number of univariate functions. While this initially seemed to provide a theoretical foundation for neural networks with just two hidden layers, the machine learning community largely dismissed it in the late 1980s. Critics, most notably Girosi and Poggio, argued that the theorem was "irrelevant" because the univariate functions required were often "pathological"—fractal-like, non-smooth, and impossible to implement efficiently in practice.
This paper breathes new life into the Kolmogorov-Arnold (KA) representation by reframing it through the lens of modern deep learning. By modifying the construction to utilize space-filling curves and "bit-extraction" logic, the author demonstrates that the KA theorem is not just a mathematical curiosity but a blueprint for deep ReLU networks that achieve optimal approximation rates.
Methods: Smoothness and Bit-Extraction
The primary challenge in applying the KA theorem is ensuring that the representation "plays nice" with the smoothness of the target function. The author addresses this through two primary mechanisms:
- Smoothness Transfer via Cantor Sets: The paper derives a new version of the KA theorem where the "outer" function inherits the smoothness of the original multivariate function. This is achieved by mapping the input space into a Cantor set using a Lebesgue space-filling curve. This mapping ensures that points far apart in the input space do not get mapped too close together, preserving the structural integrity of the function.
- Bit-Extraction Networks: To implement the "interior" function (which maps $d$ dimensions down to 1), the author utilizes a deep ReLU architecture. These layers are designed to perform "bit extraction," retrieving binary digits from the input to perform dimension reduction. The author proves that the thresholding logic required for this can be approximated to arbitrary precision using standard ReLU units.
Reinterpreting Depth
Historically, the KA theorem was viewed as a justification for shallow networks. This paper argues for a paradigm shift: a more natural interpretation of the theorem is a deep network. In this construction, the vast majority of the layers are dedicated to the interior function—essentially performing massive dimension reduction via hierarchical bit-manipulation.
Notably, in this architecture, only the weights in the final layer depend on the specific function being approximated. All preceding layers (the interior function) are generic and independent of the target function, suggesting that the power of depth lies in its ability to perform universal, hierarchical encoding.
Key Results
- Optimal Approximation Rates: The paper proves that for a $eta$-smooth function in $d$ dimensions, a deep ReLU network can achieve an approximation error of $2^{-K\beta}$ using roughly $2^{Kd}$ parameters. This matches the known theoretical lower bounds for the "curse of dimensionality," proving the construction is optimally efficient.
- Continuity of Weights: Unlike other theories that rely on discontinuous "lookup table" logic, this construction allows for a continuous assignment of weights. This means small changes in the target function lead to small changes in the network weights, a vital property for stable learning and optimization.
Limitations and Future Work
While the paper provides a robust theoretical framework, it focuses primarily on functions with smoothness $eta \le 1$ (Lipschitz or Hölder continuous). Whether this KA-based approach can be generalized to higher-order smoothness ($eta > 1$) remains an open question. Additionally, while the paper proves these networks exist, it does not address whether standard training algorithms like Stochastic Gradient Descent (SGD) can reliably find them. Future research may explore how these constructions could inform more principled network initializations or handle anisotropic smoothness, where functions vary at different rates across different dimensions.
Summary updated