Yeah most of these tricks are already well established. And their own ablations show that combining them doesn’t bring any special synergy - it’s just putting together a lot of common techniques. The baselines also are tough to believe fully. Comparing against faiss is fair since many authors are faiss contributors so they know how to run it. But they don’t and should include a comparison to a well tuned mini batch kmeans like the one in scikit.
Hi oofbey,
If you look at Figure 3 of our paper, the baseline "Sculley" is precisely the well tuned mini batch kmeans of scikit-learn. We swept on batch sizes and threshold for dead cluster reassignment (Batch size: 256, 512, 1024, 2048, 4096, 65536, 262144, 524288. Dead-cluster threshold : 0, 0.001, 0.01, 0.05, 0.1, 0.5). The reason e-means outperforms previous mini-batch methods is because it is a robust optimization framework powered by scaling laws, specializing techniques inspired from the deep learning literature for the k-means problem. Meanwhile mini-batch k-means methods rely on the MacQueen update rule introduced in 1967, which is known to be highly suboptimal and converge to a lesser solution than Lloyd (See Darken and Moody, 1990, Note on Learning Rate Schedules for Stochastic Optimization).