betaFeedback

Reading v1View latest version

WorksComputer Science

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

Abstract

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

Introduction

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

(k,z)(k,z)-clustering.

Given a finite dataset X⊆RdX\subseteq\mathbb{R}^d and an integer k≥1k\ge1, the goal is to find a set C⊆RdC\subseteq\mathbb{R}^d of kk centers minimizing

costz(X,C):=∑p∈Xdz(p,C),d(p,C):=min⁡c∈C∥p−c∥2.\begin{equation*} {\mathsf{cost}}_z(X,C):=\sum_{p\in X}d^z(p,C),\qquad d(p,C):=\min_{c\in C}\|p-c\|_2. \end{equation*}

This includes two classical clustering problems: kk-median (z=1z=1), which minimizes the sum of distances to the nearest center, and kk-means (z=2z=2), which minimizes the sum of squared distances. These objectives are widely used to represent a dataset by a small set of centers and have been extensively studied in data analysis, machine learning, and approximation algorithms [6].

Coresets.

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

Definition 1.1 (Coreset). For 0<ε<10<\varepsilon<1, an ε\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

∣costz(S,C)−costz(X,C)∣≤εcostz(X,C)for every C⊆Rd with ∣C∣=k,\begin{equation*} \bigl|{\mathsf{cost}}_z(S,C)-{\mathsf{cost}}_z(X,C)\bigr|\le\varepsilon{\mathsf{cost}}_z(X,C) \qquad\text{for every }C\subseteq\mathbb{R}^d\text{ with }|C|=k, \end{equation*}

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

A clustering algorithm can therefore run on a coreset instead of the full dataset while retaining nearly the same approximation guarantee. A smaller coreset reduces the amount of data processed by the algorithm. This has motivated a long line of work on clustering coresets in Euclidean, doubling, and graph metrics [8, 9, 20, 18, 19].

Determining the optimal coreset size in Euclidean space is a central question in this literature. Cohen-Addad, Saulpic, and Schwiegelshohn [5] described improving the Euclidean bounds as arguably “the most important open problem in coresets.” Despite substantial progress on constructions independent of the dimension, matching the dependence on kk and ε\varepsilon has remained difficult.

Cohen-Addad et al. [10] proved an Ωz(kε−2)\Omega_z(k\varepsilon^{-2}) lower bound and dimension-independent upper bounds. Subsequent work obtained 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 [11].1 These results left open whether the superlinear dependence on kk was necessary, or whether coresets of size O~(kε−2)\widetilde O(k\varepsilon^{-2}) always existed.

Huang, Li, and Wu [6] ruled out the latter possibility. They proved a lower bound of Ωz(kε−z−2)\Omega_z(k\varepsilon^{-z-2}) for ε≳zk−1/(z+2)\varepsilon\gtrsim_z k^{-1/(z+2)}, matching the known upper bound up to polylogarithmic factors. They also proved the upper bound O~z(k(2z+2)/(z+2)ε−2)\widetilde O_z(k^{(2z+2)/(z+2)}\varepsilon^{-2}) for every fixed z≥1z\ge1, extending the preceding bounds for kk-median and kk-means.

The bounds still did not match for 0<ε<k−1/(z+2)0<\varepsilon<k^{-1/(z+2)}. In the range k−(z+1)/(z+2)≲zε≲zk−1/(z+2)k^{-(z+1)/(z+2)}\lesssim_z\varepsilon\lesssim_z k^{-1/(z+2)}, Huang, Li, and Wu also proved the stronger lower bound Ωz(k(2z+3)/(z+2)ε−1)\Omega_z(k^{(2z+3)/(z+2)}\varepsilon^{-1}). Below k−(z+1)/(z+2)k^{-(z+1)/(z+2)}, the earlier Ωz(kε−2)\Omega_z(k\varepsilon^{-2}) bound was stronger. Neither matched O~z(k(2z+2)/(z+2)ε−2)\widetilde O_z(k^{(2z+2)/(z+2)}\varepsilon^{-2}) throughout 0<ε<k−1/(z+2)0<\varepsilon<k^{-1/(z+2)}, leaving the following question open:

Is O~z(k(2z+2)/(z+2)ε−2)\widetilde O_z(k^{(2z+2)/(z+2)}\varepsilon^{-2}) the optimal coreset size for every 0<ε<k−1/(z+2)0<\varepsilon<k^{-1/(z+2)}?

Our Contributions

We answer this question affirmatively, including for arbitrarily small ε\varepsilon.

Theorem 1.2 (Coreset lower bound). For every fixed real z≥1z\ge1, every integer k≥1k\ge1, and every 0<ε<k−1/(z+2)0<\varepsilon<k^{-1/(z+2)}, 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 Ω~z ⁣(k(2z+2)/(z+2)ε−2). \widetilde\Omega_z\!\left(k^{(2z+2)/(z+2)}\varepsilon^{-2}\right).

For kk-means, the previous lower bounds are Ω(k7/4ε−1)\Omega(k^{7/4}\varepsilon^{-1}) for k−3/4≲ε≲k−1/4k^{-3/4}\lesssim\varepsilon\lesssim k^{-1/4} and Ω(kε−2)\Omega(k\varepsilon^{-2}) for 0<ε≲k−3/40<\varepsilon\lesssim k^{-3/4}. At ε=k−1/2\varepsilon=k^{-1/2}, we improve the bound from Ω(k9/4)\Omega(k^{9/4}) [6] to Ω~(k5/2)\widetilde\Omega(k^{5/2}); at ε=k−1\varepsilon=k^{-1}, we improve it from Ω(k3)\Omega(k^3) [10] to Ω~(k7/2)\widetilde\Omega(k^{7/2}). These are improvements by factors of k1/4k^{1/4} and k1/2k^{1/2}, respectively, up to polylogarithmic factors.

Combining Theorem 1.2 with the known bounds [10, 6] gives the following characterization.

Corollary 1.3 (Optimal coreset size). For every fixed real z≥1z\ge1, integer k≥1k\ge1, and 0<ε<10<\varepsilon<1, the optimal worst-case coreset size for Euclidean (k,z)(k,z)-clustering, over datasets of unrestricted dimension, is Θ~z ⁣(min⁡{k(2z+2)/(z+2)ε−2, kε−z−2}). \widetilde\Theta_z\!\left(\min\left\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\right\}\right).

Technical Overview

We explain the lower bound Ω~(k3/2ε−2)\widetilde\Omega(k^{3/2}\varepsilon^{-2}) for kk-means when 0<ε<k−1/40<\varepsilon<k^{-1/4}, then extend the argument to general zz.

Revisiting the previous lower-bound construction.

At ε=Θ(k−1/4)\varepsilon=\Theta(k^{-1/4}), Huang, Li, and Wu [6] construct Θ(k2)\Theta(k^2) points in Θ(k)\Theta(\sqrt k) far-apart copies PbP_b. Within each copy, jj indexes spheres and ii labels offsets. Suppressing bb, the local points are

pj,i=k1/4ej+ui,\begin{equation*} p_{j,i}=k^{1/4}e_j+u_i, \end{equation*}

where eje_j is a coordinate direction, k1/4ejk^{1/4}e_j is sphere jj’s center, and uiu_i is a unit offset. Each copy has Θ(k)\Theta(\sqrt k) spheres and Θ(k)\Theta(k) almost orthogonal offsets. Each offset occurs on Θ(k)\Theta(\sqrt k) spheres, at most once per sphere, giving Θ(k3/2)\Theta(k^{3/2}) points per copy.

Suppose a putative coreset (S,w)(S,w) retains at most half the dataset. Choose an active copy P1P_1 with ∣S1∣≤∣P1∣/2|S_1|\le |P_1|/2, where S1=S∩P1S_1=S\cap P_1. The query CC uses one center cic_i for all occurrences of uiu_i in P1P_1. The term −2k1/4⟨ej,ci⟩-2k^{1/4}\langle e_j,c_i\rangle turns a constant change in cic_i’s eje_j-coordinate into a Θ(k1/4)\Theta(k^{1/4}) cost change on sphere jj. The other coordinates keep the center norms and ⟨ui,ci⟩\langle u_i,c_i\rangle fixed; the offset design preserves nearest-center assignments. Thus

