Mini-batch $k$-means terminates within $O(d/\epsilon )$ iterations

Gregory Schwartzman

We answer the question: "Does local progress (on batches) imply global progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $k$-means w…