Hacker News Reader

Comment by jlhawn | Hacker News Reader

I wonder if this could be used anywhere as an alternative to Lloyd's algorithm. I have a hobby project which uses Lloyd's to "relax" an icosohedral equal area mesh on the surface of a sphere [1]. I'm going to try to swap it out with an adaptation of this and see if it's much better or if I can afford more iterations with this method.

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

View on HN

Hi, I'm Swann Bessa, the author of e-means. Thanks for trying e-means. If I may I'd like to come back on a few of the points you made.

"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.

Is E-means finding the true global minimum? Or is it just finding a better solution more consistently?

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.

> 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).

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.

Since it's basically a linear interpolation between Lloyd's algorithm and not moving any points it will be at least as good but gains might be limited without careful tuning.

Edit: in fact you might end up going faster by moving the other way, set alpha = -0.1 and see what happens!

Careful tuning is provided by the scaling laws, so you don't need to set the hyperparameters yourself. I am quite skeptical about setting alpha=-0.1 tbh, but I'm curious to see what happens too lol.

It's prpbably going to diverge, but in this case there's not really a dataset to begin with. It's just alternating calculating the centroids with calculating the Voronoi diagrams. The reason it's slow is not because it can't escape a local minimum it's because the two steps are only slowly converging on the optimum.

So something that ends up increasing the step size might actually help. But in practice you're probably better of doing something more orthodox like conjugate gradient or Newton's.

Your website looks incredibly interesting! Very exited to read it when I have time. When you mentioned icosahedral meshes, I immediately thought it would be related to weather/climate modeling :D.

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/).

Reply on news.ycombinator.com