Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
Ilias Diakonikolas, Daniel M. Kane, Alistair M. Stewart · Edinburgh Research Explorer (University of Edinburgh) · 2016
We give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order nn is the discrete probability distribution of the sum of nn mutually independent Bernoulli random variables. Given O˜(1/ϵ2)O~(1/ϵ2) samples from an unknown PBD PP, our algorithm runs in time (1/ϵ)O(loglog(1/ϵ))(1/ϵ)O(loglog(1/ϵ)), and outputs a hypothesis PBD that is ϵϵ-close to PP 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~\cite{DDS12stoc}. However, the previously best known running time for properly learning PBDs~\cite{DDS12stoc, DKS15} was (1/ϵ)O(log(1/ϵ))(1/ϵ)O(log(1/ϵ)), and was essentially obtained by enumeration over an appropriate ϵϵ-cover. We remark that the running time of this cover-based approach cannot be improved, as any ϵϵ-cover for the space of PBDs has size (1/ϵ)Ω(log(1/ϵ))(1/ϵ)Ω(log(1/ϵ))~\cite{DKS15}. As one of our main contributions, we provide a novel structural characterization of PBDs, showing that any PBD PP is ϵϵ-close to another PBD QQ with O(log(1/ϵ))O(log(1/ϵ)) distinct parameters. More precisely, we prove that, for all ϵ>0,ϵ>0, there exists an explicit collection MM of (1/ϵ)O(loglog(1/ϵ))(1/ϵ)O(loglog(1/ϵ)) vectors of multiplicities, such that for any PBD PP there exists a PBD QQ with O(log(1/ϵ))O(log(1/ϵ)) distinct parameters whose multiplicities are given by some element of MM, such that QQ is ϵϵ-close to P.P. Our proof combines tools from Fourier analysis and algebraic geometry.Our approach to the proper learning problem is as follows: Starting with an accurate non-proper hypothesis, we fit a PBD to this hypothesis. More specifically, we essentially start with the hypothesis computed by the computationally efficient non-proper learning algorithm in our recent work~\cite{DKS15}. Our aforementioned structural characterization allows us to reduce the corresponding fitting problem to a collection of (1/ϵ)O(loglog(1/ϵ))(1/ϵ)O(loglog(1/ϵ)) systems of low-degree polynomial inequalities. We show that each such system can be solved in time (1/ϵ)O(loglog(1/ϵ))(1/ϵ)O(loglog(1/ϵ)), which yields the overall running time of our algorithm.