BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits

Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris Piech, Ilan Shomorony

TL;DR

BanditPAM is a novel randomized algorithm that reduces the time complexity of $k$-medoids clustering from $O(n^2)$ to $O(n \log n)$ per iteration. By framing the search for cluster centers as a multi-armed bandit problem, it adaptively samples distance computations to match the exact clustering quality of state-of-the-art methods but runs significantly faster. This breakthrough enables interpretable clustering on massive datasets with complex distance metrics.

The Challenge of $k$-Medoids Clustering

While $k$-means is the go-to clustering algorithm for many data scientists, it has two major drawbacks: it relies strictly on squared Euclidean distances, and it creates artificial cluster centers (means) that might not represent real data points. This is highly problematic for structured data like text, graphs, or code, where a "mean" object doesn't physically make sense.

$k$-medoids solves this by ensuring cluster centers (medoids) are actual data points from the dataset and by allowing arbitrary distance metrics (like tree edit distance or cosine similarity). However, the industry-standard $k$-medoids algorithm, Partitioning Around Medoids (PAM), scales quadratically ($O(n^2)$) with the dataset size in each iteration. This makes it prohibitively slow for large datasets, especially when computing the distance metric itself is computationally expensive.

BanditPAM: A Multi-Armed Bandit Approach

The authors introduce BanditPAM, which reimagines the deterministic BUILD and SWAP steps of the PAM algorithm as a statistical estimation problem. Specifically, they map it to the "best-arm identification" problem from the multi-armed bandits (MAB) literature.

Instead of computing the exact distance from a candidate medoid to every other point in the dataset to find the best cluster center, BanditPAM adaptively samples reference points. Each candidate medoid is treated as an "arm," and "pulling an arm" corresponds to computing the distance to a randomly sampled data point.

Using a combination of Upper Confidence Bound (UCB) and successive elimination, the algorithm quickly discards poor candidate medoids and focuses its computational budget on the most promising ones. Promising candidates get evaluated on more reference points to increase estimation accuracy, while bad candidates are dropped early without wasting expensive distance computations.

Key Insights

  • Clustering as a Bandit Problem: The core realization is that finding the best medoid doesn't require exact loss calculations across the entire dataset. It can be treated as finding the arm with the highest expected reward, allowing the use of highly optimized MAB algorithms to skip unnecessary math.
  • Adaptive Confidence Intervals: BanditPAM estimates the variance of distances for each candidate dynamically. This allows it to shrink confidence intervals faster for candidates with highly concentrated distances, speeding up the elimination of suboptimal points.
  • Exact Results via Approximation: Despite being a randomized algorithm, BanditPAM is mathematically proven to return the exact same cluster assignments as the deterministic PAM algorithm with high probability. It offers a rare "free lunch" in optimization: massive speedups without sacrificing output quality.

Datasets and Validation

The authors validated BanditPAM on three diverse, real-world datasets:

  • MNIST: 70,000 handwritten digit images (evaluated using $l_2$ and cosine distances).
  • 10x Genomics scRNA-seq: 40,000 cells and 10,170 genes (evaluated using $l_1$ distance, standard for single-cell RNA sequencing).
  • Code.org HOC4: 3,360 unique student solutions to a programming exercise, represented as abstract syntax trees (evaluated using the computationally heavy tree edit distance).

Key Results

BanditPAM demonstrates remarkable improvements in both theoretical complexity and empirical performance:

  • Quality: Consistently matches the exact clustering loss of PAM across all tested datasets, significantly outperforming other randomized heuristics like CLARANS or Voronoi Iteration, which sacrifice clustering quality for speed.
Final loss normalized to PAM on MNIST
  • Theoretical Speedup: Proven reduction in algorithmic complexity from $O(n^2)$ to $O(n \log n)$ per iteration.
  • Empirical Efficiency: Performs up to 200x fewer distance computations compared to standard PAM. The scaling is almost linear, avoiding the quadratic explosion seen in previous methods.
Scaling of distance computations on HOC4 dataset
  • Wall-Clock Speed: Up to 4x faster than FastPAM1 (the previous state-of-the-art) on the full MNIST dataset, even without FastPAM1's memory-heavy $O(n^2)$ distance caching.

Limitations and Future Work

  • Distributional Assumptions: The theoretical guarantees rely on the assumption that the distance distributions (the "rewards" of the bandit arms) are sub-Gaussian. While this holds empirically in their tests, it may not be strictly true for all conceivable datasets.
  • Iteration Limits: The mathematical proof assumes a hard constraint on the maximum number of SWAP iterations allowed, though the authors note this is standard practice and usually scales linearly with the number of clusters ($k$).
  • Dimensionality Scaling: The current complexity scales linearly with the data dimensionality $d$ ($O(dn \log n)$). The authors suggest future work could improve this scaling, potentially by applying similar bandit techniques to coordinate-wise distance evaluations to avoid computing full high-dimensional distances.

Summary updated

Abstract

Clustering is a ubiquitous task in data science. Compared to the commonly used k-means clustering, k-medoids clustering requires the cluster centers to be actual data points and supports arbitrary distance metrics, which permits greater interpretability and the clustering of structured objects. Current state-of-the-art k-medoids clustering algorithms, such as Partitioning Around Medoids (PAM), are iterative and are quadratic in the dataset size n for each iteration, being prohibitively expensive for large datasets. We propose BanditPAM, a randomized algorithm inspired by techniques from multi-armed bandits, that reduces the complexity of each PAM iteration from O(n^2) to O(nlogn) and returns the same results with high probability, under assumptions on the data that often hold in practice. As such, BanditPAM matches state-of-the-art clustering loss while reaching solutions much faster. We empirically validate our results on several large real-world datasets, including a coding exercise submissions dataset from Code.org, the 10x Genomics 68k PBMC single-cell RNA sequencing dataset, and the MNIST handwritten digits dataset. In these experiments, we observe that BanditPAM returns the same results as state-of-the-art PAM-like algorithms up to 4x faster while performing up to 200x fewer distance computations. The improvements demonstrated by BanditPAM enable k-medoids clustering on a wide range of applications, including identifying cell types in large-scale single-cell data and providing scalable feedback for students learning computer science online. We also release highly optimized Python and C++ implementations of our algorithm.
BibTeX
@inproceedings{tiwari2020banditpam,
  author = {Mo Tiwari and Martin Jinye Zhang and James Mayclin and Sebastian Thrun and Chris Piech and Ilan Shomorony},
  title = {{BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=LKAhTGcGYA},
}
Figure