Algorithms & Randomness Center (ARC)
Alon Orlitsky - University of CA, San Diego
Monday, April 18, 20116
Klaus 1116 West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
Learning and Forecasting over Large Domains: The Art of the Doable
Abstract:
Learning a distribution and forecasting its outcomes are important tasks whose complexity increases with the distribution's support size. We consider useful and natural formulations of these two tasks that allow them to be performed with a sample whose size is fixed and independent of the distribution or its support size.
Learning a distribution to a given KL divergence requires a sample size that increases linearly with the support size. We show that with n samples, the distribution can be learned to a KL divergence that is at most 1/sqrt(n) higher than that achievable by any estimator, even one that knows the distribution up to permutation.
Estimating a distribution's support size may require an unbounded number samples. Yet we show that with n samples, we can estimate the number of hitherto unseen elements that will be observed in up to n*log(n) new samples, thereby estimating the effective support of a much larger sample.
Joint work with Ananda Theertha Suresh and Yihong Wu.
Bio:
Alon Orlitsky received B.Sc. degrees in Mathematics and Electrical Engineering from Ben Gurion University in 1980 and 1981, and M.Sc. and Ph.D. degrees in Electrical Engineering from Stanford University in 1982 and 1986.
From 1986 to 1996 he was with the Communications Analysis Research Department of Bell Laboratories. He spent the following year as a quantitative analyst at D.E. Shaw and Company, an investment firm in New York City. In 1997 he joined the University of California San Diego, where he is currently a professor of Electrical and Computer Engineering and of Computer Science and Engineering. His research concerns information theory, statistical modeling, and machine learning.
From 2011 to 2014 Alon directed UCSD's Center for Wireless Communications, and since 2006 he has directed the Information Theory and Applications Center. He is currently the president of the Information Theory Society. He has co-organized numerous programs on information theory, machine learning, and statistics, including the Information Theory and Applications Workshop that he started in 2006 and has helped organize since.
Alon is a recipient of the 1981 ITT International Fellowship and the 1992 IEEE W.R.G. Baker Paper Award, and co-recipient of the 2006 Information Theory Society Paper Award and the 2016 NIPS Paper Award. He is a fellow of the IEEE, and holds the Qualcomm Chair for Information Theory and its Applications at UCSD.
URL: http://alon.ucsd.edu/
Host: Vijay Vazirani (vazirani@cc.gatech.edu)
