betaFeedback

WorksComputer Science

Tight Coreset Bounds for (k,z)(k,z)-Clustering in Euclidean and Doubling Metrics

Abstract

We determine the optimal worst-case size of strong coresets for (k,z)(k,z)-clustering in Euclidean spaces and doubling metrics, up to polylogarithmic factors. In Euclidean space, previous lower bounds matched the best upper bounds only for ε≳k−1/(z+2)\varepsilon\gtrsim k^{-1/(z+2)}. We close the gap for arbitrarily small ε\varepsilon, establishing the optimal size Θ~(min⁡{k(2z+2)/(z+2)ε−2, kε−z−2})\widetildeΘ(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\}) for every fixed z≥1z\ge1, all k≥1k\ge1, and 0<ε<10<\varepsilon<1. Our lower bound replaces each offset in a previous hard instance by a group of distinct offsets. A fixed family of kk-center queries and four-wise independent signs force a large relative cost error for every sufficiently small subset with arbitrary nonnegative weights. For doubling metrics of dimension DD, we resolve the previously unmatched bounds for z>2z>2. We prove an upper bound of O~(k2−2/zDε−2)\widetilde O(k^{2-2/z}D\varepsilon^{-2}) and a lower bound that, together with known upper bounds, establishes the optimal size Θ~(kDmin⁡{k1−2/zε−2, ε−z})\widetildeΘ(kD\min\{k^{1-2/z}\varepsilon^{-2},\,\varepsilon^{-z}\}) for fixed z>2z>2, 0<ε≤εz0<\varepsilon\le\varepsilon_z, and D≥Czlog⁡(2/ε)D\ge C_z\log(2/\varepsilon), where Cz>0C_z>0 and εz∈(0,1)\varepsilon_z\in(0,1) depend only on zz. The lower bound exploits the ability to encode Θ(D)Θ(D) independent signs per center without diluting relative cost discrepancy. For the upper bound, we use independent, unbiased two-point summaries that exactly preserve cluster mass and anchor cost, combined with iterative size reduction.

Introduction

We study the optimal coreset size for (k,z)(k,z)-clustering, where z≥1z \ge1 is a fixed constant.1

(k,z)(k,z)-clustering. Given a metric space (X,d)(\mathcal{X},d), a finite dataset X⊆XX \subseteq\mathcal{X}, and an integer k≥1k \ge1, the goal is to find a set C⊆XC \subseteq\mathcal{X} of kk centers minimizing

cost⁡z(X,C):=∑p∈Xdz(p,C),d(p,C):=min⁡c∈Cd(p,c).\operatorname{cost}_{z}(X,C) := \sum_{p \in X} d^{z}(p,C), \qquad d(p,C) := \min_{c \in C} d(p,c).

The cases z=1z=1 and z=2z=2 are the classical kk-median and kk-means problems, respectively. These clustering objectives have been extensively studied in data analysis, machine learning, and approximation algorithms [26, 22].

Euclidean space is the most extensively studied geometric setting, with a long line of approximation algorithms for these objectives [6, 12]. Another central setting is metrics of bounded doubling dimension: a metric has doubling dimension at most DD if every ball can be covered by at most 2D2^D balls of half its radius. This covering property captures low-dimensional structure without requiring a Euclidean embedding; for constant DD, it supports near-linear-time approximation schemes for clustering [7]. More recent parameterized approximation schemes cover both Euclidean and doubling metrics [ABB+23]. Other well-studied settings include shortest-path metrics of planar and bounded-treewidth graphs [ABB+23].

Coresets. For large datasets, coresets provide a way to reduce the input size while preserving the clustering objective [24, 15].

Definition 1.1 (Coreset). For 0<ε<10 < \varepsilon< 1, a strong ε\varepsilon-coreset for (k,z)(k,z)-clustering of XX is a subset S⊆XS \subseteq X with weights w:S→R≥0w:S \to\mathbb{R}_{\ge0} such that

