Search papers, labs, and topics across Lattice.
This paper introduces a distributionally robust k-means clustering algorithm that mitigates the brittleness of standard k-means to outliers and distribution shifts by formulating a minimax optimization problem where the population distribution lies within a Wasserstein-2 ball around the empirical distribution. The dual of this minimax problem leads to a soft-clustering scheme with smoothly weighted assignments. The authors propose a block coordinate descent algorithm with provable convergence guarantees and demonstrate improved outlier detection and robustness on benchmark datasets.
K-means, meet your match: a distributionally robust upgrade that laughs in the face of outliers and distribution shifts.
K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.
MIT CSAIL