Learning Powers of Poisson Binomial Distributions

25^th October 2017, 13:00
Vasilis Kontonis
National Technical University of Athens

Abstract

We introduce the problem of simultaneously learning all powers of a Poisson Binomial Distribution (PBD). A PBD of order n is the distribution of a sum of n mutually independent Bernoulli random variables X_i, where E[X_i]=p_i. The k'th power of this distribution, for k in a range [m], is the distribution of P_k=?_{i=1}^{n}X_{i}^{(k)}, where each Bernoulli random variable X_{i}^{(k)} has E[X_{i}^{(k)}]=(p_i)^k. The learning algorithm can query any power P_k several times and succeeds in learning all powers in the range, if with probability at least 1??: given any k?[m], it returns a probability distribution Q_k with total variation distance from P_k at most ?. We provide almost matching lower and upper bounds on query complexity for this problem. We first show a lower bound on the query complexity on PBD powers instances with many distinct parameters p_i which are separated, and we almost match this lower bound by examining the query complexity of simultaneously learning all the powers of a special class of PBD's resembling the PBD's of our lower bound. We study the fundamental setting of a Binomial distribution, and provide an optimal algorithm which uses O(1/?^2) samples. Diakonikolas, Kane and Stewart [COLT'16] showed a lower bound of ?(2^{1/?}) samples to learn the p_i's within error ?. The question whether sampling from powers of PBDs can reduce this sampling complexity, has a negative answer since we show that the exponential number of samples is inevitable. Having sampling access to the powers of a PBD we then give a nearly optimal algorithm that learns its p_i's. To prove our two last lower bounds we extend the classical minimax risk definition from statistics to estimating functions of sequences of distributions.

Joint work with Dimitris Fotakis, Piotr Krysta and Paul Spirakis.

Additional Materials

• https://arxiv.org/abs/1707.05662