- Rating
- 4
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes e-means, a mini-batch clustering algorithm that combines exponentially weighted centroid updates, a learning-rate schedule, and a cluster revival mechanism. Across diverse embedding datasets and CPU/GPU settings, e-means achieves comparable or better clustering quality with substantially fewer passes over the data. In particular, it matches the test error of Flash-KMeans after 25 passes using only 1.2–3 passes, yielding a 10–45× wall-clock speedup.
Critical strengths
The paper substantially reduces computational cost while preserving or even improving clustering quality. The empirical evaluation covers diverse image and text embeddings, a range of dataset sizes, and both CPU and GPU settings. In the main experiments, e-means matches the test error achieved by Flash-KMeans after 25 passes over the data using only 1.2–3 passes, yielding a 10–45× wall-clock speedup. Separate experiments run to convergence also show lower final error than Lloyd’s algorithm with greedy k-means++ initialization. Achieving such improvements in both efficiency and solution quality for a widely used, computationally expensive primitive is of substantial practical value.
Critical weaknesses
Although the authors argue that Figure 3 sufficiently demonstrates efficiency relative to existing mini-batch methods, I would prefer to see these methods included in the wall-clock comparisons in Figure 4 as well. Figure 3 measures progress in passes over the data, which need not translate directly into running time across different algorithms and implementations. Including these baselines in Figure 4 would therefore provide a more complete assessment of the practical speedup over existing mini-batch methods.
Questions for authors
See Critical Weaknesses.
We thank the reviewer for raising this point and for the positive assessment of our work. While we initially considered including the existing mini-batch baselines (Sculley’s mini-batch k-means and Staleness-reduction) in Figure 4, we chose to keep them in the epoch-based comparisons (Figure 3) to ensure an apples-to-apples evaluation. Because mature, runtime-optimized implementations are not currently available for these methods, comparing their wall-clock times directly against optimized baselines would be unfair to them, as the results would primarily reflect implementation differences rather than algorithmic efficiency. We hope the hardware-agnostic comparison in Figure 3 clarifies their relative performance, showing that while they achieve lower loss than Lloyd’s algorithm at low epoch counts, they ultimately converge to higher losses than the other methods.