E-means: Outperforming k-means in one-tenth the epochs
e-means.github.io
e-means.github.io
Edit: tried it, and it’s definitely not better for this use case. e-means wins by needing fewer passes over a huge dataset, but relaxing a mesh on a sphere has no dataset: each Voronoi cell’s centroid can be computed directly from its geometry. Mini-batches just swap that for a noisy sampled estimate of the same thing. It has the same objective and the same optimum, so at best it matches Lloyd. In practice it was much slower and left the grid noisy, and with small sample budgets it even tangled the mesh.
[1] https://webgcm.app/explain/grid#nudging-the-cells-into-shape
Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!
On the topic of these meshes, I'm currently exploring if we can come up with better meshing strategies in data-driven weather models (https://tcumulus.dev/blog/thesis/).
"e-means wins by needing fewer passes over a huge dataset": the improvements of e-means are shown on datasets from 10k up to 10B points (you can try e-means against Lloyd at low problem sizes at https://e-means.github.io/playground.html) so I would not say huge datasets only. It depends on what you call huge obviously, and that's relative.
"It has the same objective and the same optimum, so at best it matches Lloyd." I strongly disagree with that. e-means has the same objective and the optimal clustering is set by the problem, but Lloyd doesn't find this optimal clustering in the vast majority of cases. Lloyd gets stuck in a local minimum, and what we find is that e-means reliably finds better clusterings than Lloyd in terms of MSE, but also other clustering metrics.
Regarding your usecase : I'd be curious to know what settings you used for e-means and a reproduction code. Don't hesitate to send me your code at swann@meta.com, I'm down to have a check because we're confident about e-means' performance against Lloyd.
https://crates.io/crates/emeans
https://pypi.org/project/emeans
We use k-means to build the cells of our vector index, which today runs 5 Lloyd iterations on a sample of the data. So I ran a quick test on 500k LAION embeddings (768 dimensions, 4,096 cells) against our current code:
- Current setup of 5 iterations: about 4x faster, with slightly better recall at every probe count (for example 0.9518 vs 0.9473 at 32 probes) and fewer rows scanned per query
- Cells came out much more even. The biggest cell went from 6.6x the average size to 4.75x, and there were no empty cells (we had 7)
- With only 2 iterations it was about 10x faster and recall stayed close to what we have today
These numbers are from my mac. I'm rerunning on a Linux box with AVX-512 now. If it holds up, we'll try it in our index build
Some notes here: https://github.com/infino-ai/infino/issues/1279
Thank you for trying e-means and detailing your results. This kind of results of e-means at 2 epochs compared with Lloyd is the typical kind of acceleration we want people to know about.
If you have any questions, I’ll be happy to answer.
That's impressive!
If you are claiming that your algorithm is "highly parallelizable" and comes with "wall-clock speedups", then the actual metrics that matter here is not number of steps or even basic wall clock time as your size remains fixed, but how your algorithm scales as more data is present or parallelism is required. This algorithm splits up the minibatch across workers and has them compute local updates, then allreduces it. As the amount of data goes up, the comms become much more expensive (since you have to use a worse transport layer), which means that you're basically locked in a desperate attempt to do more local work before you send your partial update to everyone else. If you attempt this (not explored in the paper) you will find that the improvement in clustering by doing this extra work has diminishing returns–you only reduce the number of updates by a few steps (which is what drives your wall clock time). At scale you end up being heavily comms limited and not super parallel at all.
"People have been doing minibatch k-means for a while, including with an EMA update" : EMA updates are indeed used in clustering, but to our knowledge there is no paper that uses pure EMA updates for k-means clustering on a static dataset. EMA updates are typically used for moving distributions because of their ability to forget the past (as in VQ-VAEs), but their advantage for static datasets had not been empirically demonstrated. If you take a look at appendix E of the paper, we compare EMA to other gradient descent methods and show that EMA is much more stable and has better quality, especially at large batches. Our method also integrates EMA updates in an optimization framework that reliably outperforms Lloyd and previous mini-batch methods.
"the contribution here is that they tried to measure how much better it is": The contribution here is to integrate EMA updates in an optimization framework to provide a method as robust and performant as we could. If you look at previous mini-batch k-means papers, the speedups and the performance is nowhere nearly as good as e-means, which beats Lloyd at 25 epochs in 2 to 3 epochs. In fact, mini-batch k-means is known in the literature as a fast method but with lesser convergence than Lloyd, and we compare to them in Figure 3. The e-means framework allows to be both faster and have better convergence than Lloyd, without the user having to tune the batch or the step.
"How your algorithm scales as more data is present": In the first figure of the paper, we show that e-means scales up to 10 billion points and 16 million clusters.
On communication: workers only exchange per-update statistics (K×d numbers with replicated centroids). You argue that bigger batches have diminishing returns, so that extra local work doesn't cut the number of updates. But that's precisely what our batch law addresses: it returns the largest batch whose loss stays within ~0.2% of the best loss at a fixed number of epochs. In other words, we carefully scale the batch size to avoid that our speedups are driven down by the diminishing returns you mention.
The multi-node regime is in the paper: the 10B run used 32 machines, so synchronization went over the inter-node network, and the bottleneck was still the distance computation, not communication. That's also why an IVF variant, which cuts distance computations, does it in ~23 GPU-hours.
Though I suppose it may be as simple as expectation maximization with a friction term, since Sj = sj - a (sj - Sj).
Importantly they note that this update rule keeps the centroid within the convex hull, which is pretty important.
The fact that the update rule keeps the centroid within the convex hull is indeed very important. If you look at Appendix E, the gradient descent methods don't have this property and are less stable than EMA updates.
Regarding simulated annealing, I agree with the parallel. You can see mini-batches as introducing noise in the beginning of the optimization to espace local minima and the step size decreasing through the training acts like a temperature in simulated annealing. Simulated annealing was already used for k-means with theoretical proof that you can reach the global minimum in enough epochs, but in practice, those methods are really slow. A paper that comes to mind is "A simulated annealing algorithm for the clustering problem" (https://www.sciencedirect.com/science/article/pii/0031320391...).
The parallel with expectation maximization is also coherent, though less straightforward to me. K-means can be viewed as a hard-assignment, special case of the Expectation-Maximization algorithm applied to Gaussian Mixture Models (GMMs).
If you have any other questions, I'll be happy to answer.
Hope it gets added to scipy - it’s much more available in the envs many use than facebooks own faiss library.
There's still not one particularly great way to pick k for this type of clustering. There kind of can't be as clustering is sort of inherently subjective.
Other methods like HDBSCAN can find the number of clusters themselves. There's still a 'one key parameter' you have to pick yourself, but it can be more intuitive and less sensitive for some datasets, when you don't know how many clusters there are / how many you want.
Sometimes, picking k exactly is useful for practical reasons too. Like fixing the size of your codebook. Or partitioning a dataset into k equal-ish pieces, say to spread across a pool of servers of a known/fixed size.
When I was just starting out, client-server was still a bit of a specialty, mostly reserved for gaming and large institutions. Most of my education was in single task computing. If the university hadn’t offered a class in distributed computing I wouldn’t have gotten much in that direction except in independent study.
In the time since then, we seem to have focused much less on seconds per task and more on tasks per second, which results in more concern about statistical spreads, and queuing mechanisms to manage the variability between a hit and a miss. It would be better if this sort of computation were more organized into a discipline.
That makes it... not very interesting, because it's not a drop-in replacement then, and potentially many other clustering methods would have worked in particular applications as well. Or does this one beat most of the others as well?
If you look at our paper on arxiv (https://arxiv.org/abs/2611.09501), Table 2, the hyperparameters laws have been validated on 4 datasets outside of the fit, but also on scales outside of the fit. There the hyperparameters they picked made the loss only 0.07% worse than the best hyperparameters possible on average. The robust results in the paper, which are on 26 different datasets where e-means beats Lloyd by a wide margin, are also a proof of the generalization of our scaling laws.
Impressive results ...
You want to assign things to a set of clusters so that things that share similar properties are grouped closely together. But, we also want those clusters to be as big as possible. We don't want to leave little islands that only have a few things in them.
Take, for example, classification of email messages. Let's say you have a billion email messages and you want to find a way to cluster them automatically into 10 categories. You don't know what the categories are ahead of time. You just have a way of making sure that an email can be represented by a vector of numbers such that two emails that are close together in their meaning and characteristics will have similar numbers.
K-Means clustering solves that problem but is intractable to calculate for large datasets having high dimensionality (such as the email example). My understanding is that E-Means is away to achieve this spectacularly more efficiently than the best alternative previously known.
EDIT: actually I see that they have a section about "The k-means problem" and that's where I think they get it wrong. What they describe is not the problem itself but how to solve it. The real problem (for most people at least, they seem to have a different problem) is to find the clusters in a dataset where you already know that there are clusters and how many there are.
The goal of e-means is to be a drop-in replacement for k-means. It solves the exact same problem, with the exact same inputs and delivers better centroids and quality in a fraction of the time. So I'm not sure what we get wrong by working on a problem that hundreds of papers also worked on. Is the whole k-means literature getting it wrong then ?
Picking the k is a separate problem, on which also a body of literature has worked too. e-means is a drop-in replacement for k-means so you can use any method you would use for choosing the k but with e-means instead of k-means.
e-means performs better on a very wide array of datasets, definitely not degenerate cases, don't hesitate to check out our paper at https://arxiv.org/abs/2611.09501.
If you have any question or objection, I'll be happy to answer.
If you want, you can also play with it now in your browser at : https://e-means.github.io/playground.html
Feel free to ask any questions, I'll be happy to answer.