Abstract
This paper presents a novel distributed optimization framework for large-scale clustering by re-envisioning the task as a data compression problem. By demonstrating that the duality gap of this non-convex problem vanishes as the dataset size increases, the author justifies the use of Dantzig-Wolfe decomposition for massive-scale data processing. The proposed method offers improved scalability, faster convergence, and greater numerical stability compared to traditional Expectation-Maximization (EM) approaches.
Introduction
Standard clustering algorithms, particularly the state-of-the-art Expectation-Maximization (EM) for Gaussian Mixture Models, struggle with three major hurdles when applied to modern datasets. First is scalability: they often require the entire dataset to reside in a single machine's memory, which is impossible for terabyte- or petabyte-scale databases. Second is convergence speed: as a first-order optimization method, EM can be agonizingly slow to converge on complex datasets. Finally, numerical stability is a frequent issue; EM often fails or "blows up" when encountering singular covariance matrices—where data lies on a lower-dimensional subspace—or when the number of model components exceeds the actual number of clusters.
This research seeks a method that is mathematically rigorous, distributed by design, and robust against the numerical pitfalls of traditional statistical modeling by framing clustering through the lens of information theory.
Methodology
The paper's approach is built on the principle that optimal clustering should induce optimal data compression. The problem is formulated as maximizing "classification gain," a metric from information theory. For Gaussian distributions, this translates to an objective function involving the entropy of cluster assignments and the log-determinants of cluster covariance matrices.
Distributed Architecture and Decomposition
Clustering is inherently non-convex, which usually prevents the use of powerful decomposition techniques like Dantzig-Wolfe that require zero duality gaps. However, the author provides a theoretical proof using Azuma’s Inequality showing that as the number of samples ($N$) approaches infinity, the duality gap vanishes. This "Large-Scale Paradox"—where the optimization problem becomes easier to solve optimally as it gets larger—justifies the use of linear programming-style decomposition on a non-linear, non-convex problem.
As shown in Figure 1, the system consists of several "database hosts" and one "center processor." Each host performs local computations on its own slice of data and sends only a small amount of summary information (parameters) back to the center, minimizing network traffic and allowing for massive horizontal scaling.
Experimental Results
The paper evaluates the algorithm using synthetic 2D datasets designed to test specific edge cases: overlapping clusters, different means, and singular covariance matrices. While the theory is built for large-scale data, these numerical experiments used 2,048 data samples distributed across two hosts to demonstrate proof-of-concept.
Robustness to Singularity
A key advantage of this method is its handling of singular covariance matrices, a known "killer" for standard EM. By adding a tiny "white noise" term ($\sigma_n^2 I_D$) to the covariance matrices, the algorithm remains numerically stable even when data is perfectly correlated, without significantly degrading clustering accuracy.
In the singular covariance matrix test (Figure 2), the algorithm achieved a misclassification rate of 1.71%. On overlapping clusters (two Gaussians with the same mean but different orientations), the algorithm achieved a rate of 5.32%, and with clusters having different means and structures, it achieved 2.29%.
Discussion and Conclusion
The proposed framework demonstrates that viewing clustering as a compression problem provides a clear information-theoretic objective that avoids many heuristic pitfalls of distance-based clustering. Unlike standard EM, the algorithm did not encounter numerical difficulties or convergence failures when dealing with singular matrices. Furthermore, the fast convergence of the unitary matrices used to diagonalize the problem suggests it reaches solutions in fewer iterations than traditional first-order methods.
Limitations and Future Work
Despite its strengths, the current formulation assumes data follows a mixture of Gaussians. While robust, it may not capture clusters with highly non-linear, manifold-like shapes (e.g., concentric circles). Additionally, while the theory supports large-scale data, future work should involve testing on actual terabyte-scale real-world data and integrating automated model selection to determine the optimal number of clusters ($J$) during the optimization process.
Summary updated