Algebraic and Analytic Approaches for Parameter Learning in Mixture Models

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(N1/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(k2(N/ε)^8/√ε) samples suffice to exactly recover the parameters. For some of these distributions, our results represent the first guarantees for parameter estimation.