Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
Authors: Ziyi Fang
Lingxiao Huang
Runkai Yang
Venue: NeurIPS 2025 poster ()
Keywords: coreset
robust geometric median
Euclidean space
outlier
robust clustering
Primary area: optimization

Abstract: We study the robust geometric median problem in Euclidean space $\mathbb{R}^d$, with a focus on coreset construction. A coreset is a compact summary of a dataset $P$ of size $n$ that approximates the robust cost for all centers $c$ within a multiplicative error $\varepsilon$. Given an outlier count $m$, we construct a coreset of size $\tilde{O}(\varepsilon^{-2} \cdot \min \\{ \varepsilon^{-2}, d \\})$ when $n \geq 4m$, eliminating the $O(m)$ dependency present in prior work [Huang et al., 2022 & 2023]. For the special case of $d = 1$, we achieve an optimal coreset size of $\tilde{\Theta}(\varepsilon^{-1/2} + \frac{m}{n} \varepsilon^{-1})$, revealing a clear separation from the vanilla case studied in [Huang et al., 2023; Afshani and Chris, 2024]. Our results further extend to robust $(k,z)$-clustering in various metric spaces, eliminating the $m$-dependence under mild data assumptions. The key technical contribution is a novel non-component-wise error analysis, enabling substantial reduction of outlier influence, unlike prior methods that retain them. Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across a wide range of datasets.

Coreset for Robust Geometric Median: Eliminating Size Dependency on Outliers
Ziyi Fang Nanjing University
Lingxiao Huang
Runkai Yang Nanjing University
Nanjing University
Abstract
We study the robust geometric median problem in Euclidean space R4, with focus on coreset construction. A coreset is compact summary of a dataset of size n that approximates the robust cost for all centers e within a multiplicative error e. Given an outlier count m, we construct a coreset of size O(in=
d)) when
n 2 4m, eliminating the (m) dependency present in prior work [39
40) For the
special case of d 1, we achieve an optimal coreset size of ( revealing clear separation from the vanilla case studied in 40
1/2
+ m "
1. Our results
further extend to robust (k: 2) 2-cclusteiing in various metric spaces, eliminating the m-dependence under mild data assumptions. The key technical contribution is a novel non-component-we wise error analysis, enabling substantial reduction outlier influence, unlike prior methods that retain them. Empirically, our algorithms consistently outperform existing baselines in terms of size-accuracy tradeoffs and runtime, even when data assumptions are violated across wide range of datasets.
Introduction
Geometric median, also known as the Hermat-Weber problem, is foundational problem in computa- tional geometry, whose objective is to identify a center e E IRd for given dataset P C IR of size n that minimizes the sum of Euclidean distances from each data point to c. The given objective function, while simple and user- friendly, suffers from significant robustness problems when exposed to noisy or adversarial data [13] 15
14 32 24). For example, an adversary could add few distant noisy outliers to the main cluster. These points could deceive the geometric median algorithm into incorrectly positioning the center closer these outliers to minimize the cost function. Such susceptibility to outliers has been considerable obstacle in data science and machine learning, prompting substantial amount of algorithmic research on the subject [5 32
29
53 49).
Robust geometric median. We consider robust versions of the geometric median problem, specifi- cally widely-used variant that introduces outliers [13. Formally, given integer m 0, the goal of robust geometric median is to find center E R that minimizes the objective function:
cost (m)) (P,c) == min minLCP: Epery dist(p,
where L represents the set of m outliers w.r.t. and dist(p, c) ||p cll2 denotes the Euclidean distance from p to center c. Intuitively. outliers capture the points that are furthest away and these are typically considered to be noise. When the number of outliers = 0. the robust geometric median problem simplifies to the vanilla geometric median. This problem (together with its generalization: robust (k: 2) =>clusstei)gg) has been well studied in the literature 15 29 23 53). However, the
presence of outliers introduces significant computational challenges, particularly in the context of
large-scale datasets 52 50 51 53]. For example, the approximation algorithm for robust geometric
Alphabetical order. Correspondence to: huangl ingxiao@nju..u.mmmmmmomou edu. en. LH's affiliations are the State Key Laboratory of Novel Software Technology and the New Comnestone Science Laboratory.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

