Source-linked AI summary
Tight Coreset Bounds for Euclidean $(k,z)$-Clustering
Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu
TL;DR
For 0 < ε < k^-1/(z+2), prior lower bounds did not match the known upper bound, leaving the optimal Euclidean coreset size unresolved. The construction uses orthogonal projections to distinguish point coordinates and query levels to organize the points into cells. For every fixed real z ≥1, integer k ≥1, and 0 < ε < k−1/(z+2), a constructed dataset forces every ε-coreset to retain more than half these points.
Problem
For 0 < ε < k^-1/(z+2), prior lower bounds did not match the known upper bound, leaving the optimal Euclidean coreset size unresolved.
Source: §1 · p. 2Method
The construction uses orthogonal projections to distinguish point coordinates and query levels to organize the points into cells.
Source: §2.1 · p. 8, §2.2 · p. 9Results
For every fixed real z ≥1, integer k ≥1, and 0 < ε < k−1/(z+2), a constructed dataset forces every ε-coreset to retain more than half these points.
Source: §1.1 · p. 3, §1.2 · p. 7Takeaways & Limitations
Together with the larger-error lower bound, this determines the optimal coreset size across the stated error regimes.
Source: §1.1 · p. 3, §2.6 · p. 20A repetition-scale calculation alone cannot establish the lower bound because one weighted representative at each location preserves every query cost exactly.
Source: §1.2 · p. 4
Abstract
from arXiv · showhide
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 $\Omega_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 $\Omega_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\Theta_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\Theta(k^{4/3}\varepsilon^{-2})$ for $k$-median when $\varepsilon<k^{-1/3}$, and $\widetilde\Theta(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.
1 Introduction
The paper proves matching lower bounds for Euclidean (k, z)-clustering throughout the previously unmatched small-ε range, including arbitrarily small ε. Its technical overview explains how projection levels and shared-center queries detect omitted points despite arbitrary reweighting.
1 Introduction
- For ε < k^(-1/(z+2)), earlier lower bounds did not match the eO_z(k^((2z+2)/(z+2)) ε^-2) upper bound, leaving optimality open.Huang, Li, and Wu established a lower bound matching the known upper bound only for ε ≳_z k^(-1/(z+2)).Source: §1 · p. 2
1.1 Our Contributions
- At ε = k^-1/2, the k-means lower bound improves from Ω(k^9/4) to tilde-Ω(k^5/2); at ε = k^-1, it improves from Ω(k^3) [CALSS22] to tilde-Ω(k^7/2).These improve the bounds by factors of k^1/4 and k^1/2, respectively, up to polylogarithmic factors.Source: §1.1 · p. 3
- For every fixed real z ≥ 1, integer k ≥ 1, and 0 < ε < 1, Corollary 1.3 concerns the optimal worst-case coreset size for Euclidean (k, z)-clustering over datasets of unrestricted dimension.Source: §1.1 · p. 3
1.2 Technical Overview
- Projection levels encode unbiased four-wise independent signs, enabling opposite k-means queries to detect omissions despite arbitrary reweighting at relative-error scale Ω(1/(√n q L^2)).For general z, recalibrating the orthogonal center component makes the powered-cost difference use fixed coefficients, preserving the discrepancy argument; the scale remains 1/(√n q L^2).Source: §1.2 · pp. 5–7
2 Optimal Euclidean lower bound
This section constructs Euclidean instances for strong coreset lower bounds, using paired clustering queries and projection-based signs to detect omissions despite arbitrary reweighting. It extends the construction to every fixed real z ≥ 1 and establishes lower bounds in both small- and larger-error regimes.
2 Optimal Euclidean lower bound
- For every integer k≥1 and fixed z≥1, the section constructs a finite unweighted instance for the stated small-error range on which every strong ε-coreset must be large.With a different parameter choice, the construction also recovers the known eΩ_z(kε^−z−2) lower bound for k^−1/(z+2)≲_z ε<1.Source: §2 · p. 8
2.1 Construction of the dataset
- The dataset uses n separated copies of a Cartesian point set with |P|=nmq and |X|=n²mq, whose orthogonal projections recover the point indices.Each copy contains points arranged on n spheres, with offsets indexed by i and s.Source: §2.1 · p. 8
2.2 A family of query center sets
- For active copies, points are grouped by label and projection level, sharing one query center across sphere indices, so m(L + 1) centers suffice instead of nm(L + 1).Every point in an inactive copy has squared cost 2.Source: §2.2 · pp. 9–10
2.3 From geometric queries to a coreset error
- Paired queries cancel contributions outside the active points and yield a violating query whenever a weighted subset omits at least half of them, forcing every ε-coreset to retain more than half the dataset.A common projection direction and optimized signs produce the error gap, regardless of retained weights.Source: §2 · p. 8, §2.3 · p. 13
2.4 Proof of Lemma 2.1: projection levels and signs
- The projection construction selects distinct binary words with no four distinct words summing to zero, then encodes them as vectors whose projection levels and signs support a discrepancy bound.The supplied proof uses uniform averaging over sign arrays and notes a fourth-moment bound.Source: §2.1 · p. 9, §2.4 · pp. 14–15
- The projection-level signs are unbiased and four-wise independent.Odd-multiplicity products have zero expectation, and the fourth-moment calculation reduces to even multiplicity patterns.Source: §2.4 · p. 15
2.5 Extending the construction to general powers
- The calibrated construction extends to every fixed real z ≥ 1 while preserving the relative-error scale 1/(√nq L^2).The power-dependent gap n^((z−1)/2) and cost n^(z/2) leave that scale unchanged.Source: §2.5 · p. 19
2.6 Choosing parameters in all error regimes
- Every ε-coreset has size eΩ_z(k^((2z+2)/(z+2)) ε^-2) for 0 < ε ≤ k^-1/(z+2).When rounded construction parameters vanish, the known Ω_z(k ε^-2) bound or a k-point instance supplies the needed lower bound.Source: §2.6 · p. 20
- For k^-1/(z+2) ≤ ε < 1, the construction recovers the larger-error lower bound Ω_z(k ε^-z-2).For ε ≥ ε_z, a k-point instance gives Ω(k) = Ω_z(k ε^-z-2).Source: §2.6 · pp. 20–21