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
Quiz: How to Set Up a Python Project for Agentic Coding
0Real Python

How Mitts Makes Parallel Rust Builds Faster Than Cargo
0HackerNoon
The internet-dependent mattress has a recovery mode: rooting the Eight Sleep Pod 3 with a GNU tar quirk
0dev.to
How Budgeting Resources for First Input Delay Can Backfire: Tradeoffs and Debugging
0dev.to
Designing the Order Flow for a Custom Children’s Book
0dev.to
I Caught a Pricing Page Change That Would Have Cost Us a Client
0dev.to