median proposed by [52] requires OO (n m)d and [2 presents fixed- fixed-paramess parameter tractable (FPT) algorithm with m)) n (11) time. These challenges have driven extensive research on data reduction algorithms designed for limited hardware and time constraints.
Coreset. To tackle the computational challenge, we study coresets, which are (weighted) subsets S P such that the clustering cost cost(m)(S, c) approximates cost(m)) P. c) within a factor of e1+ for all center sets c E Rdd where ε > a given error parameter coreset preserves key geometric information while substantially reducing the dataset size, thus serving as a compact proxy for the original dataset P. Consequently, applying existing approximation algorithms to the coreset significantly improves computational efficiency. Moreover, coresets can be reused in future analyses of P. reducing redundant computation and saving storage resources. Finally, the size of the coreset reflects the intrinsic complexity of the problem, making the study of optimal coreset size a research topic of independent interest.
Coreset for vanilla geometric median (m = 0) has been extensively studied across different di- (see Appendix A.2 for details). When = 37 proposed a coreset of size O 1/2). Subsequently, [ extended this result by constructing an optimal coreset
mensions d [28]
16
18
19
of size ô( ()=+411++) for dimension d = 0(1). Moreover, for high dimensions > e-2, the optimal coreset size is +(= [18] 21]. In contrast, the study of coreset for robust geometric median is far from optimal, even in the simplest case of d = 1. Early work either required an exponentially large coreset size 27 or involved relaxing the outlier constraint [9]. A notable recent advancement by [39] overcame these limitations, proposing a coreset of size ((m) + Ō min(= - dd))), using hierarchical sampling framework based on (9] Further improvements reduced the core- set size to O(m) + Ö(E=² minfs d)) 40]. A recent paper
42 presented coreset size O + Vanilla size) via a novel reduction from the robust case to the vanilla case.
All previous coreset sizes for robust geometric median contain the factor m. However, the outlier number m could approach ((n) in real-world scenarios [25 30 10. For instance, the PageBlocks dataset has 5473 points with & 0.1n outliers [10]. Such m results in an inefficient coreset
size, raising natural question: Can we eliminate the ((m) term from the coreset size?
At first glance, one might assume the answer is negative, as (39] establishes coreset lower bound of (m). However, their worst-case instance critically relies on an extremely large number of outliers, specifically with m n - This requirement can be relaxed to m o(n) (see Theorem I.I. Motivated by this, we investigate the possibility of eliminating the (m) dependency when n m = (n)), and show that this condition is both necessary and sufficient. Under this setting, we obtain coreset of size Ō(=-2... min(s d)} (see Theorem 1.3
Nevertheless, this size substantially larger than that of the vanilla case across all dimensions. For instance, when d 1, our coreset size is Ö(E-2), whereas the vanilla case achieves a size of only
[37]: thus, our bound likely not optimal. On the other hand, our lower bound in Theorem I.I suggests that the optimal coresct size should indeed depend on m. This raises a natural question: What the optimal coreset size for robust geometric median, and how does it vary with m.? Answering this question sheds light on when the complexity of robust geometric median fundamentally diverges from that of the vanilla case.
1.1 Our contributions
In this paper, we study (optimal) coreset sizes for the robust geometric median problem. See Table in the appendix for a summary. We begin with a lower bound result (proof in Section C.
Theorem 1.1 (Coreset lower bound for robust geometric median). Let 0 < e < 0.5 and n > m 2 1. There exists a dataset P IR of size such that any e-coreset of P for the robust geometric median
problem must have size M m
"Here Ö(n) denotes On (nlylog(n)). hiding logarithmic factors. Herr, the computation of (ost(m) (S)m)((Ss excludes points of total weight m.; see Appendix A.1 for the formal detinition.

---

This theorem indicates that when n - m o(n), which implies m = (n), the coreset size is at least 92
m m which depends on m.. This extends the previous result in 39 to general m.
n
o(m))
Thus, n m (n)) is a necessary condition for eliminating the (()) term from the coreset size,
Accordingly, we assume 2 4m for the algorithmic results, where the constant 4 ensures the inlier number n m is sufficiently larger than the outlier number m. We first state our result when Theorem 1.2 (Optimal coreset for robust ID geometric median). Let n, m 2 1 be integers and 4m. There is linear algoritlum that given dataset P C R of size n, outputs an E-coreset for robust 1D geometric median of size Ō( à + n ===1) in (n)) time. Moreover, there exists a dataset X C R of size n such that any g-coresel must have size
1.
E (0, 1). Assume
This theorem provides the optimal coreset size for the robust ID geometric median problem. Since m S n. the coreset size is at most Ö(E-)), which is independent of m. Thus, we eliminate the O(m) dependency in the coreset size compared to previous bounds 40
In particular, relative the bound ((m) + Ö( 2) in 400, our result also improves the e-dependence from = to at most
The theorem also shows how the coreset size increases as m grows. When m S VEn, our coreset size is dominated by Ö(E 1/2) since m E- S <-1//2 This size matches the coreset size Ö( 1/2) for vanilla ID geometric median as given in [4)] As m increases from Vēn to 7, our coreset size is dominated by the term ) which is a linear function of i growing from ((s-1/3) to (. This size suggests that the complexity of robust ID geometric median is higher than vanilla ID geometric median in this range of outlier number m.
We remark that the size lower bound Q(== + = holds for any dimension d 2 1. In contrast, for d O()), the tight coreset size for the vanilla geometric median is ((s-d/(d+1) M. This implies that when 2 Ω(n g/((+11)) our coreset size lower bound exceeds Q(s ((s-d/(a+1),, resulting in gap between the coreset sizes for the robust and vanilla versions of geometric median.
Theorem 1.3 (Coreset for robust geometric median in R Let nt, m, d 2 1 be integers and E (0, 1). Assume 2 4m. There exists randomized algorithm that given a dataset P c IR of size n. outputs an e-coreset for the robust geometric median problem of size Ō( "min (5 { (d) in O(nd) time.
Compared to previous bounds ((m) + Ō(E-² min {o-2
d}) 40 and O(me Ō(e [42]
this theorem eliminates the (()) term in the coreset size when n 2 4m. This result can be extended to various metric spaces (Section E.2).
Finally, we extend this theorem to handle the robust (k, 2) cllustrrii problem (Definition F.I which encompasses robust k-median (z = 1) and robust k-means (z = 2). To capture the additional complexity introduced by k, we propose the following geometric assumption.
Assumption 1.4 (Assumptions for robust (k,, =)cllsstern Given a dataset P C Rd of n points and an e-approximate center set C C Rd of P for robust (kl.s)-luuttering De- fine Pj == arg
Eper, dist C*) to be the inlier points w.r.t. C³, where dist(p, C*) == minego- dist(p,c). Let (P....., PP)) C Pt denote the k inlier clusters induced by C**, where each P.' contains points in Pj whose closest center is ct. We assume the followings: 1) minsele| PT1 2 4m; 2) maxpe p7 dist(p, C*)²² S 4k Epery dist(p, (*)pp"
The first condition directly generalizes the assumption n 2 4m, which requires that the size of each inlier cluster more than the outlier number m. The second excludes "remote inlier points" to C** which could play a similar role as outliers. This condition holds for several real-world datasets (see Table D. demonstrating its practicality. Now we propose the following result.
Theorem 1.5 (Coreset for robust (k, 2 cluustteri, Let n, k. d 2 1 be integers and E E (0, There exists randomized algorithm that given a dataset P C Rdd of size n satisfying Assumption 1.4 outputs an E-coreset for robust (k, clllustring of size 2 min {==2, ,d)) in ((kkd) time.
It improves upon the previous result 0(m) + Ō(KZg 2= min {s 2dd) in 39 40
by eliminating
the (m)) term. Furthermore, the result can also be extended to various metric spaces (Section F33
Empirically, Section 4 we evaluate the performance of our coreset algorithms on six real-world datasets. We compare the size-error tradeoff against baselines (39 40), and across all tested sizes, our
3

---

algorithms consistently achieve lower empirical error. For instance, for robust geometric median on the Census1990 dataset, our method produces coreset of size 1000 with an empirical error of 0.012. while the baseline produces coreset of size 2300 with an empirical error slightly higher than 0.013 (Figure 2). Moreover, our algorithms provide a speedup compared to baselines for achieving the same level of empirical error (see e.g., Table Additionally, we show that our algorithms remain practically effective, regardless of which data assumption in the theoretical results is violated, further demonstrating the practical utility of our algorithms (Section G
1.2 Technical overview
We outline the technical ideas and novelty for Theorems 1.2 and 1.3] Our approach introduces a novel non-component -wise error analysis for coreset construction, enabling a substantial reduction in the number of outlier points rather than preserving them all. In contrast, previous algorithms divide the dataset P into multiple components, and their approach requires aligning the number of outliers between and S every component. This idea, as we will show, inherently introduces an (2mm)-size coreset. Furthermore, for the ID case, our new algorithm offers more refined partitioning of inlier points, enabling an adaptation of the vanilla coreset construction and leading to the optimal coreset size.
1.2.1 Overview for Theorem 1.2 (d 1)
Revisiting coreset construction for vanilla 1D geometric median. Recall that [37 first partitions dataset P- {pI..... Pn. C. E. into Ö( 0(2-1/2) buckets, where each bucket B, is a consecutive subsequence P1+1- .............. Pr) (see Definition 2.1 They select mean point (BB), assign a weight [B] for each bucket B, and output their union as a coreset such that Vc E IR,
Eiemy (B. c) - -B:| dist(u(B:),,) c) S cost(P,cc.
(2)
This follows that only the bucket containing e contributes a non-zero error at most E cost c) (see Lemma B.I.. To handle the additional outliers for the robust case, a natural idea is extend Inequality ( in the following manner: for each center e R and each tuple (m1...., m.) E ZT of outlier numbers per bucket (with EE(TT] my = m),
EnEr /cost (m..) (B,, c) - (B m.) dist (u(s), S 8 cost (m)) (m),
(3)
This bounds the induced error /cost (m.) [B;, (lB,) m.) (uis((((B)))))) when aligning the outlier numbers within this bucket for dataset P and coreset S.
of each bucket B,
Prior work [39 40 utilized this component- component-wise error analysis for robust coreset construction. They show that at most three buckets B, could induce a non-zero error, including a bucket that contains e and two "partially intersected" buckets with ( < m, < [B;] that contain both inlier and outlier points relative to c. Thus, to prove Inequality (3). it suffices to ensure that the maximum induced error joost (m.) (B, c) ([B. - m,)- dist (B.), c) of these three buckets is at most E cost (mm) (P. c)/3. However, possible that (m)) (P. c) < cost(P,cc,, which presents a significant challenge for this guarantee compared to the vanilla case. To overcome this obstacle, prior work [39 40 includes the "outmost" m points of P into the coreset to ensure zero induced error from them, resulting in an (m)) size dependency.
(m)
First attempt eliminate the O(m) dependency. We first observe that a subset PM (pm+1,.... -m } C P of size n 1 2m acts as inliers w.r.t. any center e E IR. The condition n 2 4m guarantees the existence of this Pas with |Prl = n 2m 2 2m. Since cost (P, c) Z cost (Pas, e) by the construction of Par, (m) (P, c) is intuitively not "too small", which is useful for eliminating the (m)) dependency in analysis. A natural idea is apply the vanilla coreset construction method given by 37 to PM and also include P PM in the coreset S. This attempt yields a coreset of
size 2m + (g which already improves the previous bound of ((m) + Ō(==²) by [40. To eliminate the (mm) term, it is essential to significantly reduce points in PM-
Our first attempt is to further decompose P PM into buckets and utilize the component-wise error analysis Inequality (3) As discussed earlier, the critical step is to ensure (cost (B, c) ([B.)- m²) dist(u(B.) (B), e)l S S cost c) for two partially intersecting buckets induced by e with
0 my < [B). To achieve this, we study the relative location of such buckets with respect to

---

(Lemma ). enabling us to partition the buckets based on the scale of cost (P. c), similar to the vanilla method (see Lines 1-5 of Algorithm D However, this partitioning approach is applicable only for PAs. where the scale of cost (P, c) is well-controlled (see Lemma D.Ip. Consequently, the challenge remains to control the induced error of these buckets for c $ PM-
Obstacle for PAs. Unfortunately, to ensure Inequality (3) holds for & PM. the number of constructed buckets in P- PM must be at least ((m). To see this, we provide an illustrative example in Section A.3 where there is collection Pi of (n m) points condensed into small interval, and a collection P2 of m points that are exponentially far from each other. We show that for any bucket containing two points p, Q P2 with p < q. the induced error of this bucket could be much larger than (m) (P)... c). Thus, to ensure Inequality (3) holds, all points in P22 must be included in the coreset, leading to a size of f(m)). Therefore, a new error analysis beyond Inequality (3) is required.
Key approach. W.L.O.G., we assume C > Pn-m, i.e., C is to the right of PMs. The key idea is to develop a novel non-component wise enror analysis beyond Inequality (3): we regard lcos (m)) (P. c)
cost (S, c)] as single entity and study how it changes as e shifts to the right from Pn-m- Let (c((c) and (c) denote the derivative of (ms) (P, c) and (os) c) respectively. Then the induced error can be rewritten as ccost(") (P, c) costtmmmmm (S, c)l < |cast( (m) (P.Pn- pn-m) ptm-m)--ost!"" -costmm (S.Pmm)) cost (S, by an extra fp. (x) (1)(z)) We can ensure cost (P, (P.r--m)
bucket-partitioning step (see Line 8 of Algorithm D. Thus, it suffices to ensure f fz((d)dr S e costt(m) (P,c).
pn m lfb(z)
A key geometric observation is that (c) equals the difference between the number of inliers in P located to the left of с and those to the right of e; a similar relationship holds for (c) For c, let m;
and m² denote the number of outliers in bucket B, relative dataset P and coreset S, respectively. By the geometric observation, we conclude that [fp(c) - (c)) I E, |m, - ml| + Bel. where B. denotes the bucket containing c. Therefore, pp-- (x) 8'g (z) de S (2 Im - mli + 2 B.))
dist((pn- c) (see Lemma D.3). Thus, it suffices ensure (E; |m - m m B() dist -istt (Pn-m: c) S e- cost. (m)) (P, c). This desired property can be achieved by limiting the size of each bucket in P PM
to be at most (En), which ensures E, Im:-- - m²| I (EE)) for all E Pas (see Lemma D.2p.
We remark that, due the misalignment of outlier counts, single bucket may induce arbitrarily large error in our analysis. However, these bucket-level errors can cancel out, and the overall error remains well controlled. To the best of our knowledge, this represents the first non-component-wine error analysis in the coreset literature, which may be of independent research interest. To demonstrate the power of our new error analysis, we apply it to the aforementioned obstacle instance-a a case that previous somponent-wise analyses cannot solve (Appendix (A.3). Coreset size analysis. Note that the coresct size equals the number of buckets. We partition Pa into 0()=1/2) buckets using the vanilla coreset construction method (37. The analysis for c Pa
and & Par results in most ((--1/2) buckets for the former and O [me-) (e- buckets for the latter.
Therefore, the total coreset size is Ō 1/2 + 1) (see Lemma 2.4
This coreset size is shown to be tight. To see this, we construct a worst-case example in Section D.6 where the m outliers are partitioned into sa e-- intervals, each containing en points, with the interval scales increasing exponentially. If the coreset omits all points from any such interval, each point within it contributes an error of (-cost(m)((.c)) resulting in a total error of 2g (ost (P, ch-chich is unacceptably large. Thus, to control the error, the coreset must include at least one point from each interval, yielding a lower bound of m c- on the coreset size.
1.2.2 Overview for Theorem
1.3 (general d)
The obstacle of the traditional component wise analysis remains in the high-dimensional case, motivating us to adopt the non-component-wiss analysis framework. However, due to the increased complexity of candidate center distribution, a straightforward extension of the ID analysis would involve using an s-net to partition the center space, as in (55, but this introduces an O(e- factor in the coreset size. To overcome this, we leverage the concept of the ball range space, as explored in previous works 9 39], which allows us to effectively describe high-dimensional spaces.
5

---

Our Algorithm 2 takes a uniform sample So of size Ö(E 3 min(==2, (onf==2.dd) dd) 2
from the "outmost" m
points of to include in the coreset, contrast to including them all as in [39 38]. To analyze
the error induced by So. we examine errors caused by nurlier-misaligned" points those that act
as outliers (or inliers) in P but as inliers (or outliers) in S with respect to a fixed c. The induced
error for each such point is bounded by rost! (oatt""(P (P.c) when
4m (see Lemmas E.3 R.4 and R.5)
TN To ensure the total error remains within ( cost (P.c). suffices for the number of such mutlir--isalligedd points to be Ossm). The key geometric insight is that this condition holds when So serves as an E-approximation for the ball range space on L (see Lemma E.6) This approximation
is guaranteed by ensuring |So| = Ö( -2 min(= 2.d3), ) as established in Lemma E.2
To our knowledge, this analysis is the first to apply the range space argument to outlier points. The range space argument leverages the fact that the VC dimension of I is at most (dd and can be further reduced to Ō(e-2) by dimension reduction. This enables us to generalize results to various metric spaces via the notion of VC dimension (or doubling dimension), as well as to robust
(k; 2) cluuttrring see Appendix and
2 Optimal coreset size when d 1
Let P = (pi.... Po C IR with p1 < <p2 <...
<. Pn- Denote [ := arg minigg////=m cost P
L, c) to be the set of outliers of P w.r.t. a center e, and p|() P - T,(e) to be the set of inliers. Let
c* := arg min.eR (mst(mm) (P, e) be an optimal center. Let L (e") and P7 p((")
Buckets and cumulative error. We introduce the definition of bucket proposed by 35 associated with related notions, which is useful for coreset construction when d
34
Definition 2.1 (Bucket and associated statistics). bucket a continuous subset {pi, {pt,Pt+3 Mt,,tt,....... , Pr of P for some 1 < 1 S S n. Let (BB == r 7-1+ - BBB) ;= Lecgp P represents the mean point of B, and 8(B) ;= Epen lp m(B) represents the N(B)
represents the number of points within B,
cumulative error of B.
A basic idea for vanilla coreset construction in ID case is to partition P into multiple buckets B and then retain a point BB) with weight NBB) as the representative point of B coreset. This idea works since each bucket induces an error at most ((B); see Lemma B. Thus, we have the following theorem that provides the optimal coresct for vanilla ID geometric median (37
Theorem 2.2 (Coreset for vanilla 1D geometric median (37)). There exists algorithm A, that given an input data set P C R and E (0, A(Pre) outputs an E-coreset of P for vanilla ID geometric median with size Ö(e-t) in O(PP)) time.
We will apply A to the "inlier subset" of P. say the set of middle n 2m points PM {pm+1..... Pn-mm .pa-t.,......mm.. ). Let P. (PI..... and Pn [Pn-m+1..... Pr J. Any continuous subsequence of length n - m of P must contain Pas, implying that all points in Pas must be inliers w.r.t. any center E IR. This motivates us to apply the vanilla method A to PM-
As discussed in Section 1.2 we then partition Pt an PR into buckets, which requires an understanding of the relative position between the inlier subset p(() and c. Define Tmax := maX Ip e²
CL c* Tmax and en c* + Timax. We present the following lemma (proof in Appendix B.2).
Lemma 2.3 (Location of p(o)). Letce PM be a center with c < e* and p/() + Pi. Let p be the leftmost point of p(c) Then dist(pi, CL) S 2 dist(c,ct).
symmetric observation can be made for c <> c*. Note that cost (m)) (P.c) > cost c) 2 0(n). dist(c, c²) 2 -di)t(i((pp ez). This lower bound for (mst(m)) (P.c) motivates us select the cumu- lative error bound for the bucket containing point as En dist(pi, cL). Thus, we partition Pt U PR into disjoint blocks according to points' distance to er. and CR, concept inspired by [37]. Concretely, PaN(-xx,cR) CR), (nn x))
we partition the four collections Pr.n(-o,, cr.), Pr. (e,,,,,,,,)
into blocks, respectively. Due to symmetry, we only define the blocks in Prn( 1zn(-o,, 00, cr.) below. Blocks for other parts follow similarly and are provided in Appendix B.3 see Figure D for visualization.

---

Your
Your
Year
7:0
8
(a)
(b)
Figure 1: Illustration of the block partition. The blue square marks the optimal solution c*, and the blue triangle denotes the left boundary of the inlier set Pi, with distance mmax dist c*). partitions the one-dimensional space left of Pa into disjoint blocks based on each point's position relative to cz: points farther than mmax form Biar, and those within 2cr form Bo-
Figure [(a)
Figure ((b)
shows the logarithmic subdivision of inner blocks ((() within distance maxx from CL.
Outer blocks (Bjar): Define B as the set of points that are far from CL. where
B L)
== (p PL (-o0, eL) dist(p, et) 2 rmax]
Jar
Inner blocks (B,): Define ((d) as the set of points that are close to CL, where
B = (p E Pr. cr)) dist(p, er.) 26Tmax)
For the remaining points, partition them into blocks By" based on exponentially increasing distance ranges for i = 1, .,.... [0og2(=1))] where
B = {p PL 2' dist(p, CL) < 2
The algorithm. Our algorithm (Algorithm(]) I consists of three stages. In Stage 1, we construct coreset Sas for PM using Algorithm A for vanilla ID geometric median (Theorem 2.2). ensuring that cSst(SM,c) E E1 cost( (as,, c) for any center e R. In Stage 2, we divide sets Pt. and PR into outer and inner blocks by Equations ( and greedily partition these blocks into disjoint buckets B with bounded 6(B) and (B) in Lines 3-6. In Stage 3, we ensure that cost (PPa-mm = cost (m))),)) (n-)) and cost (mm) (P, Pmm+1) = cost (mm) (S, Pm+1) to control induced error when & PM. Finally, we add the mean point (BB) of each bucket with weight N (B) into So, and return So U.S. USM as the coreset of P.
By construction, the coreset size |S| is exactly the number of buckets. Therefore, following lemma that proves the coreset size in Theorem 1.2] Its proof can be found in Section D.2
have the
Lemma 2.4 (Number buckets). Algorithm constructs at most Ö( + n =- buckets.
Key proof idea of Theorem 1.2 Using Lemma 2.3 we can control the error from partially intersected buckets when
PM (Lemma D.I. For PM, let m; and m be the number of outliers in bucket B; for P and S, respectively. We show that the total misaligned outliers satisfy Eiejy) |m, - mmm I en (Lemma D.2. In this case, the error is also bounded by |cost (m) (m)) c)
4
cost (m)) (S, < | Eiejy |m; ml En dist(c, PM) S E cost( (144) (P, c) (Lemma D.3. The complete proof can be found Appendix
3 Improved coreset sizes for general d 2 1
We present Algorithm 2 for Theorem 1.3 In Line 1, we construct L* as the set of outliers of P w.r.t. c" and Pj P- L as the set of inliers. We construct coresets for Pt and L separately. In Line 2, we take a uniform sample So from L* as the coreset of L* This step is the key for eliminating the O(m) dependency in the coreset size. In Line 3, coreset 5, for Pt. The coreset S' is the union of So and S₁ (Line 5). In Section generalize this algorithm robust (k:, =-llusteinn (Algorithm 3)
the following theorem by (40 construct
we show how to
Theorem 3.1 (Restatement of corollary 5.4 in (40). There exists a randomized algorithm Aa that in ((d) time constructs a weighted subset S₁ C Pf of size Ō( mmnn (E (e-2,d) ?,d)), such that for every dataset Po of size m, every integer 0 < t < m and every center E Rd,, (cost( (Po U Pi,c)
cost (Po U Sr, c)) I cost U Pi c) 2 cost(P),e")
7

---

Algorithm Coreset construction for ID
Input: A dataset {PI, ( PnJ J C E. with pl < ... < Pr. and E (0, 1).
Output: An e-coreset S
1: Set PM < {pm-11.... Pn-m), Pt. (pm.....Pm) Pn {pn-m+to .......
Pn.)
2: Construct SM &- A(PM; : 5) by Theorem 2.2
3: Compute optimal center c* of P for robust ID geometric median. Let Pf be the set of inliers w.r.t. ct, and 7max == maXpEP; dist(p, c²), et f Tmaxx CR f- c* + Tmax.
4: Given er and en, divide PL and Pn into outer blocks Byer" and B3(E)) by Equation and inner
jar
blocks U((,, B(L.R, (B and ( (0 S [logg(= by Equations
10
5: For each non-empty inner block B,, divide B; into disjoint buckets {Ba, h22
greedy way:
each bucket Big is maximal set with ((B;,) = e'rennmmax and N (B..)) S 16
6: If B/ is non-empty, divide Bjar into disjoint buckets (D 1/20 in greedy way: each bucket ((L) jar.j is maximal set with N( I
(L)
en The same for Bjar (.R))
16
7: Compute the inlier set p(pm+1) with respect to center pm+1 and the inlier set p(Pn-m) with respect to center с = Pn-m respectively.
8: If there exists some bucket B such that both Bn D)P((mii and B PPPm
(1) are non-empty, divide
into two buckets B n p(pm++) and B \ p(pm+)) Do the same thing for p(pn-m).
9: For every B, add (BB) with weight (B) into So.
10: Return + So U 5M.
Algorithm 2 Coreset Construction for General
Input: dataset C Rd, E E (0, 1) and an ((1)-approx center E Rdd
Output: An E-coreset S
1: L" +- mr: cost(P - L,c*), PT - P
2: Uniformly sample So C L' size Ō(s min { f d)). Set Vp E So, wo(p) +
m
[ool
3: Construct (SI,wr)= +- Aa(Pi) by Theorem 3.1
4: For any p E So, define w(p) = wp( and for any p E S,, define w(p) = w)()).
5: Return S + So U 1 and w;
The theorem tells that S₁ serves as an e-coreset for the combination of Pj and any possible set of outliers Po. The flexible choice of Po is useful for analysis. To estimate the error induced by So. we introduce the key lemma below, whose proof can be found in Section E.
Lemma 3,2 (Induced error of So). For any center E Rd., we have |cost (m)) (P,c) cost (So U
Pf c)) < O()) (m) (P.c).
Proof of Theorem 1.3 Fix center E Rd. Let Po So and
in Theorem 3.1 we have cost (*). By
Jcost (m)) (So U ci cost (So U St, I e. (m) (So U Pj.c) 25
Lemma 3.2 we have (cost (P. cost (mo UP e)))) < O(e) (om (P,c). Adding the two
incqualities above, we have (cost (most() - cost(()) (S,c) < O(s) (mst(mm) (P,,)))(PPe)))
The runtime is dominated by Line and Line 3 that costs 0 (nd)) time by Theorem 3.1 making the total overhead O(nd). This completes the proof of Theorem 1.3
4 Empirical results
We implement our coreset construction algorithm and compare its performance to several baselines. All experiments conducted on PC with an Intel Core i9 CPU and 16GB of memory, and the algorithms are implemented in C++ 11.
Baselines. We compare our algorithm with two baselines: 1) Method HJLW23 proposed by [39] which directly includes I.* in the coreset and samples points from Pj. 2) Method HI.LW25 proposed by [40], improves the sample size from Pf in [39].
8

---

0.09
Oure
0.12
Oura
0.025
HULW223
0.08
HJLW23
HILLWES
0.11
HILWWS
0.07
0.015
0.08
Ours
J3I.W25
0.07
255
0.005
0.04
1000
2000
3000
4000
1000
2000
3000
4003
500
1000
1500
2000
[S]
(a) Census1 1990
(b) Twitter
(c) Adult
Figure 2: Tradeoff between coreset size |S| and empirical error E(S).
Setup. We conduct experiments on six datasets from diverse domains, including social networks, demographics, and disease statisties, with sample sizes ranging from (10*) to (10%) and feature dimensions from to 68, as summarized in Table These datasets cover those used baseline (39), ensuring fair comparison. In each dataset, numerical features extracted create a vector for each record and the outlier number is set to 2% of the dataset size. To simplify computation, we subsample 10s points from the Twitter and Census1990 datasets, and 10 points from the Athlete and Diabetes datasets, respectively. We use k-means++ to compute an approximate center c*.
Size-error tradeoff. We evaluate the tradeoff between coreset size and empirical error. Given a (weighted) subset C P and a center с C R", we define the empirical error E(S,c) ==
lcost mm) (P.c) (PPe)-cos(!"))) (oset("))Sse)) where lower values indicate better coreset performance for c. difficult (ost(m))(P.))
to estimate the performance for every center. So we sample 500 centers c; Rd where each ej is drawn uniformly from P without replacement. Like in the literature [39]. we evaluate the empirical error (S5) := [ax. ((S,c;) c,). We vary the coreset size [S] from m to 2m, and compute the empirical error {SS). For each size and each algorithm, we run the algorithm 10 times, compute their empirical errors E(S), and report the average of 10 empirical errors.
Figure presents the empirical results illustrating the size-error tradeoff on the Census1990, Twitter and Adult datasets. As shown in Figures 2 our coreset algorithm consistently achieves the lowest empirical error among all methods. Moreover, unlike the baselines, which require coreset of size at least m, our method attains the same level error with a coreset size smaller than m. For example, with the Census1990 dataset, method yields coreset of size 1000 with empirical error of 0.012, while the best baseline needs size 2300 to achieve a worse error of 0.013. Results for other datasets presented in Section G We also perform statistical tests across six real-world datasets by comparing the ratio of empirical errors between our algorithm and baselines, which further demonstrates that our algorithm consistently outperforms the baselines; see Table The results show that both ě ((2)) and ((Sa)/E(Si) are consistently bigger than 1, demonstrating that our coreset consistently yields lower empirical error than the baselines. This confirms the applicability of our coreset across real-world datasets.
Speed-up baselines. In this experiment, compare the coreset of size 2m constructed by the HLLW25 baseline and coreset of size m constructed by Algorithm We repeat the experiment 10 times and report the averages. The result is listed in Table The construction time of coreset is similar to that of the baseline HL.W225. However, our algorithm achieves a speed-up over HLLW25 2x reduction the running time on the coreset), while achieving the same level of empirical error.
Additional experiment. In Section G.I
we demonstrate the robustness of our Algorithm 2 when the assumption 2 4m is violated dataset is noisy. In Sections G.2 G.3, and G.4 we implement our algorithms for the ID case, robust k-mddian, and k-means, respectively, and conduct similar experi- ments. The results show improved performance real-world datasets, even when the theoretical data assumptions are violated, further highlighting the practical robustness our algorithms.
5 Conclusion and future work
We investigate coreset construction for robust geometric median problem, successfully eliminating the size dependency on the number of outliers. Specifically, for the ID Euclidean case, we achieve the first optimal coreset size. Furthermore, our results generalize to robust clustering applications. Empirically, our algorithms achieve a superior size-error balance and runtime acceleration.

---

Table 1: Statistical comparison of different coreset construction methods for robust geometric median. The coreset S1 represents our coreset, S2 represents the coreset constructed by the baseline H.JL233, and S3 the coreset constructed by baseline HLLW25. For each empirical error ratio {(()) and ((S)))((S), we report the mean value over runs, with the subscript indicating the standard deviation.
Census1999
Twitter ((Sa)/E(S))
Coreset Size
E(S2)/E(S1)
{(S))/E(S))
((S2)/((S)
2200
3.2532.063
2.6451.458
1.7930.614
1.667p.479
3200
1.247 1.303u.60
1.251g.632
1.343o.234 1.2440.152
1.2830.
4200
1.168u.739
1.2466.148
Bank
Adult
Coreset Size
((5))
((Sa)/²(S1)
((S2)/E(S))
((S))/((51)
1200
1. 1.647a.972
1.3601.01s
1.4677.287
1.0944.542
1700
1.010 .o.100.654 1.010p.654
1.028
2. 2.1490.884
2.4161.002
2200
1.026p.674
1.089p.360
1.172u.537
Athlete
Diabetes
Coreset Size
(S2))
{(Ss)/8(S))
((S2)/((S,)
{(Ss)/8(S1)
210
5.1722.634 2.467 1.564
4.2001.944
5.7003.a03
5.8682.952
310
1.427o.660
1.5670.800
1.332
410
1.6 1.658g.s81
1.0450.449
1.3601.103
1.216p.943
This work opens several intriguing research directions. One immediate problem is to optimize the coreset size for setting. Extending robust coresets to the streaming model is valuable but challenging direction. The primary obstacle is their lack of mergeability, as outlier interactions across different data chunks prevent the compositional updates essential for streaming algorithms. It is also interesting to explore whether our non-component-viin analysis can be applied other robust machine learning problems, such robust regression and robust PCA.
I, particularly in cases where the size diverges from that of the vanilla
Table Comparison of runtime between our Algorithm@2 and baseline HLLW25. For each dataset, the coreset size of baseline HLLW25 is 2m and the coreset size of ours is m. We use Lloyd algorithm given by 7 to compute approximate solutions ep and eş both the original dataset P and coreset S. respectively. "COST,:" denotes cost(m)) (T)) (P, cr) on the original dataset P. "COST3" denotes cost (mm) (P. es) on the coreset constructed by METHOD. Tx the running time on the original dataset. Ts is the running time on coreset. Te is the construction time of the coreset.
DATASET
COST
METHOD
COST:
Tx
Tc
Ts
OURS
5.100
6.876
1.284
CENSUS1990
5.099x108
63.425
HLLW25
5.099x10
6.950
2.629
OURS
7.310x10*
3.233
0.633
TWITTER
7.307x10
41.816
HLLW25
7.307
3.259
1.278
OURS
7.760
1.427
0.308
BANK
7.815x10
16.555
HLLW25
7.7
1.477
0.677
OURS
3,412x10*
1.632
0.310
ADULT
3.418x10'
16.907
HLLW25
3.0
1.596
0.597
OURS
1,467
x10
0.320
0.055
ATHLETE
1.460x
2.92
HLLW25
1.463
x100
0.321
0.104
OURS
1.786x
0.366
0.062
DIABETES
1.781x10
3.977
HLLW25
1.788x10
0.360
0.135
10

---

Acknowledgment
[6] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: http://bbi.or//0222445///$3/ LH acknowledges support from the New Cornerstone Science Laboratory, and NSFC Grant No. 625707396.
References
[1] Peyman Afshani and Chris Schwiegelshohn. Optimal coresets for low-dimensional geometric median. In Forty-first International Conference on Machine Learning, ICML 2024, Viemna Austria, July 21-27, 2024. OnenReview.net, 2024.
[2] Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, and Jie Xue. Clustering what matters: Optimal approximation for clustering with outliers. Journal of Artificial Intelligence Research, 78: 143-166, 2023.
[3] Patrice Assouad. Plongements lipschitziens dans [1r))". Bulletin de la Société Mathmmtique de France, 111:429 :129-4444, 1983.
[4] Daniel N. Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth. In P Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 569-579. PMLR, 2020.
[5] Sayan Bandyapadhyay. Fedor V Fomin, and Kirill Simonov. On coresets for fair clustering in metric and Euclidean spaces and their applications. Journal of Computer and System Sciences, page 103506, 2024.
[7] Aditya Bhaskara, Sharvaree Vadgama, and Hong Xu. Greedy sampling for approximate clus- tering in the presence of outliers. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Infor- mation Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC. Canada, pages 11146-11155, 2019.
[8] Nicolas Bousquet and Stéphan Thomassé. VC-dimension and erdós-pósa property. Diseret. Math., (38(12))2332-2317, 2015.
[9] Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 -Nvember 3, 2022, pages 462-473. IEEE, 2022.
[10] Guilherme Oliveira Campos, Arthur Zimek, Jörg Sander, Ricardo J. Campello, Barbora Micenková, Erich Schubert, Ira Assent, and Michael E. Houle. On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study. Data Min. Knowl. Discov., 30(4):891-927, 2016.
[11] T-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Twitter data set. https://gitan comm/E/BBcccAAV/LPPPssccsAt..... center 2018.
[12] T.-H. Hubert Chan, Silvio Lattanzi, Mauro Sozio, and Wang. Fully dynamic k-center clustering with outliers. Algorithmica, 1611):171-193, 2024.
[13] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In S. Rao Kosaraju, editor, Proceedings of the Twelfih Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 642-651. ACM/SIAM. 1001.

---

[14] Sanjay Chawla and Aristides Gionis. k-means- A unified approach to clustering and outlier detection. In Proceedings of the 13th SIAM International Conference on Data Mining, May 2-4, 2013. Austin, Texas, USA, pages 189-197. SIAM, 2013.
[15] Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithus, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 826-835. STAM, 2008
[16] Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923 947, 2009.
[17] Flavio Chicrichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. pages 5029-5037, 2017.
[18] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. To- wards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1038-1051. ACM, 2022.
[19] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for Euclidean k-means. In Sanmi Koyejo, S. Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
[20] Vincent Cohen-Addad and Jason Li. On the Exee-parameter tractability of capacitated clustering. In ICALP, volume 132 of LIPIcs, pages 41:1-41:14, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
[21] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in Euclidean spaces. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 21085-21098, 2021.
[22] Jacobus Conradi, Benedikt Kolbe, Ioannis Psarros, and Dennis Rohde. Fast approximations and coresets for (k, 1)-median under dynamic time warping. volume abs/2312.09883 2023.
[23] Rajni Dabas, Neelima Gupta, and Tanmay Inamdar. FPT approximation for capacitated cluster- ing with outliers. Theoretical Computer Science, 1027:1 15026, 2025.
[24] Hu Ding and Zixiu Wang. Layered sampling for robust optimization problems. In Proceedings of the 37th International Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages PMLR, 2020.
[25] Olga Dorabiala, Nathan Kutz, and Aleksandr Y. Aravkin. Robust trimmed k-means. Pattern Recognit. Letr., 161:9-16. 16, 2022.
[26] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Lance Fortnow and Salil Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569-578. ACM, 2011.
[27] Dan Feldman and Leonard Schulman. Data reduction for weighted and outlier-resistant clustering. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012 pages 1343-1354. SIAM, 2012.
[28] Gereon Frahling and Christian Sohler. Coresets in dynamic geometric data streams. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 209-217, ACM, 2005.
12

---

[29] Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximation schemes for clustering with outliers. ACM Trans. Algorithms, 1562):2::1-2::66. 2019.
[30] Jing Gao, Feng Liang, Wei Fan, Chi Wang. Yizhou Sun, and Jiawei Han. On community outliers and their efficient detection in information networks. In Bharat Rao, Balaji Krishnapuram, Andrew Tomkins, and Qiang Yang. editors, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25-28, 2010, pages 813 822. ACM, 2010.
[31] Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pages 534-544-44 543. IEEE, 2003.
[32] Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moscley, and Sergei Vassilvitskii. Local search methods for k-means with outliers. Proc. VLDB Endow, 10(7):757-768, 2017.
[33] Mohammad Taghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, and Barna Saha. A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans. Algorithms, 1263):36:1-36:19, 2016.
[34] Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. In Joseph S. B. Mitchell and Günter Rote, editors, Proceedings of the 21st ACM Symposium on Computational Geometry, Pisa, Italy, June 6-8, 2005, pages 126-134. ACM, 2005.
[35] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing. Chicago, IL, USA, June 13-16, 2004, pages 291-300. ACM, 2004.
[36] Heesoo. 120 years of olympic history: Athletes and results. https: www.w...agl...oom com/ httpo/oooommi----ooooo------eeee 2016. Data originally sourced from sports-reference.com
tittasetsheesooo33
[37] Lingxiao Huang, Ruiyuan Huang. Zengfeng Huang, and Xuan Wu. On coresets for clustering in small dimensional Euclidean spaces. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 13891-13915. PMLR, 2023.
[38] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. Epsilon-coresets for clustering (with outliers) in doubling metries. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 815- IEEE Computer Society, 2018
[39] Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[40] Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: General assignment constraints and improved size bounds. In Proceedings of the 2025 ACM-SIAM Symposium Discrete Algorithms (SODA). SIAM, 2025.
[41] Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for Euclidean (k, z)-clustering, In Bojan Mohar, Igor Shinkar, and Ryan O' D'Donelll, editors, Proceedings the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1594-1604 ACM, 2024.
[42] Shaofeng H-C Jiang and Jianing Lou. Coresets for robust clustering via black- -ox reductions to vanilla case. In ICALP, 2025.
[43] Michael Kahn. Diabetes. http:///bi.nng//022444///15599
UCI
Machine
Learning Repository.
DOI:
13

---

[44] Samir Khuller, Robert Pless, and Yoram J. Sussmann. Fault tolerant k-center problems. Theor. Comput. Sci., 242(1-2):237-245, 2000.
[45] Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. J. Comput. Syst, Sci., 62(3):516-527, 2001.
[46] Chris Meek, Bo Thiesson, and David Heckerman. Us census data (1990). UCI Machine Learning Repository, 2001. DOI: http://loi.rr//1122333//cVv/
[47] S.
Moro, P. Rita, and P. Cortez. Bank marketing. UCT Machine Learning Repository, 2012. DOI: https:///oi. org//////oooo/// 10. 2..2442//533066
[48] Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in Euclidean space. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Anmual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26,
2019, pages 1064-1069. ACM, 2019.
[49] Debolina Paul, Saptarshi Chakraborty, Swagatam Das, and Jason Q. Xu. Uniform concentration bounds toward a unified framework for robust clustering. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang. and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 8307-8319, 2021.
[50] Vladimir Shenmaier. A structural theorem for center-based clustering in high-dimensional Euclidean space. In Giuseppe Nicosia, Panos M. Pardalos, Renato Umeton, Giovanni Giuffrida. and Vincenzo Sciacca, editors, Machine Learning, Optimization, and Data Science 5th International Conference, LOD 2019, Siena, Italy, September 10-13, 2019, Proceedings, volume 11943 of Lecture Notes in Computer Science, pages 284 295. Springer, 2019.
[51] Vladimir Shenmaier. Some estimates the discretization of geometric center- problems high dimensions. In Yury Kochetov, Igor Bykadorov, and Tatiana Gruzdeva, editors, Mathe- matical Optimization Theory and Operations Research, pages 88-101, Cham, 2020. Springer International Publishing.
[52] Vladimir Shenmaier. Approximation and complexity of the capacitated geometric median problem. In Rahul Santhanam and Daniil Musatov, editors, Computer Science Theory and Applications 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pages 422-434. Springer, 2021.
[53] Adiel Statman, Liat Rozenberg, and Dan Feldman. k-means: Outsies-resistant clustering+++ Algorithms, 13(1))311, 2020.
14

---

Contents
Introduction
1.1
Our contributions
Technical overview
1.2.1
Overview for Theorem
1.2
1.2.2
Overview for Theorem
1.3 (general
2
Optimal coreset size when
3
Improved coreset sizes for general d
Empirical results
5
Conclusion and future work
Omitted details Section
17
A. Formal definition of coreset
17
Other related work
17
A.3
An illustrative example for the obstacle of Inequality (3)
18
Omitted details in Section 2
19
B.1
Property of buckets
19
B.
2 Proof of Lemma 2.3
19
B.3 Complete definition of blocks
20
Justifying the selection the optimal center
20
Proof of Theorem 1.1; coreset lower bound for robust geometric median
20
Proof of Thherrmm 1.2; optimal coreset size for robust 1D geometric median
D.I
Proof of the upper bound in Theorem
21
Proof of Lemmal2 2.4 4)
Number of buckets
22
D.3
Proof of Lemma
D.I
Error analysis for E PM
22
D.4 Proof of Lemma
D.2
Number of misaligned outliers
25
D.5
Proof of Lemma
D.3
Error analysis for & PM
26
D.6
Proof of the lower bound in Theorem 1.2
27
Proofs of Theorem 1.3 d 1) and extension to metric spaces
28
Proof of Lemma 3.2 induced error of So
28
Extension to other metric spaces
35
Proof of Theorem 1.5; robust (k, 2 cllustrrig
36
Result for robust (k, clustering
38
F2
Proof of Lemma
7 Induced error of So
38
15

---

Extension to other metric spaces
40
Additional empirical results
G.1
Additional empirical results for robust geometric median
G.2
Empirical results for robust 1D) geometric median
42
G.3
Empirical results for robust k-median
43
G.4
Empirical results for robust k-means
45
16

---

Table 3: Comparison of the state-of-the-an coreset size and results for robust geometric median and robust k-median IR Robust h-median is a generalization of robust geometric median; see Definition F.I when 1.
PARAMETERS d.k
PRIOR RESULTS
OUR RESULTS (ASSUMING 4m)
((m) + O(E
40
Ö +
THEOOEM
d=1 -1 b
Ó ) 4 VANILLA SIZE
((m)) 33
91s
(THEOREM 1.2
((m) + O min(E
0 2 min 2, d)) (THEOREM 1.3
d>1
h ==
0(me VANILLA SIZE 42
Ais + + =) (THEOREM 1.2
((m) [39
((m) + 0
Ötk - ( (THEOREM 1.5
d>1
k>1
O(min [kms "
mm (mm==²)) VANILLA SIZE
UNDER ASSUMPTION L.4
[2m) [39
A Omitted details in Section
A.1 Formal definition of coreset
In this section, we define the coreset for robust geometric median. For preparation, we first generalize the cost function cost (m) to handle weighted datasets.
Definition A.1 (Generalized cost function). Let be an integer. Let S C Rd be weighted dataset with weights w() for each point E S. Let wSS) = Epes w(p). Define collection of weight functions W = {w' : S R+ Epes w') = w(S) A vp E S, w'(p) S w(p)). Moreover, we define the following cost function on S: Ve Rd, (m) == minweww Epes w/ w()). dist(p,c) c).
Intuitively, to compute cost(m) (S, c), we find a weighted subset S' with total weight w(S) m that minimizes its vanilla cost to c. Thus, this (m)) c) serves as the cost function for robust geometric median weighted set. Note that for the unweighted case where w(p) for all p E S, this cost function reduces to that in Equation (T]
Next, we define the notion of coreset for robust geometric median.
Definition A.2 (Coreset for robust geometric median). Given a point set P C Rd size n 2 1, integer m > 1 and
(0, )), say weighted subset S C P together with weight function w S + + is an g-coreset of P for robust geometric median if w(S) n and for any center E IRd, cost (S,c) E {11 + E) cost (m) (P.c).
This formulation ensures that the weighted coreset S provides accurate approximation of the original dataset P's cost for all centers c, within a tolerance specified by e.
A.2
Other related work
Coreset for robust clustering, A natural extension of robust geometric median is called robust (k, =)-
Clustering, attracting considerable interest for its coreset construction techniques in the literature [27
38
53). In early work, (27] proposed coreset construction method for the robust k-median problem, which requires an exponentially large size (Is + m) m)))0k+))) 'dlog Recently, [39
39
improved the coreset size to ((m) g 33-22 2) via hierarchical sampling framework proposed by [9. Following this, 40 further improved the size to ((m) + 5 22-22).. More recently, 42 proposed new coreset of size Omin (kme me 2= 2=1) + Vanilla size. We give Table to compare theoretical results with prior work.
Coreset for other clustering problems. Coreset construction for other variants (k: z) ( Clustering problems has also been extensively studied, including vanilla clustering 335 16
26
9
18
19
37 41 capitalized clustering 99] 20), fair clustering [17 and fault-tolerant clustering
44
Specifically, for vanilla (k, zlccutttgiing recent advancements by [19 [8 produced coreset
17

---

of size Omin ke= - 2))) When E 2
k ボे2, the coreset upper bound ke- is shown to be optimal by recent breakthrough [1]. Furthermore, recent study [37 has investigated the coreset bounds when d is small.
A.3 An illustrative example for the obstacle of Inequality 3
Recall that we partition the input dataset P C R into disjoint buckets {Bi,.... Br}. constructs representative point 1(BB) with weight [B,] for each bucket and takes their union coreset
of P for robust ID geometric median. Also, recall that prior work [39 40 use Inequality (3)
for error analysis, i.e., for any center R and any tuple of outlier numbers (m.....; my. with Eierry m4 m,
Σ RE
ccost (m)) (B,, - (IB:) - (m.))mm.ts((((BB).......)))))))) c) < & cost (Tr) (P,e).
(7)
In this section, we provide an example in which this incquality only holds if |S| = 92(m).
Construct the dataset P as follows: for i I,.... m. pi f;= for n - m + S i n, = (23((=))m) We show that the Inequality (7) only holds if each pj forms its own isolated bucket. Assume, for the sake contradiction, that there exists bucket B3 = (P.....PPp pp} such that [B, > 1 and j > nl m..
Case 1: If i (pi....,Pr. .r. Pr-mm Thus,
m. let 0. Then we have that the inlier set with respect is p/()
cost (m) (P,c) cPs((Plo) .c)
Let mi = =...= Mg-1- = 0, mg = - n + m and m. = |: for g + StS T. We have
Σ
(most(mu) (Bi, - -[BBB] - (.,))dist(u(BB),c)))
Icost (ma) (Br) c) ([B,1 (B)))
(lBg) - -ma) m(B,) -
(cost (m)) (Bqr c) I cost
cost (m) (P,c) < nn)
11 BB))) n
(1Bpl i 1, S m)
EpeB, Byl
n
n
8 cost (P,c), which leads contradiction with Inequality 7
(cost (m) (P,)) <n)
(cost
Case 2: if n m, let = P Then p(c)
In this case, we have d(p.p:) S (n -m)- -n 30mm)+m)
cost (m) (m) (P,c) Σ
PEP
Note that Bg 0 p(()) = 1, which means |Byl - m2 = 1, then we have
cost (m:) (Bi, - (lB.) - m. (m)
*E[T]
loost (m²) (By ((Byy m.))dis((((Ba)..)
dist(u(B,),c)
(most (By dist(pi, c) = 0)
EPEB, P
Byl Pi
(nr 2-2-1 1) E cost! (P,c),
n 366 3()mmmm).
S (n m) .n n (i-
18

---

which leads to contradiction with Inequality form a separated bucket.
7 Overall, Inequality
7 does not hold if {py} does
Non-component-winn analysis breaks the obstacle. We then show how to adapt our new non- component- wise analysis to this example, which allows more careful bucket decomposition. The key is that in our analysis, the induced error of the aforementioned bucket B3 = (p....., .......,,;,,..... with j > n is O, due allowing the misaligned outlier numbers in each bucket. Below illustrate the above two cases.
Case 1: If S m, 0, then only the bucket By may induce error. Since j > m,
have Pj 2 n thus
(B,)) = E EE P |Byl -=1 n22
n²
max dist(p, c).
pEp
Therefore, Bg will be totally regarded as an outlier which induces error, thus cost (S,,c) cost (P. c).
Case 2: if > n m. c = Pt, then p(c) = = 1pi-ntm-1....-1 pr). Let the bucket B, = {pt,.... ,Pr) with 1 Si n + m 1, 2 Therefore, only the buckets Br. and B, may induce an error. For B,, we have dist((((,,)... c) > (n² L)dist((1.c) c). thus Bg induces 0 error. For BL. the induced error is bounded by en n 3(4 (afi-n--n m) < cost(m) (P, c), since, in our framework, the size of each bucket in P PM is restricted to at most (En). In summary, the total error is bounded by cost (T)) (P)
+ 1 denote the leftmost bucket containing at least one inlier.
Thus, non-component-wee -wise analysis significantly reduces bucket-wise enrors in this example, which crucial for proving S is a coreset.
B Omitted details in Section 2
B.1 Property of buckets
In Section 2 we introduce useful notion called bucket. The following lemma shows that the coreset error on each bucket B is bounded by 8(B). Recall that cost c) = Lpe n dist(p, c) for any point set B C RR and center c E IR.
Lemma B.1 (Error analysis for buckets 34
Let B {pr, .......p............... pr} } C for 1 <15r5 S be
bucket and c R be a center. We have
1. if E (Pt,Pr), (cost(B,c) c) (BB) dist(p B3, c)l s 8(B);
2. if c & (pr,Pr), |cost (B) dist(u( (B), 0.
B.2 Proof of Lemma 2.3
Proof of Lemma 2.3 We prove the lemma by contradiction. Suppose there exists center c Pa
satisfying that e < c* and p(c) + Pj. and the leftmost point pj of ple) satisfies dist(pi, CL) > 2dist(c, )* Then by the assumption of c, we have pt CL, thus pt Pr. For any points p in P?.
we have
(p, s dist e²) + cc)
(Triangle Inequality) (Definition of rmax) (dist(pi, > 2dist c*))
S Tmax + dist(c.c')
Tmax + dist ct) dist(c, c*)
(pt.
This implies that any point in Pj must be in p(o) However, since PPl cannot contain any other point not Pt. This contradicts pt & Pj. Thus, dist cr.) S 2dist(c, c*) holds.
- m. p(()
0
19

---

B.3 Complete definition of blocks
Now we provide the complete definition of blocks, which are used in our algorithm I Recall that Ymax = In 1p - c*1, cr. = Tmax and c* Tmax- Then we divide the sets Pt. and
PR into disjoint blocks as follows:
Outer blocks (Bjr): Define B/(r) and (( Jur as the set of points that are far from CL and cR. where
B/(r = { dist(p, et) 2 Tmax } B {p PR (CR, (pst cR) 2 Tmax }
(8)
Inner blocks (B;): Define _ Bi (LR), t and ((RL) as the set of points that are close to er, or CR. where
T0th = {pe Pt. (-oo dist(p, er.)
< 22r }
B(LB) {p Pt. (c) dist(p, ct) < 28Tmmx }
(9)
R) B {p PR (cn 00) dist(p, en) < 2ET }
B (RL) = {p PR n (-,, dist(p, en) < 22r
For the remaining points, partition them into blocks B,Ld, ((LB), B!n)) and ((RL)) based on expo- nentially increasing distance ranges for = 1....., [log (E 1) where
Bl4) = {pe E P et.) er I dist(p, ez) < er 2
B(LR) = {pe E Pr. n [cr,, oo) 2' er Vara S dist(p, Cr.) < 2 ermmx }
(10)
B(R) = =pp E Pn (cn. 20) 2 D'ermax S dist cn) < 2r }
B(RL) { PR (-00, cal 2'eTmax dist(p, < 2 }.
B.4 Justifying the selection of the optimal center
In previous coreset constructions [39 it is hard to obtain the exact value of optimal center c², so an approximate center is generally used instead. However, when d = 1, P1 is always continuous subsequence of P. Suppose Pj {pt. .......... . P.). we have e* Pt كهي J. This indicates that P7 and can be computed in polynomial time in robust ID geometric median. Additionally, computing an app)aappronnnation of c* is also sufficient for our algorithm to remain valid, which only results in factor of (11) difference in the coreset size.
C Proof of Theorem 1.1 coreset lower bound for robust geometric median
We first construct a bad instance P {pi. .P......PP... .P.) C. R, where p: for E [m] and pj x for < < n1, -> 20.
W.L.o.g, we assume m is m
number and < (m 1)/2. Suppose (S, w) e-coreset of size [|] < T[ for robust geometric median on P. Define S == S (pm41...., Pn. and
So = S n (PI..... ... Pm There exists 2(n m) consecutive points P:-1: .... Pi. Pi-2(P----- (5-2(n-m) m) not in S for some E (m- 2(n m)]. Let the center i (n m) 1 Then we have
1 cost (m) (P,c) = 2((
2
+
1
+ 1) +
+
15 2
+ n
2
1))
(11)
< (n- - (n-m)
2
We claim that w(So) + (((()) m (1 E) (n-m) Fix center c' - x + 1. If w(S)) > m,
we have cost (P,c) P2c') and cost (m) (S, c') + co, leading to an unbounded error. Therefore
20

---

we only need to consider the case w(So) S m and our claim can be verified by as follow:
cost (m) (S,c') wr(S)) m + w((r) cost (m) (P,c)
+ (1
(12)
n - m
By this claim, we have cost (m) (S, N
(n - m + 0.5) .) (w(SS) )+ + w(I)) - m)
M MAW
E) (n 0.5) (11 (1- (1-E) (n m) (n m)
(Inequality
12
(1 +E)
(0 0.5)
(1 + cost (m (P,c)
(Inequality
II
In summary, we have (o c) 2 (1 + E) (P, c)) which contradicts the definition of e-coreset. We conclude that, each E-coreset of P is of size 92( _)
D Proof of Theorem 1.2: optimal coreset size for robust 1D geometric median
In this section, we provide the complete proof of Theorem for both upper and lower bounds.
D.1 Proof of the upper bound in Theorem 1.2
Now we show that our coreset S obbaained by Algorithm I is an E-coreset of P.
In the following discussion, we define 5 and S as follows. Given a weighted set S of total weight and center e E IR, let s(c) == arg min cs ,efo w(s)=n-m cost(s}) c) be the set of inliers
of S, where w=s)) represents the weight of s in sfc) and at most the weight of a S. Moreover, let Sj represents s(("), which exactly contains every (BB) of each bucket B in P7 with weight [B].
First, we consider the case that c E PM- Note that regardless of the position of c, at most three buckets can induce the error: the bucket containing and the buckets containing the endpoints of p(c) on either side. Actually, the coreset error in Pas is already controlled by the vanilla coreset construction algorithm A. Thus, we only have to consider the cumulative error of the buckets that
partially intersect with p( on either side. We will show that this error is controlled by the carefully selected cumulative error bound of each inner block. Moreover, we adapt the analysis for the vanilla case in 37 to the robust case, as shown in Lemma D.I This allows us avoid considering the error caused by the misaligned outliers in P and S, which still suffice to ensure that the coreset error is bounded. The proof of Lemma D.I is deferred Section
Lemma D.1 (Error analysis for E Pas). When center e (Pm+1: (oost, (m,(())))))))))))))
cost (mm) (m,) c)l < e cost (m)) (P..).
Now we analyze the case that e is not in Pas- Assume is divided into disjoint buckets B By from left right. Fix a center E IR, for each bucket B, (i [q]), define m, [B; \ p and
m2 ;= BB s(C) which represent the number of outliers in B, with respect to Obviously we have Σ, m, = -, m² m. The following lemma shows that the number of inliers in each bucket for pfc) and s(c) remains roughly consistent, which indicates that (mm) (mn) (P,cc c) and cost(mm) (m)) (S,c)
increase almost equally.
Lemma D.2. For any center E R. Σ lm,- mll <
vElgi
Let == suP.ER Σ |m; m/]. then we have r kE[g]
< Em For e & PM, we consider the derivative
of the cost value with respect to and gives upper bound of the induced error in Lemma D.3 Combined with the upper bound of T, we conclude that the induced error O dist(c, c*)), which is bounded by O(e)- fmst e) obviously. The main idea similar to that of the proof of Theorem 2.1 in 377, We defer the proof of Lemma D.2 and D.3 to Sec D.4 and D.5 respectively.
21

---

Lemma D.3 (Error analysis for e & PM.. When the center S Pm+1 OF 2 Pa-m- coot (m) (P.c)-
cost!m) c) & (T + $ (e, PM) S cost (1)) (P.c).
Now we are ready to prove the upper bound in Theorem 1.2
Proof of Theorem 1.2 (upper bound). Given a dataset P of size n, we apply Algorithm to P and obtain the output weighted set S. By Lemma 2.4 Algorithm [ divides P into Ö + m g-
buckets. Note that S contains only the mean point p(B) of each bucket B. Thus we have "s
(0=++m=-1) t) Combined with Lemma D.1 and D.3 we conclude that is an e-coreset of
For the runtime, Line 3 cost ((n) time to obtain the optimal center. Recall that P/ = {pr..... Pp} is continuous subsequence of P and C* = - J= since we only consider the one-dimensional case. Thus, we can compute P/ and e* in ((n) time, since we can sequentially replace the leftmost point in the current inliers with the next point from the outliers, and the resulting cost difference can be computed in ((1) time. Lines 4-6 cost ((n) time, since we can sequentially check whether the next point can be added to the current bucket, otherwise, we place it into a new bucket. Obviously Lines 7-8 also cost (nn time. This completes the proof.
D.2 Proof of Lemma 2.4 Number of buckets
Proof of Lemma 2.4 Note that Line 2, the number of buckets Ō(E=)) in Sas by Theorem 2.2 For Line 4, there are at most ((log(E)) non-empty blocks. For Line 6, the constraint on (( generates most 0 11) buckets. For Lines 7-8, there are O(1) new one-point buckets.
What remains is to show that each non-empty block contains Ö(E- + = buckets in Line 5. Note that each block contains at most m points, thus the constraint on N ((,))) generates at most ( buckets. Thus we only have to consider the constraint on 5( (Bt)).
Suppose we divide inner block B, into buckets (Bijhsss due to controlling 8(Big)) Since
each Biy is the maximal bucket with 8 (B.,)) I nrreanmmas we have ö(B,, U B++1,) > pr
288
288
Denote B, U B5 by C2 for j E (1..... 1 Let (en(B) = maxpeB P minpe P be the length of B. Note that 8 (BB) N (B) len ()) holds for every bucket B. Thus have:
m2 mTax 2 (B.) (B)
(N(B.) < m,len(..) < 2'ET "TTax)
1
|
2 (CC))
Σ
Jcyl
j=1
j=1
N(C,)
(Cauchy-Schwace Inequality)
(13)
[
2 C 8(
j=1
(1 t
1)2
2 8 2 max
288
So we have (1 )22 2 2 m22 mamax which implies S O(E-t). The proof above is similar Similarly, it is trivial to prove that Bd also satisfies the above inequality. non-empty blocks, the constraint on 5 5(B:,) generates at most Ō buckets. Thus Lemma holds.
288
to Lemma 2.8 in 40
Since there are O Olog
D.3 Proof of Lemma
D.1 Error analysis for c E Pas
Proof of Lemma D. Let Lo PLOL" Ro PR L*. Recall that L denote the set of outliers w.r.t. the optimal center e*. W.I.O.G, assume > ct, thus p(c) To = 6. Next, we analyze the induced error in two cases, based on the scale of dist(c, c²). When ermax dist(c, c² ).), the center
22

---

is sufficiently close to c², so cost cost(m))(p (P.c) = cost cost(m((P,c").. resulting in a small error. When efmax dist(c,c'), we have cost (m)) (P. c) > Q(n dist(c, ct)) M(EnTmax) which matches the error from any outierr-misllined bucket B, whose error is at most (den)(dist(e, e*) + ET @Tmax) by Lemma 2.3
Case 1: dist(c, c*) > Tmax-
If P/ nRo 0, then we have p(c) = P7, s(c) = SS In this case, we directly have cost (m)) (S,c) E
(1 + e))ost (P, c) by Theorem 2.2
Next we assume p( n Ro + 0. Same the above lemma, denote the leftmost and rightmost buckets intersecting Pl as BL. BR. respectively, Recall that the coreset constructed by A(PM 5)
SM. By Theorem Algorithm A ensures that
|cost(SMs,)) cost(oos c)l & (ost(PMs, < cost (P,c).
Next, we bound the cumulative error of By and BR- Define y := max(0, [log( distt/_e"" )1). Obvi- ously 6 maax I dist(c, c²) < Tmax, thus y E [0, [log(==1)] 1). By the definition of y we have dist(c, e*) S 22+ max. Denote the rightmost point of Bn as Pr, then it follows that
2e.rimax
dist(pr, cR) S 2dist(c,
(Lemma 2.3
I 27+2 Ermax-
(dist(c, 6*) S 2 eTmaxx
Recall that block B²40) {p PR 1 p> en, 2' 8f max dist en)
22+ max) So the block any bucket Big in inner
B, which contains bucket BB satisfies
S 7 + 1. By Line 5 in Algorithm |
block B, satisfies 8(B,)) s
2 Thus, 288
2 e
8(BR) I
288
Similarly,
21+1 g nurmmx
5( 5(Br.) <
288
Note that at least 111 points are on the left of c², among which there are at least (!"-m" m) inliers w.r.t center Moreover, when y O, we simply have dist(c, e*) > 2Termax by the assumption; when 7 > 0, we have dist(c, c*) > 2" ETmm by the definition of y. Thus,
cost (m) (P.c) 2 (1 n - m
"] m)- dist(c.e")
dist(c.
(n 2 4m)
(14)
27 VenTmas
2 2T
(dist(c,
48
Now ready to prove goal (m)) Ejetg m,)) dist(j((B)),)) cost (m)) (P. c). Recall that my := [B \ pf()) for each bucket By. Thus for each bucket B, that is
between Bt and BR. have m, 0; for By and BR. have B1] my |Br n p(e) and
23

---

Bal mg = |BR 0 p/0). Then we have
Σ
[1yy] mz) (1stt(((B)))))
jE(g]
< ()) cost) c)1
Σ
dist ((B.)) +
Σ
dist(p; (BR))
pEB,nR
PEB
(Triangle Inequality)
$ |cost(SM, c) cosssssMMM.. + ((L)) + 8(BR)
(Definition of (BB)
2 e max
8 cost (m) (P.c)+
3
72
Se (m)t (P,c).
(Inequality 14
Thus by the definition of s/
cost (m)) (S,c) - Σ (IB)) 10mmmp1 m,) dist(u(B,),c) < (1 + e)cost!!! (P, jE[n
Morcover, is easy to prove that the rightmost block By intersecting with s/ still satisfies S 7+11 Thus, similarly to the previous discussion, we have:
cost (m)) (P,c) (1 + e) e)oost (m)) (S,
Thus cost (m²) (m), E (1 (m) (m)
Case 2: dist(c, S Tmax
Let Wh := E EpepfOipp w(p). Consider the points in p(() P7. we have:
5
cost (m) (P,c) wi(Tmax dist(c, c²)) 2 (1 Wrr Wrrmax
W.Tmax
(15)
6
Thus,
cost (m) (P, c) cost( (
c) cost (p/s(( c),c)
2 cost () 2wn c),"
(Definition of w))
2 cost((f,
6
Wi maxx
(16)
3
2=
> cost(Pp c)
cost (m²) (P,c)
(Inequality 15
5
By the definition of cost (m)) c), we have
cost (m)) (os) (P,c) S cost(Pt,
(17)
Similarly, have
2s (ast(St,c) - cost (m) (S, & cost (m) < cost(S;, c).
(18)
By Theorem 2.2 Algorithm A ensures that (Sos((Su: c) cost (PM, c)l < to the definition of the block Bo, obtain that there is bucket that partially intersects with Pf. Thus,
3 -osst c). According
(cost(St, cost ( (P; c)1 (Sost(SM, c) - cost (PMr,C)
cost(PPp (Pas: c)
(19)
cost(P?,c) c).
24

---

Combining the above equations, we have
cost (S, < cost((i,,))
(Inequality 18
< (1 + &
(P,st(P),c)
(Inequality I9
3
25
< (1 +
(1 + cost(mm) (P,c)
(Incquality
3
5
< (1 cost (m) (P,c).
Similarly we have cost (mst < (1+e)cost( (m) (S, thus cost (S,,c (1=t) cost(mm) (P.c).
D.4 Proof of Lemma D.2: Number of misaligned outliers
Let p|() {pr,... pi+ Assume E Bμ and P1+n-m-1 E BR. Consider a point py E PL that satisfies dist(p,, c) < dist(p)+n-m- e) and (ist(((BB), > dist(u(B"). c), where pj B and Pj-n-m B'. Next we show that the total number of points satisfying the above conditions is at most (En),, which also provides upper bound for Σ m, m4l-
Proof of Lemma D.2 Note that for any center c, p| is continuous subset of size
In this case Py E p(o) By the definition of p()) we have j 2 L. If + Bt, and B' + BR, then by j 2 I, we have uBB)= max(Br.) and v(B') max(BR). Then we have
dist c) 2 (mixt(max(B)))
> dist(u(B),c) > dist(p(B'), > dist(max (aatma)aBBB... 2 dist(pf+n-m:.)
which contradicts the inequality dist(p), c) < dist(p)+n-m- c). Thus, either B = By or B' = Br holds. This indicates that the total number of points satisfying the above conditions is most [Bz] Bxll- Formally, denote ( as the bucket containing Pt, have
I Σ jE(m]
Tep pfo) dist(u(BB))) > dist(u(Bbtaam))... s S1B B|Bl++IBA |BRl-
(20)
Symmetrically, consider the points in PR, we have
Σ
U(p E pf dist(u(BU-n-mm) < dist(u(B())) s |BB + |BRl
(21)
je|n-m+1,n]
Since IP(()
m. for any i m). exactly one point in (pr. (pi.Pitn-ml) } is in pf This means
that E p(() if and only if Pitn-m & plo) Thus, Inequality 21 is equivalent to the following form:
L
Σ Hee & pfo dist(n(B()),,) < (astuu(UUn-m)).. e)) s |Byl + BBll jE(m]
(22)
Moreover, we'll show that 1, and L2 cannot both be greater than 0. Suppose 1, > 0. In this case, there exists point Pj E n pfo) such that (ist((((B))) > dist(u(B((+s-mm)) c). Consider point py E PL p obviously j' <. Then we have
+n-m) dist(p((B6)) ) > dist(u(BB))), c) > dist(u(B(itr=m)) c) 2 dist(u( (('(mu)))) c).
Thus 1g O. Conversely, it still holds due to symmetry. Based on the above analysis, we have
1 + la B& [BR]
(23)
25

---

By Ps E pf =
Pitn-m pfo. it is easy to prove that Σ|m, Im m/; in PL and PR are exactly
the same. Then it follows that
m, mll =
m ml]
B.
Σ
Σ I(ps E EP(O) I(dist(u(B:),.) < dist(u <dist(u(B(itann))) ),))
=2
B. P;EB:
2 2 Σ
I(ps E p/()) - I(dist(((B)),, c) < dist(u (ast(u(((tamm)).00
%E/m]
$ 2(I + 12)
- 2( By + [BRl)
(Inequality 23
En
(IB) - E7
- 4
16
D.5 Proof of Lemma D.3: Error analysis for & PM
Proof of Lemma D.3 W.L.O.G., we assume that 2 Pn-m- Recall that Pis divided into buckets BI...., Bg from left to right. Suppose Be (t E [4]) contains the center c, i.c., minpe P S c S ma B, p. We define function Sp(c)= (os)(m)) (P.c) and [s(c) = cost (mm) (S, c) for every E IR.
Note that fp(c)= = fp(Pn-m) + fp.- f1(x) and fs(c) = fs(pn + fpa- (x) holds for any > Pn-m- Next, we first show that (p(pn-m) fs(Pn-m) by Line in Algorithm 1 Then verify that (c) [c) is bounded by Σ |m; - mf], which suffices to prove the lemma. The
<E(n)
main idea is similar to that of the proof of Theorem 2.1 in 37
By Line 8 in Algorithm there is bucket that partially intersect with p(Pn-m), In this case, for each bucket B C P(Pa-m) dist(u I max per) (mm dist(p, c); for each bucket B & p(Pn-m)
dist(p(B), ()) max P dist(p, c). This indicates that s(mn-m) contains ((B) with weight PEP/
[B] for each B p(Pa-m), which maintains consistent weights with p(Pe-m), Then by Lemma B.1 we have J fp((n-m) = [s(pn-m.) Note that (c( is a linear function of c, and we have
[p(() 11p1 p pfc) p c) Kp p E p(o) p c)l = - m.) + [B, - B, (c, - E(B.)) - mm.) 13t
Similarly, when (BBB)) < c, we have [c(() = Eie( m{) + BBl Eis(( m(); when
((B)) > G, we have f'((c) Exce - m() - Bal - Ei>e - m(). Thus
- [s(c]] S Σ mm mii + + B,l
< r + 2 B,
(Definition of T)
en
B < En
< r +
8
16
26

---

[o
g [
[Til
[T]
m
[T]]
m
20
m
Figure 3: A case for demonstrating the coreset lower bound for robust ID geometric median. T; contains m points where each point p E T; satisfies = m To contains the remaining points where each point p E To satisfies = O.
Then by fr(c) fP fpn 8b(()) de and fs(c) = (s(pn-m) + +he f's(2) dr, we have
(sp(c) - fs(c)] = [p(Pn-m) + f fp(x) de - is fs(Pn-m) - -fe pp-m f's(o) do
pn-m
fp(x)) - (1)( do
(fp(Pn-m) = (s((n-m)
15p(z) - f35(z)) de
(T + sn
da
8
Pa-m
( en
Pn-m)
+ r)
+D) dist(c, PM).
(Definition of PM)
Moreover, since |Prl = m, at least n 2m inliers w.r.t are on the left of Pn-m- These points satisfy that dist(p, ,, c) > dist dist(pn-ma c), which implies that cost(m) (P.c) 2 (n - 2m) cist c). Then have
lSp(c) [s(c) < (c Pn-mm) ( +D) +
< 3mn
(c pn-m)
(Lemma D.2)
8
< e(n 2m)(e (c- Pu-m)
(n 2 4m)
cost (P, (P,c).
This completes the proof.
D.6 Proof of the lower bound in Theorem
1.2
Next we show that for n 2 4m, the size lower bound of e-coreset for robust 1D geometric median (2== + n m-- This lower bound matches the upper bound the above discussion, which completes the proof of Theorem 1.2 In the following discussion, we assume that the size of dataset P is sufficiently large such that En 1, which holds in nearly all practical scenarios.
Proof of Theorem T.2 (lower bound). For vanilla ID geometric median, 26 shows that the size lower bound of e-coreset 2)== which is obviously also the coreset size lower bound for robust ID geometric median. Thus, it remains to show the coreset size is 92( c-!) when > eà.
We first construct the dataset P of size n.. Let = L The dataset P is union of 1+g disjoint sets (To, , J. For each i E (I,..., 4). T; contains L points, and every point E T; satisfies p ma where a 2 + (s (s) To contains al points where each point p To satisties p 0. Correspondingly, define q disjoint intervals {4,..... 14). where 1, [m (f-)a+++ m ma-1].
J.
27

---

Suppose S is a E-coreset of P with size |S| < q. Then by the pigeonhole principle, there exists an interval 1 (j E ()) such that S does not include any points located in 1z. This implies that for any point p E S, we have p - mnUi-)aat or p 2 maa+1 Fix the center e = m then we have
cost (m) (S,
(n m) min ci
pES
(n m) (mj m 1)
(S 0)
[[1 m m' " m|m
> [[1 ²²)n - -m]me
(a ( 2 + log (s-
> [[1 E - -2a²)n )n + EN - m m
(e 1
(1 {11 22)n (m 1)]m
Since n 2 4m, we have Tol = n -
|m
2 n - m. Consider the points in To and Tÿ as inliers,
we have
cost (m)
(P,c)) S (Tost(Tj00) + (n- m
[Ty Dmm
m l)maa
= (n m -
(Definition of T2)
S (n m
+ 1)
q
S [(1 28)n (m 1)]m²a
(Definition of q)
It follows that (0)) > (1 + s)oost (m)) (P, c). thus S is not e-coreset of P, which leads to contradiction. This implies that any e-coreset of P contains P2 m. s-1) points when > et.
Considering the discussion above, the lower bound of the coreset size is Q + me-
Note that the dataset P we construct is a multiset, which is slightly different from the definition. However, this does not affect the proof, because we can move each point by a sufficiently small and distinct distance, making the cost value almost unchanged.
When 1, consider a trivial method that applies algorithm A on PM and keeps all points not in Par- It's easy to prove that this method constructs an e-coreset of the original dataset under the assumption. In this case, the coreset size is Ö(E= + m), which matches the above lower bound.
show that the coreset size is l2== 1 + m) by the above discussion. Moreover,
E Proofs of Theorem 1.3 d N 1) and extension to metric spaces
In this section, list out the missing proof in Section 3 and show how extend Theorem 1.3 to various metric spaces.
E.1 Proof of Lemma 3.2 induced error of So
Below we briefly introduce the proof idea. We first observe that the induced error of So is primarily caused by points that act inliers in P but outliers in S, or vice versa, shown in Lemmas E.3
and E.4 The error from a single point is bounded by O O( (oae (see Lemma E.5. The next task is ensuring that there are (em) such points in So, which guaranteed when So provides an e-approximation for the ball range space on L (Lemma E.6). To achieve this, we sample (dds²²)
points for So (Lemma F.2)
Fix a center c E I Let [(c) == arg mig cost(P L, c) be the set of outliers of P w.r.t. and mp |L* n [((e represent the number of these outliers contained in Lt, For So U Pf. we first define a family of weight functions W == {wss So U P; - R (s((p) S w(p), Vp E
So: ws(p) < 1, Vp P7; ||ws||a n -m). Intuitively, W represents the collection of all possible
28

---

weight functions for n - m inliers of the weighted dataset So U PÝ. Define a weight function w/ as follows:
w' == arg min WyEW
ws(p) . dist(p,
PESOUP?
ie., (8o U P;, . w²) represents the m inliers of So U P1 with respect center Let mg Epeso (w(p) w' (p)) denote the number of outliers of So U PJ w.r.t. c that are contained in So.
For preparation, we introduce the concept of ball range space, which facilitates a precise analysis of point distributions in P and S.
Definition E.1 (Approximation of ball range space, Definition F2 in (3) For given dataset C IRd the ball range space on (P,P) where P == (P n (a u) E IR, u > 0} and
Ball(c, u) = {p E TRd dist(p, c) S u). subset Y P is called an s-approximation of the ball range space (P,P) if for every C, u E Rd,
P Ball w)
Y Ball(c, u)l
S..
[P]
Based on this definition, we have the following preparation lemma that measures the performance of So: which is refined from [39].
Lemma E.2 (Refined from Lemma F.3 of (39 Given dataset Po C Rd. Let So be uniform
sampling of size ( a from Po. then with probability at least 1 pofy{1/E)
So is an s-approximation
of the ball range space on Po. Define a weight function w: w(p) any Rd. u RT,
IPo So
for any p So. Then for
IPPo n Ball(c, u)l w(S n Ball(e, u))l S e|Pol.
By the iterative method introduced by [48], the factor (dd) of coreset size can be replaced by Ö( -2). Therefore, So an E-approximation of the ball range space on L*.
Then we are ready to prove Lemma 3.2 We first analyze where the induced error comes from.
Recall that we fix center in this section. Let To == minpez- dist(p, e) denote the minimum distance from points in Lt to c. Let Ty := maxpep; dist(p, c) denote the maximum distance from points in Pf
We have the following Lemma.
Lemma E.3 (Comparing To and Tj). When mp = m, /cost (P,c) (m)t(())(S) U PP. holds. When mp To < T7 holds.
Proof. If m.p m, for any point p L", we have dist(p, c) 2 maxpery dist(p, c). Since So is sampled from L*, know that for any point p E So, dist(p, 2 maxpep7 dist(p, (p,c), c). Therefore, we have mp = my = m and then cost(m)) (m) = cos c) = cost(m) (So U PT,c).
If mp m, then there exists point P Pj such that dist c) 2 To. By definition, we also know that dist(p. c) < Tj. Therefore, combining these two conditions, have To < Tı.
remains analyze the case that mp < m. In this setting, we present the following lemma, which provides an upper bound the estimation error (cost(m)) (P., cost (Soo c) Before stating the lemma, we introduce a notation that will also be used in subsequent lemmas. We sort all distances dist(p, c) for each point p Pf in descending order, w.l.o.g. say dist(p1, c) > ... >> dist (p) c). Here, we can safely assume all distances dist(p, c) are distinct, given that adding small values the distances has only a subtle impact on the cost. Let d, == dist(p;, c) for i E [m]. Then di...., dm represent the distances from the m furthest points in Pj to the center c. Now, we are ready to provide the following lemmas.
Lemma E.4 (An upper bound of the induced enror of So). When mp m, suppose IPoo n Ball(c, u)] w(So n Ball(c, w))l < A for any > 0, the following holds: (cost(mm) (P,
cost (m) (So U P/ c)) 2- Imp msl) (Ti - To).
29

---

Proof. By Fact F.1 in 39, we have
cort (1 (I',c) = 1000 (m mp - |2 Balllc, d) (mm))
000
(24)
and
cost (ms) (So,c) (ms) (000 (m- ms -----s--ws w(So n Ball(c, u))) du
(25)
where (a)+ max {a, 0}.
Let T P (ist(p,c) c) and Ts maxpeSo (p)>0 (ist(p, c). Then we know that
To & T, Ts T, By definition, for any distance >> T, we have | n Ball(c, u)l 2 mp. Then we can transform the Inequality (24 to
cost (m (L cL',
(m mp LL n Ball(c, u)l)
(26)
Similarly, for any distance u > Ts. we have w(So n Ball(c, u)) 2 m ms. We can transform the Inequality (25 to
cost. (ms) (So,
(m-ms- (m- ms - w(So n Ball(c, d)
(27)
Based on the notation of .i.... dm. we know that each point p E Pt satisfying dist(p, c) S
dm-mp++1 is an inlier of P7 U LL, and each point q P7 with weight w/ w'(4) > 0 satisfying
dist(q, c) I dm-[ms] is an inlier of So U Pj. Let m's == |ms] Let == Imp mgl denote the
difference in the number of outliers. If mp ms, have
1 dm-mm m² I cost (m-mp) (PJ cost mm) (Ppmm)
(28)
and
cost mm (m-mm) S 11 dmmmm--l cost ma- (PT, (ammm))(Pt..o
(29)
If mp mg, we have
1 dmmmmp mp S cost (m-
mmm (P) cost (Pi
(30)
and
cost (m- (-)-m)((Pt. (PF, cost (m- (om-mp)((2 (m S dm-m's
(31)
mp my, we have By definition, we know that
cost (m (am-ms)(Pp..)))) cost (m- (mPP)))) =0
(32)
dm S dm S di ST,
(33)
When ms * m, we know the point p E Pj that has distance dist(p, c) dm-ms is an outlier on Př U So. Then there exists point g E So such that dist(g. S dist(p, c). Then we have
dm-mns 2 To.
(34)
Similarly, the point p E Pt with distance dist(p, c) = dm-mp an outlier on P. thus there exists a point L* such that dist(g,e) dist(p, c). Then we have
dm-mp 2 To.
(35)
By Lemma suffices to discuss the following three cases based on the values of mp and mg.
Case 1: ms = m71
Recall that / = m. mp, we have
cost (L*,)
(m -mp LL Ball(c, dd
(Inequality (6)
[' (1 1-I Balll(,, u)()du
T
ms -mp)
T L n BBlll(e, u)ldu
= I-T- -
(Vp E L", dist(p, c) 2 To).
To
30

---

Since ms = m and mp < ms, each point E L - L(r) satisfies distíp, c) < mingeso dist c).
For each To < S T, we have w(So Ball(c, u)) 0. Since - Ball(c, u) w(So
(a u)) - A, we know T. n Ball (c, u)] x A for To S u < and
1. (T To) A cost cost ( S1.T.
Since cost (ms (mmmmm(())) (So. = 0, we have
cost (my) (So,c) 11-T cost (m)) (L* (Lt
(36)
and
cost (m.s) (So. c) cost (L', ( -T-To) A 1.
(37)
Adding Inequality 30 and Inequality (36). we have
cost(m) (P, c) cost (So U c) < T. - To
(T S Ty and Inequality 35
mp msl (T, To)
(Lemma)
E.6
Adding Inequality 31 into Inequality 37
have
cost (m)) (So UP. c) cost (m)
(P.c)
-T- To) +/ (d)-T)
TT) A +1.(II - -To)
(To ST < Ty and Inequality (33)
(mmp- - + A) ([]-TT)).
Then we complete the proof of Case 2.
Case 2: ms # mp < m Without loss of generality, we assume that mp ms and T 2 Ts.
Firstly, we prove that cost (1P) (P, cost (ms) (So Pf.c s 2(A + |mp msl) - (Tr To). We have
cost. (mst( (I* .) cost, (ms) (So,c) c))
(m mp - -b Ball(c, u)
Ts
(m - ms w n Ball(c, u)))du
(Inequalities (26 and 27
To
(ms mp + w(So Ball(B u)) [L* n Ball(e, u))
(m - mp - -1p
u)l)du
(T Ts)
Ts
(w(So n Ball(c, u)) L n Ball(c, u)l)du 1- TTs
T
(m mp-12 n Ball(c, u)l)du
Ts
/' (m mp - mp-IL
A (T's - To) T- + JTs
Ball(c, du.
For Ts < u < T, we have IL' n MaBlllc, u)l 2 m A, thus
(mp) (T*,, ; c) cost (ms) (So,c)
s -Ts - To) + (A - -mp)du -1 I.
TT
5 A. GTSs To) + (T TTs) T
< A. (T, - To) - T
(To < Ts < T, and T < TT).
31

---

Adding Inequality 29
and the above inequality, we obtain
cost (m)) cost (m))
(So U cf
K A- (Tr - (T) + (dm-mp+1 I's)
A. (Ti - TT) +1 (T, -To)
(Inequality 33
W
(2 A + mp - msl) (Ir - (T))
Secondly, prove that cost(ms)) By Inequality (26) and Inequality 27.. we have
(So U P7, c) cost S (A mm msl) (T, To).
cost (ms) (So.c) c) cost (mar) (L*
Ts
J
(m- - (m- -ms=w(So n Bal d)))
(m mp -1-" BBal((c, u))ddu
P3
(mp ms IL" 0 Ball u)] wSSo n Ball(c, u))
J0
T
(m mp - mpp
- Ball(c, w)))du
TT)
Ts
Ts
(mp ms + |L* Ball(c, u)] w(So n Ball(c, u))
Ts
W4
(|I.* (BBal(ee u)] w(So Ball(c, u)) + 1 Ts
To
(Ts-To) + + Ts.
Adding Inequality 28 and the above inequality, have
cost (m)
(So
U Pf, c) - cost. (m) (P,c)
A (Ts To) +1 (Ts dmi')
A (Ii To) +1 +l-(Ir -To)
(Inequality (34 and T's S T7)
(A+ + mp ms|) (Ti - -To).
In summary, we have
Jeost (m) (P. (m)) cost (So U U c)1 2 2:2-(A-2 + |mp mmp) (Ti To).
Similarly, we can get the same conclusion when T < Ts. Moreover, for the case that mp < ms. with the help of Inequalities (3 33 (3) the conclusion still holds.
Case 3: mp ms # m
By Inequality 32). we have
[cost (m) (So UP cost (ost (P,c))
cost (mrt
By similar argument as in Case 2, we have
(ms) (So Pf c) cost (me) (mst (P.c)) 2 |mp msl) -aasss)-(i---- To).
Overall, complete the proof of Lemma E.4
The Lemma E.4 tells that most 2(A |mp msl) points contribute the error, with each point inducing at most Ti To error. We now analyze the magnitude of Ti - To.
Lemma E.5 (Bounding induced error of each point). Ti To ((cost(m)(PP.))
32

---

Proof. Let Fmax == maxpep; dist(p, c*) denote the maximum distance from Pf to c², Let dmax == dist(c, e*) denote the distance between the approximate center c* and the center Let F ==
post(P) p))))) denote the average distance from Pj c*
mm
Utilizing the triangle inequality, for any point p E L", we can assert that dist(p; c) 2 dist(p, c*)- dist(c, ct) 2 Tmax dmax. thus To 2 T'ax - dmax. Similarly, for any point p E Pf. we have Tmax + dmax. thus Ti mmax dmax. Consequently, depending on whether Tmax is greater than or less than dmax we derive different expressions for Ti- - To: If Tmax 2 dmax, then Tr To S 2 dmaxi if fmax < dmaxs given that To 2 0, it follows that To Tmax dimax < 2 dmax- Therefore, We discuss the relationship between dmax and F in two cases.
dist(p, c) dist(p, c²) )= + dist(c, c*)
turn prove 2-m 3-m-dmax Ocost (m) (P, e)).
Case 1: dmax < 4F By definition of F, we have
4 cost (m)) (P,c*)
(n m)r
(n m m
m dmax
(n 2 4m).
since et is an -appooiimee solution for robust geometric median, we have
Occost (m)) (P.c)) 2 2 m dmax
Case 2: dmaxx > 4F Let P= tv E (p, S 2F]. By definition, we have |p| 1 |17
Since dmaxx 4F, obtain
8 cost (m) (P,c)
8 ((n m)/2 m)) min dist(p, c)
PEP
V IV IV W
4 min ci
(n 2 4m)
PE
4 m min(d cp))(pp'))) PEP
(Triangle Inequality)
4 m (dmax - 27)
2 m dmaxx
Overall, we have Tj To S Ocost (m)) (P, c)/m), which completes the proof.
Combining Lemmas E.4 and E.5
we obtain the bound: |cost (P,c) cost (m) (So U e) S
0(1) (A + |mp msl) cost Lim
(Pic) To prove (cost(mm) (P, - (m) UP (e))
cost (m)) (P. remains ensure that A = (sm) and |mp msl 0 We show that both conditions hold when So is an e-approximation for the ball range space on L*
Lemma E.6 (Bounding misaligned outlier count). Suppose So is an s-approximation for the ball range space L*, we have |mp- ms| < 2 m.
E Before proving this lemma, we first analyze the properties of w'. Given a point E So U Pt, we say
p is of partial weight w.r.t. c 0 < w (p) w(p) when p E So and 0 < w w'(p) < 1 when p E Pj. Intuitively, such a point is partially an inlier and partially an outlier of So U Pi to c. The following claim indicates that the number of partial-weight points is at most one for any c.
Claim (Properties of wertht points). For every center c C Rd, there exists at most one point v E So U Pf of partial weight w.r.t. Moreover, for any other point p E So U P7 with w/ (p) = wp)), we have dist(p,c) c) S dist(u,
Proof. By contradiction, we assume that there exist two points v, E So P of partial weight w.r.t. W.l.o.g., suppose dist(v, c) < dist(e', c). We note that transferring weight from to o' increases (v) by any constant > and decreases w w'vv') by does not increase the term cost (m)) (S) U Pf.c) c). Then by selecting suitable 6, we can make either v or o' no longer of partial weight. Henee, there exists at most one point v So U Pf of partial weight w.r.t.
33

---

we have For any other point E So Pł with w'() = w(p), suppose dist(u, e) < dist(p, c). In this case, increasing w')v) by small amount 5 > 0 and decreasing w' (p) by 5 decreases cost (m) (So U .j. This contradicts the definition of w', which completes the proof.
Recall that ....... dn represent the distances from the m furthest points in Pf to the center c. Now we are ready to prove Lemma E.6
and mp < mg. Without loss of generality, we assume that mp > mg. Let l == m mp + 1. Based on the definition of di,..., dm. each inlier point satisfies dist(p, c) I di, There are mp inlier points in L so
Proof of Lemma E.6 We only need to consider the case of my
we have:
IL n Ball(c, dr, I mp.
(38)
Let 12 = m - [mg] Since mp > mis; we have mp 2 [g] 1, then we get the inequality
1 1- 4.
(39)
Moreover, we claim that
w(S n Ball(c, di,-1)) S [ms] +
(40)
By Claim I at most one point v. E So U Pf of partial weight w.r.t. c exists. If U E Pf. we have dist(v, c) d Any point v' Pj with dist(v', c) > d1,-1 is outlier of So U Pj. Then there points in P/ that have distance to C at least d13-1- By contradiction, we assume Then there are less than m points in P that have a distance to c greater than d1,-1, which contradicts the fact that v' is an outlier of So U P7. Hence, Inequality (40) holds. For the case that v E So or there no point of partial weight w.r.t. c, the argument is similar.
are m mm] that w(So n Balls(c, dz,-1)) [ms]
Since mp mg, we have w(So n Ball(c,, dr, conclude that
mp. Combining with Inequality
38
[L* (BBllBlc, di,))
m mp
(41)
w (So n Ball(c, dr,)):
Moreover,
w(So n Ball(e, da))(
w(So n Ball(c, dig-1)) 1))
(42)
m |ms] -1
Then, we have
||L Ball(e, d wSo Ball(c, d:)))
= w(So n Ball(c, di.)) [L* n Ball(c, d:.)l
(Inequality 41
mp |ms]
(Inequality (38) and 42
mp ms - 1.
Since So an e-approximation for the ball range space on L*, by Lemma E.2
|| n Ball(c, dr, ) - wSS n Ball(c, di, ))1 s 5.mm. m.
Combining the above two inequalities, we have
|mp ms < E. + 11+ 2 m. Similarly, we can get the same conclusion when mp < my, which completes the proof of Lemma
E.6
Now we are ready to prove Lemma 3.2
Proof of Lemma
3.2 Based on Lemmas
B3 and E.4 we have
lcost (m) (P.c) cost (m) P2 U S),c)
2 (A + [mp msl) (Tr To)
5 0(1) (A + |mp ms)) )) cost (m) (m)())))))))))) (P,c)/m
(Lemma E.5
r O(1) (em + |mp mmm) cost (m)) (P, c)/m
(Lemma E.8
O(c) - cost (m) (P.c),
(Lemma
which completes the proof.
34

---

E.2 Extension to other metric spaces
In this section, we explore the extension of Algorithm 2 designed for the robust geometric median in Euclidean space, to the metric spaces by leveraging the notions of VC dimension and doubling
dimension since the VC dimension is known for various metric spaces X 9 40
Let (A, dist) denote the metric space, where X' is the set under consideration, and dist X' x Rgo is function that measures the distance between points in X, satisfying the triangle inequality. Specifically, in the Euclidean metric, X' represents Euclidean space Id and dist is the Euclidean distance.
Similar to the analysis for robust geometric median on Euclidean space, we discuss the induced error of Sy and So separately. We first introduce how to bound the error induced by So. Since the dist function satisfies the triangle inequality, our Lemmas E.3 E.4 hold, ensuring that each point in So induces at most O (cost (P, /m) error. To ensure the number of points in So inducing error ((mm), it suffices for So to be an e-approximation for the ball range space on L (as shown in Lemma E.6). Next, we illustrate how this condition can be satisfied using the notions: 1) VC
dimension; 2) doubling dimension.
VC dimension. We begin by introducing the concept of the VC dimension of the ball range space, which serves as a measure of the complexity of this ball range space.
Definition E.7 (VC dimension of ball range space). Let M = (X,, dist) be the metric space and [Ball(c, u) | c E X, u 0} the collection of balls in the space. The VC
define Balls(X)) dimension of the ball range space (X, Balls(X)). denoted by dyc (2), is the maximum |P]. P C X such that [P Pn (alls(X) = 2| where PO Balls(X)) == {P Ball(c, u) Ball(c, u) E Balls(A)).
The VC dimension of (X, Balls(X))) aligns to the pseudo-dimension of (X, Balls( used by 45 Based on this observation, we give out refined lemma from 455.
Lemma E.8 (Refined from (45)). Let M = (X, dist) be the metric space with VC dimension
(X). Given dataset Po S X, assume So is uniform sample of size Ö ((dvo()) from Po. then with probability 1 - 1/poly(1/e) So is an e-approximation of the ball range space on Po.
The Lemma E.2 used earlier for the Euclidean space case, is direct corollary, since in Euclidean space IRd, we have dvc(X)= = (d). This lemma illustrates the number of samples required from L
Doubling dimension. Another notion to measure the complexity of the ball range space is the doubling dimension.
Definition E.9 (Doubling dimension BI 3). The doubling dimension ddim(X)) of metric space (X, dist) is the least integer / such that for any Ball(c, u) with e E X, u > 0, it can be covered by 24 balls of radius u/2.
We denote the metric space with bounded doubling dimension as doubling metric. Based on B8]. is known that the VC dimension of a doubling metric (X' dist) may not be bounded. Therefore, the previous Lemma E...does not apply for an effective bound. We want to directly relate the ball range space bound to the doubling dimension. This goal can be achieved by the following refined lemma.
Lemma E.10 (Ball range space approximation in doubling metrics [8).. Let M = (X, dist) be the metric space with doubling dimension ddim( Given Po S X, assume So is uniform sample of size D(ddim(())=+ from Po, then with probability 1/poly(1/e)) So is an e-approximation of the ball range space on Po.
Proof. Suppose the distorted distance function dist': X' x X' - R20 satisfies: for any Z, y/ E X, we have (1 c)dist(x, y) < dist' (z,v) < (1 + e)dist v). By Lemma 3.1 of (38], we know that with probability
(1/))(1/),.55 So is an e-ball range space approximation of Po w.r.t. dist', when So = ((ddim(x))=3) By setting of dist', we know So is an (ee)-ball range space approximation of Po w.r.t. dist, which completes the proof.
This lemma illustrates the number of points needed to be sampled order to bound the induced error of So when the metric space is a doubling metric.
35

---

The remaining problem is to bound the induced error of Sj. We give out generalized version of Theorem B.I. as below.
Theorem E.11 (Refined from Corollary 5.4 in 40]. Let M = (X, dist) be the metric space. There exists a randomized algorithm that in (n) time constructs weighted subset S1 S Pj of size:
(ddvo(X) =)²,, w.r.. the VC dimension (vc
O(ddim(XX) x 2),
w.rt. the doubling dimension ddim(())
such that for every dataset Po of size m, every integer 0 S t S m and every center R cost (Po Pi c) 28 cost(Pi,
(cost (Po cj (ost U S1,
By combining the discussions of the errors induced by So and Sj, present the main theorem for constructing a coreset for the robust geometric median across various metric spaces. We study the shortest-path metric (X, dist). where X' is the vertex set of graph G (V. E)), and dist(.;-) measures the shortest distance between two points the graph. The treewidth of graph measures how ttree-like" the graph is; see Definition 2.1 of [4] for formal definition. A graph excluding fixed minor is one that does not contain particular substructure, known as the minor.
Theorem E.12 (Coreset size for robust geometric median in various metric spaces). Let & E (0, 1). For metric space M dist) and dataset X C X of size 2 4m, let S = So St be sampled set of size
(log(1x1)) 4) if M is general metric space.
(ddim((X) - =-²
M is a doubling metric with doubling dimension ddim(
Ō(t.e if M is shortest-path metric of a graph with bounded treewidth
O((H) if M is shortest-path metric of a graph that excludes fixed minor HI
Then S is an e-coreset for robust geometric median on X.
This theorem illustrates the coreset size with respect to different metric spaces, improving upon previous results for robust coresets by eliminating the (m)) dependency.
M (X, dist) general metric space, then dyc(X) Olog x)).. Thus, we have |Sol (log( (1x 2- by Lemma E.8 and [S]] (log( (l)) -=)))))-))))) e-4)
Proof of Theorem 12
by Theorem
E.11 leading to a coreset of size (log(( ([log((x))- -
If M (X, dist)) is doubling metric space, then by definition, ddim( ()) is bounded. Thus have |Sol O(ddim(X') 3-3) by Lemma E.10 and [S] O(diim(X) ===) by Theorem E.11
leading to coreset of size (ddim(XX) 222).
AM = (X' dist) is shortest-patt metric of graph with bounded treewidth t, we have dyc(x)= O(t) by g). Thus, we have |Sol = Ö(t e 2-2 by Lemma E.8 and |S]] = Ö(t ead)) by Theorem E.11 leading to a coreset of size Õ e11)
If M = (X, dist) ) is a shortest-path metric of a graph that excludes a fixed minor H, we have (x) O(HH) by [8] Thus, have |Sol Ö(H - =-- by Lemma E.8 and |Sy]
O(H H -4) by Theorem E.11 leading to coreset of size Ö( -
F Proof of Theorem 1.5 robust ccclustring
In this section, provide coreset construction for robust (k, =)-cluttering when d 2 1. We first extend the definition of the robust geometric median and its coreset to the robust -llustein and its corresponding coreset.
36

---

Definition F.1 (Robust (k, 2) clustering). Given dataset P C IR of size n 2 1 and an integer m 2 0, the robust (k: z)-chsstei problem is to find a center set C' C IRd |C| that minimizes the objective function below:
cost (P,C):=
min
E (dist(p, C))²
LCP: L|=m
DEPAL
where L represents the set of m outliers w.r.t. C' and dist(p, C) = mineec dist(p, c) denotes the Euclidean distance from p to the closest center among
Before we define the coreset for robust (k, cluustrri,, we introduce the generalized cost function in the context of the robust (k, -)ccusstei,
Definition F.2 (Generalized cost function for robust (k:, =)-clustering). Let m be an integer. Let S S Rdd be weighted dataset with weights wr(p) for each point p E S. Let w(S) = Epes w(p). Define a collection of weight functions W := fww' S + R 1 w/ (p) = w(5) m A Ap S, wu' (p) S w())). Moreover, we define the following cost function on S:
AC C Rdd |C| = k cost (S, C) == min EW PES
Σ w')p)
(dist(p.
With this definition of the generalized cost function, we now define the notion of a coreset for robust (k, =)-cusstein
Definition F.3 (Coreset for robust (k: =)-luutterrn Given a point set P C Rd of size n 2 1, integeer
m 2 1 and E E (0, 1), we say weighted subset S P together with a weight function S + R e-coreset of P for robust (k:, 2) 2)-clustering if wSS) and for any center set C C R. |C| = k
cost (m)) (S, C) E (1 + e) cost. (mm) (P,C).
Finally, we extend the concepts of inliers, outliers, and the ball range space.
Inliers and outliers. Throughout this section, we denote the approximate center set for robust (k, =)- clustering by C = {ci...... ) C Rd. which is an ((p-xxxpoonnnaoion of the optimal solution. We then define the inliers and outliers with respect this approximation center set.
Let L == arg min L|=m cost, (P - L, C*) denote the set of m outliers with respect to C* and define Pj == P L* as the corresponding inlier set. The inlier set Pj is naturally partitioned where each cluster P contains the points in Pj closest to its
by C' into & clusters {Pi ......... P }. corresponding center c;. Additionally, define Fmax == maXpeP; dist(p, C*) which represents the
maximum distance from the points in 17 to this center C*. Let = v/ //cost.(P3.00 denote the average distance from P7 to C** Under these notations, the second condition of Assumption I.4 can be rewritten as (fmax)* 4k (F)#.
Ball range space. We introduce the concept of the k-balls range space, which is direct extension of the ball range space defined in Definition E.
Definition F.4 (Approximation of b-balls range space, Definition F.2 in 39
Let Balls u)
Ualc u). For given dataset P C Rdd the k-balls range space P is (P,P) where P = (P Balls(C, u) C C Rdd CI k. u E R R+}. A subset Y C P is called an e-approximation of the b-balls range space (P, PP) if for every C C Rd, |C| k, Rt
PP n Balls(C,
Y Balls(C, u))
Se.
PP|
Y
Based on this definition, we have the following lemma that measures the performance of So for robust (k, z)-clustering.
Lemma E.5 (Refined from Lemma F33 (3)). Given dataset Po C Rd. Let So be a uniform sampling of size Ó Edd from Po, then with probability at least 1 poly(k/e)
So is an e-approximation Pol
of the k-balls range space on Po- Define a weight function w: w(p) = [ for any E So- Then for any C. C IRd, |C| u. +
IlPo n Balls(C, u)l w(o n Balls(C, u))l - Pol
Then ready to give out main result.
37

---

F1 Result for robust (k, 2) clustering
We first recall the following theorem.
Theorem F.6 (Restatement of Corollary 5.4 in 40 There exists a randomized algorithm And that
in (nkkd) time constructs a weighted subset S S Pj of size Ō(k2=-2 min {=-2, _d))), such that
for every dataset Po of size m, every integer S t S m and every center set C C R., [C| =
Jcost 1 (Po U pj C) cost. (1) (Po (PoUSA S₁, C)I S cost (Po Pi,C) + 2 cost, cost:(P], C*).
This theorem is a generalization of Theorem 3.1 describing the number of points that need to be sampled from Pj for robust (k; -)cluttrein
To adapt Algorithm 2 for Theorem 1.5 we only need to adjust the size of So to Ō(ke min (E d)) in Line and modify the algorithm A, Aga in Line (see Algorithm 3 Consequently, the runtime remains dominated by Line 1 and Line 3, resulting in an overall complexity of O(ndk) according to Theorem R6
Algorithm 3 Coreset Construction for General and General
Input: A dataset P C Rd, s E (0,1) 1) and 0 -app-xppooee center set C* C Rdd
Output: An s-coreset S
1: L <- arg Li (P C") Pi t P- It*
2: Uniformly sample So C L of size Ō(kE 22 min {= 2, dd)). Set vp E So. wp( + [
3: Construct (Sr, wy) + ARa(PT) by Theorem F.6
4: For any p E So. define w(p) (p) and for any p E Sr, define w(p) wr(p))
5: Return S + So U US and w;
Similar to the robust geometric median, we present the key lemma used to prove Theorem L.3 below.
Lemma E.7 (Induced error of So). For any center set C' C Rd, |C| k; have |cost (m) (P,C)-
cost (m)) (So U Pj, C)I < O(e) cost!!") (P,C).
Theorem 1.5 follows as a corollary of Theorem F.6 and this lemma, with a proof similar to that of Theorem 1.3
Remark F.8. The second condition in Assumption 1.4 can be replaced with dist cf)= >
min(1FFlle311 for any G E C i + j. Under this modified assumption, Theorem 1.5 be-
m-r
comes a direct generalization of Theorem 1.3 as the second condition vanishes when i = I. This modification ensures that clusters are sufficiently well-separated, which explains why our algorithm
performs well on the Bank dataset when 3, as this modified assumption is satisfied in this case.
Below we illustrate why this assumption also works. If points in each cluster are mostly assigned to dis-
tinct centers, then cost." (m)) (P, C') ss cost. (m) (P, C*), making the error /cost! (m)) (P, C)- costt (m)) (PFU So, C²)l easy to bound. Alternatively, if two clusters each have at least half of their points assigned to
the same center, then by the modified assumption, cost."" (17) (P, C) >> mr mrmax max: which is large enough to bound the error induced by So.
F.2 Proof of Lemma F.7: Induced error of So
In this section, fix center set C C Rdd of size k and define To minper- (dist(p, C))², Tr = max (pist(p, C))². We observe that Lemmas B.3 and E.4 can be directly extended to robust (k, =)-cluttering. Therefore, the induced error of each point is at most T, - To. Next, we show that T, To < O((ost (P, (P) c)/m). supported by a detailed discussion of the sizes of Tr and To (see Lemma F.. The remaining task is to ensure that the number of points that may induce error is O(em). The result of Lemma E.6 can be extended to robust (k:, =-ccusterrn when So an E-approximation of the b-balls range space on L*. By Lemma E.5 points from L to ensure the approximation.
we sample Ökks min(s- 2,d))
We then demonstrate how to prove that T To < Occost! (m)) (Cccost(((((p)) (P.c)/m).
38

---

Lemma F,9 (Bounds for 7y and To). When mp m, we have Ti To S O(cost." (T²) (P, PP,c//m)
Proof. Let dmax == EC dist(c", C)) denote the maximum distance points to Let d'axx maxeec dist(e, C**) denote the maximum distance of points in C to C".
We first claim that Tj I (Fmax dmax)². Let p be defined as maXpeP7 dist(p, C). Denote oj as the closest approximate center to P. where cp : arg min. dist(p, c²),, and Cp as the closest center ep. where Cp == arg mincee dist(cp, c). This setup allows us establish an upper bound for Ty:
dist (F, C) s dist(p. cp)
dist(p. (.))) + dist(c op)
(Triangle Inequality)
Tmax + dmaxx
thus, Tj I (Fmax + dmnxx)
Next, we discuss the relationship between C' and C* in two cases: Tmax I dmaxxi 2) Fmax dmaxx-
Case 1: dmax 2 Tmax this case, have Ty To S 2 since To O. Therefore, C))).. Suppose dist(ct, C) = dmax. let (Fr)² = (Tm) (P, (T)
suffices to prove 2 ded S Occost
, //PTT Based on the scale of dmaxx we discuss in cases.
Case 1.1: dmax S 8r; By definition of F., we have
16 cost (m)) (psttt))pppp)))tp (P,CC)) =
16 1PM| (Fa)²
2 PT|| diaax
2 m diaax
(Item of Assumption 1.4
Since C* is an ([1))-)pprxxiattt solution for robust (k, clusstrrn, we have
2 (dmax)² )² <
16 cost (m²) (P, <
Case 1.2: dmax > 8f;
Let P: = (p E Pł (p, C*) S 4r,). By definition, we have |P3| I
For any point p Pi.
suppose Cp == arg minaeo dpst(p, c), then we have
dist(p, c)
dist(c) cp) - dist(p, of) dist(c;; C) dist c))
(Triangle Inequality)
(43)
dmax dist(p, cf)
dmax 4F;
(Definition of P.)
Since dmax > 8F,, we obtain
3
8 cost (P,c)
IV
8 ( P.1 11
m) min (dist(p, C))* pEP:
8 ()) P. (ddmax 4F;)
(Inequality 43
4a (- P?1 m m)dinax
IV
2 m dmax
(Item 1 of Assumption 1.4
Overall, we have T, - To & (cost! (m)
(P.C)/m)
Case 2: dmax Tmax We have Ti To 2 r since To 2 0. By Item 2 of Assumption 1.4 we have m riax S 72, thus T, To < 2 cost !omt (P, (P.C)/m
Combine Case and Case 2, we complete the proof.
39

---

F.3 Extension to other metric spaces
In this section, we explore the extension of Algorithm for robust (k, clussternn in Euclidean space, to various other metric spaces.
Similar to the analysis for robust geometric median, we discuss the induced error of S and So separately. For the error induced by So, Lemma 19 still holds, so it suffices for So to be an e-approximation of the k-balls range space.
VC dimension We begin by introducing the concept of the VC dimension of the k-balls range space.
Definition F.10 (VC dimension of k-balls range space). Let (X' dist) be the metric space and > 0}. The VC dimension of the k- balls range space (X', Balls; (2)),, denoted by dve()', ) is the maximum [P], P S X such that [P Balls,( = PI, where Pn Ballss (2') {P n Balls(C, Balls(C, u) E (a))s
define (al)))())) : (Balls(C. u) C C X, CI
The VC dimension of (X,, Balls;( aligns the nneudo-dimension of (X, Balls; (X)) used by Based on this observation, we give out refined lemma from 45
45
Lemma F.11 (Refined from [45]) Let (X, dist) be the metric space. Given dataset Po S X, assume
So is uniform sample of size Ö (=ávv(()) ) from Po, then with probability 1/poly(k/e), So is a e-approximation of the k-balls range space on Po-
This lemma illustrates the number of points needed to be sampled from L*
Doubling dimension Similar to the Lemma E.10 we give out the Lemma F.12 that illustrates the number of points needed to be sampled in order to bound the induced error of So
Lemma F.12 (Balls range space approximation for the doubling dimension). Let M = (X, dist) be the metric space with doubling dimension ddim(X).. Given Po S X, assume So uniform 2=22. k) from Po. then with probability 1/poly k. 1/e), So is an E-approximation of the k-balls range space on Po-
sample of size O(ddim(X)) g-=
The remaining problem is bound the induced error of Sy. We give out generalized version of Theorem E. as below.
Theorem F.13 (Refined from Corollary 5.4 in 40). Let (X, dist) be the metric space. There exists randomized algorithm that in O(nk) time constructs weighted subset S₁ Př of size:
Ók dvv(x) - -22=2), w.r. VC dimension dvc(X),
Ō -ddim(X)) g--22) w.r.t. doubling dimension ddim,()),
such that for every datasel Po of size m, every integer S 1 S. m and every center set C Rdd. (t) CD cost?? (PoUS:, C)I S c-ostt (PoUP;, C) 2e-ccott C*). |C|=k; = !cost
By combining the discussions of the errors induced by So and S,, we present the main theorem for constructing a coreset for the robust (k:, 2)-clustering across various metric spaces.
Theorem E.14 (Coreset size for robust (ks, clccutrrgi in various metric spaces). Let e E (0, 1). For metric space M dist) and dataset X C X' satisfying Assumption 1.4 let 5 So US be a sampled set of size
Ö(KZ log(1>1) e 22=22 if M general metric space.
Ō(kZ. dddi(x)) - - if M is a doubling metric with doubling dimension ddim(X).
Ō(kZ t. =2--)= if M a shortest-path metric of a graph with bounded treewidth t.
0 | -22-2) if M is shortest-pathh metric of graph that excludes a fixed minor
H.
Then S is an e-coreset for robust (k, (k,,))-cuuse clusttrring on X.
40

---

Table 4: Datasets used in our experiments. For each dataset, we report its size, dimension (DIM), number of outliers (m.) The number of centers (k) used in robust (k, -)-usterrnnng. We also provide the values of min; | and (Fmax// for robust (k, =/-custteinng. Our Assumption 1.4 requires that min; P 2 4m and (Fmax/ r I 4k. The value Y (resp. N) indicates these assumptions are satisfied or not. Note that the Athlete dataset is sourced from Kaggle, while the other datasets are
from the UCI repository.
min; PP1|
DATASET
SIZE
DIM.
Y/1
==
==
TWITTER
10
2
2000
5
8968,
588.N
3.819,Y
1.083.Y
CENSUS 1990 46
10a
68
2000
5927,N
5927.N
1.873,
3.252.Y
BANK 47
41188
10
824
1361,N
1361,N
4.674,Y
15.731.Y
ADULT 6
48842
6
977
5
4508.
186.N
5.151,Y
5.834,Y
ATHLETE 36
10000
200
1018,Y
1018,Y
2.923.Y
7.062,Y
DIABETES
10000
10
200
1415,Y
1459,Y
2.551,Y
2.527.Y
This theorem illustrates the coresct size with respect to different metric spaces for robust (k,2)- 2)- clustering, improving upon previous results by eliminating the O(m) dependency.
Proof of Theorem F.14
If = (X, dist) is a general metric space, then d = O(log (1).
Thus, we have So Ó(k log(1>') s-2) ) by Lemma E.8 and |S = 0 log([>t) -) by
Theorem E.1l leading to a coreset of size Ō(k² log([ ) t)
If ..M (X, dist) is doubling metric space, then by definition, ddim is bounded. Thus we have |So| Ö(k ddfe-ddd(()))) 2- by Lemma E. and and [S Ó ddim(X) e by Theorem E.1
leading to coreset of size Ö(k² (adim(X)-e
.M = (X', dist) is thootest--atth metric graph with bounded treewidth t, we have dy dyc(X)=
((t) by 8 Thus, we have |Sol = Ō tt g-2 by Lemma E.8 and | = Ö(k 1 t..-tt55 1- by Theorem E. leading to coreset of size Ō . E4)
If M (X, dist) is shortest-path metrie of graph that excludes fixed minor H, have (x) ((H)) by [ Thus, have |Sol Ō(k | e-2) by Lemma E.8 and [Sr]
Ō(k2. [ s )) by Theorem E.1l leading coreset of size Ö(k2 --
G Additional empirical results
G.1 Additional empirical results for robust geometric median
We first present Table 4 which lists the parameters of the datasets used in our experiments.
We show the missing result of Section Oo Bank, Athlete and Diabetes dataset in Figure This figure demonstrates that our coreset construction algorithm consistently outperforms the baselines. For instance, the Diabetes dataset, our method produces coreset of size 180 with empirical error of 0.057, while the best baseline, HLIW25, results in a coreset size of 280 with an empirical error of 0.065.
Analysis of our algorithm when n < 4m. For robust geometric median, we set m = n/2 2 in the six dataset, violating the assumption 2 4m, and report the corresponding size-error tradeoff in F The results show that our method still consistently outperforms the baselines even when < 4m. For instance, in Census 990 dataset, our method produces coreset of size 50200 with an empirical error of 0.004, while the best baseline produces coreset of size 51200 with much larger empirical error of 0.012.
41

---

Chura HJLWWS
Oura HJLW29 HILWWS
HULW23 HILL HELWWES
HLLN HILLW2
500
1000
1500
2000
100
200
300
400
100
200
300
400
[8]
(a) Bank
(b) Athlete
(c) Diabetes
Figure 4: Tradeoff between coreset size |S| and empirical error E(S). The horizontal axis is |S| and the vertical axis E(S).
Ours
Durs
Ours HJLW22
0.03
HJLW23
HLLW95
0.04
HJLW23
HILWW2
0.04
HLLW29
0.03
0.02
0.02
0.01
0.01
0
[S]
x10*
x10"
x10
(a) Census1990
(b) Twitter
(c) Bank
0.08
0.05
0.05
0.04
0.04
32
0.03
0.03
0.02
0.02
0.01
2.48
2.5
2.52
2.54
2.58
5400
5600
5800
5600
5800
(d) Adult
(e) Athlete
(f) Diabetes
Figure 5: Tradoff between coreset size |S] and empirical error ((S) for robust geometric median when we set m = n/2. this scenario, the assumption n 2 4m is violated.
Analysis under heavy-tailed contamination. For each dataset, we randomly perturb 10% of the points by adding independent Cauchy(O, noise every dimension, thereby simulating heavy-tailed data environment. As shown in Figure 6 our method consistently outperforms the baselines the robust geometric median task, demonstrating that its performance advantage remains stable even under heavy-taile contamination. For example, on the perturbed Twitter dataset, our method achieves coreset of size 1500 with an empirical error of 0.031, whereas the best baseline, HLLW25, requires a coreset twice as large (3000) to attain a higher error of 0.032.
G.2 Empirical results for robust 1D geometric median
We implement our 1D coreset construction algorithm and compare its performance to the previous baselines and our general dimension method. All experiments are conducted on PC with an Intel Core 19 CPU and 16GB of memory, and the algorithms are implemented in C++ 11.
Setup. We select the first dimension of the Twitter dataset, the second dimension of the Adult dataset, and the second dimension of the Bank dataset to create the Twitter1D, AdultID, and Bank datasets. We choose these dimensions because other dimensions in the four datasets listed in Table 4 contain no more than 130 distinct points, which would result in an overly small coreset. We conduct experiments on these ID datasets. To compute an approximate center for each dataset, we use the k-means++ algorithm.
'The probability density function of Cauchy 1) f(x) m(++2) for any H.
42

---

Oura
Oura
HUL
H.LWS W23
NLLWW2
0.1
Qura
HLLW22
0.02
HJLW23
HLLW25
0.05
1000
2000
3000
4000
1000
2000
3000
4000
500
1000
1500
2000
[5]
[S]
(a) Census1999
(b) Twitter
(c) Bank
0.14
0.25
Our
Dure
0.12
HJL
0.2
0.1
0.15
0.1
0.08
W
0.1
0.06
0.05
0.05
0.04
1500
2000
160
400
(d) Adult
(e) Athlete
(1) Diabetes
Figure 6: Tradoff between coreset size |S| and empirical error E(S) for robust geometric median when we perturb 10% points.
Experiment result. We vary the coreset size from 200 m 1000, and compute the empirical error E(S) w.r.t. the coreset size (S]. For each size and each algorithm, we independently run the algorithm 10 times and obtain 10 coresets, compute their empirical errors 8(S), and report the average of 10 empirical errors. Figure 7 presents our results. This figure shows that our ID coreset (denoted by OurlD) outperforms the previous baselines and our coreset for general dimension. For example, with the Twitter1D dataset, our ID method provides coreset of size 320 with an empirical error 0.013. The best empirical error achieved by our general dimension method for a coreset size 3500 is much larger, 0.087. Note that the coreset size of OurlD method does not grow uniformly, since the number buckets does not increase linearly with & or 1122
0.25
0.1
0.2
0.08
0.08
0.15
0.06
OurlD
Ours
0.04
0.04
0.05
HLLW29
HULW23
0.02
HLLW25
0.02
1000
2000
3000
500
1000
1500
2000
1000
1500
[8]
[5]
(a) Twitter1D
(b) AdultID
(c) Bank1D
Figure 7: Tradeoff between coreset size |S] and empirical error E(S) in ID datasets.
G.3 Empirical results for robust k-median
We implement Algorithm 3 for robust k-median and compare its performance the previous baselines.
Setup. We do experiments on the six datasets listed in Table 4 and set the number of centers k to be 5. We use Lloyd version k-means++ to compute approximate center C*.
Coreset size and empirical error tradeoff for robust k-median. We vary the coreset size from mn to 2m, and compute the empirical error ((S w.r.t. the coreset size (S]. For each size and each algorithm, we independently run the algorithm 10 times and obtain 10 coresets, compute their empirical errors E(S), and report the average of 10 empirical errors. Figure presents results.
43

---

This figure shows that our algorithm (Ours) outperforms the previous baselines. For example, with the Census1990 dataset, our method provides coreset of size 2200 with empirical error 0.012. The best empirical error achieved by baselines for coreset size 3600 is larger, 0.013.
0.05
0.1
0.08
Oura
Ours
Our HJLW33 HLLWSS
0.04
HJLLW23
HLLW2S
0.08
HJLW23
HLLW25
0.06
0.06
0.04
0.02
0.02
1000
2000
5000
4000
1000
2000
3000
4000
500
1000
1500
2000
[8]
[S]
[8]
(a) Census1999
(b) Twitter
(c) Bank
0.1
0.8
0.4
Ours
HJLWE0
0.08
HLL ILLW25
0.6
HILLW2S
0.3
HLLW22
0.06
0.4
0.2
0.04
0.2
0.1
0.62
500
1000
1500
2000
[8]]
|8
(d) Adult
(e) Athlete
(I) Diabetes
Figure 8: Tradeoff between coreset size |S] and empirical error ((S) for robust k-median on real-
world datasets.
Statistical fest. Similar to the robust geometric median, we evaluate the statistical performance between our method and baselines for robust k-median on all six real-world datasets. The results, listed Table 5 further demonstrate that our algorithm consistently outperforms the baselines.
Table 5: Statistical comparison of different coreset construction methods for robust k-median. The coreset S₁ represents our coreset, S2 represents the coreset constructed by the baseline H.JLW23, and S3 the coreset constructed by baseline HLLW25. For each empirical error ratio ((52) and ((S)))((S)), we report the mean value over 20 runs, with the subscript indicating the standard deviation.
Census1990
Twitter {(Sa)/8(S))
Coreset Size
{(S))/8(S)
((S))/((S))
((S2)/((S)
2200
3.374u.814
3.8001.262
2.958a.785
3.1491.
3200
1.800 6.99
1.4830.334
1.654g. 1.4080.439
1.5740.710
4200
1. 1.5413.559
1.3160.373
1.3799.369
Bank
Adult
Coreset Size
(S2))
((Sa)/E(Si)
((S))/8(S1)
((S))/E(S))
1200
1.657d.415 1.548p.552 1.3930.558
2.019..740
2.098b.551
2. 2.153..772
1700
1.257
1.440p.619
1. 1.702
2200
1.460o.737
1.450p.077
1.3730.545
Athlete
Diabetes
Coreset Size
{(S))/((S1)
((Ss)/E(S1)
{(S2)/E(S1)
{(S))/E(S))
210
11.481
8.85
12.688a.443
8.0801.652
310
2. 2.1422.525
1.798p.553
1.902..512
1.4020.395
410
2.
1.5230.481
1.6910.546
1.257a
Speed-up baselines. We compare the coreset of size 2m constructed by the HL..25 baselines and We repeat the experiment 10 times and report the aver- coresct of size m conducted by Algorithm 3.
44

---

Our algorithm achieves a speed-up up over 2L specifically. a 2x reduction in the running time on the coresct-while while maintaining the same level of empirical ervor.
ages. The result is listed in Table 6
Validity of Assumption 1.4 for robust k-median. We evaluate the validity of Assumption [.4 for robust k-median across SiX datasets. The results in Table show that the assumptions are satisfied by the Twitter, Adult, Athlete, and Diabetes datasets, while the condition mmax S 4kr holds for all six datasets. These results demonstrate that our assumptions are practical in real-world scenarios, and our algorithm performs well even when the assumption min, [P_ 2 4m is violated. Note that the condition Tmax I 4kF is satisfied by all six real-world datasets, even across different choices of k and m.
Analysis under heavy-tailed contamination. For each dataset, we randomly perturb 10% of the points by adding independent Cauchy (0. 1) noise to every dimension, thereby simulating a heavy- tailed data environment. As shown in Figure 9 our method consistently outperforms the baselines on the robust k-median task, confirming that its superior performance remains stable even under heavy-tailed contamination. For example. on the perturbed Bank dataset, our method achieves coreset of size 600 with an empirical error of 0.044, whereas the best baseline, HLLW25, requires a coreset of size 1300 to reach a higher error of 0.046.
0.04
0.1
0.15
0.08
0.63
0.06
62
0.02
0.04
0.05
0.02
0.01
1000
2000
3000
4000
1000
2000
3000
4000
1000
1500
2000
[M]
(a) Census1990
(b) Twitter
(c) Bank
0.12
Oure
0.3
Oure HJLWES
0.5
Oure HJLW223
0.1
HJLW23
HILLW2S
HLLWSS
0.2
HILLWWS
0.08
0.06
0.1
0.04
0.02
500
1000
1500
2000
100
200
300
400
100
200
300
400
[S]
[S
[S]
(d) Adult
(c) Athlete
(f) Diabetes
Figure 9: Tradoff between coreset size |S] and empirical error E(S) for robust k-median when we
perturb 10% points.
G.4 Empirical results for robust k-means
We implement Algorithm 3 for robust k-means and compare its performance to the previous baselines.
Setup. We do experiments on the six datasets listed in Table 4 and set the number of centers k to be 5. We use k-means++ to compute an approximate center C
Coreset size and empirical error tradeoff' for Robust k-means. We vary the coreset size from m to 2m, and compute the empirical error E(S) w.r.t. the coreset size |S]. For each size and each algorithm, we independently run the algorithm 10 times and obtain 10 coresets, compute their empirical errors E(S), and report the average of 10 empirical errors. Figure 10 presents our results. This figure shows that our algorithm (Ours) outperforms the previous baselines. For example, with the Twitter dataset, our method provides coreset of size 2200 with an empirical error 0.039. The best empirical error achieved by our general dimension method for a coreset size 4000 is much larger, 0.056.
45

---

Table 6: Comparison of runtime between our Algorithm and baseline HLLW25 for robust k-median. For each dataset, the coreset size of baseline HLLW25 2m and the coreset size of ours m. We use Lloyd algorithm given by ? to compute approximate solutions Cp and Cs for both the original dataset P and coreset S, respectively. "COSTp" denotes cost (m)) (P, Cp) the original dataset P. "COSTs" denotes cost, (T*) (P, Cs) on the coreset constructed by METHOD, Tx is the running time on the original dataset. Ts is the running time on coreset. Te is the construction time of the coreset.
DATASET
COSTP
METHÓD
COSTs
Tx
Tc
Ts
OURS
1,030 10
38,862
5.532
CENSUS1990
1.032x10
312.606
HLLWW25
1.040x10
38.703
10.815
OURS
10"
12,220
1.621
TWITTER
1.328x10
96.024
HLLW25
x.347x10
12.452
2.995
OURS
3.194 10"
9.021
1.484
BANK
3.179x10"
147.324
HLLW25
3.207
9.210
3.445
OURS
9.153x10*
9.324
1.854
ADULT
9.221 x00
144.185
HLLW25
9.166x100
9.266
3.517
OURS
7.503 X10"
1.825
0.206
ATHLETE
7.251 x10
41.541
HLLW22
7.389 x10*
1.872
0.421
OURS
8.791x10'
1.829
0.226
DIABETES
8.571x10
44.733
HLLW25
8.811x10'
1.850
0.473
Ours
Ours
HJLWW3
0.22
HJLW23
HJLW2
HLLWW5
HLLW25
0.18
HLLW23
0.1
0.2
0.14
0.16
0.05
0.12
0.14
1000
2000
3000
4000
500
1000
1500
2000
500
1000
1500
2000
[8]
[5]
[8]
(a) Twitter
(b) Adult
(c) Bank
HILL HELLWES
0.6
HLLW25
HILLWSS
0.3
0.4
0.2
0.2
0.1
1000
2000
3000
4000
300
400
(d) Census1990
(c) Athlete
(f) Diabetes
Figure 10: Tradeoff between coreset size |S| and empirical error E(S) for robust k-means.
Statistical test. Similar to the previous cases, we evaluate the statistical performance between our method and basclines for robust k-means on all six real-world datasets. The results, listed in Table 7 further demonstrate that our algorithm consistently outperforms the basclines.
Speed-up baselines. We compare the coreset of size 2m constructed by the HLLW25 baselines and coreset of size m conducted by Algorithm We repeat the experiment 10 times and report the aver- ages. The result listed in Table g Our algorithm achieves speed-up over HLLLW25-specfficn a 2x reduction in the running time on the woreset-while maintaining the same level of empirical error.
Validity of Assumption 1.4 for robust k-means. We evaluate the validity of Assumption T.4 for robust k-maa across six datasets. The results in Table show that our assumptions are satisfied by datasets Athlete and Diabetes, while the assumption max S 4k72 is satisfied by all six datasets.
46

---

Table 7: Statistical comparison of different coreset construction methods for robust geometric median. The coreset S1 represents our coreset, S2 represents the coreset constructed by the baseline H.JL233, and S3 the coreset constructed by baseline HLLW25. For each empirical error ratio {(()) and ((S)))((S), we report the mean value over runs, with the subscript indicating the standard deviation.
Census1999
Twitter ((Sa)/E(S))
Coreset Size
E(S2)/E(S1)
{(S))/E(S))
((S2)/((S)
2200
3.2532.063
2.6451.458
1.7930.614
1.667p.479
3200
1.257 1.3030.60
1.251g.632
1.343o.234 1.2440.152
1.2830.
4200
1.168u.739
1.2466.148
Bank
Adult
Coreset Size
((5))
((Sa)/²(S1)
((S2)/E(S))
((S))/((51)
1200
1. 1.647a.972
1.3601.01s
1.4677.287
1.0944.542
1700
1.010 1o.100.654 1.010p.654
1.028
2. 2.1490.884
2.4161.002
2200
1.026p.674
1.089p.360
1.172u.537
Athlete
Diabetes
Coreset Size
(S2))
{(Ss)/8(S))
((S2)/((S,)
{(Ss)/8(S1)
210
5.1722.634
4.2001.944
5.7003.a03
5.8682.952
310
2.467 1.564
1.427o.660
1.5670.800
1.332
410
1.658g.s81
1.045p.449
1.3601.103
1.216n.943
Table 8: Comparison of runtime between our Algorithm and baseline HLLW25 for robust k-means. For each dataset, the coreset size of baseline HLLW25 2m and the coreset size of ours m. We use Lloyd algorithm given by 7 to compute approximate solutions C'p and Css for both the original dataset and coreset S, respectively. "COST," denotes cost. fmm (P, Cp) on the original dataset P. "COSTs" denotes cost. (17) (P, Cs) on the coreset constructed by METHOD, Tx is the running time on the original dataset. Ts the running time on coreset. Te is the construction time of the coreset.
DATASET
COSTP
METHOD
COSTs
Tx
Tc
Ts
OURS
1.170x 10
35,513
5.770
CENSUS1990
1.172x10
358.218
HLLW25
1.170x10"
35.399
1 11.043
OURS
2.664x10'
14.084
1.806
TWITTER
2.657x107
106.327
HLLW25
2.662x10*
13.330
3.494
OURS
3.5
7.478
1.283
BANK
3.477x10*
133.978
HLLW25
3.530x
7.225
2.725
OURS
2.646x10'5
8.273
1.564
ADULT
20
139.16
HLLW25
2
8,048
3.091
OURS
9.089x10*
1,890
0.251
ATHLETE
8.630x10'
44.208
HLLW25
9.016x10*
1,909
0.466
OURS
6.814x
1.622
0.196
DIABETES
6.490x10*
39.570
HLLW25
6.838x10
1.602
0.413
These results show that assumptions are practical in real-world datasets, and our algorithm performs well even when the assumption min; [P" > 4m is violated.
Analysis of our algorithm when Assumption 1.4 violates. We evaluate the applicability of our algorithm when both assumptions min; PM 4m and (Fmax/ /T)2 < 4k are violated. Bank dataset, we let &o 3, then we have (Fmax/ F) 15.001 > 4k and min; PP' = 1432 < 4m, violating the two assumptions. 36.278 > 4k and min; P 1592 < 4m, violating the two assumptions. We present the size-error tradeoff for robust k-means on these datasets Figure [1 Our results show that our method still outperforms the baselines even when both assumptions violated.
Adult dataset, we let l m 500, then we have (Fmax/F)²
47

---

0.14
Ours
0.2
Ours
0.12
HJLW23
HJLW23
HLLW25
HLLW25
0.1
0.15
0.08
0.1
0.06
0.04
0.05
500
1000
1500
2000
500
1000
1500
[S]
[S]
(a) Bank
(b) Adult
Figure 11: Tradcoff between coreset size |S| and empirical error E(S) for robust k-means. We
k = 3 in the Bank dataset and set k = 8, m = 500 in the Adult dataset. In these cases, the values (Tuax/ / and min [P:"] violate both of our assumptions. The goal of this figure is examine whether our algorithm remains applicable when the assumptions are not satisfied.
Analysis under heavy-tailed contamination. For each dataset, randomly perturb 10% of the points by adding independent Cauchy (0, 1) noise to every dimension, thereby simulating heavy- tailed data environment, As shown in Figure 12, method consistently outperforms the baselines on the robust k-means task. For example, on the perturbed Athlete dataset, our method yields coreset of size 110 with empirical error of 0.181, whereas the best baseline, HLLW25, attains higher eтror of 0.196 even with a larger coresct of size 290.
0.12
0.2
Oura HJLW223
Oura HULWWS
Ours HJILW29
0.1
HLLW2E
0.15
HILLWES
HLLW25
0.08
0.1
0.08
V
0.04
0.05
1000
2000
5000
4000
1000
2000
3000
4000
1000
1500
2000
(S)
[S]
(a) Census1990
(b) Twitter
(c) Bank
HJLW23
HJLW23 HLLW2S
HJLW23
W/25
HILL W22
30
0.2
500
1000
1500
2000
100
200
300
400
100
200
300
400
[5]
(d) Adult
(e) Athlete
(0 Diabetes
Figure 12: Tradoff between coreset size |S| and empirical error ((S) for robust k- m-masss when we perturb 10% points.
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
In Section I.1 we list the contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and empirical results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The Theorems I.3 and 1.5 demonstrate that our coreset size is not tight for
d 1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
49

---

Justification: In Section 1.1 we present each theorem's 's assumptions and cite their formal definitions. Sections and F.2 list the lemmas required to prove the theorems.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. empirical result reproducibility
Does the paper fully disclose all the information needed to reproduce the main empirical results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
and present the methods used in our experiments. The corresponding code is provided in the supplementary material.
Justification: Algorithms I 2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
50

---

Question: Does the paper provide open access to the data and code, with sufficient in- structions faithfully reproduce the main empirical results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide our code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Plea the NeurIPS code and data submission guidelines (https::/nips.cc///
Suidess/CodeSubmissaa ssionoocccii for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ mrips..c//ublic/guuddee CooeeSumeeeeeeeeeeeeee isi iesioniycccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all empirical results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We demonstrate the parameters of datasets in Table
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In Section 4 report the empirical error across different coreset sizes for robust geometric median on each dataset. We list the results the statistical significance
experiments in Tables 1 and 7
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
51

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We list out the compute resources in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
Our research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper mainly propose the theoretical results, which has no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
52

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Table listts the sources of our datasets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
53

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
54

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy hateap///eerrpppc.cc///ofeeerers for what should or should not be described.
55


Reviews:
[{"review_id": "fBnRxsHyIj", "reviewer": "Reviewer_y1bN", "summary": "Let P be a set of n points in R^d, m>1 and epsilon>0. Given a center c in R^d, we denote by cost^m(P,c) the sum of Euclidean distances over the points of P to c, excluding the m farthest points.\n\nThe main result is a randomized algorithm that gets P, m>1 and epsilon>0, and return a subset of size ~d/epsilon^2 that approximates cost^m(P,c) to every given c in R^d, up to a multiplicative factor of 1+epsilon. It is independent of $m$.\nFor d=1, the size is ~1/sqrt(eps)+m/(epsilon * n).\nThere are also some generalization to k-means with more assumptions,", "questions": "- Can you commit to an open code upon acceptance?\n- What is the definition of \\tilde{O}?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strong:\n- This is a very fundamental problem that would probably affect many other types of related coresets in many areas.\n- Unlike previous coresets, the size is independent of m.\n- The theory seems correct and interesting.\n- The technique is novel, at least to me.\n- Code in C++.\n\nWeak:\n- \\tilde{O} is undefined, although it is used everywhere, including the main theorem.\n- Assumption F6 is critical but appears only in the appendix. It is not clear, since most of the terms there (i,r,Pi) are undefined.\n- A single center seems easy and less interesting then k-median/mean.\n- Paper [1] is not cited, although it is one of the few papers that handle this problem.\n- It was very hard to understand the pseudo-code. I Some figures would have helped.\n- Put points on the curves, when you actually made the experiment.\n- Datasets: Does it make sense to run your algorithm on these datasets? For what purposes?\n\n[1] article{DBLP:journals/algorithms/StatmanRF20,\n  author       = {Adiel Statman and\n                  Liat Rozenberg and\n                  Dan Feldman},\n  title        = {k-Means: Outliers-Resistant Clustering+++},\n  journal      = {Algorithms},\n  volume       = {13},\n  number       = {12},\n  pages        = {311},\n  year         = {2020},\n  url          = {https://doi.org/10.3390/a13120311},\n  doi          = {10.3390/A13120311},\n  timestamp    = {Sat, 09 Jan 2021 14:14:06 +0100},\n  biburl       = {https://dblp.org/rec/journals/algorithms/StatmanRF20.bib},\n  bibsource    = {dblp computer science bibliography, https://dblp.org}\n}", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and for acknowledging the significance, correctness, and contributions of our work. We truly appreciate your detailed suggestions.  \n\nIn response to your concerns regarding paper presentation and code availability, we will (i) move Assumption F.6 to the main body and include the definition of $(i,r,P_i)$, (ii) add illustrative figures to accompany the pseudo-code, (iii) include markers on the curves for clarity, and (iv) release the code publicly upon acceptance. \n\nBelow we address your specific questions.\n\n\n> What is the definition of $\\tilde{O}$?\n\n\nThank you for your question. The notation $\\tilde{O}(n)$ denotes $O(n \\cdot \\text{polylog}(n))$. For example, our coreset size upper bound $\\tilde{O}(\\varepsilon^{-2}\\cdot \\min  \\\\{\\varepsilon^{-2}, d \\\\})$ in Theorem 1.3 (Line 105) hides a polylog$(\\frac{1}{\\varepsilon},d)$ factor. \n\nWe will add a footnote in the final version to clarify this notation.\n\n\n> Paper [1] is not cited, although it is one of the few papers that handle this problem.\n\nThank you for pointing this out. We apologize for missing this citation. \n\n* [1] provides an $O(\\log (k+m))$-approximation for robust $k$-median or $k$-means in $O(n)$ time by constructing a weak coreset of size $O(k+m)$. This is a time-efficient algorithm for robust clustering, while its approximation ratio is not constant. \n\n* [1] also proposes an $\\varepsilon$-coreset for robust $k$-median or $k$-means of size $O((1/\\varepsilon)^d (k+m)\\log n)$. This size contains exponential dependence on $d$, much larger than our size $\\tilde{O}(k^2 \\varepsilon^{-2} \\cdot \\min\\\\{\\varepsilon^{-2}, d\\\\})$.\n\nWe will cite this paper in Section 1 in the final version.\n\n\n> Datasets: Does it make sense to run your algorithm on these datasets? For what purposes?\n\nThank you for raising this question. The choice of these datasets aim to show our proposed methods consistently outperform the baselines [39, 40], across a range of scales ($10^4$–$10^5$), dimensions (2–68), and diverse domains (such as social network data, demographic data, and disease data). Moreover, these datasets cover those used in baseline [39], increasing the fairness in the comparison. Empirical results demonstrate the robustness of our methods' outperformance relative to the baselines.\n\nWe will clarify the criterion for selecting these datasets in the final version.\n\n\nThank you again for your comments, which have helped us enhance the clarity of our results and the quality of our references."}, {"review_id": "QgOa0h0lXg", "reviewer": "Reviewer_n7bA", "summary": "This paper addresses the problem of constructing coresets for the robust geometric median in Euclidean space $\\mathbb{R}^d$. The key innovation is a method that removes the dependence on the number of outliers $m$ in the coreset size, which was a central limitation in prior works. The authors achieve this through a novel non-component-wise error analysis, leading to a coreset of size $\\tilde{O}(\\varepsilon^{-2} \\cdot \\min\\{\\varepsilon^{-2}, d\\})$ when $n \\geq 4m$. For $d = 1$, they obtain an optimal bound of $\\Theta(\\varepsilon^{-1/2} + \\frac{m}{n} \\varepsilon^{-1})$. The paper extends the results to robust $(k,z)$-clustering in various metric spaces. In terms of theoretical novelty, the paper introduces a novel non-component-wise error analysis, which enables a substantial reduction in the influence of outliers. The authors also provide empirical results on real-world datasets showing improved size-accuracy trade-offs and runtime.", "questions": "1. Does the proposed non-component-wise error analysis can be generalized to other robust learning tasks, such as robust regression or PCA, or is it fundamentally specific to clustering-like cost functions?\n\n2. How does the proposed method perform when the assumption $n \\geq 4m$ is violated in a controlled way?\n\n3. How does the coreset behave under adversarial or heavy-tailed conditions for the datasets? \n\n4. Is it possible to construct an $\\varepsilon$-coreset for the robust geometric median (or more generally, robust $(k,z)$-clustering) in high-dimensional Euclidean space $\\mathbb{R}^d$ with optimal or near-optimal size, without relying on uniform sampling of outliers or the ball range space framework—perhaps via alternative geometric or combinatorial constructions?", "limitations": "The main theoretical results rely on the assumption $n \\geq 4m$, which may not hold in many practical scenarios, and the coreset bounds for $d > 1$ are not tight. The analysis depends on structural properties such as bounded VC-dimension, but the sensitivity of the method to violations of these assumptions is not studied. Computational aspects, including the overhead of constructing the coreset and its scalability to large-scale or streaming settings, are not addressed. The generalization to robust $(k, z)$-clustering is stated but not formally supported. Overall, the novelty of this paper is incremental and lacks thorough and extensive theoretical comparison, empirical validation, and contextualization within the broader literature.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 1, "strengths_and_weaknesses": "$\\mathbf{Strengths}$: \n1. The paper is technically sound and presents significant theoretical advancements. The proposed non-component-wise error analysis is an elegant departure from prior component-wise methods, and the theoretical claims are backed with detailed proofs and matching lower bounds.\n\n2. The paper is well-organized and offers a detailed exposition of the techniques. However, clarity suffers due to occasional overuse of notation and a lack of high-level intuition in the main text. The manuscript would benefit from more concrete examples or illustrations, especially to help interpret the new error analysis approach.\n\n3. The elimination of $O(m)$ dependency is a notable contribution to the literature on robust coreset construction. However, the improvement is restricted to the regime where $n \\geq 4m$. Moreover, the practical impact is limited by the modest empirical gains over strong baselines. \n\n\n$\\mathbf{Weakness}$:\n\n1. The paper lacks a comparison with recent state-of-the-art literature such as Ding, H. and Wang, Z., 2020; Paul, D. et. al., 2021; Cohen-Addad, V. et. al., 2022 and related coreset literature. These should be included to better contextualize the contribution.\n\n2. The empirical section is limited in scope. While results are presented across 6 datasets, there is insufficient analysis on the robustness of the proposed methods under adversarial or heavy-tailed distributions.\n\n3. The paper makes some strong assumptions (e.g., $n \\geq 4m$, existence of VC-dimension bounds) but does not clearly discuss their practical validity or limitations.\n\n4. While the paper claims that the proposed methodology generalizes to broader robust clustering applications, this generalization is not rigorously substantiated—neither through theoretical guarantees nor through empirical demonstrations on such tasks.\n\n\n$\\mathbf{References:}$\n\nDing, H. and Wang, Z., 2020, November. Layered sampling for robust optimization problems. In International Conference on Machine Learning (pp. 2556-2566). PMLR.\n\nPaul, D., Chakraborty, S., Das, S. and Xu, J., 2021. Uniform concentration bounds toward a unified framework for robust clustering. Advances in Neural Information Processing Systems, 34, pp.8307-8319.\n\nCohen-Addad, V., Larsen, K.G., Saulpic, D. and Schwiegelshohn, C., 2022, June. Towards optimal lower bounds for k-median and k-means coresets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1038-1051).", "was_revised": true, "final_justification": "Thanks for your responses. My concerns for all the experiments have been addressed. The theoretical bottlenecks are still there and that makes the contributions somewhat limited. I am happy to raise the score to 4.", "rebuttal": "Thank you for your feedbacks and detailed suggestions. We appreciate your recognition of the soundness, presentation, and contribution of our work.  \n\n> Q1: Does the proposed non-component-wise error analysis can be generalized to other robust learning tasks, such as robust regression or PCA, or is it fundamentally specific to clustering-like cost functions?\n\nThank you for the insightful question. To the best of our knowledge, existing coreset methods for robust PCA and robust regression do not partition the dataset into components but take samples from the entity (e.g., [26]). This makes it challenging to directly apply our non-component-wise error analysis to robust regression or PCA. \n\n\n> Q2: How does the proposed method perform when the assumption $n\\ge 4m$ is violated in a controlled way?\n\nThank you for this valuable question. Suppose $n< 4m$.\n* Theoretically, the proposed method does not guarantee to produce a coreset. This is because when $n - m = o(n)$, the coreset size for the robust geometric median is $\\Omega(m)$ (Theorem 1.1). Thus, the assumption $n\\ge 4m$ is necessary (up to a constant factor) for our coreset construction.\n* In practice, our method continues to outperform the baselines when $n =2m$ (Figure 5, Section G.1), demonstrating the robustness of our method.\n\n\n> Q3: How does the coreset behave under adversarial or heavy-tailed conditions?\n\nThank you for raising this question. We do the following experiment accordingly:\n\nOn the **Census1990** dataset, we fix outlier number $m = 2000$ and randomly perturb 10% of the points by adding i.i.d. Cauchy(0,1) noise, simulating heavy-tailed contamination. Our method outperforms baselines on this perturbed dataset, demonstrating the robustness of our method’s outperformance. For example, our coreset of **size 900** achieves an empirical error of **0.018**, while the best baseline error is **0.020** when the size is **2200**.\n\nWe will include this experiment in the final version.\n\n> Q4: Is it possible to construct an $\\varepsilon$-coreset for the robust geometric median (or more generally, robust (k,z)-clustering) in high-dimensional Euclidean space $\\mathbb{R}^d$  with optimal or near-optimal size, without relying on uniform sampling of outliers or the ball range space framework—perhaps via alternative geometric or combinatorial constructions?\n\nThank you for raising this point. Achieving near-optimal robust coreset sizes in high-dimensional Euclidean spaces via geometric or combinatorial constructions is indeed challenging. This difficulty arises primarily due to the increased complexity in the distribution of candidate centers, which complicates geometric partitioning strategies. For example, [15] employs an $\\varepsilon$-net to partition the space, but this approach incurs an exponential factor of $O(\\varepsilon^{-d})$ in the coreset size (see Lines 212–215). To the best of our knowledge, the current state-of-the-art coresets for both vanilla and robust geometric median problems are derived through sampling-based methods.\n\n\n\n> concrete examples or illustrations ... new error analysis approach.\n\nThank you for this insightful comment. We agree that a concrete example can largely improve the clarity of our new error analysis approach. Below we specify one: Let $P=P_1\\cup P_2$ where $P_1=\\\\{p_1,\\ldots,p_{n-m}\\\\}$ with $p_i = \\frac{i}{n}$ and $P_2=\\\\{p_{n-m+1},\\ldots,p_n\\\\}$ with $p_i = n^{3(i-n+m)}$ (see also Appendix A.3). \n\n* Algorithm 1 decomposes $P_2$ into at most $O(\\varepsilon^{-1})$ buckets $B_i$, where each bucket contains $\\varepsilon n/16$ points, and collects their mean points $\\mu(B_i)$ in the coreset $S$.\n\n* Let $B=\\\\{p_l,\\ldots,p_r\\\\}$ be a bucket within $P_2$. Let center $c=p_l=n^{3j}$. Since $p_l$ is an inlier point of $P$  w.r.t. $c$, the outlier number of $B$ w.r.t. $c$ must be $|B|-1$.\n\n* In the component-wise analysis, the induced error of bucket $B$ is $\\left|\\text{cost}^{(|B| - 1)}(B, c) - |\\mu(B) - c|\\right|$, which is at least $\\text{dist}(\\mu(B), c) = \\Omega(n^{3(j+1)})$. However, $\\text{cost}^{(m)}(P,c)$ is approximately $(n-m)\\cdot 3^j \\ll \\text{dist}(\\mu(B), c)$, which implies that the induced error substantially exceed the coreset error bound.\n\n* In contrast, in our non-component-wise analysis, the induced error of bucket $B$ is 0. This is because we allow the misaligned outlier numbers in each bucket. Since $\\text{dist}(\\mu(B),c) \\gg \\text{dist}(p,c)$ for any point $p \\in P_1$, $\\mu(B)$ will be totally regarded as an outlier w.r.t. $c$. As a result, $B$ contributes zero error.\n\n* Thus, non-component-wise analysis significantly reduces bucket-wise errors in this example, which is crucial for proving $S$ is a coreset.\n\nWe will add this example to the appendix in the final version.\n\n\n\n> modest empirical gains over strong baselines.\n\nThank you for raising this point. Below we summarize the empirical gains of our method over baselines:\n\n* **Smaller coreset size at same error**: Our method reduces the coreset size by **25%–45%** compared to baselines when achieving the same empirical error. For instance, on the **Census1990** dataset, our method achieves an empirical error of **0.012** while saving **28.6%** of the data relative to the baselines (see Lines 324–329).\n\n* **Consistent improvement across datasets**:  This size improvement consistently holds across diverse datasets across different data scales ($10^4$–$10^5$), dimensions ($2$–$64$), and diverse domains (including social network, demographic, and disease data)\n\n* **Smaller than $m$ coreset size**:\n  Unlike baselines, which require a coreset of size at least $m$, our method can achieve the same level of error with a coreset size **smaller than $m$**.\n  For example, on the **Census1990** dataset with $m = 2000$:\n  * Our method yields a coreset of **size 600** with an empirical error of **0.021**\n  * The best baseline needs **size 2300** to achieve a worse error of **0.022**\n\n  This highlights the strength of our method, especially in settings with **many outliers**.\n\nWe will include this new empirical result in the final version.\n\n\n> lacks a comparison with recent state-of-the-art literature ...\n\nThank you for suggesting these references. \n* [Ding and Wang (2020)] propose a layered sampling framework that constructs a weak coreset of size $\\tilde{O}(kd\\varepsilon^{-2}) + (1+\\varepsilon^{-1})m$ in $O(nkd)$ time. \n* [Paul et al. (2021)] propose an iterative algorithm for robust clustering.\n* [Cohen-Addad et al. (2022)] has been discussed in Lines 46–47.\n\nIn comparison, our paper focuses on (strong) coreset construction for robust clustering, which differs in objective from their works. We will cite these references in the Section 1 of the final version.\n\n\n\n> The paper makes some strong assumptions (e.g., , existence of VC-dimension bounds) but does not clearly discuss their practical validity or limitations.\n\nWe apologize for any confusion. \n\n* Theorems E.11, E.12 work for any VC-dimension, just the coreset size is proportional to the VC dimension. We will remove the sentence \"if the VC dimension $d_{VC}(\\mathcal{X})$ is bounded\" in Theorem E.11.\n\n* VC-dimension bounds are often known [9, 18, 40]: \n  * For general metric space $\\mathcal{X}$, its VC-dimension is $O(\\log|\\mathcal{X}|)$.\n  * For shortest-path metric of a graph with bounded treewidth $t$, its VC-dimension is $O(t)$.\n  * For shortest-path metric of a graph that excludes a fixed minor $H$, its VC-dimension is $O(H)$.\n\n\nWe will clarify this in the final version.\n\n\n> Computational aspects, including the overhead of constructing the coreset and its scalability to large-scale or streaming settings, are not addressed. \n\nThank you for raising these important points. \n\n**Computational overhead.**\nThe overhead for constructing our robust coresets is efficient.\n\n* **Robust 1D geometric median (Algorithm 1):** The construction takes $O(n)$ time, as detailed in Section D (Lines 1020–1026).\n* **Robust geometric median (Algorithm 2):** The overall complexity is dominated by one step that takes $O(nd)$ time, making the total overhead $O(nd)$.\n* **Robust $(k,z)$-clustering (Algorithm 3):** The total complexity is **$O(nkd)$**, with the dominant step detailed in Theorem F.7.\n\n**Scalability to large-scale data.** \nWe measure scalability by the practical speed-up achieved when running downstream algorithms on the coreset versus the full dataset. Our empirical results in Table 1 show that using our robust coresets provides a 7x-10x speed-up in computation time while maintaining high accuracy, demonstrating its practical scalability.\n\n**Streaming Settings**\nExtending robust coresets to a streaming model is a valuable but challenging future direction. The primary difficulty is that our robust coreset may not satisfy the mergeability property—a key requirement for most streaming algorithms—due to the complex ways noise and outliers can interact across different data chunks.\n\nWe will add this discussion on computational overhead and scalability to the main paper and explicitly list the streaming setting as an important direction for future work.\n\n> The generalization to robust (k,z)-clustering is stated but not formally supported.\n\nThe formal definition and supporting proofs for robust $(k,z)$-clustering can be found in Appendix F. \n\n\nThank you for your thoughtful comments, which have helped us improve the clarity and empirical reach of our work."}, {"review_id": "GTohzk1wkD", "reviewer": "Reviewer_NhxZ", "summary": "This paper studies the robust geometric median problem in the d=1 and general d case, and provides improved results for coresets in these settings.  For d=1 their algorithm polynomially reduces the dependence on the error term eps, removes the dependence on the number of outliers m, and is tight up to poly-logarithmic factors.  For the general d case, they use the insight from the d=1 case to make a simple and clever adaptation of previous results, and this also improves the previous results by removing the dependence on the number of outliers m.  \nThese results extend to provide improved results for robust (k,z)-clustering.  \nExperiments are provided to show on real data the improvement in size/error trade-off on previous robust-median coresets algorithms.", "questions": "N/A", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I found the new methods and analysis relatively simple, but it improves the results which appeared in STOC, SODA, ICALP, FOCS in the last few years -- in that it removes the dependence on the number of outliers.  I appreciate the simple analysis, it is a positive.  And removing the dependence on the number of outliers is an important improvement.  \n\nThe topic of coresets, and clustering, and robust estimators are all very relevant for NeurIPS, so since this is an important improvement, I think the paper should be accepted.  \n\nI found the writing to be formal, and no errors or concerned, but a bit dense.  I appreciate the Figure 1, but I did not find it very well labeled.  \n\nI was glad to see the experiments, even though it is a theory paper.  They convinced me that the improvements were meaningful.", "was_revised": true, "final_justification": "Clear and nice theoretical results on a problem central to NeurIPS (clustering for coresets).  The new methods are simple -- this is a good thing.  Shows real improvement in simple experiments, so seems a real improvment, not just theoretical.", "rebuttal": "Thank you for your positive feedback and for recognizing both the significance of our contributions and the strength of our experimental results. We also appreciate your comment regarding Figure 1's labeling; in the final version we will enhance the axis titles, legend descriptions, and in-figure annotations to ensure it is fully self-explanatory."}, {"review_id": "aSFWqsVZVG", "reviewer": "Reviewer_sFeV", "summary": "The paper proposes improved coreset constructions for the robust geometric median problem that remove the dependency on the number of outliers. It also extends to robust $(k, z)$-clustering and shows strong empirical performance.", "questions": "1. **Presentation Alignment:** Several figures, tables, and algorithm blocks are not placed near the corresponding explanatory text. Reorganizing the layout so that each element appears closer to the relevant discussion would significantly improve readability and reader comprehension.\n\n2. **Structure of Experimental Results:** Key experimental results are currently not sufficiently highlighted in the main text. Could the authors restructure the paper to better emphasize these results in the main body, rather than relegating them to the appendix or supplementary material?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Quality:**\nThe paper appears technically sound, with well-defined theoretical contributions and empirical validation across multiple datasets. The improvements over prior work, particularly in terms of coreset size and runtime efficiency, are clearly articulated and seem well-supported by both analysis and experiments.\n\n**Clarity:**\nThe manuscript is generally clear and well-organized. However, there are some presentation issues—specifically, the placement of figures, tables, and algorithm blocks could be more closely aligned with the corresponding narrative. Additionally, the structure of the paper could be improved to highlight key experimental results more prominently in the main body, rather than deferring them to the appendix or supplementary materials.\n\n**Significance:**\nThe problem of robust coreset construction for geometric median and $(k, z)$-clustering is important for scalable learning. The elimination of outlier dependency and the extension to general metric spaces indicate potential for meaningful impact in both theory and practice.\n\n**Originality:**\nThe work introduces a novel non-component-wise error analysis technique and achieves theoretical and empirical improvements over existing methods. These contributions appear to be a non-trivial and original step forward in the field.", "was_revised": true, "final_justification": "The authors have adequately addressed my concerns. I will maintain my current recommendation.", "rebuttal": "Thank you for your positive assessment of our work’s quality, clarity, significance, and originality. In response to your feedback, we will improve the paper’s organization for better readability and move key experimental results from the appendix into the main text to enhance accessibility.\n\n> Presentation Alignment: Several figures, tables, and algorithm blocks are not placed near the corresponding explanatory text. Reorganizing the layout so that each element appears closer to the relevant discussion would significantly improve readability and reader comprehension.\n\nThanks for your comment. We will do this to improve readability in the final version.\n\n> Structure of Experimental Results: Key experimental results are currently not sufficiently highlighted in the main text. Could the authors restructure the paper to better emphasize these results in the main body, rather than relegating them to the appendix or supplementary material?\n\nThank you for your question. Yes, we will move the experimental results on the robust geometric median to the main text, including:\n\n* **Statistical test (Table 4):** Results show that our coreset consistently achieves lower empirical error than the baselines across six datasets, demonstrating the consistency of our method’s outperformance.\n* **Analysis for $n < 4m$ (Figure 5):** Results indicate that our coreset remains effective even when the assumption $n \\geq 4m$ is not satisfied, highlighting the robustness of our method.\n* **Size-error tradeoff for 1D case (Figure 6):** Results show that our 1D method consistently outperforms the baselines for the robust 1D geometric median.\n\nIncorporating these results into the main text will enhance the integrity of the experiments presented in the main text.\n\nThank you again for your comments. To further improve the paper’s presentation, we will also move Assumption F.6 to the main text and add figures to illustrate the pseudo-code."}]

Author rebuttal:

Meta-review: This paper proposes ways to construct improved coresets for the robust geometric median problem, which also applies to the general problem of (k,z) clustering and to general metric spaces. The reviewers largely agree on the positive aspects of the paper, and find the empirical examples a helpful validation of a largely theoretical work. The paper focuses on a analysis that allows for the coreset size to be independent of the outlier count, and to the best of my knowledge, the analysis that is not component-based is novel and leads to tighter bounds than existing techniques. The contributions address a timely topic and reviewers agree on the merits of the work, though it will be improved with consideration for their constructive criticisms, including comments on notation, missing references, etc.
Decision: Accept (poster)