∣cost⁡z(S,C)−cost⁡z(X,C)∣≤εcost⁡z(X,C)for every C⊆X with ∣C∣=k,\left|\operatorname{cost}_{z}(S,C)-\operatorname{cost}_{z}(X,C)\right| \le\varepsilon\operatorname{cost}_{z}(X,C) \qquad\text{for every } C \subseteq\mathcal{X} \text{ with } |C|=k,

where cost⁡z(S,C):=∑p∈Sw(p)dz(p,C)\operatorname{cost}_{z}(S,C) := \sum_{p \in S} w(p)d^{z}(p,C).

A clustering algorithm can run on a coreset instead of the full dataset while retaining nearly the same approximation guarantee. An efficiently constructed small coreset separates the cost of reading the data from the more expensive task of optimizing the centers. This has motivated extensive work on coresets in Euclidean spaces [24, 15, 16, 25], doubling metrics [17, 11], and graph metrics [BJKW21, CDR+25].

Coreset sizes. Determining the optimal coreset size in Euclidean space is a central problem in the area; Cohen-Addad, Saulpic, and Schwiegelshohn [10] described improving the Euclidean bounds as arguably “the most important open problem in coresets.” Following a sequence of dimension-independent constructions, Cohen-Addad et al. [9] proved an Ω(kε−2)\Omega(k\varepsilon^{-2}) lower bound, which became a natural target for upper bounds. Subsequent upper bounds of O~(k4/3ε−2)\widetilde{O}(k^{4/3}\varepsilon^{-2}) for kk-median and O~(k3/2ε−2)\widetilde{O}(k^{3/2}\varepsilon^{-2}) for kk-means still left open whether a superlinear dependence on kk was necessary [8]. Huang, Li, and Wu [22] showed that such a superlinear dependence is unavoidable in part of the parameter range: their Ω(kε−z−2)\Omega(k\varepsilon^{-z-2}) lower bound matches the known upper bound for ε≳k−1/(z+2)\varepsilon\gtrsim k^{-1/(z+2)}. They also obtained the upper bound O~(k(2z+2)/(z+2)ε−2)\widetilde{O}(k^{(2z+2)/(z+2)}\varepsilon^{-2}) for every fixed z≥1z \ge1. The remaining gap lies in the small-error regime 0<ε<k−1/(z+2)0 < \varepsilon< k^{-1/(z+2)}, where the known lower bounds are Ω(k(2z+3)/(z+2)ε−1)\Omega(k^{(2z+3)/(z+2)}\varepsilon^{-1}) for ε≳k−(z+1)/(z+2)\varepsilon\gtrsim k^{-(z+1)/(z+2)} and Ω(kε−2)\Omega(k\varepsilon^{-2}) for smaller ε\varepsilon. These lower bounds do not match the upper bound throughout the small-error regime, leaving the following question.

Problem 1. For fixed z≥1z \ge1, what is the optimal worst-case coreset size for Euclidean (k,z)(k,z)-clustering in the remaining regime 0<ε<k−1/(z+2)0 < \varepsilon< k^{-1/(z+2)}?

Doubling metrics provide a second important setting in which to seek tight coreset bounds. Beginning with the first efficient input-size-independent construction of Huang et al. [17], subsequent work sharpened the dependence on kk, ε\varepsilon, and DD. The framework of Cohen-Addad, Saulpic, and Schwiegelshohn [11] yields size O~(kDmin⁡{kε−2,ε−max⁡{z,2}})\widetilde{O}(kD\min\{k\varepsilon^{-2},\varepsilon^{-\max\{z,2\}}\}). The Ω(kDε−2)\Omega(kD\varepsilon^{-2}) lower bound of Cohen-Addad et al. [9] holds for D≳log⁡(k/ε)D \gtrsim\log(k/\varepsilon), matching this upper bound up to logarithmic factors for 1≤z≤21 \le z \le2 in that dimension range.

For z>2z > 2, however, the dependence on kk and ε\varepsilon remained unresolved.

