mlsanityData to 7 Oct 2026

Towards Optimal Lower Bounds for k-median and k-means Coresets

arXiv 2202.12793 ↗First posted 25 Feb 2022cs.DS cs.CG cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

Given a set of points in a metric space, the (k,z)-clustering problem consists of finding a set of k points called centers, such that the sum of distances raised to the power of z of every data point to its closest center is minimized. Special cases include the famous k-median problem (z = 1) and k-means problem (z = 2). The k-median and k-means problems are at the heart of modern data analysis and massive data applications have given raise to the notion of coreset: a small (weighted) subset of the input point set preserving the cost of any solution to the problem up to a multiplicative (1 ± varepsilon) factor, hence reducing from large to small scale the input to the problem. In this paper, we present improved lower bounds for coresets in various metric spaces. In finite metrics consisting of n points and doubling metrics with doubling constant D, we show that any coreset for (k,z) clustering must consist of at least Omega(k varepsilon-2 log n) and Omega(k varepsilon-2 D) points, respectively. Both bounds match previous upper bounds up to polylog factors. In Euclidean spaces, we show that any coreset for (k,z) clustering must consists of at least Omega(kvarepsilon-2) points. We complement these lower bounds with a coreset construction consisting of at most tildeO(kvarepsilon-2· min(varepsilon-z,k)) points.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 46 of its 88 references that are in the map. First posted on arXiv 25 Feb 2022.

Builds on

46 of 88 references.

References · 46

  1. 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
  2. 2016Coresets for Scalable Bayesian Logistic Regressioncited by 79
  3. 2018On Coresets for Logistic Regressioncited by 65
  4. 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
  5. 2018Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clusteringcited by 53
  6. 2019Coresets for Clustering with Fairness Constraintscited by 51
  7. 2014Dimensionality Reduction for k-Means Clustering and Low Rank Approximationcited by 48
  8. 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 41
  9. 2017Training Gaussian Mixture Models at Scale via Coresetscited by 38
  10. 2020Coresets for Near-Convex Functionscited by 38
  11. 2021A New Coreset Framework for Clusteringcited by 38
  12. 2020Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimalcited by 31
34 more
  1. 2018Near-Optimal Coresets of Kernel Density Estimatescited by 30
  2. 2019Discrepancy, Coresets, and Sketches in Machine Learningcited by 30
  3. 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
  4. 2014An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimizationcited by 26
  5. 2015Improved and Simplified Inapproximability for k-meanscited by 22
  6. 2018varepsilon-Coresets for Clustering (with Outliers) in Doubling Metricscited by 19
  7. 2020Sets Clusteringcited by 19
  8. 2020On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applicationscited by 19
  9. 2017One-Shot Coresets: The Case of k-Clusteringcited by 15
  10. 2018Near-Linear Time Approximation Schemes for Clustering in Doubling Metricscited by 14
  11. 2020Coresets for Clustering in Excluded-minor Graphs and Beyondcited by 14
  12. 2017On the Local Structure of Stable Clustering Instancescited by 13
  13. 2020On Approximability of Clustering Problems Without Candidate Centerscited by 13
  14. 2016Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metricscited by 11
  15. 2018Optimal terminal dimensionality reduction in Euclidean spacecited by 11
  16. 2017A Fast Approximation Scheme for Low-Dimensional k-Meanscited by 10
  17. 2019Fast and Accurate Least-Mean-Squares Solverscited by 10
  18. 2021Coresets for Decision Trees of Signalscited by 10
  19. 2019Coresets for Clustering in Graphs of Bounded Treewidthcited by 9
  20. 2019Coresets for Ordered Weighted Clusteringcited by 8
  21. 2020Coresets for Regressions with Panel Datacited by 8
  22. 2021Coresets for Time Series Clusteringcited by 8
  23. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  24. 2018Composable Core-sets for Determinant Maximization Problems via Spectral Spannerscited by 7
  25. 2018Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensionscited by 7
  26. 2021A Refined Approximation for Euclidean k-Meanscited by 7
  27. 2021Terminal Embeddings in Sublinear Timecited by 6
  28. 2016Terminal Embeddingscited by 5
  29. 2021Coresets for Clustering with Missing Valuescited by 5
  30. 2015A bi-criteria approximation algorithm for k Meanscited by 4
  31. 2017Clustering High Dimensional Dynamic Data Streamscited by 4
  32. 2021Coresets for Kernel Clusteringcited by 4
  33. 2019Efficient approximation schemes for uniform-cost clustering problems in planar graphscited by 2
  34. 2015Optimal parameterized algorithms for planar facility location problems using Voronoi diagramscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 5; 2025: 5; 2026: 2.

23 papers.

Sort:

  1. 2024Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyondcited by 15
  2. 2022Coresets for Vertical Federated Learning: Regularized Linear Regression and K-Means Clusteringcited by 14
  3. 2023Provable Data Subset Selection For Efficient Neural Network Trainingcited by 14
  4. 2022An Empirical Evaluation of k-Means Coresetscited by 7
  5. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  6. 2023Near-Optimal Quantum Coreset Construction Algorithms for Clusteringcited by 6
  7. 2023Parameterized Approximation Schemes for Clustering with General Norm Objectivescited by 5
  8. 2023Multi-Swap k-Means++cited by 4
  9. 2023On Generalization Bounds for Projective Clusteringcited by 4
  10. 2024Settling Time vs. Accuracy Tradeoffs for Clustering Big Datacited by 4
  11. 2025A Tight VC-Dimension Analysis of Clustering Coresets with Applicationscited by 4
  12. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
11 more
  1. 2024Ridge Leverage Score Sampling for ℓp Subspace Approximationcited by 2
  2. 2023Differentially Private Clustering in Data Streamscited by 1
  3. 2024Accurate Coresets for Latent Variable Models and Regularized Regressioncited by 1
  4. 2022Improved Coresets for Euclidean k-Meanscited by 0
  5. 2023Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streamingcited by 0
  6. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  7. 2025Random Normed k-Means: A Paradigm-Shift in Clustering within Probabilistic Metric Spacescited by 0
  8. 2025Learning Augmented Graph k-Clusteringcited by 0
  9. 2025Coresets for Clustering Under Stochastic Noisecited by 0
  10. 2026Fair Dataset Distillation via Cross-Group Barycenter Alignmentcited by 0
  11. 2026Beyond Worst-Case Coreset Bounds for k-Clustering via Determinantal Samplingcited by 0