Algebraic and Analytic Approaches for Parameter Learning in Mixture Models
This work addresses the problem of exact parameter estimation for mixture models in statistics and machine learning, offering new guarantees for specific distributions, though it is incremental in building on existing methods.
The paper tackles parameter learning in one-dimensional mixture models by presenting two approaches: a complex-analytic method for Gaussian, binomial, and Poisson mixtures, and an algebraic-combinatorial method for binomial and geometric mixtures, with results such as exp(O(N^{1/3})) samples for Poisson mixtures and O(k^2(N/ε)^{8/√ε}) samples for binomial mixtures.
We present two different approaches for parameter learning in several mixture models in one dimension. Our first approach uses complex-analytic methods and applies to Gaussian mixtures with shared variance, binomial mixtures with shared success probability, and Poisson mixtures, among others. An example result is that $\exp(O(N^{1/3}))$ samples suffice to exactly learn a mixture of $k<N$ Poisson distributions, each with integral rate parameters bounded by $N$. Our second approach uses algebraic and combinatorial tools and applies to binomial mixtures with shared trial parameter $N$ and differing success parameters, as well as to mixtures of geometric distributions. Again, as an example, for binomial mixtures with $k$ components and success parameters discretized to resolution $ε$, $O(k^2(N/ε)^{8/\sqrtε})$ samples suffice to exactly recover the parameters. For some of these distributions, our results represent the first guarantees for parameter estimation.