The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

2026-02-10 · Roy R. Lederman, David Silva-Sánchez, Ziling Chen, Gilles Mordant, Amnon Balanov, Tamir Bendory arxiv

Lloyd's k-means algorithm is one of the most widely used clustering methods. We prove that in high-dimensional, high-noise settings, the algorithm exhibits catastrophic failure: with high probability, essentially every partition of the data is a fixed point. Consequently, Lloyd's algorithm simply returns its initial partition - even when the underlying clusters are trivially recoverable by other methods. In contrast, we prove that Hartigan's k-means algorithm does not exhibit this pathology. Our results show the stark difference between these algorithms and offer a theoretical explanation for the empirical difficulties often observed with k-means in high dimensions.

📄 PDF Abstract BibTeX arXiv:2602.09936

Code (0)

등록된 구현이 없습니다.

Safer Deep RL with Shallow MCTS: A Case Study in Pommerman

2019-04-10 · Bilal Kartal, Pablo Hernandez-Leal, Chao GAO, Matthew E. Taylor

Safe reinforcement learning has many variants and it is still an open research problem. Here, we focus on how to use action guidance by means of a non-expert demonstrator to avoid catastrophic events in a domain with spa…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Robot Learning with Crash Constraints

2020-10-16 · Alonso Marco, Dominik Baumann, Majid Khadiv, Philipp Hennig 외

In the past decade, numerous machine learning algorithms have been shown to successfully learn optimal policies to control real robotic systems. However, it is common to encounter failing behaviors as the learning loop p…

Bayesian Optimization

Less is MoE: Trimming Experts in Domain-Specialist Language Models

2026-06-04 · Haoze He, Xinkai Zou, Xuan Jiang, Xingyuan Ding 외 arxiv

Mixture-of-Experts (MoE) models achieve strong performance through conditional computation, but their large parameter footprint poses deployment challenges. Prior MoE compression approaches catastrophically fail when eva…

Unsupervised Feature Selection for the k-means Clustering Problem

2009-12-01 · NeurIPS 2009 12 · Christos Boutsidis, Petros Drineas, Michael W. Mahoney

We present a novel feature selection algorithm for the $k$-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter $\epsilon \in (0,1)$, selects and appropriately rescales in an unsuperv…

Clustering feature selection

On Using Machine Learning to Early Detect Catastrophic Failures in Marine Diesel Engines

2026-03-13 · Francesco Maione, Paolo Lino, Giuseppe Giannino, Guido Maione arxiv

Catastrophic failures of marine engines imply severe loss of functionality and destroy or damage the systems irreversibly. Being sudden and often unpredictable events, they pose a severe threat to navigation, crew, and p…

Data Augmentation