Meta Rewrites K-Means: Training Rounds Cut by 90% | K-Means | e-means | Meta FAIR | Clustering Al...

Original Media · 14m · 中文 · YouTube · Best Partners TV

TLDR

Meta's FAIR team introduced e-means, a K-Means variant that replaces the centroid update rule with exponential moving averages (EMA), reducing required epochs to ~1/10th and achieving up to 45.5x speedup on billion-scale vectors while matching or beating Lloyd's algorithm in error. The method automates hyperparameter selection via power-law formulas fitted on one dataset but transferable to others, and includes practical engineering like fused kernels and dead-cluster revival.

For you

PRO members can sign in and request more information — or their own version of this digest, tuned to what they care about.

Sign in to unlock

Surprising Insights

•

The classic Lloyd algorithm's monotonic error decrease actually traps it in bad local optima, while the noise from mini-batch updates lets e-means correct course.

•

Power-law hyperparameter formulas fitted on a single dataset (DEEP) transfer to diverse image and text datasets with near-optimal performance, despite unknown intrinsic dimensionality.

•

e-means achieves lower error than Lloyd even with random initialization and no k-means++, because k-means++ is serial and too costly at scale.

Key takeaways

•

e-means keeps the classic K-Means objective but changes the centroid update to EMA on per-cluster counts and sums, letting centroids adapt quickly early on and stabilize later without accumulating stale statistics.

•

The EMA decay rate is scheduled via cosine annealing, and a final recomputation of centroids from the last epoch's assignments yields zero-cost error reduction; an optional slower EMA can improve generalization to new data.

•

Dead clusters are revived every five batches by splitting the largest cluster, which ablation shows is critical: without it, 26% of clusters get fewer than 10 points; with it, only 0.3%.

•

Stochastic mini-batch updates help e-means escape poor local optima: on imbalanced two-cluster data, Lloyd gets stuck 26% of the time vs. 3.5% for e-means; on five linear clusters, 46% vs. 0%.

•

Hyperparameters (batch size, learning rate) are predicted by power-law formulas fitted on 75k runs on the DEEP dataset, transferring to SIFT, SPACEV, and text vectors with median error increase of only 0.19% over per-dataset tuning.

•

On 10 billion DINO vectors (16.77M clusters), e-means reaches Flash-KMeans' 25-epoch error in 2.5 epochs (779 GPU hours on 32 machines) vs. 6,784 GPU hours (64 machines) for Lloyd, with lower final error.

•

Engineering optimizations—block-wise centroid processing, fused distance/assignment kernels, low-precision (BF16/FP8/INT8) assignment, and IVF approximation for huge cluster counts—multiply the algorithmic speedup.

Notable quotes

“K-Means 大概是机器学习里最不起眼的算法了”

▸ Notable quotes · 0:03

“目标函数一个字没动,只是重写了聚类中心的更新方式,就将达到同等聚类质量需要的训练轮次压到了原来的十分之一左右”

▸ Notable quotes · 0:24

“在 10 亿条向量的实验里,实际耗时快了 45.5 倍”

▸ Notable quotes · 0:34

“它把 K-Means 的更新当成了一种硬分配的 EM,只是统计量带了衰减”

▸ Notable quotes · 3:30

“调参也被省掉了”

▸ Notable quotes · 7:04

“少一轮是算法层面的事,而少一次显存读写是系统层面的事,两个叠加才有了最后那个数字”

▸ Notable quotes · 11:12

Chapters

•

0:00 — Introduction and Motivation: Host introduces K-Means as an old but ubiquitous algorithm; Meta FAIR's e-means rewrites the centroid update to achieve 10x fewer epochs and 45.5x speedup on 1B vectors.

•

1:01 — Classic Lloyd Algorithm and Its Bottleneck: Explains Lloyd's two-step loop (assign, recompute mean) and its linear cost per epoch; Faiss defaults to 25 epochs, costing thousands of GPU hours at 10B scale.

•

2:03 — Mini-Batch K-Means and Its Unsolved Problems: Reviews mini-batch history (MacQueen, Sculley) and its issues: accumulated stale statistics, higher final error, and manual tuning of batch size and learning rate per dataset.

•

3:00 — e-means: EMA-Based Centroid Updates: Describes e-means' EMA on per-cluster counts and sums, decay scheduling, connection to hard-assignment EM, and advantages over SGD (centroids stay in convex hull).

•

4:26 — Escaping Local Optima and Reviving Dead Clusters: Shows e-means' stochasticity escapes bad local optima (Lloyd 26% vs 3.5% failure on imbalanced clusters) and details the dead-cluster revival mechanism that splits large clusters.

•

6:18 — Training Stabilization and Final Polish: Covers random init with tiny weight, cosine annealing, zero-cost final centroid recomputation, and optional slower EMA for generalization.

•

7:04 — Automated Hyperparameter Selection via Power Laws: Authors fit power laws for batch size and learning rate from 75k experiments on DEEP; formulas transfer to other datasets with median 0.19% error increase.

•

8:52 — Large-Scale Experiments and Retrieval Impact: Reports 9.5–45.5x speedup on 1M–10B vectors, lower error than Lloyd and Flash-KMeans; on 10B DINO vectors, 2.5 epochs vs 25; IVF approximation further cuts cost; retrieval recall improves at same training time.

Speakers

•

大飞 — Host

⋮