Huang, Li, and Wu [22] proved a lower bound of Ω(kDε−z/log⁡k)\Omega(kD\varepsilon^{-z}/\log k) for ε≳k−1/(z+2)\varepsilon\gtrsim k^{-1/(z+2)}, matching the corresponding upper bound up to logarithmic factors, and an additional lower bound of Ω(k(2z+1)/(z+2)Dε−1)\Omega(k^{(2z+1)/(z+2)}D\varepsilon^{-1}) for k−(z+1)/(z+2)≲ε≲k−1/(z+2)k^{-(z+1)/(z+2)} \lesssim\varepsilon\lesssim k^{-1/(z+2)}. In both constructions, DD denotes the resulting ambient doubling dimension. For smaller ε\varepsilon, the bounds remained unmatched, raising the following problem:

Problem 2. For fixed z>2z > 2, what is the optimal dependence of the worst-case coreset size on kk, ε\varepsilon, and the doubling dimension DD for 0<ε<k−1/(z+2)0 < \varepsilon< k^{-1/(z+2)}?

Our Contributions

We establish matching coreset-size bounds, up to polylogarithmic factors, in Euclidean spaces and doubling metrics. For Euclidean spaces, our contribution is a lower bound that closes the remaining small-error gap. For doubling metrics, we improve both upper and lower bounds for z>2z > 2, resolving the remaining gap when D≳log⁡(2/ε)D \gtrsim\log(2/\varepsilon) and ε\varepsilon is sufficiently small. Table 1 summarizes the bounds.

Metric spacePrevious resultsThis work
Euclidean z≥1z \ge1Uppermin⁡{k2z+2z+2ε−2,kε−z−2}\min\{k^{\frac{2z+2}{z+2}}\varepsilon^{-2}, k\varepsilon^{-z-2}\} [9, 22]—
Lowerkε−2k\varepsilon^{-2} [9]; min⁡{k2z+3z+2ε−1,kε−z−2}\min\{k^{\frac{2z+3}{z+2}}\varepsilon^{-1}, k\varepsilon^{-z-2}\} [22]min⁡{k2z+2z+2ε−2,kε−z−2}\min\{k^{\frac{2z+2}{z+2}}\varepsilon^{-2}, k\varepsilon^{-z-2}\}
Doubling z>2z > 2UpperkDmin⁡{kε−2,ε−z}kD\min\{k\varepsilon^{-2},\varepsilon^{-z}\} [11]New upper branch: k2−2/zDε−2k^{2-2/z}D\varepsilon^{-2}
LowerkDε−2kD\varepsilon^{-2} [9]; kDmin⁡{kz+2z+2ε−1,ε−z}kD\min\{k^{\frac{z+2}{z+2}}\varepsilon^{-1},\varepsilon^{-z}\} [22]kDmin⁡{k1−2/zε−2,ε−z}kD\min\{k^{1-2/z}\varepsilon^{-2},\varepsilon^{-z}\}

Table 1. Coreset-size bounds up to polylogarithmic factors and zz-dependent constants. The new doubling upper branch holds for all D≥1D \ge1 and 0<ε<10 < \varepsilon< 1; combined with the previous kDε−zkD\varepsilon^{-z} branch, it matches our lower bound for 0<ε≤εz0 < \varepsilon\le\varepsilon_z and D≥Czlog⁡(2/ε)D \ge C_z\log(2/\varepsilon). Other restrictions are as in the cited results and Corollary 1.3.

We strengthen the construction of Huang, Li, and Wu [22] to obtain the following lower bound, which closes the gap throughout 0<ε<k−1/(z+2)0 < \varepsilon< k^{-1/(z+2)}.

Theorem 1.2 (Euclidean coreset lower bound). For every fixed real z≥1z \ge1, every integer k≥1k \ge1, and every 0<ε<10 < \varepsilon< 1, there exist an integer d≥1d \ge1 and a finite dataset X⊆RdX \subseteq\mathbb{R}^{d} such that every ε\varepsilon-coreset for (k,z)(k,z)-clustering of XX has size

Ω~(min⁡{kz+2z+2ε−2,kε−z−2}).\widetilde{\Omega}\left(\min\left\{k^{\frac{z+2}{z+2}}\varepsilon^{-2}, k\varepsilon^{-z-2}\right\}\right).

Combining this theorem with the known upper bounds [9, 22] gives the optimal size.

