Introduction
We study the optimal coreset size for ( k , z ) (k,z) ( k , z ) -clustering, where z ≥ 1 z \ge1 z ≥ 1 is a fixed constant.1
( k , z ) (k,z) ( k , z ) -clustering. Given a metric space ( X , d ) (\mathcal{X},d) ( X , d ) , a finite dataset X ⊆ X X \subseteq\mathcal{X} X ⊆ X , and an integer k ≥ 1 k \ge1 k ≥ 1 , the goal is to find a set C ⊆ X C \subseteq\mathcal{X} C ⊆ X of k k k centers minimizing
cost z ( X , C ) : = ∑ p ∈ X d z ( p , C ) , d ( p , C ) : = min c ∈ C d ( 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). cost z ( X , C ) := p ∈ X ∑ d z ( p , C ) , d ( p , C ) := c ∈ C min d ( p , c ) .
The cases z = 1 z=1 z = 1 and z = 2 z=2 z = 2 are the classical k k k -median and k k k -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 D D D if every ball can be covered by at most 2 D 2^D 2 D balls of half its radius. This covering property captures low-dimensional structure without requiring a Euclidean embedding; for constant D D D , 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 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , a strong ε \varepsilon ε -coreset for ( k , z ) (k,z) ( k , z ) -clustering of X X X is a subset S ⊆ X S \subseteq X S ⊆ X with weights w : S → R ≥ 0 w:S \to\mathbb{R}_{\ge0} w : S → R ≥ 0 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, ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ ε cost z ( X , C ) for every C ⊆ X with ∣ C ∣ = k , where cost z ( S , C ) : = ∑ p ∈ S w ( p ) d z ( p , C ) \operatorname{cost}_{z}(S,C) := \sum_{p \in S} w(p)d^{z}(p,C) cost z ( S , C ) := ∑ p ∈ 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}) Ω ( k ε − 2 ) lower bound, which became a natural target for upper bounds. Subsequent upper bounds of O ~ ( k 4 / 3 ε − 2 ) \widetilde{O}(k^{4/3}\varepsilon^{-2}) O ( k 4/3 ε − 2 ) for k k k -median and O ~ ( k 3 / 2 ε − 2 ) \widetilde{O}(k^{3/2}\varepsilon^{-2}) O ( k 3/2 ε − 2 ) for k k k -means still left open whether a superlinear dependence on k k k 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}) Ω ( k ε − z − 2 ) lower bound matches the known upper bound for ε ≳ k − 1 / ( z + 2 ) \varepsilon\gtrsim k^{-1/(z+2)} ε ≳ k − 1/ ( z + 2 ) . They also obtained the upper bound O ~ ( k ( 2 z + 2 ) / ( z + 2 ) ε − 2 ) \widetilde{O}(k^{(2z+2)/(z+2)}\varepsilon^{-2}) O ( k ( 2 z + 2 ) / ( z + 2 ) ε − 2 ) for every fixed z ≥ 1 z \ge1 z ≥ 1 . The remaining gap lies in the small-error regime 0 < ε < k − 1 / ( z + 2 ) 0 < \varepsilon< k^{-1/(z+2)} 0 < ε < k − 1/ ( z + 2 ) , where the known lower bounds are Ω ( k ( 2 z + 3 ) / ( z + 2 ) ε − 1 ) \Omega(k^{(2z+3)/(z+2)}\varepsilon^{-1}) Ω ( k ( 2 z + 3 ) / ( z + 2 ) ε − 1 ) for ε ≳ k − ( z + 1 ) / ( z + 2 ) \varepsilon\gtrsim k^{-(z+1)/(z+2)} ε ≳ k − ( z + 1 ) / ( z + 2 ) and Ω ( k ε − 2 ) \Omega(k\varepsilon^{-2}) Ω ( k ε − 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 ≥ 1 z \ge1 z ≥ 1 , what is the optimal worst-case coreset size for Euclidean ( k , z ) (k,z) ( k , z ) -clustering in the remaining regime 0 < ε < k − 1 / ( z + 2 ) 0 < \varepsilon< k^{-1/(z+2)} 0 < ε < 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 k k k , ε \varepsilon ε , and D D D . The framework of Cohen-Addad, Saulpic, and Schwiegelshohn [11 ] yields size O ~ ( k D min { k ε − 2 , ε − max { z , 2 } } ) \widetilde{O}(kD\min\{k\varepsilon^{-2},\varepsilon^{-\max\{z,2\}}\}) O ( k D min { k ε − 2 , ε − m a x { z , 2 } }) . The Ω ( k D ε − 2 ) \Omega(kD\varepsilon^{-2}) Ω ( k D ε − 2 ) lower bound of Cohen-Addad et al. [9 ] holds for D ≳ log ( k / ε ) D \gtrsim\log(k/\varepsilon) D ≳ log ( k / ε ) , matching this upper bound up to logarithmic factors for 1 ≤ z ≤ 2 1 \le z \le2 1 ≤ z ≤ 2 in that dimension range.
For z > 2 z > 2 z > 2 , however, the dependence on k k k and ε \varepsilon ε remained unresolved.
Huang, Li, and Wu [22 ] proved a lower bound of Ω ( k D ε − z / log k ) \Omega(kD\varepsilon^{-z}/\log k) Ω ( k D ε − z / log k ) for ε ≳ k − 1 / ( z + 2 ) \varepsilon\gtrsim k^{-1/(z+2)} ε ≳ k − 1/ ( z + 2 ) , matching the corresponding upper bound up to logarithmic factors, and an additional lower bound of Ω ( k ( 2 z + 1 ) / ( z + 2 ) D ε − 1 ) \Omega(k^{(2z+1)/(z+2)}D\varepsilon^{-1}) Ω ( k ( 2 z + 1 ) / ( z + 2 ) D ε − 1 ) for k − ( z + 1 ) / ( z + 2 ) ≲ ε ≲ k − 1 / ( z + 2 ) k^{-(z+1)/(z+2)} \lesssim\varepsilon\lesssim k^{-1/(z+2)} k − ( z + 1 ) / ( z + 2 ) ≲ ε ≲ k − 1/ ( z + 2 ) . In both constructions, D D D denotes the resulting ambient doubling dimension. For smaller ε \varepsilon ε , the bounds remained unmatched, raising the following problem:
Problem 2. For fixed z > 2 z > 2 z > 2 , what is the optimal dependence of the worst-case coreset size on k k k , ε \varepsilon ε , and the doubling dimension D D D for 0 < ε < k − 1 / ( z + 2 ) 0 < \varepsilon< k^{-1/(z+2)} 0 < ε < 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 > 2 z > 2 z > 2 , resolving the remaining gap when D ≳ log ( 2 / ε ) D \gtrsim\log(2/\varepsilon) D ≳ log ( 2/ ε ) and ε \varepsilon ε is sufficiently small. Table 1 summarizes the bounds.
Table 1. Coreset-size bounds up to polylogarithmic factors and z z z -dependent constants. The new doubling upper branch holds for all D ≥ 1 D \ge1 D ≥ 1 and 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 ; combined with the previous k D ε − z kD\varepsilon^{-z} k D ε − z branch, it matches our lower bound for 0 < ε ≤ ε z 0 < \varepsilon\le\varepsilon_z 0 < ε ≤ ε z and D ≥ C z log ( 2 / ε ) D \ge C_z\log(2/\varepsilon) D ≥ C z log ( 2/ ε ) . 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)} 0 < ε < k − 1/ ( z + 2 ) .
Theorem 1.2 (Euclidean coreset lower bound). For every fixed real z ≥ 1 z \ge1 z ≥ 1 , every integer k ≥ 1 k \ge1 k ≥ 1 , and every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , there exist an integer d ≥ 1 d \ge1 d ≥ 1 and a finite dataset X ⊆ R d X \subseteq\mathbb{R}^{d} X ⊆ R d such that every ε \varepsilon ε -coreset for ( k , z ) (k,z) ( k , z ) -clustering of X X X has size
Ω ~ ( min { k z + 2 z + 2 ε − 2 , k ε − z − 2 } ) . \widetilde{\Omega}\left(\min\left\{k^{\frac{z+2}{z+2}}\varepsilon^{-2}, k\varepsilon^{-z-2}\right\}\right). Ω ( min { k z + 2 z + 2 ε − 2 , k ε − z − 2 } ) .
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 ≥ 1 z \ge1 z ≥ 1 , the lower bound in Theorem 1.2 is tight up to polylogarithmic factors for every integer k ≥ 1 k \ge1 k ≥ 1 and 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , over datasets of unrestricted dimension.
In particular, the optimal size is Θ ~ ( k 4 / 3 ε − 2 ) \widetilde{\Theta}(k^{4/3}\varepsilon^{-2}) Θ ( k 4/3 ε − 2 ) for k k k -median when ε < k − 1 / 3 \varepsilon< k^{-1/3} ε < k − 1/3 , and Θ ~ ( k 3 / 2 ε − 2 ) \widetilde{\Theta}(k^{3/2}\varepsilon^{-2}) Θ ( k 3/2 ε − 2 ) for k k k -means when ε < k − 1 / 4 \varepsilon< k^{-1/4} ε < k − 1/4 . Up to polylogarithmic factors, the additional dependence on k k k remains necessary throughout this regime, including for arbitrarily small ε \varepsilon ε . For example, for k k k -means at ε = k − 1 \varepsilon= k^{-1} ε = k − 1 , the lower bound increases from Ω ( k 3 ) \Omega(k^3) Ω ( k 3 ) [9 ] to Ω ~ ( k 7 / 2 ) \widetilde{\Omega}(k^{7/2}) Ω ( k 7/2 ) .
For doubling metrics, we improve both the upper and lower bounds, obtaining the following characterization.
Theorem 1.4 (Optimal coreset size in doubling metrics). For every fixed real z ≥ 2 z \ge2 z ≥ 2 , there are constants C z > 0 C_z > 0 C z > 0 and ε z ∈ ( 0 , 1 ) \varepsilon_z \in(0,1) ε z ∈ ( 0 , 1 ) such that, for every integer k ≥ 1 k \ge1 k ≥ 1 , every 0 < ε ≤ ε z 0 < \varepsilon\le\varepsilon_z 0 < ε ≤ ε z , and every D ≥ C z log ( 2 / ε ) D \ge C_z \log(2/\varepsilon) D ≥ C z log ( 2/ ε ) , the optimal worst-case size of a strong ε \varepsilon ε -coreset for ( k , z ) (k,z) ( k , z ) -clustering, over finite positively weighted inputs in metric spaces of doubling dimension at most D D D , is
Θ ~ ( k D min { k 1 − 2 / z ε − 2 , ε − z } ) . \widetilde{\Theta}\left(kD\min\left\{k^{1-2/z}\varepsilon^{-2},\varepsilon^{-z}\right\}\right). Θ ( k D min { k 1 − 2/ z ε − 2 , ε − z } ) .
The new upper bound is O ~ ( k 2 − 2 / z D ε − 2 ) \widetilde{O}(k^{2-2/z}D\varepsilon^{-2}) O ( k 2 − 2/ z D ε − 2 ) , valid for all D ≥ 1 D \ge1 D ≥ 1 and 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 ; combining it with the existing O ~ ( k D ε − z ) \widetilde{O}(kD\varepsilon^{-z}) O ( k D ε − z ) bound [11 ] gives the combined upper bound in the theorem. Our lower bound matches it for every prescribed D D D under the stated conditions, using an ambient space with doubling dimension between D / 8 D/8 D /8 and D D D .
For z > 2 z > 2 z > 2 , the new upper branch is smaller than the previous k 2 D ε − 2 k^{2}D\varepsilon^{-2} k 2 D ε − 2 branch [11 ] by a factor of k 2 / z k^{2/z} k 2/ z . For sufficiently small ε \varepsilon ε , our lower bound improves on the previous Ω ( k D ε − 2 ) \Omega(kD\varepsilon^{-2}) Ω ( k D ε − 2 ) bound [9 ] by a factor of k 1 − 2 / z k^{1-2/z} k 1 − 2/ z .
The two branches of the optimal-size bound meet at ε = k − 1 / z \varepsilon= k^{-1/z} ε = k − 1/ z .
Technical Overview
Starting from the separated-copy framework of Huang, Li, and Wu [22 ] , we replace individual offsets by distinct points and design a fixed family of queries with k k k centers. The challenge is to ensure that every sufficiently small subset fails some query under any nonnegative reweighting. Shared centers realize four-wise independent sign tests within the center budget; for general z z z , we calibrate perturbations so that powered-cost differences retain a common coefficient. Doubling metrics allow direct distance assignments, letting a center test more groups without increasing the distance scale. For the upper bound, we average unbiased two-point summaries that exactly preserve cluster mass and anchor cost.
Revisiting the previous lower-bound construction. At ε = Θ ( k − 1 / 4 ) \varepsilon= \Theta(k^{-1/4}) ε = Θ ( k − 1/4 ) , Huang, Li, and Wu [22 ] construct Θ ( k 2 ) \Theta(k^2) Θ ( k 2 ) points in Θ ( k ) \Theta(\sqrt{k}) Θ ( k ) far-apart copies P b P_b P b . Within each copy, j j j indexes spheres and i i i labels offsets. Suppressing b b b , the local points are
p j , i = k 1 / 4 e j + u i , p_{j,i}=k^{1/4}e_j+u_i, p j , i = k 1/4 e j + u i ,
where e j e_j e j is a coordinate direction, k 1 / 4 e j k^{1/4}e_j k 1/4 e j is sphere j j j ’s center, and u i u_i u i is a unit offset. Each copy has Θ ( k ) \Theta(\sqrt{k}) Θ ( k ) spheres and Θ ( k ) \Theta(k) Θ ( k ) almost orthogonal offsets. Each offset occurs on Θ ( k ) \Theta(\sqrt{k}) Θ ( k ) spheres, at most once per sphere, giving Θ ( k 3 / 2 ) \Theta(k^{3/2}) Θ ( k 3/2 ) points per copy.
Suppose a putative coreset ( S , w ) (S,w) ( S , w ) retains at most half the dataset. Choose an active copy P 1 P_1 P 1 with ∣ S 1 ∣ ≤ ∣ P 1 ∣ / 2 |S_1| \leq|P_1|/2 ∣ S 1 ∣ ≤ ∣ P 1 ∣/2 , where S 1 = S ∩ P 1 S_1 = S \cap P_1 S 1 = S ∩ P 1 . The query C C C uses one center c i c_i c i for all occurrences of u i u_i u i in P 1 P_1 P 1 . The term − 2 k 1 / 4 ⟨ e j , c i ⟩ -2k^{1/4}\langle e_j,c_i\rangle − 2 k 1/4 ⟨ e j , c i ⟩ turns a constant change in c i c_i c i ’s e j e_j e j -coordinate into a Θ ( k 1 / 4 ) \Theta(k^{1/4}) Θ ( k 1/4 ) cost change on sphere j j j . The other coordinates keep the center norms and ⟨ u i , c i ⟩ \langle u_i,c_i\rangle ⟨ u i , c i ⟩ fixed; the offset design preserves nearest-center assignments. Thus
d 2 ( p , C ) = { B , p ∈ S 1 , B − γ , p ∈ P 1 ∖ S 1 , B = Θ ( k ) , γ = Θ ( k 1 / 4 ) . 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}),\qquad\gamma=\Theta(k^{1/4}). d 2 ( p , C ) = { B , B − γ , p ∈ S 1 , p ∈ P 1 ∖ S 1 , B = Θ ( k ) , γ = Θ ( k 1/4 ) .
The perturbation can be reversed. The other copies are served by their sphere centers, at unit squared cost per point, and the combined query respects the center budget [22 Claim 2.2] .
A distant-center query forces ∑ p ∈ S 1 w ( p ) = ( 1 ± O ( ε ) ) ∣ P 1 ∣ \sum_{p\in S_1}w(p)=(1\pm O(\varepsilon))|P_1| ∑ p ∈ S 1 w ( p ) = ( 1 ± O ( ε )) ∣ P 1 ∣ [22 Claim 2.1] . Orienting the cost difference to avoid cancellation with the inactive error gives absolute error Ω ( γ ∣ P 1 ∣ ) − O ( ε B ∣ P 1 ∣ ) \Omega(\gamma|P_1|)-O(\varepsilon B|P_1|) Ω ( γ ∣ P 1 ∣ ) − O ( εB ∣ P 1 ∣ ) . Since the active and total costs are both Θ ( B ∣ P 1 ∣ ) \Theta(B|P_1|) Θ ( B ∣ P 1 ∣ ) , the relative error is at least
Ω ( γ / B ) − O ( ε ) = Ω ( k − 1 / 4 ) − O ( ε ) . \Omega(\gamma/B)-O(\varepsilon)=\Omega(k^{-1/4})-O(\varepsilon). Ω ( γ / B ) − O ( ε ) = Ω ( k − 1/4 ) − O ( ε ) .
This proves the Ω ( k 2 ) \Omega(k^2) Ω ( k 2 ) bound for a sufficiently small constant in ε = Θ ( k − 1 / 4 ) \varepsilon=\Theta(k^{-1/4}) ε = Θ ( k − 1/4 ) : one center controls an offset’s occurrences on many spheres.
Failed attempts. Below ε = k − 1 / 4 \varepsilon=k^{-1/4} ε = k − 1/4 , the target polynomial size exceeds k 2 k^2 k 2 . Repeating each point q ≍ k − 1 / 2 ε − 2 q\asymp k^{-1/2}\varepsilon^{-2} q ≍ k − 1/2 ε − 2 times gives a multiset X r e p X_{\mathrm{rep}} X rep of size Θ ( k 2 q ) \Theta(k^2q) Θ ( k 2 q ) and suggests the required error scale. Draw N = ∣ X r e p ∣ N=|X_{\mathrm{rep}}| N = ∣ X rep ∣ uniform samples with replacement. Each location’s count has mean q q q and standard deviation Θ ( q ) \Theta(\sqrt{q}) Θ ( q ) . An active copy has Θ ( k 3 / 2 ) \Theta(k^{3/2}) Θ ( k 3/2 ) locations with cost differences of order k 1 / 4 k^{1/4} k 1/4 , while the total cost is of order k 2 q k^2q k 2 q . This suggests
k 1 / 4 ⋅ k 3 / 2 q k 2 q = k − 1 / 4 q ≍ k 3 / 2 N . \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}}. k 2 q k 1/4 ⋅ k 3/2 q = q k − 1/4 ≍ N k 3/2 .
Equating this expression to ε \varepsilon ε gives N ≍ k 3 / 2 ε − 2 N\asymp k^{3/2}\varepsilon^{-2} N ≍ k 3/2 ε − 2 . This calculation only suggests the scale: one representative of weight q q q at each location preserves every query cost exactly. Sampling fluctuations therefore do not establish a lower bound against arbitrary reweighting.
To prevent identical points from collapsing into one representative, a second attempt replaces u i u_i u i by distinct offsets u i , s u_{i,s} u i , s :
p j , i , s = k 1 / 4 e j + u i , s , s ∈ [ q ] . p_{j,i,s}=k^{1/4}e_j+u_{i,s},\qquad s\in[q]. p j , i , s = k 1/4 e j + u i , s , s ∈ [ q ] .
One center per replacement requires Θ ( k q ) \Theta(kq) Θ ( k q ) active centers, exceeding k k k as q q q grows. If instead the offsets with s ∈ G ⊆ [ q ] s\in G\subseteq[q] s ∈ G ⊆ [ q ] share c i , G c_{i,G} c i , G across spheres, their distance to that center contains the common term
− 2 k 1 / 4 ⟨ e j , c i , G ⟩ for every s ∈ G . -2k^{1/4}\langle e_j,c_{i,G}\rangle
\qquad\text{for every }s\in G. − 2 k 1/4 ⟨ e j , c i , G ⟩ for every s ∈ G .
Changing ⟨ e j , c i , G ⟩ \langle e_j,c_{i,G}\rangle ⟨ e j , c i , G ⟩ cannot reproduce the costs B B B and B − γ B-\gamma B − γ 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 ( p j , i , s ) − 1 ) \sum_{s\in G}(w(p_{j,i,s})-1) ∑ s ∈ G ( w ( p j , i , s ) − 1 ) , with w = 0 w=0 w = 0 on omitted points. We therefore need a family of groupings, each using few centers, such that for every reweighting, at least one grouping detects the aggregate discrepancy. The following properties make this requirement precise.
Identifying the properties needed from the new offsets. We keep equal-sized, far-apart copies. For any ( S , w ) (S,w) ( S , w ) retaining at most half of the new dataset X X X , choose an active copy P 1 P_1 P 1 with at least half its points omitted. We require:
P1. Distinct replacements. Each label’s q q q replacements on a sphere are distinct, preventing compression of repeated points into a single representative.
P2. Few centers per grouping. Each label admits partitions into polylogarithmically many groups, with one center per group shared across spheres.
P3. Balanced costs. Every query satisfies cost 2 ( P 1 , C ) ≍ cost 2 ( X , C ) ≍ ∣ X ∣ \operatorname{cost}_2(P_1,C) \asymp\operatorname{cost}_2(X,C) \asymp|X| cost 2 ( P 1 , C ) ≍ cost 2 ( X , C ) ≍ ∣ X ∣ , so inactive costs do not dilute the active error.
P4. Error under arbitrary reweighting. Some query has absolute coreset error Ω ( k 1 / 4 ∣ P 1 ∣ / q ) \Omega(k^{1/4}|P_1|/\sqrt{q}) Ω ( k 1/4 ∣ P 1 ∣/ q ) , assuming only that at least half of P 1 P_1 P 1 is omitted, not half of each group.
The dataset and query family are fixed before ( S , w ) (S,w) ( S , w ) ; only the active copy and witnessing query depend on it. With Θ ( k ) \Theta(\sqrt{k}) Θ ( k ) copies, P3 turns P4 into the relative-error scale suggested by repetition.
Constructing the dataset and sharing centers. Keep b b b for copies, j j j for spheres, and i i i for labels; s s s indexes a label’s replacements. Take n n n far-apart copies, each with n n n spheres and m m m labels. Now choose the u i u_i u i to be orthonormal, and replace each label’s single offset by { u i + x s : s ∈ [ q ] } \{u_i+x_s:s\in[q]\} { u i + x s : s ∈ [ q ]} . The local configuration is
P = { p j , i , s = n e j + u i + x s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ] } . P=\{p_{j,i,s}=\sqrt{n}\,e_j+u_i+x_s:j\in[n],\ i\in[m],\ s\in[q]\}. P = { p j , i , s = n e j + u i + x s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ]} .
The e j e_j e j , the u i u_i u i , and the distinct unit vectors x s x_s x s lie in three mutually orthogonal subspaces; the x s x_s x s need not be mutually orthogonal. Every offset now occurs on every sphere. All triples are distinct, each at distance 2 \sqrt{2} 2 from its sphere center n e j \sqrt{n}\,e_j n e j , so ∣ P ∣ = n m q |P|=nmq ∣ P ∣ = nm q and ∣ X ∣ = n 2 m q |X|=n^2mq ∣ X ∣ = n 2 m q , giving P1.
Fix ( S , w ) (S,w) ( S , w ) and an active copy P 1 P_1 P 1 as above; use local coordinates for its points and query centers. Lemma 2.1 supplies the x s x_s x s and a fixed family V V V of directions with
⟨ x s , v ⟩ = t ℓ ( s ; v ) , t ℓ = 1 − 2 ℓ L , 0 ≤ ℓ ≤ L , \langle x_s,v\rangle=t_{\ell(s;v)},\qquad t_\ell=1-\frac{2\ell}{L},\qquad0\leq\ell\leq L, ⟨ x s , v ⟩ = t ℓ ( s ; v ) , t ℓ = 1 − L 2 ℓ , 0 ≤ ℓ ≤ L ,
where ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) is the level index of x s x_s x s , and L = O ( log ( q + 1 ) ) L=O(\log(q+1)) L = O ( log ( q + 1 )) . One center c i , ℓ c_{i,\ell} c i , ℓ will serve all points of label i i i and level ℓ \ell ℓ across spheres. Inactive copies use their n ( n − 1 ) n(n-1) n ( n − 1 ) sphere centers, giving the budget
n ( n − 1 ) + m ( L + 1 ) ≤ k . n(n-1)+m(L+1)\leq k. n ( n − 1 ) + m ( L + 1 ) ≤ k .
Thus a query needs m ( L + 1 ) m(L+1) m ( L + 1 ) active centers instead of m q mq m q . Changing v v v 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)} ( − 1 ) ℓ ( s ; v ) unbiased four-wise independent signs for uniform v ∈ V v\in V v ∈ V . The discrepancy bound below guarantees that, for any retained weights, at least one of these groupings detects omissions.
Realizing level costs with shared centers. For signs σ = ( σ j i ) ∈ { − 1 , 1 } n × m \sigma=(\sigma_{ji})\in\{-1,1\}^{n\times m} σ = ( σ j i ) ∈ { − 1 , 1 } n × m , let C ( v , σ ) C(v,\sigma) C ( v , σ ) contain the active centers, the inactive sphere centers, and remote centers padding the count to k k k . The active costs are
d 2 ( p j , i , s , C ( v , σ ) ) = D ℓ ( s ; v ) + n 8 L 2 σ j i ( − 1 ) ℓ ( s ; v ) , D ℓ = Θ ( n ) , (1) 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)} d 2 ( p j , i , s , C ( v , σ )) = D ℓ ( s ; v ) + 8 L 2 n σ j i ( − 1 ) ℓ ( s ; v ) , D ℓ = Θ ( n ) , (1)
where the D ℓ D_{\ell} D ℓ are the baselines in Eq. (7) , independent of v , σ v,\sigma v , σ . The sphere-axis component of c i , ℓ c_{i,\ell} c i , ℓ is proportional to − ( − 1 ) ℓ ∑ j , i σ j i e j -(-1)^{\ell}\sum_{j,i}\sigma_{j i}e_j − ( − 1 ) ℓ ∑ j , i σ j i 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 n ( t ℓ ′ − t ℓ ) 2 . With grid spacing 2 / L 2/L 2/ L , this penalty dominates any change in the signed term. Claim 2.2 verifies that c i , ℓ ( s ; v ) c_{i,\ell}(s;v) c i , ℓ ( s ; v ) remains nearest for every σ \sigma σ , giving P2. Inactive points have squared cost 2, so the active and total costs are both Θ ( n ∣ P 1 ∣ ) = Θ ( ∣ X ∣ ) \Theta(n|P_1|)=\Theta(|X|) Θ ( n ∣ P 1 ∣ ) = Θ ( ∣ X ∣ ) , giving P3.
Defeating arbitrary reweighting with opposite queries. Extend w w w by zero to omitted points, and write Δ ( C ) = cost 2 ( S , C ) − cost 2 ( X , C ) \Delta(C)=\operatorname{cost}_2(S,C)-\operatorname{cost}_2(X,C) Δ ( C ) = cost 2 ( S , C ) − cost 2 ( X , C ) . The queries C ( v , σ ) C(v,\sigma) C ( v , σ ) and C ( v , − σ ) C(v,-\sigma) C ( v , − σ ) have identical baselines and inactive costs. Subtracting their signed errors gives
Δ ( C ( v , σ ) ) − Δ ( C ( v , − σ ) ) = n 4 L 2 ∑ j , i σ j i ∑ s ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) . \Delta(C(v,\sigma))-\Delta(C(v,-\sigma))=\frac{\sqrt{n}}{4L^2}\sum_{j,i}\sigma_{j i}\sum_s(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}. Δ ( C ( v , σ )) − Δ ( C ( v , − σ )) = 4 L 2 n j , i ∑ σ j i s ∑ ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) .
The common baselines and all inactive contributions cancel exactly, without an upper bound on the retained weights. For each fixed v v v , choose σ j i \sigma_{j i} σ j i to match the sign of its inner sum. Lemma 2.1 then supplies one common direction with
max v ∈ V ∑ j , i ∣ ∑ s ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) ∣ ≥ 1 3 ( ∑ j , i ( ∑ s ( w ( p j , i , s ) − 1 ) 2 ) ) 1 / 2 ≥ ∣ P 1 ∣ 2 3 q . \max_{v\in V}\sum_{j,i}\left|\sum_s\left(w(p_{j,i,s})-1\right)(-1)^{\ell(s;v)}\right|\geq\frac{1}{\sqrt{3}}\left(\sum_{j,i}\left(\sum_s\left(w(p_{j,i,s})-1\right)^2\right)\right)^{1/2}\geq\frac{|P_1|}{2\sqrt{3q}}. v ∈ V max j , i ∑ s ∑ ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) ≥ 3 1 ( j , i ∑ ( s ∑ ( w ( p j , i , s ) − 1 ) 2 ) ) 1/2 ≥ 2 3 q ∣ P 1 ∣ .
For the last inequality, each omitted point contributes 1 to a squared discrepancy. Each q q q -point group’s norm is at least its number of omissions divided by q \sqrt{q} q , and P 1 P_1 P 1 omits at least half its points. The common direction makes the aggregate discrepancy large; individual groups need not attain their maxima at that direction.
The opposite queries therefore have signed errors differing by Ω ( n ∣ P 1 ∣ / ( L 2 q ) ) \Omega(\sqrt{n}|P_1|/(L^2\sqrt{q})) Ω ( n ∣ P 1 ∣/ ( L 2 q )) . At least one query has absolute error at least half this difference. Its true cost is Θ ( n ∣ P 1 ∣ ) \Theta(n|P_1|) Θ ( n ∣ P 1 ∣ ) , giving relative error Ω ( 1 / ( n q L 2 ) ) \Omega(1/(\sqrt{nq}L^2)) Ω ( 1/ ( n q L 2 )) . For n ≃ k n\simeq\sqrt{k} n ≃ 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. In the main parameter range, the center budget permits n ≃ k n\simeq\sqrt{k} n ≃ k and m ≃ k / L m\simeq k/L m ≃ k / L . The relative-error bound then allows q = Θ ~ ( k − 1 / 2 ε − 2 ) q=\widetilde{\Theta}(k^{-1/2}\varepsilon^{-2}) q = Θ ( k − 1/2 ε − 2 ) , giving ∣ X ∣ = n 2 m q = Θ ~ ( k 3 / 2 ε − 2 ) |X|=n^2mq=\widetilde{\Theta}(k^{3/2}\varepsilon^{-2}) ∣ X ∣ = n 2 m q = Θ ( k 3/2 ε − 2 ) . Every coreset must retain more than half of these points. Section 2.3 makes these parameter choices precise and handles the integer boundary cases.
Extension to a general power z z z . For z ≠ 2 z\ne2 z = 2 , raising Eq. (1) to z / 2 z/2 z /2 produces a level-dependent difference between opposite queries. Since ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) changes with v v v , the coefficient of ( − 1 ) ℓ ( s ; v ) (-1)^{\ell(s;v)} ( − 1 ) ℓ ( s ; v ) in the error sum would vary with the direction. The discrepancy lemma requires coefficients that do not depend on the direction. Constant-factor estimates do not suffice for this signed sum.
Choose a sphere-axis displacement δ ℓ \delta_\ell δ ℓ for each level so that
( D ℓ + 2 n δ ℓ ) z / 2 − ( D ℓ − 2 n δ ℓ ) z / 2 = n ( z − 1 ) / 2 32 L 2 . (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}. ( D ℓ + 2 n δ ℓ ) z /2 − ( D ℓ − 2 n δ ℓ ) z /2 = 32 L 2 n ( z − 1 ) /2 .
Readjusting the orthogonal center component preserves D ℓ D_\ell D ℓ . Monotonicity and the mean value theorem give the required displacement without changing the nearest-center assignments; see Section 2.5. The powered-cost difference is now a fixed coefficient times σ j i ( − 1 ) ℓ ( s ; v ) \sigma_{ji}(-1)^{\ell(s;v)} σ j i ( − 1 ) ℓ ( s ; v ) , so the same discrepancy argument applies.
An active point costs Θ ( n z / 2 ) \Theta(n^{z/2}) Θ ( n z /2 ) . Using ⌈ n z / 2 ⌉ \lceil n^{z/2}\rceil ⌈ n z /2 ⌉ copies, each with n n n spheres, preserves the cost balance and uses O ( n ( z + 2 ) / 2 ) O(n^{(z+2)/2}) O ( n ( z + 2 ) /2 ) inactive centers. The relative-error scale remains 1 / ( n q L 2 ) 1/(\sqrt{nq}L^2) 1/ ( n q L 2 ) . Hence taking n ≃ k 2 / ( z + 2 ) n\simeq k^{2/(z+2)} n ≃ k 2/ ( z + 2 ) , L ≃ log ( 2 + k − 1 / ( z + 2 ) ε − 1 ) L\simeq\log(2+k^{-1/(z+2)}\varepsilon^{-1}) L ≃ log ( 2 + k − 1/ ( z + 2 ) ε − 1 ) , m ≃ k / L m\simeq k/L m ≃ k / L , and q ≃ ε − 2 / ( n L 4 ) q\simeq\varepsilon^{-2}/(nL^4) q ≃ ε − 2 / ( n L 4 ) gives
∣ X ∣ = ⌈ n z / 2 ⌉ n m q = Θ ~ ( k ( 2 z + 2 ) / ( z + 2 ) ε − 2 ) . |X|=\lceil n^{z/2}\rceil nmq=\widetilde{\Theta}(k^{(2z+2)/(z+2)}\varepsilon^{-2}). ∣ X ∣ = ⌈ n z /2 ⌉ nm q = Θ ( k ( 2 z + 2 ) / ( z + 2 ) ε − 2 ) .
Section 2.5 completes the parameter choices and the larger-error case of Theorem 1.2.
Lower bounds in doubling metrics (Theorem 1.4). Doubling metrics allow more flexible distance assignments than Euclidean space. This lets one center control more groups without increasing its distance scale. Take B B B separated copies, each with n m q nmq nm q distinct points p b , j , i , s p_{b,j,i,s} p b , j , i , s at unit distance from an anchor. Each label i ∈ [ m ] i\in[m] i ∈ [ m ] has n n n groups of q q q points, indexed by j j j . An active copy uses one center per label, with
d ( p b , j , i , s , c b , i ) = R − σ b i ( j ) χ s , R ≥ 4. d(p_{b,j,i,s},c_{b,i})=R-\sigma_{bi}^{(j)}\chi_s,\qquad R\geq4. d ( p b , j , i , s , c b , i ) = R − σ bi ( j ) χ s , R ≥ 4.
Here σ b i ∈ { − 1 , 1 } n \sigma_{bi}\in\{-1,1\}^n σ bi ∈ { − 1 , 1 } n , and χ ∈ H \chi\in\mathcal{H} χ ∈ H ranges over a fixed polynomial-size family supporting unbiased, four-wise independent signs. Other labels’ centers have distance R + 1 R+1 R + 1 , so c b , i c_{b,i} c b , i serves all its label’s groups without projection levels. Inactive copies use their anchors.
The dataset and candidate centers are fixed before seeing ( S , w ) (S,w) ( S , w ) .
For a candidate ( S , w ) (S,w) ( S , w ) with ∣ S ∣ ≤ ∣ X ∣ / 2 |S|\leq|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 , activate the g g g copies with most omissions. They omit at least half their points in total, not necessarily in each group. Subtract the signed errors of C ± = C ( ± σ , χ ) C^{\pm}=C(\pm\sigma,\chi) C ± = C ( ± σ , χ ) . Inactive contributions cancel; each active p = p b , j , i , s p=p_{b,j,i,s} p = p b , j , i , s satisfies
d z ( p , C − ) − d z ( p , C + ) = [ ( R + 1 ) z − ( R − 1 ) z ] σ b i ( j ) χ s . d^{z}(p,C^{-})-d^{z}(p,C^{+})=\left[(R+1)^{z}-(R-1)^{z}\right]\sigma_{b i}^{(j)}\chi_{s}. d z ( p , C − ) − d z ( p , C + ) = [ ( R + 1 ) z − ( R − 1 ) z ] σ bi ( j ) χ s .
The coefficient is constant across groups, so no calibration is needed. For fixed χ \chi χ , choose σ \sigma σ so that group contributions add rather than cancel. Lemma 3.2 gives one common χ \chi χ with error gap Ω ( g R z − 1 n m q ) \Omega(gR^{z-1}nm\sqrt{q}) Ω ( g R z − 1 nm q ) for arbitrary nonnegative retained weights. One query has absolute error at least half this gap and true cost O ( ( g R z + B ) n m q ) O((gR^{z}+B)nmq) O (( g R z + B ) nm q ) . Balancing B ≳ g R z B\gtrsim gR^{z} B ≳ g R z therefore gives relative error Ω ( 1 / ( R q ) ) \Omega(1/(R\sqrt{q})) Ω ( 1/ ( R q )) , rather than the Euclidean scale 1 / n q 1/\sqrt{nq} 1/ n q up to logarithmic factors. Increasing n n n adds points without weakening this error.
Counting all n m q nmq nm q inputs and m 2 n ∣ H ∣ m2^{n}|\mathcal{H}| m 2 n ∣ H ∣ candidates per copy gives dimension O ( n + log ( m + 1 ) + log ( q + 1 ) ) O(n+\log(m+1)+\log(q+1)) O ( n + log ( m + 1 ) + log ( q + 1 )) , since ∣ H ∣ = poly ( q + 1 ) |\mathcal{H}|=\operatorname{poly}(q+1) ∣ H ∣ = poly ( q + 1 ) . A radius-two ball contains 2 n 2^{n} 2 n candidates requiring separate radius-one balls, giving dimension Ω ( n ) \Omega(n) Ω ( n ) . The choices below satisfy m ≲ ε − z m\lesssim\varepsilon^{-z} m ≲ ε − z and q ≲ ε − 2 q\lesssim\varepsilon^{-2} q ≲ ε − 2 . Thus D ≳ log ( 2 / ε ) D\gtrsim\log(2/\varepsilon) D ≳ log ( 2/ ε ) allows n ≍ D n\asymp D n ≍ D while keeping dimension at most D D D . Joining copies and padding points along a line avoids dependence on their number.
Choose q ≍ ε − 2 R − 2 q\asymp\varepsilon^{-2}R^{-2} q ≍ ε − 2 R − 2 with a small constant to make the relative error exceed ε \varepsilon ε . Allocate B ≍ k B\asymp k B ≍ k and g m ≲ k gm\lesssim k g m ≲ k within the center budget B + g ( m − 1 ) ≤ k B+g(m-1)\leq k B + g ( m − 1 ) ≤ k . Together with cost balance, this gives m ≍ R z m\asymp R^{z} m ≍ R z , g ≲ k / R z g\lesssim k/R^{z} g ≲ k / R z , and
∣ X ∣ = B n m q ≍ k D ε − 2 R z − 2 , R z ≲ min { k , ε − z } . |X|=Bnmq\asymp kD\varepsilon^{-2}R^{z-2},\qquad R^{z}\lesssim\min\{k,\varepsilon^{-z}\}. ∣ X ∣ = B nm q ≍ k D ε − 2 R z − 2 , R z ≲ min { k , ε − z } .
where the restrictions follow from g , q ≥ 1 g,q\geq1 g , q ≥ 1 . Maximizing R R R yields
∣ X ∣ ≳ k D min { k 1 − 2 / z ε − 2 , ε − z } . |X|\gtrsim kD\min\{k^{1-2/z}\varepsilon^{-2},\varepsilon^{-z}\}. ∣ X ∣ ≳ k D min { k 1 − 2/ z ε − 2 , ε − z } .
Every coreset must retain more than half these points. The first branch uses g ≲ 1 g\lesssim1 g ≲ 1 ; the second has R ≳ ε − 1 R\gtrsim\varepsilon^{-1} R ≳ ε − 1 , q ≲ 1 q\lesssim1 q ≲ 1 , and m ≍ ε − z m\asymp\varepsilon^{-z} m ≍ ε − z . We then need g ≲ k ε z g\lesssim k\varepsilon^{z} g ≲ k ε z active copies to use the center budget. For z = 2 z=2 z = 2 , both branches give Θ ( k D ε − 2 ) \Theta(kD\varepsilon^{-2}) Θ ( k D ε − 2 ) . § 3 verifies the metric and handles boundary cases.
Upper bounds in doubling metrics (Theorem 1.4 ). For fixed z ≥ 2 z\geq2 z ≥ 2 , partition X X X around a constant-factor solution A A A with at most k k k anchors. Write M i = ∑ p ∈ P i u p M_i=\sum_{p\in P_i}u_p M i = ∑ p ∈ P i u p and V i = cost z ( P i , A ) V_i=\operatorname{cost}_{z}(P_i,A) V i = cost z ( P i , A ) for the mass and anchor cost of cluster P i P_i P i at a i a_i a i . Preserving M i M_i M i cancels the anchor term from the error, leaving g C ( p ) = d z ( p , C ) − d z ( a i , C ) gC(p)=d^{z}(p,C)-d^{z}(a_i,C) g C ( p ) = d z ( p , C ) − d z ( a i , C ) . To control it, sample nonnegative weights u ^ \widehat{u} u preserving V i V_i V i as well:
∑ p ∈ P i u ^ p = M i , ∑ p ∈ P i u ^ p d z ( p , A ) = V i , E u ^ p = u p . \sum_{p\in P_i}\widehat{u}_p=M_i,\qquad\sum_{p\in P_i}\widehat{u}_p d^{z}(p,A)=V_i,\qquad\mathbb{E}\widehat{u}_p=u_p. p ∈ P i ∑ u p = M i , p ∈ P i ∑ u p d z ( p , A ) = V i , E u p = u p .
The two exact constraints define a polytope whose vertices have at most two nonzero weights. Sampling vertices from a convex decomposition of the input weights gives unbiased two-point summaries (Lemma 4.2). We average independent summaries; their coordinates need not be independent. No ring decomposition is needed.
Hölder’s inequality gives ∑ p ∈ P i u ^ p d ( p , A ) ≤ M i 1 − 1 / z V i 1 / z \sum_{p\in P_i}\widehat{u}_p d(p,A)\leq M_i^{1-1/z}V_i^{1/z} ∑ p ∈ P i u p d ( p , A ) ≤ M i 1 − 1/ z V i 1/ z . Together with the metric inequalities and anchor-cost preservation, this yields, on every draw,
∣ ∑ p ∈ P i u ^ p g C ( p ) ∣ ≲ V i + d ( a i , C ) z − 1 M i 1 − 1 / z V i 1 / z . \left|\sum_{p\in P_i}\widehat{u}_p gC(p)\right|\lesssim V_i+d(a_i,C)^{z-1}M_i^{1-1/z}V_i^{1/z}. p ∈ P i ∑ u p g C ( p ) ≲ V i + d ( a i , C ) z − 1 M i 1 − 1/ z V i 1/ z .
Each draw is bounded by cluster totals, not the largest individual residual. Let V = ∑ i V i > 0 V = \sum_i V_i > 0 V = ∑ i V i > 0 , α i = V i / V \alpha_i = V_i/V α i = V i / V , and take s i = 1 + ⌈ T α i 2 / z ⌉ s_i = 1+\lceil T\alpha_i^{2/z}\rceil s i = 1 + ⌈ T α i 2/ z ⌉ summaries in P i P_i P i . After averaging, their squared ranges sum to O ( 1 / s i ) O(1/s_i) O ( 1/ s i ) times the preceding bound squared, canceling V i 2 / z V_i^{2/z} V i 2/ z . Since 2 − 2 / z ≥ 1 2-2/z \ge1 2 − 2/ z ≥ 1 , each remaining sum of powers is bounded by the power of the sum. Using ∑ i M i d z ( a i , C ) ≲ cost z ( X , C ) + V \sum_i M_i d^z(a_i,C) \lesssim\operatorname{cost}_z(X,C)+V ∑ i M i d z ( a i , C ) ≲ cost z ( X , C ) + V and V ≲ cost z ( X , C ) V \lesssim\operatorname{cost}_z(X,C) V ≲ cost z ( X , C ) gives a total of O ( cost z ( X , C ) 2 / T ) O(\operatorname{cost}_z(X,C)^2/T) O ( cost z ( X , C ) 2 / T ) . For each fixed query, Hoeffding bounds the probability of relative error exceeding ε \varepsilon ε by 2 exp ( − Ω ( ε 2 T ) ) 2\exp(-\Omega(\varepsilon^2T)) 2 exp ( − Ω ( ε 2 T )) . Concavity gives ∑ i α i 2 / z ≤ k 1 − 2 / z \sum_i \alpha_i^{2/z} \le k^{1-2/z} ∑ i α i 2/ z ≤ k 1 − 2/ z , hence ∣ S ∣ ≤ 2 ∑ i s i ≲ k + T k 1 − 2 / z |S| \le2\sum_i s_i \lesssim k+Tk^{1-2/z} ∣ S ∣ ≤ 2 ∑ i s i ≲ k + T k 1 − 2/ z . Zero-cost clusters are exact, including when V = 0 V=0 V = 0 .
To cover all queries, discard residuals where d ( p , A ) < c z ε d ( a i , C ) d(p,A)<c_z\varepsilon d(a_i,C) d ( p , A ) < c z ε d ( a i , C ) for small c z > 0 c_z>0 c z > 0 . These are O ( ε ) d z ( p , C ) O(\varepsilon)d^z(p,C) O ( ε ) d z ( p , C ) and controlled directly for input and sample. For the others, record a smallest covering ball for each center, together with its scale and the cluster cutoffs. At p p p , only records at scales at most d ( p , A ) d(p,A) d ( p , A ) are needed: they retain the nearest centers to p p p and a i a_i a i . Comparing queries with the same records controls both nearest distances in both directions. Lemma 4.4 gives a cover with logarithmic size H = O ( k log ( 2 ∣ X ∣ ) + k D log ( 2 / ε ) ) H=O(k\log(2|X|)+kD\log(2/\varepsilon)) H = O ( k log ( 2∣ X ∣ ) + k D log ( 2/ ε )) and pointwise error O ( ε ) d z ( p , A ) O(\varepsilon)d^z(p,A) O ( ε ) d z ( p , A ) , whose sum is bounded by anchor-cost preservation. For each vector, fix before sampling a representative with cost z ( X , C ) + V \operatorname{cost}_z(X,C)+V cost z ( X , C ) + V at most twice that of any query mapped to it. Its concentration bound then applies to all those queries. A union bound with T = O ( ε − 2 H ) T=O(\varepsilon^{-2}H) T = O ( ε − 2 H ) gives constant success probability.
Finally, iterative size reduction [BJKW21] gives a weighted coreset of size poly ( k , D , ε − 1 ) \operatorname{poly}(k,D,\varepsilon^{-1}) poly ( k , D , ε − 1 ) . Apply the sampling bound again, splitting the error budget between stages. Coreset composition gives
O ( k 2 − 2 / z ε − 2 [ D log ( 2 / ε ) + log ( 2 k ) ] ) = O ~ ( k 2 − 2 / z D ε − 2 ) . O\left(k^{2-2/z}\varepsilon^{-2}\left[D\log(2/\varepsilon)+\log(2k)\right]\right)=\widetilde{O}\left(k^{2-2/z}D\varepsilon^{-2}\right). O ( k 2 − 2/ z ε − 2 [ D log ( 2/ ε ) + log ( 2 k ) ] ) = O ( k 2 − 2/ z D ε − 2 ) .
Section 4 gives the details.
Other Related Work
Sharper bounds for clustering coresets. Bansal et al. [2 ] showed that sensitivity sampling constructs Euclidean k k k -means coresets of size O ~ ( min { k 3 / 2 ε − 2 , k ε − 4 } ) \widetilde{O}(\min\{k^{3/2}\varepsilon^{-2},k\varepsilon^{-4}\}) O ( min { k 3/2 ε − 2 , k ε − 4 }) . For instances with constant cost stability, the same algorithm achieves size O ~ ( k ε − 2 ) \widetilde{O}(k\varepsilon^{-2}) O ( k ε − 2 ) without knowing the stability parameter. Using VC dimension as a structural parameter, Cohen-Addad et al. [13 ] obtained improved k k k -median coreset bounds, including O ~ ( k ε − 2 ) \widetilde{O}(k\varepsilon^{-2}) O ( k ε − 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 [20 , 4 , 3 , 21 PSSW27] . For Euclidean capacitated ( k , z ) (k,z) ( k , z ) -clustering with fixed z ≥ 1 z\ge1 z ≥ 1 , Huang et al. [21 ] obtained coresets of size O ~ ( k 2 ε − 2 z − 2 ) \widetilde{O}(k^2\varepsilon^{-2z-2}) O ( k 2 ε − 2 z − 2 ) .2
Coresets for robust clustering. Coresets for clustering with outliers have also received substantial attention [18 , 21 JL25, 14 , 19 ] . For Euclidean ( k , z ) (k,z) ( k , z ) -clustering with m m m outliers and fixed z ≥ 1 z\ge1 z ≥ 1 , Huang et al. [19 ] obtained coresets of size O ( m ε − z ) + O ~ ( min { k ( 2 z + 2 ) / ( z + 2 ) ε − 2 , k ε − z − 2 } ) O(m\varepsilon^{-z})+\widetilde{O}(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},k\varepsilon^{-z-2}\}) O ( m ε − z ) + O ( min { k ( 2 z + 2 ) / ( z + 2 ) ε − 2 , k ε − z − 2 }) , and an alternative bound of O ( m ) + O ~ ( k ε − 2 z − 2 ) O(m)+\widetilde{O}(k\varepsilon^{-2z-2}) O ( m ) + O ( k ε − 2 z − 2 ) .
Optimal Euclidean lower bound
This section proves Theorem 1.2 . The first four subsections treat k k k -means with 0 < ε < k − 1 / 4 0<\varepsilon<k^{-1/4} 0 < ε < k − 1/4 , and the final subsection extends the construction to general powers z ≥ 1 z\ge1 z ≥ 1 across both the small- and large-error regimes, 0 < ε < k − 1 / ( z + 2 ) 0 < \varepsilon< k^{-1/(z+2)} 0 < ε < k − 1/ ( z + 2 ) and k − 1 / ( z + 2 ) ≤ ε < 1 k^{-1/(z+2)} \le\varepsilon< 1 k − 1/ ( z + 2 ) ≤ ε < 1 .
Construction of the dataset
We follow the far-apart-copy framework of [22 ] , in which each copy contains points on spheres centered along coordinate axes. We construct each offset from two orthogonal components: one identifies its label, and the other determines its projection level. Let n , m , q , L ≥ 1 n, m, q, L \ge1 n , m , q , L ≥ 1 be integer parameters to be chosen later. For now, assume that 2 L > q + ( q 3 ) 2^L > q + \binom{q}{3} 2 L > q + ( 3 q ) , as required by Lemma 2.1 ; we verify this condition when choosing the parameters. The dataset X ⊆ R d X \subseteq\mathbb{R}^d X ⊆ R d , where d = n + m + 2 L + 1 d = n + m + 2L + 1 d = n + m + 2 L + 1 , consists of n n n sufficiently separated translates of the set
p j , i , s = n e j + u i + x s , P = { p j , i , s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ] } . (2) 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)} p j , i , s = n e j + u i + x s , P = { p j , i , s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ]} . (2)
Here e 1 , … , e n e_1,\ldots,e_n e 1 , … , e n and u 1 , … , u m u_1,\ldots,u_m u 1 , … , u m are orthonormal bases of mutually orthogonal subspaces R n \mathbb{R}^n R n and R m \mathbb{R}^m R m . The distinct unit vectors x 1 , … , x q x_1,\ldots,x_q x 1 , … , x q lie in a third orthogonal subspace R 2 L \mathbb{R}^{2L} R 2 L ; fix them, together with the set V ⊆ R 2 L V \subseteq\mathbb{R}^{2L} V ⊆ R 2 L , as supplied by Lemma 2.1 below. We reserve the remaining coordinate direction, with unit vector f f f , for adjusting center norms. Because the three summands of p j , i , s p_{j,i,s} p j , i , s lie in mutually orthogonal subspaces, distinct triples ( j , i , s ) (j,i,s) ( j , i , s ) yield distinct points, giving ∣ P ∣ = n m q |P| = nmq ∣ P ∣ = nm q and ∣ X ∣ = n 2 m q |X| = n^2mq ∣ X ∣ = n 2 m q . Moreover, since ∥ p j , i , s − n e j ∥ 2 = ∥ u i + x s ∥ 2 = 2 \lVert p_{j,i,s} - \sqrt{n}e_j\rVert^2 = \lVert u_i + x_s\rVert^2 = 2 ∥ p j , i , s − n e j ∥ 2 = ∥ u i + x s ∥ 2 = 2 , each copy is partitioned in local coordinates into n n n spheres of radius 2 \sqrt{2} 2 centered at n e 1 , … , n e n \sqrt{n}e_1,\ldots,\sqrt{n}e_n n e 1 , … , n e n , with m q mq m q points per sphere. Our queries will incur squared cost Θ ( n ) \Theta(n) Θ ( n ) per point in one active copy and O ( 1 ) O(1) O ( 1 ) per point in the remaining n − 1 n-1 n − 1 copies, keeping both contributions of order ∣ X ∣ |X| ∣ X ∣ . The following lemma provides the vectors x s x_s x s and a family of directions V V V that induce a small number of projection levels while certifying a large discrepancy on the active copy.
Lemma 2.1 (Discrete projections and a discrepancy bound). Let L , q ≥ 1 L, q \ge1 L , q ≥ 1 be integers satisfying 2 L > q + ( q 3 ) 2^L > q + \binom{q}{3} 2 L > q + ( 3 q ) . There exist distinct vectors x 1 , … , x q ∈ R 2 L x_1,\ldots,x_q \in\mathbb{R}^{2L} x 1 , … , x q ∈ R 2 L and a nonempty finite set V ⊆ R 2 L V \subseteq\mathbb{R}^{2L} V ⊆ R 2 L with the following properties:
⟨ x s , v ⟩ ∈ { 1 − 2 ℓ L : ℓ ∈ { 0 , … , L } } . (3) \langle x_s, v\rangle\in\left\{1 - \frac{2\ell}{L} : \ell\in\{0,\ldots,L\}\right\}. \tag*{(3)} ⟨ x s , v ⟩ ∈ { 1 − L 2 ℓ : ℓ ∈ { 0 , … , L } } . (3) Define the level index ℓ ( s ; v ) ∈ { 0 , … , L } \ell(s;v) \in\{0,\ldots,L\} ℓ ( s ; v ) ∈ { 0 , … , L } by ⟨ x s , v ⟩ = 1 − 2 ℓ ( s ; v ) / L \langle x_s,v\rangle= 1 - 2\ell(s;v)/L ⟨ x s , v ⟩ = 1 − 2 ℓ ( s ; v ) / L .
For every integer t ≥ 1 t \ge1 t ≥ 1 and every collection of fixed coefficient vectors A ( 1 ) , … , A ( t ) ∈ R q A^{(1)},\ldots,A^{(t)} \in\mathbb{R}^q A ( 1 ) , … , A ( t ) ∈ R q ,
max v ∈ V ∑ r = 1 t ∣ ∑ s = 1 q A s ( r ) ( − 1 ) ℓ ( s ; v ) ∣ ≥ 1 3 ∑ r = 1 t ∥ A ( r ) ∥ 2 . (4) \max_{v \in V}\sum_{r=1}^{t}\left|\sum_{s=1}^{q} A_s^{(r)}(-1)^{\ell(s;v)}\right| \ge\frac{1}{\sqrt{3}}\sum_{r=1}^{t}\lVert A^{(r)}\rVert_2. \tag*{(4)} v ∈ V max r = 1 ∑ t s = 1 ∑ q A s ( r ) ( − 1 ) ℓ ( s ; v ) ≥ 3 1 r = 1 ∑ t ∥ A ( r ) ∥ 2 . (4) The vectors x s x_s x s and the set V V V depend only on L , q L,q L , q , not on the coefficient vectors.
The proof is deferred to § 2.4 . Each v ∈ V v \in V v ∈ V groups the indices s ∈ [ q ] s \in[q] s ∈ [ q ] according to their projection levels ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) . Having only L + 1 L+1 L + 1 levels allows the construction in § 2.2 to use just L + 1 L+1 L + 1 centers for each i ∈ [ m ] i \in[m] i ∈ [ m ] . Varying v v v allows both the grouping and the parity signs ( − 1 ) ℓ ( s ; v ) (-1)^{\ell(s;v)} ( − 1 ) ℓ ( s ; v ) to change; the discrepancy bound guarantees a single direction v ∈ V v \in V v ∈ V common to all sphere–label pairs that produces a large coresets error, as shown in § 2.3 .
A family of query center sets
Fix a candidate weighted subset ( S , w ) (S,w) ( S , w ) with ∣ S ∣ ≤ ∣ X ∣ / 2 |S| \le|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 . By averaging, at least one of the n n n copies has at most half of its points in S S S ; we fix such a copy P 1 P_1 P 1 as the active copy and call the remaining n − 1 n-1 n − 1 copies inactive . Our query family places adjustable centers in P 1 P_1 P 1 and a fixed center at each of the n ( n − 1 ) n(n-1) n ( n − 1 ) sphere centers of the inactive copies. Working in the local coordinates of P 1 P_1 P 1 (so that points p j , i , s ∈ P 1 p_{j,i,s} \in P_1 p j , i , s ∈ P 1 and their active centers undergo the same translation), we write w ( p j , i , s ) w(p_{j,i,s}) w ( p j , i , s ) for the weight assigned by S S S to p j , i , s ∈ P 1 p_{j,i,s} \in P_1 p j , i , s ∈ P 1 , setting w ( p j , i , s ) = 0 w(p_{j,i,s})=0 w ( p j , i , s ) = 0 if p j , i , s ∉ S p_{j,i,s} \notin S p j , i , s ∈ / S .
We call i ∈ [ m ] i \in[m] i ∈ [ m ] the label of the offsets u i + x s u_i+x_s u i + x s and their corresponding points on each sphere. For a fixed v ∈ V v \in V v ∈ V , the level of p j , i , s p_{j,i,s} p j , i , s is ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) , determined by ⟨ x s , v ⟩ = 1 − 2 ℓ ( s ; v ) / L \langle x_s,v\rangle=1-2\ell(s;v)/L ⟨ x s , v ⟩ = 1 − 2 ℓ ( s ; v ) / L . The points on sphere j j j with label i i i and level ℓ \ell ℓ form the cell
X j , i , ℓ ( v ) = { p j , i , s : s ∈ [ q ] , ℓ ( s ; v ) = ℓ } , j ∈ [ n ] , i ∈ [ m ] , 0 ≤ ℓ ≤ L . X_{j,i,\ell}(v)=\{p_{j,i,s}:s\in[q],\ \ell(s;v)=\ell\},\qquad j\in[n],\ i\in[m],\ 0\le\ell\le L. X j , i , ℓ ( v ) = { p j , i , s : s ∈ [ q ] , ℓ ( s ; v ) = ℓ } , j ∈ [ n ] , i ∈ [ m ] , 0 ≤ ℓ ≤ L .
Because ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) depends only on s s s and v v v , this partition into cells (some of which may be empty) is identical across all n n n spheres. A single active center c i , ℓ ( v , σ ) c_{i,\ell}(v,\sigma) c i , ℓ ( v , σ ) will serve the cells X j , i , ℓ ( v ) X_{j,i,\ell}(v) X j , i , ℓ ( v ) across all spheres j ∈ [ n ] j\in[n] j ∈ [ n ] , reducing the number of active centers from n m ( L + 1 ) nm(L+1) nm ( L + 1 ) to m ( L + 1 ) m(L+1) m ( L + 1 ) (see Figure 1 ).
Figure 1. The Euclidean lower-bound construction. (a) Points have the form p j , i , s = a j + u i + x s p_{j,i,s}=a_j+u_i+x_s p j , i , s = a j + u i + x s . Different colors indicate different offset groups. The same offset pattern repeats across spheres and copies. (b) Two candidate coresets select different sets of four points from the same eight-point group. Filled circles are selected points, each with weight 2; hollow circles are omitted points. For each candidate, we choose a direction v ∈ V v \in V v ∈ V and signs σ \sigma σ to obtain a center set C σ = C ( v , σ ) C_{\sigma}=C(v,\sigma) C σ = C ( v , σ ) from the fixed query family. The diamonds illustrate how the centers change with v v v and σ \sigma σ . The query detects a gap in total weighted cost; it need not make every selected point cheaper than every omitted point. Only a few centers are shown, and the drawing is not to scale.
Our family C ( v , σ ) C(v,\sigma) C ( v , σ ) is parameterized by v ∈ V v\in V v ∈ V and a sign array σ ∈ { − 1 , 1 } n × m \sigma\in\{-1,1\}^{n\times m} σ ∈ { − 1 , 1 } n × m . For each fixed v v v , the construction must keep the nearest-center assignments independent of σ \sigma σ . For a point on sphere j j j with label i i i and level ℓ \ell ℓ , its squared cost should consist of a sign-independent baseline depending only on ℓ \ell ℓ , plus a perturbation proportional to σ j i ( − 1 ) ℓ \sigma_{ji}(-1)^\ell σ j i ( − 1 ) ℓ with the same positive coefficient for all points. Let t ℓ : = 1 − 2 ℓ / L t_\ell:=1-2\ell/L t ℓ := 1 − 2 ℓ / L be the ℓ \ell ℓ -th projection value in (3) . For each ( i , ℓ ) ∈ [ m ] × { 0 , … , L } (i,\ell)\in[m]\times\{0,\ldots,L\} ( i , ℓ ) ∈ [ m ] × { 0 , … , L } , define the local center
c i , ℓ ( v , σ ) = 2 n u i + n t ℓ v − ( − 1 ) ℓ 16 L 2 ∑ j = 1 n σ j i e j + λ ℓ f , (5) 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)} c i , ℓ ( v , σ ) = 2 n u i + n t ℓ v − 16 L 2 ( − 1 ) ℓ j = 1 ∑ n σ j i e j + λ ℓ f , (5)
where f f f is a unit vector orthogonal to every data point, so its coefficient adjusts the center norm without changing point–center inner products. Choose
λ ℓ = ( 4 n + ( n − 2 n ) t ℓ 2 − n 256 L 4 ) 1 / 2 . \lambda_\ell=\left(4n+(\sqrt{n}-2n)t_\ell^2-\frac{n}{256L^4}\right)^{1/2}. λ ℓ = ( 4 n + ( n − 2 n ) t ℓ 2 − 256 L 4 n ) 1/2 .
The square root is well-defined: n − 2 n ≤ 0 \sqrt{n}-2n\le0 n − 2 n ≤ 0 , t ℓ 2 ≤ 1 t_\ell^2\le1 t ℓ 2 ≤ 1 , and L ≥ 1 L\ge1 L ≥ 1 imply that its radicand satisfies
4 n + ( n − 2 n ) t ℓ 2 − n 256 L 4 ≥ 511 256 n + n > 0. 4n+(\sqrt{n}-2n)t_\ell^2-\frac{n}{256L^4}\ge\frac{511}{256}n+\sqrt{n}>0. 4 n + ( n − 2 n ) t ℓ 2 − 256 L 4 n ≥ 256 511 n + n > 0.
The sign component has squared norm ∥ ∑ j = 1 n σ j i e j ∥ 2 = ∑ j = 1 n σ j i 2 = n \left\|\sum_{j=1}^{n}\sigma_{ji}e_j\right\|^2=\sum_{j=1}^{n}\sigma_{ji}^2=n ∑ j = 1 n σ j i e j 2 = ∑ j = 1 n σ j i 2 = n . The remaining norms are ∥ u i ∥ = ∥ f ∥ = 1 \|u_i\|=\|f\|=1 ∥ u i ∥ = ∥ f ∥ = 1 and ∥ v ∥ 2 = 2 \|v\|^2=2 ∥ v ∥ 2 = 2 , the latter by Lemma 2.1 . Combining these values with the sign-norm calculation gives
∥ c i , ℓ ( v , σ ) ∥ 2 = 4 n + 2 n t ℓ 2 + n 256 L 4 + λ ℓ 2 = 8 n + n t ℓ 2 . (6) \begin{aligned}
\|c_{i,\ell}(v,\sigma)\|^2=4n+2nt_\ell^2+\frac{n}{256L^4}+\lambda_\ell^2 \\
&=8n+\sqrt{n}t_\ell^2. \tag*{(6)}
\end{aligned} ∥ c i , ℓ ( v , σ ) ∥ 2 = 4 n + 2 n t ℓ 2 + 256 L 4 n + λ ℓ 2 = 8 n + n t ℓ 2 . (6)
The center norm is therefore independent of v v v and σ \sigma σ . We include a center for every label–level pair, even when its cells are empty. Different labels have different u i u_i u i -components; for a fixed label, different levels have different v v v -components because the values t ℓ t_\ell t ℓ are distinct and ∥ v ∥ 2 = 2 \|v\|^2=2 ∥ v ∥ 2 = 2 . Thus the m ( L + 1 ) m(L+1) m ( L + 1 ) active centers are distinct.
The full center set contains these m ( L + 1 ) m(L+1) m ( L + 1 ) active centers and the n ( n − 1 ) n(n-1) n ( n − 1 ) fixed sphere centers in the inactive copies. The parameter choice in § 2.3 will ensure that m ( L + 1 ) + n ( n − 1 ) ≤ k m(L+1)+n(n-1)\le k m ( L + 1 ) + n ( n − 1 ) ≤ k .
We obtain exactly k k k distinct centers by placing the remaining centers sufficiently far from X X X , 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 ∈ V v \in V v ∈ V and σ ∈ { − 1 , 1 } n × m \sigma\in\{-1,1\}^{n \times m} σ ∈ { − 1 , 1 } n × m , the center set C ( v , σ ) C(v,\sigma) C ( v , σ ) has the following properties:
Nearest-center assignment. For every j ∈ [ n ] j \in[n] j ∈ [ n ] , i ∈ [ m ] i \in[m] i ∈ [ m ] , and 0 ≤ ℓ ≤ L 0 \le\ell\le L 0 ≤ ℓ ≤ L , the unique nearest center of each point p ∈ X j , i , ℓ ( v ) p \in X_{j,i,\ell}(v) p ∈ X j , i , ℓ ( v ) is c i , ℓ ( v , σ ) c_{i,\ell}(v,\sigma) c i , ℓ ( v , σ ) .
Pointwise costs. For every p ∈ X j , i , ℓ ( v ) p \in X_{j,i,\ell}(v) p ∈ X j , i , ℓ ( v ) ,
d 2 ( p , C ( v , σ ) ) = D ℓ + n 8 L 2 σ j i ( − 1 ) ℓ , (7) d^2(p,C(v,\sigma)) = D_\ell+ \frac{\sqrt{n}}{8L^2}\sigma_{ji}(-1)^\ell, \tag*{(7)} d 2 ( p , C ( v , σ )) = D ℓ + 8 L 2 n σ j i ( − 1 ) ℓ , (7) where D ℓ = 9 n + 2 − 4 n − n t ℓ 2 D_\ell= 9n + 2 - 4\sqrt{n} - \sqrt{n}\,t_\ell^2 D ℓ = 9 n + 2 − 4 n − n t ℓ 2 , and
5 n ≤ d 2 ( p , C ( v , σ ) ) ≤ 9 n . (8) 5n \le d^2(p,C(v,\sigma)) \le9n. \tag*{(8)} 5 n ≤ d 2 ( p , C ( v , σ )) ≤ 9 n . (8) Every point in an inactive copy has squared cost 2 2 2 .
cost 2 ( X , C ( v , σ ) ) ≤ 11 ∣ X ∣ . \operatorname{cost}_2(X,C(v,\sigma)) \le11|X|. cost 2 ( X , C ( v , σ )) ≤ 11∣ X ∣.
Proof. Fix p = p j , i , s ∈ X j , i , ℓ ( v ) p=p_{j,i,s} \in X_{j,i,\ell}(v) p = p j , i , s ∈ X j , i , ℓ ( v ) , so that ⟨ x s , v ⟩ = t ℓ \langle x_s,v\rangle=t_\ell ⟨ x s , v ⟩ = t ℓ . First,
∥ p ∥ 2 = n + 2. \|p\|^2=n+2. ∥ p ∥ 2 = n + 2.
For any candidate indices i ′ ∈ [ m ] i' \in[m] i ′ ∈ [ m ] and 0 ≤ ℓ ′ ≤ L 0 \le\ell' \le L 0 ≤ ℓ ′ ≤ L , bilinearity and orthogonality give
⟨ p , c i ′ , ℓ ′ ( v , σ ) ⟩ = 2 n 1 { i ′ = i } + n t ℓ t ℓ ′ − n 16 L 2 ( − 1 ) ℓ ′ σ j i ′ . \langle p,c_{i',\ell'}(v,\sigma)\rangle
=2\sqrt{n}\,\mathbf{1}_{\{i'=i\}}+\sqrt{n}\,t_\ell t_{\ell'}-\frac{\sqrt{n}}{16L^2}(-1)^{\ell'}\sigma_{ji'}. ⟨ p , c i ′ , ℓ ′ ( v , σ )⟩ = 2 n 1 { i ′ = i } + n t ℓ t ℓ ′ − 16 L 2 n ( − 1 ) ℓ ′ σ j i ′ .
Substituting these quantities and (6) into the squared-distance identity gives
∥ p − c i ′ , ℓ ′ ( v , σ ) ∥ 2 = 9 n + 2 + n t ℓ ′ 2 − 4 n 1 { i ′ = i } − 2 n t ℓ t ℓ ′ + n 8 L 2 ( − 1 ) ℓ ′ σ j i ′ = D ℓ + n ( t ℓ ′ − t ℓ ) 2 + 4 n 1 { i ′ ≠ i } + n 8 L 2 ( − 1 ) ℓ ′ σ j i ′ . \begin{aligned}
\|p-c_{i',\ell'}(v,\sigma)\|^2
&=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'}\\
&=D_\ell+\sqrt{n}(t_{\ell'}-t_\ell)^2+4\sqrt{n}\,\mathbf{1}_{\{i'\ne i\}}+\frac{\sqrt{n}}{8L^2}(-1)^{\ell'}\sigma_{ji'}.
\end{aligned} ∥ p − c i ′ , ℓ ′ ( v , σ ) ∥ 2 = 9 n + 2 + n t ℓ ′ 2 − 4 n 1 { i ′ = i } − 2 n t ℓ t ℓ ′ + 8 L 2 n ( − 1 ) ℓ ′ σ j i ′ = D ℓ + n ( t ℓ ′ − t ℓ ) 2 + 4 n 1 { i ′ = i } + 8 L 2 n ( − 1 ) ℓ ′ σ j i ′ .
Here the square completion uses the two identities
n t ℓ ′ 2 − 2 n t ℓ t ℓ ′ = n ( t ℓ ′ − t ℓ ) 2 − n t ℓ 2 , \sqrt{n}\,t_{\ell'}^2-2\sqrt{n}\,t_\ell t_{\ell'}=\sqrt{n}(t_{\ell'}-t_\ell)^2-\sqrt{n}\,t_\ell^2, n t ℓ ′ 2 − 2 n t ℓ t ℓ ′ = n ( t ℓ ′ − t ℓ ) 2 − n t ℓ 2 ,
− 4 n 1 { i ′ = i } = − 4 n + 4 n 1 { i ′ ≠ i } . -4\sqrt{n}\,\mathbf{1}_{\{i'=i\}}=-4\sqrt{n}+4\sqrt{n}\,\mathbf{1}_{\{i'\ne i\}}. − 4 n 1 { i ′ = i } = − 4 n + 4 n 1 { i ′ = i } .
The u i u_i u i - and v v v -components produce the label and level penalties. The norm adjustment supplies the quadratic term needed to complete the square and keeps the common cost of order n n n . Both penalties vanish at ( i ′ , ℓ ′ ) = ( i , ℓ ) (i',\ell')=(i,\ell) ( i ′ , ℓ ′ ) = ( i , ℓ ) . If ℓ ′ ≠ ℓ \ell'\ne\ell ℓ ′ = ℓ , then
∣ t ℓ ′ − t ℓ ∣ = 2 ∣ ℓ ′ − ℓ ∣ L ≥ 2 L . |t_{\ell'}-t_\ell|=\frac{2|\ell'-\ell|}{L}\ge\frac{2}{L}. ∣ t ℓ ′ − t ℓ ∣ = L 2∣ ℓ ′ − ℓ ∣ ≥ L 2 .
A wrong level therefore incurs at least 4 n / L 2 4\sqrt{n}/L^2 4 n / L 2 . A wrong label incurs 4 n ≥ 4 n / L 2 4\sqrt{n} \ge4\sqrt{n}/L^2 4 n ≥ 4 n / L 2 , since L ≥ 1 L \ge1 L ≥ 1 . Meanwhile,
∣ ( − 1 ) ℓ ′ σ j i ′ − ( − 1 ) ℓ σ j i ∣ ≤ 2. \left|(-1)^{\ell'}\sigma_{ji'}-(-1)^\ell\sigma_{ji}\right| \le2. ( − 1 ) ℓ ′ σ j i ′ − ( − 1 ) ℓ σ j i ≤ 2.
Consequently, whenever ( i ′ , ℓ ′ ) ≠ ( i , ℓ ) (i',\ell') \ne(i,\ell) ( i ′ , ℓ ′ ) = ( i , ℓ ) ,
∥ p − c i , ℓ ′ ( v , σ ) ∥ 2 − ∥ p − c i , ℓ ( v , σ ) ∥ 2 ≥ 4 n L 2 − n 4 L 2 − 15 n 4 L 2 > 0. \left\|p-c_{i,\ell'}(v,\sigma)\right\|^2-\left\|p-c_{i,\ell}(v,\sigma)\right\|^2
\ge\frac{4\sqrt{n}}{L^2}-\frac{\sqrt{n}}{4L^2}-\frac{15\sqrt{n}}{4L^2}>0. ∥ p − c i , ℓ ′ ( v , σ ) ∥ 2 − ∥ p − c i , ℓ ( v , σ ) ∥ 2 ≥ L 2 4 n − 4 L 2 n − 4 L 2 15 n > 0.
Thus c i , ℓ ( v , σ ) c_{i,\ell}(v,\sigma) c i , ℓ ( v , σ ) is the unique nearest active center. Substituting ( i ′ , ℓ ′ ) = ( i , ℓ ) (i',\ell')=(i,\ell) ( i ′ , ℓ ′ ) = ( i , ℓ ) removes both penalties and yields (7) . The signs σ j i \sigma_{ji} σ j i will align the error contributions across pairs ( j , i ) (j,i) ( j , i ) , while ( − 1 ) ℓ (-1)^\ell ( − 1 ) ℓ distinguishes even and odd levels. The perturbation therefore tests the distribution of weights across levels, not just their total mass.
To verify the constants in (8) , first bound the cost from below:
∥ p − c i , ℓ ( v , σ ) ∥ 2 ≥ 9 n + 2 − 41 8 n ( t ℓ 2 ≤ 1 , L ≥ 1 ) ≥ 103 n − 9 16 ≥ 5 n ( 2 n ≤ n + 1 , n ≥ 1 ) . \begin{aligned}
\left\|p-c_{i,\ell}(v,\sigma)\right\|^2 \ge9n+2-\frac{41}{8}\sqrt{n}
\qquad(t_\ell^2\le1,\ L\ge1) \\
&\ge\frac{103n-9}{16}\ge5n
\qquad(2\sqrt{n}\le n+1,\ n\ge1).
\end{aligned} ∥ p − c i , ℓ ( v , σ ) ∥ 2 ≥ 9 n + 2 − 8 41 n ( t ℓ 2 ≤ 1 , L ≥ 1 ) ≥ 16 103 n − 9 ≥ 5 n ( 2 n ≤ n + 1 , n ≥ 1 ) .
For the upper estimate,
∥ p − c i , ℓ ( v , σ ) ∥ 2 ≤ 9 n + 2 − 31 8 n ( t ℓ 2 ≥ 0 , L ≥ 1 ) \left\|p-c_{i,\ell}(v,\sigma)\right\|^2 \le9n+2-\frac{31}{8}\sqrt{n}
\qquad(t_\ell^2\ge0,\ L\ge1) ∥ p − c i , ℓ ( v , σ ) ∥ 2 ≤ 9 n + 2 − 8 31 n ( t ℓ 2 ≥ 0 , L ≥ 1 )
Note for § 2.5 that both bounds in (8) remain valid whenever the sign perturbation has magnitude at most n / ( 8 L 2 ) \sqrt{n}/(8L^2) n / ( 8 L 2 ) .
We also verify that no center from another copy can be closer. In local coordinates,
∥ p ∥ 2 = n + 2 ≤ 3 n , ∥ c i , ℓ ( v , σ ) ∥ 2 ≤ 8 n + n ≤ 9 n , ∥ n e j ∥ 2 = n , \|p\|^2=n+2\le3n,\qquad\|c_{i,\ell}(v,\sigma)\|^2\le8n+\sqrt{n}\le9n,\qquad\|\sqrt{n}e_j\|^2=n, ∥ p ∥ 2 = n + 2 ≤ 3 n , ∥ c i , ℓ ( v , σ ) ∥ 2 ≤ 8 n + n ≤ 9 n , ∥ n e j ∥ 2 = n ,
where the middle bound uses (6) and n ≥ 1 n\ge1 n ≥ 1 . Thus all local points and centers have norm at most 3 n 3\sqrt{n} 3 n . The copies can be fixed in advance with translation vectors separated by at least 20 n 20\sqrt{n} 20 n . The reverse triangle inequality then gives a cross-copy distance of at least 20 n − 3 n − 3 n = 14 n 20\sqrt{n}-3\sqrt{n}-3\sqrt{n}=14\sqrt{n} 20 n − 3 n − 3 n = 14 n , whereas the triangle inequality gives a within-copy distance of at most 6 n 6\sqrt{n} 6 n . The copy separation is fixed uniformly over v v v and σ \sigma σ .
In an inactive copy, the squared distance from p j , i , s p_{j,i,s} p j , i , s to sphere center n e j ′ \sqrt{n}e_{j'} n e j ′ is
∥ p j , i , s − n e j ′ ∥ 2 = 2 n 1 { j ′ ≠ j } + 2. \left\|p_{j,i,s}-\sqrt{n}e_{j'}\right\|^2=2n\mathbf{1}_{\{j'\ne j\}}+2. p j , i , s − n e j ′ 2 = 2 n 1 { j ′ = j } + 2.
Thus its own sphere center is uniquely nearest, with squared cost 2 2 2 . Additional centers are placed far enough away to affect none of these assignments. The within-copy and cross-copy comparisons establish the global assignments and pointwise costs. Summing these costs gives
cost 2 ( X , C ( v , σ ) ) ≤ 9 n ∣ P 1 ∣ + 2 ( n − 1 ) ∣ P 1 ∣ (by xref‘(8)‘) \operatorname{cost}_2(X,C(v,\sigma))\le9n|P_1|+2(n-1)|P_1|\qquad\text{(by {xref}`(8)`) } cost 2 ( X , C ( v , σ )) ≤ 9 n ∣ P 1 ∣ + 2 ( n − 1 ) ∣ P 1 ∣ (by xref ‘(8)‘)
≤ 11 n ∣ P 1 ∣ = 11 ∣ X ∣ . (9) \le11n|P_1|=11|X|. \tag*{(9)} ≤ 11 n ∣ P 1 ∣ = 11∣ X ∣. (9)
□ \square □
Coreset error and parameter choice for k k k -means
We now choose two center sets from the preceding family whose signed errors are far apart, forcing at least one to have a large absolute error. Throughout this subsection, z = 2 z=2 z = 2 .
Proposition 2.3 (Detecting omissions with paired queries). For the dataset X X X constructed above, suppose n ( n − 1 ) + m ( L + 1 ) ≤ k n(n-1)+m(L+1)\le k n ( n − 1 ) + m ( L + 1 ) ≤ k . Let ( S , w ) (S,w) ( S , w ) be a nonnegatively weighted subset with ∣ S ∣ ≤ ∣ X ∣ / 2 |S|\le|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 , and choose an active copy P 1 P_1 P 1 as in § 2.2 . The associated query family contains a center set C C C such that
∣ cost 2 ( S , C ) − cost 2 ( X , C ) ∣ cost 2 ( X , C ) ≥ 1 176 3 n q L 2 . (10) \frac{\left|\operatorname{cost}_2(S,C)-\operatorname{cost}_2(X,C)\right|}{\operatorname{cost}_2(X,C)}
\ge\frac{1}{176\sqrt{3}\sqrt{nq}L^2}. \tag*{(10)} cost 2 ( X , C ) ∣ cost 2 ( S , C ) − cost 2 ( X , C ) ∣ ≥ 176 3 n q L 2 1 . (10)
Proof. Extend w w w by zero to X X X , and write
Δ ( C ) : = cost 2 ( S , C ) − cost 2 ( X , C ) = ∑ p ∈ X ( w ( p ) − 1 ) d 2 ( p , C ) . \Delta(C) := \operatorname{cost}_2(S,C)-\operatorname{cost}_2(X,C)=\sum_{p\in X}(w(p)-1)d^2(p,C). Δ ( C ) := cost 2 ( S , C ) − cost 2 ( X , C ) = p ∈ X ∑ ( w ( p ) − 1 ) d 2 ( p , C ) .
Opposite perturbations and sign maximization. For a fixed v ∈ V v\in V v ∈ V , reversing σ \sigma σ keeps the grouping fixed and cancels the baseline D ℓ D_\ell D ℓ . By Eq. (7) ,
d 2 ( p j , i , s , C ( v , σ ) ) − d 2 ( p j , i , s , C ( v , − σ ) ) = n 4 L 2 σ j i ( − 1 ) ℓ ( s ; v ) . 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)}. d 2 ( p j , i , s , C ( v , σ )) − d 2 ( p j , i , s , C ( v , − σ )) = 4 L 2 n σ j i ( − 1 ) ℓ ( s ; v ) .
Inactive points have the same cost under both queries, so their contributions cancel regardless of their weights. Hence
Δ ( C ( v , σ ) ) − Δ ( C ( v , − σ ) ) = n 4 L 2 ∑ j , i σ j i ∑ s = 1 q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) . \Delta(C(v,\sigma))-\Delta(C(v,-\sigma))
=\frac{\sqrt{n}}{4L^2}\sum_{j,i}\sigma_{ji}\sum_{s=1}^{q}(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}. Δ ( C ( v , σ )) − Δ ( C ( v , − σ )) = 4 L 2 n j , i ∑ σ j i s = 1 ∑ q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) .
For each fixed v v v , choose σ j i \sigma_{ji} σ j i with the sign of its inner sum, taking either sign when that sum is zero. These choices remove cancellation between different sphere–label pairs. Maximizing also over v v v gives
max v , σ [ Δ ( C ( v , σ ) ) − Δ ( C ( v , − σ ) ) ] = n 4 L 2 max v ∈ V ∑ j , i ∣ ∑ s = 1 q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) ∣ . (11) \max_{v,\sigma}\left[\Delta(C(v,\sigma))-\Delta(C(v,-\sigma))\right]
=\frac{\sqrt{n}}{4L^2}\max_{v\in V}\sum_{j,i}\left|\sum_{s=1}^{q}(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}\right|. \tag*{(11)} v , σ max [ Δ ( C ( v , σ )) − Δ ( C ( v , − σ )) ] = 4 L 2 n v ∈ V max j , i ∑ s = 1 ∑ q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) . (11)
Choosing v v v and counting omissions. The discrepancies within a pair may still cancel for a particular v v v . Apply Lemma 2.1 to the fixed coefficient vectors ( w ( p j , i , s ) − 1 ) s = 1 q (w(p_{j,i,s})-1)_{s=1}^{q} ( w ( p j , i , s ) − 1 ) s = 1 q , indexed by ( j , i ) ∈ [ n ] × [ m ] (j,i)\in[n]\times[m] ( j , i ) ∈ [ n ] × [ m ] , to obtain
max v ∈ V ∑ j , i ∣ ∑ s = 1 q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) ∣ ≥ 1 3 ∑ j , i ( ∑ s = 1 q ( w ( p j , i , s ) − 1 ) 2 ) 1 / 2 . (12) \max_{v\in V}\sum_{j,i}\left|\sum_{s=1}^{q}(w(p_{j,i,s})-1)(-1)^{\ell(s;v)}\right|
\ge\frac{1}{\sqrt{3}}\sum_{j,i}\left(\sum_{s=1}^{q}(w(p_{j,i,s})-1)^2\right)^{1/2}. \tag*{(12)} v ∈ V max j , i ∑ s = 1 ∑ q ( w ( p j , i , s ) − 1 ) ( − 1 ) ℓ ( s ; v ) ≥ 3 1 j , i ∑ ( s = 1 ∑ q ( w ( p j , i , s ) − 1 ) 2 ) 1/2 . (12)
The maximum is outside the sum, so one common v v v serves every pair.
Let M j i M_{ji} M j i count omitted points with sphere index j j j and label i i i in P 1 P_1 P 1 . Each omitted point has discrepancy − 1 -1 − 1 , while every squared discrepancy is nonnegative. Since M j i ≤ q M_{ji} \le q M j i ≤ q and ∑ j , i M j i ≥ ∣ P 1 ∣ / 2 \sum_{j,i} M_{ji} \ge|P_1|/2 ∑ j , i M j i ≥ ∣ P 1 ∣/2 ,
∑ j , i ( ∑ s = 1 q ( w ( p j , i , s ) − 1 ) 2 ) 1 / 2 ≥ ∑ j , i M j i ≥ ∑ j , i M j i q ≥ ∣ P 1 ∣ 2 q . (13) \begin{aligned}
\sum_{j,i}\left(\sum_{s=1}^{q}(w(p_{j,i,s})-1)^2\right)^{1/2} &\ge\sum_{j,i}\sqrt{M_{ji}} \\
&\ge\frac{\sum_{j,i}M_{ji}}{\sqrt{q}} \ge\frac{|P_1|}{2\sqrt{q}}. \tag*{(13)}
\end{aligned} j , i ∑ ( s = 1 ∑ q ( w ( p j , i , s ) − 1 ) 2 ) 1/2 ≥ j , i ∑ M j i ≥ q ∑ j , i M j i ≥ 2 q ∣ P 1 ∣ . (13)
Choose v , σ v,\sigma v , σ attaining the maximum in Eq. (11) , and set C + = C ( v , σ ) C^+ = C(v,\sigma) C + = C ( v , σ ) and C − = C ( v , − σ ) C^- = C(v,-\sigma) C − = C ( v , − σ ) . Combining Eqs. (12) and (13) gives
Δ ( C + ) − Δ ( C − ) ≥ n ∣ P 1 ∣ 8 3 q L 2 . \Delta(C^+) - \Delta(C^-) \ge\frac{\sqrt{n}|P_1|}{8\sqrt{3}\sqrt{q}L^2}. Δ ( C + ) − Δ ( C − ) ≥ 8 3 q L 2 n ∣ P 1 ∣ .
At least one query has absolute error at least half this gap. Its true cost is at most 11 ∣ X ∣ = 11 n ∣ P 1 ∣ 11|X| = 11n|P_1| 11∣ X ∣ = 11 n ∣ P 1 ∣ by Eq. (9) , proving Eq. (10) .
Consequently, at least one query has relative error at least 2 ε 2\varepsilon 2 ε whenever
ε n q L 2 ≤ c 0 , c 0 : = 1 352 3 . (14) \varepsilon\sqrt{nq}\,L^2 \le c_0,\qquad c_0 := \frac{1}{352\sqrt{3}}. \tag*{(14)} ε n q L 2 ≤ c 0 , c 0 := 352 3 1 . (14)
Together with the coding condition and the center budget, this forces every ε \varepsilon ε -coreset to contain more than ∣ X ∣ / 2 |X|/2 ∣ X ∣/2 points.
Parameter choice and contradiction. Ignoring rounding and fixed constants, the center budget and error condition suggest
n 2 ≲ k , m L ≲ k , q ≲ ε − 2 n L 4 . n^2 \lesssim k,\qquad mL \lesssim k,\qquad q \lesssim\frac{\varepsilon^{-2}}{nL^4}. n 2 ≲ k , m L ≲ k , q ≲ n L 4 ε − 2 .
For 0 < ε < k − 1 / 4 0 < \varepsilon< k^{-1/4} 0 < ε < k − 1/4 , choose
L = ⌈ 8 log 2 ( 2 + k − 1 / 4 ε − 1 ) ⌉ , q = max { 1 , ⌈ k − 1 / 2 ε − 2 L 4 ⌉ } , L = \left\lceil8\log_2(2+k^{-1/4}\varepsilon^{-1})\right\rceil,\qquad q = \max\left\{1,\left\lceil\frac{k^{-1/2}\varepsilon^{-2}}{L^4}\right\rceil\right\}, L = ⌈ 8 log 2 ( 2 + k − 1/4 ε − 1 ) ⌉ , q = max { 1 , ⌈ L 4 k − 1/2 ε − 2 ⌉ } ,
and round n , m n,m n , m down from sufficiently small fixed multiples of k , k / L \sqrt{k}, k/L k , k / L , respectively. Since q ≤ k − 1 / 2 ε − 2 q \le k^{-1/2}\varepsilon^{-2} q ≤ k − 1/2 ε − 2 ,
2 L ≥ ( 2 + k − 1 / 4 ε − 1 ) 8 > 2 ( k − 1 / 2 ε − 2 ) 3 ≥ q + ( q 3 ) . 2^L \ge(2+k^{-1/4}\varepsilon^{-1})^8 > 2(k^{-1/2}\varepsilon^{-2})^3 \ge q+\binom{q}{3}. 2 L ≥ ( 2 + k − 1/4 ε − 1 ) 8 > 2 ( k − 1/2 ε − 2 ) 3 ≥ q + ( 3 q ) .
Moreover, k − 1 / 4 ε − 1 ≥ 1 k^{-1/4}\varepsilon^{-1} \ge1 k − 1/4 ε − 1 ≥ 1 implies L 4 ≲ k − 1 / 2 ε − 2 L^4 \lesssim k^{-1/2}\varepsilon^{-2} L 4 ≲ k − 1/2 ε − 2 , so rounding q q q up to one loses only an absolute factor and q ≲ k − 1 / 2 ε − 2 / L 4 q \lesssim k^{-1/2}\varepsilon^{-2}/L^4 q ≲ k − 1/2 ε − 2 / L 4 .
Suppose first that n , m ≥ 1 n,m \ge1 n , m ≥ 1 . Then n ≍ k n \asymp\sqrt{k} n ≍ k and m ≍ k / L m \asymp k/L m ≍ k / L , and the sufficiently small leading constants ensure n ( n − 1 ) + m ( L + 1 ) ≤ k n(n-1)+m(L+1)\le k n ( n − 1 ) + m ( L + 1 ) ≤ k . With L L L fixed as above,
ε n q L 2 ≲ n k . \varepsilon\sqrt{nq}\,L^2 \lesssim\sqrt{\frac{n}{\sqrt{k}}}. ε n q L 2 ≲ k n .
Taking the leading constant in n n n sufficiently small makes this quantity at most c 0 c_0 c 0 . Thus every ε \varepsilon ε -coreset satisfies
∣ S ∣ > ∣ X ∣ 2 = 1 2 n 2 m q ≍ k 3 / 2 ε − 2 L 5 ≍ k 3 / 2 ε − 2 [ log ( 2 + k − 1 / 4 ε − 1 ) ] 5 . |S| > \frac{|X|}{2} = \frac{1}{2}n^2mq \asymp\frac{k^{3/2}\varepsilon^{-2}}{L^5} \asymp\frac{k^{3/2}\varepsilon^{-2}}{[\log(2+k^{-1/4}\varepsilon^{-1})]^5}. ∣ S ∣ > 2 ∣ X ∣ = 2 1 n 2 m q ≍ L 5 k 3/2 ε − 2 ≍ [ log ( 2 + k − 1/4 ε − 1 ) ] 5 k 3/2 ε − 2 .
If either rounded count vanishes, then k = O ( 1 ) k=O(1) k = O ( 1 ) or k = O ( L ) k=O(L) k = O ( L ) , respectively. In either case,
k 3 / 2 ε − 2 L 5 = k ε − 2 k L 5 = O ( k ε − 2 ) . \frac{k^{3/2}\varepsilon^{-2}}{L^5}=k\varepsilon^{-2}\frac{\sqrt{k}}{L^5}=O(k\varepsilon^{-2}). L 5 k 3/2 ε − 2 = k ε − 2 L 5 k = O ( k ε − 2 ) .
For ε < 1 / 2 \varepsilon<1/2 ε < 1/2 , the known Ω ( k ε − 2 ) \Omega(k\varepsilon^{-2}) Ω ( k ε − 2 ) lower bound for k k k -means [9 Theorem 11] therefore suffices. For ε ≥ 1 / 2 \varepsilon\ge1/2 ε ≥ 1/2 , take X X X to consist of k k k distinct points. Any proper weighted subset has zero cost for a query containing its retained points and padded to k k k distinct centers outside X X X , while the true cost is positive. Thus all k k k points are necessary; since ε − 2 ≤ 4 \varepsilon^{-2}\le4 ε − 2 ≤ 4 , this gives the required Ω ( k ε − 2 ) \Omega(k\varepsilon^{-2}) Ω ( k ε − 2 ) bound. This completes the k k k -means lower bound throughout 0 < ε < k − 1 / 4 0<\varepsilon<k^{-1/4} 0 < ε < k − 1/4 .
Proof of Lemma 2.1: projection levels and signs
We now prove the projection lemma used in the preceding construction and error analysis.
Proof of Lemma 2.1. We first construct distinct binary words b 1 , … , b q ∈ { 0 , 1 } L b_1,\ldots,b_q\in\{0,1\}^{L} b 1 , … , b q ∈ { 0 , 1 } L such that no four distinct words sum to zero. Sums of binary words are taken coordinatewise modulo two. Suppose b 1 , … , b s − 1 b_1,\ldots,b_{s-1} b 1 , … , b s − 1 have been chosen. To choose b s b_s b s , exclude
{ b s ′ : 1 ≤ s ′ < s } ∪ { b s 1 + b s 2 + b s 3 : 1 ≤ s 1 < s 2 < s 3 < s } . \{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\}. { b s ′ : 1 ≤ s ′ < s } ∪ { b s 1 + b s 2 + b s 3 : 1 ≤ s 1 < s 2 < s 3 < s } .
The number of excluded words is at most
( s − 1 ) + ( s − 1 3 ) < q + ( q 3 ) < 2 L ( s ≤ q and the lemma’s hypothesis ) . (s-1)+\binom{s-1}{3}<q+\binom{q}{3}<2^L \qquad(s\le q\text{ and the lemma's hypothesis}). ( s − 1 ) + ( 3 s − 1 ) < q + ( 3 q ) < 2 L ( s ≤ q and the lemma’s hypothesis ) .
The two terms count previous words and previous triples; coincident exclusions only reduce the count. Fewer than all binary words are excluded, so a valid choice remains at every step. The first exclusion enforces distinctness; the second rules out a four-word zero sum, since its last word would equal the sum of three earlier words.
Let h a , β h_{a,\beta} h a , β , for a ∈ [ L ] a\in[L] a ∈ [ L ] and β ∈ { 0 , 1 } \beta\in\{0,1\} β ∈ { 0 , 1 } , be an orthonormal basis of R 2 L \mathbb{R}^{2L} R 2 L , and let b s ( a ) b_s(a) b s ( a ) denote the a a a th bit of b s b_s b s . Define
x s = 1 L ∑ a = 1 L h a , b s ( a ) , s ∈ [ q ] . x_s=\frac{1}{\sqrt{L}}\sum_{a=1}^{L}h_{a,b_s(a)},\qquad s\in[q]. x s = L 1 a = 1 ∑ L h a , b s ( a ) , s ∈ [ q ] .
These vectors have unit norm:
∥ x s ∥ 2 = 1 L ∑ a = 1 L 1 = 1. \lVert x_s\rVert^2=\frac{1}{L}\sum_{a=1}^{L}1=1. ∥ x s ∥ 2 = L 1 a = 1 ∑ L 1 = 1.
If two binary words differ at coordinate a a a , their vectors have different coefficients on h a , 0 h_{a,0} h a , 0 and h a , 1 h_{a,1} h a , 1 . Hence the vectors are distinct.
Draw the signs r a , β r_{a,\beta} r a , β independently and uniformly from { − 1 , 1 } \{-1,1\} { − 1 , 1 } , and set
v = 1 L ∑ a = 1 L ∑ β ∈ { 0 , 1 } r a , β h a , β . v=\frac{1}{\sqrt{L}}\sum_{a=1}^{L}\sum_{\beta\in\{0,1\}}r_{a,\beta}h_{a,\beta}. v = L 1 a = 1 ∑ L β ∈ { 0 , 1 } ∑ r a , β h a , β .
Distinct sign arrays have distinct coordinates in the basis, so the 2 2 L 2^{2L} 2 2 L arrays yield 2 2 L 2^{2L} 2 2 L vectors; let V V V be their set. Moreover,
∥ v ∥ 2 = 1 L ∑ a = 1 L ∑ β ∈ { 0 , 1 } r a , β 2 = 2. \lVert v\rVert^2=\frac{1}{L}\sum_{a=1}^{L}\sum_{\beta\in\{0,1\}}r_{a,\beta}^2=2. ∥ v ∥ 2 = L 1 a = 1 ∑ L β ∈ { 0 , 1 } ∑ r a , β 2 = 2.
Throughout this proof, E v \mathbb{E}_v E v denotes the uniform average over V V V , equivalently expectation over the independent signs. This averaging argument establishes a maximum bound for the fixed family; it does not randomize the dataset. Let ℓ ( s ; v ) \ell(s;v) ℓ ( s ; v ) count the coordinates a a a with r a , b s ( a ) = − 1 r_{a,b_s}(a)=-1 r a , b s ( a ) = − 1 . Then
⟨ x s , v ⟩ = 1 L ∑ a = 1 L r a , b s ( a ) = 1 − 2 ℓ ( s ; v ) L . \langle x_s,v\rangle=\frac{1}{L}\sum_{a=1}^{L}r_{a,b_s}(a)=1-\frac{2\ell(s;v)}{L}. ⟨ x s , v ⟩ = L 1 a = 1 ∑ L r a , b s ( a ) = 1 − L 2 ℓ ( s ; v ) .
This proves (3) . The same count also gives
∏ a = 1 L r a , b s ( a ) = ( − 1 ) ℓ ( s ; v ) . (15) \prod_{a=1}^{L}r_{a,b_s}(a)=(-1)^{\ell(s;v)}. \tag*{(15)} a = 1 ∏ L r a , b s ( a ) = ( − 1 ) ℓ ( s ; v ) . (15)
For the moment calculations, write χ s ( v ) : = ( − 1 ) ℓ ( s ; v ) \chi_s(v):=(-1)^{\ell(s;v)} χ s ( v ) := ( − 1 ) ℓ ( s ; v ) . Fix a coefficient vector A = ( A s ) s = 1 q ∈ R q A=(A_s)_{s=1}^{q}\in\mathbb{R}^{q} A = ( A s ) s = 1 q ∈ R q and define
Y ( v ) : = ∑ s = 1 q A s χ s ( v ) . Y(v):=\sum_{s=1}^{q}A_s\chi_s(v). Y ( v ) := s = 1 ∑ q A s χ s ( v ) .
The second moment identifies the scale ∥ A ∥ 2 2 \lVert A\rVert_2^2 ∥ 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] T ⊆ [ q ] of size 2 or 4,
E v ∏ s ∈ T χ s ( v ) = 0. (16) \mathbb{E}_v\prod_{s\in T}\chi_s(v)=0. \tag*{(16)} E v s ∈ T ∏ χ s ( v ) = 0. (16)
For each a a a , let N a : = ∑ s ∈ T b s ( a ) N_a:=\sum_{s\in T}b_s(a) N a := ∑ s ∈ T b s ( a ) be an ordinary integer sum, counting the words in T T T whose a a a th bit is 1. The other ∣ T ∣ − N a |T|-N_a ∣ T ∣ − N a words have bit 0. Hence
∏ s ∈ T χ s ( v ) = ∏ a = 1 L r a , 0 ∣ T ∣ − N a r a , 1 N a (by xref‘(15)‘). \prod_{s\in T}\chi_s(v)=\prod_{a=1}^{L}r_{a,0}^{|T|-N_a}r_{a,1}^{N_a}
\qquad\text{(by {xref}`(15)`).} s ∈ T ∏ χ s ( v ) = a = 1 ∏ L r a , 0 ∣ T ∣ − N a r a , 1 N a (by xref ‘(15)‘).
If ∣ T ∣ = 2 |T|=2 ∣ T ∣ = 2 , distinctness gives ∑ s ∈ T b s ≠ 0 \sum_{s\in T}b_s\ne0 ∑ s ∈ T b s = 0 modulo two. If ∣ T ∣ = 4 |T|=4 ∣ T ∣ = 4 , the exclusion of four-word zero sums gives the same conclusion. Thus some coordinate a ∗ a_* a ∗ has N a ∗ N_{a_*} N a ∗ odd. At that coordinate,
E [ r a ∗ , 1 N a ∗ ] = E [ r a ∗ , 1 ] = 0 , \mathbb{E}[r_{a_*,1}^{N_{a_*}}]=\mathbb{E}[r_{a_*,1}]=0, E [ r a ∗ , 1 N a ∗ ] = E [ r a ∗ , 1 ] = 0 ,
because an odd power of a sign equals the sign itself and the sign is uniform. By independence,
E v ∏ s ∈ T χ s ( v ) = ∏ a = 1 L ( E [ r a , 0 ∣ T ∣ − N a ] E [ r a , 1 N a ] ) (independent signs) = 0 (the a ∗ , 1 factor vanishes). \begin{aligned}
\mathbb{E}_v\prod_{s\in T}\chi_s(v)
&=\prod_{a=1}^{L}\left(\mathbb{E}[r_{a,0}^{|T|-N_a}]\mathbb{E}[r_{a,1}^{N_a}]\right)
\qquad\text{(independent signs)}\\
&=0\qquad\text{(the }a_{*,1}\text{ factor vanishes).}
\end{aligned} E v s ∈ T ∏ χ s ( v ) = a = 1 ∏ L ( E [ r a , 0 ∣ T ∣ − N a ] E [ r a , 1 N a ] ) (independent signs) = 0 (the a ∗ , 1 factor vanishes).
This proves (16) . For a product of one or three distinct χ s \chi_s χ s , the total multiplicity at each coordinate is odd, so at least one of r a , 0 , r a , 1 r_{a,0},r_{a,1} r 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 χ s is a sign, so χ s 2 = 1 \chi_s^2=1 χ s 2 = 1 . Expanding the second moment gives
E v Y 2 = ∑ s = 1 q A s 2 = ∥ A ∥ 2 2 (by xref‘(16)‘). \mathbb{E}_v Y^2=\sum_{s=1}^{q} A_s^2=\lVert A\rVert_2^2 \qquad\text{(by {xref}`(16)`).} E v Y 2 = s = 1 ∑ q A s 2 = ∥ A ∥ 2 2 (by xref ‘(16)‘).
In the fourth moment, multiplicity patterns 3 + 1 3+1 3 + 1 and 2 + 1 + 1 2+1+1 2 + 1 + 1 reduce to products of two distinct signs; pattern 1 + 1 + 1 + 1 1+1+1+1 1 + 1 + 1 + 1 uses four distinct signs. Their expectations vanish by (16) . The surviving patterns are 4 4 4 and 2 + 2 2+2 2 + 2 , and the latter has ( 4 2 ) = 6 \binom{4}{2}=6 ( 2 4 ) = 6 orderings. Therefore,
E v Y 4 = ∑ s A s 4 + 6 ∑ s < s ′ A s 2 A s ′ 2 = 3 ( ∑ s A s 2 ) 2 − 2 ∑ s A s 4 ≤ 3 ∥ A ∥ 2 4 . \begin{aligned}
\mathbb{E}_v Y^4=\sum_s A_s^4+6\sum_{s<s'}A_s^2A_{s'}^2 \\
&=3\left(\sum_s A_s^2\right)^2-2\sum_s A_s^4\le3\lVert A\rVert_2^4.
\end{aligned} E v Y 4 = s ∑ A s 4 + 6 s < s ′ ∑ A s 2 A s ′ 2 = 3 ( s ∑ A s 2 ) 2 − 2 s ∑ A s 4 ≤ 3 ∥ A ∥ 2 4 .
If A = 0 A=0 A = 0 , the required average bound is immediate. Otherwise E v Y 2 > 0 \mathbb{E}_vY^2>0 E v Y 2 > 0 , so E v Y 4 > 0 \mathbb{E}_vY^4>0 E v Y 4 > 0 and Lemma 2.4 applies:
E v ∣ Y ∣ ≥ ( E v Y 2 ) 3 / 2 ( E v Y 4 ) 1 / 2 (xref‘Lemma 2.4‘) ≥ 1 3 ∥ A ∥ 2 (the second and fourth moments). \begin{aligned}
\mathbb{E}_v|Y|\ge\frac{(\mathbb{E}_vY^2)^{3/2}}{(\mathbb{E}_vY^4)^{1/2}}\qquad\text{({xref}`Lemma 2.4`)} \\
&\ge\frac{1}{\sqrt{3}}\lVert A\rVert_2\qquad\text{(the second and fourth moments).}
\end{aligned} E v ∣ Y ∣ ≥ ( E v Y 4 ) 1/2 ( E v Y 2 ) 3/2 ( xref ‘Lemma 2.4‘) ≥ 3 1 ∥ A ∥ 2 (the second and fourth moments).
For the vectors A ( 1 ) , … , A ( t ) A^{(1)},\ldots,A^{(t)} A ( 1 ) , … , A ( t ) in the lemma, let Y r ( v ) : = ∑ s A s ( r ) χ s ( v ) Y_r(v):=\sum_s A_s^{(r)}\chi_s(v) Y r ( v ) := ∑ s A s ( r ) χ s ( v ) . Summing the expectation bounds for the coefficient vectors and comparing the average with the maximum yields
max v ∈ V ∑ r = 1 t ∣ Y r ( v ) ∣ ≥ E v ∑ r = 1 t ∣ Y r ( v ) ∣ = ∑ r = 1 t E v ∣ Y r ( v ) ∣ ≥ 1 3 ∑ r = 1 t ∥ A ( r ) ∥ 2 (the average bound for each vector). \begin{aligned}
\max_{v\in V}\sum_{r=1}^{t}|Y_r(v)|\ge\mathbb{E}_v\sum_{r=1}^{t}|Y_r(v)|=\sum_{r=1}^{t}\mathbb{E}_v|Y_r(v)| \\
&\ge\frac{1}{\sqrt{3}}\sum_{r=1}^{t}\lVert A^{(r)}\rVert_2\qquad\text{(the average bound for each vector).}
\end{aligned} v ∈ V max r = 1 ∑ t ∣ Y r ( v ) ∣ ≥ E v r = 1 ∑ t ∣ Y r ( v ) ∣ = r = 1 ∑ t E v ∣ Y r ( v ) ∣ ≥ 3 1 r = 1 ∑ t ∥ A ( r ) ∥ 2 (the average bound for each vector).
Substituting the definitions of Y r Y_r Y r and χ s \chi_s χ s gives (4) , with one common v v v for every coefficient vector. □
Lemma 2.4 (Moment interpolation). Every real-valued random variable Y Y Y with 0 < E ∣ Y ∣ 4 < ∞ 0<\mathbb{E}|Y|^4<\infty 0 < E ∣ Y ∣ 4 < ∞ satisfies
E ∣ Y ∣ ≥ ( E ∣ Y ∣ 2 ) 3 / 2 ( E ∣ Y ∣ 4 ) 1 / 2 . \mathbb{E}|Y|\ge\frac{(\mathbb{E}|Y|^2)^{3/2}}{(\mathbb{E}|Y|^4)^{1/2}}. E ∣ Y ∣ ≥ ( E ∣ Y ∣ 4 ) 1/2 ( E ∣ Y ∣ 2 ) 3/2 . Proof. The first and second absolute moments are finite because ∣ Y ∣ r ≤ 1 + ∣ Y ∣ 4 |Y|^r\le1+|Y|^4 ∣ Y ∣ r ≤ 1 + ∣ Y ∣ 4 for r ∈ { 1 , 2 } r\in\{1,2\} r ∈ { 1 , 2 } . Factor ∣ Y ∣ 2 |Y|^2 ∣ Y ∣ 2 so that Hölder’s exponents are 3 / 2 3/2 3/2 and 3 3 3 :
E ∣ Y ∣ 2 = E [ ∣ Y ∣ 2 / 3 ∣ Y ∣ 4 / 3 ] \mathbb{E}|Y|^2=\mathbb{E}\left[|Y|^{2/3}|Y|^{4/3}\right] E ∣ Y ∣ 2 = E [ ∣ Y ∣ 2/3 ∣ Y ∣ 4/3 ] ≤ ( E ∣ Y ∣ ) 2 / 3 ( E ∣ Y ∣ 4 ) 1 / 3 (H o ¨ lder, 3/2 and 3). \le(\mathbb{E}|Y|)^{2/3}(\mathbb{E}|Y|^4)^{1/3}\qquad\text{(Hölder, 3/2 and 3).} ≤ ( E ∣ Y ∣ ) 2/3 ( E ∣ Y ∣ 4 ) 1/3 (H o ¨ lder, 3/2 and 3). Raising both sides to the power 3 / 2 3/2 3/2 , which preserves the inequality between nonnegative quantities, gives
( E ∣ Y ∣ 2 ) 3 / 2 ≤ E ∣ Y ∣ ( E ∣ Y ∣ 4 ) 1 / 2 . (\mathbb{E}|Y|^2)^{3/2}\le\mathbb{E}|Y|(\mathbb{E}|Y|^4)^{1/2}. ( E ∣ Y ∣ 2 ) 3/2 ≤ E ∣ Y ∣ ( E ∣ Y ∣ 4 ) 1/2 . Dividing by ( E ∣ Y ∣ 4 ) 1 / 2 > 0 (\mathbb{E}|Y|^4)^{1/2}>0 ( E ∣ Y ∣ 4 ) 1/2 > 0 proves the claim. □
General powers and remaining parameter ranges
General powers z ≥ 1 z \ge1 z ≥ 1 . Fix a real z ≥ 1 z \ge1 z ≥ 1 and 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 . We retain the local dataset and projection family, but use ⌈ n z / 2 ⌉ \lceil n^{z/2}\rceil ⌈ n z /2 ⌉ copies instead of n n n . Each copy still contains n m q nmq nm q points, so
∣ X ∣ = ⌈ n z / 2 ⌉ n m q ≍ n ( z + 2 ) / 2 m q . |X| = \lceil n^{z/2}\rceil nmq \asymp n^{(z+2)/2}mq. ∣ X ∣ = ⌈ n z /2 ⌉ nm q ≍ n ( z + 2 ) /2 m q .
The active points will have cost Θ ( n z / 2 ) \Theta(n^{z/2}) Θ ( n z /2 ) , so this copy count keeps the active contribution comparable to ∣ X ∣ |X| ∣ X ∣ . For a weighted subset ( S , w ) (S,w) ( S , w ) with ∣ S ∣ ≤ ∣ X ∣ / 2 |S| \le|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 , extend w w w by zero to X X X and choose an active copy P 1 P_1 P 1 containing at most half its points in S S S , as before. Each inactive copy receives its n n n fixed sphere centers. Together with the m ( L + 1 ) m(L+1) m ( L + 1 ) active centers, this uses n ( ⌈ n z / 2 ⌉ − 1 ) + m ( L + 1 ) n(\lceil n^{z/2}\rceil-1)+m(L+1) n (⌈ n z /2 ⌉ − 1 ) + m ( L + 1 ) centers; we verify the budget below and pad to exactly k k k centers as before.
The remaining change is to the perturbation magnitudes. For z = 2 z=2 z = 2 , opposite perturbations give the same pointwise cost difference at every level. For general z z z , taking the z / 2 z/2 z /2 -th power introduces a dependence on the baseline D ℓ D_\ell D ℓ . We compensate by choosing, for every 0 ≤ ℓ ≤ L 0 \le\ell\le L 0 ≤ ℓ ≤ L , a magnitude δ ℓ ∈ ( 0 , 1 / ( 16 L 2 ) ] \delta_\ell\in(0,1/(16L^2)] δ ℓ ∈ ( 0 , 1/ ( 16 L 2 )] satisfying
( D ℓ + 2 n δ ℓ ) z / 2 − ( D ℓ − 2 n δ ℓ ) z / 2 = n ( z − 1 ) / 2 32 L 2 . (17) \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)} ( D ℓ + 2 n δ ℓ ) z /2 − ( D ℓ − 2 n δ ℓ ) z /2 = 32 L 2 n ( z − 1 ) /2 . (17)
Both arguments lie in [ 5 n , 9 n ] [5n,9n] [ 5 n , 9 n ] throughout the allowed interval, by the estimates in Claim 2.2 . Since ( z / 2 ) u z / 2 − 1 ≥ n z / 2 − 1 / 6 (z/2)u^{z/2-1}\ge n^{z/2-1}/6 ( z /2 ) u z /2 − 1 ≥ n z /2 − 1 /6 on this interval for every z ≥ 1 z\ge1 z ≥ 1 , the mean value theorem gives
( D ℓ + n 8 L 2 ) z / 2 − ( D ℓ − n 8 L 2 ) z / 2 ≥ n ( z − 1 ) / 2 24 L 2 . \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}. ( D ℓ + 8 L 2 n ) z /2 − ( D ℓ − 8 L 2 n ) z /2 ≥ 24 L 2 n ( z − 1 ) /2 .
The gap is continuous and strictly increasing from zero to a value above the target, so the required δ ℓ \delta_\ell δ ℓ exists uniquely. It depends only on z , n , L , ℓ z,n,L,\ell z , n , L , ℓ , not on v , σ , S v,\sigma,S v , σ , S , or w w w .
In the active-center formula of § 2.2 , replace 1 / ( 16 L 2 ) 1/(16L^2) 1/ ( 16 L 2 ) by δ ℓ \delta_\ell δ ℓ and set
λ ℓ = ( 4 n + ( n − 2 n ) t ℓ 2 − n δ ℓ 2 ) 1 / 2 . \lambda_\ell=\left(4n+(\sqrt{n}-2n)t_\ell^2-n\delta_\ell^2\right)^{1/2}. λ ℓ = ( 4 n + ( n − 2 n ) t ℓ 2 − n δ ℓ 2 ) 1/2 .
The radicand only increases, and the squared center norm remains 8 n + n t ℓ 2 8n+\sqrt{n}\,t_\ell^2 8 n + n t ℓ 2 . The label and level penalties in Claim 2.2 are unchanged, while each sign perturbation still has absolute value at most n / ( 8 L 2 ) \sqrt{n}/(8L^2) n / ( 8 L 2 ) . Thus the same nearest-center comparison and separation between copies apply. An active point p j , i , s p_{j,i,s} p j , i , s at level ℓ = ℓ ( s ; v ) \ell=\ell(s;v) ℓ = ℓ ( s ; v ) therefore has cost
d z ( p j , i , s , C ( v , σ ) ) = ( D ℓ + 2 n δ ℓ σ j i ( − 1 ) ℓ ) z / 2 ∈ [ ( 5 n ) z / 2 , ( 9 n ) z / 2 ] , d^z(p_{j,i,s},C(v,\sigma))=\left(D_\ell+2\sqrt{n}\,\delta_\ell\sigma_{ji}(-1)^\ell\right)^{z/2}\in[(5n)^{z/2},(9n)^{z/2}], d z ( p j , i , s , C ( v , σ )) = ( D ℓ + 2 n δ ℓ σ j i ( − 1 ) ℓ ) z /2 ∈ [( 5 n ) z /2 , ( 9 n ) z /2 ] ,
whereas every inactive point has cost 2 z / 2 2^{z/2} 2 z /2 . Consequently,
cost z ( X , C ( v , σ ) ) ≤ ( 9 n ) z / 2 ∣ P 1 ∣ + 2 z / 2 ( ⌈ n z / 2 ⌉ − 1 ) ∣ P 1 ∣ ≲ n z / 2 ∣ P 1 ∣ ≍ ∣ X ∣ . (18) \operatorname{cost}_z(X,C(v,\sigma))\le(9n)^{z/2}|P_1|+2^{z/2}(\lceil n^{z/2}\rceil-1)|P_1|
\lesssim n^{z/2}|P_1|\asymp|X|. \tag*{(18)} cost z ( X , C ( v , σ )) ≤ ( 9 n ) z /2 ∣ P 1 ∣ + 2 z /2 (⌈ n z /2 ⌉ − 1 ) ∣ P 1 ∣ ≲ n z /2 ∣ P 1 ∣ ≍ ∣ X ∣. (18)
Write Δ ( C ) = cost z ( S , C ) − cost z ( X , C ) \Delta(C)=\operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C) Δ ( C ) = cost z ( S , C ) − cost z ( X , C ) . By Eq. (17) , opposite sign arrays satisfy
d z ( p j , i , s , C ( v , σ ) ) − d z ( p j , i , s , C ( v , − σ ) ) = n ( z − 1 ) / 2 32 L 2 σ j i ( − 1 ) ℓ ( s ; v ) . d^z(p_{j,i,s},C(v,\sigma))-d^z(p_{j,i,s},C(v,-\sigma))=\frac{n^{(z-1)/2}}{32L^2}\sigma_{ji}(-1)^{\ell(s;v)}. d z ( p j , i , s , C ( v , σ )) − d z ( p j , i , s , C ( v , − σ )) = 32 L 2 n ( z − 1 ) /2 σ j i ( − 1 ) ℓ ( s ; v ) .
The coefficient is independent of the level and direction, and inactive contributions cancel. The same sign maximization and Eqs. (12) and (13) give a pair C + = C ( v , σ ) C^+=C(v,\sigma) C + = C ( v , σ ) and C − = C ( v , − σ ) C^-=C(v,-\sigma) C − = C ( v , − σ ) with
Δ ( C + ) − Δ ( C − ) ≥ n ( z − 1 ) / 2 ∣ P 1 ∣ 64 3 q L 2 . \Delta(C^+)-\Delta(C^-)\ge\frac{n^{(z-1)/2}|P_1|}{64\sqrt{3}\sqrt{q}L^2}. Δ ( C + ) − Δ ( C − ) ≥ 64 3 q L 2 n ( z − 1 ) /2 ∣ P 1 ∣ .
At least one query has absolute error at least half this gap. Together with Eq. (18) , this yields
max C ∈ { C + , C − } ∣ Δ ( C ) ∣ cost z ( X , C ) ≳ 1 n q L 2 . \max_{C\in\{C^+,C^-\}} \frac{|\Delta(C)|}{\operatorname{cost}_z(X,C)} \gtrsim\frac{1}{\sqrt{nq}\,L^2}. C ∈ { C + , C − } max cost z ( X , C ) ∣Δ ( C ) ∣ ≳ n q L 2 1 .
Thus the relative-error scale is the same as for k k k -means. For a sufficiently small constant c z > 0 c_z > 0 c z > 0 depending only on z z z , this error is at least 2 ε 2\varepsilon 2 ε whenever
ε n q L 2 ≤ c z . (19) \varepsilon\sqrt{nq}\,L^2 \le c_z. \tag*{(19)} ε n q L 2 ≤ c z . (19)
Subject to the coding condition and center budget, this forces every ε \varepsilon ε -coreset to contain more than ∣ X ∣ / 2 |X|/2 ∣ X ∣/2 points.
Small errors: 0 < ε < k − 1 / ( z + 2 ) 0 < \varepsilon< k^{-1/(z+2)} 0 < ε < k − 1/ ( z + 2 ) . As in the k k k -means case, the center budget and error condition suggest
n ( z + 2 ) / 2 ≲ k , m L ≲ k , q ≲ ε − 2 n L 4 . n^{(z+2)/2} \lesssim k,\qquad mL \lesssim k,\qquad q \lesssim\frac{\varepsilon^{-2}}{nL^4}. n ( z + 2 ) /2 ≲ k , m L ≲ k , q ≲ n L 4 ε − 2 .
Choose
L = ⌈ 8 log 2 ( 2 + k − 1 / ( z + 2 ) ε − 1 ) ⌉ , q = max { 1 , ⌈ k − 2 / ( z + 2 ) ε − 2 L 4 ⌉ } , L=\left\lceil8\log_2\left(2+k^{-1/(z+2)}\varepsilon^{-1}\right)\right\rceil,\qquad q=\max\left\{1,\left\lceil\frac{k^{-2/(z+2)}\varepsilon^{-2}}{L^4}\right\rceil\right\}, L = ⌈ 8 log 2 ( 2 + k − 1/ ( z + 2 ) ε − 1 ) ⌉ , q = max { 1 , ⌈ L 4 k − 2/ ( z + 2 ) ε − 2 ⌉ } ,
and round n , m n,m n , m down from sufficiently small fixed multiples of k 2 / ( z + 2 ) , k / L k^{2/(z+2)}, k/L k 2/ ( z + 2 ) , k / L , respectively, allowing the multiplier for n n n to depend on z z z . The same coding and rounding estimates as in § 2.3 give
2 L > q + ( q 3 ) , q ≲ k − 2 / ( z + 2 ) ε − 2 L 4 . 2^L > q+\binom{q}{3},\qquad q\lesssim\frac{k^{-2/(z+2)}\varepsilon^{-2}}{L^4}. 2 L > q + ( 3 q ) , q ≲ L 4 k − 2/ ( z + 2 ) ε − 2 .
Suppose first that both rounded counts are positive. Then n ≍ k 2 / ( z + 2 ) n\asymp k^{2/(z+2)} n ≍ k 2/ ( z + 2 ) and m ≍ k / L m\asymp k/L m ≍ k / L . Taking their leading constants sufficiently small ensures
n ( ⌈ n z / 2 ⌉ − 1 ) + m ( L + 1 ) ≤ n ( z + 2 ) / 2 + m ( L + 1 ) ≤ k . n\left(\left\lceil n^{z/2}\right\rceil-1\right)+m(L+1)\le n^{(z+2)/2}+m(L+1)\le k. n ( ⌈ n z /2 ⌉ − 1 ) + m ( L + 1 ) ≤ n ( z + 2 ) /2 + m ( L + 1 ) ≤ k .
Moreover,
ε n q L 2 ≲ n k 2 / ( z + 2 ) . \varepsilon\sqrt{nq}\,L^2\lesssim\sqrt{\frac{n}{k^{2/(z+2)}}}. ε n q L 2 ≲ k 2/ ( z + 2 ) n .
With L L L fixed as above, choosing the leading constant in n n n sufficiently small makes this quantity at most c z c_z c z . Hence every ε \varepsilon ε -coreset satisfies
∣ S ∣ > ∣ X ∣ 2 ≳ n ( z + 2 ) / 2 m q ≍ k ( 2 z + 2 ) / ( z + 2 ) ε − 2 L 5 |S|>\frac{|X|}{2}\gtrsim n^{(z+2)/2}mq\asymp\frac{k^{(2z+2)/(z+2)}\varepsilon^{-2}}{L^5} ∣ S ∣ > 2 ∣ X ∣ ≳ n ( z + 2 ) /2 m q ≍ L 5 k ( 2 z + 2 ) / ( z + 2 ) ε − 2
≳ k ( 2 z + 2 ) / ( z + 2 ) ε − 2 [ log ( 2 + k − 1 / ( z + 2 ) ε − 1 ) ] 5 . \gtrsim\frac{k^{(2z+2)/(z+2)}\varepsilon^{-2}}{\left[\log\left(2+k^{-1/(z+2)}\varepsilon^{-1}\right)\right]^5}. ≳ [ log ( 2 + k − 1/ ( z + 2 ) ε − 1 ) ] 5 k ( 2 z + 2 ) / ( z + 2 ) ε − 2 .
If either rounded count vanishes, then k = O ( 1 ) k=O(1) k = O ( 1 ) or k = O ( L ) k=O(L) k = O ( L ) , respectively, so k z / ( z + 2 ) / L 5 = O ( 1 ) k^{z/(z+2)}/L^5=O(1) k z / ( z + 2 ) / L 5 = O ( 1 ) and the target bound is O ( k ε − 2 ) O(k\varepsilon^{-2}) O ( k ε − 2 ) . For ε < 1 / 2 \varepsilon<1/2 ε < 1/2 , the known Ω ( k ε − 2 ) \Omega(k\varepsilon^{-2}) Ω ( k ε − 2 ) lower bound [9 Theorem 11] suffices; for ε ≥ 1 / 2 \varepsilon\ge1/2 ε ≥ 1/2 , the k k k -point argument in § 2.3 gives the required Ω ( k ) \Omega(k) Ω ( k ) bound. This completes the small-error case of Theorem 1.2 .
Larger errors: k − 1 / ( z + 2 ) ≤ ε < 1 k^{-1/(z+2)} \le\varepsilon< 1 k − 1/ ( z + 2 ) ≤ ε < 1 . The same construction also recovers the known larger-error branch [22 ] . A single offset per label suffices: for sufficiently small ε \varepsilon ε depending only on z z z , choose
L = q = 1 , n ≍ ε − 2 , m ≍ k . L=q=1,\qquad n\asymp\varepsilon^{-2},\qquad m\asymp k. L = q = 1 , n ≍ ε − 2 , m ≍ k .
rounding n , m n,m n , m down from sufficiently small fixed multiples. These counts are positive, and ε − z − 2 ≤ k \varepsilon^{-z-2}\le k ε − z − 2 ≤ k allows the leading constants to be chosen so that
n ( ⌈ n z / 2 ⌉ − 1 ) + 2 m ≤ n ( z + 2 ) / 2 + 2 m ≤ k , ε n ≤ c z . n\left(\left\lceil n^{z/2}\right\rceil-1\right)+2m\le n^{(z+2)/2}+2m\le k,\qquad\varepsilon\sqrt{n}\le c_z. n ( ⌈ n z /2 ⌉ − 1 ) + 2 m ≤ n ( z + 2 ) /2 + 2 m ≤ k , ε n ≤ c z .
The coding condition is immediate, so every coreset has size ∣ S ∣ > ∣ X ∣ / 2 ≍ n ( z + 2 ) / 2 m ≍ k ε − z − 2 |S|>|X|/2\asymp n^{(z+2)/2}m\asymp k\varepsilon^{-z-2} ∣ S ∣ > ∣ X ∣/2 ≍ n ( z + 2 ) /2 m ≍ k ε − z − 2 . When ε \varepsilon ε is bounded below by a positive constant depending only on z z z , this target is O ( k ) O(k) O ( k ) and the k k k -point argument again suffices. This proves the larger-error case and completes Theorem 1.2 ; the known upper bounds then give Corollary 1.3.
Lower bound in doubling metrics
We prove the lower-bound part of Theorem 1.4 through the following lemma: it constructs an unweighted dataset in a finite metric space of prescribed doubling dimension for which every ε \varepsilon ε -coreset must retain more than half of the input points.
The finite metric space consists of the dataset, all candidate centers, and auxiliary anchor and padding points.
Lemma 3.1 (Coreset lower bound in doubling metrics). For every fixed real z ≥ 2 z\ge2 z ≥ 2 , there exist constants C z > 0 C_z>0 C z > 0 and ε z ∈ ( 0 , 1 ) \varepsilon_z\in(0,1) ε z ∈ ( 0 , 1 ) such that for every integer k ≥ 1 k\ge1 k ≥ 1 , every ε ∈ ( 0 , ε z ] \varepsilon\in(0,\varepsilon_z] ε ∈ ( 0 , ε z ] , and every D ≥ C z log ( 2 / ε ) D\ge C_z\log(2/\varepsilon) D ≥ C z log ( 2/ ε ) , one can construct a finite metric space ( X , d ) (\mathcal{X},d) ( X , d ) satisfying
D / 8 ≤ ddim ( X , d ) ≤ D D/8\le\operatorname{ddim}(\mathcal{X},d)\le D D /8 ≤ ddim ( X , d ) ≤ D and an unweighted dataset X ⊆ X X\subseteq\mathcal{X} X ⊆ X of size
∣ X ∣ ≍ k D min { k 1 − 2 / z ε − 2 , ε − z } (20) |X|\asymp kD\min\left\{k^{1-2/z}\varepsilon^{-2},\varepsilon^{-z}\right\} \tag*{(20)} ∣ X ∣ ≍ k D min { k 1 − 2/ z ε − 2 , ε − z } (20) for which every ε \varepsilon ε -coreset for ( k , z ) (k,z) ( k , z ) -clustering of X X X in ( X , d ) (\mathcal{X},d) ( X , d ) has size greater than ∣ X ∣ / 2 |X|/2 ∣ X ∣/2 .
Proof of Lemma 3.1. Unlike in the Euclidean construction, we can prescribe the signed distances directly. A center will serve several groups of points at distances R − 1 R-1 R − 1 or R + 1 R+1 R + 1 , with an independently chosen sign for each group. The doubling dimension, rather than the distance scale R R R , controls the number of groups. Comparing queries with opposite sign choices then detects omissions despite arbitrary coreset weights.
Construction of the ambient metric
Let B , n , m , q ≥ 1 B,n,m,q\ge1 B , n , m , q ≥ 1 be integer parameters and let R ≥ 4 R\ge4 R ≥ 4 , to be chosen below. For each b ∈ [ B ] b\in[B] b ∈ [ B ] , create an anchor a b a_b a b and a copy
P b = { p b , j , i , s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ] } . P_b=\{p_{b,j,i,s}:j\in[n],\ i\in[m],\ s\in[q]\}. P b = { p b , j , i , s : j ∈ [ n ] , i ∈ [ m ] , s ∈ [ q ]} .
The unweighted dataset is
X = ⋃ b = 1 B P b , ∣ X ∣ = B n m q . X=\bigcup_{b=1}^{B}P_b,\qquad|X|=Bnmq. X = b = 1 ⋃ B P b , ∣ X ∣ = B nm q .
We index the candidate centers by a finite family H \mathcal{H} H of ± 1 \pm1 ± 1 vectors. This family has the same unbiased four-wise independence property as the Euclidean parity vectors { ( ( − 1 ) ℓ ( s ; v ) ) s ∈ [ q ] : v ∈ V } \{((-1)^{\ell(s;v)})_{s\in[q]}:v\in V\} {(( − 1 ) ℓ ( s ; v ) ) s ∈ [ q ] : v ∈ V } from Lemma 2.1 . Its discrepancy guarantee will play the same role in detecting omitted points, but no projection levels are needed.
Lemma 3.2 (A finite sign family). For every integer q ≥ 1 q \ge1 q ≥ 1 , there is a distribution on a finite set H ⊆ { − 1 , 1 } q \mathcal{H} \subseteq\{-1,1\}^{q} H ⊆ { − 1 , 1 } q such that a random vector χ ∈ H \chi\in\mathcal{H} χ ∈ H has unbiased, four-wise independent coordinates and
2 ≤ ∣ H ∣ ≤ 4 ( q + 2 ) 6 , E χ ∣ ⟨ A , χ ⟩ ∣ ≥ 1 3 ∥ A ∥ 2 ( A ∈ R q ) . 2 \le|\mathcal{H}| \le4(q+2)^6,\qquad\mathbb{E}_{\chi}|\langle A,\chi\rangle| \ge\frac{1}{\sqrt{3}}\|A\|_2\quad(A\in\mathbb{R}^{q}). 2 ≤ ∣ H ∣ ≤ 4 ( q + 2 ) 6 , E χ ∣ ⟨ A , χ ⟩ ∣ ≥ 3 1 ∥ A ∥ 2 ( A ∈ R q ) . The family and its distribution depend only on q q q .
The proof is given in § 3.5 .
Candidate centers and their distances. For every copy b ∈ [ B ] b \in[B] b ∈ [ B ] , label i ∈ [ m ] i \in[m] i ∈ [ m ] , sign vector σ b i = ( σ b i ( j ) ) j ∈ [ n ] ∈ { − 1 , 1 } n \sigma_{bi}=(\sigma_{bi}^{(j)})_{j\in[n]}\in\{-1,1\}^{n} σ bi = ( σ bi ( j ) ) j ∈ [ n ] ∈ { − 1 , 1 } n , and χ ∈ H \chi\in\mathcal{H} χ ∈ H , add a distinct candidate center c b , i , σ b i , χ c_{b,i,\sigma_{bi},\chi} c b , i , σ bi , χ . Each copy contains m 2 n ∣ H ∣ m2^n|\mathcal{H}| m 2 n ∣ H ∣ candidate centers.
We also include k k k isolated padding points a B + 1 , … , a B + k a_{B+1},\ldots,a_{B+k} a B + 1 , … , a B + k so that every query can be padded to k k k centers.
The full point set is
X = X ∪ { a b : b ∈ [ B + k ] } ∪ { c b , i , σ b i , χ : b ∈ [ B ] , i ∈ [ m ] , σ b i ∈ { − 1 , 1 } n , χ ∈ H } . \mathcal{X}=\mathcal{X}\cup\{a_b:b\in[B+k]\}
\cup\{c_{b,i,\sigma_{bi},\chi}:b\in[B],\ i\in[m],\ \sigma_{bi}\in\{-1,1\}^{n},\ \chi\in\mathcal{H}\}. X = X ∪ { a b : b ∈ [ B + k ]} ∪ { c b , i , σ bi , χ : b ∈ [ B ] , i ∈ [ m ] , σ bi ∈ { − 1 , 1 } n , χ ∈ H } .
A component consists of one copy P b P_b P b , its anchor a b a_b a b , and all its candidate centers; each padding point a B + 1 , … , a B + k a_{B+1},\ldots,a_{B+k} a B + 1 , … , a B + k forms a separate singleton component.
The distances are specified by the following cases.
Input–input distances. For distinct p , p ′ ∈ P b p,p'\in P_b p , p ′ ∈ P b , set d ( p , p ′ ) = 2 d(p,p')=2 d ( p , p ′ ) = 2 .
Anchor–center distances. For every candidate center c c c in copy b b b , set d ( a b , c ) = R d(a_b,c)=R d ( a b , c ) = R .
Center–center distances. For distinct candidate centers c , c ′ c,c' c , c ′ in the same copy, set d ( c , c ′ ) = 2 d(c,c')=2 d ( c , c ′ ) = 2 .
d ( p b , j , i , s , c b , i ′ , σ b i ′ , χ ) = { R − σ b i ( j ) χ s , i ′ = i , R + 1 , i ′ ≠ i . d(p_{b,j,i,s},c_{b,i',\sigma_{bi'},\chi})=
\begin{cases}
R-\sigma_{bi}^{(j)}\chi_s, & i'=i,\\
R+1, & i'\ne i.
\end{cases} d ( p b , j , i , s , c b , i ′ , σ b i ′ , χ ) = { R − σ bi ( j ) χ s , R + 1 , i ′ = i , i ′ = i .
d ( x , y ) = 10 R ∣ t − t ′ ∣ if their components have positions t and t ′ . (21) d(x,y)=10R\lvert t-t^{\prime}\rvert\quad\text{if their components have positions }t\text{ and }t^{\prime}. \tag*{(21)} d ( x , y ) = 10 R ∣ t − t ′ ∣ if their components have positions t and t ′ . (21)
Diagonal and symmetry. Finally, set d ( x , x ) = 0 d(x,x)=0 d ( x , x ) = 0 and impose symmetry.
These cases specify every distance, including those involving padding points. The line arrangement keeps the dimension independent of the number of components; equal cross-distances would not.
Thus all n m q nmq nm q input points in P b P_b P b lie in the unit ball centered at a b a_b a b . For each label i i i , the index j j j specifies one of n n n groups, each containing q q q points indexed by s s s . A single selected center of label i i i will serve all n n n groups, with an independent sign choice for each group.
The metric and its doubling dimension
We prove that the points and distances specified above form a finite metric space ( X , d ) (\mathcal{X}, d) ( X , d ) , and then bound its doubling dimension.
We will choose the parameters to satisfy
n m q + 1 ≤ 2 2 n , m ∣ H ∣ ≤ 2 n . (22) nmq + 1 \le2^{2n}, \qquad m|\mathcal{H}| \le2^n. \tag*{(22)} nm q + 1 ≤ 2 2 n , m ∣ H ∣ ≤ 2 n . (22)
The first condition bounds the inputs and anchor in each copy; the second bounds its m 2 n ∣ H ∣ m2^n|\mathcal{H}| m 2 n ∣ H ∣ candidate centers. The next lemma converts these counts into a bound on the full metric’s doubling dimension.
Lemma 3.3. The prescribed distances define a metric. Under (22) , its doubling dimension satisfies
n + 1 ≤ ddim ( X , d ) ≤ 2 n + 1 , n + 1 \le\operatorname{ddim}(\mathcal{X}, d) \le2n + 1, n + 1 ≤ ddim ( X , d ) ≤ 2 n + 1 , independently of the number of copies and padding points.
Proof. Within a single copy, the inputs and anchor have pairwise distances in { 1 , 2 } \{1,2\} { 1 , 2 } , and the candidate centers have pairwise distance 2 2 2 . For triangles involving both inputs/anchor and candidate centers: a triangle with an input, the anchor, and a candidate center has side lengths ( 1 , R , R ± 1 ) (1,R,R \pm1) ( 1 , R , R ± 1 ) ; a triangle with the anchor and two candidate centers has side lengths ( R , R , 2 ) (R,R,2) ( R , R , 2 ) ; and a triangle with either two inputs and one center or one input and two centers has one side of length 2 2 2 and two sides in [ R − 1 , R + 1 ] [R-1,R+1] [ R − 1 , R + 1 ] . Since R ≥ 4 R \ge4 R ≥ 4 , all intra-copy triangle inequalities hold.
Across components, each component has diameter at most R + 1 < 5 R R+1 < 5R R + 1 < 5 R . A triangle spanning three distinct components reduces to the line metric in (21) , while a triangle with two points in the same component and one in another has two equal sides of length at least 10 R 10R 10 R and a third side of length at most R + 1 R+1 R + 1 . Thus ( X , d ) (\mathcal{X},d) ( X , d ) is a metric space.
By (22) , each component has size at most 2 2 n + 1 2^{2n+1} 2 2 n + 1 . Any ball of radius r < T : = 10 R r < T := 10R r < T := 10 R is contained in a single component and can therefore be covered by at most 2 2 n + 1 2^{2n+1} 2 2 n + 1 balls of radius r / 2 r/2 r /2 (one per point). For r ≥ T r \ge T r ≥ T , a ball of radius r r r is the union of all components whose line indices t t t lie in an interval of length at most 2 ⌊ r / T ⌋ + 1 2\lfloor r/T\rfloor+ 1 2 ⌊ r / T ⌋ + 1 . Partitioning this index interval into at most three sub-intervals of length at most 2 ⌊ r / ( 2 T ) ⌋ + 1 2\lfloor r/(2T)\rfloor+ 1 2 ⌊ r / ( 2 T )⌋ + 1 and placing a ball of radius r / 2 r/2 r /2 at the anchor of each sub-interval’s middle component covers every component in the sub-interval: points in the middle component lie within its diameter R + 1 < T / 2 ≤ r / 2 R+1 < T/2 \le r/2 R + 1 < T /2 ≤ r /2 , and points in the other components of the sub-interval lie at distance at most ⌊ r / ( 2 T ) ⌋ T ≤ r / 2 \lfloor r/(2T)\rfloor T \le r/2 ⌊ r / ( 2 T )⌋ T ≤ r /2 . Since 3 ≤ 2 2 n + 1 3 \le2^{2n+1} 3 ≤ 2 2 n + 1 for n ≥ 1 n \ge1 n ≥ 1 , this establishes ddim ( X , d ) ≤ 2 n + 1 \operatorname{ddim}(\mathcal{X},d) \le2n+1 ddim ( X , d ) ≤ 2 n + 1 .
For the lower bound, a radius-two ball centered at any candidate center contains all m 2 n ∣ H ∣ m2^n|\mathcal{H}| m 2 n ∣ H ∣ candidate centers in its copy. No radius-one ball covers two of them: their pairwise distance is two, every input and anchor is at distance at least R − 1 > 1 R-1>1 R − 1 > 1 from them, and all other components are farther away. Thus the doubling constant is at least m 2 n ∣ H ∣ ≥ 2 n + 1 m2^n|\mathcal{H}| \ge2^{n+1} m 2 n ∣ H ∣ ≥ 2 n + 1 , using m ≥ 1 m \ge1 m ≥ 1 and ∣ H ∣ ≥ 2 |\mathcal{H}| \ge2 ∣ H ∣ ≥ 2 . ∎
Query center sets and costs
Fix an integer g g g with 1 ≤ g ≤ B 1 \le g \le B 1 ≤ g ≤ B and a weighted subset ( S , w ) (S,w) ( S , w ) with ∣ S ∣ ≤ ∣ X ∣ / 2 |S| \le|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 . We choose the g g g copies containing the most points omitted by S S S as active, breaking ties arbitrarily. Without loss of generality, denote them by P 1 , … , P g P_1,\ldots,P_g P 1 , … , P g . The line positions remain fixed when the active copies are relabeled. We select m m m candidate centers in each active copy, one per label, and the anchor of each inactive copy.
For χ ∈ H \chi\in\mathcal{H} χ ∈ H , choose one vector σ b i \sigma_{bi} σ bi for each active copy b ∈ [ g ] b \in[g] b ∈ [ g ] and label i ∈ [ m ] i \in[m] i ∈ [ m ] , and write
σ = ( σ b i ) b ∈ [ g ] , i ∈ [ m ] ∈ ( { − 1 , 1 } n ) g × m , σ b i = ( σ b i ( j ) ) j ∈ [ n ] . \sigma= (\sigma_{bi})_{b\in[g],\,i\in[m]} \in\left(\{-1,1\}^n\right)^{g\times m}, \qquad\sigma_{bi} = \left(\sigma_{bi}^{(j)}\right)_{j\in[n]}. σ = ( σ bi ) b ∈ [ g ] , i ∈ [ m ] ∈ ( { − 1 , 1 } n ) g × m , σ bi = ( σ bi ( j ) ) j ∈ [ n ] .
Thus σ \sigma σ consists of g m gm g m n n n -dimensional vectors, one for each selected active center; j j j indexes the coordinates of each vector. Together with the inactive anchors, this uses g m + ( B − g ) = B + g ( m − 1 ) gm+(B-g)=B+g(m-1) g m + ( B − g ) = B + g ( m − 1 ) centers. To stay within the center budget, we will choose the parameters so that
B + g ( m − 1 ) ≤ k . (23) B+g(m-1)\le k. \tag*{(23)} B + g ( m − 1 ) ≤ k . (23)
Adding fixed padding centers gives the following set of k k k centers:
C ( σ , χ ) = { c b , i , σ b i , χ : b ∈ [ g ] , i ∈ [ m ] } ∪ { a b : g < b ≤ B } ∪ { a B + t : 1 ≤ t ≤ k − B − g ( m − 1 ) } . \begin{aligned}
C(\sigma,\chi)={}&\{c_{b,i,\sigma_{bi},\chi}:b\in[g],\ i\in[m]\}\\
&\cup\{a_b:g<b\le B\}\\
&\cup\{a_{B+t}:1\le t\le k-B-g(m-1)\}.
\end{aligned} C ( σ , χ ) = { c b , i , σ bi , χ : b ∈ [ g ] , i ∈ [ m ]} ∪ { a b : g < b ≤ B } ∪ { a B + t : 1 ≤ t ≤ k − B − g ( m − 1 )} .
With these active copies fixed, define
C = { C ( σ , χ ) : σ ∈ { − 1 , 1 } g m , χ ∈ H } . \mathcal{C}=\left\{C(\sigma,\chi):\sigma\in\{-1,1\}^{gm},\ \chi\in\mathcal{H}\right\}. C = { C ( σ , χ ) : σ ∈ { − 1 , 1 } g m , χ ∈ H } .
In our error analysis, we pair each C ( σ , χ ) ∈ C C(\sigma,\chi)\in\mathcal{C} C ( σ , χ ) ∈ C with C ( − σ , χ ) C(-\sigma,\chi) C ( − σ , χ ) , where − σ -\sigma − σ negates all g m gm g m sign vectors while keeping χ \chi χ , the active copies, and the padding centers fixed.
Claim 3.4 (Pointwise and total costs). For every C ( σ , χ ) ∈ C C(\sigma,\chi)\in\mathcal{C} C ( σ , χ ) ∈ C , the following properties hold.
d z ( p b , j , i , s , C ( σ , χ ) ) = ( R − σ b i ( j ) χ s ) z . (24) d^z(p_{b,j,i,s},C(\sigma,\chi))=(R-\sigma_{bi}^{(j)}\chi_s)^z. \tag*{(24)} d z ( p b , j , i , s , C ( σ , χ )) = ( R − σ bi ( j ) χ s ) z . (24) Every point in an inactive copy has cost one.
cost z ( X , C ( σ , χ ) ) ≲ g R z n m q (25) \operatorname{cost}_z(X,C(\sigma,\chi))\lesssim gR^z nmq \tag*{(25)} cost z ( X , C ( σ , χ )) ≲ g R z nm q (25) provided B ≤ 2 g R z B\le2gR^z B ≤ 2 g R z .
Proof. In an active copy, the anchor is not selected. The point p b , j , i , s p_{b,j,i,s} p b , j , i , s has distance R − σ b i ( j ) χ s R-\sigma_{bi}^{(j)}\chi_s R − σ bi ( j ) χ s to its designated center and distance R + 1 R+1 R + 1 to each selected center of another label. All selected centers outside this copy have distance at least 10 R > R + 1 10R>R+1 10 R > R + 1 . Thus the designated center is always a nearest center, with possible ties when its distance is R + 1 R+1 R + 1 , proving (24) . An inactive point is served by its own anchor at distance one.
Summing these pointwise costs gives
cost z ( X , C ( σ , χ ) ) ≤ [ g ( R + 1 ) z + B − g ] n m q . \operatorname{cost}_z(X,C(\sigma,\chi))\le[g(R+1)^z+B-g]nmq. cost z ( X , C ( σ , χ )) ≤ [ g ( R + 1 ) z + B − g ] nm q .
To obtain (25) , it is sufficient to keep the inactive contribution within a constant factor of the active contribution. We therefore impose
B ≤ 2 g R z , (26) B\le2gR^z, \tag*{(26)} B ≤ 2 g R z , (26)
which will be enforced in the parameter choice. Since R ≥ 4 R\ge4 R ≥ 4 , the preceding cost estimate is then O ( g R z n m q ) O(gR^z nmq) O ( g R z nm q ) .
Coreset error and parameter choice
Proposition 3.5 (Two center sets detecting omissions). Under (23) , (26) , and (22) , for every weighted subset ( S , w ) (S,w) ( S , w ) with ∣ S ∣ ≤ ∣ X ∣ / 2 |S|\leq|X|/2 ∣ S ∣ ≤ ∣ X ∣/2 , the family C \mathcal{C} C constructed above for S S S contains two center sets C + , C − C^+,C^- C + , C − , each of size exactly k k k , satisfying
max C ∈ { C + , C − } ∣ cost z ( S , C ) − cost z ( X , C ) ∣ cost z ( X , C ) ≳ 1 R q . (27) \max_{C\in\{C^+,C^-\}}\frac{\left|\operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C)\right|}{\operatorname{cost}_z(X,C)}\gtrsim\frac{1}{R\sqrt{q}}. \tag*{(27)} C ∈ { C + , C − } max cost z ( X , C ) ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≳ R q 1 . (27)
Proof. Fix ( S , w ) (S,w) ( S , w ) and let P 1 , … , P g P_1,\ldots,P_g P 1 , … , P g be the active copies selected above. Throughout this proof, sums over b , j , i b,j,i b , j , i range over [ g ] × [ n ] × [ m ] [g]\times[n]\times[m] [ g ] × [ n ] × [ m ] , and sums over s s s range over [ q ] [q] [ q ] . Extend w w w by zero to omitted points, and set
A b j i = ( w ( p b , j , i , s ) − 1 ) s ∈ [ q ] . A_{bji}=(w(p_{b,j,i,s})-1)_{s\in[q]}. A bj i = ( w ( p b , j , i , s ) − 1 ) s ∈ [ q ] .
Write the signed error as
Δ ( C ) = cost z ( S , C ) − cost z ( X , C ) = ∑ p ∈ X ( w ( p ) − 1 ) d z ( p , C ) . \Delta(C)=\operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C)=\sum_{p\in X}(w(p)-1)d^z(p,C). Δ ( C ) = cost z ( S , C ) − cost z ( X , C ) = p ∈ X ∑ ( w ( p ) − 1 ) d z ( p , C ) .
For arbitrary χ ∈ H \chi\in\mathcal{H} χ ∈ H and σ ∈ { − 1 , 1 } g × m \sigma\in\{-1,1\}^{g\times m} σ ∈ { − 1 , 1 } g × m , let C + = C ( σ , χ ) C^+=C(\sigma,\chi) C + = C ( σ , χ ) and C − = C ( − σ , χ ) C^-=C(-\sigma,\chi) C − = C ( − σ , χ ) . For an active point, (24) gives
d z ( p b , j , i , s , C − ) − d z ( p b , j , i , s , C + ) = σ b i ( j ) χ s [ ( R + 1 ) z − ( R − 1 ) z ] ≳ R z − 1 σ b i ( j ) χ s . d^z(p_{b,j,i,s},C^-)-d^z(p_{b,j,i,s},C^+)=\sigma_{bi}^{(j)}\chi_s\left[(R+1)^z-(R-1)^z\right]\gtrsim R^{z-1}\sigma_{bi}^{(j)}\chi_s. d z ( p b , j , i , s , C − ) − d z ( p b , j , i , s , C + ) = σ bi ( j ) χ s [ ( R + 1 ) z − ( R − 1 ) z ] ≳ R z − 1 σ bi ( j ) χ s .
Every inactive point has the same cost in both center sets. Subtracting the errors therefore cancels all inactive contributions and yields
Δ ( C − ) − Δ ( C + ) = ∑ p ∈ X ( w ( p ) − 1 ) [ d z ( p , C − ) − d z ( p , C + ) ] ≳ R z − 1 ∑ b , j , i σ b i ( j ) ⟨ A b j i , χ ⟩ . \begin{aligned}
\Delta(C^-)-\Delta(C^+)
&=\sum_{p\in X}(w(p)-1)\left[d^z(p,C^-)-d^z(p,C^+)\right]\\
&\gtrsim R^{z-1}\sum_{b,j,i}\sigma_{bi}^{(j)}\langle A_{bji},\chi\rangle.
\end{aligned} Δ ( C − ) − Δ ( C + ) = p ∈ X ∑ ( w ( p ) − 1 ) [ d z ( p , C − ) − d z ( p , C + ) ] ≳ R z − 1 b , j , i ∑ σ bi ( j ) ⟨ A bj i , χ ⟩ .
For fixed χ \chi χ , choose σ b i ( j ) = sgn ( ⟨ A b j i , χ ⟩ ) \sigma_{bi}^{(j)}=\operatorname{sgn}(\langle A_{bji},\chi\rangle) σ bi ( j ) = sgn (⟨ A bj i , χ ⟩) , with either choice when this is zero. The last sum then equals ∑ b , j , i ∣ ⟨ A b j i , χ ⟩ ∣ \sum_{b,j,i}|\langle A_{bji},\chi\rangle| ∑ b , j , i ∣ ⟨ A bj i , χ ⟩ ∣ . Applying Lemma 3.2 and linearity of expectation now gives
max χ ∈ H ∑ b , j , i ∣ ⟨ A b j i , χ ⟩ ∣ ≥ E χ ∑ b , j , i ∣ ⟨ A b j i , χ ⟩ ∣ ≳ ∑ b , j , i ∥ A b j i ∥ 2 . (28) \max_{\chi\in\mathcal{H}}\sum_{b,j,i}|\langle A_{bji},\chi\rangle|
\geq\mathbb{E}_{\chi}\sum_{b,j,i}|\langle A_{bji},\chi\rangle|
\gtrsim\sum_{b,j,i}\|A_{bji}\|_2. \tag*{(28)} χ ∈ H max b , j , i ∑ ∣ ⟨ A bj i , χ ⟩ ∣ ≥ E χ b , j , i ∑ ∣ ⟨ A bj i , χ ⟩ ∣ ≳ b , j , i ∑ ∥ A bj i ∥ 2 . (28)
The same χ \chi χ is used in every term of the sum.
Let M b j i = ∣ { s ∈ [ q ] : p b , j , i , s ∉ S } ∣ M_{bji}=|\{s\in[q]:p_{b,j,i,s}\notin S\}| M bj i = ∣ { s ∈ [ q ] : p b , j , i , s ∈ / S } ∣ . Each omitted point has coefficient − 1 -1 − 1 , so ∥ A b j i ∥ 2 ≥ M b j i \|A_{bji}\|_2\geq\sqrt{M_{bji}} ∥ A bj i ∥ 2 ≥ M bj i . The active copies contain the most omissions, hence their average number of omissions is at least the average over all B B B copies. Since ∣ X ∖ S ∣ ≥ B n m q / 2 |X\setminus S|\geq Bnmq/2 ∣ X ∖ S ∣ ≥ B nm q /2 , we have ∑ b , j , i M b j i ≳ g n m q \sum_{b,j,i}M_{bji}\gtrsim gnmq ∑ b , j , i M bj i ≳ g nm q . Together with 0 ≤ M b j i ≤ q 0\leq M_{bji}\leq q 0 ≤ M bj i ≤ q , this gives
∑ b , j , i ∥ A b j i ∥ 2 ≥ ∑ b , j , i M b j i ≥ ∑ b , j , i M b j i q ≳ g n m q . (29) \sum_{b,j,i}\|A_{bji}\|_2\geq\sum_{b,j,i}\sqrt{M_{bji}}\geq\frac{\sum_{b,j,i}M_{bji}}{\sqrt{q}}\gtrsim gnm\sqrt{q}. \tag*{(29)} b , j , i ∑ ∥ A bj i ∥ 2 ≥ b , j , i ∑ M bj i ≥ q ∑ b , j , i M bj i ≳ g nm q . (29)
Choose χ \chi χ attaining the maximum in (28) and align σ \sigma σ as above. Combining (28) and (29) with ( R + 1 ) z − ( R − 1 ) z ≳ R z − 1 (R+1)^z-(R-1)^z\gtrsim R^{z-1} ( R + 1 ) z − ( R − 1 ) z ≳ R z − 1 gives
Δ ( C − ) − Δ ( C + ) ≳ g R z − 1 n m q . \Delta(C^-)-\Delta(C^+)\gtrsim gR^{z-1}nm\sqrt{q}. Δ ( C − ) − Δ ( C + ) ≳ g R z − 1 nm q .
By the triangle inequality and (25) ,
max C ∈ { C + , C − } ∣ Δ ( C ) ∣ cost z ( X , C ) ≥ Δ ( C − ) − Δ ( C + ) cost z ( X , C − ) + cost z ( X , C + ) ≥ g R z − 1 n m q g R z n m q = 1 R q . \max_{C\in\{C^+,C^-\}}\frac{|\Delta(C)|}{\operatorname{cost}_z(X,C)} \ge\frac{\Delta(C^-)-\Delta(C^+)}{\operatorname{cost}_z(X,C^-)+\operatorname{cost}_z(X,C^+)}
\ge\frac{gR^{z-1}nm\sqrt{q}}{gR^z nmq}=\frac{1}{R\sqrt{q}}. C ∈ { C + , C − } max cost z ( X , C ) ∣Δ ( C ) ∣ ≥ cost z ( X , C − ) + cost z ( X , C + ) Δ ( C − ) − Δ ( C + ) ≥ g R z nm q g R z − 1 nm q = R q 1 .
This proves (27) .
Choosing the parameters. Set n = ⌊ D / 8 ⌋ n=\lfloor D/8\rfloor n = ⌊ D /8 ⌋ . Fix a sufficiently small constant 0 < γ z ≤ 1 0<\gamma_z\le1 0 < γ z ≤ 1 so that Proposition 3.5 gives relative error greater than ε \varepsilon ε whenever
ε R q ≤ γ z . \varepsilon R\sqrt{q}\le\sqrt{\gamma_z}. εR q ≤ γ z .
Ignoring integer rounding for the moment, take B ≍ z k B\asymp_z k B ≍ z k and g m ≍ k gm\asymp k g m ≍ k . For fixed R R R , the error condition allows q ≍ z ε − 2 R − 2 q\asymp_z\varepsilon^{-2}R^{-2} q ≍ z ε − 2 R − 2 , while the cost-balance condition requires g ≳ z k / R z g\gtrsim_z k/R^z g ≳ z k / R z . Taking g g g at this scale leaves the largest possible order of m m m within the center budget, giving
g ≍ z k / R z , m ≍ z R z , ∣ X ∣ ≍ z k D ε − 2 R z − 2 . g\asymp_z k/R^z,\qquad m\asymp_z R^z,\qquad|X|\asymp_z kD\varepsilon^{-2}R^{z-2}. g ≍ z k / R z , m ≍ z R z , ∣ X ∣ ≍ z k D ε − 2 R z − 2 .
The requirements g ≥ 1 g\ge1 g ≥ 1 and q ≥ 1 q\ge1 q ≥ 1 limit R z R^z R z to order min { k , ε − z } \min\{k,\varepsilon^{-z}\} min { k , ε − z } . Since z ≥ 2 z\ge2 z ≥ 2 , the dataset size is nondecreasing in R R R . We therefore take
k 0 : = min { k , ⌊ ε − z ⌋ } , R z ≍ z k 0 . k_0:=\min\{k,\lfloor\varepsilon^{-z}\rfloor\},\qquad R^z\asymp_z k_0. k 0 := min { k , ⌊ ε − z ⌋} , R z ≍ z k 0 .
These scales yield the desired size:
∣ X ∣ ≍ z k D ε − 2 k 0 1 − 2 / z ≍ z k D min { k 1 − 2 / z ε − 2 , ε − z } . |X|\asymp_z kD\varepsilon^{-2}k_0^{1-2/z}\asymp_z kD\min\{k^{1-2/z}\varepsilon^{-2},\varepsilon^{-z}\}. ∣ X ∣ ≍ z k D ε − 2 k 0 1 − 2/ z ≍ z k D min { k 1 − 2/ z ε − 2 , ε − z } .
To see why we allow g g g active copies rather than fixing g = 1 g=1 g = 1 , consider the parameter scales established above. The discrepancy argument gives
error gap = Ω ( g n m 2 − 1 / z q ) , cost z ( X , C ) = Θ ( ( g m + B ) n m q ) . \operatorname{error\ gap}=\Omega(gnm^{2-1/z}\sqrt{q}),\qquad\operatorname{cost}_z(X,C)=\Theta((gm+B)nmq). error gap = Ω ( g n m 2 − 1/ z q ) , cost z ( X , C ) = Θ (( g m + B ) nm q ) .
For g = 1 g=1 g = 1 , B ≍ k B\asymp k B ≍ k , and m ≤ k m\le k m ≤ k , the relative-error lower bound certified by this argument has scale
m 1 − 1 / z ( m + B ) q ≲ k − 1 / z q . \frac{m^{1-1/z}}{(m+B)\sqrt{q}}\lesssim\frac{k^{-1/z}}{\sqrt{q}}. ( m + B ) q m 1 − 1/ z ≲ q k − 1/ z .
Making this guarantee exceed ε \varepsilon ε would require q ≲ ε − 2 k − 2 / z q\lesssim\varepsilon^{-2}k^{-2/z} q ≲ ε − 2 k − 2/ z , which is incompatible with q ≥ 1 q\ge1 q ≥ 1 when k / ε − z k/\varepsilon^{-z} k / ε − z is unbounded. Thus this discrepancy argument with a single active copy does not yield the required dataset size throughout the parameter range. Allowing g ≍ k / m g\asymp k/m g ≍ k / m lets us keep m ≲ ε − z m\lesssim\varepsilon^{-z} m ≲ ε − z while using Θ ( k ) \Theta(k) Θ ( k ) active centers; these parameter scales give the claimed lower bound.
Integral choices and dimension. Choose ρ z > 0 \rho_z>0 ρ z > 0 with
ρ z ≤ min { 1 / 4 , γ z / 2 } , ρ z z ≤ 1 / 8 , \rho_z\le\min\{1/4,\sqrt{\gamma_z}/2\},\qquad\rho_z^z\le1/8, ρ z ≤ min { 1/4 , γ z /2 } , ρ z z ≤ 1/8 ,
and choose ε z ≤ 1 / 2 \varepsilon_z\le1/2 ε z ≤ 1/2 small enough that γ z ε z − 2 / 16 ≥ 4 \gamma_z\varepsilon_z^{-2}/16\ge4 γ z ε z − 2 /16 ≥ 4 . For k 0 k_0 k 0 above a sufficiently large constant depending only on z z z , set
g = ⌊ k / k 0 ⌋ , R = ρ z k 0 1 / z , B = g ⌈ R z ⌉ , g=\lfloor k/k_0\rfloor,\qquad R=\rho_z k_0^{1/z},\qquad B=g\lceil R^z\rceil, g = ⌊ k / k 0 ⌋ , R = ρ z k 0 1/ z , B = g ⌈ R z ⌉ ,
m = ⌊ k 0 / 2 ⌋ , q = ⌊ γ z ε − 2 R − 2 ⌋ . m=\lfloor k_0/2\rfloor,\qquad q=\lfloor\gamma_z\varepsilon^{-2}R^{-2}\rfloor. m = ⌊ k 0 /2 ⌋ , q = ⌊ γ z ε − 2 R − 2 ⌋ .
The threshold ensures R ≥ 4 R \ge4 R ≥ 4 and m ≥ 1 m \ge1 m ≥ 1 . Since k 0 ≤ ε − z k_0 \le\varepsilon^{-z} k 0 ≤ ε − z , the unrounded value defining q q q is at least γ z / ρ z 2 ≥ 4 \gamma_z/\rho_z^2 \ge4 γ z / ρ z 2 ≥ 4 . Thus q ≥ 1 q \ge1 q ≥ 1 , q ≳ z ε − 2 R − 2 q \gtrsim_z \varepsilon^{-2}R^{-2} q ≳ z ε − 2 R − 2 , and ε R q ≤ γ z \varepsilon R\sqrt{q} \le\sqrt{\gamma_z} εR q ≤ γ z . Also 1 ≤ g ≤ B ≤ 2 g R z 1 \le g \le B \le2gR^z 1 ≤ g ≤ B ≤ 2 g R z , and
B + g ( m − 1 ) = g ( ⌈ R z ⌉ + m − 1 ) ≤ g ( R z + k 0 / 2 ) ≤ g k 0 ≤ k . B + g(m-1) = g(\lceil R^z\rceil+ m - 1) \le g(R^z + k_0/2) \le gk_0 \le k. B + g ( m − 1 ) = g (⌈ R z ⌉ + m − 1 ) ≤ g ( R z + k 0 /2 ) ≤ g k 0 ≤ k .
Hence the center budget and cost balance hold. Since g k 0 ≍ k gk_0 \asymp k g k 0 ≍ k , these integral choices preserve the parameter scales above.
Taking C z C_z C z sufficiently large in the dimension assumption ensures
n ≥ 16 ( z + 20 ) log 2 ( 2 / ε ) . (30) n \ge16(z+20)\log_2(2/\varepsilon). \tag*{(30)} n ≥ 16 ( z + 20 ) log 2 ( 2/ ε ) . (30)
Using m ≤ ε − z m \le\varepsilon^{-z} m ≤ ε − z , q ≤ ε − 2 q \le\varepsilon^{-2} q ≤ ε − 2 , and Lemma 3.2 , we obtain
log 2 ( m ∣ H ∣ ) ≤ ( z + 14 ) log 2 ( 2 / ε ) ≤ n , \log_2(m|\mathcal{H}|) \le(z+14)\log_2(2/\varepsilon) \le n, log 2 ( m ∣ H ∣ ) ≤ ( z + 14 ) log 2 ( 2/ ε ) ≤ n ,
log 2 ( n m q + 1 ) ≤ log 2 n + ( z + 4 ) log 2 ( 2 / ε ) ≤ 2 n . \log_2(nmq+1) \le\log_2 n + (z+4)\log_2(2/\varepsilon) \le2n. log 2 ( nm q + 1 ) ≤ log 2 n + ( z + 4 ) log 2 ( 2/ ε ) ≤ 2 n .
Here the last inequality uses log 2 n ≤ n \log_2 n \le n log 2 n ≤ n and (30) . These estimates verify (22) , so Lemma 3.3 gives
D / 8 < n + 1 ≤ ddim ( X , d ) ≤ 2 n + 1 ≤ D . D/8 < n+1 \le\operatorname{ddim}(\mathcal{X},d) \le2n+1 \le D. D /8 < n + 1 ≤ ddim ( X , d ) ≤ 2 n + 1 ≤ D .
The capacity estimates depend on ε \varepsilon ε and z z z , but not on the number of copies, so no log k \log k log k term is needed in the dimension assumption. Together with Proposition 3.5 and the size calculation above, this proves the claim for sufficiently large k 0 k_0 k 0 .
For bounded k 0 k_0 k 0 , keep n = ⌊ D / 8 ⌋ n=\lfloor D/8\rfloor n = ⌊ D /8 ⌋ and use
B = g = k , m = 1 , R = 4 , q = ⌊ γ z ε − 2 / 16 ⌋ . B=g=k,\qquad m=1,\qquad R=4,\qquad q=\lfloor\gamma_z\varepsilon^{-2}/16\rfloor. B = g = k , m = 1 , R = 4 , q = ⌊ γ z ε − 2 /16 ⌋ .
The choice of ε z \varepsilon_z ε z ensures q ≥ 1 q \ge1 q ≥ 1 . The center budget, cost balance, and error condition hold, and the same capacity estimates apply. This gives ∣ X ∣ ≍ z k D ε − 2 |X| \asymp_z kD\varepsilon^{-2} ∣ X ∣ ≍ z k D ε − 2 , which has the required order because k 0 1 − 2 / z = Θ z ( 1 ) k_0^{1-2/z}=\Theta_z(1) k 0 1 − 2/ z = Θ z ( 1 ) in this case. Proposition 3.5 completes the proof of Lemma 3.1 .
Remark 3.6 (k-means). For z = 2 z=2 z = 2 , the constant-scale choice B = g = k B=g=k B = g = k , m = 1 m=1 m = 1 , R = 4 R=4 R = 4 , and q = ⌊ γ 2 ε − 2 / 16 ⌋ q=\lfloor\gamma_2\varepsilon^{-2}/16\rfloor q = ⌊ γ 2 ε − 2 /16 ⌋ already gives ∣ X ∣ ≍ k D ε − 2 |X|\asymp kD\varepsilon^{-2} ∣ X ∣ ≍ k D ε − 2 for every k k k .
Proof of the sign-family lemma
To prove Lemma 3.2 , we use the binary signs from the Euclidean code in Lemma 2.1 , without the projection levels.
Proof of Lemma 3.2. Let L ≥ 1 L \ge1 L ≥ 1 be the least integer with 2 L > q + ( q 3 ) 2^L > q+\binom{q}{3} 2 L > q + ( 3 q ) . Use the distinct binary words b 1 , … , b q ∈ { 0 , 1 } L b_1,\ldots,b_q \in\{0,1\}^L b 1 , … , b q ∈ { 0 , 1 } L constructed in the proof of Lemma 2.1 , no four distinct of which sum to zero coordinatewise modulo two. For independent uniform signs r a , β r_{a,\beta} r a , β , a ∈ [ L ] a \in[L] a ∈ [ L ] , β ∈ { 0 , 1 } \beta\in\{0,1\} β ∈ { 0 , 1 } , set
χ s = ∏ a = 1 L r a , b s ( a ) . \chi_s=\prod_{a=1}^{L}r_{a,b_s(a)}. χ s = a = 1 ∏ L r a , b s ( a ) .
The parity-moment calculation from the Euclidean code proof gives unbiased four-wise independent coordinates. There are at most 2 2 L 2^{2L} 2 2 L outcomes, and minimality of L L L gives 2 L ≤ 2 ( q + ( q 3 ) + 1 ) ≤ 2 ( q + 2 ) 3 2^L \le2(q+\binom{q}{3}+1) \le2(q+2)^3 2 L ≤ 2 ( q + ( 3 q ) + 1 ) ≤ 2 ( q + 2 ) 3 . This proves the upper cardinality bound; unbiasedness gives ∣ H ∣ ≥ 2 |\mathcal{H}| \ge2 ∣ H ∣ ≥ 2 . For Z = ∑ s A s χ s Z=\sum_s A_s\chi_s Z = ∑ s A s χ s , the second and fourth moments satisfy
E Z 2 = ∑ s A s 2 , E Z 4 ≤ 3 ( ∑ s A s 2 ) 2 . \mathbb{E}Z^2=\sum_s A_s^2,\qquad\mathbb{E}Z^4\le3\left(\sum_s A_s^2\right)^2. E Z 2 = s ∑ A s 2 , E Z 4 ≤ 3 ( s ∑ A s 2 ) 2 .
If A ≠ 0 A\ne0 A = 0 , Hölder’s inequality gives E ∣ Z ∣ ≥ ( E Z 2 ) 3 / 2 / ( E Z 4 ) 1 / 2 ≥ ∥ A ∥ 2 / 3 \mathbb{E}|Z|\ge(\mathbb{E}Z^2)^{3/2}/(\mathbb{E}Z^4)^{1/2}\ge\|A\|_2/\sqrt{3} E ∣ Z ∣ ≥ ( E Z 2 ) 3/2 / ( E Z 4 ) 1/2 ≥ ∥ A ∥ 2 / 3 . The case A = 0 A=0 A = 0 is immediate.
Upper bound in doubling metrics
The following lemma supplies the upper bound used in Theorem 1.4 . Throughout this section, X X X has input weights u p > 0 u_p > 0 u p > 0 , and cost z ( X , C ) = ∑ p ∈ X u p d z ( p , C ) \operatorname{cost}_z(X,C) = \sum_{p\in X} u_p d^z(p,C) cost z ( X , C ) = ∑ p ∈ X u p d z ( p , C ) ; input subsets inherit these weights. The output S S S has weights w p w_p w p , with cost z ( S , C ) = ∑ p ∈ S w p d z ( p , C ) \operatorname{cost}_z(S,C) = \sum_{p\in S} w_p d^z(p,C) cost z ( S , C ) = ∑ p ∈ S w p d z ( p , C ) . All cardinalities count support points.
Lemma 4.1 (Coreset upper bound in doubling metrics). For every fixed real z ≥ 2 z \ge2 z ≥ 2 , integer k ≥ 1 k \ge1 k ≥ 1 , D ≥ 1 D \ge1 D ≥ 1 , and 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , every finite positively weighted dataset X X X in a metric space ( X , d ) (\mathcal{X},d) ( X , d ) with ddim ( X , d ) ≤ D \operatorname{ddim}(\mathcal{X},d) \le D ddim ( X , d ) ≤ D admits a nonnegatively weighted subset S ⊆ X S \subseteq X S ⊆ X of size
O ( k 2 − 2 / z ε − 2 [ D log ( 2 / ε ) + log ( 2 k ) ] ) (31) O\left(k^{2-2/z}\varepsilon^{-2}\left[D\log(2/\varepsilon)+\log(2k)\right]\right) \tag*{(31)} O ( k 2 − 2/ z ε − 2 [ D log ( 2/ ε ) + log ( 2 k ) ] ) (31) such that
∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ ε cost z ( X , C ) for every C ⊆ X with 1 ≤ ∣ 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 }1\le|C|\le k. ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ ε cost z ( X , C ) for every C ⊆ X with 1 ≤ ∣ C ∣ ≤ k .
Coreset construction and proof of Lemma 4.1
Let n = ∣ X ∣ n=|X| n = ∣ X ∣ . Choose a subset A ⊆ X A\subseteq X A ⊆ X with 1 ≤ ∣ A ∣ ≤ k 1\le|A|\le k 1 ≤ ∣ A ∣ ≤ k minimizing cost z ( X , A ) \operatorname{cost}_z(X,A) cost z ( X , A ) ; then cost z ( X , A ) ≤ 2 z cost z ( X , C ) \operatorname{cost}_z(X,A)\le2^z\operatorname{cost}_z(X,C) cost z ( X , A ) ≤ 2 z cost z ( X , C ) for every query C C C with 1 ≤ ∣ C ∣ ≤ k 1\le|C|\le k 1 ≤ ∣ C ∣ ≤ k . Write A = { a 1 , … , a ∣ A ∣ } A=\{a_1,\ldots,a_{|A|}\} A = { a 1 , … , a ∣ A ∣ } and partition X X X into P 1 , … , P ∣ A ∣ P_1,\ldots,P_{|A|} P 1 , … , P ∣ A ∣ by nearest-anchor assignment, breaking ties arbitrarily. We use the optimum only to simplify constants; approximate anchors are discussed at the end of this section. Within each cluster P i P_i P i , the algorithm draws s i s_i s i independent two-point weighted summaries and averages their weight vectors:
Algorithm 1. Coreset construction via two-point sampling
Input: X X X with weights u p > 0 u_p>0 u p > 0 , anchors A A A and clusters P i P_i P i as above, and 0 < ε , β < 1 0<\varepsilon,\beta<1 0 < ε , β < 1 .
If cost z ( X , A ) = 0 \operatorname{cost}_z(X,A)=0 cost z ( X , A ) = 0 , return X X X with its input weights.
For each i i i , set
s i = 1 + ⌈ K z ε − 2 ( cost z ( P i , A ) cost z ( X , A ) ) 2 / z [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ⌉ (32) s_i=1+\left\lceil K_z\varepsilon^{-2}\left(\frac{\operatorname{cost}_z(P_i,A)}{\operatorname{cost}_z(X,A)}\right)^{2/z}\left[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)\right]\right\rceil \tag*{(32)} s i = 1 + ⌈ K z ε − 2 ( cost z ( X , A ) cost z ( P i , A ) ) 2/ z [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β ) ] ⌉ (32)
where K z > 0 K_z>0 K z > 0 is a sufficiently large constant depending only on z z z .
Independently for each i i i and j ∈ [ s i ] j\in[s_i] j ∈ [ s i ] , draw ( u ^ p ( j ) ) p ∈ P i (\widehat{u}_p^{(j)})_{p\in P_i} ( u p ( j ) ) p ∈ P i using the distribution in Lemma 4.2 with weights ( u p ) p ∈ P i (u_p)_{p\in P_i} ( u p ) p ∈ P i and h p = d z ( p , A ) h_p=d^z(p,A) h p = d z ( p , A ) . Set
w p = 1 s i ∑ j = 1 s i u ^ p ( j ) ( p ∈ P i ) . (33) w_p=\frac{1}{s_i}\sum_{j=1}^{s_i}\widehat{u}_p^{(j)}\qquad(p\in P_i). \tag*{(33)} w p = s i 1 j = 1 ∑ s i u p ( j ) ( p ∈ P i ) . (33)
Return ( S , ( w p ) p ∈ S ) (S,(w_p)_{p\in S}) ( S , ( w p ) p ∈ S ) , where S = { p ∈ X : w p > 0 } S=\{p\in X:w_p>0\} S = { p ∈ X : w p > 0 } .
The next lemma supplies the two-point sampling distribution for Step 3.
Lemma 4.2 (Two-point unbiased sampling). Let ( u p ) (u_p) ( u p ) be nonnegative weights on a finite set and let h p ≥ 0 h_p\ge0 h p ≥ 0 . There is a finite distribution over nonnegative weight vectors ( u ^ p ) (\widehat{u}_p) ( u p ) , each supported on at most two points of { p : u p > 0 } \{p:u_p>0\} { p : u p > 0 } , such that
∑ p u ^ p = ∑ p u p , ∑ p u ^ p h p = ∑ p u p h p , E u ^ p = u p for every p . \sum_p \widehat{u}_p=\sum_p u_p,\qquad\sum_p \widehat{u}_p h_p=\sum_p u_p h_p,\qquad\mathbb{E}\widehat{u}_p=u_p\quad\text{for every }p. p ∑ u p = p ∑ u p , p ∑ u p h p = p ∑ u p h p , E u p = u p for every p .
Proof. Consider the bounded polytope of nonnegative weight vectors ( u ^ p ) (\widehat{u}_p) ( u p ) supported on { p : u p > 0 } \{p : u_p > 0\} { p : u p > 0 } that satisfy the two linear equations. There are two equality constraints and nonnegativity constraints, so every vertex (basic feasible solution) has at most two positive entries. Since ( u p ) (u_p) ( u p ) lies in this polytope, we can decompose ( u p ) (u_p) ( u p ) as a convex combination of its vertices and sample a vertex with probability equal to its convex coefficient.
Each draw in Step 3 is supported on at most two points of P i P_i P i and preserves the cluster’s total weight and anchor cost. Consequently, the averaged weights ( w p ) p ∈ X (w_p)_{p\in X} ( w p ) p ∈ X satisfy, deterministically for every i i i ,
∑ p ∈ P i w p = ∑ p ∈ P i u p , ∑ p ∈ P i w p d z ( p , A ) = ∑ p ∈ P i u p d z ( p , A ) = cost z ( P i , A ) . (34) \sum_{p\in P_i} w_p = \sum_{p\in P_i} u_p,\qquad\sum_{p\in P_i} w_p d^z(p,A) = \sum_{p\in P_i} u_p d^z(p,A) = \operatorname{cost}_z(P_i,A). \tag*{(34)} p ∈ P i ∑ w p = p ∈ P i ∑ u p , p ∈ P i ∑ w p d z ( p , A ) = p ∈ P i ∑ u p d z ( p , A ) = cost z ( P i , A ) . (34)
The averaged weights are also unbiased (E w p = u p \mathbb{E}\,w_p = u_p E w p = u p for all p ∈ X p\in X p ∈ X ). Together, these properties give the following guarantee for Algorithm 1.
Lemma 4.3 (Coreset guarantee for Algorithm 1). For every 0 < ε , β < 1 0 < \varepsilon,\beta< 1 0 < ε , β < 1 , Algorithm 1 returns a nonnegatively weighted subset S ⊆ X S\subseteq X S ⊆ X of size at most
O ( k 1 − 2 / z ε − 2 [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ) (35) O\left(k^{1-2/z}\varepsilon^{-2}\left[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)\right]\right) \tag*{(35)} O ( k 1 − 2/ z ε − 2 [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β ) ] ) (35) that is a strong ε \varepsilon ε -coreset of X X X with probability at least 1 − β 1-\beta 1 − β .
To see the size bound in Lemma 4.3 , note first that if cost z ( X , A ) = 0 \operatorname{cost}_z(X,A)=0 cost z ( X , A ) = 0 , then ∣ X ∣ ≤ k |X|\le k ∣ X ∣ ≤ k and the bound holds trivially. Otherwise, each of the s i s_i s i draws in cluster P i P_i P i contributes at most two points to S S S , so
∣ S ∣ ≤ 2 ∑ i s i ≲ ε − 2 [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ∑ i ( cost z ( P i , A ) cost z ( X , A ) ) 2 / z |S|\le2\sum_i s_i \lesssim\varepsilon^{-2}\left[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)\right]\sum_i\left(\frac{\operatorname{cost}_z(P_i,A)}{\operatorname{cost}_z(X,A)}\right)^{2/z} ∣ S ∣ ≤ 2 i ∑ s i ≲ ε − 2 [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β ) ] i ∑ ( cost z ( X , A ) cost z ( P i , A ) ) 2/ z
≲ k 1 − 2 / z ε − 2 [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] . (36) \lesssim k^{1-2/z}\varepsilon^{-2}\left[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)\right]. \tag*{(36)} ≲ k 1 − 2/ z ε − 2 [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β ) ] . (36)
The last inequality follows from the concavity of t 2 / z t^{2/z} t 2/ z for z ≥ 2 z\ge2 z ≥ 2 and ∑ i cost z ( P i , A ) = cost z ( X , A ) \sum_i\operatorname{cost}_z(P_i,A)=\operatorname{cost}_z(X,A) ∑ i cost z ( P i , A ) = cost z ( X , A ) . This proves the size bound in Lemma 4.3 ; we defer its approximation guarantee to the next subsection.
We first reduce to polynomial input size, then apply the sharper sampling bound once more. For 0 < η , β < 1 / 4 0 < \eta,\beta< 1/4 0 < η , β < 1/4 , Lemma 4.3 applies to weighted inputs and yields a coreset of size O ( k 2 − 2 / z ( D + 1 ) η − 3 log ( 2 n ) log ( 2 / β ) ) O(k^{2-2/z}(D+1)\eta^{-3}\log(2n)\log(2/\beta)) O ( k 2 − 2/ z ( D + 1 ) η − 3 log ( 2 n ) log ( 2/ β )) , using log ( 2 / η ) = O ( η − 1 ) \log(2/\eta)=O(\eta^{-1}) log ( 2/ η ) = O ( η − 1 ) . Applying Theorem A.4 with ρ = 3 \rho=3 ρ = 3 and s ( k ) = k 2 − 2 / z ( D + 1 ) s(k)=k^{2-2/z}(D+1) s ( k ) = k 2 − 2/ z ( D + 1 ) produces an ε / 4 \varepsilon/4 ε /4 -coreset X ′ ⊆ X X'\subseteq X X ′ ⊆ X of size polynomial in k k k , D D D , ε − 1 \varepsilon^{-1} ε − 1 , with probability at least 0.99 0.99 0.99 . In particular,
log ( 2 ∣ X ′ ∣ ) = O ( log ( 2 k ) + log ( D + 1 ) + log ( 2 / ε ) ) . \log(2|X'|)=O(\log(2k)+\log(D+1)+\log(2/\varepsilon)). log ( 2∣ X ′ ∣ ) = O ( log ( 2 k ) + log ( D + 1 ) + log ( 2/ ε )) .
Applying Lemma 4.3 once more to X ′ X' X ′ with its coreset weights, accuracy ε / 2 \varepsilon/2 ε /2 , and failure probability 1 / 100 1/100 1/100 , gives
∣ S ∣ ≲ k 1 − 2 / z ε − 2 [ k log ( 2 ∣ X ′ ∣ ) + k D log ( 2 / ε ) + 1 ] |S|\lesssim k^{1-2/z}\varepsilon^{-2}\left[k\log(2|X'|)+kD\log(2/\varepsilon)+1\right] ∣ S ∣ ≲ k 1 − 2/ z ε − 2 [ k log ( 2∣ X ′ ∣ ) + k D log ( 2/ ε ) + 1 ]
≲ k 2 − 2 / z ε − 2 [ D log ( 2 / ε ) + log ( 2 k ) ] . \lesssim k^{2-2/z}\varepsilon^{-2}\left[D\log(2/\varepsilon)+\log(2k)\right]. ≲ k 2 − 2/ z ε − 2 [ D log ( 2/ ε ) + log ( 2 k ) ] .
where log ( D + 1 ) = O ( D ) \log(D+1)=O(D) log ( D + 1 ) = O ( D ) for D ≥ 1 D\ge1 D ≥ 1 . With constant probability, both stages succeed; coreset composition then makes S ⊆ X ′ ⊆ X S\subseteq X'\subseteq X S ⊆ X ′ ⊆ X an ε \varepsilon ε -coreset, proving Lemma 4.1 .
Matching bounds. Combining (31) with the known O ~ ( k D ε − z ) \widetilde{O}(kD\varepsilon^{-z}) O ( k D ε − z ) upper bound [11 , 22 ] gives the upper bound in Theorem 1.4 .
Proof of Lemma 4.3: Error analysis
It remains to prove the approximation guarantee of Lemma 4.3 . The case cost z ( X , A ) = 0 \operatorname{cost}_z(X,A)=0 cost z ( X , A ) = 0 is exact, so assume cost z ( X , A ) > 0 \operatorname{cost}_z(X,A)>0 cost z ( X , A ) > 0 . Fix a query C C C . Clusters of zero anchor cost contain only their anchor and have zero residual; omit them from the range calculations. Exact cluster-mass preservation gives
cost z ( S , C ) − cost z ( X , C ) = ∑ i ∑ p ∈ P i ( w p − u p ) ( d z ( p , C ) − d z ( a i , C ) ) . \operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C)=\sum_i\sum_{p\in P_i}(w_p-u_p)\left(d^z(p,C)-d^z(a_i,C)\right). cost z ( S , C ) − cost z ( X , C ) = i ∑ p ∈ P i ∑ ( w p − u p ) ( d z ( p , C ) − d z ( a i , C ) ) .
To bound the fluctuations, we truncate the cost difference when C C C is far from a i a_i a i relative to d ( p , A ) d(p,A) d ( p , A ) (where d z ( p , C ) ≈ d z ( a i , C ) d^z(p,C)\approx d^z(a_i,C) d z ( p , C ) ≈ d z ( a i , C ) deterministically) and define, for p ∈ P i p\in P_i p ∈ P i ,
g C ( p ) = { d z ( p , C ) − d z ( a i , C ) , d ( p , A ) ≥ 2 − 3 z ε d ( a i , C ) , 0 , otherwise . (37) g_C(p)=
\begin{cases}
d^z(p,C)-d^z(a_i,C), & d(p,A)\ge2^{-3z}\varepsilon d(a_i,C),\\
0, & \text{otherwise}.
\end{cases} \tag*{(37)} g C ( p ) = { d z ( p , C ) − d z ( a i , C ) , 0 , d ( p , A ) ≥ 2 − 3 z ε d ( a i , C ) , otherwise . (37)
By (33) ,
∑ p ∈ X ( w p − u p ) g C ( p ) = ∑ i 1 s i ∑ j = 1 s i ∑ p ∈ P i ( u ^ p ( j ) − u p ) g C ( p ) . \sum_{p\in X}(w_p-u_p)g_C(p)=\sum_i\frac{1}{s_i}\sum_{j=1}^{s_i}\sum_{p\in P_i}(\widehat{u}_p^{(j)}-u_p)g_C(p). p ∈ X ∑ ( w p − u p ) g C ( p ) = i ∑ s i 1 j = 1 ∑ s i p ∈ P i ∑ ( u p ( j ) − u p ) g C ( p ) .
The summands indexed by ( i , j ) (i,j) ( i , j ) are independent by construction and centered by unbiasedness in Lemma 4.2 : independence is between weighted draws, not between coordinates within a draw. We bound the sum of their squared ranges to apply Hoeffding’s inequality.
Bounding the squared ranges. For p ∈ P i p\in P_i p ∈ P i , Lemma A.1 gives
∣ g C ( p ) ∣ ≤ ∣ d z ( p , C ) − d z ( a i , C ) ∣ ≲ d z ( p , A ) + d ( p , A ) d ( a i , C ) z − 1 . (38) |g_C(p)|\leq|d^z(p,C)-d^z(a_i,C)|\lesssim d^z(p,A)+d(p,A)d(a_i,C)^{z-1}. \tag*{(38)} ∣ g C ( p ) ∣ ≤ ∣ d z ( p , C ) − d z ( a i , C ) ∣ ≲ d z ( p , A ) + d ( p , A ) d ( a i , C ) z − 1 . (38)
For the fixed query C C C , let R i R_i R i be the range length of s i − 1 ∑ p ∈ P i u ^ p ( j ) g C ( p ) s_i^{-1}\sum_{p\in P_i}\widehat{u}_p^{(j)}g_C(p) s i − 1 ∑ p ∈ P i u p ( j ) g C ( p ) over all draws. This range is the same for every j ∈ [ s i ] j\in[s_i] j ∈ [ s i ] and is unchanged by centering the summand. By Hölder’s inequality (Lemma A.2 ) and the two preserved totals in (34) ,
∑ p ∈ P i u ^ p ( j ) d ( p , A ) ≤ ( ∑ p ∈ P i u ^ p ( j ) ) 1 − 1 / z ( ∑ p ∈ P i u ^ p ( j ) d z ( p , A ) ) 1 / z = ( ∑ p ∈ P i u p ) 1 − 1 / z cost z ( P i , A ) 1 / z . \sum_{p\in P_i}\widehat{u}_p^{(j)}d(p,A)\leq\left(\sum_{p\in P_i}\widehat{u}_p^{(j)}\right)^{1-1/z}\left(\sum_{p\in P_i}\widehat{u}_p^{(j)}d^z(p,A)\right)^{1/z}=\left(\sum_{p\in P_i}u_p\right)^{1-1/z}\operatorname{cost}_z(P_i,A)^{1/z}. p ∈ P i ∑ u p ( j ) d ( p , A ) ≤ p ∈ P i ∑ u p ( j ) 1 − 1/ z p ∈ P i ∑ u p ( j ) d z ( p , A ) 1/ z = p ∈ P i ∑ u p 1 − 1/ z cost z ( P i , A ) 1/ z .
Combining the preceding moment bound with (38) controls each uncentered draw and hence its range length:
R i ≲ 1 s i [ cost z ( P i , A ) + d ( a i , C ) z − 1 ( ∑ p ∈ P i u p ) 1 − 1 / z cost z ( P i , A ) 1 / z ] . (39) R_i\lesssim\frac{1}{s_i}\left[\operatorname{cost}_z(P_i,A)+d(a_i,C)^{z-1}\left(\sum_{p\in P_i}u_p\right)^{1-1/z}\operatorname{cost}_z(P_i,A)^{1/z}\right]. \tag*{(39)} R i ≲ s i 1 cost z ( P i , A ) + d ( a i , C ) z − 1 p ∈ P i ∑ u p 1 − 1/ z cost z ( P i , A ) 1/ z . (39)
There are s i s_i s i independent terms of range length R i R_i R i in cluster P i P_i P i . Squaring (39) , summing over clusters, and substituting the choice of s i s_i s i from (32) yields
∑ i s i R i 2 ≲ ∑ i cost z ( P i , A ) 2 + ( ∑ p ∈ P i u p d z ( a i , C ) ) 2 − 2 / z cost z ( P i , A ) 2 / z s i \sum_i s_i R_i^2 \lesssim\sum_i \frac{\operatorname{cost}_z(P_i,A)^2+\left(\sum_{p\in P_i}u_p d^z(a_i,C)\right)^{2-2/z}\operatorname{cost}_z(P_i,A)^{2/z}}{s_i} i ∑ s i R i 2 ≲ i ∑ s i cost z ( P i , A ) 2 + ( ∑ p ∈ P i u p d z ( a i , C ) ) 2 − 2/ z cost z ( P i , A ) 2/ z
≲ ε 2 cost z ( X , A ) 2 / z K z [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ⋅ ∑ i [ cost z ( P i , A ) 2 − 2 / z + ( ∑ p ∈ P i u p d z ( a i , C ) ) 2 − 2 / z ] . \lesssim\frac{\varepsilon^2\operatorname{cost}_z(X,A)^{2/z}}{K_z[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)]}\cdot\sum_i\left[\operatorname{cost}_z(P_i,A)^{2-2/z}+\left(\sum_{p\in P_i}u_p d^z(a_i,C)\right)^{2-2/z}\right]. ≲ K z [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β )] ε 2 cost z ( X , A ) 2/ z ⋅ i ∑ cost z ( P i , A ) 2 − 2/ z + p ∈ P i ∑ u p d z ( a i , C ) 2 − 2/ z .
Since 2 − 2 / z ≥ 1 2-2/z\ge1 2 − 2/ z ≥ 1 , each sum of nonnegative powers is at most the corresponding power of the sum. Combining this observation with Lemma A.1 gives
∑ i ∑ p ∈ P i u p d z ( a i , C ) ≤ 2 z − 1 [ cost z ( X , C ) + cost z ( X , A ) ] , \sum_i\sum_{p\in P_i}u_p d^z(a_i,C)\le2^{z-1}[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(X,A)], i ∑ p ∈ P i ∑ u p d z ( a i , C ) ≤ 2 z − 1 [ cost z ( X , C ) + cost z ( X , A )] ,
∑ i cost z ( P i , A ) 2 − 2 / z ≤ cost z ( X , A ) 2 − 2 / z , \sum_i\operatorname{cost}_z(P_i,A)^{2-2/z}\le\operatorname{cost}_z(X,A)^{2-2/z}, i ∑ cost z ( P i , A ) 2 − 2/ z ≤ cost z ( X , A ) 2 − 2/ z ,
∑ i ( ∑ p ∈ P i u p d z ( a i , C ) ) 2 − 2 / z ≲ [ cost z ( X , C ) + cost z ( X , A ) ] 2 − 2 / z . \sum_i\left(\sum_{p\in P_i}u_p d^z(a_i,C)\right)^{2-2/z}\lesssim[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(X,A)]^{2-2/z}. i ∑ p ∈ P i ∑ u p d z ( a i , C ) 2 − 2/ z ≲ [ cost z ( X , C ) + cost z ( X , A ) ] 2 − 2/ z .
Substituting these estimates yields
∑ i s i R i 2 ≲ ε 2 [ cost z ( X , C ) + cost z ( X , A ) ] 2 K z [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] . (40) \sum_i s_iR_i^2\lesssim\frac{\varepsilon^2[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(X,A)]^2}{K_z[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)]}. \tag*{(40)} i ∑ s i R i 2 ≲ K z [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β )] ε 2 [ cost z ( X , C ) + cost z ( X , A ) ] 2 . (40)
Hoeffding’s inequality (Lemma A.3 ) therefore gives
∣ ∑ p ∈ X ( w p − u p ) g C ( p ) ∣ ≤ 2 − z − 6 ε [ cost z ( X , C ) + cost z ( X , A ) ] (41) \left|\sum_{p\in X}(w_p-u_p)g_C(p)\right|\le2^{-z-6}\varepsilon[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(X,A)] \tag*{(41)} p ∈ X ∑ ( w p − u p ) g C ( p ) ≤ 2 − z − 6 ε [ cost z ( X , C ) + cost z ( X , A )] (41)
except with probability at most
2 exp ( − c z K z [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ) , (42) 2\exp(-c_zK_z[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)]), \tag*{(42)} 2 exp ( − c z K z [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β )]) , (42)
where c z > 0 c_z>0 c z > 0 depends only on z z z .
The preceding concentration bound holds for each fixed C C C . To obtain a guarantee for all queries C C C simultaneously, we use the following net.
Lemma 4.4 (Covering the truncated cost differences). There is a finite family V ⊆ R X V\subseteq\mathbb{R}^X V ⊆ R X and a map associating each query C C C with a vector v ∈ V v\in V v ∈ V , fixed before sampling, such that
∣ g C ( p ) − v p ∣ ≤ 2 − z − 6 ε d z ( p , A ) ( p ∈ X ) , (43) |g_C(p)-v_p|\le2^{-z-6}\varepsilon d^z(p,A)\qquad(p\in X), \tag*{(43)} ∣ g C ( p ) − v p ∣ ≤ 2 − z − 6 ε d z ( p , A ) ( p ∈ X ) , (43) log ∣ V ∣ ≲ k log ( 2 n ) + k D log ( 2 / ε ) . (44) \log|V|\lesssim k\log(2n)+kD\log(2/\varepsilon). \tag*{(44)} log ∣ V ∣ ≲ k log ( 2 n ) + k D log ( 2/ ε ) . (44)
Proof. Write r p = d ( p , A ) r_p=d(p,A) r p = d ( p , A ) and L = 2 3 z ε − 1 + 2 L=2^{3z}\varepsilon^{-1}+2 L = 2 3 z ε − 1 + 2 . Points with r p = 0 r_p=0 r p = 0 equal their anchors and have g C ( p ) = 0 g_C(p)=0 g C ( p ) = 0 for every C C C ; if all scales are zero, take V = { 0 } V=\{0\} V = { 0 } . Otherwise, fix δ = 2 − z − 8 ε / ( z L z − 1 ) ≍ ε z \delta=2^{-z-8}\varepsilon/(zL^{z-1})\asymp\varepsilon^z δ = 2 − z − 8 ε / ( z L z − 1 ) ≍ ε z . For each p ∈ P i p\in P_i p ∈ P i with r p > 0 r_p>0 r p > 0 , fix a cover of B ( a i , L r p ) B(a_i,Lr_p) B ( a i , L r p ) by balls of radius δ r p \delta r_p δ r p . Give every covering ball its own index, retaining its radius even if its center occurs in other covers. For each c ∈ C c\in C c ∈ C , record the index of a smallest-radius covering ball containing c c c , with ties broken by a fixed order; use a null record if no ball contains c c c . Sort the records and pad to k k k slots with null records. Together with the active suffix in each cluster, as defined by (37) , these slots form the query’s code. All covers and ordering rules are fixed before sampling.
Consider queries C , C ′ C,C' C , C ′ with the same code and an active p ∈ P i p\in P_i p ∈ P i with r p > 0 r_p>0 r p > 0 . At this coordinate, keep only records of radius at most δ r p \delta r_p δ r p . For x ∈ { p , a i } x\in\{p,a_i\} x ∈ { p , a i } , a center c ∈ C c\in C c ∈ C nearest to x x x satisfies d ( a i , c ) ≤ d ( a i , C ) + 2 r p ≤ L r p d(a_i,c)\le d(a_i,C)+2r_p\le Lr_p d ( a i , c ) ≤ d ( a i , C ) + 2 r p ≤ L r p . It therefore has a record of radius at most δ r p \delta r_p δ r p and is not discarded. The same record contains a center c ′ ∈ C ′ c'\in C' c ′ ∈ C ′ , so d ( c , c ′ ) ≤ 2 δ r p d(c,c')\le2\delta r_p d ( c , c ′ ) ≤ 2 δ r p and d ( x , C ′ ) ≤ d ( x , C ) + 2 δ r p d(x,C')\le d(x,C)+2\delta r_p d ( x , C ′ ) ≤ d ( x , C ) + 2 δ r p . The active suffixes agree, so exchanging C , C ′ C,C' C , C ′ gives ∣ d ( x , C ) − d ( x , C ′ ) ∣ ≤ 2 δ r p |d(x,C)-d(x,C')|\le2\delta r_p ∣ d ( x , C ) − d ( x , C ′ ) ∣ ≤ 2 δ r p . Thus discarding coarser and null records changes neither nearest distance. Both distances are at most L r p Lr_p L r p , by the cutoff and the triangle inequality. The mean value theorem now gives
∣ g C ( p ) − g C ′ ( p ) ∣ ≤ 4 z δ L z − 1 r p z = 2 − z − 6 ε r p z . |g_C(p)-g_{C'}(p)|\le4z\delta L^{z-1}r_p^z=2^{-z-6}\varepsilon r_p^z. ∣ g C ( p ) − g C ′ ( p ) ∣ ≤ 4 z δ L z − 1 r p z = 2 − z − 6 ε r p z .
Inactive coordinates and zero-scale coordinates agree exactly.
By doubling, the total number N N N of indexed covering balls is at most n ( O ( L / δ ) ) D n(O(L/\delta))^D n ( O ( L / δ ) ) D . Sorting each cluster by r p r_p r p gives at most n + 1 n+1 n + 1 active suffixes, including the empty suffix; equal radii are kept or discarded together. There are consequently at most ( N + 1 ) k ( n + 1 ) k (N+1)^k(n+1)^k ( N + 1 ) k ( n + 1 ) k codes. Choose one query C E C_E C E for each attained code E E E , set V = { g C E } V=\{g_{C_E}\} V = { g C E } , and map C C C to g C E ( C ) g_{C_E}(C) g C E ( C ) . These choices are fixed before sampling. The preceding comparison proves (43) ; counting the codes gives (44) , since L / δ = O z ( ε − ( z + 1 ) ) L/\delta=O_z(\varepsilon^{-(z+1)}) L / δ = O z ( ε − ( z + 1 ) ) . ∎
Uniform coreset guarantee. For each attained v ∈ V v\in V v ∈ V , fix before sampling a representative query C v C_v C v whose cost z ( X , C v ) + cost z ( X , A ) \operatorname{cost}_z(X,C_v)+\operatorname{cost}_z(X,A) cost z ( X , C v ) + cost z ( X , A ) is within a factor of two of the infimum over queries associated with v v v . Thus, for every C C C associated with v v v ,
cost z ( X , C v ) + cost z ( X , A ) ≤ 2 [ cost z ( X , C ) + cost z ( X , A ) ] . \operatorname{cost}_z(X,C_v)+\operatorname{cost}_z(X,A)\le2[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(X,A)]. cost z ( X , C v ) + cost z ( X , A ) ≤ 2 [ cost z ( X , C ) + cost z ( X , A )] .
The infimum is positive because cost z ( X , A ) > 0 \operatorname{cost}_z(X,A)>0 cost z ( X , A ) > 0 , so such a representative exists. Its concentration error is bounded in terms of the cost of every query it represents. There are at most ∣ V ∣ |V| ∣ V ∣ such fixed representatives. By (42) and (44) , a union bound shows that the probability that (41) fails for any of them is at most
2 ∣ V ∣ exp ( − c z K z [ k log ( 2 n ) + k D log ( 2 / ε ) + log ( 2 / β ) ] ) ≤ β . 2|V|\exp\left(-c_zK_z\left[k\log(2n)+kD\log(2/\varepsilon)+\log(2/\beta)\right]\right)\le\beta. 2∣ V ∣ exp ( − c z K z [ k log ( 2 n ) + k D log ( 2/ ε ) + log ( 2/ β ) ] ) ≤ β .
for sufficiently large K z K_z K z . Hence, with probability at least 1 − β 1-\beta 1 − β , concentration holds for every C v C_v C v . On this event, combining the cost comparison above and ∣ g C ( p ) − g C v ( p ) ∣ ≤ 2 − z − 5 ε d z ( p , A ) |g_C(p)-g_{C_v}(p)|\le2^{-z-5}\varepsilon d^z(p,A) ∣ g C ( p ) − g C v ( p ) ∣ ≤ 2 − z − 5 ε d z ( p , A ) with exact anchor-cost preservation and cost z ( X , A ) ≤ 2 z cost z ( X , C ) \operatorname{cost}_z(X,A)\le2^z\operatorname{cost}_z(X,C) cost z ( X , A ) ≤ 2 z cost z ( X , C ) gives, for every C C C associated with v v v ,
∣ ∑ p ∈ X ( w p − u p ) g C ( p ) ∣ ≤ ∣ ∑ p ∈ X ( w p − u p ) g C v ( p ) ∣ + 2 − z − 4 ε cost z ( X , A ) ≤ ε 8 cost z ( X , C ) . (45) \left|\sum_{p\in X}(w_p-u_p)g_C(p)\right|
\le\left|\sum_{p\in X}(w_p-u_p)g_{C_v}(p)\right|+2^{-z-4}\varepsilon\operatorname{cost}_z(X,A)
\le\frac{\varepsilon}{8}\operatorname{cost}_z(X,C). \tag*{(45)} p ∈ X ∑ ( w p − u p ) g C ( p ) ≤ p ∈ X ∑ ( w p − u p ) g C v ( p ) + 2 − z − 4 ε cost z ( X , A ) ≤ 8 ε cost z ( X , C ) . (45)
For points removed by the cutoff, g C ( p ) = 0 g_C(p)=0 g C ( p ) = 0 and d ( p , A ) < 2 − 3 z ε d ( a i , C ) d(p,A)<2^{-3z}\varepsilon d(a_i,C) d ( p , A ) < 2 − 3 z ε d ( a i , C ) . The latter condition implies d ( a i , C ) ≤ 2 d ( p , C ) d(a_i,C)\le2d(p,C) d ( a i , C ) ≤ 2 d ( p , C ) , so Lemma A.1 gives ∣ d z ( p , C ) − d z ( a i , C ) ∣ ≤ ε 4 d z ( p , C ) |d^z(p,C)-d^z(a_i,C)|\le\frac{\varepsilon}{4}d^z(p,C) ∣ d z ( p , C ) − d z ( a i , C ) ∣ ≤ 4 ε d z ( p , C ) . Combining the sampled and truncated contributions over X X X , with ∣ w p − u p ∣ ≤ w p + u p |w_p-u_p|\le w_p+u_p ∣ w p − u p ∣ ≤ w p + u p , yields
∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ ε 8 cost z ( X , C ) + ε 4 [ cost z ( X , C ) + cost z ( S , C ) ] , |\operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C)|
\le\frac{\varepsilon}{8}\operatorname{cost}_z(X,C)
+\frac{\varepsilon}{4}\left[\operatorname{cost}_z(X,C)+\operatorname{cost}_z(S,C)\right], ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ 8 ε cost z ( X , C ) + 4 ε [ cost z ( X , C ) + cost z ( S , C ) ] ,
which implies ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ 5 ε / 8 1 − ε / 4 cost z ( X , C ) < ε cost z ( X , C ) |\operatorname{cost}_z(S,C)-\operatorname{cost}_z(X,C)|\le\frac{5\varepsilon/8}{1-\varepsilon/4}\operatorname{cost}_z(X,C)<\varepsilon\operatorname{cost}_z(X,C) ∣ cost z ( S , C ) − cost z ( X , C ) ∣ ≤ 1 − ε /4 5 ε /8 cost z ( X , C ) < ε cost z ( X , C ) , proving Lemma 4.3 .
Approximate anchors. Write Q C = cost z ( X , C ) Q_C = \operatorname{cost}_z(X,C) Q C = cost z ( X , C ) and V = cost z ( X , A ) V = \operatorname{cost}_z(X,A) V = cost z ( X , A ) . The argument also applies to any A ⊆ X A \subseteq X A ⊆ X with 1 ≤ ∣ A ∣ ≤ k 1 \le|A| \le k 1 ≤ ∣ A ∣ ≤ k and V ≤ α Q C V \le\alpha Q_C V ≤ α Q C for every query, where 1 ≤ α = O z ( 1 ) 1 \le\alpha= O_z(1) 1 ≤ α = O z ( 1 ) , using the nearest-anchor partition. For target accuracy ε \varepsilon ε in a sampling stage, use internal accuracy η = ε / [ 8 ( 1 + α ) ] \eta= \varepsilon/[8(1+\alpha)] η = ε / [ 8 ( 1 + α )] in place of ε \varepsilon ε . Before applying the anchor comparison, the preceding proof bounds the error on truncated residuals by 2 − z − 6 η ( 2 Q C + 6 V ) 2^{-z-6}\eta(2Q_C + 6V) 2 − z − 6 η ( 2 Q C + 6 V ) and the discarded error by η [ Q C + cost z ( S , C ) ] / 4 \eta[Q_C + \operatorname{cost}_z(S,C)]/4 η [ Q C + cost z ( S , C )] /4 . Substituting V ≤ α Q C V \le\alpha Q_C V ≤ α Q C and moving the sampled-error term to the left gives relative error at most η [ 2 − z − 6 ( 2 + 6 α ) + 1 / 2 ] / ( 1 − η / 4 ) < ε \eta[2^{-z-6}(2 + 6\alpha) + 1/2]/(1-\eta/4) < \varepsilon η [ 2 − z − 6 ( 2 + 6 α ) + 1/2 ] / ( 1 − η /4 ) < ε . This rescales both the sampling and covering accuracies, changing only constants depending on z z z and α \alpha α . At every iterative size-reduction stage, choose such anchors for the current weighted input and rescale that stage’s target accuracy in the same way.
AI methodology
We used ChatGPT (OpenAI) to help develop and draft parts of the proofs and to revise the exposition. The authors revised and verified the arguments, checked the references, and take full responsibility for the paper.
Auxiliary results
The following inequalities and size-reduction theorem supply the auxiliary tools used in § 4 .
Lemma A.1 (Metric inequalities). Let ( X , d ) (\mathcal{X},d) ( X , d ) be a metric space, let C ⊆ X C \subseteq\mathcal{X} C ⊆ X be nonempty and finite, and let z ≥ 2 z \ge2 z ≥ 2 be real. For all p , q ∈ X p,q \in\mathcal{X} p , q ∈ X ,
d z ( p , C ) ≤ 2 z − 1 [ d z ( p , q ) + d z ( q , C ) ] , d^z(p,C) \le2^{z-1}\left[d^z(p,q)+d^z(q,C)\right], d z ( p , C ) ≤ 2 z − 1 [ d z ( p , q ) + d z ( q , C ) ] , ∣ d z ( p , C ) − d z ( q , C ) ∣ ≤ z 2 z − 2 [ d z ( p , q ) + d ( p , q ) d z − 1 ( q , C ) ] . \left|d^z(p,C)-d^z(q,C)\right| \le z2^{z-2}\left[d^z(p,q)+d(p,q)d^{z-1}(q,C)\right]. ∣ d z ( p , C ) − d z ( q , C ) ∣ ≤ z 2 z − 2 [ d z ( p , q ) + d ( p , q ) d z − 1 ( q , C ) ] .
Proof. The triangle inequality gives d ( p , C ) ≤ d ( p , q ) + d ( q , C ) d(p,C) \le d(p,q)+d(q,C) d ( p , C ) ≤ d ( p , q ) + d ( q , C ) and ∣ d ( p , C ) − d ( q , C ) ∣ ≤ d ( p , q ) \left|d(p,C)-d(q,C)\right| \le d(p,q) ∣ d ( p , C ) − d ( q , C ) ∣ ≤ d ( p , q ) . The first bound follows from ( x + y ) z ≤ 2 z − 1 ( x z + y z ) (x+y)^z \le2^{z-1}(x^z+y^z) ( x + y ) z ≤ 2 z − 1 ( x z + y z ) for x , y ≥ 0 x,y \ge0 x , y ≥ 0 .
For the second bound, the mean value theorem gives, for all x , y ≥ 0 x,y \ge0 x , y ≥ 0 ,
∣ x z − y z ∣ ≤ z ∣ x − y ∣ max { x , y } z − 1 . (46) \left|x^z-y^z\right| \le z|x-y|\max\{x,y\}^{z-1}. \tag*{(46)} ∣ x z − y z ∣ ≤ z ∣ x − y ∣ max { x , y } z − 1 . (46)
Substitute x = d ( p , C ) x=d(p,C) x = d ( p , C ) and y = d ( q , C ) y=d(q,C) y = d ( q , C ) . The triangle inequality bounds max { d ( p , C ) , d ( q , C ) } ≤ d ( q , C ) + d ( p , q ) \max\{d(p,C),d(q,C)\} \le d(q,C)+d(p,q) max { d ( p , C ) , d ( q , C )} ≤ d ( q , C ) + d ( p , q ) ; applying ( x + y ) z − 1 ≤ 2 z − 2 ( x z − 1 + y z − 1 ) (x+y)^{z-1} \le2^{z-2}(x^{z-1}+y^{z-1}) ( x + y ) z − 1 ≤ 2 z − 2 ( x z − 1 + y z − 1 ) then gives the second bound.
Lemma A.2 (Hölder’s inequality). For z > 1 z>1 z > 1 and nonnegative finite sequences ( a p ) (a_p) ( a p ) and ( b p ) (b_p) ( b p ) ,
∑ p a p b p ≤ ( ∑ p a p z / ( z − 1 ) ) 1 − 1 / z ( ∑ p b p z ) 1 / z . \sum_p a_pb_p \le\left(\sum_p a_p^{z/(z-1)}\right)^{1-1/z}\left(\sum_p b_p^z\right)^{1/z}. p ∑ a p b p ≤ ( p ∑ a p z / ( z − 1 ) ) 1 − 1/ z ( p ∑ b p z ) 1/ z . In particular, for nonnegative ( v p ) (v_p) ( v p ) and ( t p ) (t_p) ( t p ) ,
∑ p v p t p ≤ ( ∑ p v p ) 1 − 1 / z ( ∑ p v p t p z ) 1 / z . \sum_p v_pt_p \le\left(\sum_p v_p\right)^{1-1/z}\left(\sum_p v_pt_p^z\right)^{1/z}. p ∑ v p t p ≤ ( p ∑ v p ) 1 − 1/ z ( p ∑ v p t p z ) 1/ z .
Lemma A.3 (Hoeffding’s inequality [23 ] ). Let Y 1 , … , Y m Y_1,\ldots,Y_m Y 1 , … , Y m be independent real-valued random variables, and let a j ≤ b j a_j \le b_j a j ≤ b j be finite deterministic bounds such that a j ≤ Y j ≤ b j a_j \le Y_j \le b_j a j ≤ Y j ≤ b j almost surely for every j ∈ [ m ] j \in[m] j ∈ [ m ] . For every t > 0 t>0 t > 0 ,
Pr [ ∣ ∑ j = 1 m ( Y j − E Y j ) ∣ ≥ t ] ≤ 2 exp ( − 2 t 2 ∑ j = 1 m ( b j − a j ) 2 ) . \Pr\left[\left|\sum_{j=1}^{m}(Y_j-\mathbb{E}Y_j)\right|\ge t\right]\le2\exp\left(-\frac{2t^2}{\sum_{j=1}^{m}(b_j-a_j)^2}\right). Pr [ j = 1 ∑ m ( Y j − E Y j ) ≥ t ] ≤ 2 exp ( − ∑ j = 1 m ( b j − a j ) 2 2 t 2 ) . If ∑ j = 1 m ( b j − a j ) 2 = 0 \sum_{j=1}^{m}(b_j-a_j)^2=0 ∑ j = 1 m ( b j − a j ) 2 = 0 , the probability on the left is zero.
The two-sided bound follows by applying Hoeffding’s one-sided inequality to ( Y j ) j = 1 m (Y_j)_{j=1}^{m} ( Y j ) j = 1 m and ( − Y j ) j = 1 m (-Y_j)_{j=1}^{m} ( − Y j ) j = 1 m and taking a union bound.
Theorem A.4 (Iterative size reduction [BJKW21, Theorem 3.1]). Fix z ≥ 1 z \ge1 z ≥ 1 , a constant ρ ≥ 1 \rho\ge1 ρ ≥ 1 , and a family M \mathcal{M} M of metric spaces. Suppose that, for some function s : N → [ 1 , ∞ ) s : \mathbb{N} \to[1,\infty) s : N → [ 1 , ∞ ) , a randomized algorithm constructs, for every integer k ≥ 1 k \ge1 k ≥ 1 , every finite positively weighted dataset X ⊆ X X \subseteq\mathcal{X} X ⊆ X with ( X , d ) ∈ M (\mathcal{X},d) \in\mathcal{M} ( X , d ) ∈ M , and every 0 < η , β < 1 / 4 0 < \eta,\beta< 1/4 0 < η , β < 1/4 , a strong η \eta η -coreset for ( k , z ) (k,z) ( k , z ) -clustering supported on X X X of size
O ( η − ρ s ( k ) log ( 2 ∣ X ∣ ) log ( 2 / β ) ) O(\eta^{-\rho}s(k)\log(2|X|)\log(2/\beta)) O ( η − ρ s ( k ) log ( 2∣ X ∣ ) log ( 2/ β )) with probability at least 1 − β 1-\beta 1 − β . Then iterating this algorithm with suitable accuracies and failure probabilities constructs, for every 0 < ε , β < 1 / 4 0 < \varepsilon,\beta< 1/4 0 < ε , β < 1/4 , a strong ε \varepsilon ε -coreset supported on X X X of size
O ~ ( ε − ρ s ( k ) log ( 2 / β ) ) \widetilde{O}(\varepsilon^{-\rho}s(k)\log(2/\beta)) O ( ε − ρ s ( k ) log ( 2/ β )) with probability at least 1 − β 1-\beta 1 − β . Here ∣ X ∣ |X| ∣ X ∣ counts support points, and O ~ \widetilde{O} O hides only logarithmic factors in ε − 1 \varepsilon^{-1} ε − 1 , s ( k ) s(k) s ( k ) , and log ( 2 / β ) \log(2/\beta) log ( 2/ β ) .