Title: Learning Mixture of Gaussians with Streaming Data,
Abstract: 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\sigma$ distant
with $C=\Omega((k\log k)^{1/4}\sigma)$ and where $\sigma^2$ is the maximum
variance of any Gaussian component, we show that asymptotically the algorithm
estimates the centers optimally (up to constants); our center separation
requirement matches the best known result for spherical Gaussians
\citep{vempalawang}. For finite samples, we show that a bias term based on the
initial estimate decreases at $O(1/{\rm poly}(N))$ rate while variance
decreases at nearly optimal rate of $\sigma^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\cdot 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\rightarrow \infty$.