Nested Mini-Batch K-Means
A new algorithm is proposed which accelerates the mini-batch k-means algorithm of Sculley (2010) by using the distance bounding approach of Elkan (2003). We argue that, when incorporating distance bounds into a mini-batch algorithm, already used data should preferentially be reused. To this end we propose using nested mini-batches, whereby data in a mini-batch at iteration t is automatically reused at iteration t + 1. Using nested mini-batches presents two difficulties. The first is that unbalanced use of data can bias estimates, which we resolve by ensuring that each data sample contributes exactly once to centroids. The second is in choosing mini-batch sizes, which we address by balancing premature fine-tuning of centroids with redundancy induced slow-down. Experiments show that the resulting nmbatch algorithm is very effective, often arriving within 1% of the empirical minimum 100× earlier than the standard mini-batch algorithm.
The paper presents an accelerated implementation of mini-batch k-means algorithm, with supported good empirical performance. 
Technical quality:  It seems the nested-batch method is likely to introduce overhead by keeping all previously sampled points in memory, especially since mini-batch k-means is usually run for many iterations? And the computational cost of checking whether a point is already sampled grows as the number of iteration grows as well. How did this not seem to have an effect in your experiments, as comparing to the original mini-batch algorithm?  The experiments in Fig. 2 may be a little misguiding: it shows that nested-mini-batch achieves same level of k-means cost faster than the other compared methods; however, this may only mean that it plateaued faster. As time increases, it's possible that the other algorithms will achieve a lower k-means cost eventually (they reach a plateau with a lower k-means cost). The authors do not discuss whether the experiments reveal this feature of nested-mini-batch k-means.   Novelty:  The paper mostly adapts the idea of distance bounding using triangle inequality (Elkan) to the setting of mini-batch k-means.  Potential impact: This paper may have marginal contribution to the existing mini-batch method.  Clarity and presentation: The paper is well written and the ideas are clearly presented.