BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T123434Z
UID:Seminar-EcCo-560@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20171025T130000
DTEND:20171025T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Vasilis Kontonis: Learning Powers of Poisson Binomial Distributions\n\n 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.\n\nJoint work with Dimitris Fotakis, Piotr Krysta and Paul Spirakis.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=560
LOCATION:
END:VEVENT
END:VCALENDAR