---
title: "Caltech's DRKM++ Beats K-Means on Outlier Detection With 10x Faster Speed"
subtitle: "Researchers at Caltech and MIT propose a worst-case reformulation of K-means that stays stable under outliers, noise, and tiny datasets."
url: "https://alphasignal.ai/news/caltech-s-drkm-beats-k-means-on-outlier-detection-with-10x-faster-speed"
author: "AlphaSignal Newsroom"
author_url: "https://alphasignal.ai/editorial-team"
company: "AlphaSignal"
company_url: "https://alphasignal.ai/company/alphasignal"
published: "2026-04-13T00:00:00.000Z"
updated: "2026-08-24T03:20:46.086Z"
type: "Paper"
topics:
  - "Data"
  - "Benchmarks"
subtopics:
  - "Data Curation"
  - "Datasets"
upvotes: 1700
source_url: "https://arxiv.org/abs/2604.11118"
comments: 0
truncated: true
---

# 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.

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](https://arxiv.org/abs/2604.11118), 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.

_Preview only. Full text requires an AlphaSignal Pro account._

## Sources

- [Distributionally Robust K-Means Clustering (arXiv abstract)](https://arxiv.org/abs/2604.11118)
- [Distributionally Robust K-Means Clustering (arXiv HTML)](https://arxiv.org/html/2604.11118)
- [Distributionally Robust K-Means Clustering (PDF)](https://arxiv.org/pdf/2604.11118)