Backend
Small Is Not Dead: Distance-Aware Cluster Revival for e-means
arXiv stat.ML0 views
arXiv:2611.18238v1 Announce Type: cross Abstract: e-means (Bessa et al., 2026) is a recent mini-batch k-means algorithm, now part of the FAISS library, that reaches the error of Lloyd's algorithm about an order of magnitude faster on large embedding datasets. Every five mini-batches, it removes every cluster whose running point count falls below a tenth of the average and reuses its centre to split a large cluster. In the authors' ablation, removing this mechanism, called dead-cluster revival, raises the error more than removing any other component added to the moving-average update. The rule, however, considers only cluster size: it cannot distinguish a cluster that is small because it is redundant from one that covers a rare, isolated group of points, and on data with such groups it repeatedly removes centres whose removal is costly. We add a second condition, based on the distance between centres: a small cluster is removed only if its centre is close to another centre, relative to a running estimate of the mean squared error. When a centre equals the mean of its points, this squared distance is an upper bound on the average increase in squared error, per point of the cluster, caused by removing the centre. The condition costs one nearest-centre search for the small clusters every five mini-batches and adds no measurable running time. On the e-means paper's embedding benchmarks, it never prevents a removal, so the results are identical to those of FAISS. On datasets with small isolated groups not used during development, it reduces the test error after two epochs by roughly 10% to 80% relative to count-based revival, and it preserves the advantage of k-means++ initialization; on the other evaluation datasets, it stays within about 1% of the better of revival enabled and disabled. We also report two failure modes that the analysis predicts. This is a CPU proof of concept; GPU implementations are left to future work.
Source:https://arxiv.org/abs/2611.18238PreviousHierarchical Bayesian physics-augmented neural networks for populations of hyperelastic laws: specimen variability and uncertainty from scarce, noisy dataNextDECODE: Decomposable Environments for COntrolled Sequential-Decision Evaluation
Related posts
Helsing backer Plural raises $1.1B to fund Europe’s next moonshots
0TechCrunch
Building Mobile Connectivity in Afghanistan: A Look at Roshan
0dev.to
Your Tests Blocked System.exit With a SecurityManager and Java 25 Will Not Let You Install One
0dev.to
We autoscaled our Java pricing service on memory and it grew to twenty pods and stayed there
0dev.to
Nine small tools I stopped installing apps for
0dev.to
I built a small tool to capture website screenshots across devices
0dev.to Productivity