acceptodds
Under review as a conference paper at ICLR 2027

-means : Outperforming k-means (in one-tenth the epochs)

Abstract

Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined -means, is much faster than Lloyd k-means and converges to lower losses, even when compared to k-means++. It consistently beats the loss of Lloyd k-means at convergence in 1.2 to 3 epochs, which translates to 10-45 GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, -means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at a tenth of its epochs.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
clustering, kmeans, k-means, exponential, emeans, e-means, means, efficient, scaling law, mini-batch, exponential moving average, vector quantization, nearest neighbor search

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_3xHEOpenReview ↗
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.

1 comment

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.

Reviewer_x2RuOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes e-means, an efficient large-scale clustering algorithm based on exponential moving averages (EMA), to address the high computational cost of traditional K-means and the relatively high final clustering error of Mini-batch K-means. Specifically, the proposed method integrates EMA-based centroid updates, cosine annealing, dead-cluster revival, and final centroid refinement to improve clustering efficiency and quality. Extensive experimental results demonstrate that e-means achieves lower clustering errors with fewer iterations while providing substantial computational speedups.

Critical strengths

This paper addresses the computational efficiency and clustering quality of classical K-means, with a clear research motivation and strong practical relevance. The proposed method features a simple design and effectively improves clustering performance without modifying the original K-means objective function.

Critical weaknesses

1.Although the experimental results demonstrate that e-means achieves lower clustering errors than traditional Lloyd K-means, the paper lacks sufficient theoretical analysis to explain the underlying reasons for this improvement.

2.The proposed scaling laws rely primarily on extensive empirical fitting using a single dataset, and their generalization ability across different data distributions and clustering configurations remains to be further validated.

Questions for authors

1.Could the authors provide an explanation from an optimization or theoretical perspective as to why EMA updates can achieve a lower objective function value than fully converged Lloyd K-means?

2.Could the authors additionally report clustering metrics such as ACC, NMI, or ARI on datasets with ground-truth class labels to further validate the effectiveness of the proposed method in practical clustering tasks?

2 comments

Why e-means reaches lower losses than Lloyd.

Thank you for suggesting that this matter should be discussed in greater detail. We provide two interpretations to explain the lower clustering errors obtained by e-means.

In the first interpretation, we highlight that Lloyd's algorithm is a special case of EMA updates. With batch size B=nB = n (nn being the dataset size) and a constant decay γ=0\gamma = 0, i.e. a step α=1−γ=1\alpha = 1 - \gamma = 1 without the cosine schedule, the EMA updates of Equations (2)–(4) become

Nj←nj,Sj←sj,cj=SjNj=1nj∑x:a(x)=jx,N_j \leftarrow n_j, \qquad S_j \leftarrow s_j, \qquad c_j = \frac{S_j}{N_j} = \frac{1}{n_j} \sum_{x : a(x) = j} x,

where njn_j and sjs_j are the number and the sum of the points currently assigned to cjc_j. Each EMA step is then exactly a Lloyd step, assuming no cosine schedule. Therefore, properly tuned EMA updates cannot be worse than Lloyd. We plotted the loss landscape of EMA updates at convergence depending on BB and γ\gamma in Appendix C.1 (Figure 8): Lloyd is a special case that remains out of the optimal region.

A second interpretation, detailed in Appendix C.2, is that mini-batch updates introduce noise in the optimization which allows to better escape local minima.

It is known that the k-means landscape has many local minima [1, 2], and that finding the global one is NP-hard [3]. Lloyd's algorithm is a greedy descent method: it never increases the loss, so it stops at the first local minimum it reaches [4].

To the best of our knowledge, no theorem directly shows that mini-batch k-means reaches better minima than full-batch k-means in the general case. Convergence results for mini-batch k-means guarantee convergence to a local minimum [4, 5, 6], but not to any particular one.

It is, however, a long-standing observation in optimization that stochastic updates tend to end in better minima than greedy ones, because the noise can move the parameters into another, possibly deeper, basin [7]. For k-means, noise injected into the search and then annealed has been used to escape the local minima: simulated annealing over partitions is shown to converge to a global minimum when cooled slowly enough [8], and annealed random label draws beat k-means in practice, at the price of many more epochs [9].

