Reviews: Nested Mini-Batch K-Means

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 Figure 1 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).