E-means: Outperforming k-means in one-tenth the epochs

436 points · 54 comments on HN · read original →

Points and comments are a snapshot, not live.

New e-means method beats k-means in 1.2 to 3 epochs versus 25.

Researchers propose e-means, a mini-batch k-means variant using exponential moving average updates with automatic hyperparameter tuning via scaling laws. It reaches loss below Lloyd's 25-epoch baseline in 1.2-3 epochs across datasets from 10k to 10B points, achieving 10-45× wall-clock speedup on GPU and 8-15× on CPU. The method includes cosine-scheduled step decay, dead-cluster revival by splitting large clusters, and specialized GPU kernels. Validation on 24 datasets shows consistent quality improvements and better escape from local minima, with no hyperparameter tuning required.

What commenters are saying

Reception is strongly positive, with several commenters praising the clarity of the visualizations and the automatic hyperparameter laws. The author, Swann Bessa, responds to multiple questions, defending the scaling laws' generalization and clarifying that mini-batch noise helps escape local minima. One commenter tested e-means on a spherical mesh relaxation project and found it inferior there since no dataset exists-each Voronoi cell's centroid is computed directly. Others discuss theoretical links to simulated annealing, expectation maximization, and the importance of keeping centroids within the convex hull. Several ask about practical applications, with one reply noting index build time reductions of 50-80%.