On the Optimal Expressive Power of ReLU DNNs and Its Application in Approximation With the Kolmogorov Superposition Theorem

This article is devoted to studying the optimal expressive power of rectified linear unit (ReLU) deep neural networks (DNNs) and its application in approximation via the Kolmogorov superposition theorem (KST). We first constructively prove that any continuous piecewise linear (CPwL) functions on $[{0,1}]$ , comprising $\mathcal {O}(N^{2}L)$ segments, can be represented by ReLU DNNs with L hidden layers and N neurons per layer. Subsequently, we demonstrate that this construction is optimal regarding the parameter count of DNNs, achieved through investigating the shattering capacity of ReLU DNNs. Moreover, by invoking the KST, we achieve an enhanced approximation rate for ReLU DNNs of arbitrary width and depth when dealing with continuous functions in high-dimensional spaces.