We can make a parallel between simulated annealing and e-means: its noise comes for free from mini-batch sampling, with the step size acting as a temperature [10], and its cosine schedule anneals this step: the large early steps explore and can carry the centroids out of poor basins, and the small late steps exploit the basin they settle in.

Note that this second argument on stochasticity applies to SGD or Adam as well, which we also found to be able to reach lower losses than Lloyd at convergence (see Appendix F.1, Figure 18). Interestingly, EMA has the additional advantage that it guarantees centroids to always be a weighted average of dataset points, while SGD or Adam can overshoot past the convex hull of dataset points. This makes EMA more stable at large learning rates, which empirically helps for fast convergence (Appendix F.2, Figure 19).

Additional clustering metrics.

We thank the reviewer for suggesting this addition. We had not originally experimented on ACC, NMI or ARI, but found that e-means obtains similar speedups and performance improvements on these metrics as well. We recorded these metrics on the train set, as is typically done in the literature. We experimented on the real and synthetic datasets from our paper which do have labels: two real datasets from the VIBE benchmark, ImageNet-CLIP (labelled with its 1,000 object classes) and CelebA (labelled with its 10,177 identities), and two synthetic Gaussian mixtures detailed in Appendix E.2, a standard one and one with stretched components (both with n=106n = 10^6, k=16,384k = 16{,}384 and d=128d = 128).

We included the full curves depending on the number of epochs in Appendix E.3 (Figure 15). We ran the experiments with k-means++ initialization. Below we report epochs to reach Lloyd’s performance at 25 epochs (100 epochs for ImageNet) for each metric, and the metric value at 25 and 100 epochs for both Lloyd and e-means. ImageNet having a longer convergence time, values for that dataset are reported at 100 epochs.

DatasetMetricEpochs to reach LloydLloyd at 25/100 epochse-means at 25/100 epochs
ImageNet-CLIP (k = 1,000)ACC80.40480.4071
ImageNet-CLIP (k = 1,000)NMI80.66650.6673
ImageNet-CLIP (k = 1,000)ARI80.28200.2837
CelebA (k = 10,177)ACC20.08710.0944
CelebA (k = 10,177)NMI20.66550.6800
CelebA (k = 10,177)ARI20.00750.0096
Gaussian mixture (k = 16,384)ACC10.96330.9708
Gaussian mixture (k = 16,384)NMI10.99640.9974
Gaussian mixture (k = 16,384)ARI20.94810.9674
Stretched mixture (k = 16,384)ACC10.96170.9661
Stretched mixture (k = 16,384)NMI20.99630.9970
Stretched mixture (k = 16,384)ARI20.94760.9607

The results are consistent across all four datasets, and they mirror what we observe on the train and test loss. e-means reaches Lloyd's ACC, NMI and ARI in 1 to 8 epochs, and after 25 epochs (100 for ImageNet-CLIP) it ends above Lloyd run to convergence on every metric and every dataset.

We thank the reviewer for suggesting this addition which allows to generalize the scope of our experimental validation.

References

[1] D. Steinley, "Local optima in K-means clustering: what you don't know may hurt you", Psychological Methods 8(3):294–304, 2003.

[2] W. Qian, Y. Zhang, Y. Chen, "Structures of Spurious Local Minima in k-means", arXiv:2002.06694, 2020.

[3] D. Aloise, A. Deshpande, P. Hansen, P. Popat, "NP-hardness of Euclidean sum-of-squares clustering", Machine Learning 75(2):245–248, 2009.

[4] L. Bottou, Y. Bengio, "Convergence Properties of the K-Means Algorithms", Advances in Neural Information Processing Systems (NIPS), 585–592, 1994.

[5] J. MacQueen, "Some Methods for Classification and Analysis of Multivariate Observations", Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1:281–297, 1967.

[6] C. Tang, C. Monteleoni, "Convergence rate of stochastic k-means", AISTATS, PMLR 54:1495–1503, 2017.

