On the Multidimensional Random Subset Sum Problem

In the Random Subset Sum Problem, given n i.i.d. random variables X1, ..., Xn, we wish to approximate any point z ∈ [-1,1] as the sum of a suitable subset Xi1(z), ..., Xis(z) of them, up to error varepsilon. Despite its simple statement, this problem is of fundamental interest to both theoretical computer science and statistical mechanics. More recently, it gained renewed attention for its implications in the theory of Artificial Neural Networks. An obvious multidimensional generalisation of the problem is to consider n i.i.d. d-dimensional random vectors, with the objective of approximating every point z ∈ [-1,1]d. In 1998, G. S. Lueker showed that, in the one-dimensional setting, n=O(log frac 1varepsilon) samples guarantee the approximation property with high probability.In this work, we prove that, in d dimensions, n = O(d3log frac 1varepsilon · (log frac 1varepsilon + log d)) samples suffice for the approximation property to hold with high probability. As an application highlighting the potential interest of this result, we prove that a recently proposed neural network model exhibits universality: with high probability, the model can approximate any neural network within a polynomial overhead in the number of parameters.