# Modified K-means Algorithm with Local Optimality Guarantees

arXiv: https://arxiv.org/abs/2506.06990 · HTML: https://mlsanity.com/paper/2506.06990/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 8 Jun 2025.

## Builds on (most cited first, 9 of 9)

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [SqueezeLLM: Dense-and-Sparse Quantization](https://mlsanity.com/paper/2306.07629/) (2023)
- [Data-Driven Clustering via Parameterized Lloyd's Families](https://mlsanity.com/paper/1809.06987/) (2018)
- [Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D](https://mlsanity.com/paper/1701.07204/) (2017)
- [On Clustering Time Series Using Euclidean Distance and Pearson Correlation](https://mlsanity.com/paper/1601.02213/) (2016)
- [Adapting k-means algorithms for outliers](https://mlsanity.com/paper/2007.01118/) (2020)
- [A k-means procedure based on a Mahalanobis type distance for clustering multivariate functional data](https://mlsanity.com/paper/1708.00386/) (2017)
- [Kullback-Leibler Divergence-Based Fuzzy C-Means Clustering Incorporating Morphological Reconstruction and Wavelet Frames for Image Segmentation](https://mlsanity.com/paper/2002.09479/) (2020)
- [Partial k-means to avoid outliers, mathematical programming formulations, complexity results](https://mlsanity.com/paper/2302.05644/) (2023)

## Built on by (most cited first, 2 of 2)

- [AutoSOTA: An End-to-End Automated Research System for State-of-the-Art AI Model Discovery](https://mlsanity.com/paper/2604.05550/) (2026)
- [Two-Point Local Optimality in k-Means via Boundary-Point Screening](https://mlsanity.com/paper/2610.06182/) (2026)

## Abstract (arXiv)

The K-means algorithm is one of the most widely studied clustering algorithms in machine learning. While extensive research has focused on its ability to achieve a globally optimal solution, there still lacks a rigorous analysis of its local optimality guarantees. In this paper, we first present conditions under which the K-means algorithm converges to a locally optimal solution. Based on this, we propose simple modifications to the K-means algorithm which ensure local optimality in both the continuous and discrete sense, with the same computational complexity as the original K-means algorithm. As the dissimilarity measure, we consider a general Bregman divergence, which is an extension of the squared Euclidean distance often used in the K-means algorithm. Numerical experiments confirm that the K-means algorithm does not always find a locally optimal solution in practice, while our proposed methods provide improved locally optimal solutions with reduced clustering loss. Our code is available at https://github.com/lmingyi/LO-K-means.