Optimal coreset sizes for precise clustering in Euclidean spaces

Tight Coreset Bounds for Euclidean $(k,z)$-Clustering

Data Structures and AlgorithmsComputational Geometry

Summary

Clustering groups similar points together, but handling large data precisely needs summaries called coresets. The authors found the exact smallest size these summaries must be for a wide range of settings in Euclidean spaces. They solved a puzzle on how corest size depends on data accuracy and number of clusters. Their new math shows exactly how small these summaries can get without losing important information.

What this means in practice

  • For machine learning engineers: Design data summarization techniques that guarantee smallest possible summaries when clustering large Euclidean datasets with specific precision.
  • For data infrastructure teams: Optimize storage and query costs by understanding minimal data summaries needed for cluster analysis at given accuracy levels.

A theory result. No direct application yet.

Authors

Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu

Abstract

We study the optimal coreset size for Euclidean $(k,z)$-clustering, where $z\ge1$ is fixed. Huang, Li, and Wu (STOC 2024) proved a lower bound of $Ω_z(k\varepsilon^{-z-2})$ for $\varepsilon\gtrsim_z k^{-1/(z+2)}$, matching the known upper bound up to polylogarithmic factors. For $0<\varepsilon<k^{-1/(z+2)}$, the upper bound $\widetilde O_z(k^{(2z+2)/(z+2)}\varepsilon^{-2})$ remained unmatched. The previous lower bounds gave only $Ω_z(\max\{k\varepsilon^{-2},k^{(2z+3)/(z+2)}\varepsilon^{-1}\})$. We close this gap by proving a matching lower bound throughout $0<\varepsilon<k^{-1/(z+2)}$, including arbitrarily small $\varepsilon$. Together with known bounds, this determines the optimal worst-case coreset size as $$ \widetildeΘ_z\!\left(\min\left\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\right\}\right) $$ for every integer $k\ge1$ and $0<\varepsilon<1$. In particular, the bounds are $\widetildeΘ(k^{4/3}\varepsilon^{-2})$ for $k$-median when $\varepsilon<k^{-1/3}$, and $\widetildeΘ(k^{3/2}\varepsilon^{-2})$ for $k$-means when $\varepsilon<k^{-1/4}$. Our construction uses projection levels to encode four-wise independent signs, allowing $k$ centers to detect omissions regardless of how the retained points are reweighted.