Re:E-means: 10x faster k-means at equal loss
by manvillej on Tuesday November 10, 2026 @07:55AM
(#50439663)
Is E-means finding the true global minimum? Or is it just finding a better solution more consistently?
Re:E-means: 10x faster k-means at equal loss
by swann_bessa on Tuesday November 10, 2026 @09:29AM
(#50440904)
Hi, I'm Swann Bessa, the author of e-means. Thanks for your questions.
The answer is that e-means consistently finds a better solution than Lloyd. It's impossible to know if it's the global minimum or not. Finding the true global optimum is NP-hard, so no practical algorithm can guarantee that.
Re:E-means: 10x faster k-means at equal loss
by nine_k on Tuesday November 10, 2026 @10:41AM
(#50441930)
> if it's the global minimum or not
Not impossible, just very expensive, because k-means is NP-hard, and finding the strictly optimal solution may require exponential time (or worse).
Re:E-means: 10x faster k-means at equal loss
by swann_bessa on Tuesday November 10, 2026 @10:51AM
(#50442100)
Yes, right. That's more rigorous to say it like that. Note that at the scales of the paper it is in practice impossible with today's computational means.
"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 [email protected], I'm down to have a check because we're confident about e-means' performance against Lloyd.