Source-linked AI summary
The Kolmogorov-Arnold representation theorem revisited
Johannes Schmidt-Hieber
TL;DR
The paper addresses whether the Kolmogorov-Arnold representation explains multiple hidden layers, given that its outer function may be irregular even for smooth targets. It develops modified representations transferring smoothness to the outer function and approximates them with deep ReLU networks. The resulting interpretation is a deep network in which most layers approximate the interior function.
Problem
Whether the Kolmogorov-Arnold representation can explain additional neural-network hidden layers remains disputed because its outer function depends on the represented function and may be irregular even when that function is smooth.
Method
The paper derives modified Kolmogorov-Arnold representations that transfer smoothness to the outer function and links them to deep ReLU network constructions.
Results
The construction achieves the expected approximation rate 2^-Kβ using order 2^Kd network parameters, without requiring network sparsity.
Takeaways & Limitations
The Kolmogorov-Arnold representation is more naturally interpreted as a deep neural network whose layers primarily approximate the interior function rather than as a two-hidden-layer network.
Takeaways & Limitations
It remains unclear whether the construction generalizes to higher-order or anisotropic smoothness, and the interior map’s distance behavior lacks a general characterization.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper revisits whether the Kolmogorov-Arnold representation explains additional neural-network layers, focusing on its structure, limitations, and a parameter-efficient deep ReLU construction.
- Motivation and representation: The Kolmogorov-Arnold representation expresses every continuous multivariate function using univariate inner and outer functions, resembling a network with two hidden layers.Its original formulation uses (2d+1)(d+1) univariate functions, while a related formulation realizes the structure with hidden layers of widths d and 2d+1.
- Motivation and representation: The composition of two ridge functions is essential because continuous multivariate functions lack exact ridge-function representations with matching best-approximation bounds.This composition differs from representing the target directly with a single ridge-function family.
- Motivation and representation: The theorem’s relevance to neural networks is disputed because its original proofs are non-constructive and its inner functions can be rough.The literature contains opposing assessments of whether Kolmogorov’s theorem is relevant to neural-network representations.
- Approximation objective: For β-smooth functions, approximation error m^-β requires at least order md parameters, establishing the target efficiency for a neural construction.The paper seeks a construction with at most order md parameters while retaining this approximation scale.
- Approximation objective: The paper derives modified representations that transfer smoothness from the multivariate function to the outer function and connects them to deep ReLU networks.This approach addresses explicit approximation-rate analysis and the low regularity of earlier interior functions.
- Approximation objective: Earlier sigmoid-based constructions require more than m^(4+d) weights for error of order m^-β, making them sub-optimal under the parameter target.A newer related approach leaves explicit rates unclear because the outer function depends non-trivially on the represented function.
2 New versions of the KA representation
The paper develops KA representations whose interior map is invertible and whose outer function can inherit smoothness from the represented function. These constructions preserve approximation rates while clarifying both the irregularity of the original representation and the scope of the new one.
- Motivation and construction: A space-filling construction rewrites a multivariate function using an interior map and a univariate outer function, but continuous surjective maps cannot generally be injective.The KA-style alternative uses a d-variate interior map, whereas the original KA representation uses univariate interior functions.
- Motivation and construction: The initial binary-digit representation makes the interior map invertible, yet its outer function can be discontinuous even when the represented function is smooth.For f(x)=x, every point with finite binary representation is a discontinuity of the outer function.
- Cantor-set representation: Using the Lebesgue curve and restricting the outer function to the Cantor set overcomes the earlier irregularity by producing a continuous invertible space-filling curve.The resulting interior map is surjective, invertible, and continuous, while its image has Hausdorff dimension log 2/log 3.
- Cantor-set representation: For β-smooth f, the modified representation transfers smoothness to the outer function g instead of allowing arbitrarily large fluctuations caused by the interior map.The construction relates proximity in the Cantor set to shared binary digits of the recovered coordinates.
- Approximation properties: The modified representation incurs no approximation-rate loss because g has smoothness α = β log 2/(d log 3) on a set of Hausdorff dimension d* = log 2/log 3, giving α/d* = β/d.This reduces multivariate approximation to univariate approximation on the Cantor set.
- Approximation properties: For functions piecewise constant on a dyadic grid, the modified outer function is Lipschitz with constant at most 2∥f∥∞3^kd, although the represented class with smooth outer functions is broader than β-smooth functions.The broader class includes all dyadic piecewise-constant functions when the outer function is Lipschitz continuous.
3 Deep ReLU networks and the KA representation
The paper reframes the KA representation as a deep ReLU construction: additional layers efficiently approximate the interior function, while the outer function is approximated separately.
- Interior-function approximation: Deep networks extract successive binary digits of an input, making the interior function efficient to represent with many layers and few parameters.The construction uses threshold-like units for bit extraction and linear units for accumulating the output.
- Interior-function approximation: The interior-function network uses K + 1 hidden layers, width 3d, and an overall number of non-zero parameters of order Kd.This makes the network deep while keeping the interior step inexpensive relative to approximating the univariate outer function.
- ReLU implementation: Threshold activations can be approximated with two ReLU units, yielding a deep ReLU network with K hidden layers and width four.The approximation may require potentially huge network parameters; additional hidden layers can reduce parameter magnitudes.
- Theorem 3 construction: Theorem 3 constructs a deep ReLU network with 2K + 3 hidden layers and architecture (2K + 3, (d, 4d, . . . , 4d, d, 1, 2Kd + 1, 1)).All network weights are bounded in absolute value by 2(Kd ∨∥f∥∞)2K(d∨(pβ)).
- Theorem 3 construction: The construction computes the interior map exactly on a large subset of [0, 1]d, with the exceptional set having Lebesgue measure bounded by 2−Kβp/d.The proof combines this interior approximation with an outer-function network and controls the resulting approximation error.
- Efficiency and scope: The resulting rate is 2−Kβ using order 2Kd network parameters, matching the expected rate without requiring network sparsity.The authors note that generalization to higher-order or anisotropic smoothness remains unclear.
4 Related literature
Related work connects deep ReLU approximation to partitioning, local Taylor expansions, modified KA representations, and efficient bit encoding, while differing in objectives and computability.
- Deep approximation constructions: A related construction partitions the input space into enumerated smaller hypercubes before approximating functions, and another combines this approach with local Taylor expansions.The latter achieves optimal approximation rates for functions smoother than Lipschitz.
- Modified KA representations: A modified KA representation can remove dependence of the outer activation function on f, but its activation is not computable and transfer to ReLU remains unclear.Later work addresses computable activations whose complexity increases as ε ↓0.
- Bit-based constructions: Prior deep-network results use bit encoding to compress several function values into one number, whereas this paper applies bit extraction to approximate the KA interior function.The cited works use related deep-network mechanisms for VC-dimension bounds or approximation rates.