[Colloquium] 2/8 Talks at TTIC: Xiaorui Sun, Columbia

[Mary Marre]

When:     Monday, February 8th at 11:00 am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Who:       Xiaorui Sun, Columbia

Title: Efficient Density Estimation via Piecewise Polynomial Approximation

Abstract:

The problem of density estimation(or distribution learning) is to construct
a
highly accurate hypothesis distribution given i.i.d. samples drawn from an
unknown probability distribution. It is a classic problem in probability
theory
and statistics, and has been studied intensively in theoretical computer
science during the past two decades.

In this talk, I will describe an algorithmic framework for distribution
learning
that yields provably efficient estimators for many natural and well-studied
distribution families. The key tool that enables this approach is a highly
efficient "semi-agnostic" learning algorithm for univariate piecewise
polynomial
distributions. We obtain learning algorithms for distribution families of
interest
by combining our framework and structural results showing that they can be
well approximated using piecewise polynomial distributions.

We apply this framework to obtain a wide range of results for many natural
distributions over both continuous and discrete domains. Our general
techniques
yield computationally efficient algorithms for all these problems, in many
cases
with provably optimal sample complexities (up to logarithmic factors) in all
parameters.

I will also discuss briefly the work in other areas of theoretical computer
science
such as graph isomorphism and algorithmic game theory.


Host: Madhur Tulsiani, madhurt at ttic.edu



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757 <%28773%29%20834-1757>*
*f: (773) 357-6970 <%28773%29%20357-6970>*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160201/1408e027/attachment.htm