On Learning Mixtures of Heavy-Tailed Distributions
- 15 November 2005
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 491-500
- https://doi.org/10.1109/sfcs.2005.56
Abstract
We consider 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; to the best of our knowledge, there were no previous algorithms known with provable learning guarantees for distributions having infinite variance and/or expectation. For Gaussians and log-concave distributions, our results match the best known sufficient separation conditions by D. Achlioptas and F. McSherry (2005) and S. Vempala and G. Wang (2004). Our algorithm requires a sample of size O/spl tilde/(dk), where d is the number of dimensions and k is the number of distributions in the mixture. We also show that for isotropic power-laws, exponential, and Gaussian distributions, our separation condition is optimal up to a constant factor.Keywords
This publication has 5 references indexed in Scilit:
- A spectral algorithm for learning mixture modelsJournal of Computer and System Sciences, 2004
- Learning mixtures of GaussiansPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Spectral analysis of dataPublished by Association for Computing Machinery (ACM) ,2001
- Mixture ModelsNSF-CBMS Regional Conference Series in Probability and Statistics, 1995
- Nearest neighbor pattern classificationIEEE Transactions on Information Theory, 1967