Research map / Learning theory and algorithms / Clustering
Modified K-means Algorithm with Local Optimality Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that K-means need not converge to a locally optimal solution (via a 1-D counterexample) and proposes LO-K-means, which adds C-local and D-local checks after convergence while keeping K-means per-iteration complexity.
Problem
K-means (Lloyd's algorithm) is widely assumed to converge to a locally optimal solution, but this local optimality has not been rigorously established, especially for weighted K-means with Bregman divergences.
Approach
Derives necessary and sufficient conditions for C-local and D-local optimality of K-means solutions under Bregman divergences, and adds post-convergence checks (C-LO, D-LO, Min-D-LO) that move a point to strictly decrease the loss whenever the converged solution is not locally optimal, so the algorithm ends at a C-local or D-local solution at the same per-iteration complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add D-local search to K-means++ | K-means++ · News20, K=10 | clustering loss: 697,527 ± 32,211 -> 634,216 ± 5,596 | Helped |
| Use minimum-loss D-local move instead of the first improving D-local move (ablation) | D-LO · News20, K=10 | computation time: 6.18 -> 2.55 | Helped |
| Use minimum-loss D-local move instead of the first improving D-local move (ablation) | D-LO · News20, K=10 | clustering loss: 634,216 ± 5,596 -> 634,293 ± 6,477 | No clear effect |
| Add continuous-locality check after K-means convergence (ablation) | K-means · real-world datasets | clustering loss | No clear effect |
| Add discrete-locality search after K-means convergence | K-means · real-world datasets | clustering loss | Helped |
Surprising findings
- The widely cited K-means convergence-to-local-optimum claim is false: a simple 1-D counterexample shows K-means can stop at a non-locally-optimal solution.
- On real-world datasets, K-means almost always converges to a C-local solution, so C-LO rarely changes the output.
Limitations
- Improvements over K-means appear mainly for D-local variants, which may need many more iterations (e.g., News20 K=25 D-LO takes over 3000 iterations).
- Experiments are limited to squared Euclidean and a few Bregman divergences on small benchmarks, with synthetic data restricted to integer grids.
Experimental setup
Datasets: Iris Wine Quality News20 synthetic integer points in [1,10]^d
Benchmarks: Iris Wine Quality News20
Metrics: clustering loss computation time number of iterations improvement ratio
Baselines: K-means K-means++ D-LO-P&X
Builds on: Lloyd's algorithm K-means++ Bregman divergence
Closest papers by meaning
- Clustering with Bregman Divergences: an Asymptotic Analysis (NeurIPS 2016 · similarity 0.89)
- Improved Guarantees for k-means++ and k-means++ Parallel (NeurIPS 2020 · similarity 0.88)
- Bregman Power k-Means for Clustering Exponential Family Data (ICML 2022 · similarity 0.88)
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.86)
- An Objective for Hierarchical Clustering in Euclidean Space and Its Connection to Bisecting K-means (AAAI 2020 · similarity 0.86)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.