Caltech's DRKM++ Beats K-Means on Outlier Detection With 10x Faster Speed
Researchers at Caltech and MIT propose a worst-case reformulation of K-means that stays stable under outliers, noise, and tiny datasets.
PRO- Caltech and MIT researchers propose a distributionally robust K-means variant using a Wasserstein-2 ball.
- The minimax formulation yields soft, weighted assignments instead of hard nearest-neighbor ones.
- A block coordinate descent algorithm has provable monotonic decrease and local linear convergence.
- Perfect outlier recall on MNIST and NIPS in low-data regimes with corrupted points.
- On Fashion-MNIST at N=2000 with 40% noise, average accuracy of 0.84 vs 0.63 for k-means++.
- No public code release yet; algorithm and closed-form updates are fully specified in the paper.
A group of researchers has taken one of the oldest workhorses of unsupervised learning and given it a robustness upgrade grounded in optimal transport. In Distributionally Robust K-Means Clustering, Vikrant Malik and Babak Hassibi (Caltech), together with Taylan Kargin (now at MIT), reformulate the classic algorithm as a minimax problem over a Wasserstein ball of plausible data distributions, and show the resulting method holds up in the exact regimes where standard K-means falls apart.
Why plain K-means keeps breaking
K-means is a staple of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. The reason is baked into the objective: standard K-means minimizes the average squared distance to the nearest centroid on the empirical distribution of your data. When you only have a few samples, or when a handful of points have been corrupted, that empirical distribution is a poor proxy for the true one, and the centroids drift toward the noise.
The authors frame this as a distribution-shift problem. They posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution, and seek cluster centers that minimize the worst-case expected squared distance over this ambiguity set. In plain terms: rather than trusting your dataset exactly, you hedge against every distribution within a bounded transport cost of it, and pick centroids that do well in the worst case.
From hard assignments to soft ones, for free
Solving that minimax directly would require optimizing over an infinite-dimensional space of probability measures. The clever part is that a tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. Each data point gets a probability vector over the K centroids rather than being locked to its nearest one, and a dual parameter (called gamma in the paper) controls how sharp that assignment is.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
