Guaranteed Intervals for Kolmogorov’s Theorem (and Their Possible Relation to Neural Networks)

Abstract In 1987, R. Hecht-Nielsen noticed that a theorem that was proved by Kolmogorov in 1957 as a solution to one of Hilbert's problems, actually shows that an arbitrary function f can be implemented by a 3-layer neural network with appropriate activation functions and O/. The more accurately we implement these functions, the better approximation to f we get. Kolmogorov's proof can be transformed into a fast iterative algorithm that converges to the description of a network. However, this algorithm does not provide us with a guaranteed approximation accuracy: namely, if we want to approximate a given function f with a given accuracy ", this algorithm does not tell us after what iteration we can guarantee this accuracy. In 1991, Kurkova proposed a second algorithmic version of Kolmogorov's theorem. Namely, she showed how for every continuous function f, and for every " ? 0, we can construct a neural network that approximates f with a given accuracy ", i.e., whose output belongs to an interval [f (x1;:::; xn) \\Gamma "; f (x1;:::; xn) + "]. In the original Kolmogorov's theorem, the design (and, in particular, the number Nhidden of hidden neurons) does not change with ". In Kurkova's algorithm, when " ! 0, the number of hidden neurons increases (Nhidden! 1), and so does the complexity of the approximating network. The natural question is: can we provide a guaranteed approximation property and still keep Nhidden independent on "? Our asnwer is "yes". In this paper, we describe algorithms that generate the functions and O / (from the original