On the Multidimensional Random Subset Sum Problem

Luca Becchetti, Arthur Carvalho Walraven da Cunha, Andrea Clementi, Francesco D'Amore, Hicham Lesfari, Emanuele Natale, Luca TrevisanarXiv 2022 · DOI · OpenReview

TL;DR

This paper tackles the multidimensional Random Subset Sum Problem (RSSP), a fundamental challenge in computer science and statistical mechanics with recent ties to neural network theory. The authors provide a new theoretical bound showing that a significantly smaller number of samples (specifically, $O(d^3 \log(1/\varepsilon)(\log(1/\varepsilon) + \log d))$) are needed to approximate any point in a $d$-dimensional hypercube with high probability, compared to previous results. This breakthrough has direct implications for understanding the universality of certain neural network models.

What Problem Does This Paper Address?

The core problem is the Multidimensional Random Subset Sum Problem (RSSP). Imagine you have a collection of $n$ random $d$-dimensional vectors. The goal is to determine if, with high probability, you can form any target vector $\mathbf{z}$ within a $d$-dimensional hypercube (like $[-1, 1]^d$) by summing up a subset of these random vectors, with a small error $\varepsilon$.

This problem is a generalization of the one-dimensional RSSP, where it's known that $O(\log(1/\varepsilon))$ samples are sufficient. The challenge in $d$ dimensions is that the number of possible subsets grows exponentially, and the geometric complexity of covering the $d$-dimensional space with sums of these subsets becomes significantly harder. Previous work had shown that approximating any point in $d$ dimensions required a number of samples that grew exponentially with $d$, making it impractical. This paper aims to bridge this gap by finding a polynomial dependency on $d$.

Methods

The authors employ a second-moment approach to tackle the problem. This is a standard technique in probability theory for bounding the probability of a random variable being close to its mean. Here's a breakdown of their key methods:

  • Probabilistic Argument and Subset Families: They first establish the existence of "well-behaved" families of subsets. These families have the property that any two subsets in the family have a small intersection. This is crucial for controlling the dependencies between subset sums.
  • Second Moment Estimation: The core of the proof involves estimating the variance of the random variable representing the number of subsets that approximate a target vector. This is done by carefully bounding the covariance between the indicator variables for different subsets.
  • Leveraging Independence: They exploit the independence of the random vectors $X_i$ and analyze the sums of subsets by partitioning them into independent and dependent parts.
  • Concentration Inequalities: Chebyshev's inequality is used to relate the variance to the probability of deviation from the mean.
  • Probability Amplification: A union bound is applied to extend the result from approximating a single target vector to approximating all target vectors in the hypercube.
  • Application to Neural Networks: A key application involves showing the universality of a specific neural network model (the NNE model). They demonstrate that with high probability, this model can approximate any feed-forward neural network within a polynomial overhead in parameters, a significant improvement over previous exponential bounds.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on proving bounds for random variables drawn from specific distributions (standard normal).

Key Insights and Ideas

  • Polynomial Dependence on Dimension: The most significant insight is that the number of samples required for the multidimensional RSSP scales polynomially with the dimension $d$ (specifically, $d^3$), rather than exponentially. This makes the problem tractable in higher dimensions.
  • Controlled Intersections are Key: The paper highlights the importance of controlling the size of intersections between subsets. This allows for a more precise analysis of the dependencies between subset sums, which is crucial for bounding the variance.
  • Universality in Neural Networks: The result has a direct and impactful application in proving the universality of certain neural network architectures. It shows that a specific evolutionary neural network model can, with high probability, approximate any feed-forward network using a polynomial number of parameters, a substantial improvement over prior exponential bounds.
  • Tightness of Bounds: The authors provide arguments and lemmas that suggest their derived bounds are close to optimal, indicating that the polynomial dependence on $d$ is likely inherent to the problem.

Key Results

  • Main Theorem (Theorem 2): For $n$ independent $d$-dimensional standard normal random vectors, $n = \mathcal{O}(d^3 \log(1/\varepsilon)(\log(1/\varepsilon) + \log d))$ samples suffice to approximate any target vector $\mathbf{z} \in [-1,1]^d$ with error $\varepsilon$, with high probability.
  • Neural Network Universality (Theorem 10): A specific neural network model (NNE) can approximate any feed-forward neural network with a polynomial overhead in parameters, with high probability. This is a significant improvement over previous exponential bounds.
  • Generalizations: The paper also extends these results to a wider class of distributions and to non-centered, non-unitary normal random vectors.

Limitations and Future Work

  • Specific Distribution: The main results are proven for standard normal random vectors. While generalizations to other distributions are discussed, the core analysis is tied to the Gaussian assumption.
  • Approximation Error: The bounds are for approximating any point within a hypercube. The paper doesn't directly address the problem of approximating a specific target value with a very high probability, which might require different sample sizes.
  • Practical Implementation: The paper is theoretical. While it provides bounds, translating these into practical algorithms for very high dimensions might still be challenging due to the constants involved and the complexity of the bounds.
  • Discrete Setting: The authors suggest that adapting the proof to discrete distributions is a natural next step, and they briefly show how their results imply an analogous discrete result.
  • Wider Class of Networks: Extending the universality results to other types of neural network architectures (e.g., convolutional networks) is also mentioned as future work.

Summary updated

Abstract

In the Random Subset Sum Problem, given $n$ i.i.d. random variables $X_1, ..., X_n$, we wish to approximate any point $z \in [-1,1]$ as the sum of a suitable subset $X_{i_1(z)}, ..., X_{i_s(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 $\mathbf{z} \in [-1,1]^d$. In 1998, G. S. Lueker showed that, in the one-dimensional setting, $n=\mathcal{O}(\log \frac 1\varepsilon)$ samples guarantee the approximation property with high probability.In this work, we prove that, in $d$ dimensions, $n = \mathcal{O}(d^3\log \frac 1\varepsilon \cdot (\log \frac 1\varepsilon + \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.
BibTeX
@misc{becchetti2022multidimensional,
  author = {Luca Becchetti and Arthur Carvalho Walraven da Cunha and Andrea Clementi and Francesco D'Amore and Hicham Lesfari and Emanuele Natale and Luca Trevisan},
  title = {{On the Multidimensional Random Subset Sum Problem}},
  year = {2022},
  eprint = {2207.13944},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.13944},
}
Figure