Properly Learning Poisson Binomial Distributions (ctd)

18^th October 2017, 14:00
Piotr Krysta
University of Liverpool

Abstract

This talk is based on the paper "Properly Learning Poisson Binomial Distributions in Almost Polynomial Time" by Diakonikolas, Kane and Stewart, published at COLT 2016. They give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order n ? Z+ is the discrete probability distribution of the sum of n mutually independent Bernoulli random variables. Given O (1/?^2) samples from an unknown PBD P, this algorithm runs in time (1/?)^{O(log log(1/?))}, and outputs a hypothesis PBD that is ?-close to P in total variation distance. The sample complexity of our algorithm is known to be nearly-optimal, up to logarithmic factors, as established in previous work. However, the previously best known running time for properly learning PBDs was (1/?)^{O(log(1/?))}, and was essentially obtained by enumeration over an appropriate ?-cover.

As one of their contributions, they provide a novel structural characterisation of PBDs, showing that any PBD P is ?-close to another PBD Q with O(log(1/?)) distinct parameters. More precisely, they prove that, for all ? > 0, there exists an explicit collection M of (1/?)^{O(log log(1/?))} vectors of multiplicities, such that for any PBD P there exists a PBD Q with O(log(1/?)) distinct parameters whose multiplicities are given by some element of M, such that Q is ?-close to P. Their proof combines tools from Fourier analysis and algebraic geometry.

In this talk I will continue from last week and will present an upper bound. This talk will be self contained (for those who did not attend last week's).