ARC Colloquium: Siu On Chan - Microsoft Research

Event Details
  • Date/Time:
    • Monday November 10, 2014 - Tuesday November 11, 2014
      12:00 pm - 11:59 am
  • Location: Klaus Room 1116 W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:

denton at cc dot gatech dot edu


Summary Sentence: Efficient Density Estimation via Piecewise Polynomial Approximation

Full Summary: No summary paragraph submitted.


Efficient Density Estimation via Piecewise Polynomial Approximation



We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let p be an arbitrary distribution over an interval I which is τ-close (in total variation distance) to an unknown probability distribution q that is defined by an unknown partition of I into t intervals and t unknown degree-d polynomials specifying q over each of the intervals. We give an algorithm that draws O~(t (d+1)/ε^2) samples from p, runs in time poly(t,d,1/ ε), and with high probability outputs a piecewise polynomial hypothesis distribution h that is (O(τ)+ε)-close (in total variation distance) to p. This sample complexity is essentially optimal; we show that even for τ=0, any algorithm that learns an unknown t-piecewise degree-d probability distribution over I to accuracy ε must use Ω(t(d+1)/(polylog(d+1) ε^2)) samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming.


We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of t-modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of k-monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.


Short Bio:

Siu On Chan is a Postdoc at Microsoft Research. He did his undergrad in Chinese University of Hong Kong, MSc at University of Toronto, and PhD at UC Berkeley. He is interested in studying the limitations of approximation algorithms, in terms of NP-hardness and integrality gaps of convex programming hierarchies. He is also interested in random graphs and property testing. He received a Best Paper Award at STOC 2013.

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
No keywords were submitted.
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Nov 3, 2014 - 12:42pm
  • Last Updated: Apr 13, 2017 - 5:21pm