CS 789 THEORY SEMINAR [home]

Speaker:   Mark Sandler
Date:         April 18, 2005
Title:          On learning mixtures of heavy tailed distributions
 

Abstract:

We will talk about the problem of learning mixtures of arbitrary symmetric distributions. We formulate sufficient separation conditions and present a learning algorithm with provable guarantees for mixtures of distributions that satisfy these separation conditions.  Our bounds are independent of the variances of the distributions, and to the best of our knowledge, the presented algorithm is the first with provable learning guarantees for distributions with infinite variance and/or expectation. The same algorithm matches the best known separation bounds for Gaussians and log-concave distributions.

Our algorithm requires a sample of size O(dk), where d is the number of dimensions and k is the number of distributions in the mixture.

We will also show that for isotropic power-laws, exponential, and Gaussian distributions, our separation condition is optimal up to the constant factor.

This is a joint work with Anirban Dasgupta, John Hopcroft and Jon Kleinberg