[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

REMINDER:

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Tuesday, May 2, 2017
Ryerson 251 @ 3pm

Rocco Servedio
Columbia University
http://www.cs.columbia.edu/~rocco/

Title: Learning Sums of Independent Commonly Supported Integer Random Variables

Abstract:
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 k=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 k >= 4, it is possible to learn any S-SICSIRV with poly(1/\epsilon, \log \log a_k) samples; and * already when k=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 Anindya De and Phil Long.

Host: Prof. Razborov

Refreshments will be served before the talk in Ry 255.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170502/46110f54/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: RoccoS.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 379202 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170502/46110f54/attachment-0001.docx>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170502/46110f54/attachment-0003.html>