What is most impressive about this excellent work is not just the staggering time savings but the robustness of the technique in its assignment of single centroids where legacy may create two due to artefacting or worse one centroid for two blobs. Their explanation that: mini-batches provide more noisy updates that are more likely to explore the optimization landscape and escape local minima makes perfect sense and just goes to show it is all not settled hash. Incredible work with real world benefits of real marginal utility.