Stabilizing Exponential Moving Average k-Means: Repairing Two Counterexamples
e-means (Bessa et al., 2026) replaces Lloyd iterations with exponential moving averages of cluster counts and sums and revives low-mass clusters. Assylbekov (2026) gave two counterexamples: mass-based revival can destroy a global optimum, making the ratio of expected losses to Lloyd unbounded under k-means++ seeding, and near-zero initial counts let a single mini-batch move a decision boundary past an unvisited point (probability 24/49 in his second example). Working from the author's reference implementation, we show which fix resolves which counterexample. A seed-loss check (return Lloyd from the seeds whenever the e-means output is worse than the seeds) resolves the first and, on every input, keeps the 8(ln k + 2) expected approximation bound of k-means++, at two data passes when it does not trigger. A pseudo-count floor τ resolves the second: a one-step argument gives τ* = 0.1927, and in 20,000 shuffles per value the failure rate falls from 48.66% to zero between τ = 0.1925 and 0.193. Neither fix alone resolves both; their combination is e-means+. We also report costs on non-adversarial data, including cases where the fixes do not help. On SIFT1M (1M vectors, k = 1024, 3 seeds), e-means+ matches the loss of 25 Lloyd iterations (0.9998×) in 4 data passes instead of 26, with the same Recall@10, and the check never triggers. Code, results and the scripts that generate and check every number in the paper: https://github.com/rohanarun/emeans-plus
Authors
- Rohan Arun
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24354548
- Primary Topic
- Advanced Clustering Algorithms Research
- Type
- preprint