The Kolmogorov Superposition Theorem can Break the Curse of Dimensionality When Approximating High Dimensional Functions

We explain how to use Kolmogorov Superposition Theorem (KST) to overcome the curse of dimensionality in approximating multi-dimensional functions and learning multi-dimensional data sets by using neural networks of two hidden layers. That is, there is a class of functions called $K$-Lipschitz continuous in the sense that the K-outer function $g$ of $f$ is Lipschitz continuous and can be approximated by a ReLU network of two layers with $(2d+1)dn, dn$ widths to have an approximation order $O(d^2/n)$. In addition, we show that polynomials of high degree can be reproduced by using neural networks with activation function $\sigma_\ell(t)=(t_+)^\ell$ for $\ell\ge 2$ with multiple layers and appropriate widths. More layers of neural networks, the higher degree polynomials can be reproduced. Furthermore, we explain how many layers, weights, and neurons of neural networks are needed in order to reproduce high degree polynomials based on $\sigma_\ell$. Finally, we present a mathematical justification for image classification by using the convolutional neural network algorithm.