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.