Reproduce “Towards Optimal Lower Bounds for k-median and k-means Coresets” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn
This paper establishes tighter lower bounds for the size of coresets for k-median and k-means clustering across various metric spaces, including Ω(k·log(n)/ε²) for finite metrics, Ω(kD/ε²) for doubling metrics, and Ω(k/ε²) for Euclidean space. It also presents a novel coreset construction for Euclidean space of size O(k/ε² · min(ε⁻ᶻ, k)), narrowing the gap between theoretical limits and practical constructions.
Key insights
- The minimum coreset size depends fundamentally on the number of clusters (k) and the approximation error (ε), with the Ω(k/ε²) bound holding for Euclidean space regardless of dimension.
- The complexity of the underlying metric space, such as the doubling constant D, directly influences the minimum required coreset size, shown by the Ω(kD/ε²) bound for doubling metrics.
- Any effective coreset must capture information about the clustering structure across multiple scales, which inherently requires a minimum number of points dependent on both k and ε.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.