I'd want to see final cluster quality, not just inertia, before treating "one-tenth the epochs" as a drop-in win. On badly imbalanced or overlapping clusters, Lloyd's often spends early iterations bouncing centroids around. If the interpolation mainly damps that motion, you can look converged on the objective while the partition is still poor. A plot of ARI or NMI versus epoch budget on messy data would make the claim a lot more convincing.
Hi, I'm Swann Bessa, the author of the e-means paper. FYI, we get very good results on ARI and NMI on ImageNet and also synthetic data. We will release them in a later revision. If you have another distribution you have in mind for us to test, I would be glad to run it as well.
