Learning Mixture of Univariate Gaussians There are many papers on learning mixtures of multivariate Gaussians, which exploit various separation/projection techniques. What about one-dimensional (univariate) Gaussians -- any formal guarantees for learning these?

UPDATE: I should clarify: I am particularly interested in polynomial-time algorithms, in the number of mixture components.
Sorry, but there is lots of evidence that not only is this problem a pain in the univariate case, but moreover that having few dimensions actually makes things worse.

For evidence of the difficulty, please see Proposition 15 in Section 6 ("Exponential dependence on $k$ is inevitable") and the related Figure 1 of the following paper, the follow-up to Ankur Moitra and Greg Valiant's original joint work with Adam Kalai:


  Ankur Moitra and Greg Valiant, "Settling the Polynomial Learnability of Mixtures of Gaussians", FOCS 2010.


Proposition 15 states that there exist two mixtures of $k^2$ Gaussians on the line whose $L^1$ distance is exponentially small in $k$.  Since the construction is careful and the distribution parameters are well-behaved (polynomially-sized), this dependence on $k$ is real, and thus any algorithm whose performance depends on statistical distance will run into trouble.  

For evidence that few dimensions actually forms a bad regime, please see the following very recent work:


  Daniel Hsu and Sham Kakade, "Learning mixtures of spherical Gaussians: moment methods and spectral decompositions", ITCS 2013.


This work presents a spectral method for recovering spherical mixtures of Gaussians.  So far, so good: univariate Gaussians are spherical.  However, this algorithm requires the $k$ individual means to span a rank-$k$ subspace (and the performance depends on the condition number of these points, meaning you can't just perturb your univariate instance in a $k$-dimensional space and then closely recover your original Gaussians).  As such, you could view their circumvention of the Moitra-Valiant lower bound as coming from an increase in dimension (and of course by maintaining the speherical nature you find from 1-d).

The above two papers have lots of excellent discussion, techniques, nice references.  This is not my field and I can only offer a very surface intuition for what is going on.  In the univariate case, things are really crowded, so the contribution of different Gaussians is confused and it's hard to disentangle them.  In the high-dimensional case, basically everything is far apart and low density; it's hard to get crowded, and easy to pick out points of high density (which now must reside near means).

I only have one other thing to point out, and that's the connection to $k$-means.  $k$-means has a DP in the 1-d case; google tells me it's from the 40s, and while I haven't seen that reference, we can cook up a DP fairly easily:  make your table have size $n\times k$, where $n$ is the number of points, and use "optimal $k$-means cost using $j\leq k$ means and the first $m\leq n$ data points" as your subproblem, noting that each mean owns a contiguous subset of the data.  As I tried just now to adjust this to the Gaussians case, it was interesting to see how the differences between these two scenarios became acute.  First, the hard vs. soft clustering aspect means we can't just knock out contiguous subsets and claim they are owned by some Gaussian (furthermore, for univariate Gaussians of differing variances, the regions where one or the other dominates aren't just two intervals..).  Second, we have no relationship between the variances, the univariate assumption really doesn't help us there (it would seem we need more; and of course, $k$-means is like knowing a fixed (common) variance up front).

So, oh well.