# ProtoBandit: Efficient Prototype Selection via Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2210.01860 · HTML: https://mlsanity.com/paper/2210.01860/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 45 references that are in the map.
- First posted on arXiv 4 Oct 2022.

## Builds on (most cited first, 11 of 11)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Representer Point Selection for Explaining Deep Neural Networks](https://mlsanity.com/paper/1811.09720/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [The Bayesian Case Model: A Generative Approach for Case-Based Reasoning and Prototype Classification](https://mlsanity.com/paper/1503.01161/) (2015)
- [Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/1810.05691/) (2018)
- [Fast Distributed Bandits for Online Recommendation Systems](https://mlsanity.com/paper/2007.08061/) (2020)
- [PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1901.08386/) (2019)
- [SPOT: A framework for selection of prototypes using optimal transport](https://mlsanity.com/paper/2103.10159/) (2021)
- [An Optimal Elimination Algorithm for Learning a Best Arm](https://mlsanity.com/paper/2006.11647/) (2020)
- [BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits](https://mlsanity.com/paper/2006.06856/) (2020)

## Abstract (arXiv)

In this work, we propose a multi-armed bandit-based framework for identifying a compact set of informative data instances (i.e., the prototypes) from a source dataset S that best represents a given target set T. Prototypical examples of a given dataset offer interpretable insights into the underlying data distribution and assist in example-based reasoning, thereby influencing every sphere of human decision-making. Current state-of-the-art prototype selection approaches require O(|S||T|) similarity comparisons between source and target data points, which becomes prohibitively expensive for large-scale settings. We propose to mitigate this limitation by employing stochastic greedy search in the space of prototypical examples and multi-armed bandits for reducing the number of similarity comparisons. Our randomized algorithm, ProtoBandit, identifies a set of k prototypes incurring O(k3|S|) similarity comparisons, which is independent of the size of the target set. An interesting outcome of our analysis is for the k-medoids clustering problem T = S setting) in which we show that our algorithm ProtoBandit approximates the BUILD step solution of the partitioning around medoids (PAM) method in O(k3|S|) complexity. Empirically, we observe that ProtoBandit reduces the number of similarity computation calls by several orders of magnitudes (100-1000 times) while obtaining solutions similar in quality to those from state-of-the-art approaches.