"Density estimation via piecewise polynomial
approximation in sample near-linear time"
Ilias Diakonikolas
(University of Southern California)
Monday, February 29nd, 2016, 2:00 pm
EBU3B, Room 4258
Abstract:
In this talk, I will focus on the problem of density estimation, i.e., how to estimate (learn) a distribution based on random samples. I will describe a sample-optimal and computationally efficient algorithm to learn univariate distributions that are well-approximated by piecewise polynomial density functions. As a corollary of this algorithm, we obtain the first (near-)sample optimal and *near-linear time* density estimators for a wide range of well-studied structured distribution families.
If time permits, I will sketch applications of the underlying algorithmic ideas to other inference tasks (e.g., regression).
(Joint work with J. Acharya, J. Li, and L. Schmidt.)