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 $\supportset \subset \Z_{+}$,
a {\em sum of independent random variables with collective
support $\supportset$} (called an $\supportset$-sum in this
paper) is a distribution $\bS = \bX_1 + \cdots + \bX_N$ where the
$\bX_i$'s are mutually independent (but not necessarily identically
distributed) integer random variables with $\cup_i \supp(\bX_i) \subseteq
\supportset.$
We give two main algorithmic results for learning such distributions:
\begin{enumerate}
\item
For the case $| \supportset | = 3$,
we give an algorithm for learning
$\supportset$-sums
to accuracy $\eps$ that uses $\poly(1/\eps)$ samples and runs in time $\poly(1/\eps)$, independent of $N$ and of the elements of $\supportset$.
\item For an arbitrary constant $k \geq 4$, if
$\supportset = \{ a_1,...,a_k\}$ with $0 \leq a_1 < ... < a_k$,
we give an algorithm that uses $\poly(1/\eps) \cdot \log \log a_k$ samples (independent of $N$) and runs in time
$\poly(1/\eps, \log a_k).$
\end{enumerate}
We prove an essentially matching lower bound: if $|\supportset| = 4$,
then any algorithm
must use
\[
\Omega(\log \log a_4)
\]
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 $\supportset$ is not known to the learner.
Our learning algorithms employ new limit theorems which may be of independent interest. Our lower bounds rely on equidistribution type results from number theory. Our algorithms and lower bounds together settle the question of how the sample complexity of learning
sums of independent integer random variables
scales with the elements in the union of their supports,
both in the known-support and unknown-support settings. Finally, all our algorithms easily extend to the ``semi-agnostic''
learning model, in which training data is generated from a distribution that
is only $c \epsilon$-close to some
$\supportset$-sum for a constant $c>0$.