skip to main content
Caltech
Fires burning in Greater Los Angeles area have had significant impact on the Caltech's community and surrounding areas. For information and resources for members of the Caltech community, go to https://www.caltech.edu/fire.

CS Theory Seminar

Thursday, November 30, 2017
3:00pm to 4:00pm
Add to Cal
Annenberg 314
Learning Sums of Independent Commonly Supported Integer Random Variables
Anindya De, Northwestern University,

Abstract: This talk is about learning Sums of Independent Commonly Supported Integer Random Variables, or SICSIRVs. For S a finite set of natural numbers, an "S-supported SICSIRV" is a random variable which is the sum of N independent random variables each of which is supported on S. 

So, for example, if S = {0,1}, then an S-supported SICSIRV is a sum of N independent but not necessarily identically distributed Bernoulli random variables (a.k.a. a Poisson Binomial random variable).
Daskalakis et. al. (STOC 12, FOCS 13) have shown that for S={0,1,...,k-1}, there is an algorithm for learning an unknown S-SICSIRV using poly(k,1/\epsilon) draws from the distribution and running in poly(k,1/\epsilon) time, independent of N.

In this work we investigate the problem of learning an unknown S-SICSIRV where S={a_1,...,a_k} may be any finite set. We show that when |S|=3, it is possible to learn any S-SICSIRV with poly(1/\epsilon) samples, independent of the values a_1,a_2,a_3; when |S| >= 4, it is possible to learn any S-SICSIRV with poly(1/\epsilon, \log \log a_k) samples; and already when |S|=4, at least \log \log a_k samples may be required for learning.

We thus establish a sharp transition in the complexity of learning S-SICSIRVs when the size of S goes from three to four.
Joint work with Phil Long and Rocco Servedio.

For more information, please contact Bonnie Leung by email at bjleung@caltech.edu.