Skip to main content
AI Socratic

e-means: outperforming k-means (in one-tenth the epochs)

e-means: outperforming k-means (in one-tenth the epochs)

Researchers at FAIR at Meta and École Nationale des Ponts et Chaussées have published e-means, a replacement for Lloyd's k-means, the standard clustering algorithm behind much of retrieval, quantization and data curation. Instead of recomputing every centroid from the full dataset each epoch, e-means updates centroids with an exponential moving average over mini-batches, using the optimization machinery of deep learning.

The authors report that across a wide range of embedding datasets it beats the loss Lloyd's k-means reaches at 25 epochs in 1.4 to 2.6 epochs, which they say translates to 10 to 45 times less GPU wall-clock time than state-of-the-art k-means implementations, and that it frequently converges to a lower loss than k-means++. They also derive scaling laws for how decay rate and batch size affect the final result, which gives a formula for setting both without a hyperparameter sweep.

At the largest scale tested, e-means partitions DINO10B, 10 billion DINO embeddings, into 16 million clusters in 2.5 epochs, ending below the loss of Lloyd's at 25. The code is released in Faiss.

Sources

arXiv paper