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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Stabilizing Exponential Moving Average k-Means: Repairing Two Counterexamples

Rohan Arun
2 links
Zenodo (CERN European Organization for Nuclear Research)
Advanced Clustering Algorithms Research
preprint

Stabilizing Exponential Moving Average k-Means: Repairing Two Counterexamples

Rohan Arun
preprint en

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
Advanced Clustering Algorithms Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon