We consider a basic problem in unsupervised learning: learning an unknown
Poisson Binomial Distribution. A Poisson Binomial Distribution (PBD)
over $\0,1,\dots,n\$ is the distribution of a sum of $n$ independent
Bernoulli random variables which may have arbitrary, potentially non-equal,
expectations. These distributions were first studied by S. Poisson in 1837
Poisson:37 and are a natural $n$-parameter generalization of the
familiar Binomial Distribution. Surprisingly, prior to our work this basic
learning problem was poorly understood, and known results for it were far from
optimal.
We essentially settle the complexity of the learning problem for this basic
class of distributions. As our first main result we give a highly efficient
algorithm which learns to $\eps$-accuracy (with respect to the total variation
distance) using $O(1/\eps^3)$ samples independent of $n$. The
running time of the algorithm is quasilinear in the size of its input
data, i.e., $O(łog(n)/\eps^3)$ bit-operations. (Observe that each draw
from the distribution is a $łog(n)$-bit string.) Our second main result is a
proper learning algorithm that learns to $\eps$-accuracy using
$O(1/\eps^2)$ samples, and runs in time $(1/\eps)^(łog
(1/\eps)) n$. This is nearly optimal, since any algorithm for this
problem must use $Ømega(1/\eps^2)$ samples. We also give positive and
negative results for some extensions of this learning problem to weighted sums
of independent Bernoulli random variables.
%0 Journal Article
%1 daskalakis2011learning
%A Daskalakis, Constantinos
%A Diakonikolas, Ilias
%A Servedio, Rocco A.
%D 2011
%K probability stats
%T Learning Poisson Binomial Distributions
%U http://arxiv.org/abs/1107.2702
%X We consider a basic problem in unsupervised learning: learning an unknown
Poisson Binomial Distribution. A Poisson Binomial Distribution (PBD)
over $\0,1,\dots,n\$ is the distribution of a sum of $n$ independent
Bernoulli random variables which may have arbitrary, potentially non-equal,
expectations. These distributions were first studied by S. Poisson in 1837
Poisson:37 and are a natural $n$-parameter generalization of the
familiar Binomial Distribution. Surprisingly, prior to our work this basic
learning problem was poorly understood, and known results for it were far from
optimal.
We essentially settle the complexity of the learning problem for this basic
class of distributions. As our first main result we give a highly efficient
algorithm which learns to $\eps$-accuracy (with respect to the total variation
distance) using $O(1/\eps^3)$ samples independent of $n$. The
running time of the algorithm is quasilinear in the size of its input
data, i.e., $O(łog(n)/\eps^3)$ bit-operations. (Observe that each draw
from the distribution is a $łog(n)$-bit string.) Our second main result is a
proper learning algorithm that learns to $\eps$-accuracy using
$O(1/\eps^2)$ samples, and runs in time $(1/\eps)^(łog
(1/\eps)) n$. This is nearly optimal, since any algorithm for this
problem must use $Ømega(1/\eps^2)$ samples. We also give positive and
negative results for some extensions of this learning problem to weighted sums
of independent Bernoulli random variables.
@article{daskalakis2011learning,
abstract = {We consider a basic problem in unsupervised learning: learning an unknown
\emph{Poisson Binomial Distribution}. A Poisson Binomial Distribution (PBD)
over $\{0,1,\dots,n\}$ is the distribution of a sum of $n$ independent
Bernoulli random variables which may have arbitrary, potentially non-equal,
expectations. These distributions were first studied by S. Poisson in 1837
\cite{Poisson:37} and are a natural $n$-parameter generalization of the
familiar Binomial Distribution. Surprisingly, prior to our work this basic
learning problem was poorly understood, and known results for it were far from
optimal.
We essentially settle the complexity of the learning problem for this basic
class of distributions. As our first main result we give a highly efficient
algorithm which learns to $\eps$-accuracy (with respect to the total variation
distance) using $\tilde{O}(1/\eps^3)$ samples \emph{independent of $n$}. The
running time of the algorithm is \emph{quasilinear} in the size of its input
data, i.e., $\tilde{O}(\log(n)/\eps^3)$ bit-operations. (Observe that each draw
from the distribution is a $\log(n)$-bit string.) Our second main result is a
{\em proper} learning algorithm that learns to $\eps$-accuracy using
$\tilde{O}(1/\eps^2)$ samples, and runs in time $(1/\eps)^{\poly (\log
(1/\eps))} \cdot \log n$. This is nearly optimal, since any algorithm {for this
problem} must use $\Omega(1/\eps^2)$ samples. We also give positive and
negative results for some extensions of this learning problem to weighted sums
of independent Bernoulli random variables.},
added-at = {2020-02-26T13:53:25.000+0100},
author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Servedio, Rocco A.},
biburl = {https://www.bibsonomy.org/bibtex/2d3c3423c29798eab110c936393965748/kirk86},
description = {[1107.2702] Learning Poisson Binomial Distributions},
interhash = {7d5fdd6a99b822a7732b3292400bf651},
intrahash = {d3c3423c29798eab110c936393965748},
keywords = {probability stats},
note = {cite arxiv:1107.2702Comment: Revised full version. Improved sample complexity bound of O~(1/eps^2)},
timestamp = {2020-02-26T13:53:25.000+0100},
title = {Learning Poisson Binomial Distributions},
url = {http://arxiv.org/abs/1107.2702},
year = 2011
}