Learning Sums of Independent Random Variables with Sparse Collective Support

Abstract

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For $\mathcal{A} \subset \mathbb{Z}_{+}$, a {sum of independent random variables with collective support $\mathcal{A}$} (called an $\mathcal{A}$-sum in this paper) is a distribution $\mathbf{S} = \mathbf{X}_1 + \cdots + \mathbf{X}_N$ where the $\mathbf{X}_i$'s are mutually independent (but not necessarily identically distributed) integer random variables with $\cup_i \mathrm{supp}(\mathbf{X}_i) \subseteq \mathcal{A}.$ We give two main algorithmic results for learning such distributions. First, for the case $| \mathcal{A} | = 3$, we give an algorithm for learning an unknown $\mathcal{A}$-sum to accuracy $\epsilon$ using $\mathrm{poly}(1/\epsilon)$ samples and running in time $\mathrm{poly}(1/\epsilon)$, independent of $N$ and of the elements of $\mathcal{A}$. Second, for an arbitrary constant $k \geq 4$, if $\mathcal{A} = \{ a_1,...,a_k\}$ with $0 \leq a_1 0$.