Learning Mixture of Gaussians with Streaming Data
This work addresses the challenge of efficient parameter estimation for Gaussian mixtures in streaming settings, which is incremental as it adapts existing methods like Lloyd's and EM to online scenarios with theoretical guarantees.
The paper tackles the problem of learning a mixture of Gaussians from streaming data by analyzing a streaming version of Lloyd's heuristic, showing that it accurately estimates cluster centers under sufficient separation conditions, with asymptotic optimality and finite-sample error rates such as variance decreasing at nearly optimal σ²d/N. It also introduces an online PCA-based seeding method and compares to a streaming EM variant for two Gaussians, achieving consistent estimation with error tending to zero as sample size increases.
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 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 $σ^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$.