d2(p,C)={B,p∈S1,B−γ,p∈P1∖S1,B=Θ(k),γ=Θ(k1/4).\begin{equation*} d^2(p,C)= \begin{cases} B,&p\in S_1,\\ B-\gamma,&p\in P_1\setminus S_1, \end{cases} \qquad B=\Theta(\sqrt k),\quad\gamma=\Theta(k^{1/4}). \end{equation*}

The cost difference can be reversed. The other copies use their sphere centers, at unit squared cost per point, and all centers together fit within the budget [6 Claim 2.2].

A distant-center query forces ∑p∈S1w(p)=(1±O(ε))∣P1∣\sum_{p\in S_1}w(p)=(1\pm O(\varepsilon))|P_1| [6 Claim 2.1]. Orienting the cost difference to avoid cancellation with the inactive error gives absolute error Ω(γ∣P1∣)−O(εB∣P1∣)\Omega(\gamma|P_1|)-O(\varepsilon B|P_1|). Since the active and total costs are both Θ(B∣P1∣)\Theta(B|P_1|), the relative error is at least

Ω(γ/B)−O(ε)=Ω(k−1/4)−O(ε).\begin{equation*} \Omega(\gamma/B)-O(\varepsilon)=\Omega(k^{-1/4})-O(\varepsilon). \end{equation*}

This proves the Ω(k2)\Omega(k^2) bound for a sufficiently small constant in ε=Θ(k−1/4)\varepsilon=\Theta(k^{-1/4}): one center controls an offset’s occurrences on many spheres.

Failed attempts.

Below ε=k−1/4\varepsilon=k^{-1/4}, the target polynomial size exceeds k2k^2. Repeating each point q≍k−1/2ε−2q\asymp k^{-1/2}\varepsilon^{-2} times gives a multiset XrepX_{\mathrm{rep}} of size Θ(k2q)\Theta(k^2q) and suggests the required error scale. Draw N=∣Xrep∣N=|X_{\mathrm{rep}}| uniform samples with replacement. Each location’s count has mean qq and standard deviation Θ(q)\Theta(\sqrt q). An active copy has Θ(k3/2)\Theta(k^{3/2}) locations with cost differences of order k1/4k^{1/4}, while the total cost is of order k2qk^2q. This suggests

k1/4⋅k3/2qk2q=k−1/4q≍k3/2N.\begin{equation*} \frac{k^{1/4}\cdot k^{3/2}\sqrt q}{k^2q} =\frac{k^{-1/4}}{\sqrt q} \asymp\sqrt{\frac{k^{3/2}}{N}}. \end{equation*}

Equating this expression to ε\varepsilon gives N≍k3/2ε−2N\asymp k^{3/2}\varepsilon^{-2}. But the calculation only motivates the scale: one representative of weight qq at each location preserves every query cost exactly, so sampling fluctuations cannot rule out arbitrary reweighting.

A second attempt replaces uiu_i by distinct offsets ui,su_{i,s}:

pj,i,s=k1/4ej+ui,s,s∈[q].\begin{equation*} p_{j,i,s}=k^{1/4}e_j+u_{i,s},\qquad s\in[q]. \end{equation*}

One center per replacement requires Θ(kq)\Theta(kq) active centers, exceeding kk as qq grows. If instead the offsets with s∈G⊆[q]s\in G\subseteq[q] share ci,Gc_{i,G} across spheres, their distance to that center contains the common term

−2k1/4⟨ej,ci,G⟩for every s∈G.\begin{equation*} -2k^{1/4}\langle e_j,c_{i,G}\rangle \qquad\text{for every }s\in G. \end{equation*}

Changing ⟨ej,ci,G⟩\langle e_j,c_{i,G}\rangle cannot reproduce the costs BB and B−γB-\gamma for retained and omitted replacements in the same group while the other distance terms remain fixed. A common cost change on this group changes the coreset error by that amount times ∑s∈G(w(pj,i,s)−1)\sum_{s\in G}(w(p_{j,i,s})-1), with w=0w=0 on omitted points. The replacements must therefore admit groupings using few centers that detect these aggregate discrepancies despite arbitrary reweighting. We state the required properties next.

Identifying the properties needed from the new offsets.

We keep equal-sized, far-apart copies. For any (S,w)(S,w) retaining at most half of the new dataset XX, choose an active copy P1P_1 with at least half its points omitted. We require:

  1. Distinct replacements. Each label’s qq replacements on a sphere are distinct, preventing compression of repeated points into a single representative.

  2. Few centers per grouping. Each label admits partitions into polylogarithmically many groups, with one center per group shared across spheres.

  3. Balanced costs. Every query satisfies cost2(P1,C)≍cost2(X,C)≍∣X∣{\mathsf{cost}}_2(P_1,C)\asymp{\mathsf{cost}}_2(X,C)\asymp |X|, so inactive costs do not dilute the active error.

  4. Error under arbitrary reweighting. Some query has absolute coreset error Ω~(k1/4∣P1∣/q)\widetilde\Omega(k^{1/4}|P_1|/\sqrt q), assuming only that at least half of P1P_1 is omitted, not half of each group.

The dataset and query family are fixed before (S,w)(S,w); only the active copy and witnessing query depend on it. With Θ(k)\Theta(\sqrt k) copies, P3 turns P4 into the relative-error scale suggested by repetition.

Constructing the dataset and sharing centers.

Keep bb for copies, jj for spheres, and ii for labels; ss indexes a label’s replacements. Take nn far-apart copies, each with nn spheres and mm labels. Now choose the uiu_i to be orthonormal, and replace each label’s single offset by {ui+xs:s∈[q]}\{u_i+x_s:s\in[q]\}. The local configuration is

P={pj,i,s=n ej+ui+xs:j∈[n], i∈[m], s∈[q]}.\begin{equation*} P=\{p_{j,i,s}=\sqrt n\,e_j+u_i+x_s:j\in[n],\ i\in[m],\ s\in[q]\}. \end{equation*}

The eje_j, the uiu_i, and the distinct unit vectors xsx_s lie in three mutually orthogonal subspaces; the xsx_s need not be mutually orthogonal. Every offset now occurs on every sphere. All triples are distinct, each at distance 2\sqrt2 from its sphere center n ej\sqrt n\,e_j, so ∣P∣=nmq|P|=nmq and ∣X∣=n2mq|X|=n^2mq, giving P1.

Fix (S,w)(S,w) and an active copy P1P_1 as above; use local coordinates for its points and query centers. Lemma 2.1 supplies the xsx_s and a fixed family VV of directions with

⟨xs,v⟩=tℓ(s;v),tℓ=1−2ℓL,0≤ℓ≤L,\begin{equation*} \langle x_s,v\rangle=t_{\ell(s;v)},\qquad t_\ell=1-\frac{2\ell}{L},\qquad 0\le\ell\le L, \end{equation*}

Here ℓ(s;v)\ell(s;v) is the level index of xsx_s, and L=O(log⁡(q+1))L=O(\log(q+1)). We will construct one center ci,ℓc_{i,\ell} serving all points of label ii and level ℓ\ell across spheres. Inactive copies use their n(n−1)n(n-1) sphere centers, giving the budget

n(n−1)+m(L+1)≤k.\begin{equation*} n(n-1)+m(L+1)\le k. \end{equation*}

Thus a query needs m(L+1)m(L+1) active centers instead of mqmq. Changing vv changes the grouping without increasing this count. A fixed partition with equal costs within each sphere–label–level group could be compressed to one weighted representative per group. To ensure that some grouping detects omissions, Lemma 2.1 also makes (−1)ℓ(s;v)(-1)^{\ell(s;v)} unbiased four-wise independent signs for uniform v∈Vv\in V. Their discrepancy guarantee, used below, is what rules out such compression across all queries.

Figure 1. Geometry of the active copy (z=2z=2; schematic sectional views). (a) Spheres centered at aj=n eja_j=\sqrt n\,e_j repeat the same offset groups. (b) Both labels on one enlarged sphere: black arrows show u1,u2u_1,u_2, colored solid arrows show xsx_s in their perpendicular sections, and dashed arrows show ui+xsu_i+x_s, ending on the sphere of radius 2\sqrt2. Each same-colored pair forms a cell and shares the matching nearest center (diamond) across all spheres. We illustrate levels ℓ=0,3,6\ell=0,3,6 for L=6L=6. The two offset sections are shown in local three-dimensional frames; relative lengths and query-center positions are not to scale.

Realizing level costs with shared centers.

For signs σ=(σji)∈{−1,1}n×m\sigma=(\sigma_{ji})\in\{-1,1\}^{n\times m}, let C(v,σ)C(v,\sigma) contain the active centers, the inactive sphere centers, and remote centers padding the count to kk. The active costs are

d2(pj,i,s,C(v,σ))=Dℓ(s;v)+n8L2σji(−1)ℓ(s;v),Dℓ=Θ(n),\begin{equation} d^2(p_{j,i,s},C(v,\sigma)) =D_{\ell(s;v)}+\frac{\sqrt n}{8L^2}\sigma_{ji}(-1)^{\ell(s;v)}, \qquad D_\ell=\Theta(n), \tag*{(1)} \end{equation}

where the DℓD_\ell are the baselines in Eq. (7), independent of v,σv,\sigma. The sphere-axis component of ci,ℓc_{i,\ell} is proportional to −(−1)ℓ∑jσjiej-(-1)^\ell\sum_j\sigma_{ji}e_j, encoding one sign per sphere without changing its norm when signs are reversed. The label component separates labels. For a point at level ℓ\ell, the projection component and an orthogonal norm adjustment make a competing level ℓ′\ell' incur the penalty n(tℓ′−tℓ)2\sqrt n(t_{\ell'}-t_\ell)^2. With grid spacing 2/L2/L, this penalty dominates any change in the signed term. Claim 2.2 verifies that ci,ℓ(s;v)c_{i,\ell(s;v)} remains nearest for every σ\sigma, giving P2. Inactive points have squared cost 22, so the active and total costs are both Θ(n∣P1∣)=Θ(∣X∣)\Theta(n|P_1|)=\Theta(|X|), giving P3.

Defeating arbitrary reweighting with opposite queries.

Extend ww by zero to omitted points, and write Δ(C)=cost2(S,C)−cost2(X,C)\Delta(C)={\mathsf{cost}}_2(S,C)-{\mathsf{cost}}_2(X,C). The queries C(v,σ)C(v,\sigma) and C(v,−σ)C(v,-\sigma) have identical baselines and inactive costs. Subtracting their signed errors gives

Δ(C(v,σ))−Δ(C(v,−σ))=n4L2∑j,iσji∑s(w(pj,i,s)−1)(−1)ℓ(s;v).\begin{equation*} \Delta(C(v,\sigma))-\Delta(C(v,-\sigma)) =\frac{\sqrt n}{4L^2}\sum_{j,i}\sigma_{ji} \sum_s(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}. \end{equation*}

The common weighted costs cancel exactly, without any bound on the retained weights. For each fixed vv, choose σji\sigma_{ji} to match the sign of its inner sum. Lemma 2.1 then supplies one common direction with

max⁡v∈V∑j,i∣∑s(w(pj,i,s)−1)(−1)ℓ(s;v)∣≥13∑j,i(∑s(w(pj,i,s)−1)2)1/2≥∣P1∣23q.\begin{align*} \max_{v\in V}\sum_{j,i}\left|\sum_s(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}\right| &\ge\frac1{\sqrt3}\sum_{j,i}\left(\sum_s(w(p_{j,i,s})-1)^2\right)^{1/2}\\ &\ge\frac{|P_1|}{2\sqrt{3q}}. \end{align*}

For the last inequality, each omitted point contributes 11 to a squared discrepancy. Each qq-point group’s norm is at least its number of omissions divided by q\sqrt q, and P1P_1 omits at least half its points. Only the sum must be large for the common direction; different groups need not attain their maxima there.

The opposite queries therefore have signed errors differing by Ω(n ∣P1∣/(L2q))\Omega(\sqrt n\,|P_1|/(L^2\sqrt q)). At least one query has absolute error at least half this difference. Dividing by its true cost Θ(n∣P1∣)\Theta(n|P_1|) yields relative error Ω(1/(nq L2))\Omega(1/(\sqrt{nq}\,L^2)). For n≍kn\asymp\sqrt k, this proves P4 and recovers the scale suggested by repetition, now for every reweighting. Proposition 2.3 formalizes this argument.

Choosing parameters to obtain the lower bound.

The center budget permits n≍kn\asymp\sqrt k and m≍k/Lm\asymp k/L; the relative error exceeds ε\varepsilon when εnq L2\varepsilon\sqrt{nq}\,L^2 is sufficiently small. In the principal range, Lemma 2.5 meets these requirements with

L≍log⁡(2+k−1/4ε−1),q≍k−1/2ε−2L4,∣X∣=n2mq≍k3/2ε−2L5.\begin{equation*} L\asymp\log(2+k^{-1/4}\varepsilon^{-1}),\qquad q\asymp\frac{k^{-1/2}\varepsilon^{-2}}{L^4},\qquad |X|=n^2mq\asymp\frac{k^{3/2}\varepsilon^{-2}}{L^5}. \end{equation*}

Every coreset must retain more than half these points, proving the lower bound.2

Extension to a general power zz.

For z≠2z\ne2, raising Eq. (1) to z/2z/2 produces a level-dependent difference between opposite queries. Since ℓ(s;v)\ell(s;v) changes with vv, the coefficient of (−1)ℓ(s;v)(-1)^{\ell(s;v)} in the error sum would vary with the direction. The discrepancy lemma requires fixed coefficients; constant-factor estimates cannot substitute for equality in this signed sum.

Choose a sphere-axis displacement δℓ\delta_\ell for each level so that

(Dℓ+2n δℓ)z/2−(Dℓ−2n δℓ)z/2=n(z−1)/232L2.\begin{equation*} (D_\ell+2\sqrt n\,\delta_\ell)^{z/2} -(D_\ell-2\sqrt n\,\delta_\ell)^{z/2} =\frac{n^{(z-1)/2}}{32L^2}. \end{equation*}

Readjusting the orthogonal center component preserves DℓD_\ell. Monotonicity and the mean value theorem allow this calibration within the displacement bound that preserves assignments; see § 2.5. The powered-cost difference is now a fixed coefficient times σji(−1)ℓ(s;v)\sigma_{ji}(-1)^{\ell(s;v)}, so the same discrepancy argument applies.

An active point costs Θz(nz/2)\Theta_z(n^{z/2}). Using ⌈nz/2⌉\lceil n^{z/2}\rceil copies, each with nn spheres, preserves the cost balance and uses O(n(z+2)/2)O(n^{(z+2)/2}) inactive centers. The relative-error scale remains 1/(nq L2)1/(\sqrt{nq}\,L^2). Hence taking n≍zk2/(z+2)n\asymp_z k^{2/(z+2)}, L≍log⁡(2+k−1/(z+2)ε−1)L\asymp \log(2+k^{-1/(z+2)}\varepsilon^{-1}), m≍k/Lm\asymp k/L, and q≍zε−2/(nL4)q\asymp_z\varepsilon^{-2}/(nL^4) gives

∣X∣=⌈nz/2⌉nmq=Θ~z(k(2z+2)/(z+2)ε−2).\begin{equation*} |X|=\lceil n^{z/2}\rceil nmq =\widetilde\Theta_z(k^{(2z+2)/(z+2)}\varepsilon^{-2}). \end{equation*}

§ 2.6 completes the integer and boundary cases.

