The 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. 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.