# Learning Sums of Independent Random Variables with Sparse Collective Support

arXiv: https://arxiv.org/abs/1807.07013 · HTML: https://mlsanity.com/paper/1807.07013/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)

## Abstract (arXiv)

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.