Learning Mixture of Gaussians with Streaming Data
In this paper, we study the problem of learning a mixture of Gaussians with streaming data: given a stream of N points in d dimensions generated by an unknown mixture of k spherical Gaussians, the goal is to estimate the model parameters using a single pass over the data stream. We analyze a streaming version of the popular Lloyd's heuristic and show that the algorithm estimates all the unknown centers of the component Gaussians accurately if they are sufficiently separated. Assuming each pair of centers are Cσ distant with C = Ω((k log k) 1/4 σ) and where σ 2 is the maximum variance of any Gaussian component, we show that asymptotically the algorithm estimates the centers optimally (up to certain constants); our center separation requirement matches the best known result for spherical Gaussians [18]. For finite samples, we show that a bias term based on the initial estimate decreases at O(1/poly(N )) rate while variance decreases at nearly optimal rate of σ 2 d/N . Our analysis requires seeding the algorithm with a good initial estimate of the true cluster centers for which we provide an online PCA based clustering algorithm. Indeed, the asymptotic per-step time complexity of our algorithm is the optimal d · k while space complexity of our algorithm is O(dk log k). In addition to the bias and variance terms which tend to 0, the hard-thresholding based updates of streaming Lloyd's algorithm is agnostic to the data distribution and hence incurs an approximation error that cannot be avoided. However, by using a streaming version of the classical (soft-thresholding-based) EM method that exploits the Gaussian distribution explicitly, we show that for a mixture of two Gaussians the true means can be estimated consistently, with estimation error decreasing at nearly optimal rate, and tending to 0 for N → ∞.
This paper proposes a LLoyd type method with PCA initialization to estimate means of Gaussians in a streaming setting. References seem to be severely lacking as the domain is wide. The key point of the algorithm seems to be the initialization and there is no discussion on this part (comparison with the literature on k-means initialization). While the technical results might be interesting I have difficulties commenting on them without the proper background on the subject. I find as well that the technical exposition of proofs is not very clear (notations, chaining of arguments). 
Other concerns
1. Line 116 : What about the estimation of variance and weights? 
2. Algorithm 1 : How do you know N in a streaming setting?
3. Theorem 1 : The error bound assumes that estimated centers ans true centers are matched. The bound is a k-means type bound. Hence, the title of the paper is misleading as it should talk about k-means clustering of Gaussian mixtures.  The estimation of sigma is vaguely discussed in Section 6.
4. Section 6 looks like a very partial result with no appropriate discussion on why it is interesting.