The introduction and general idea behind the paper is written in a way that is easy to understand and logically structured. There are, though, a few places were clarity could be improved. Most of these are around the plot in Fig. 4 which is often referenced as showcasing particular properties, especially in 3.2. This is in part due to the content and meaning of the figure never being fully and completely being introduced, doing so would be beneficial for a figure which appears so central to the paper. Another aspect that would have been nice to see is a comparison of the theoretical results with the practical ones, i.e. it would be interesting to see how loose the bound from Theorem 2.1 is in practice, at least for the datasets used. In the experiments it is mentioned that 1000 runs were performed for every experiment, yet only the average value is reported. While the log scale might make the variance of those values hard to impossible to visualize providing some intuition on the variability in the results would be appreciated.

This paper proposes a randomized method that reduces the number of distance computations needed to identify the medoid of a set. Earlier results are based on reducing the computational problem into a statistical inference problem (multi-armed bandit). This paper is farther extending this technique by exploits the underlying structure of the computational problem. This is done by correlating the samples, i.e., using the same samples to estimate a set of estimators. The authors claim that in many real-world problems this technique is reducing the variance of the estimators which leads to better results. Indeed, the experimental results show a big improvement in comparison with other existing algorithms. In addition, the authors show data dependent theoretical result under the assumption that the estimators are sub-Gaussian. -The paper is really well-written and clearly structured. I have really enjoyed reading it. Especially the introduction and related work sections. They are doing great work describing the novelty, originality, and main ideas of the paper. Moreover, I liked the figures and their locations inside the paper. Well done! -I briefly read the proof of the main theorem (It is inside the supplementary). It appears to be correct. I think that finding assumptions on the distribution of the data or the metric space, which guarantee a small number of distance computations (small H_2) can really strengthen the theoretic part. Moreover, I believe the assumptions of the theorem should be stated clearly inside the theorem (T>=nlogn and the main assumption). -In my opinion, the notion and results introduced in the paper are important. According to the experiments, it seems that the suggested algorithm obtains a big improvement on some interesting data sets. Moreover, I believe that due to the good presentation and the simple ideas of this paper, practitioners and researchers can use this idea in other domains. Edit: I have read the author response. It seems the author understood my comments and is planning to fix what's necessary for the final version. Other comments: - line 115: The footnote notation looks like the notation of the square sign (^2). It confused me and it took me a while to understand this. - typo: equation under line 122: x_2->x_i -Inside the algorithm: T is not defined. Should be written as an input to the algorithm. It took me time to understand that this is the budget. - Table 1: What is the error rate of corrSH? does it missing? - Line 249: What is the middle of the road point? - in my opinion, remark 3 should be inside the main paper. Observation and discussion are important to the reader.

This submission attempts to improve an existing randomized algorithm for estimating the medoid of a set of points using a multi-armed bandit technique by taking advantage of sampling distances using the same reference point. Intuitively, this improved technique makes sense. They show that the assumption that looking at the difference of their random variables improves concentration (Fig 4). Through both theoretical guarantees (The 2.1) and experiments they show the benefits of this sampling technique paired with a suitable multi-armed bandit algorithm. While the idea of correlated sampling is obviously nothing new, this technique has not yet been applied to the medoid problem. The mathematical content is of a relatively high quality. The precision of writing leaves something to be desired. In a number of places there are grammatical errors and the phrasing is somewhat sloppy. This is a minor detail, but giving the manuscript to a proofreader proficient in technical writing would benefit this work. This algorithm is one that is likely to be used in practice for estimating the medoid of a dataset when the cost of an exact solution (O(n^2)) is too expensive. However, I am not fully qualified to judge how often such a situation arises, or the importance of the problem of computing the medoid of a dataset. Including references or specific examples in which this computation is needed would go a long way in motivating the importance of the problem. The first paragraph of the paper simply fails to do so, and lacks any references.