Sharper bounds for clustering coresets.

Bansal et al. [7] showed that sensitivity sampling constructs Euclidean kk-means coresets of size O~(kε−2min⁡{k,ε−2})\widetilde O(k\varepsilon^{-2}\min\{\sqrt{k},\varepsilon^{-2}\}). For instances with constant cost stability, the same algorithm achieves size O~(kε−2)\widetilde O(k\varepsilon^{-2}) without knowing the stability parameter. Beyond Euclidean spaces, Cohen-Addad et al. [13] developed a sharp VC-dimension-based analysis, obtaining improved kk-median coreset bounds, including O~(kε−2)\widetilde O(k\varepsilon^{-2}) for shortest-path metrics in planar graphs.

Coresets for constrained clustering.

Coresets for capacitated and fair clustering, as well as more general assignment constraints, have been studied extensively [2, 3, 12, 15, 1]. For Euclidean capacitated (k,z)(k,z)-clustering with fixed z≥1z\ge1, Huang et al. [15] obtained coresets of size O~z(k2ε−2z−2)\widetilde O_z(k^2\varepsilon^{-2z-2}).3

Coresets for robust clustering.

Coresets for clustering with outliers have also received substantial attention [4, 15, 16, 17, 14]. For Euclidean (k,z)(k,z)-clustering with mm outliers and fixed z≥1z\ge1, Huang et al. [14] obtained coresets of size O(mε−z)+O~z(min⁡{k(2z+2)/(z+2)ε−2,kε−z−2})O(m\varepsilon^{-z})+\widetilde O_z(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},k\varepsilon^{-z-2}\}), and an alternative bound of O(m)+O~z(kε−2z−2)O(m)+\widetilde O_z(k\varepsilon^{-2z-2}).

Optimal Euclidean lower bound

This section proves Theorem 1.2: for every integer k≥1k\ge1, fixed real z≥1z\ge1, and 0<ε≲zk−1/(z+2)0<\varepsilon\lesssim_z k^{-1/(z+2)}, we construct a finite unweighted instance X⊆RdX\subseteq\mathbb{R}^d such that every strong ε\varepsilon-coreset has size Ω~z ⁣(k2z+2z+2ε−2)\widetilde{\Omega}_z\!\left(k^{\frac{2z+2}{z+2}}\varepsilon^{-2}\right). With a different parameter choice, the same construction also recovers the known Ω~z(kε−z−2)\widetilde{\Omega}_z(k\varepsilon^{-z-2}) lower bound in the large-error regime k−1/(z+2)≲zε<1k^{-1/(z+2)}\lesssim_z\varepsilon<1. We first treat z=2z=2 and 0<ε<k−1/40<\varepsilon<k^{-1/4}, then extend the argument to general zz and the remaining error range.

The proof combines a geometric construction, Proposition 2.3, and the parameter choice in Lemma 2.5. We first form a dataset from well-separated copies of the same point set. Any weighted subset containing at most half of the data points must omit at least half of the points in one copy. In that copy, we use two query center sets with opposite perturbations: their nearest-center assignments agree, while subtracting their signed errors cancels all terms independent of the perturbations. Optimizing the perturbation signs and then applying a discrepancy lemma yields a common projection direction with a large error gap, regardless of the retained weights. Finally, we choose the parameters so that the center budget is respected and at least one query violates the coreset guarantee.

Construction of the dataset

We follow the far-apart-copy framework of [6], in which each copy contains points on spheres centered along coordinate axes. Our construction splits each offset into two orthogonal components and uses one of them to group the points more finely. Let n,m,q,L≥1n,m,q,L\ge1 be integer parameters to be chosen later. For now, assume that 2L>q+(q3)2^L>q+\binom q3, as required by Lemma 2.1; we verify this condition when choosing the parameters. The dataset X⊆RdX\subseteq\mathbb{R}^d, where d=n+m+2L+1d=n+m+2L+1, consists of nn sufficiently separated translates of the set

pj,i,s=n ej+ui+xs,P={pj,i,s:j∈[n], i∈[m], s∈[q]}.\begin{equation} p_{j,i,s}=\sqrt n\,e_j+u_i+x_s,\qquad P=\{p_{j,i,s}:j\in[n],\ i\in[m],\ s\in[q]\}. \tag*{(2)} \end{equation}

Here e1,…,ene_1,\ldots,e_n and u1,…,umu_1,\ldots,u_m are orthonormal bases of mutually orthogonal subspaces Rn\mathbb{R}^n and Rm\mathbb{R}^m. The distinct unit vectors x1,…,xqx_1,\ldots,x_q lie in a third orthogonal subspace R2L\mathbb{R}^{2L}; fix them, together with the set V⊆R2LV\subseteq\mathbb{R}^{2L}, as supplied by Lemma 2.1 below. We reserve the remaining dimension, with unit vector ff, for adjusting center norms. Thus PP is the Cartesian product, embedded in orthogonal subspaces, of {n ej:j∈[n]}\{\sqrt n\,e_j:j\in[n]\}, {ui:i∈[m]}\{u_i:i\in[m]\}, and {xs:s∈[q]}\{x_s:s\in[q]\}. The three orthogonal projections recover jj, ii, and ss, respectively, so different triples give different points. Consequently, ∣P∣=nmq|P|=nmq and ∣X∣=n2mq|X|=n^2mq.

For each point in the jjth group, ∥pj,i,s−n ej∥2=∥ui+xs∥2=2\left\| p_{j,i,s}-\sqrt n\,e_j \right\|^2 =\left\| u_i+x_s \right\|^2=2.

Thus, in local coordinates, each copy lies on nn spheres of radius 2\sqrt2, centered at n ej\sqrt n\,e_j for j∈[n]j\in[n]. The jjth sphere contains the mqmq points n ej+ui+xs\sqrt n\,e_j+u_i+x_s, indexed by i∈[m]i\in[m] and s∈[q]s\in[q]. Our queries will incur squared cost Θ(n)\Theta(n) per point in one copy, to be designated the active copy later; using nn copies keeps this contribution of order ∣X∣|X|. The following lemma supplies vectors with few projection levels and a common discrepancy witness. We will later apply it to the coreset weight discrepancies within the active copy.

Lemma 2.1 (Discrete projections and a discrepancy bound). Let L,q≥1L,q\ge1 be integers satisfying 2L>q+(q3)2^L>q+\binom q3. There exist distinct vectors x1,…,xq∈R2Lx_1,\ldots,x_q\in\mathbb{R}^{2L} and a nonempty finite set V⊆R2LV\subseteq\mathbb{R}^{2L} with the following properties:

  • Every xsx_s has norm 11, and every v∈Vv\in V has squared norm 22.

  • For every s∈[q]s\in[q] and v∈Vv\in V, ⟨xs,v⟩∈{1−2ℓL:ℓ∈{0,…,L}}. \left\langle x_s,v\right\rangle\in\left\{1-\frac{2\ell}{L}:\ell\in\{0,\ldots,L\}\right\}. Define the level index ℓ(s;v)∈{0,…,L}\ell(s;v)\in\{0,\ldots,L\} by ⟨xs,v⟩=1−2ℓ(s;v)/L\left\langle x_s,v\right\rangle=1-2\ell(s;v)/L.

  • For every integer t≥1t\ge1 and every collection of fixed coefficient vectors A(1),…,A(t)∈RqA^{(1)},\ldots,A^{(t)}\in\mathbb{R}^q, max⁡v∈V∑r=1t∣∑s=1qAs(r)(−1)ℓ(s;v)∣≥13∑r=1t∥A(r)∥2. \max_{v\in V}\sum_{r=1}^t\left|\sum_{s=1}^q A_s^{(r)}(-1)^{\ell(s;v)}\right| \ge\frac1{\sqrt3}\sum_{r=1}^t\|A^{(r)}\|_2.

The vectors xsx_s and the set VV depend only on L,qL,q, not on the coefficient vectors.

The proof is deferred to § 2.4. Each v∈Vv\in V groups the indices s∈[q]s\in[q] according to their projection levels ℓ(s;v)\ell(s;v). Having only L+1L+1 levels allows the construction in § 2.2 to use just L+1L+1 centers for each i∈[m]i\in[m]. Varying vv allows both the grouping and the parity signs (−1)ℓ(s;v)(-1)^{\ell(s;v)} to change; the discrepancy bound guarantees a common choice that produces a large coreset error, as shown in § 2.3.

A family of query center sets

Fix a weighted subset (S,w)(S,w) with ∣S∣≤∣X∣/2|S|\le|X|/2. We construct query center sets that will show that (S,w)(S,w) cannot be an ε\varepsilon-coreset once the parameters are chosen appropriately. Since the copies have equal size, some copy contains at most half its points in SS. Denote it by P1P_1 and call it the active copy; the remaining copies are inactive. We use adjustable centers for P1P_1 and place one fixed center at each sphere center in every inactive copy. Below, we use local coordinates for P1P_1 and write its points as pj,i,sp_{j,i,s}; all centers assigned to this copy receive the same translation as its points. In this notation, w(pj,i,s)w(p_{j,i,s}) denotes the weight of the corresponding translated point in P1P_1, and is zero when that point is omitted from SS. Thus the weight-discrepancy vectors are (w(pj,i,s)−1)s=1q(w(p_{j,i,s})-1)_{s=1}^q, indexed by (j,i)∈[n]×[m](j,i)\in[n]\times[m].

We call i∈[m]i\in[m] the label of the offsets ui+xsu_i+x_s and their corresponding points on each sphere. For a fixed v∈Vv\in V, the level of pj,i,sp_{j,i,s} is ℓ(s;v)\ell(s;v), determined by ⟨xs,v⟩=1−2ℓ(s;v)/L\left\langle x_s,v\right\rangle=1-2\ell(s;v)/L. The points on sphere jj with label ii and level ℓ\ell form the cell

Xj,i,ℓ(v)={pj,i,s:s∈[q], ℓ(s;v)=ℓ},j∈[n],i∈[m],0≤ℓ≤L.\begin{equation*} X_{j,i,\ell}(v)=\{p_{j,i,s}:s\in[q],\ \ell(s;v)=\ell\},\qquad j\in[n],\quad i\in[m],\quad 0\le\ell\le L. \end{equation*}

Cells may be empty. The same grouping applies on every sphere: labels are fixed, whereas levels may change with vv. We will use one center for all cells with the same label and level, regardless of the sphere index jj. Thus the active copy needs m(L+1)m(L+1) centers rather than nm(L+1)nm(L+1). Figure 1 illustrates the offsets, cells, and shared query centers.

Our family C(v,σ)C(v,\sigma) is parameterized by v∈Vv\in V and a sign array σ∈{−1,1}n×m\sigma\in\{-1,1\}^{n\times m}. For each fixed vv, we want the nearest-center assignments to be independent of σ\sigma. For a point on sphere jj with label ii and level ℓ\ell, its squared cost should consist of a sign-independent baseline depending only on ℓ\ell, plus a perturbation proportional to σji(−1)ℓ\sigma_{ji}(-1)^\ell with the same positive coefficient for all points. Let tℓ:=1−2ℓ/Lt_\ell:=1-2\ell/L be the ℓ\ellth projection value in (3). For each (i,ℓ)∈[m]×{0,…,L}(i,\ell)\in[m]\times\{0,\ldots,L\}, define the local center

ci,ℓ(v,σ)=2n ui+n tℓv−(−1)ℓ16L2∑j=1nσjiej+λℓf,\begin{equation} c_{i,\ell}(v,\sigma) =2\sqrt n\,u_i+\sqrt n\,t_\ell v -\frac{(-1)^\ell}{16L^2}\sum_{j=1}^n\sigma_{ji}e_j+\lambda_\ell f, \tag*{(5)} \end{equation}

where ff is the unit vector reserved for norm adjustment. Choose

