Research map / Bandits and online learning / Multi-armed bandits
BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive bandit sampling instead of exact PAM search | PAM BUILD and SWAP searches · Large real-world datasets | distance computations: up to 200x fewer distance computations | Helped |
| Use BanditPAM instead of the FastPAM1 implementation | k-medoids clustering · MNIST, n = 70,000 | runtime: 4x faster | Helped |
| Use BanditPAM rather than PAM | k-medoids clustering · MNIST subsamples, l2, k=5 | clustering loss ratio to PAM: 1 | No clear effect |
| Re-estimate arm-dependent sigma values at each BUILD or SWAP search (ablation) | BanditPAM · MNIST BUILD steps | computational performance | Helped |
| Apply BanditPAM under the scRNA-PCA projection, where arm means are concentrated and rewards have heavier tails | BanditPAM · scRNA-PCA, l2 | distance-calls-per-iteration scaling: 1.204 | Hurt |
Closest papers by meaning
- BanditPAM++: Faster $k$-medoids Clustering (NeurIPS 2023 · similarity 0.96)
- OneBatchPAM: A Fast and Frugal K-Medoids Algorithm (AAAI 2025 · similarity 0.90)
- Global Optimal K-Medoids Clustering of One Million Samples (NeurIPS 2022 · similarity 0.89)
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.86)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.86)
- Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts (ICLR 2025 · similarity 0.85)
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.