Research map / Learning theory and algorithms / Combinatorial and search optimization
OneBatchPAM: A Fast and Frugal K-Medoids Algorithm
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OneBatchPAM, a k-medoids local-search that estimates swap objectives with a single random batch of size O(log n), cutting dissimilarity computations to O(n log n) while approximating FasterPAM's solutions.
Problem
Scalable k-medoids clustering: PAM-style local search needs O(n^2) pairwise dissimilarities and memory, which is infeasible for large n with expensive dissimilarities.
Approach
Compute dissimilarities only between all n points and one uniformly drawn batch of size m=O(log n), and use the batch-estimated objective to pick swaps over the full candidate set X_n (not just the batch), with a Hoeffding-based theorem showing the same swaps as FasterPAM w.h.p.; adds debiasing and nearest-neighbor importance weighting.
Key results
- OneBatchPAM-nniw reduces running time to about 15.5% of FasterPAM on small-scale datasets (roughly 7x faster on average) with 1.7% objective penalty relative to FasterPAM.
- On large-scale datasets where FasterPAM and BanditPAM++ fail, OneBatchPAM-nniw achieves the best objective (ΔRO 0.0) while FasterCLARA-5 is about 7x faster but 8.0% worse.
- Debiasing and NNIW give modest gains over uniform sampling (about 0.2% and 1.2% objective improvement respectively), and LWCS degrades performance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use nearest-neighbor importance weighting instead of uniform sampling (ablation) | OneBatchPAM · Small scale | ΔRO (%): above 1.2% over uniform sampling | Helped |
| use nearest-neighbor importance weighting instead of uniform sampling (ablation) | OneBatchPAM · Large scale | ΔRO (%): 1.2 -> 0.0 | Helped |
| set sampled-point self-dissimilarity to infinity (ablation) | OneBatchPAM · Small and large scale | ΔRO (%): 3.9 -> 3.7; 1.2 -> 0.8 | Helped |
| use lightweight coreset sampling instead of uniform sampling (ablation) | OneBatchPAM · Small scale | ΔRO (%): 3.9 -> 12.3 | Hurt |
| use lightweight coreset sampling instead of uniform sampling (ablation) | OneBatchPAM · Large scale | ΔRO (%): 1.2 -> 2.8 | Hurt |
Surprising findings
- The lightweight coreset (LWCS) sampling variant degrades objective quality relative to uniform sampling, which the authors attribute to LWCS being designed for k-means++ rather than PAM.
Limitations
- Theoretical sample size depends on 1/Δ^2 and D^2, so close objectives may require larger batches; the empirical choice m=100 log(kn) is not derived from it.
- Potential overfitting on highly imbalanced datasets where distant points may not be covered by the batch.
- Memory usage is O(n log n), higher than BanditPAM's O(n).
Experimental setup
Datasets: MNIST CIFAR-10 abalone bankruptcy mapping drybean letter dota2 gas covertype
Benchmarks: MNIST CIFAR-10 abalone bankruptcy mapping drybean letter dota2 gas covertype
Metrics: relative objective (ΔRO) relative time (RT)
Baselines: FasterPAM BanditPAM++ FasterCLARA k-means++ kmc2 LS-k-means++ Alternate Random
Builds on: PAM FastPAM FasterPAM CLARA BanditPAM
Closest papers by meaning
- BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits (NeurIPS 2020 · similarity 0.90)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.82)
- k-HyperEdge Medoids for Clustering Ensemble (AAAI 2025 · similarity 0.82)
- Accelerating Matroid Optimization through Fast Imprecise Oracles (NeurIPS 2024 · similarity 0.81)
- Geometric Median (GM) Matching for Robust k-Subset Selection from Noisy Data (ICML 2025 · similarity 0.81)
- Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants (AAAI 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.