λℓ=(4n+(n−2n)tℓ2−n256L4)1/2.\begin{equation*} \lambda_\ell =\left(4n+(\sqrt n-2n)t_\ell^2-\frac{n}{256L^4}\right)^{1/2}. \end{equation*}

The square root is well-defined: n−2n≤0\sqrt n-2n\le0, tℓ2≤1t_\ell^2\le1, and L≥1L\ge1 imply that its radicand satisfies

4n+(n−2n)tℓ2−n256L4≥511256n+n>0.\begin{equation*} 4n+(\sqrt n-2n)t_\ell^2-\frac{n}{256L^4} \ge\frac{511}{256}n+\sqrt n>0. \end{equation*}

The sign component has squared norm

∥∑j=1nσjiej∥2=∑j=1nσji2=n.\begin{equation*} \left\|\sum_{j=1}^n\sigma_{ji}e_j\right\|^2 =\sum_{j=1}^n\sigma_{ji}^2=n. \end{equation*}

The remaining norms are ∥ui∥=∥f∥=1\left\| u_i \right\|=\left\| f \right\|=1 and ∥v∥2=2\left\| v \right\|^2=2, the latter by Lemma 2.1. Combining these values with the sign-norm calculation gives

∥ci,ℓ(v,σ)∥2=4n+2ntℓ2+n256L4+λℓ2=8n+n tℓ2.\begin{equation} \begin{aligned} \left\| c_{i,\ell}(v,\sigma) \right\|^2 &=4n+2nt_\ell^2+\frac{n}{256L^4}+\lambda_\ell^2\\ &=8n+\sqrt n\,t_\ell^2. \end{aligned} \tag*{(6)} \end{equation}

In particular, this norm is independent of vv and σ\sigma. We include a center for every label–level pair, even when its cells are empty. Different labels have different uiu_i-components; for a fixed label, different levels have different vv-components because the values tℓt_\ell are distinct and ∥v∥2=2\left\| v \right\|^2=2. Thus the m(L+1)m(L+1) active centers are distinct.

The full center set contains these m(L+1)m(L+1) active centers and the n(n−1)n(n-1) fixed sphere centers in the inactive copies. Lemma 2.5 will ensure that m(L+1)+n(n−1)≤km(L+1)+n(n-1)\le k. We obtain exactly kk distinct centers by placing the remaining centers sufficiently far from XX, using the same additional centers for every query. The following claim verifies the assignments and costs of the resulting center sets.

Claim 2.2 (Nearest centers and costs). For every v∈Vv\in V and σ∈{−1,1}n×m\sigma\in\{-1,1\}^{n\times m}, the center set C(v,σ)C(v,\sigma) has the following properties:

  • Nearest-center assignment. For every j∈[n]j\in[n], i∈[m]i\in[m], and 0≤ℓ≤L0\le\ell\le L, the unique nearest center of each point p∈Xj,i,ℓ(v)p\in X_{j,i,\ell}(v) is ci,ℓ(v,σ)c_{i,\ell}(v,\sigma).

  • Pointwise costs. For every p∈Xj,i,ℓ(v)p\in X_{j,i,\ell}(v),

    d2(p,C(v,σ))=Dℓ+n8L2σji(−1)ℓ,\begin{equation} d^2(p,C(v,\sigma))=D_\ell+\frac{\sqrt n}{8L^2}\sigma_{ji}(-1)^\ell, \tag*{(7)} \end{equation}

    where Dℓ=9n+2−4n−n tℓ2D_\ell=9n+2-4\sqrt n-\sqrt n\,t_\ell^2, and

    5n≤d2(p,C(v,σ))≤9n.\begin{equation} 5n\le d^2(p,C(v,\sigma))\le9n. \tag*{(8)} \end{equation}

    Every point in an inactive copy has squared cost 22.

  • Total cost. The full dataset satisfies

    cost2(X,C(v,σ))≤11∣X∣.\begin{equation*} {\mathsf{cost}}_2(X,C(v,\sigma))\le11|X|. \end{equation*}

Proof. Fix p=pj,i,s∈Xj,i,ℓ(v)p=p_{j,i,s}\in X_{j,i,\ell}(v), so that ⟨xs,v⟩=tℓ\left\langle x_s,v\right\rangle=t_\ell. First,

∥p∥2=n+2.\begin{equation*} \left\| p \right\|^2=n+2. \end{equation*}

For any candidate indices i′∈[m]i'\in[m] and 0≤ℓ′≤L0\le\ell'\le L, bilinearity and orthogonality give