Corollary 1.3 (Optimal Euclidean coreset size). For every fixed real z≥1z \ge1, the lower bound in Theorem 1.2 is tight up to polylogarithmic factors for every integer k≥1k \ge1 and 0<ε<10 < \varepsilon< 1, over datasets of unrestricted dimension.

References

  1. [2]Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. In Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1707–1723. IEEE, 2024. doi:10.1109/FOCS61266.2024.00106.DOI
  2. [3]Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 462–473. IEEE, 2022. doi: 10.1109/FOCS54457.2022.00051.DOI
  3. [4]Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and Euclidean spaces and their applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.23, doi: 10.4230/LIPIcs.ICALP.2021.23.DOI
  4. [6][CAEMN22] Vincent Cohen-Addad, Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1621–1628. ACM, 2022. arXiv:2204.04828, doi:10.1145/3519935.3520011.
  5. [7][CAFS19] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximations schemes for clustering in doubling metrics. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 540–559. IEEE, 2019. arXiv:1812.08664, doi:10.1109/FOCS.2019.00041.
  6. [8][CALS+22] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for euclidean k-means. In Advances in Neural Information Processing Systems, volume 35, 2022.
  7. [9][CALSS22] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing, pages 1038–1051. ACM, 2022. doi:10.1145/3519935.3519946.
  8. [10][CASS21a] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in Euclidean spaces. In Advances in Neural Information Processing Systems, volume 34, pages 21085–21098, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.html.
  9. [11][CASS21b] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 169–182. ACM, 2021. URL: https://arxiv.org/abs/2104.06133, arXiv:2104.06133, doi:10.1145/3406325.3451022.
  10. [12][CCAG+26] Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, and Ernest van Wijland. A (4 + ε)-approximation for Euclidean k-means via non-monotone dual-fitting. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026. ACM, 2026. URL: https://people.idsia.ch/~grandoni/Pubblicazioni/CCGGLW26stoc.pdf, doi:10.1145/3798129.3800894.
  11. [13][CDR+25] Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. A tight VC-dimension analysis of clustering coresets with applications. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, pages 4783–4808. SIAM, 2025. doi:10.1137/1.9781611978322.162.
  12. [14][FHY25] Ziyi Fang, Lingxiao Huang, and Runkai Yang. Coreset for robust geometric median: Eliminating size dependency on outliers. In Advances in Neural Information Processing Systems, volume 38, 2025. arXiv:2510.24621, doi:10.52202/085713–0171.
  13. [15][FL11] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 569–578. ACM, 2011.
  14. [16]Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM Journal on Computing, 49(3):601–657, 2020. arXiv:1807.04518, doi:10.1137/18M1209854.
  15. [17]Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. ε-coresets for clustering (with outliers) in doubling metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 814–825. IEEE, 2018. arXiv:1804.02530, doi:10.1109/FOCS.2018.00082.DOI
  16. [18]Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In The Eleventh International Conference on Learning Representations, 2023. URL: https://openreview.net/forum?id=Nc1ZkRW8Vde.arxiv.org/abs/2210.10394
  17. [19]Lingxiao Huang, Zhenyu Jiang, Yi Li, and Xuan Wu. Towards tight robust coresets for k-medians clustering. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), pages 112:1–112:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. arXiv:2507.11260, doi:10.4230/LIPIcs.ICALP.2026.112.DOI
  18. [20]Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems, volume 32, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.html.arxiv.org/abs/1906.08484
  19. [21]Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4732–4782. SIAM, 2025. arXiv:2301.08460, doi:10.1137/1.9781611978322.161.DOI
  20. [22]Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for euclidean (k, z)-clustering. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1594–1604. ACM, 2024. doi:10.1145/3618260.3649707.DOI
  21. [23]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/01621459.1963.10500830.DOI
  22. [24]Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pages 291–300. ACM, 2004.
  23. [25]Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in Euclidean spaces: Importance sampling is nearly optimal. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1416–1429. ACM, 2020. doi:10.1145/3357713.3384296.DOI
  24. [26]Anil K. Jain. Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31(8):651–666, 2010. doi:10.1016/j.patrec.2009.09.011.DOI

Paper details

vlnc:W_w8g2dt3e
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents