# Improved Coresets for Euclidean k-Means

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 57 references that are in the map.
- First posted on arXiv 15 Nov 2022.

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

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [Coresets for Regressions with Panel Data](https://mlsanity.com/paper/2011.00981/) (2020)
- [Coresets for Time Series Clustering](https://mlsanity.com/paper/2110.15263/) (2021)
- [Dimensionality Reduction for Sum-of-Distances Metric](https://mlsanity.com/paper/1912.12003/) (2019)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction](https://mlsanity.com/paper/2205.00371/) (2022)
- [Coresets for Kernel Clustering](https://mlsanity.com/paper/2110.02898/) (2021)
- [Polylogarithmic Sketches for Clustering](https://mlsanity.com/paper/2204.12358/) (2022)

## Abstract (arXiv)

Given a set of n points in d dimensions, the Euclidean k-means problem (resp. the Euclidean k-median problem) consists of finding k centers such that the sum of squared distances (resp. sum of distances) from every point to its closest center is minimized. The arguably most popular way of dealing with this problem in the big data setting is to first compress the data by computing a weighted subset known as a coreset and then run any algorithm on this subset. The guarantee of the coreset is that for any candidate solution, the ratio between coreset cost and the cost of the original instance is less than a (1± varepsilon) factor. The current state of the art coreset size is tilde O(min(k2 · varepsilon-2,k· varepsilon-4)) for Euclidean k-means and tilde O(min(k2 · varepsilon-2,k· varepsilon-3)) for Euclidean k-median. The best known lower bound for both problems is Omega(k varepsilon-2). In this paper, we improve the upper bounds tilde O(min(k3/2 · varepsilon-2,k· varepsilon-4)) for k-means and tilde O(min(k4/3 · varepsilon-2,k· varepsilon-3)) for k-median. In particular, ours is the first provable bound that breaks through the k2 barrier while retaining an optimal dependency on varepsilon.