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