Show simple item record

dc.contributor.authorBelkin, Mikhail
dc.contributor.authorSinha, Kaushik
dc.identifier.citationBelkin, Mikhail; Sinha, Kaushik. 2015. Polynomial learning of distribution families. SIAM Journal on Computing, vol. 44:no. 4:pp 889-911en_US
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractThe question of polynomial learnability of probability distributions, particularly Gaussian mixture distributions, has recently received significant attention in theoretical computer science and machine learning. However, despite major progress, the general question of polynomial learnability of Gaussian mixture distributions still remained open. The current work resolves the question of polynomial learnability for Gaussian mixtures in high dimension with an arbitrary fixed number of components. Specifically, we show that parameters of a Gaussian distribution with a fixed number of components can be learned using a sample whose size is polynomial in dimension and all other parameters. The result on learning Gaussian mixtures relies on an analysis of distributions belonging to what we call polynomial families in low dimension. These families are characterized by their moments being polynomial in parameters and include almost all common probability distributions as well as their mixtures and products. Using tools from real algebraic geometry, we show that parameters of any distribution belonging to such a family can be learned in polynomial time and using a polynomial number of sample points. The result on learning polynomial families is quite general and is of independent interest. To estimate parameters of a Gaussian mixture distribution in high dimensions, we provide a deterministic algorithm for dimensionality reduction. This allows us to reduce learning a high-dimensional mixture to a polynomial number of parameter estimations in low dimension. Combining this reduction with the results on polynomial families yields our result on learning arbitrary Gaussian mixtures in high dimensions.en_US
dc.description.sponsorshipThis work was partially supported by NSF grants 0643916 and 1117707.en_US
dc.publisherSociety for Industrial and Applied Mathematicsen_US
dc.relation.ispartofseriesSIAM Journal on Computing;v.44:no.4
dc.subjectGaussian mixture modelsen_US
dc.subjectStatistical inferenceen_US
dc.subjectLearning theoryen_US
dc.subjectSemialgebraic geometryen_US
dc.titlePolynomial learning of distribution familiesen_US
dc.rights.holder© 2015, Society for Industrial and Applied Mathematicsen_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record