C. Daskalakis and I. Diakonikolas and R. O'Donnell and R. Servedio and L.-Y. Tan.

In

Let S = X_1 + ... + X_n be a sum of n independent
integer random variables X_i, where each X_i is supported on
\{0,1,...,k-1\} but otherwise may have an arbitrary distribution
(in particular the X_i's need not be identically distributed).
How many samples are required to learn the distribution S to high
accuracy? In this paper we show
that the answer is *completely independent of n*,
and moreover we give a computationally efficient algorithm which
achieves this low sample complexity. More precisely, our algorithm learns
any such S to \epsilon-accuracy (with respect to the total variation distance
between distributions) using poly(k,1/\epsilon)
samples, independent of n. Its running time is
poly(k,1/\epsilon) in the standard word RAM model. Thus we give
a broad generalization of the main result of \cite{DDS12stoc}
which gave a similar learning result for the special case k=2 (when
the distribution S is a Poisson Binomial Distribution).

Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k = 2, sums of independent \{0,1,2\}-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated --- they are not log-concave, they can be Theta(n)-modal, there is no relationship between Kolmogorov distance and total variation distance for the class, etc. Nevertheless, the heart of our learning result is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent \{0,1,\dots, k-1\}-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the random variables X_i in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent \{0,1,\dots,k-1\}-valued random variables, is of independent interest.

pdf (full version).