Learning Sums of Independent Random Variables with Sparse Collective Support

We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For A subset Z+, a sum of independent random variables with collective support A (called an A-sum in this paper) is a distribution S = X1 + cdots + XN where the Xi's are mutually independent (but not necessarily identically distributed) integer random variables with cupi mathsfsupp(Xi) subseteq A. We give two main algorithmic results for learning such distributions: 1. For the case | A | = 3, we give an algorithm for learning A-sums to accuracy ε that uses mathsfpoly(1/ε) samples and runs in time mathsfpoly(1/ε), independent of N and of the elements of A. 2. For an arbitrary constant k ≥ 4, if A = a1,...,ak with 0 ≤ a1 < ... < ak, we give an algorithm that uses mathsfpoly(1/ε) · log log ak samples (independent of N) and runs in time mathsfpoly(1/ε, log ak). We prove an essentially matching lower bound: if |A| = 4, then any algorithm must use Omega(log log a4) samples even for learning to constant accuracy. We also give similar-in-spirit (but quantitatively very different) algorithmic results, and essentially matching lower bounds, for the case in which A is not known to the learner.