[7] Y. LeCun, L. Bottou, G. B. Orr, K.-R. Müller, "Efficient BackProp", Neural Networks: Tricks of the Trade, LNCS 1524:9–50, Springer, 1998.

[8] S. Z. Selim, K. Alsultan, "A simulated annealing algorithm for the clustering problem", Pattern Recognition 24(10):1003–1008, 1991.

[9] G. Celeux, G. Govaert, "A classification EM algorithm for clustering and two stochastic versions", Computational Statistics & Data Analysis 14(3):315–332, 1992.

[10] T. Heskes, E. T. P. Slijpen, H. J. Kappen, "Cooling schedules for learning in neural networks", Physical Review E 47(6):4457–4464, 1993.

Reviewer_E1KaOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors proposed a novel Exponential Moving-Average (EMA) optimization strategy for mini-batch k-means and its adoption in the proposed "e-means" algorithm. They furthermore proposed scaling laws with which the hyperparameters for the EMA steps can be computed during training. The scaling law was fitted using a huge grid search (75k runs) on the DEEP* dataset and verified on 7 other datasets. The results show improved MAEs and faster convergence.

Critical strengths
  • e-means converges faster AND to a lower MAE than competitors.
  • e-means doesn't have any hyperparameters, but computes the corresponding parameter values during training
Critical weaknesses
  • It's not completely clear if the major improvements came from the novel EMA optimization strategy and the scaling laws OR from the dead-cluster revival strategy.
Questions for authors

Questions:

  • Table 1 suggests that the major improvement comes from the dead clusters revival strategy. Did you perform an in-depth experiment comparison to "Lloyd/FAISS + the novel dead-cluster revival strategy" to see whether the scaling laws or the dead cluster revival are the important novel aspects? I.e., why/how does e-means reach lower MAE than Lloyd and FAISS?

  • Line 198: why is it "guaranteed to decrease the train MSE."?

  • Line 157: you initialize N_j with 1e-10. Are you not running into floating division problems with such a small number when dividing by N_j in Equation (4)? Did you implement some checks against this?

Comments / Minor questions:

Section 3:

  • Please specify the shape of the data points / the dataset (are the points in R^d?).
3 comments

Disentangling EMA and scaling laws from dead-cluster revival.

Thank you for suggesting this ablation.

To isolate the impact of each component, we conducted a 2×2 ablation comparing Lloyd (25 epochs, implemented with Flash K-Means) and e-means (3 epochs), both with and without our dead-cluster revival strategy. To implement Lloyd with dead-cluster revival, we do the following: At the end of each epoch, we compute exact cluster sizes njn_j and apply the exact same splitting criterion used for the EMA counts NjN_j in e-means.

The table below reports the mean test MSE over 10 seeds, alongside relative percentages compared to the standard 25-epoch Lloyd baseline:

Datasetne-means, 3 epochsLloyd, 25 epochse-means, 3 epochsLloyd, 25 epochs
dead cluster revivalyesyesnono
DEEP*1M0.38784 (-0.33%)0.38882 (-0.08%)0.39664 (+1.93%)0.38912 (ref)
DINO10B1M205,463 (-0.31%)205,944 (-0.07%)210,048 (+1.92%)206,097 (ref)
SPACEV1M7,201 (-0.40%)7,224 (-0.08%)7,381 (+2.10%)7,230 (ref)
SimSearchNet++1M113,138 (-0.35%)113,516 (-0.02%)114,673 (+1.00%)113,539 (ref)
DEEP*10M0.34140 (-0.24%)0.34205 (-0.05%)0.35375 (+3.37%)0.34221 (ref)
DINO10B10M188,088 (-0.13%)188,269 (-0.03%)193,836 (+2.92%)188,334 (ref)
SPACEV10M6,352 (-0.38%)6,374 (-0.05%)6,664 (+4.51%)6,377 (ref)
SimSearchNet++10M109,188 (-0.28%)109,448 (-0.05%)113,445 (+3.60%)109,500 (ref)