⟨p,ci′,ℓ′(v,σ)⟩=2n 1{i′=i}+n tℓtℓ′−n16L2(−1)ℓ′σji′.\begin{equation*} \left\langle p,c_{i',\ell'}(v,\sigma)\right\rangle =2\sqrt n\,\mathbf{1}_{\{i'=i\}} +\sqrt n\,t_\ell t_{\ell'} -\frac{\sqrt n}{16L^2}(-1)^{\ell'}\sigma_{ji'}. \end{equation*}

Substituting these quantities and (6) into the squared-distance identity gives

∥p−ci′,ℓ′(v,σ)∥2=9n+2+n tℓ′2−4n 1{i′=i}−2n tℓtℓ′+n8L2(−1)ℓ′σji′=Dℓ+n(tℓ′−tℓ)2⏟level penalty+4n 1{i′≠i}⏟label penalty+n8L2(−1)ℓ′σji′⏟sign perturbation.\begin{align*} &\left\| p-c_{i',\ell'}(v,\sigma) \right\|^2\\ &\quad=9n+2+\sqrt n\,t_{\ell'}^2 -4\sqrt n\,\mathbf{1}_{\{i'=i\}} -2\sqrt n\,t_\ell t_{\ell'} +\frac{\sqrt n}{8L^2}(-1)^{\ell'}\sigma_{ji'}\\ &\quad=D_\ell +\underbrace{\sqrt n(t_{\ell'}-t_\ell)^2}_{\text{level penalty}} +\underbrace{4\sqrt n\,\mathbf{1}_{\{i'\ne i\}}}_{\text{label penalty}} +\underbrace{\frac{\sqrt n}{8L^2}(-1)^{\ell'}\sigma_{ji'}}_{\text{sign perturbation}}. \end{align*}

Here the square completion uses the two identities

n tℓ′2−2n tℓtℓ′=n(tℓ′−tℓ)2−n tℓ2,−4n 1{i′=i}=−4n+4n 1{i′≠i}.\begin{align*} \sqrt n\,t_{\ell'}^2-2\sqrt n\,t_\ell t_{\ell'} &=\sqrt n(t_{\ell'}-t_\ell)^2-\sqrt n\,t_\ell^2,\\ -4\sqrt n\,\mathbf{1}_{\{i'=i\}} &=-4\sqrt n+4\sqrt n\,\mathbf{1}_{\{i'\ne i\}}. \end{align*}

The uiu_i- and vv-components produce the label and level penalties. The norm adjustment changes no inner product with the data, supplies the quadratic term needed to complete the square, and keeps the common cost of order nn.

Both penalties vanish at (i′,ℓ′)=(i,ℓ)(i',\ell')=(i,\ell). If ℓ′≠ℓ\ell'\ne\ell, then

∣tℓ′−tℓ∣=2∣ℓ′−ℓ∣L≥2L.\begin{equation*} |t_{\ell'}-t_\ell|=\frac{2|\ell'-\ell|}{L}\ge\frac2L. \end{equation*}

A wrong level therefore incurs at least 4n/L24\sqrt n/L^2. A wrong label incurs 4n≥4n/L24\sqrt n\ge4\sqrt n/L^2, since L≥1L\ge1. Meanwhile,

∣(−1)ℓ′σji′−(−1)ℓσji∣≤2.\begin{equation*} \left|(-1)^{\ell'}\sigma_{ji'}-(-1)^\ell\sigma_{ji}\right|\le2. \end{equation*}

Consequently, whenever (i′,ℓ′)≠(i,ℓ)(i',\ell')\ne(i,\ell),

∥p−ci′,ℓ′(v,σ)∥2−∥p−ci,ℓ(v,σ)∥2≥4nL2−n4L2=15n4L2>0.\begin{align*} &\left\| p-c_{i',\ell'}(v,\sigma) \right\|^2-\left\| p-c_{i,\ell}(v,\sigma) \right\|^2\\ &\quad\ge\frac{4\sqrt n}{L^2}-\frac{\sqrt n}{4L^2} =\frac{15\sqrt n}{4L^2}>0. \end{align*}

Thus ci,ℓ(v,σ)c_{i,\ell}(v,\sigma) is the unique nearest active center. Substituting (i′,ℓ′)=(i,ℓ)(i',\ell')=(i,\ell) removes both penalties and yields (7). The signs σji\sigma_{ji} will align the error contributions across pairs (j,i)(j,i), while (−1)ℓ(-1)^\ell distinguishes even and odd levels. Hence the cost changes reflect the distribution of weights across levels, not merely their total mass.

For completeness, the constants in (8) follow from explicit upper and lower estimates. The lower estimate is

∥p−ci,ℓ(v,σ)∥2≥9n+2−418n(tℓ2≤1, L≥1)≥103n−916≥5n(2n≤n+1, n≥1).\begin{align*} \left\| p-c_{i,\ell}(v,\sigma) \right\|^2 &\ge9n+2-\frac{41}{8}\sqrt n \qquad\text{($t_\ell^2\le1$, $L\ge1$)}\\ &\ge\frac{103n-9}{16}\ge5n \qquad\text{($2\sqrt n\le n+1$, $n\ge1$)}. \end{align*}

For the upper estimate,

∥p−ci,ℓ(v,σ)∥2≤9n+2−318n(tℓ2≥0, L≥1)≤9n.\begin{align*} \left\| p-c_{i,\ell}(v,\sigma) \right\|^2 &\le9n+2-\frac{31}{8}\sqrt n \qquad\text{($t_\ell^2\ge0$, $L\ge1$)}\\ &\le9n. \end{align*}

The same estimates hold for any sign perturbation whose absolute value is at most n/(8L2)\sqrt n/(8L^2), a fact used in the general-zz extension.

We also verify that no center from another copy can be closer. In local coordinates,

∥p∥2=n+2≤3n,∥ci,ℓ(v,σ)∥2≤8n+n≤9n,∥n ej∥2=n,\begin{equation*} \left\| p \right\|^2=n+2\le3n,\qquad \left\| c_{i,\ell}(v,\sigma) \right\|^2\le8n+\sqrt n\le9n,\qquad \left\| \sqrt n\,e_j \right\|^2=n, \end{equation*}

where the middle bound uses (6) and n≥1n\ge1. Thus all local points and centers have norm at most 3n3\sqrt n. The copies can be fixed in advance with translation vectors separated by at least 20n20\sqrt n. The reverse triangle inequality then gives a cross-copy distance of at least 20n−3n−3n=14n20\sqrt n-3\sqrt n-3\sqrt n=14\sqrt n, whereas the triangle inequality gives a within-copy distance of at most 6n6\sqrt n. This separation is uniform over vv and σ\sigma.

In an inactive copy, the squared distance from pj,i,sp_{j,i,s} to sphere center n ej′\sqrt n\,e_{j'} is

∥pj,i,s−n ej′∥2=2n 1{j′≠j}+2.\begin{equation*} \left\| p_{j,i,s}-\sqrt n\,e_{j'} \right\|^2 =2n\,\mathbf{1}_{\{j'\ne j\}}+2. \end{equation*}

Thus its own sphere center is uniquely nearest, with squared cost 22. Additional centers are placed far enough away to affect none of these assignments. The preceding within-copy and cross-copy comparisons prove the claimed global assignments and pointwise costs. Finally,

\begin{equation} \begin{aligned} \ensuremath{\mathsf{cost}}_2(X,C(v,\sigma)) &\le9n|P_1|+2(n-1)|P_1| \qquad\text{(by~\eqref{eq:pointwise_cost_bound})}\\ &\le11n|P_1|=11|X|. \end{aligned} \tag*{(9)} \end{equation}

◻

From geometric queries to a coreset error

The preceding construction realizes sign tests as differences of clustering costs. The next proposition isolates the argument that turns these tests into a lower bound against arbitrary reweighting. It will be used both for kk-means and for general powers zz.

Proposition 2.3 (Detecting omissions with paired queries). Fix z≥1z\ge1. Let XX be a finite dataset and let P={pa,s:a∈[t], s∈[q]}⊆XP=\{p_{a,s}:a\in[t],\ s\in[q]\}\subseteq X consist of tqtq distinct points. Let VV and χs(v)=(−1)ℓ(s;v)\chi_s(v)=(-1)^{\ell(s;v)} be supplied by Lemma 2.1. Suppose that, for every v∈Vv\in V and σ∈{−1,1}t\sigma\in\{-1,1\}^t, a set C(v,σ)C(v,\sigma) of kk centers satisfies dz(pa,s,C(v,σ))−dz(pa,s,C(v,−σ))=2η σaχs(v),dz(p,C(v,σ))−dz(p,C(v,−σ))=0(p∈X∖P), \begin{aligned} d^z(p_{a,s},C(v,\sigma))-d^z(p_{a,s},C(v,-\sigma)) &=2\eta\,\sigma_a\chi_s(v),\\ d^z(p,C(v,\sigma))-d^z(p,C(v,-\sigma))&=0 \qquad(p\in X\setminus P), \end{aligned} where η>0\eta>0 is independent of a,s,v,σa,s,v,\sigma. Suppose also that 0<costz(X,C(v,σ))≤H0<{\mathsf{cost}}_z(X,C(v,\sigma))\le H for every query. Then every nonnegatively weighted subset (S,w)(S,w) with ∣S∩P∣≤∣P∣/2|S\cap P|\le |P|/2 admits a query CC in this family such that ∣costz(S,C)−costz(X,C)∣costz(X,C)≥η∣P∣23 Hq. \frac{|{\mathsf{cost}}_z(S,C)-{\mathsf{cost}}_z(X,C)|}{{\mathsf{cost}}_z(X,C)} \ge \frac{\eta |P|}{2\sqrt3\,H\sqrt q}.

Proof. Extend ww by zero outside SS, and set Aa=(w(pa,s)−1)s=1qA^a=(w(p_{a,s})-1)_{s=1}^q. Subtracting the two signed errors and applying Eq. (10) gives

Δ(C(v,σ))−Δ(C(v,−σ))=∑p∈X(w(p)−1)(dz(p,C(v,σ))−dz(p,C(v,−σ)))=2η∑a=1tσa⟨Aa,χ(v)⟩.\begin{align*} \Delta(C(v,\sigma))-\Delta(C(v,-\sigma)) &=\sum_{p\in X}(w(p)-1) \bigl(d^z(p,C(v,\sigma))-d^z(p,C(v,-\sigma))\bigr)\\ &=2\eta\sum_{a=1}^t\sigma_a\langle A^a,\chi(v)\rangle. \end{align*}

The contributions outside PP cancel exactly, regardless of their weights. For fixed vv, choosing σa\sigma_a with the sign of ⟨Aa,χ(v)⟩\langle A^a,\chi(v)\rangle makes the last sum equal to ∑a∣⟨Aa,χ(v)⟩∣\sum_a|\langle A^a,\chi(v)\rangle|. Lemma 2.1 then yields

max⁡v,σ[Δ(C(v,σ))−Δ(C(v,−σ))]≥2η3∑a=1t∥Aa∥2.\begin{equation} \max_{v,\sigma}\bigl[\Delta(C(v,\sigma))-\Delta(C(v,-\sigma))\bigr] \ge\frac{2\eta}{\sqrt3}\sum_{a=1}^t\|A^a\|_2. \tag*{(12)} \end{equation}

The maximum is outside the sum: the lemma supplies one common direction for all groups, not a separate direction for each group.

Let MaM_a be the number of omitted points in group aa. Each omitted point has discrepancy −1-1, so ∥Aa∥2≥Ma\|A^a\|_2\ge\sqrt{M_a}. Since 0≤Ma≤q0\le M_a\le q and ∑aMa≥∣P∣/2\sum_aM_a\ge|P|/2,

∑a∥Aa∥2≥∑aMa≥∑aMaq≥∣P∣2q.\begin{equation} \sum_a\|A^a\|_2 \ge\sum_a\sqrt{M_a} \ge\frac{\sum_aM_a}{\sqrt q} \ge\frac{|P|}{2\sqrt q}. \tag*{(13)} \end{equation}

Here Ma≥Ma/q\sqrt{M_a}\ge M_a/\sqrt q follows from Ma≤qM_a\le q, including when Ma=0M_a=0. Combining Eqs. (12) and (13), the maximizing queries have an error gap at least η∣P∣/(3q)\eta|P|/(\sqrt3\sqrt q). At least one has absolute error at least half this gap. Dividing by its true cost, which is at most HH, proves Eq. (11). ◻

Applying the proposition to kk-means.

Fix a weighted subset with ∣S∣≤∣X∣/2|S|\le|X|/2, and choose the active copy P1P_1 as above. Its nmnm sphere–label pairs form the groups in Proposition 2.3. By Eq. (7), reversing σ\sigma changes an active point’s squared cost by

d2(pj,i,s,C(v,σ))−d2(pj,i,s,C(v,−σ))=n4L2σji(−1)ℓ(s;v).\begin{equation*} d^2(p_{j,i,s},C(v,\sigma))-d^2(p_{j,i,s},C(v,-\sigma)) =\frac{\sqrt n}{4L^2}\sigma_{ji}(-1)^{\ell(s;v)}. \end{equation*}

Inactive costs agree. Thus Eq. (10) holds with η=n/(8L2)\eta=\sqrt n/(8L^2). Eq. (9) bounds the true cost by H=11∣X∣=11n∣P1∣H=11|X|=11n|P_1|. The proposition therefore supplies a query with relative error at least

n ∣P1∣8L2⋅23⋅11n∣P1∣q=11763 nq L2.\begin{equation*} \frac{\sqrt n\,|P_1|}{8L^2\cdot2\sqrt3\cdot11n|P_1|\sqrt q} =\frac{1}{176\sqrt3\,\sqrt{nq}\,L^2}. \end{equation*}

In particular, this error is at least 2ε2\varepsilon whenever

εnq L2≤c0,c0:=13523.\begin{equation} \varepsilon\sqrt{nq}\,L^2\le c_0,\qquad c_0:=\frac{1}{352\sqrt3}. \tag*{(14)} \end{equation}

Together with the coding condition and the center budget, this forces every ε\varepsilon-coreset to contain more than ∣X∣/2|X|/2 points. § 2.6 chooses the integer parameters simultaneously for all fixed z≥1z\ge1, including z=2z=2, and treats the ranges where the main construction is not feasible.

Proof of Lemma 2.1: projection levels and signs

This proof is independent of the rest of the argument. The extension in § 2.5 uses only the lemma statement.

Proof of Lemma 2.1. We first construct distinct binary words b1,…,bq∈{0,1}Lb_1,\ldots,b_q\in\{0,1\}^L such that no four distinct words sum to zero. Sums of binary words are taken coordinatewise modulo two. Suppose b1,…,bs−1b_1,\ldots,b_{s-1} have been chosen. To choose bsb_s, exclude

{bs′:1≤s′<s}  ∪  {bs1+bs2+bs3:1≤s1<s2<s3<s}.\begin{equation*} \{b_{s'}:1\le s'<s\} \;\cup\; \{b_{s_1}+b_{s_2}+b_{s_3}:1\le s_1<s_2<s_3<s\}. \end{equation*}

The number of excluded words is at most

(s−1)+(s−13)<q+(q3)<2L(s≤q and the lemma’s hypothesis).\begin{equation*} (s-1)+\binom{s-1}{3}<q+\binom q3<2^L \qquad\text{($s\le q$ and the lemma's hypothesis)}. \end{equation*}

The first upper bound counts at most one excluded word per previous word or previous triple; coincident exclusions can only reduce the count. Thus a valid choice exists at every step. The first exclusion ensures distinctness. The second prevents four distinct words from summing to zero, because the last word in such a relation would be the sum of three earlier words.

Let ha,βh_{a,\beta}, for a∈[L]a\in[L] and β∈{0,1}\beta\in\{0,1\}, be an orthonormal basis of R2L\mathbb{R}^{2L}, and let bs(a)b_s(a) denote the aath bit of bsb_s. Define

xs=1L∑a=1Lha,bs(a),s∈[q].\begin{equation*} x_s=\frac1{\sqrt L}\sum_{a=1}^Lh_{a,b_s(a)},\qquad s\in[q]. \end{equation*}

These vectors have unit norm:

∥xs∥2=1L∑a=1L1=1.\begin{equation*} \left\| x_s \right\|^2=\frac1L\sum_{a=1}^L1=1. \end{equation*}

If two binary words differ at coordinate aa, their vectors have different coefficients on ha,0h_{a,0} and ha,1h_{a,1}. Hence the vectors are distinct.

Draw the signs ra,βr_{a,\beta} independently and uniformly from {−1,1}\{-1,1\}, and set

v=1L∑a=1L∑β∈{0,1}ra,βha,β.\begin{equation*} v=\frac1{\sqrt L}\sum_{a=1}^L\sum_{\beta\in\{0,1\}}r_{a,\beta}h_{a,\beta}. \end{equation*}

Distinct sign arrays have distinct coordinates in the basis, so the 22L2^{2L} arrays yield 22L2^{2L} vectors; let VV be their set. Moreover,

∥v∥2=1L∑a=1L∑β∈{0,1}ra,β2=2.\begin{equation*} \left\| v \right\|^2=\frac1L\sum_{a=1}^L\sum_{\beta\in\{0,1\}}r_{a,\beta}^2=2. \end{equation*}

Throughout this proof, Ev\mathop{\mathrm{{\mathbb{E}}}}_v is the uniform average over VV, equivalently the expectation over the independent signs. This auxiliary average is used only to establish the maximum bound. Let ℓ(s;v)\ell(s;v) count the coordinates aa with ra,bs(a)=−1r_{a,b_s(a)}=-1. Then

⟨xs,v⟩=1L∑a=1Lra,bs(a)=1−2ℓ(s;v)L.\begin{equation*} \left\langle x_s,v\right\rangle=\frac1L\sum_{a=1}^Lr_{a,b_s(a)} =1-\frac{2\ell(s;v)}L. \end{equation*}

This proves (3). The same count also gives

∏a=1Lra,bs(a)=(−1)ℓ(s;v).\begin{equation} \prod_{a=1}^Lr_{a,b_s(a)}=(-1)^{\ell(s;v)}. \tag*{(15)} \end{equation}

For the moment calculations, write χs(v):=(−1)ℓ(s;v)\chi_s(v):=(-1)^{\ell(s;v)}. Fix a coefficient vector A=(As)s=1q∈RqA=(A_s)_{s=1}^q\in\mathbb{R}^q and define

Y(v):=∑s=1qAsχs(v).\begin{equation*} Y(v):=\sum_{s=1}^qA_s\chi_s(v). \end{equation*}

The second moment identifies the scale ∥A∥22\|A\|_2^2; a fourth-moment bound ensures that this scale is not due only to rare large values. It suffices to prove that for every fixed subset T⊆[q]T\subseteq[q] of size 22 or 44,

Ev∏s∈Tχs(v)=0.\begin{equation} \mathop{\mathrm{{\mathbb{E}}}}_v\prod_{s\in T}\chi_s(v)=0. \tag*{(16)} \end{equation}

For each aa, let Na:=∑s∈Tbs(a)N_a:=\sum_{s\in T}b_s(a) be an ordinary integer sum, counting the words in TT whose aath bit is 11. The other ∣T∣−Na|T|-N_a words have bit 00. Hence

\begin{equation*} \prod_{s\in T}\chi_s(v) =\prod_{a=1}^Lr_{a,0}^{|T|-N_a}r_{a,1}^{N_a} \qquad\text{(by~\eqref{eq:parity})}. \end{equation*}

If ∣T∣=2|T|=2, distinctness gives ∑s∈Tbs≠0\sum_{s\in T}b_s\ne0 modulo two. If ∣T∣=4|T|=4, the exclusion of four-word zero sums gives the same conclusion. Thus some coordinate a∗a_* has Na∗N_{a_*} odd. At that coordinate,

E[ra∗,1Na∗]=E[ra∗,1]=0,\begin{equation*} \mathop{\mathrm{{\mathbb{E}}}}\bigl[r_{a_*,1}^{N_{a_*}}\bigr]=\mathop{\mathrm{{\mathbb{E}}}}[r_{a_*,1}]=0, \end{equation*}

because an odd power of a sign equals the sign itself and the sign is uniform. By independence,

Ev∏s∈Tχs(v)=∏a=1L(E[ra,0∣T∣−Na] E[ra,1Na])(independent signs)=0(the a∗,1 factor vanishes).\begin{align*} \mathop{\mathrm{{\mathbb{E}}}}_v\prod_{s\in T}\chi_s(v) &=\prod_{a=1}^L \left(\mathop{\mathrm{{\mathbb{E}}}}[r_{a,0}^{|T|-N_a}]\,\mathop{\mathrm{{\mathbb{E}}}}[r_{a,1}^{N_a}]\right) \qquad\text{(independent signs)}\\ &=0 \qquad\text{(the $a_*,1$ factor vanishes)}. \end{align*}

This proves (16). For a product of one or three distinct χs\chi_s, the total multiplicity at each coordinate is odd, so at least one of ra,0,ra,1r_{a,0},r_{a,1} has odd multiplicity. Its expectation is zero as well. Thus the signs are unbiased and four-wise independent; the following moment calculation only needs the even cases.

Every χs\chi_s is a sign, so χs2=1\chi_s^2=1. Expanding the second moment gives

\begin{equation*} \mathop{\mathrm{\ensuremath{\mathbb{E}}}}_vY^2=\sum_{s=1}^qA_s^2=\|A\|_2^2 \qquad\text{(by~\eqref{eq:euclidean-parity-cancellation})}. \end{equation*}

In the fourth moment, multiplicity patterns 3+13+1 and 2+1+12+1+1 reduce to products of two distinct signs; pattern 1+1+1+11+1+1+1 uses four distinct signs. Their expectations vanish by (16). The surviving patterns are 44 and 2+22+2, and the latter has (42)=6\binom42=6 orderings. Therefore,

EvY4=∑sAs4+6∑s<s′As2As′2=3(∑sAs2)2−2∑sAs4≤3∥A∥24.\begin{align*} \mathop{\mathrm{{\mathbb{E}}}}_vY^4 &=\sum_sA_s^4+6\sum_{s<s'}A_s^2A_{s'}^2\\ &=3\left(\sum_sA_s^2\right)^2-2\sum_sA_s^4 \le3\|A\|_2^4. \end{align*}

If A=0A=0, the required average bound is immediate. Otherwise EvY2>0\mathop{\mathrm{{\mathbb{E}}}}_vY^2>0, so EvY4>0\mathop{\mathrm{{\mathbb{E}}}}_vY^4>0 and Lemma (?) applies:

\begin{align*} \mathop{\mathrm{\ensuremath{\mathbb{E}}}}_v|Y| &\ge\frac{(\mathop{\mathrm{\ensuremath{\mathbb{E}}}}_vY^2)^{3/2}}{(\mathop{\mathrm{\ensuremath{\mathbb{E}}}}_vY^4)^{1/2}} \qquad\text{(Lemma~\ref{lem:holder})}\\ &\ge\frac1{\sqrt3}\|A\|_2 \qquad\text{(the second and fourth moments)}. \end{align*}

For the vectors A(1),…,A(t)A^{(1)},\ldots,A^{(t)} in the lemma, let Yr(v):=∑sAs(r)χs(v)Y_r(v):=\sum_sA_s^{(r)}\chi_s(v). Applying the preceding bound separately to each coefficient vector yields

max⁡v∈V∑r=1t∣Yr(v)∣≥Ev∑r=1t∣Yr(v)∣=∑r=1tEv∣Yr(v)∣≥13∑r=1t∥A(r)∥2(the average bound for each vector).\begin{align*} \max_{v\in V}\sum_{r=1}^t|Y_r(v)| &\ge\mathop{\mathrm{{\mathbb{E}}}}_v\sum_{r=1}^t|Y_r(v)| =\sum_{r=1}^t\mathop{\mathrm{{\mathbb{E}}}}_v|Y_r(v)|\\ &\ge\frac1{\sqrt3}\sum_{r=1}^t\|A^{(r)}\|_2 \qquad\text{(the average bound for each vector)}. \end{align*}

Substituting the definitions of YrY_r and χs\chi_s gives (4), with one common vv for every coefficient vector. ◻

Lemma (Moment interpolation). Every real-valued random variable YY with 0<E∣Y∣4<∞0<\mathop{\mathrm{{\mathbb{E}}}}|Y|^4<\infty satisfies E∣Y∣≥(E∣Y∣2)3/2(E∣Y∣4)1/2. \mathop{\mathrm{{\mathbb{E}}}}|Y|\ge\frac{(\mathop{\mathrm{{\mathbb{E}}}}|Y|^2)^{3/2}}{(\mathop{\mathrm{{\mathbb{E}}}}|Y|^4)^{1/2}}.

Proof. The first and second absolute moments are finite because ∣Y∣r≤1+∣Y∣4|Y|^r\le1+|Y|^4 for r∈{1,2}r\in\{1,2\}. Factor ∣Y∣2|Y|^2 so that Hölder’s exponents are 3/23/2 and 33:

E∣Y∣2=E[∣Y∣2/3∣Y∣4/3]≤(E∣Y∣)2/3(E∣Y∣4)1/3(Ho¨lder, 3/2 and 3).\begin{align*} \mathop{\mathrm{{\mathbb{E}}}}|Y|^2 &=\mathop{\mathrm{{\mathbb{E}}}}\bigl[|Y|^{2/3}|Y|^{4/3}\bigr]\\ &\le(\mathop{\mathrm{{\mathbb{E}}}}|Y|)^{2/3}(\mathop{\mathrm{{\mathbb{E}}}}|Y|^4)^{1/3} \qquad\text{(H\"older, $3/2$ and $3$)}. \end{align*}

Raising both sides to the power 3/23/2, which preserves the inequality between nonnegative quantities, gives

(E∣Y∣2)3/2≤E∣Y∣ (E∣Y∣4)1/2.\begin{equation*} (\mathop{\mathrm{{\mathbb{E}}}}|Y|^2)^{3/2}\le\mathop{\mathrm{{\mathbb{E}}}}|Y|\,(\mathop{\mathrm{{\mathbb{E}}}}|Y|^4)^{1/2}. \end{equation*}

Dividing by (E∣Y∣4)1/2>0(\mathop{\mathrm{{\mathbb{E}}}}|Y|^4)^{1/2}>0 proves the claim. ◻

Extending the construction to general powers

Dataset construction.

Fix a real z≥1z\ge1. Each copy uses the construction of § 2.1, but the full dataset now consists of ⌈nz/2⌉\lceil n^{z/2}\rceil copies rather than nn. Their sizes satisfy

∣Pb∣=nmq,∣X∣=⌈nz/2⌉nmq≍n(z+2)/2mq.|P_b|=nmq,\qquad |X|=\lceil n^{z/2}\rceil nmq\asymp n^{(z+2)/2}mq.

An active point will contribute Θz(nz/2)\Theta_z(n^{z/2}) to the cost, so this choice keeps the active contribution comparable to ∣X∣|X|.

Center set construction.

Fix a weighted subset (S,w)(S,w) with ∣S∣≤∣X∣/2|S|\le|X|/2, and extend ww by zero to X∖SX\setminus S. Some copy contains at most half its points in SS; call it P1P_1, the active copy. Write its points in local coordinates, carrying their weights along. All active centers defined below receive the translation of this copy. For every v∈Vv\in V, recall that ∥v∥2=2\left\| v \right\|^2=2 and

⟨xs,v⟩=tℓ(s;v),tℓ=1−2ℓL,0≤ℓ≤L.\left\langle x_s,v\right\rangle=t_{\ell(s;v)},\qquad t_\ell=1-\frac{2\ell}{L},\qquad 0\le\ell\le L.

The query family is indexed by v∈Vv\in V and σ∈{−1,1}n×m\sigma\in\{-1,1\}^{n\times m}. A point pj,i,sp_{j,i,s} is intended to use the center with label ii and level ℓ(s;v)\ell(s;v).

To make the opposite-query cost difference independent of the level, choose the displacement δℓ\delta_\ell as the unique solution in (0,1/(16L2)](0,1/(16L^2)] to

(Dℓ+2n δℓ)z/2−(Dℓ−2n δℓ)z/2=n(z−1)/232L2,\begin{equation} \left(D_\ell+2\sqrt n\,\delta_\ell\right)^{z/2}-\left(D_\ell-2\sqrt n\,\delta_\ell\right)^{z/2}=\frac{n^{(z-1)/2}}{32L^2}, \tag*{(17)} \end{equation}

where Dℓ=9n+2−4n−n tℓ2D_\ell=9n+2-4\sqrt n-\sqrt n\,t_\ell^2, as in the z=2z=2 case. To verify existence, use the bounds in Claim 2.2: both arguments in (17) lie in [5n,9n][5n,9n] throughout the allowed displacement interval. Since (z/2)uz/2−1≥nz/2−1/6(z/2)u^{z/2-1}\ge n^{z/2-1}/6 for u∈[5n,9n]u\in[5n,9n] and z≥1z\ge1, the mean value theorem gives

(Dℓ+n8L2)z/2−(Dℓ−n8L2)z/2≥n(z−1)/224L2>n(z−1)/232L2.\left(D_\ell+\frac{\sqrt n}{8L^2}\right)^{z/2}-\left(D_\ell-\frac{\sqrt n}{8L^2}\right)^{z/2}\ge\frac{n^{(z-1)/2}}{24L^2}>\frac{n^{(z-1)/2}}{32L^2}.

The left-hand side of (17) is continuous and strictly increasing from zero, so the required solution exists uniquely. It depends only on z,n,L,ℓz,n,L,\ell, not on v,σ,S,v,\sigma,S, or ww, including when 1≤z<21\le z<2; at z=2z=2, it is δℓ=1/(128L2)\delta_\ell=1/(128L^2).

For each i∈[m]i\in[m] and 0≤ℓ≤L0\le\ell\le L, define

ci,ℓ(v,σ)=2n ui+n tℓv−(−1)ℓδℓ∑j=1nσjiej+λℓf,λℓ=(4n+(n−2n)tℓ2−nδℓ2)1/2.\begin{aligned} c_{i,\ell}(v,\sigma)&=2\sqrt n\,u_i+\sqrt n\,t_\ell v-(-1)^\ell\delta_\ell\sum_{j=1}^n\sigma_{ji}e_j+\lambda_\ell f,\\ \lambda_\ell&=\left(4n+(\sqrt n-2n)t_\ell^2-n\delta_\ell^2\right)^{1/2}. \end{aligned}

The radicand is at least 2n+n−n/(256L4)>02n+\sqrt n-n/(256L^4)>0. Orthogonality gives

∥ci,ℓ(v,σ)∥2=4n+2ntℓ2+nδℓ2+λℓ2=8n+n tℓ2≤9n,\left\| c_{i,\ell}(v,\sigma) \right\|^2=4n+2nt_\ell^2+n\delta_\ell^2+\lambda_\ell^2=8n+\sqrt n\,t_\ell^2\le9n,

independently of v,σv,\sigma. The m(L+1)m(L+1) active centers are distinct by their label and level components. In each inactive copy, put the nn centers at the translated sphere centers n ej,j∈[n]\sqrt n\,e_j,j\in[n]. The parameter choice below ensures m(L+1)+n(⌈nz/2⌉−1)≤km(L+1)+n(\lceil n^{z/2}\rceil-1)\le k; place the remaining centers sufficiently far from the data.

Cost calculation.

Fix an active point p=pj,i,sp=p_{j,i,s}, and put ℓ=ℓ(s;v)\ell=\ell(s;v). For any candidate indices i′∈[m]i'\in[m] and 0≤ℓ′≤L0\le\ell'\le L, orthogonality and ⟨xs,v⟩=tℓ\left\langle x_s,v\right\rangle=t_\ell give

⟨p,ci′,ℓ′(v,σ)⟩=2n ⟨ui,ui′⟩+n tℓ′⟨xs,v⟩−n δℓ′(−1)ℓ′∑a=1nσai′⟨ej,ea⟩=2n 1{i′=i}+n tℓtℓ′−n δℓ′(−1)ℓ′σji′.\begin{aligned} &\left\langle p,c_{i',\ell'}(v,\sigma)\right\rangle\\ &\quad=2\sqrt n\,\left\langle u_i,u_{i'}\right\rangle+\sqrt n\,t_{\ell'}\left\langle x_s,v\right\rangle-\sqrt n\,\delta_{\ell'}(-1)^{\ell'}\sum_{a=1}^n\sigma_{ai'}\left\langle e_j,e_a\right\rangle\\ &\quad=2\sqrt n\,\mathbf{1}_{\{i'=i\}}+\sqrt n\,t_\ell t_{\ell'}-\sqrt n\,\delta_{\ell'}(-1)^{\ell'}\sigma_{ji'}. \end{aligned}

Substituting this identity, ∥p∥2=n+2\left\| p \right\|^2=n+2, and the center norm into the squared-distance identity yields

∥p−ci′,ℓ′(v,σ)∥2=∥p∥2+∥ci′,ℓ′(v,σ)∥2−2⟨p,ci′,ℓ′(v,σ)⟩=9n+2+n tℓ′2−4n 1{i′=i}−2n tℓtℓ′+2n δℓ′(−1)ℓ′σji′=Dℓ+n(tℓ′−tℓ)2⏟level penalty+4n 1{i′≠i}⏟label penalty+2n δℓ′(−1)ℓ′σji′⏟sign perturbation.\begin{aligned} &\left\| p-c_{i',\ell'}(v,\sigma) \right\|^2\\ &\quad=\left\| p \right\|^2+\left\| c_{i',\ell'}(v,\sigma) \right\|^2-2\left\langle p,c_{i',\ell'}(v,\sigma)\right\rangle\\ &\quad=9n+2+\sqrt n\,t_{\ell'}^2-4\sqrt n\,\mathbf{1}_{\{i'=i\}}-2\sqrt n\,t_\ell t_{\ell'}+2\sqrt n\,\delta_{\ell'}(-1)^{\ell'}\sigma_{ji'}\\ &\quad=D_\ell+\underbrace{\sqrt n(t_{\ell'}-t_\ell)^2}_{\text{level penalty}}+\underbrace{4\sqrt n\,\mathbf{1}_{\{i'\ne i\}}}_{\text{label penalty}}+\underbrace{2\sqrt n\,\delta_{\ell'}(-1)^{\ell'}\sigma_{ji'}}_{\text{sign perturbation}}. \end{aligned}

The last equality completes the square, exactly as for z=2z=2. Both penalties vanish at (i′,ℓ′)=(i,ℓ)(i',\ell')=(i,\ell). A wrong level incurs at least 4n/L24\sqrt n/L^2, since ∣tℓ′−tℓ∣≥2/L|t_{\ell'}-t_\ell|\ge2/L; a wrong label incurs 4n≥4n/L24\sqrt n\ge4\sqrt n/L^2. In contrast, the change in the sign perturbation has absolute value at most 2n(δℓ′+δℓ)2\sqrt n(\delta_{\ell'}+\delta_\ell). Hence, whenever (i′,ℓ′)≠(i,ℓ)(i',\ell')\ne(i,\ell),

∥p−ci′,ℓ′(v,σ)∥2−∥p−ci,ℓ(v,σ)∥2≥4nL2−2n(δℓ′+δℓ)≥15n4L2>0,\begin{aligned} &\left\| p-c_{i',\ell'}(v,\sigma) \right\|^2-\left\| p-c_{i,\ell}(v,\sigma) \right\|^2\\ &\quad\ge\frac{4\sqrt n}{L^2}-2\sqrt n(\delta_{\ell'}+\delta_\ell)\ge\frac{15\sqrt n}{4L^2}>0, \end{aligned}

using δℓ,δℓ′≤1/(16L2)\delta_\ell,\delta_{\ell'}\le1/(16L^2). Thus ci,ℓ(v,σ)c_{i,\ell}(v,\sigma) is the unique nearest active center. The unchanged local norm bound 3n3\sqrt n and copy separation exclude cross-copy assignments, as in Claim 2.2; the padding centers are also too far away. Inactive points retain their own sphere center as the nearest center, at distance ∥ui+xs∥=2\left\| u_i+x_s \right\|=\sqrt2, and therefore have cost 2z/22^{z/2}.

It follows that every active point has powered cost

dz(pj,i,s,C(v,σ))=(Dℓ(s;v)+2n δℓ(s;v)σji(−1)ℓ(s;v))z/2∈[(5n)z/2,(9n)z/2],\begin{equation} \begin{aligned} d^z(p_{j,i,s},C(v,\sigma)) &=\left(D_{\ell(s;v)}+2\sqrt n\,\delta_{\ell(s;v)}\sigma_{ji}(-1)^{\ell(s;v)}\right)^{z/2}\\ &\in[(5n)^{z/2},(9n)^{z/2}], \end{aligned} \tag*{(18)} \end{equation}

while every inactive point has cost 2z/22^{z/2}. Therefore

costz(X,C(v,σ))=∑p∈P1dz(p,C(v,σ))+2z/2(⌈nz/2⌉−1)∣P1∣≤(9z/2+2z/2)nz/2∣P1∣≤2⋅3znz/2∣P1∣≤2⋅3z∣X∣.\begin{equation} \begin{aligned} {\mathsf{cost}}_z(X,C(v,\sigma)) &=\sum_{p\in P_1}d^z(p,C(v,\sigma))+2^{z/2}(\lceil n^{z/2}\rceil-1)|P_1|\\ &\le(9^{z/2}+2^{z/2})n^{z/2}|P_1|\\ &\le2\cdot3^z n^{z/2}|P_1|\le2\cdot3^z|X|. \end{aligned} \tag*{(19)} \end{equation}

The active contribution is also at least (5n)z/2∣P1∣(5n)^{z/2}|P_1|, so the total cost is Θz(∣X∣)\Theta_z(|X|).

Applying the query proposition to general powers.

For an active point p=pj,i,sp=p_{j,i,s} at level ℓ=ℓ(s;v)\ell=\ell(s;v), the sign σji(−1)ℓ\sigma_{ji}(-1)^\ell is either 11 or −1-1. By Eq. (18), reversing it exchanges the two perturbed squared costs. Hence

\begin{align*} &d^z(p,C(v,\sigma))-d^z(p,C(v,-\sigma))\\ &\quad=\sigma_{ji}(-1)^\ell \left[\left(D_\ell+2\sqrt n\,\delta_\ell\right)^{z/2} -\left(D_\ell-2\sqrt n\,\delta_\ell\right)^{z/2}\right]\\ &\quad=\frac{n^{(z-1)/2}}{32L^2}\sigma_{ji}(-1)^\ell \qquad\text{(by Eq.~\eqref{eq:euclidean-z-powered-gap})}. \end{align*}

The calibration is what makes the coefficient independent of the level and the direction. Inactive costs do not change. Thus Proposition 2.3 applies to the nmnm sphere–label groups with

η=n(z−1)/264L2,H=2⋅3znz/2∣P1∣,\begin{equation*} \eta=\frac{n^{(z-1)/2}}{64L^2},\qquad H=2\cdot3^z n^{z/2}|P_1|, \end{equation*}

where the true-cost bound is Eq. (19). Any weighted subset omitting at least half of P1P_1 consequently admits a query with relative error at least

η∣P1∣23 Hq=12563 3znq L2.\begin{equation*} \frac{\eta|P_1|}{2\sqrt3\,H\sqrt q} =\frac{1}{256\sqrt3\,3^z\sqrt{nq}\,L^2}. \end{equation*}

In particular, the error is at least 2ε2\varepsilon if

εnq L2≤cz,cz:=15123 3z.\begin{equation} \varepsilon\sqrt{nq}\,L^2\le c_z,\qquad c_z:=\frac{1}{512\sqrt3\,3^z}. \tag*{(20)} \end{equation}

The power-dependent gap n(z−1)/2n^{(z-1)/2} and cost nz/2n^{z/2} leave the same relative-error scale 1/(nq L2)1/(\sqrt{nq}\,L^2) as for kk-means. It remains to choose integer parameters that also meet the center budget.

Choosing parameters in all error regimes

We now satisfy the coding condition, the center budget, and the error threshold simultaneously. The choice below applies to every fixed real z≥1z\ge1. For z=2z=2, its threshold is smaller than c0c_0 in Eq. (14), so it also completes the kk-means argument.

Lemma 2.5 (Integer parameters for the small-error regime). Fix a real z≥1z\ge1, and put cz=(5123 3z)−1c_z=(512\sqrt3\,3^z)^{-1}. For every integer k≥1k\ge1 and 0<ε≤k−1/(z+2)0<\varepsilon\le k^{-1/(z+2)}, define r=k−1/(z+2)ε−1,L=⌈8log⁡2(2+r)⌉,G=k(2z+2)/(z+2)ε−2L5. r=k^{-1/(z+2)}\varepsilon^{-1},\qquad L=\left\lceil8\log_2(2+r)\right\rceil,\qquad G=\frac{k^{(2z+2)/(z+2)}\varepsilon^{-2}}{L^5}. There are constants az,dz,Dz>0a_z,d_z,D_z>0, depending only on zz, such that the integers n=⌊azk2/(z+2)⌋,m=⌊k4(L+1)⌋,q=max⁡{1,⌊r2L4⌋} n=\left\lfloor a_z k^{2/(z+2)}\right\rfloor,\qquad m=\left\lfloor\frac{k}{4(L+1)}\right\rfloor,\qquad q=\max\left\{1,\left\lfloor\frac{r^2}{L^4}\right\rfloor\right\} have the following properties. If n,m≥1n,m\ge1, then 2L>q+(q3),n(⌈nz/2⌉−1)+m(L+1)≤k,εnq L2≤cz/2,⌈nz/2⌉nmq≥dzG. \begin{gathered} 2^L>q+\binom q3,\qquad n\bigl(\lceil n^{z/2}\rceil-1\bigr)+m(L+1)\le k,\\ \varepsilon\sqrt{nq}\,L^2\le c_z/2,\qquad \lceil n^{z/2}\rceil nmq\ge d_z G. \end{gathered} If n=0n=0 or m=0m=0, then G≤Dzkε−2G\le D_z k\varepsilon^{-2}.

Proof. Write α=2/(z+2)\alpha=2/(z+2) and β=(z+2)/2=1/α\beta=(z+2)/2=1/\alpha. We first bound the effect of rounding qq, before choosing the coefficient of nn. For r≥1r\ge1, the difference 2r−log⁡2(2+r)2\sqrt r-\log_2(2+r) is positive at r=1r=1 and increasing. Hence log⁡2(2+r)≤2r\log_2(2+r)\le2\sqrt r and L≤17rL\le17\sqrt r. Set C0=174C_0=17^4 and R=r2/L4R=r^2/L^4. Then R≥1/C0R\ge1/C_0 and

R2≤q≤max⁡{1,R}≤C0R,q≤r2.\begin{equation} \frac R2\le q\le\max\{1,R\}\le C_0R,\qquad q\le r^2. \tag*{(23)} \end{equation}

For the lower bound, if R<2R<2 then q≥1>R/2q\ge1>R/2; otherwise ⌊R⌋≥R/2\lfloor R\rfloor\ge R/2. The upper bounds follow from the definition of qq and r≥1r\ge1. Moreover,

2L≥(2+r)8>2r6≥2q3≥q+(q3),\begin{equation*} 2^L\ge(2+r)^8>2r^6\ge2q^3\ge q+\binom q3, \end{equation*}

so the coding condition holds regardless of whether n,mn,m are positive.

Choose

az=min⁡{14,cz24C0}.\begin{equation*} a_z=\min\left\{\frac14,\frac{c_z^2}{4C_0}\right\}. \end{equation*}

Suppose first that n,m≥1n,m\ge1. Since ⌈u⌉−1≤u\lceil u\rceil-1\le u, n≤azkαn\le a_z k^\alpha, and β≥1\beta\ge1,

n(⌈nz/2⌉−1)+m(L+1)≤nβ+k4≤azβk+k4≤k2≤k.\begin{align*} n\bigl(\lceil n^{z/2}\rceil-1\bigr)+m(L+1) &\le n^\beta+\frac{k}{4}\\ &\le a_z^\beta k+\frac{k}{4}\le\frac{k}{2}\le k. \end{align*}

The choice of aza_z also controls the error. By Eq. (23) and r2=k−αε−2r^2=k^{-\alpha}\varepsilon^{-2},

εnq L2≤εazkαC0r2/L4 L2=azC0≤cz/2.\begin{equation*} \varepsilon\sqrt{nq}\,L^2 \le\varepsilon\sqrt{a_z k^\alpha C_0r^2/L^4}\,L^2 =\sqrt{a_zC_0}\le c_z/2. \end{equation*}

Thus the same fixed coefficient satisfies both the budget and the prescribed error threshold.

When a rounded count is positive, ⌊u⌋≥u/2\lfloor u\rfloor\ge u/2 for u≥1u\ge1. Consequently,

n≥az2kα,m≥k8(L+1)≥k16L,q≥r22L4.\begin{equation*} n\ge\frac{a_z}{2}k^\alpha,\qquad m\ge\frac{k}{8(L+1)}\ge\frac{k}{16L},\qquad q\ge\frac{r^2}{2L^4}. \end{equation*}

The dataset size therefore satisfies

⌈nz/2⌉nmq≥nβmq≥(az/2)β32 k2r2L5=(az/2)β32 G.\begin{align*} \lceil n^{z/2}\rceil nmq &\ge n^\beta m q\\ &\ge\frac{(a_z/2)^\beta}{32}\,\frac{k^2r^2}{L^5} =\frac{(a_z/2)^\beta}{32}\,G. \end{align*}

This proves Eq. (22) with dz=(az/2)β/32d_z=(a_z/2)^\beta/32.

It remains to account for zero rounded counts. Since

Gkε−2=k1−αL5,\begin{equation*} \frac{G}{k\varepsilon^{-2}}=\frac{k^{1-\alpha}}{L^5}, \end{equation*}

if n=0n=0 then kα<1/azk^\alpha<1/a_z gives this ratio at most az−z/2a_z^{-z/2}. If m=0m=0 then k<4(L+1)≤8Lk<4(L+1)\le8L, so the ratio is at most 81−αL−4−α≤88^{1-\alpha}L^{-4-\alpha}\le8. Taking Dz=max⁡{az−z/2,8}D_z=\max\{a_z^{-z/2},8\} proves the remaining assertion. ◻

Completing the small-error lower bound.

When n,m≥1n,m\ge1, Lemma 2.5 ensures that the construction of § 2.5 is feasible, and Proposition 2.3 together with Eq. (20) forces every ε\varepsilon-coreset to have size ∣S∣>∣X∣/2≳zG=Ω~z(k(2z+2)/(z+2)ε−2)|S|>|X|/2\gtrsim_z G=\widetilde\Omega_z(k^{(2z+2)/(z+2)}\varepsilon^{-2}). Otherwise, the lemma gives G=Oz(kε−2)G=O_z(k\varepsilon^{-2}), so the known Ωz(kε−2)\Omega_z(k\varepsilon^{-2}) lower bound [10 Theorem 11] suffices for ε<1/2\varepsilon<1/2; for ε≥1/2\varepsilon\ge1/2, an instance of kk distinct points requires all points to be retained and yields Ω(k)=Ωz(G)\Omega(k)=\Omega_z(G). This completes the proof of Theorem 1.2.

Completing the larger-error range.

The same query family also recovers the known larger-error lower bound. Suppose k−1/(z+2)≤ε<1k^{-1/(z+2)}\le\varepsilon<1. Put

γz=min⁡{1/4,cz2/4},εz=min⁡{1/2,γz/2}.\begin{equation*} \gamma_z=\min\{1/4,c_z^2/4\},\qquad \varepsilon_z=\min\{1/2,\sqrt{\gamma_z/2}\}. \end{equation*}

For ε<εz\varepsilon<\varepsilon_z, choose

L=q=1,n=⌊γzε−2⌋,m=⌊k/4⌋.\begin{equation*} L=q=1,\qquad n=\lfloor\gamma_z\varepsilon^{-2}\rfloor,\qquad m=\lfloor k/4\rfloor. \end{equation*}

Here γzε−2>2\gamma_z\varepsilon^{-2}>2 and k≥ε−z−2>8k\ge\varepsilon^{-z-2}>8, so both rounded counts are positive. The coding condition is immediate. With β=(z+2)/2\beta=(z+2)/2,

n(⌈nz/2⌉−1)+2m≤nβ+k/2≤γzβε−z−2+k/2≤3k/4,εnq L2≤γz≤cz/2.\begin{align*} n\bigl(\lceil n^{z/2}\rceil-1\bigr)+2m &\le n^\beta+k/2\\ &\le\gamma_z^\beta\varepsilon^{-z-2}+k/2\le3k/4,\\ \varepsilon\sqrt{nq}\,L^2&\le\sqrt{\gamma_z}\le c_z/2. \end{align*}

Thus the construction applies and every coreset has size

Ω(⌈nz/2⌉nm)=Ωz(kε−z−2).\begin{equation*} \Omega(\lceil n^{z/2}\rceil nm) =\Omega_z(k\varepsilon^{-z-2}). \end{equation*}

For ε≥εz\varepsilon\ge\varepsilon_z, the kk-point instance above gives Ω(k)=Ωz(kε−z−2)\Omega(k)=\Omega_z(k\varepsilon^{-z-2}). Together with Theorem 1.2 and the known upper bounds, this completes the proof of Corollary 1.3.

References

  1. [1]Prabhu, M., Schwiegelshohn, C., Shyam, S., & Waingarten, E. (2027). Coresets for Capacitated Clustering via Dual Concentration. Proceedings of the 2027 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
  2. [2]Huang, L., Jiang, S. H.-C., & Vishnoi, N. K. (2019). Coresets for Clustering with Fairness Constraints. Advances in Neural Information Processing Systems, 32. https://proceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.htmlproceedings.neurips.cc/paper/2019/hash/810dfbbebb17302018ae903e9cb7a483-Abstract.html
  3. [3]Bandyapadhyay, S., Fomin, F. V., & Simonov, K. (2021). On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198, 23:1–23:15. https://doi.org/10.4230/LIPIcs.ICALP.2021.23
  4. [4]Huang, L., Jiang, S. H.-C., Lou, J., & Wu, X. (2023). Near-optimal Coresets for Robust Clustering. The Eleventh International Conference on Learning Representations. https://openreview.net/forum?id=Nc1ZkRW8Vdeopenreview.net/forum?id=Nc1ZkRW8Vde
  5. [5]Cohen-Addad, V., Saulpic, D., & Schwiegelshohn, C. (2021). Improved Coresets and Sublinear Algorithms for Power Means in Euclidean Spaces. Advances in Neural Information Processing Systems, 34, 21085–21098. https://proceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.htmlproceedings.neurips.cc/paper/2021/hash/b035d6563a2adac9f822940c145263ce-Abstract.html
  6. [6]Huang, L., Li, J., & Wu, X. (2024). On Optimal Coreset Construction for Euclidean (k, z)-Clustering. Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, 1594–1604. https://doi.org/10.1145/3618260.3649707
  7. [7]Bansal, N., Cohen-Addad, V., Prabhu, M., Saulpic, D., & Schwiegelshohn, C. (2024). Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds. Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 1707–1723. https://doi.org/10.1109/FOCS61266.2024.00106
  8. [8]Har-Peled, S., & Mazumdar, S. (2004). On Coresets for k-Means and k-Median Clustering. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 291–300.
  9. [9]Feldman, D., & Langberg, M. (2011). A Unified Framework for Approximating and Clustering Data. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 569–578.
  10. [10]Cohen-Addad, V., Larsen, K. G., Saulpic, D., & Schwiegelshohn, C. (2022). Towards Optimal Lower Bounds for $k$-Median and $k$-Means Coresets. Proceedings of the 54th Annual ACM Symposium on Theory of Computing, 1038–1051. https://doi.org/10.1145/3519935.3519946
  11. [11]Cohen-Addad, V., Larsen, K. G., Saulpic, D., Schwiegelshohn, C., & Sheikh-Omar, O. A. (2022). Improved Coresets for Euclidean $k$-Means. Advances in Neural Information Processing Systems, 35.
  12. [12]Braverman, V., Cohen-Addad, V., Jiang, S. H.-C., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M. B., & Wu, X. (2022). The Power of Uniform Sampling for Coresets. 63rd IEEE Annual Symposium on Foundations of Computer Science, 462–473. https://doi.org/10.1109/FOCS54457.2022.00051
  13. [13]Cohen-Addad, V., Draganov, A., Russo, M., Saulpic, D., & Schwiegelshohn, C. (2025). A Tight VC-Dimension Analysis of Clustering Coresets with Applications. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 4783–4808. https://doi.org/10.1137/1.9781611978322.162
  14. [14]Huang, L., Jiang, Z., Li, Y., & Wu, X. (2026). Towards Tight Robust Coresets for $k$-Medians Clustering. 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), 374, 112:1–112:21. https://doi.org/10.4230/LIPIcs.ICALP.2026.112
  15. [15]Huang, L., Li, J., Lu, P., & Wu, X. (2025). Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 4732–4782. https://doi.org/10.1137/1.9781611978322.161
  16. [16]Jiang, S. H.-C., & Lou, J. (2025). Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), 334, 101:1–101:18. https://doi.org/10.4230/LIPIcs.ICALP.2025.101
  17. [17]Fang, Z., Huang, L., & Yang, R. (2025). Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers. Advances in Neural Information Processing Systems, 38. https://doi.org/10.52202/085713-0171
  18. [18]Cohen-Addad, V., Saulpic, D., & Schwiegelshohn, C. (2021). A New Coreset Framework for Clustering. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 169–182. https://doi.org/10.1145/3406325.3451022
  19. [19]Braverman, V., Jiang, S. H.-C., Krauthgamer, R., & Wu, X. (2021). Coresets for Clustering in Excluded-Minor Graphs and Beyond. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2679–2696. https://doi.org/10.1137/1.9781611976465.159
  20. [20]Feldman, D., Schmidt, M., & Sohler, C. (2020). Turning Big Data into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering. SIAM Journal on Computing, 49(3), 601–657. https://doi.org/10.1137/18M1209854

Paper details

vlnc:W_w8g2dt3e
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