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

Gregory Schwartzman

TL;DR

This paper proves that mini-batch $k$-means, a popular clustering algorithm, can terminate efficiently with an "early stopping" condition. They show that with a sufficiently large batch size, progress on a small batch guarantees progress on the entire dataset, leading to a termination time independent of the dataset size and dependent only on the data dimension and desired accuracy.

What Problem Does This Paper Address?

The $k$-means algorithm is a cornerstone of unsupervised learning, but its standard implementation can be computationally expensive for massive datasets. Mini-batch $k$-means offers a solution by processing data in smaller batches. However, a key theoretical question arises: does "local progress" on a mini-batch translate to "global progress" on the entire dataset, especially when the algorithm uses an "early stopping" criterion (terminating when improvement on a batch falls below a threshold) rather than a fixed number of iterations? This paper tackles this by proving that, under certain conditions, local progress does imply global progress, guaranteeing termination within a predictable number of steps.

Methods

The authors analyze a generic mini-batch $k$-means algorithm with an early stopping condition based on the improvement in the clustering quality on a sampled batch. They first establish a theoretical bound using a large batch size, showing that if the batch size is $\tilde{\Omega}((d/\epsilon)^2)$, the algorithm terminates within $O(d/\epsilon)$ iterations with high probability, irrespective of the initial center positions. This is achieved by demonstrating that a large batch acts as a "sparsifier" for the entire dataset, making batch progress a reliable indicator of global progress.

They then refine this by considering the standard $k$-means update rule and a smaller batch size, $\tilde{\Omega}((d/\epsilon)^2)$. This improvement relies on the stability introduced by the standard update rule, which allows for a more efficient analysis. Finally, they extend their results to the specific early stopping condition used in the popular scikit-learn library, showing its applicability and deriving corresponding bounds.

Datasets

Not discussed in the paper. The analysis is theoretical and relies on a general input dataset $X \subseteq [0, 1]^d$.

Key Insights and Ideas

  • Local Progress Implies Global Progress: The core insight is that for mini-batch $k$-means, with a sufficiently large batch, improvements on a small sample reliably indicate improvements for the entire dataset. This is a crucial theoretical justification for using early stopping in practice.
  • Batch Size is Key: The paper highlights that the size of the mini-batch is the critical factor determining whether local progress translates to global progress. A batch size related to $(d/\epsilon)^2$ is shown to be sufficient.
  • Termination Independent of Dataset Size: Remarkably, the guaranteed termination time $O(d/\epsilon)$ does not depend on the total number of data points ($n$), making it highly scalable for large datasets.
  • Initialization Doesn't Matter (for Termination): The theoretical guarantee on termination time holds regardless of how the initial cluster centers are chosen. This simplifies theoretical analysis and practical implementation.
  • Standard Update Rule Adds Stability: The paper shows that the standard $k$-means update rule (averaging assigned points) provides enough stability to reduce the required batch size compared to a more generic update rule.

Key Results

  • Termination Bound: For a batch size of $\tilde{\Omega}((d/\epsilon)^2)$, mini-batch $k$-means with an early stopping condition (improvement < $\epsilon$) terminates within $O(d/\epsilon)$ iterations with high probability.
  • Approximation Ratio: When combined with the $k$-means++ initialization scheme, the algorithm achieves an approximation ratio of $O(\log k)$, matching the full-batch version.
  • Scikit-learn Applicability: The theoretical results are shown to apply to the mini-batch $k$-means implementation in scikit-learn, though with slightly larger batch size and iteration bounds for its specific stopping condition.

Limitations and Future Work

  • Batch Size Dependency: While the paper provides bounds, the required batch size can still be substantial, particularly for high dimensions or small $\epsilon$. The paper notes that the batch size in Section 3 is about a $kd$ factor larger than in Section 4.
  • Approximation Guarantees: The primary focus is on termination time. While $k$-means++ initialization is discussed for approximation quality, the main theoretical results are about convergence speed, not necessarily reaching the global optimum.
  • Specific Stopping Conditions: The paper analyzes a specific early stopping condition and shows its relevance to scikit-learn's condition. However, other variations of early stopping might require different analyses.
  • Future Work: The paper suggests exploring how to further reduce the batch size requirement and analyzing other variants of mini-batch $k$-means. The applicability to other clustering algorithms or different objective functions could also be a direction.

Summary updated

Abstract

We answer the question: "Does \emph{local} progress (on batches) imply \emph{global} progress (on the entire dataset) for mini-batch $k$-means?". Specifically, we consider mini-batch $k$-means which terminates only when the improvement in the quality of the clustering on the sampled batch is below some threshold. Although at first glance it appears that this algorithm might execute forever, we answer the above question in the affirmative and show that if the batch is of size $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within $O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension of the input, and $\epsilon$ is a threshold parameter for termination. This is true \emph{regardless} of how the centers are initialized. When the algorithm is initialized with the $k$-means++ initialization scheme, it achieves an approximation ratio of $O(\log k)$ (the same as the full-batch version). Finally, we show the applicability of our results to the mini-batch $k$-means algorithm implemented in the scikit-learn (sklearn) python library.
BibTeX
@inproceedings{schwartzman2023mini,
  author = {Gregory Schwartzman},
  title = {{Mini-batch $k$-means terminates within $O(d/\textbackslash\{\}epsilon)$ iterations}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=jREF4bkfi_S},
}
Figure