Both components are necessary, and neither is enough on its own:

  • Revival alone does not explain the gains. Adding revival to Lloyd reduces MSE by less than 0.1%. Full e-means still does clearly better in 3 epochs than Lloyd does in 25. So the convergence advantage requires EMA updates with scaling laws.
  • e-means needs revival. Without it, e-means degrades by +1.00% to +4.51% and falls behind the Lloyd baseline. Because e-means updates on mini-batches, some clusters get starved of points early in training [1], and revival prevents this.

The two components are complementary: EMA optimization drives fast convergence, and revival keeps it stable under mini-batch updates. We have added this full ablation to Appendix C.3 (Table 8). Appendix C.1 and C.2 also give additional insights about why EMA optimization reaches a lower loss.

Why the last-epoch mean is “guaranteed to decrease train MSE”

This relates to the last step of e-means, described in line 11 of Algorithm 1. Each centroid is updated as the exact mean of training points assigned to its cluster. For a fixed assignment of training points to clusters, the optimal centroids are the exact means of each cluster (this is one of Lloyd’s required conditions for optimality [2]). Therefore updating centroids with this exact mean is guaranteed to decrease train MSE.

Note that the training MSE in all our experiments is calculated using these cluster IDs from the last epoch rather than an extra full-dataset re-assignment pass, which we found to yield a worse training MSE at fixed compute. While this was noted in the caption of Table 1, it was missing from the main text. To make this completely clear, we made the following updates to the paper:

  • Algorithm 1 now returns the last-epoch cluster assignments alongside the centroids.
  • In Section 3.2’s “last-epoch-mean” paragraph (lines 193–198), we clarified that the returned training assignments come from the last epoch and explained why updating to their exact means is guaranteed not to increase train MSE.

Risks of numerical issues with Nj=10−10N_j = 10^{-10}

Thank you for raising this question about numerical precision. First, we clarify why 10−1010^{-10} does not cause floating-point division issues for our implementation. As noted in Appendix K.2 (lines 2012–2015), NjN_j, SjS_j, and cjc_j are maintained in FP32 throughout training (dynamic range ≈[1.2×10−38,3.4×1038]\approx [1.2 \times 10^{-38}, 3.4 \times 10^{38}]). Only the nearest-centroid distance computation uses reduced precision. Because the small scale factor in NjN_j and SjS_j cancels out in Equation (4) when computing cj=Sj/Njc_j = S_j / N_j, the centroids cjc_j remain well-scaled and the reduced-precision search is unaffected.

Because NjN_j is initialized strictly positive (10−1010^{-10}) and updated via EMA updates of batch counts, NjN_j tends to increase and stays away from FP32 underflow thresholds. Moreover, any cluster whose EMA count NjN_j decays substantially gets re-initialized by our dead-cluster revival mechanism before underflow can occur.

To validate our claims empirically, we reran the experiments of Table 3 (up to scale 100M, 20 seeds per configuration) at the indicated numbers of epochs and recorded the lowest and highest values of NjN_j and SjS_j (among all coordinates) across all the trainings of e-means.

LowestHighest
NjN_j4.8e-131.7e3
SjS_j (nonzero coordinates)2.1e-202.3e5

We found that the lowest values obtained were 4.8e-13 and 2.1e-20, which is comfortably inside the FP32 range. We thank the reviewer for raising this point, which led us to verify empirically that our default NjN_j value is numerically sound.

Section 3 (Dataset shape): Thank you for pointing this out. The dataset indeed consists of nn vectors in Rd\mathbb{R}^d (X={x1,x2,…,xn}⊂RdX = \lbrace x_1, x_2, \dots, x_n \rbrace \subset \mathbb{R}^d). While this was defined in Section 1 (line 028), we have now also explicitly restated X⊂RdX \subset \mathbb{R}^d at the beginning of Section 3.1 (line 142) and in Algorithm 1 for clarity.

References

[1] P. Dhariwal, H. Jun, C. Payne, J. W. Kim, A. Radford, I. Sutskever, "Jukebox: A Generative Model for Music", arXiv:2005.00341, 2020.

[2] S. P. Lloyd, "Least Squares Quantization in PCM", IEEE Transactions on Information Theory 28(2):129–137, 1982.

Thanks for the clarifications. I raised my score to "clear accept".

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.