BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260918T131929Z
UID:Seminar-EcCo-559@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20171018T140000
DTEND:20171018T150000
SUMMARY:Economics and Computation Series
DESCRIPTION:Piotr Krysta: Properly Learning Poisson Binomial Distributions (ctd)\n\n 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.\n\nAs 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.\n\nIn 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).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=559
LOCATION:
END:VEVENT
END:VCALENDAR