NeurIPS 2020

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


Meta Review

Two of the three reviewers support acceptance of this paper, and the reviewers all agree that efficient k-median clustering is an important and useful problem. Reviewers 1 and 5 agree that the algorithm is practical and provides significant speedups over state of the art k-median algorithms. A common concern of the reviewers is that the techniques used to obtain the speedups are not too novel given the work of Bagaria et al. (2018) on efficiently computing the median of a set of points. During the discussion period, the reviewers agreed that the results of the current paper do not immediately follow from the prior work, but that the main strength of the paper is the practicality of the algorithm. Since the proposed algorithm is practical, provides a significantly faster algorithm for PAM clustering, and has a very high quality code submission, I recommend accept. The authors should add the experiments and clarifying comments discussed in the reviews and the author response to the camera ready version of the paper.