Coresets for Clustering Under Stochastic Noise
Authors: Lingxiao Huang
Zhize Li
Nisheeth K. Vishnoi
Runkai Yang
Haoyu Zhao
Venue: NeurIPS 2025 poster ()
Keywords: coreset
clustering
stochastic noise
error metrics
Primary area: theory
TL;DR: We propose a new error metric for constructing coresets in \$(k,z)\$-clustering with noisy data, leading to smaller coresets, stronger theoretical guarantees, and improved empirical performance compared to classical methods.

Abstract: We study the problem of constructing coresets for $(k, z)$-clustering when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of a coreset is inherently challenging, as the true underlying dataset is unobserved. To address this, we investigate coreset construction using surrogate error metrics that are tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new error metric that more closely aligns with the true cost. Although our metric is defined independent of the noise distribution, it enables approximation guarantees that scale with the noise level. We design a coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an $\varepsilon$-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metrics. In particular, we prove that the coreset size can improve by a factor of up to $\mathrm{poly}(k)$, where $n$ is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.

Coresets for Clustering Under Stochastic Noise
Lingxiao Huang' Nanjing University
Zhize Li Singapore Management University
Nisheeth K. Vishnoi Yale University
Runkai Yang
Haoyu Zhao
Nanjing University
Princeton University
Abstract
We study the problem of constructing coresets for (ks, 2) >llcstrennn when the input dataset is corrupted by stochastic noise drawn from a known distribution. In this setting, evaluating the quality of coreset inherently challenging, the true underlying dataset is unobserved. To address this, we investigate coreset construc- tion using surrogate error metrics that tractable and provably related to the true clustering cost. We analyze a traditional metric from prior work and introduce a new eπrоr metric that more closely aligns with the true cost. Although our metric is defined independently of the noise distribution, it enables approximation guarantees that scale with the noise level. We design coreset construction algorithm based on this metric and show that, under mild assumptions on the data and noise, enforcing an s-bound under our metric yields smaller coresets and tighter guarantees on the true clustering cost than those obtained via classical metries. In particular, we prove that the coreset size can improve by factor up to poly where n is the dataset size. Experiments on real-world datasets support our theoretical findings and demonstrate the practical advantages of our approach.
Introduction
Clustering is a foundational tool in machine learning, with applications ranging from image seg- mentation and customer behavior analysis to sensor data summarization [67, 80, 5, 20]. An im- portant class of clustering problems is called (k: z)
the goal is to find (),,))CCUuse -LLUSTERRG where, given a dataset P C Rd C Idd of l points that minimizes the cost cost, () = Exero d (Ix C.). Here d (xx C) = min {d (d, c) : c C} is the distance of x to the center set C' and d denotes the z-th power of the Euclidean distance. Examples of (k: 2)- CLUSTERING include k-MEDIAN (when the dataset P is large. and it is desirable to have small representative subset that requires less storage and computation while allowing to solve the underlying clustering problem. Coresets have been proposed as solution towards this [48] a coreset is a subset S C P that approximately preserves the clustering cost for all center sets. Coresets have found further applications in sublinear models, including streaming [48, 16], distributed [8, 56), and dynamic settings [5] 1]] due to the ability to merge and compose them (see, e-g. [83, Section 3.3]).
of n points and a k
1) and k-MEANS (when z 2). In many applications.
Yet, a critical limitation of existing coreset constructions their reliance on exact, noise-free data- condition rarely met in practice. In practical applications, data is frequently corrupted by measurement eиror, transmission artifacts, or deliberate noise insertion for privacy and robustness. One reason is that the measurement process may itself introduce noise into the data, or corruption may occur during
Alphabetical order. Conrespondence to: nisheeth. vishnoi@gmail. com com
huanglingxiaoonjju edu, en, thizeli@smi eeu.mmeedd..s. edu.sg,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

the recording or reporting processes [46, 3, 75, 58]. Further, noise can be introduced intentionally in data due to privacy concerns [44, 31, 43], or to ensure robustness [84, 66]. In these scenarios, instead of the true dataset P. one observes a noisy dataset P C IR Various types of noise can emerge depending the context: stochastic noise, adversarial noise, and noise due to missing data [7, 11,11.. 58].
The degree of knowledge about the noise may range from complete uncertainty to full specification of its distributional parameters. Stochastic noise, in particular, has been studied in problems such as clustering [58] and regression [81], and is commonly encountered in fields like the social sciences [12, 72, 39], economies [34], and machine learning [31, 84, 66]. When the attributes of data interact weakly with each other, independent and additive stochastic noise is considered [86, 40, 65]. In such case, for each point p E P and every attribute j E [d], the observed point is P; = Pj + Sp.j where Ep. is drawn from a known distribution Dj. Various choices for D; have been explored, including Gaussian distribution [77, 49], Laplace distribution [17], uniform distribution [3. 74), and Dirac delta distribution [87]. Such noise can reflect inherent individual variability for example, fluctuations in STEM scores across repeated exams [12. 72), where the mean and variance can be estimated by multiple exams, from employers making decisions based statistical information about the groups individuals belong to [34]. In settings focused on privacy or robustness, noise with known parameters might be deliberately added data, such as the use of i.i.d. Gaussian noise in the Gaussian mechanism [30], or the introduction of i.i.d. Gaussian noise to enhance robustness against adversarial attacks in deep learning [84, 66]. The noise level might also be well known or estimable when data is collected using sensors [73, 79]; see Sections 2 and B.2 for further discussions. Numerous studies have examined the effects of modeled noise, specifically Gaussian noise [85, 58], on clustering tasks [29, 42, 58]. They analyze the relationship between the level of noise and the performance of clustering algorithms, showing that a small amount of noise can actually benefit centroid-based clustering methods [58].
Given the widespread use of coresets in clustering problems, it is crucial explore the possibility of constructing compact coresets that remain effective in the presence of noise. The effectiveness of a coreset S is usually measured via the approximation quality of S's optimal center set C(S) in P:
rr()()) = mill =l cost, (P.C)
cost, (P.C(S)
(P.(())) OPT
In the noise-free setting, challenges for evaluating quality ry (C(S) lie in the computation of the optimal clustering cost OPT p. which is NP-hard. To address this, one traditionally considers a surrogate error metric that bounds the maximum (over all possible center sets) ratio [36, 24]:
Err(S, P) = suPocR4|j0==& (S.) (8,C)
(2)
This ratio, serving as an upper bound for (r((r(S)) (see Section 2), helps derive the minimum size necessary for coreset construction. There is long and productive line of work focused on analyzing
the optimal tradeoff between the coreset size |S] and the associated estimation error [21, 22, 55] in
the noise-free setting. However, in the noisy setting, there is an additional challenge for evaluating Tp (C(()))): the true underlying dataset P is unobservable. This leads to a natural question: Can the traditional surrogate error Err guide coreset construction when the observed data is noisy?
Our contributions. We study the problem of coreset construction for clustering in the presence of noise. Motivated by the applications mentioned above, we consider a stochastic additive noise model where each D, (as defined earlier) is parameterized by known noise-level 0, constrained by a bounded-momed measure for coreset construction to this noise model, along with a bound for the coreset's i quality TP(C(S) (Theorem 3.1). To our knowledge, this is the first result to study how coreset performance degrades under noise. We show that Err can significantly overestimate coresct error under noise, resulting in overly pessimistic guarantees (Section 2).
condition (see Definition 2.1). Our first result is adapting the use of the Err
To address this limitation of using Err, we introduce new surrogate metric Err., termed approximation-ratt (Equation (6)). Using this new metric, we design cluster-wise sampling algorithm (Algorithm 1) that partitions the given noisy dataset into l clusters and takes a uniform sample from each cluster. We show that, under natural and necessary assumptions on P. this new algorithm yields smaller coresets (by a factor of up to poly and tighter quality guarantees for (P()()) (Theorem 3.3). These improvements hinge on distinguishing the influence of noise on the clustering cost and the location of the optimal center set C(S), and may be of independent interest.

---

Empirical results, in Section 4, support our theoretical findings even for datasets that do not meet the assumptions required by our theoretical analysis (see, e.g., Table 1), and in scenarios involving non-i.i.d. noise across dimensions (see, e.g., Table 7). Overall, our algorithm effectively generates small coresets with theoretical quality bounds, which can be integrated into clustering frameworks, enhancing robustness in noisy environments.
2
Noise models and metrics for coreset quality
This section formalizes the noisy data models we consider, defines the ideal (but unobservable) metric for coreset quality, and introduces two surrogate metrics-Err (standard) and Err,, (ours). We compare their behavior under noise and motivate our new construction.
Noise distribution and models. Given a probability distribution D on I with mean and variance a², D is said to satisfy Bernstein condition [15, 14, 33] if there exists some constant that for every integer 2 3. Ex-D ||X - =d|]] S filo i = 3, 4,... This condition imposes an upper bound on each moment of D, allowing control over tail behaviors, and we consider such noise distributions in this paper. Several well-known distributions satisfy the Bernstein condition, including the Gaussian distribution, Laplace distribution, sub- Gausssasian distributions, sub-ex cub-exponential distributions, and so on [82]; see Section B.1 for a discussion. We begin with a probabilistic noise model that reflects real-world data corruption: with some probability, each point either remains untouched or receives independent additive noise on each coordinate.
such
Definition 2.1 (Noise model I). Let 0 E [0, 1] be a noise parameter and Dı,..., Da be probability distributions on I with mean O and variance 1 that satisfy the Bernstein condition. 2 Every point (p E P) is i..dd drawn from the following distribution: 1) with probability 1 1 0, ğ = p; 2) with probability 0, for every [d]. D. Pj + Ep.s where Ep.j is drawn from Dj.
When 0 0, P P and 0- P becomes increasingly noisy, Note that this noise model roughly selects a fraction 0 of underlying points and adds an independent noise to each feature j E [d] that is drawn from a certain distribution D,.
We also consider the following model, called noise model II: For every E [n] and j E [d] Pi. Pi.j + Ep.j where E..j is drawn from Dj. probability distribution on E with mean O, variance o², and satisfying the Bernstein condition. The main difference from noise model I is that we add noise to every coordinate of each point with a changeable variance o² instead 1. Moreover, we consider more general noise models where the noise is non-independent across dimensions. For example, the covariance matrix of each noise vector Ep is Σ E IR Rdddd which extends Σ = 0² Ia when each D, = NO, 2) under the noise model II.
Several applications mentioned in Section use these noise models. For example, setting 0 = 1 and each Dj as Gaussian distribution corresponds the Gaussian mechanism in differential privacy [30, 66]. The noise parameter 0 is usually known in real-world scenarios. In domains like healthcare, location services, and financial analytics, adding Laplace or Gaussian noise data points a common strategy to protect privacy [73, 79], creating a noisy dataset, P. In such cases, is known in advance, removing the need to compute it during coreset construction. Other scenarios where 0 is known include: 1) measurement errors in sensor data, and 2) noise in STEM exam scores (see Section B.2).
The ideal metric. Let C denote the collection of all subsets C C Rd of size k, termed center sets. For any dataset X C Rd, let C(X) denote the optimal center set for (k, (k,z)-CLUSS CLUSTERNN,,,,, i.e., C(X) := arg mingee cost (X, C). Given dataset P C Rd of size n, coreset is weighted set S C nd with function w S + R20 such that for all C' E C,
cost. C) == Eaes w(x) d' C) (1 +) cost=(P,C)
(3)
Ideally, we would measure the effectiveness of a coreset S by how well the clustering solution yields on S generalizes to the true dataset P. This leads to the ideal quality measure:
rr(C(S)) = (P,C_() OPT
where OPTp == mincec cost, (P,C). Note that (P()))) 2 1, with equality if C(S) = C(P). However, computing C(S) is generally NP-hard, and even estimating rp(C())) is infeasible in
"The variance of each D, can be fixed to any t 0 since we scale each point in the dataset by 1.
3

---

the noisy setting where P is unobservable. To account for approximate clustering, we define for any a 2 1 the of o-approximate center sets for S: (S) := {C E C : rs(C)) S a). where
rs( (C) == =ost=(S, C)/PTTs g. We then define the worst-case quality over this set:
(S, maxCEC.(S)
cost, (P.C)
P
This function is monotonically increasing in a, and rp(S, (C())))). We focus on settings where a is close to I, such as when PTAS is available for (k, C)-USTETRG As discussed in Section I, directly evaluating rp a) is computationally hard and, in noisy settings, fundamentally
the need for surrogate metrics.
The metric Err. In the noise-free setting, a standard surrogate for rp(S, o:) is the relative emror:
Err(S, (S, P) := supcec clost (3.C)
(S.),((S))) (P.C))
This quantity provides a bound on how much the clustering cost on S deviates from that on P. uniformly over all center sets. In particular, for the optimal center C(S) of
S, we have: (S.C_)) (P0...
S Err(S, P), which implies (ost)(P)((S)) E
cost, (S,C(8)
I+) Er((S,))) co, ((S)). Since C(S) is optimal for S, this yields a lower bound on P and extends to all a-approximate center sets:
VC' E (S), = s (I+EE P)) cS, (S, C) s (1+Er((, - (s.)t,
Combining these gives:
rr ( o)) S (1 Err(S, P))2
(5)
This justifies the use of Err(S, P) as surrogate for rp(S, a) in the noise-free setting.
In the noisy setting, however, P is unobservable. A natural alternative is to compute Err(S, P) instead. This raises the question: how does Err(S, P) relate to the true coreset quality rp a)? We explore this relationship and show how Err(S, P) can still guide coreset construction (see Theorem 3.1).
The new metric. While Pr) is a valid surrogate in the noise-free setting, its adaptation to noisy data via Err(S, P) is problematic: noise inflates clustering costs on P. weakening its connection to the true quality rS(S at. To mitigate this, we introduce a new surrogate metric that compares the relative quality of a center set on P versus S:
Erra P) supcec. (8) rs(C)
FP(C) 1.
(6)
rp(C) 1, and therefore rp(S, S (1 (Sr P)) aa This bound justifies Err, as a surrogate for (S, The metric is monotonic in a, independent of the noise distribution, and aligns better with coreset quality under noise than Err, which measures absolute cost deviation.
Since rC( S a, we have (Sr 2 supcec.(S) a.
In practice, we compute (S, P) as proxy for (Sr, P). We analyze this in Theorem 3.3, showing that it can guide coreset construction under noise. Notably, Err, extends prior approximation- ratio-based coreset ideas [23, 53] to the noisy setting.
Comparing two metries under noise. We illustrate the advantage of Err, over Err through simple 1 1-MEANS example in R, with t- = d = 1, 2 = 2, and a = 1.
Let P = P- U P+, where P_ has n/2 points -1 and P+ has n/2 points at 1. The optimal center C(P) = with OPT, = n. Now consider P. generated under noise model with and
D, = NN 1). This adds i.i.d. Gaussian noise to each point, inflating clustering cost by roughly
2n for any center c, i.c. cost, (P.c) cost. v 2n. Hence, Err(P, P)
2n 2.4 yielding
bound:
(P S (M((
In contrast, because the noise E, averages out, the empirical center satisfies C(P) E 1/m,, V//m with high probability, and: cost, (P, ((P) I n +1 This implies Err, (P, P) s n and therefore:
TP ((PP $1+1.

---

Thus, Err, provides much tighter estimate of rp under noise, by compensating for the uniform cost inflation that Err fails to account for. We elaborate on this example and provide additional comparisons in Section B.3.
Finally, note that setting differs fundamentally from "robust" coreset models [38, 52, 54), which assume direct access to the clean dataset P. In contrast, we construct coresets directly from noisy observations P; see Section A for a detailed comparison.
3 Theoretical results
This section gives theoretical guarantees for coreset construction under noise. We present two algo- rithms for k- A-MEANS (z = 2) using noise model I, based on the surrogate metrics Err (Theorem 3.1) and Erra (Theorem 3.3). While both yield bounds on coreset quality, the Erra-based method achieves smaller coresets and tighter guarantees under mild structural assumptions. We write cost for cost, throughout. Extensions to other noise models and (k: 2) CJ.USSSTRRI are Section
We begin with Err-based coresets. Theorem 3.1 extends its use to noisy data and bounds rr o:) in terms of 0, d, and n. See Section for the proof.
Theorem 3.1 (Coreset using Err). Let P be drawn from P via noise model with known 0 2 Let E E (0, 1) and fix a 2 1. Let A be an algorithm that constructs a weighted subset C for k-MEANS of size A(e) and with guarantee Err(S, P) S E. Then with probability at least 0.9,
Err(S, P) S 5 O OPTr
OPT and mnd,ppSS,0 a)) S (1 + + +0 +0
(OPT,
And OPT + + OPTT ))² a.
To ensure Err(S, S., we may use an importance sampling algorithm [10] with coreset size A(e) ((min(b'.5 ks 43),
which matches the state of the art in the noise-free setting. However, the resulting bounds for Ond
v OPTP): ). due to the gap Err P) (see Lemma C.2). As discussed in Section 2, this gap can be overly conservative conservative-espeecie especially when noise uniformly inflates clustering cost. In such cases, Err,, :PP1 P) < Err(P, P). shown in earlier example. While this inflation always occurs when k: = 1, it may not persist for general k, where noise can change point-to-cente assignments between /' and P. To address this, we introduce structural assumptions that preserve assignments under noise.
Err(S, P) and rr(S, a) incur an additive term O Ond
OPTP
Assumptions on data. To theoretically separate the performance of Err and Err., we impose mild structural assumptions the dataset to ensure that point-to-cente assignments remain stable under noise. A natural but strong assumption is to posit a generative model, such as a Gaussian mixture Ek - ( 1), where the means μr E IRd are well separated, c.g., l| - p || 2 n [35, 57]. This would make the assignments between P and P nearly identical. However, this is more than we require-wa we instead use structural assumptions that capture the relevant properties directly.
The first is cost stability, widely studied notion in clustering and coreset literature [71, 6, 59, 2, 25, 10]. Let OPTp(m) denotes the optimal cost of m-means on P. For 7 > 0, dataset P is y-cost-stable if
OPT OPT
21+7
As increases, the clusters are more well-separated, making assignments more robust to noise. In our setting, cost stability ensures that the assignment changes between P' and P remain limited, and we function of the noise level in Assumption 3.2. This assumption
specify the required value of also necessary to distinguish Err(P: P, P) from Err, (P, P). As shown in Appendix E.I, when cost stability is weak, the two metrics can behave similarly; e.g., in 3-means instance with y = 1, we find Err(P, P) Err,
We also assume that does not contain strong outliers. Let Pi..... Ps denote the partition of P induced by its optimal center set C(P). For each cluster P,, define the average and maximum radius:
:=
IP: EpER. d' C(P).), r; == maxpeP, d(p. C(P))).
5

---

We assume S 87; for all i, which rules out heavy-tailed clusters and helps distinguish noise from genuine outliers. This choice of is made to simplify analysis and is satisfied by real-world datasets; see Table 2.
Assumption 3.2 (Cost stability and limited outliers). Given a 2 1 and 0 E =0, 1]. assume P is y-cost-stable with
7 7= ( (1+
log (kdd (kd/va-]
OPTP
and that & 87, for all i [k:].
Under these assumptions, the following theorem gives performance guarantees for a coreset algorithm based on the ErR, metric. The proof appears in Section D.
Theorem 3.3 (Coreset using the Erra metric). Let P be an observed dataset drawn from P under the noise model I with known parameter 0 E [0, ]. Let E (0, 1) and fix a E [1, Under Assumption 3.2, there exists randomized algorithm that constructs weighted S C for k-MEANS with probability least
of size O va O
klog k (a 13k log & and with guarantee (rr, (S, P)
12
0.99. Moreover,
Esra S + O
va-1
/8kdOPT +-8d and PPT
OPT
(r( (1 (1+E+ O
BkdOP P OPT
T=+tnd) ))
OPT
We consider the regime 8 < OPTr, ensuring that noise does not dominate the clustering cost, i.e.. nd
cost P, C* (ccos((P, C)). The coreset size depends on the knowledge of OPT but we later show how to remove this dependence. In the special case = 0 and = 1, the bound becomes (S, P)- (Sr Err,
which factor k/n smaller than the bound Err(P, P) OPTr
0kd
O p end o from Theorem 3.1. This supports the use of Err, under Assumption 3.2.
Subsequently, we also provide interpretation for different terms in the bounds of Err and Err.-
Comparison of coreset performance using two metrics. We now compare the coreset size and error bounds for (S,,, a:) achieved by Theorem 3.1 (CN) and Theorem 3.3 (CN,). Let ş = 1 1/poly poly(())))) and a = + ce for a constant 0 < c < 0.5, ensuring that an a-approximate center set can be efficiently computed [62]. Under this setting, the stability parameter in Assumption 3.2 becomes O(1 + log (kd/e)), since 0 < OPTp// (/nd).
Va-Tond Coreset size. When T0PTr the size Ö(min(kl.5/ //2 k//41) of CN by factor of Vilee.
ce/2, the coreset size from CN, is Ö(k/E), which improves over
Bound on rp. The error bound in Theorem 3.3 includes a term OPT
Okd
+
Va-I
VBkdOPTT OPT
whose dominant component, when n >> [k]y is at most O tighter than the bound from Theorem 3.1, which scales O least poly(k).
And
This is again
poly(kj
OPT
6nd OPTP
6nd
by factor of at
OPT,)
For general ē E (0, 1), provide another example that demonstrates improved coreset performance orT and poly((() Following the same analysis above, observe that the coreset size of CN, improves over that of CN by factor of VT/e, while the error bound improves by at least a poly(k) factor.
for CN,- Let a
Overall, CN, yields smaller coresets and tighter theoretical guarantees for r a). improving over CN by at least factor poly(k) (k), owing to the more noise-aware nature the Err,, metric.
Applying Theorems 3.1 and 3.3 in practice. In practical settings, we often aim to construct a coreset such that P a) $ (1 z) a. There are two ways achieve this:
Use Ce' from Theorem 3.1, with g = E - O
And OPTT
V OPT

---

2. Use CNa(Ea) from Theorem 3.3, with Ea = E =0
0 Bkdd OPTP +
ya-I
P P p+00d
OPTP
Both approaches require an estimate of OPT which can be obtained by computing O(1)-
approximate center set O for P and using cost(P, C) as proxy; see discussion in Section E.3. When 0 S OPT (PTp)(nd), this yields a valid approximation. Notably, both CN and CN, already compute such C as first step,
additional overhead is incurred.
practical question is when to prefer CNa(Ea) over CN(EE). This depends on whether P satisfies Assumption 3.2. Although is unobserved, the observed dataset P often satisfies an approximate version of the assumption. We discuss how verify this in Section E.2, allowing practitioners to choose the tighter construction when applicable. In practice, we note that CN performs well even when the assumptions violated; Section
Key ideas in the proof of Theorem 3.1. The goal is to relate Err(S, P) to Err(S, P), from which the bound on (p(S, a:) follows via Equation (5). The Err metric satisfies a standard composition bound: (r P) S Err(S, P) + O(Err(P. P, P)) (Lemma C.3). Thus, it suffices to bound Err Err(P, P). We
show Err( P, P) =
Ond OPT
Ond OPT
(Lemma C.2). This obtained by controlling the difference:
cost (ost(PPC) - cost(P,C) S Epep (llEpll2 + (Ep. p-pp) c))
for all C E and showing that the sum on the r.h.s. above normalized by cost(P, C)) is O
Ond
0nd
The proof uses concentration from the independence of noise {Ep), com-
OPT
OPT
bined with bounded higher moments ensured by the Bernstein condition.
We note that the first term, O end (PTT>)
is information ciroriiiinthrrtrilllll.l necessary and cannot be improved
in the worst case; see Section C.2. The second term, O (v 6nd
arises from a loose upper bound in our analysis and is not known to be tight. This term is introduced when bounding the cumulative error over all points and center sets C' by applying
OPT
(
(I [Idnno)) <VBnd - (P,C(
Σ (S).P-c) S pEP
Σ 16p11
This worst-case analysis assumes full alignment of all error contributions, which may be overly pessimistic. more refined analysis could potentially tighten or remove this term by accounting for enror cancellation.
Key ideas in the proof of Theorem 3.3. The proof has two parts: (1) designing coreset algorithm that guarantees (S, P) < c, and (2) bounding the gap between Err, (S, P) and E5r, P).
Coreset design. We first construct coreset in the noise-free setting (P- = P) such that <.
( S. Under Assumption 3.2, we partition P into & well-separated clusters P....., each of diameter at most 2r, From each P,, the algorithm samples a uniform subset S, of size where A = -anTonn
O log:k E-A
aOPTp Let S = U, S, Standard concentration bounds imply that C(S) is close C(P), and OPTs S OPT p. which yield Err, (S, P) I (Lemma D.4).
(a-1)logk)
(E-A)²
To extend this to Err P) S e, we leverage geometric property: for any C C, (S), each center of C(S); (Lemma D.3). This follows from cost stability, which ensures consistent cluster structure for all such C.
c; lies within distance O (v /
n4
Directly applying this algorithm the noisy dataset introduces several analytical challenges. First, noise can significantly increase the diameter of each cluster P,, weakening the closeness guarantee between C(5) and C(P). Second, highly noisy points may shift cluster assignments across partitions Pi, breaking the geometric structure required for all C E C. (S). To address both issues, we eliminate extremely noisy points from P (see Line 3 of Algorithm 1), which is the key innovation of our
7

---

Algorithm A coreset algorithm CN using the Err metric under the noise model
Input:
noisy dataset P derived from P under noise model I with A > 0, E (0, 1), [1, 2). and an -appoxppoo center set Ô = (Ck...,;kk] C. Output: a weighted set
Decompose P into & clusters P. by Č, where P. {p P: arg min d(p, c) a.j.
For cach E [k], compute F. = V cost &.,
3: Compute P. = P. n B,, where ball B, B(G, R.) with R == 37, Ol dd 1t9kd
va-T
4: For each E [k]. take uniform sample S; of size O
log
(a- 1) log
18nd
GUFT
D0PT
5: Return S = Use( St with w(p)
for S.. [S
algorithm. In contrast to the existing approaches, our method explicitly excludes high-noise points and focuses the coreset on points whose assignments are reliable. This noise-aware sampling step critical preserving geometric stability. Moreover, we show that the effect of the removed points on the location of C(P") )') is negligible (Lemma D.5). Together, these steps ensure that Algorithm achieves the desired bound Err (S, P) S.
Metric bounds. A natural approach is to compose Erra(S, P) with (rra(P,P) P), as with the Err metric. However, this fails because set C' (S) may only satisfy C' Ca(1+e)(P)) preventing direct use of (r. P). To resolve this, we instead compose (rr, P) with Err Erra(1+e) P), yielding:
Err. (S, P) S ((Erra()+s)))) P)). P)).
The remaining task is bound (rr (P, P). Assumption 3.2 allows to analyze this quantity cluster by cluster. For simplicity, we illustrate the argument on one cluster P; and its noisy counterpart P.. Note that C(P:) = C(P:) + P. Eper. Sp by the optimality condition of 1 I-MEANS. Then:
cost( P,, (P,,C((P)) ((P:) OPT P. + [Pd] EpER Ep1 and hence,
1
Err,(P: P.) cost(P..c(P)) OPT,;
OPT
using standard concentration for sums of independent noise vectors (Lemma D.12). This is signifi- cantly smaller than Err(P., P.), which lacks cancellation.
Aggregating across clusters and plugging into the composition bound gives:
Err, (S, SE
okd OPT
Va(1-s)-1
v V8kdOPT +nnd OPT,
This bound matches Theorem 3.3, up to extra (1 + e) factor inside the square root. This artifact can be removed by composing through p' instead of P (see Lemmas D.4 and D.5). Note that the accounts for center drift due to noise. Intuitively, each optimal center in C(P) may shift by ((dd) under noise, resulting in a total movement of (@kdd) This implies that C(P) forms a )-approximate center set for P. yielding the corresponding error term. The final term,
term O
Okd
OPT
(1 + OPT
0kd
VOkd OPT + Ond OPTp
captures the additional approximation error from using a-aaproximmate center rather than exact optima. It scales with the gap between a and 1, and vanishes as a 1.
Thus, complete the proof of Theorem 3.3. Note that other noise models primarily affect the concentration bounds of the term Epep, &p the analysis; see details in Section

---

Empirical results
We now evaluate the empirical performance of our proposed coresct algorithms on real-world datasets under varying noise levels and tolerance thresholds. The goal is to test whether our theoretical guarantees translate into practical improvements in coreset size, accuracy, and robustness. We also assess how well the theoretical bounds track actual performance in both clean and noisy data regimes.
Setup. We consider the k-MEANS problem on the Adult [61] and Census 1990 [68] datasets from the UCI Repository. Both satisfy the limited outlier assumption but exhibit small cost-stability constants 7, Table 2. We set & = 10. We perturb each dataset under noise model using Gaussian noise with 0 E {0, 0.01, 0.05, 0.25), where 0 = 0 denotes the noise-free case. For varying tolerance levels E (0.1, 0.2, 0.25, 0.3). we construct a coreset S from P using CN and CN,, For the initialization of our algorithms, we run k-means++ with max iter 5 on P to obtain a fast ((1) apprrxxaoe solution. Implementation details appear in Section G.I.
Metrics. For each coreset S, report: (i) coreset size [S], (ii) empirical approximation ratio (n.C(P.Caa. and (iii) tightness ratio Ki == Es where us the theoretical bound for (p(Cs) from Theorems 3.1 and 3.3. The approximation ratio ïs measures how well the coreset solution approximates the true clustering cost on P. To calculate is. we obtain C's and Cp by running k-means++ 10 times (default settings, varied seeds) on S and P separately and selecting the best
rs c's)
solution for each. Letting OPT cost (P, PCp), we set:
(1
8 +
And
+
OPT 22
and
(CN)
OPT
us
8 +
Ohd
Ond
(CN.).
OPT
OPT
A value Ks $ 1 implies the empirical ratio is below the theoretical bound; values closer to 1 indicate tighter guarantees. All experiments are repeated 10 times, and average metrics are reported.
Analysis. Table reports results on the Adult dataset across noise levels. Results on Census 1 1990 appear in Section G.2 and follow similar trends. all settings, CN. consistently produces smaller coresets and achieves Kg values closer to 1 than CN. For example, at 0.2, 0 = 0.01, CN, yields coreset of size 1940 (82% of CN's 2371), with Ki 0.937 vs. 0.596 for CN indicating much tighter empirical bounds.
We also find that for higher tolerance levels (e 0.2), CN, often yields better empirical approx- imation: e.g., for = 0.2,6 0 0.01, CN, attains ïs = 1.156 vs. 1.193 for CN. This suggests that CNa outperforms even in noise-free settings. indicating its potential value beyond noisy data applications. Moreover, in the noise-free case (0 = 0), empirical ratios is consistently satisfy rs S 1+ for CN, further validating the theoretical guarantees.
Additional results under Laplace, uniform, non-i.i.d., and noise model Il appear in Section F.1. These confirm the robustness and broader applicability of CN, across diverse noise regimes.
Summary. Overall, the empirical results demonstrate that CN, consistently achieves tighter approximation guarantees with smaller coresets across range of noise levels. These findings validate the practical utility of the -based construction and suggest that remains effective even when the theoretical assumptions (e.g., exact cost-stability
only approximately satisfied. The robustness of CNa across multiple datasets and noise models underscores its suitability for integration into practical data preprocessing pipelines.
5 Conclusion, limitations, and future work
This paper studies the practically relevant problem of coreset construction for clustering in the presence of noise. The main contributions are new algorithms that construct coresets with provable guarantees relative to the true (unobserved) dataset, one based on adapting the traditional surrogate metric Err, and the other introducing a new metric Err.. We prove that the algorithm based on Err, yields smaller coreset sizes and tighter performance bounds, assuming the dataset satisfies certain natural assumptions that necessary in worst-case scenarios. Our analysis quantifies how noise impacts clustering costs and perturbs the optimal center sets, relying on properties such as noise cancellation and the concentration of the empirical center C(P). The new metric Err. may

---

Table 1: Results of Adult dataset under noise model with Gaussian noise. |S| represents the coreset size, F's represents its empirical approximation ratio, and rig denotes the tightness ratio of its empirical approximation ratio over the theoretical bound.
(a) f = 0
(b) 8 = 0.01
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
|S|
CN
9486
4216
2371
1517
1054
[|]
CN
9486
4216
2371
1517
1054
CN
6445
3178
1940
CN.
6445
3178
1940
1320
CN
1,000
1.183
1.200
CN
1,037
1.081
1.193
1.187
Fg
F5
CN.
1.085
1.155
1,150
1.197
1.124
CN.
1.114
1,069
1.156
1.154
1.145
CN
0.859
0.817
0.821
0.818
0.710
CN
0.600
0.581
0.596
0.554
0.543
K.5
CN.
0.986
0.969
0.959
0.958
0.865
CN
0.984
0.904
0.937
0.899
0.859
(c) 8 0.05
(d) 0 0.25
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
|8|
CN
9486
4216
2371
1517
1054
|S|]
CN
9486
4216
2371
1317
1054
CN,
6445
3178
1940
1320
960
CN
6445
3178
1940
1320
960
CN
1.027
1.061
1,217
1.152
1.200
CN
1,044
1,049
1.067
1.234
1.341
Fgg
Fis
CN.
1,120
1.108
1.133
1.186
1.154
CN.
1.125
1,163
1.173
1.158
0.369
0.359
0.389
0.343
CN
0.131
0.127
0.139
K5
CN,
0,886
0.844
0.830
0.839
0.788
Kg
CN
0.585
0.590
0.581
0.559
0.576
also have independent utility beyond the noisy setting, for instance, enabling further coreset size reduction noise-free tasks where preserving near-optimal solutions suffices-such as in regression. Empirical evaluations strongly support the theoretical findings, demonstrating robust performance across a broad range of real-world datasets (which may violate the theoretical assumptions) and under diverse noise models. These results suggest that the proposed algorithms can be readily integrated into existing coreset- clustering pipelines to improve robustness in noisy environments.
One limitation lies in extending the use of the Err, metric to coreset construction in the streaming model. Although Err, satisfies a composition property akin to Err, it may lack the mergeability property (the union of coresets is a coreset for the union of datasets), which is crucial for enabling coreset construction in streaming settings. As a result, adapting the Err, metric to the streaming model remains technically challenging problem. As an initial step toward this challenge, we present a relaxed version of mergeability for the Err,, metric Section B.4, which may be applicable in certain scenarios.
Besides this, our work opens several promising avenues for future research. A natural next step is to explore weaker assumptions that are applicable beyond worst-case scenarios, thereby improving the generalizability of our results. Another key direction to extend our analysis to more realistic noise models, including those with dependencies across data points, heavy-tailed noise, or adversarially structured noise. Furthermore, our work focuses on clustering problems in Euclidean spaces. Extending coreset construction under noise general metric spaces presents interesting direction for future research. However, without access to Euclidean coordinates, becomes nontrivial to define additive noise on individual points. A natural alternative in such settings is to model noise additively on pairwise distances (cdges) rather than on point coordinates. In addition to clustering, would be valuable to investigate how noise affects coresct construction in other learning tasks such as regression and classification. Furthermore, studying connections between coreset constructions and other robustness notions in clustering could yield new insights. Finally, our empirical results suggest that coresets based on the Err, metric may outperform those based on Err even in the absence of noise. Characterizing the conditions under which Err, provides tighter guarantees than Err in the noise-free setting is an intriguing direction for future theoretical study.
We anticipate positive societal impact from this work by enabling more accurate and reliable data analysis pipelines. These improvements could benefit various sectors, including healthcare, finance, and technology, by enabling more robust data-driven decisions.
10

---

Acknowledgments
LH acknowledges support from the State Key Laboratory Novel Software Technology, the New Cornerstone Science Foundation, and NSFC Grant No. 625707396. ZL was supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier grant. NKV was supported in part by NSF Grant CCF-2112665.
References
[1] Margareta Ackerman, Shai Ben-David, David Loker, and Sivan Sabato. Clustering oligarchies. In Artificial Intelligence and Statistics, pages 66-74, PMLR, 2013.
[2] Manu Agarwal, Ragesh Jaiswal, and Arindam Pal. k-means++ under approximation stability. In Theoretical Computer Science, 2013.
[3] Parag Agrawal, Anish Das Sarma, Jeffrey D. Ullman, and Jennifer Widom. Foundations of uncertain-date integration. Proc. VLDB Endow, 31):10800-0000 2010.
[4] David Arthur, Bodo Manthey, and Heiko Röglin. Smoothed analysis the k-means method. Journal of the ACM (JACM), 58(5)11311,2))
[5] David Arthur and Sergei Vassilvitskii. k-means++ the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027-1035, 2007.
[6] Pranjal Awasthi, Avrim Blum, and Or Sheffet. Stability yields ptas for k-median and k-means clustering. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 309-3 318, 2010.
[7] Maria-Florina Balean, Avrim Blum, and Santosh Vempala. discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 671-680, 2008.
[8] Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering general communication topologies. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Anmual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, 2013.
pages
[9] Maria Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. SIAM Journal on Computing, 45(1):102-155, 2016.
[10] Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1707-1723. IEEE, 2024.
[11] Gustavo A. P. A. Batista and Maria Carolina Monard. An analysis of four missing data treatment methods for supervised learning, Appl. Artif. Intell., (7(5-6):519--5) 2003.
[12] Ariane Baye and Christian Monseur. Gender differences in variability and extreme scores in an international context. Large-scale Assessments in Education, 4:1-16, 2016.
[13] Shai Ben-David and Nika Haghtalab. Clustering in the presence of background noise. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 280-288. 2014.
[14] George Bennett. Probability inequalities for the sum independent random variables. Journal of the American Statistical Association, 57:33-45, 1962.
[15] Sergei Bernstein. The theory of probabilities. Gostechizdat, Moscow, page 348, 1946.

---

[16] Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. New frameworks for offline and streaming coreset constructions. arXiv preprint arXiv:1612.00889, 2016.
[17] Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts.
J. Mach. Learn. Res., 1-9::44,, 2019.
[18] Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In SODA, volume I, pages 642-651. Citeseer, 2001.
[19] Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages $26-835, 2008.
[20] Adam Coates and Andrew Y. Ng. Learning feature representations with k-means. In Grégoire Montavon, Genevieve B. Orr, and Klaus-Robert Müller, editors, Neural Networks: Tricks of the Trade Second Edition, volume 7700 of Lecture Notes in Computer Science, pages 561 561-580. Springer, 2012.
[21] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. To- wards optimal lower bounds for k-median and k k-means coresets. In STOC '22: 54th Annual ACM SIGACT' Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1038- 1051, ACM, 2022.
[22] Vincent Addan-Addad, Kasper Green Larsen, David Saulpie, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for Euclidean k-means. In Advances in Neural Information Processing Systems 35: Anmual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, 2022.
[23] Vincent Cohen-Addad. David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in euclidean spaces. In NeurlPS, pages 21085-21098, 2021.
[24] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Compuling, Virtual Event, Italy, June 21-25, 2021, pages 169-182. ACM, 2021.
[25] Vincent Cohen- and Chris Schwiegelshohn. On the local structure of stable clustering instances. 2017 IEEE 58th Anmual Symposium on Foundations of Computer Science (FOCS), pages 49-60, 2017.
[26] Juan Antonio Cuesta-Albertos, Alfonso Gordaliza, and Carlos Matrán. Trimmed k-means: an attempt to robustify quantizers. The Annals of Statistics, 25(2):553-576, 1997.
[27] Matan Danos. Coresets for clustering by uniform sampling and generalized rank aggregation. PhD thesis, Master's thesis, Weizmann Institute of Science, 2021, 2021.
[28] Rajesh N Dave. Characterization and detection of noise in clustering. Pattern Recognition Letters, 12(11):657 1991.
[29] Rajesh N Dave. Robust fuzzy clustering algorithms. In /Proceedings 1993] Second IEEE International Conference on Fuzzy Systems, pages 1281-1286. IEEE, 1993.
[30] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 9(344:2111440) 2014.
[31] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserve principal component analysis. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 June 03, 2014, pages 11-20. ACM, 2014.
[32] Vitalii Emelianov, Nicolas Gast, Krishna P. Gummadi, and Patrick Loiseau. On fair selection in the presence of implicit and differential variance. Artif. Intell., 302: 103609, 2022.
12

---

[33] Xiequan Fan, lon Grama, and Quansheng Liu. Sharp large deviation results for sums of independent random variables. Science China Mathematics, 58:1939- 2012.
[34] Hanming Fang and Andrea Moro. Theories of statistical discrimination and affirmative action: survey, Microeconomics: Asymmetric & Private Information eJournal, 2010.
[35] Dan Feldman, Matthew Faulkner, and Andreas Krause. Scalable training of mixture models via coresets. In John Shawe-Taylor, Richard S. Zemel, Peter L.. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. I. Proceedings of meeting held 12-14 December 2011, Granada, Spain, pages 214 2142-2150, 2011.
[36] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569-578, ACM, 2011.
[37] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means. pea and projective clustering. In Proceedings of the Twenty-Fourth Fourth Anmual ACM-SIAM Symposium on Discrete Algorithms, pages 1434-1453. SIAM, 2013.
[38] Dan Feldman and Leonard J. Schulman. Data reduction for weighted and outlier-resistant clustering. In Yuval Rabani, editor, Proceedings of the Twenty-Thive Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1343-1354, SIAM, 2012.
[39] Hortense Fong, Vineet Kumar, Anay Mehrotra, and Nisheeth K. Vishnoi. Fairness for AUC via feature augmentation. In FAceT '22: 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul, Republic of Korea, June 2/- 24, 2022, page 610. ACM, 2022.
[40] Alex Alves Freitas. Understanding the crucial role of attribute interaction in data mining. Artificial Intelligence Review, 16:177-199, 2001.
[41] Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R Salavatipour. Approximation schemes for clustering with outliers. ACM Transactions on Algorithms (TALGG) 15(2):1-26, 2019.
[42] Luis A. Drrcfa-Escudero, Alfonso Gordaliza, Carlos Matrán, and Agustin Mayo-Iscar, A general trimming approach to robust cluster Analysis. The Annals of Statistics, 36(3):1324 1345, 2008
[43] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Differentially private clustering: Tight approximation ratios. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiet Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[44] Gabriel Ghinita, Panagiotis Karras, Panos Kalnis, and Nikos Mamoulis. Fast data anonymization with low information loss. In Christoph Koch, Johannes Gehrke, Minos N. Garofalakis, Divesh Srivastava, Karl Aberer, Anand Deshpande, Daniela Florescu, Chee Yong Chan, Venkatesh Ganti, Carl- Carl-Christian Kanne, Wolfgang Klas, and Erich J. Neuhold, editors, Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007, pages 758-769. ACM, 2007.
[45] Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moseley, and Sergei Vassilvitskii. Local search methods for k-means with outliers. Proceedings of the VLDB Endowment, 10(7):757-768, 2017.
[46] Alon Y. Halevy, Anand Rajaraman, and Joann J. Ordille. Data integration: The teenage years. In Umeshwar Dayal, Kyu- Young Whang, David Lomet, Gustavo Alonso, Guy M. Lohman, Martin I.. Kersten, Sang Kyun Cha, and Young-Kuk Kim, editors, Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006, pages 9-16. ACM, 2006.
13

---

[47] Frank R Hampel. A general qualitative definition of robustness. The annals of mathematical statistics, 42(6))1887-1888 1971.
[48] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In 36th Annual ACM Symposium Theory of Compuling,, pages 291-300, 2004.
[49] Majed EI Helou and Sabine Süsstrunk. Blind universal bayesian image denoising with gaussian noise level learning. IEEE Trunsactions on Image Processing, 29:4885-4897, 2019.
[50] Christian Hennig. Dissolution point and isolation robustness: Robustness criteria for general cluster analysis methods. Journal of Multivariate Analysis, 99: 154-1176, 2008.
[51] Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 57:1-57:21. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[52] Lingxiao Huang. Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu. e-coresets for clustering (with outliers) doubling metrics. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814-825, IEEE Computer Society, 2018.
[53] Lingxiao Huang, Shaofeng H.-C. Jiang, and Jianing Lou. The power of uniform sampling for k-median. ICML, volume 202 of Proceedings of Machine Learning Research, pages 13933-13956. PMLR, 2023.
[54] Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In ICLR. OpenReview.net, 2023.
[55] Lingxiao Huang. Jian Li, and Xuan Wu. On optimal coreset construction for Euclidean (k, z)- clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1594-16080 2024.
[56] Lingxiao Huang, Zhize Li, Jialin Sun, and Haoyu Zhao. Coresets for vertical federated learning: Regularized linear regression and K- K-means clustering, In Advances in Neural Information Processing Systems, pages 29566-29581 2022.
[57] Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi. Coresets for time series clustering. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Confer- on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 22849-22866 2021.
[58] Natthakan lam-on. Clustering data with the presence of attribute noise: study of noise completely at random and ensemble of multiple k-means clusterings. Int. Mach. Learn. Cybern., 11 11(3):491-500 2020.
[59] Ragesh Jaiswal and Nitin Garg. Analysis of k-means++ for separable data. In International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012.
[60] Xiaodan Jin and Keigo Hirakawa. Approximations to camera sensor noise. Image Processing: Algorithms and Systems, volume 8655 of SPIE Proceedings, page 86550H. SPIE, 2013.
[61] Ronny Kohavi and Barry Becker. UCI machine learning repository, 1996.
[62] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1 + aaapproxximtioon algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium on Foundations of Computer Science, pages 454-662, IEFF, 2004.
[63] Shrinu Kushagra, Samira Samadi, and Shai Ben-David. amidst background noise. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings 27, pages 339-354. Springer, 2016.
Finding meaningful cluster structure
14

---

[64] Shrinu Kushagra, Yaoliang Yu, and Shai Ben- Provably noise-robust, regularised k-means clustering. arXiv preprint arXiv:1711.1122 2017.
[65] Pat Langley, Wayne Iba, and Kevin Thompson. An amalysis of bayesian classifiers. In William R. Swartout, editor, Proceedings of the 10th National Conference Artificial Intelligence, San Jose, CA, USA, July 12-16, 1992, pages 223 223-228.42 AAAI Press / The MIT Press, 1992.
[66]
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin, Certified adversarial robustness with additive noise. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9459-9469, 2019.
[67] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Information Theory, 28(2):129- 136, 1982.
[68] Chris Meek, Bo Thiesson, and David Heckerman. US Census Data (1990). UCI Machine Learning Repository, 2001. DOI: https://6..ogg//0223333//vVV
[69] Steven J. Miller. Chapter 16. The Chi-square Distribution, pages 427-446. Princeton University Press, Princeton, 2017.
[70] Alexander Munteanu and Chris Schwiegelshohn. Coresets methods and history: A theoreticians design pattern for approximation and streaming algorithms. KI-Kinnttliche Intelligenz, 32:37-53, 2018.
[71] Rafail M. Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. The effective- ness of lloyd-type methods for the k-means problem. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (66),, pages 165-176, 2006.
[72] Rose E. O'Dea, Malgorzata Lagisz, Michael D. Jemnions, and Shinichi Nakagawa. Gender differences in individual variation in academic grades fail to fit expected patterns for stem. Nature Communications, 9, 2018.
[73] Vincent Primault, Sonia Ben Mokhtar, Cédric Lauradoux, and Lionel Brunie. Differentially private location privacy in practice. CoRR, abs/1410.7744, 2014.
[74] Violeta Roizman, Matthieu Jonckheere, and Frédéric Pascal. A flexible EM-like clustering algorithm for noisy data. IEEE transactions on pattern analysis and machine intelligence, PP, 2019.
[75] José A. Sáez, Mikel Galar, Julián Luengo, and Francisco Herrera. Tackling the problem of classification with noisy data using multiple classifier systems: Analysis of the performance and robustness. Inf. Sci., 247:1-20, 2013.
[76] Benjamin Schelling and Claudia Plant. KMN removing noise from k-means clustering results.
In Carlos Ordonez and Ladjel Bellatreche, editors, Big Data Analytics and Knowledge Discovery 20th International Conference, DaWak 2018, Regensburg. Germany, September 3-6, 2018, Proceedings, volume 11031 of Lecture Notes in Computer Science, pages 137-151. Springer, 2018.
[77] Marco Secondini. Chapter 20 information capacity of optical channels. In Alan E. Willner, editor, Optical Fiber Telecommunications VII, pages 867-920. Academic Press, 2020.
[78] Adiel Statman, Liat Rozenberg, and Dan Feldman. k-meanst ++: Outliers-resistant clustering. Algorithms,, 13(12):311, 2020.
[79] Rishabh Subramanian. Differential privacy techniques for healthcare data. In IDSTA, pages 95-100. IEEE, 2022.
[80] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, et al. Cluster analysis: basic concepts and algorithms. Introduction to data mining, 8:487-568, 2006.
[81] Sergios Theodoridis. Parameter learning: convex analytic path. Machine Learning, 2020.
15

---

[82] Roman Vershynin. digeh-imensional probability. University of California, Irvine, 2020.
[83] Zixiu Wang, Yiwen Guo, and Hu Ding. Robust and fully-dynamic coreset for continuous- and-bounded learning (with outliers) problems. 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 14319-14331, 2021.
[84] Xue Ying. An overview of overfitting and its solutions. Journal of Physics: Conference Series, 1 1668, 2019.
[85] Zhiwen Yu and Hau-San Wong. Class discovery from gene expression data based on perturbation and cluster ensemble. IEEE Transactions on NanoBioscience, 8: 147--66 2009.
[86] Xingquan Zhu and Xindong Wu. Class noise vs. attribute noise: quantitative study. Artif. Intell. Rev. 2773):177-210, 2004.
[87] Manfred Zimmermann and Klaus M. Dostert. Analysis and modeling of impulsive noise in broad-band powerline communications. IEEE Transactions on Electromagnetic Compatibility, 14:249-258 2002.
16

---

Contents
1 Introduction
2 Noise models and metrics for coreset quality
3 Theoretical results
4 Empirical results
5 Conclusion, limitations, and future work
A Related work
18
Additional discussion on assumptions and error metrics
18
B.1
Distributions satisfying the Bernstein condition
18
B.2 Practical scenarios with known estimable 0
19
B.3 Comparing Err and Erra
19
B.4 Weak mergeability under Err,
20
C Proof of Theorem 3.1: Using Err
21
C.1 Proof of Lemma C.2: Bounding Err(P, P).
22
C.2 Lower bound of P)
24
Proof of Theorem 3.3: Using Erra
24
D.1 Proof of Lemma D.3: structural properties of CS)
26
D.2 Proof of Lemma D.4: properties of S
30
D.3 Proof of Lemma D.5: movement of centers of P'
D.4 Justifying Assumption D.2: Finding center sets within local balls
34 ................................
Missing results and discussions from Section 3
34
E.1 Necessity the stability assumption in the worst case
E,2 Examining Assumption 3.2 in practice
36
E.3 Impact of Cost Estimation of OPT on Algorithm Performance
36
Extensions of Theorems 3.1 and 3.3
37
F1 Extension to other noise models
37
F.2 Extension (k, CLUSTEERING
39
G Additional empirical results
40
G.I Implementation details of CN and CN2
40
G.2 Results on the Census1990 dataset.
G.3 Results under other noise settings
17

---

A Related work
Coresets for clustering (with noise). There is substantial body of work coreset construction for (k, 2)-LLSSTHRIING across various metric spaces, including Euclidean spaces, doubling metrics, graph shortest-path metries, and general discrete metries [48, 36, 37, 16, 52, 24, 25J. An alternative notion called weak coresets has also been studied [70, 24, 27J, which only require preservation of -pppapprox solutions. However, weak coresets offer no significant improvement in size compared to standard coresets in practice.
In the context of noise, most prior work focuses identifying and removing outliers [38, 52, 54]. These approaches assume that noise manifests as identifiable outliers, and the goal is to build a robust coreset by filtering them out. By contrast, model assumes full observation of only noisy data, with no oracle access to the clean underlying distribution. This represents a conceptual shift: instead of excluding noise, our algorithms construct coresets that directly accommodate it. This setting reflects realistic scenarios which noise and signal cannot be reliably constructions that remain robust without preprocessing or filtering steps.
-eennnglednnessitttiiin coreset
Clustering under noise. Clustering with noisy data has been studied extensively, typically under two paradigms. The first assumes noise is generated stochastically from known distribution [29, 42], while the second considers adversarial noise with bounded magnitude or cardinality [7, 13, 9, 63, 64]. Our work aligns more closely with the first setting.
Broadly, this literature branches into two directions. The first investigates the robustness of existing clustering algorithms to noise-quanee quantifyannnnngggg their performance degradation in noisy environments [28, 47, 50, 4]. The second direction designs new algorithms that can tolerate or adapt noise [26, 29, 13, 64). A related line of work in robust clustering allows the algorithm to discard fraction of points as outliers [18, 19, 45, 76, 41, 74, 78]. While our work shares a similar structural noise model with some previous works, the goal is significantly different. Prior works mostly ask whether standard algorithm can efficiently solve the problem on the noisy dataset P. For instance, [4] uses Gaussian perturbations for k-means and shows that k-means converges quickly on the noisy data. In contrast, we aim to construct a coreset from f that approximates the clustering cost on the original, unobserved dataset P. Here, noise the main challenge, a tool for tractability.
B Additional discussion on assumptions and error metrics
This section provides additional context and justification for the modeling choices made in the main text. We first clarify the Bernstein condition and show it is satisfied by a wide class of noise distributions. We then discuss practical scenarios where the noise variance is known or can be estimated. Next, we compare the standard error metric Err with the proposed Err.. using concrete examples to highlight the tighter guarantees enabled by our approach. Finally, we present a weak mergeability property for Erra measure, which may be useful for streaming settings.
B.1 Distributions satisfying the Bernstein condition
The Bernstein condition plays a central role our theoretical analysis, as it enables control over higher-order moments and supports concentration arguments under noise. We show that this condition satisfied by several widely used distribution families.
Sub-Gaussian and sub-exponential distributions. A distribution D is called tab-Gaussian if there exists constant K such that for all >
Pr | 2 t] < 2e R//K X
Similarly, D is called sub-exponential if there cxists K 0 such that
Pr 1r 2 1 2c 1/K
X-D P
Gaussian distributions are sub-Gaussian; Laplace distributions are sub-exponential.
Lemma B.1 (Moment bounds [82, Sections 2.5 and 2.7]). D is aab-Gausiian, there exists constant K > O such that for all integers: 2 1,
Ex~D|LX]11 KVi.
18

---

D is sub-exponential, then for some K > 0.
Ex-n||x]] I Ki.
Combining Lemma B.1 with Stirling's s approximation, we conclude that both sub-Gaussian and sub- exponential distributions satisfy the Bernstein condition. On the other hand, heavy-tailed distributions such the Pareto, log- log-normal, and Student's t-distributions generally do not.
B.2 Practical scenarios with known or estimable
Several real-world applications provide natural access to the noise parameter 8, either directly through andeinformation.
Sensor networks. In settings such as environmental monitoring using sensor arrays (e.g.. for air quality), each measurement Pt.j = Pi.j + & is perturbed by Gaussian noise & (0, 0) [60]. Although the exact may be unknown, sensor specifications often report an upper bound 0', which can be directly used in our algorithm without additional estimation.
Standardized assessments. In educational assessments (e.g., STEM exam scores), observed out- comes are noisy proxies for latent ability [32]. Here, Pt.j = P.,j + E,. with ε representing unknown variation. Historical data or variance analyses over large student cohorts often enable institutions to estimate 9 empirically, which can then be reused to construct robust coresets for future datasets.
B.3 Comparing Err and Erra
We now illustrate how Err, yields significantly tighter guarantees than Err, even in simple ID settings.
Noisy setting. Consider 1 1-MEANS in R, with l d = 1. Let P consist of n/2 points at -1 and n/2 points at +1. Then C(P) = and OPT = n. Both -1 and +1 are 2-approximate centers: cost 1) cost(P, 1) 2n.
Let P be the noisy version of P under model I, with 0 and Ep N((0 1). Using the decomposi- tion:
cost (P, c) - cost (P.c) p) Σ
115 + 2 Σ (Ep. c),
PEP
PEP
the first term concentrates around n.. Bounding the second term naively:
2 Σ (pp. c) Σ
(11& + |pp - cl13)
PEP
pEP
get Err(P, P))
2n
3. yielding (P < (1+ - 5
3n
Now consider Err (P. P). We have:
C(P)
1
Σ Spp ((P)-C(P)) = (1131 coss(P
n
PEP
Thus, Err (fri(P, (P, S) n giving rp (,1) (P,(P S 1 much sharper guarantee.
Noise-free setting. Consider the I-Median problem in R, with n points at 0 and one point at 1. Then C(P) = 0 and OPT 1. Let have points 0 and 1/n. Then:
C(S) 0, OPTs 1/n, rp(C(S)) 1, rs((()))
Emr(SS)) 0.
However,
Err(S, |cost(P, C(S) cost(S, C(S))
cost(S, C(S))
This example underscores that even in noise-free settings, Err,, can yield dramatically smaller errors than Err, especially when datasets differ slightly but preserve the same optimal solution.
19

---

B.4 Weak mergeability under Erra
We discuss the mergeability under our proposed measure Erra- In the ideal case, mergeability means that if two coresets S1, S2 for disjoint datasets PI, P2 each satisfy (Sr, Pt) S e, then their union also satisfies
Err, (Si USSUS S P.UP))S..
However, this guarantee can fail with our new metric Err.- Consider the cases that S1 and S2 summarize datasets with significantly different cluster structures. In such cases, the optimal center set for S U S2 may differ substantially from the union of the individual optimal, and the combined coreset may not encode enough information capture this emergent structure.
Mergeability remains plausible when the two coresets are structurally similar. there exists S a' S such that
(S1) S (S22 and (a2) S C. (S1),
then S1 and S2 approximately share the same set of near-optimal solutions. This overlap enables weaker form of mergeability under Err.-
Claim B.2 (Weak mergeability under Erra). Let > 0 and a, a' 2 with a' < a. Given datasets Pi and P2 and weighted subsets S₁ and S2, suppose (Sp, Pt) I and C, (S,) S C, (S3-e) for
1112 1,2. Define:
min (OPT s. OPT sa)
T s S P1 OPTs,/OPTr, OPTs
OPT s, u,S,
Then:
(S PiUP) <d' (1
In the limiting case where a' a 1 and 1, this bound recovers the ideal mergeability condition:
Err. U2, Pi P.PP:)
Proof of Claim B.2. We first prove that for any center set C C1+(a-1)n (S C (Si) n
Ca (S2). By contradiction if there exists some C' Ci+(a-1)e(S) U S2) such that C & (a) n C, (S2). Then
(S S2 C)
OPTs + (a - 1) min (OPT OPT
(C & (c.() (Defn. of x)
OPT S (a 1)x OPTs.us>
= (1+ (a 1)k) OPT
Thus, C & (t+(a-1)).(.. S2), which is contradiction.
Fix a center set C' (5 We now have C (S)) Since Erra(Se, Pt) s
E, we have
TP, (C) Ts, (C) Se.
rs,
implying that rp, (C) < (1 + s)rs, (C). Moreover, let C(P) denote the optimal center set of S and
we have C(P) E C. (Si) C C.. (S2). Thus, we have
OPT UPTs S co U S2 C(P) < OPTs, s, + + OPT S a'(OT + OPTs))
(8)
20

---

Thus,
PPUu (C) Sis (C)
(C)
PPuB, (C)
TS,Us; (C*)
cost(Pi, + cost (oost(Ps P2 C) OPT S1US2 -1
cost(S1, C)) cost cost( (S2, C)
OPTr,urs
OPTr, -rn (C) + OPT (C) OPTs -1
OPTs, rs) (C) OPT 8, (C) OPT OPT AuP
OPTp, (C) (C)+ OPTP, (C) OPTs
< (1++) OPTs, rs, (C) OPT S2 rs, (C)
1
PPTPuP
(CP (1 (1+))rs((C))
1PT OPT P OPT
S
< (1 + E) max
OPT 9
OPT PIUPS
OPT OPT
(OPT, S. + OPT S.)
< (1 + E) max
(Ineq. (8))
OPT OPTs,
OPT + OPT P2
OPT OPT
OPTs OPTs
< a +6) max
OPTs
OPT 82
max
OPT OPT P1
< a'7(1 +6)
(Defn. of r)
C Proof of Theorem 3.1:
Using Err
In this section, we prove Theorem 3.1. Our proof primarily relies on bounding Err(P, P), which we will show in Section C.I. Additionally, provide lower bound for Err(P, P) in Section C.2. This helps explain each additive term in Theorem 3.1.
Theorem C.1 (Restatement of Theorem 3.1). Let P be drawn from P via noise model I with known 0 2 O. Let E (0, 1) and fix 1. Let A be algorithm that constructs weighted subset S c P for k- G-MEANN of size A(e) and with guarantee Err(S, P) S E. Then with probability p >> 0.9.
Err(S,P) & E O
6nd
+
OPT, and T a:) & (1 + + O Ond
+
/
9nd ))² a. OPT
For simplicity, use OPT to denote OPT in the following discussion. For preparation, provide the following lemmas.
Lemma C.2 (Bounding Err(P, P)). For any P derived from n-point dataset P RR using noise model I, with parameter 0 we have that with probability p > 0.9,
Err(P, P) < O
Bnd OPT
Bnd OPT
(9)
Lemma C.3 (Composition property). Given P, P,P. IR, suppose Err(S, (0, 1), then have
Err(S, P) Err(S, P) 2Err(P,))
Proof.
Suppose Err(S, PS) and Err(P, (,, P) E'. For every center set C, we have
[cost((P, C) (S C)I S (S, C),
and
- P9, C)I < é' cost( C).
21

---

Combine these inequalities above, we have
(. C) - cost(S, C*]
I cost(P, (,C) .) cost(S, C) |cost(P,C) (P))(
(Triangle Inequality)
E e cost(S, C) + E' cost C)
3 (e + 5'(1 + e)) cost(S, C)
I (E 2=') co C)
(E <)
Thus Err(S, supcee
lonst, (8.C) cost, (P.C) cost, (S,C)
< Err(S, P) 2Err(P, P).
We ready prove Theorem 3.1.
Proof of Theorem 3.1. Suppose weighted subset S C P constructed by Algorithm satisfies that Err(S, P) S e. By Lemma C.2, with probability p > 0.9,
Ond OPT
Ond OPT
Err(P, < 0
By Lemma C.3,
And
Ond
Err(S, S Err(S, P) 2Err( = O
OPT
OPT
Moreover, for the optimal center set C(S) of S, we have
(cost((,, co C(S)) cost(S, C(S)) < Err(S, P),
which implies
Err(S, P)" (1 Eri(S, P1) cost, (S, C(S)).
cost (P, C(S)) E
For an a-approximate center set C of S, we have
cost(P, < (1+ Err(S, P)) cost(S, C) 5 (1rrS, a cost(S, C(S)).
Combining these gives:
rp(S,a) S (1 + Err(S, P))?
(10)
This implies that (S a) (1 + a 0( 8nd OPT
V OPT ))
8nd
a.
C.1 Proof of Lemma C.2: Bounding Err(P. P)
For each P, recall that & = p- - p is the noise vector. We first have the following claim that bounds norms of these noise vectors.
Claim C.4 (Bounding Eper 112) With probability at least 0.95, Epep 115p112 < 600nd.
Proof. Note that for every p P.
ES, [16
0 Dg
Σ o
= > Var Varep. [Spol - Egps Dyn [Sp,1]
= fd.
(Defn. of D,)
22

---

Thus, we have
E p
15pp12 PEP
6nd.
(11)
Furthermore,
Var
Σ 11
PEP
Varg, [115:11]]
(12)
n (Es, [11Ep112 -Es, [1|E> 112 ?
On (2d + d2 Od.) 30nd
where (d) represents the chi-square distribution with degrees of freedom, whose variance is known to be 2d [69].
If 0 < 20n we have that
Pr
1 = 0 = (1 0)" (1
20n )" 2 0.95,
PEP
implying that Prp
1 Eper 116p112 S 600nd] 2 0.95. Otherwise, if S n we have that
Pr
1ksp112
600nd
pEp
Pr
Σ
1k
l/2
Ep
Σ 16pll2
33v0n On
Var
1|5p11 PEP
Σ
(Eq. (11) and Ineq. (12))
PEP
PEP
(Chebyshev's 's ineq.)
10000n
1
0.05.
(0 2 20n
Thus, we complete the proof of the claim.
Now are ready to prove Lemma C.2.
Proof of Lemma C.2. By Claim C.4, with probability at least 0.95, ΣpE P 11pp < 600nd, which assume happens in the following. It suffices prove that for any center set C C.
600nd
150nd
(cost(P,C) cost(P, (P,C)) <
OPT 4
cost((P.)) (P,C).
(13)
OPT
By the triangle inequality, we know that for each P, [d(p, C) d(p, C)I < 115pl12, which implies that ld C) - d C)I < 1| + 2112 d(p, C)..
23

---

By a similar analysis of Lemma D.8, we have cost(P,c) = O(cost(P,C)) (), since we assume OPT 0nd, thus we have
cost((P,C) cost((, (P,
cost(P,,) (P,PP) C)
Σ Eper 16 122 + 2/15p112 d(p, C)
Dost(P,Co C)
600nd
2 2xper 115p 112
d(p. C)
(by assumption)
OPT
cost (CCt(
2 Epe PEP 115p113) Eppe d2 (p(,
600nd
+
Cauuhy-Schwarz
OPT
cost (P, C)
600nd
150nd
+
V
(by assumption)
OPT
cost( (P,C)
600nd
150nd
+ VV
(Defn. of OPT)
OPT
OPT
which completes the proof of Inequality (13).
C.2 Lower bound of Err( (er(P, P. P)
We provide the following lower bound for Err(P,
Claim C.5 (Lower Bound of Err(P, P)). With probabiiliy p > 0.8, Er((PP) = [2( Ond
OPTp! = )
Proof of Claim C.5. We show this by worst-case example. Let 0.1, 10000 and k n Let P (p: = 100ne; : i E [n]] C R where is the i-th unit basis in R An optimal solution and hence, OPT 10000n2. Note that with probability at least 0.8, the following events hold: Epep ||E, 12 = (fnd) and for every p E P. ||cp112 S 10d n. Conditioned on these events, the optimal solution C(P) of P must consist of points T E P and the average of the remaining two points in P. Assume C(P) = pi,.... Pn-2- Pn-1th. 6n calculation, we obtain that
C(P) = P P PP-22 Pnn-., Pa-1+pm
2
j. By
cost(P, C(P)) 2 (1 + 52 Ond
OPT ));
implying that Err(P, P OPT
D Proof of Theorem 3.3: Using Erra
Theorem D.I (Restatement of Theorem 3.3). Let P be an observed dataset drawn from P under the noise model I with known parameter E [0, P Let E (0, 1) and fix a E [1, Under Assumption 3.2, there exists randomized algorithm that constructs weighted S C for k-MEANS of size O klog Iond
(a-1)k log and with guarantee (8, P) with probability least
0.99. Moreover,
0kd OPT,
Va
VekdOPT 6nd
(S,P)
OPTp
and
0kd
Va
OkdOPT P + 0nd )) a. OPT
rp(S,a) 5 11++0
OPTP

---

Recall that we use Algorithm to construct such a coreset S. For ease of analysis, we provide the following assumption for the center set C obtained in Line of Algorithm 1. We will justify this assumption in Section D.4.
Assumption D.2 (Locality). Assume that for each & E C (i e [b)), ((, & O(r + Vd 1+0kd) Here, of represents the i-th center in C(P).
the following discussion, we denote of to the i-th center in C(P), and use (xX) Epex P denote the mean point of any dataset X.
[X] to
For preparation, we first show that given C (S), every center ei C lies within local ball centered at an optimal center oj E C(P).
Lemma D.3 (Structural properties of (S)). With high probability, for every C' Ca(S) and
every E [b], there exist a center e. E C such that c E B(e, O a(OPT+Ond lug?( vn-1
kd
Moreover
for each point p E Pi E i j. d(p. (i) < <dppog) oj).
Next, we provide some useful geometric properties of S.
Lemma D.4 (Properties of S). With probability p > 0.99,
For any i e [K] [I((P)) - ((S))113 < ( :OPT
OPTs S (1 + 0 (
Erra(S, S
Finally, provide upper bound for the movement distance of centers from P' to P, which helps bound the error caused by noise.
Lemma D.5 (Movement of centers of P'), With high probability, for any E [R].
- M(P:)11 < 0 Od
+ Vo 10d)
n2
Now are ready to prove Theorem 3.3.
Proof of Theorem 3.3. Suppose we run Algorithm to construct a weighted S C P for k-MEANS of size By Lemma D.4, directly have Err, (S,P) P) < E. It remains to prove rp(S,a) s
(1 O( + OPT
0kd Va-T T vokdOPT+Ond a.
OPT
Given an a-approximate center set C. {cI,..., C of S by Lemma D.3, we can assume min.ec. d(p.)) e) = e; for any E [k] and any point p E P.. This implies that any point p E P; satisfies d(p, c.) < d(p, 0j) for any j * i.
25

---

Then we have
Tp(Ca)
cost P.. Ca)
OPT
Eiet cost P. G. cost(Pp:
OPT
Eiennilles nilla ((P:)ll2 +1
OPT iEN
Eiek n. (IIu(P,) - m(Pill + (I((P)))))))))))))){()) ((S))I + ll))s))) - +112
OPT
(Triangle inequality)
O(=OPT' 0kd + Va 10nd + V(a 1)0kdOPT) (a 1)OPTs
OPT
O(5OPT' + 0kd + va - I0nd + V(a 1)0kdOPT) + (a 1)(1 + 0 0)PP
Va
+1
OPT
(++0(
Okd OPT
Va 1
VOkdPPT + Ond
a
OPT
This completes the proof.
D.1 Proof of Lemma D.3: structural properties of (S)
Useful properties of P. For preparation, we first show some properties of P. In the following. Claim D.6 and Lemma D.7 show that the clustering cost for 1-MEANS remains stable under noise perturbation. It also helps bound the cost difference in each cluster in the general d-MEANS setting.
Claim D.6 (Statistics of cost difference). In 1 1-MEANS problem, for any center e E Rd, we have
cost (P c) - cost(P. c) = Σ
11 + Σ (Ep: p c).
peP
PEP
Moreover, we have
Ep Epep 1|sp = Ond and Varp EpEp 115p113 < <30nd:
Ep EpeplSe:P-o c) and Var EpEplEp: c) cost(P,c).
Proof. We have cost P. coost(ssP)))) =ee)==ppPar d (P,c) (p,cc) Eper p-c).
For the first error term Σpep 115, we have E,s Epep 115p 0nd, and
Varp
Σ 1152112
pEp
n Varg, [115p11]]]
(Es, [116p112] - -EG [1]sp112]]
On (2d + dt - 0dd2) 30ndd
where (d) represents the chi-square distribution with degrees of freedom, whose variance known to be 2d [69].
26

---

For the second error term Σpep ppp. p c), its expectation is obvious 0 and we have
Varş
Σ PEP
(Sp, - c)
=
Σ
Vang,
[(.. c)1
PEP
Σ LE, (5p P ct21
PēP
0
lp - c12
PEP
0 cost((P,pp
By Claim D.6, it suffices prove that
Epep | + Epppppl c)
Ond
0d
sup
00
(14)
cost(P.c)
OPT
OPT
<ER4
By Claim D.6 and Chebyshev's inequality, directly have that EpEp 15p S 20nd happens with probability least 0.95. For the second error term 2 EE c), we provide an upper bound by the following lemma, which strengthens the second property of Claim D.6.
Lemma D.7 (Error bound for 1-MEANS). In 1-MEANS problem, with probability at least 1 1 0.056
for 0 < 8 1, the following holds
(p c)l (Ost(P,c)
Od V 80PT
sup ogRd
10
Proof. Let X - P: E * 0) be random variable. When On I 0.018, we have Pr[X 0 = (1 0)" 1- 0.025.
Conditioned on the event that X O, have
Eper(6p:1 - c)l
sup
(P,
cER
which completes the proof.
In the following, we analyze the case that On > 0.015. Let E be the event that ||
Epep Spl12 s
Ol Ond/ō). We have the following claim:
Pr F 2 0.025.
(15)
Note that E[X] = On and hence, Pr[X < 1000n/8 2 1 - 0.018 by Markov's inequality. Hence, only need to prove Pr [F X 1000n/8 6] for Claim 15. Also note that Epep Ep has the same distribution N N(0, X Ia). Then by Theorem 3.1.1 in [82].
Pr
Σ PEP
Epll2 S 10 X S 1000n 1
Thus, we prove (15).
In the remaining proof, we condition on event E. Fix an arbitrary center c E Rd and let I = ||c C(P)ll2. By the optimality of C(P), it is well known that
cost (Pst(P.c) c) = cost(P, C(P)) + n ||e C(P) = OPT nd?.
Note that Eper(Sn.P - c\1 < Eper C(P)) + Eper (Sp, C(P)) By Chebyshev's inequality, have
cost( (P, (est((,C(PP) ((P(()) 0.018. (16)
Prl
Σ (Sp.P C(P)) 2 10 OPT/8 < P PEP
(10 OPT/8)2
27

---

We also have
Σ PEP
(5p, c- C(P) & Σ
Spl1al1c C(P))
(Cauchy-schwarz))
PEP
(17)
s
101
VOnd/8
Combining with Inequalities 16 and 17, we conclude that
Epper(pp12 c0l co I 20
1. -.Vond/e
Od
OPT + nl? S
V 80PT
happens with probability least 0.95, which completes the proof of Lemma D.7.
Recall that P. denote the data clustered to o in P. where cç is the i-th center in the optimal
cluster of P. We P. denote the points in P; with the presence the noise, and C to denote the mean P.. Now we bound OPT in the general k- k-MEANS case.
Lemma D.8 (Bounding OPTp). With probability at least 0.9, we have for all i [k]
cost((,,,) OPT; + O (On,dk: + vodk- OPT:) S 1.50PT; O(fm,dk)).
Besides, we also have with high probability
OPT S Σ cost P., P., OPT O(Ond + vOd OPT)
Proof. Similar to the 1-MEANS setting (Claim D.6), have the following decomposition of the еггoг
cost (P,,))
25 cost(P:, S cost((.,.c) cost((P,,c) =
Σ
1 +2
Σ
(5.. P - ci).
PEP:
PEP.
Besides, we have the following variance of the error terms
Ep Epep, [|sp12] = Ondd and Varp, E 115a = O(0n,dP);
Ep, EpEr, ( ci) and Varp, EpEp, (5p. p c:) = =8.
From Lemma D.7 by choosing 1/k; we know that with probability at least
0.05
we have
b
Epee p. (5m, P - ci)l cost (Pr, es)
Odk
sup
10
V OPT;
cERd
Besides from Chybeshev's inequality, we also have EpEp; 11&, < 20n,dk happens with probability least k Then we conclude the proof by applying union bound E [k].
As shown in [10], under the stability assumption of the dataset, for any sufficiently good approximate k-MEANS solution {c....., } centers are pairwise well-separated.
Lemma D.9 (Restatement of Lemma C.1 in [10D. Given stabbe datasel P C RRd and a S 11+3 let C (e1...., 6k) be a-approximation center set. Then for any i, E [k] with + j. holds
that
OPP
d (c,,,;;) 2 minn,,,nn)
Ond log
OPT OpT+0ndl 0nd Ing (W=r))
By 0(1
have (c cj) 2 a O min(R.,ny)
OPT
Now are ready to prove Lemma D.3
28

---

Proof of Lemma D.3. For ease of analysis, we prove the structural property of P', and the property of naturally holds, as S is obtained by uniform sampling from Pr. We first show that with high probability, for all i, |P:1 > 0.5m; Note that for any p P.. P & P. implies that ||spl| > R - dp, @)) O(vd 4a
Note that since fn satisfies Bernstein condition for any j [d] if + O, we have
t²
Pr[lepa 2 E 0] exp
Vi [d]. t 0.
2(1 ((1++b)
Thus we have for large enough (larger than b).
Pr [[p..p] 2 tlsp * 0] - exx (-s(t)).
It follows that
SSp + 0 s 2dexp (-o(
Pr IIll 2 E + S d. Pr Sp
Vd
Thus for any single point p P., with probability at most o(1), 1 & B(c,, Ra). Then we have |P|| 2 0.5n; with high probability by Chernoff bound.
Note that for any points ç in P.
d(p.ct) S d(p,c) + a()
R, ( + O(Volog 1 Okd
(Assumption D.2)
Va
(T)) O(v O(Vilog 1 Akd
(Ta S 877)
Va I
OPT O(V
) OV + Okd
Va
a(OPT lnd
kd
O(V
Va-I
n₂
(LOPT-Ondlog
Suppose there exists i [k] such that C B OV
-. Then
cost(P' P', C) >
CP,C(
Σ (CC,ct)- - (p.cc)
PEP!
n
0 aOPT + 0nd),
2
ni
w a O(PTT + 0nd).
By Lemma D.8, we have with high probability
OPT' <0(OPT + +0nd).
Then we have
cost(P" C) cost(P/, C) a O(OPT 0nd) OPT'
2 a.
OPT' Thus we prove it by contradiction. This directly implies that for any i E [k), there exists exactly one
OPT'
kd +O
center 6, satisfying e E B(e;, O
Moreover, by Lemma D.9, for any
j E [k),j # i,
OPT + Ond log 2 Va
((), 2 a. 0
min (2,, n2)))
29

---

Then we have
d(p,c)) Sr, Sritdda, S O(d(e,,)))
Thus for any point p P..
d(p.c) -(p.cc))dpp.c))---- ddp,c))))))))
which completes the proof.
D.2 Proof of Lemma D.4: properties of S
Lemma D.10 (Movement of coreset centers). Let P be of points and let S be set m points sampled uniformly at random with replacement from P, let OPT Exer |> - p (P)). then
OPT
E(1 [(I) (sS)
TU
Proof. For each p P. let dy == p - u(P). Obviously Eper dp 0.
Thus
-pes(P- p(P))
- (II((P)-M())))
=E
m7
Σ
d
m
PeS
1
Σ PES
1d +2
Σ
(dei
m
Pe.PYESiicj
Epep
d
ΣΣ
< dp
P(m,n)
PEP
OPT
Σ dps Σ dg
nm
P(m,n)
PPEP
QEP
OPT
nm
where P(m,n) is polynomial in and Now we prove Lemma D.4.
Proof of Lemma D.4. For any E [k], by Lemma D.10, B([la(P)) ((S))l1P)
OPT: [rll.
Note that [P'] > 0.5m, and my > O Let =s- OPT
va-Tond
Then by Hoeffding bound, with
p 2 0.99,
-(S)) 0 kOPT
E d'OPT T1
= O
[PN||
Next we discuss the upper bound of OPT Let C' = ch...., cf be the optimal center set for P! with cost OPT'. Given an a-approximate center set Ca fci.... ), For each point S,
Wp
[
thus
E (o,st(S,, C")
m;
Σ ZEP!
ll C²) w. = OPT.
PM
30

---

Then by Chernoff bound, we have for any t >> 0 and i E [k]]
Pr [)) - OPT *OPT S exp
-22
)
12 m
)
Set t O (V log and by union bound, it follows that
Pr [s, OPT 2 1OPT S 0.01
Thus, with probability > 0.99.
OPT s S CS) 1+0 (+ |
OPT' < (1+ 0 ))PPT'
m
Having the above properties, we conclude that
(S, cost (P,, C.)
aOPT p
E, cost(P,,,,) cost cost(P,,,s P., ct)
-11 -11--
aOPT'
Σ, nillm((P)) col3
aOPT' (1 -1-
>. (T(()((P.) u(P))) + (I((P))) - ((S))l - ail) (1- 1
(M()))
aOPT'
(Triangle inequality)
O(s'OPT' + - 10nd) + (a - 1)OPTs -1 -
aOPT'
(a ()PT OPT')
aOPT'
Va Is
00
+
(Lemma D.4)
α
<e
The last inequality is ensured by fixing sufficient large constant factor in the sample size. This completes the proof.
D.3 Proof of Lemma D.5: movement of centers of p
Recall that P; = (p + Eplp E P.) C P represent the cluster with noise corresponding to P. Let
O P. B, O+++; P. B, where j + i, 1, == U.z: By the above definition, have
P. = (P. U.
For simplicity, we use n;, ni" noue to denote [P.]. |4| respectively.
Lemma D.11 (Impact of removed points). With probability p > 0.99, for any [k].
Epeo, - ix()) & O(Va - T. Od). nf
1p- < 0 0d).
Proof.
Note that since Ep.j satisties Bernstein condition for any [d] Ep + we have
(-
t²
Pr [1ppal 2 E * 0] < 2 exp
(_2(1+b()
Vj [d. t 0.
31

---

Thus we have for large enough (larger than b),
Pr[Knn 2 115p + 0] - 2exp (-Q(t))
By union bound, with high probability,
(-D((2))
Pr [rll 2 Blpp + 0J S d Pr [Epol 2 Vd
Eo + s 2dexp
Note that for any p O,,
1 0kd
- 1 - Ep - (PP)lll + |1l/ s 2(r; O(Vdlog
)) 115p112
va -
Then we can decompose the cost as
Σ pEO:
lp- - 1(P))13
2(r; + O(Vdlog 1 0kd
2² Va - - +1) p(l1spll ()dt
< n, 0
n1 0-
9t? 9t2p(1Epp1 t)dt.
n+tOlvdlog 2)k
Note that when [r 2 16p + 0] < 2dexp (-1(( for a constant p(1k<pl 1) satisfies that
ct
p(lspll =t) s 20V
(-a)
Thus
Ti O(Vdlog L-Akd Va
Jnsorov/ama ep(lle/1 t)dt s d(ri OVV
1 0kd Va
)) exp|0( vd
< 10va--1a Id).
Then applying Markov's inequality, we have with probability 0.99,
Σ
ll 1 (P-
S Σ
lp < -(Va-11-0 1.dd).
72
n4
PEO:
PEO:
By the definition of I, B(G, Ra) for any p I,, thus
max |lp ((P.))) < 2R. net.
Note that for any point E T; 2 P,,
|| -- < R; + 1pp l/1l2 < R, Ry + 11lp122
By the stability of dataset P. every point E 1; P, satisfies that
OPT + Ondlog²(
kd
OPT + 0ndlog² (an kd
(va=T)
12 2 O( min(n,,n,))
Va
O(R, R,) 2 O min(n;, n2j)
32

---

Thus
3/1
1p
(P))) v Bi n
An to R2:))
PEL
4 AR
E ((ng))))
n?
ARl n² 0
On log
va-i
kd
exp [-2((R:) exp
- -22(
n²
n2g
2 O(1 (2) exp
On log
kd
va-1
-92(
n4.
n4
O(dd Va 1) 1)
Then we complete the proof by Markov inequality.
For the center of P; and P;, we have the following properties:
Lemma D.12 (Movement of noisy centers). With high probability, for any E [M]
Od
[Ix(P.)) u(P:))l < 0
74
Proof. Note that
((P:)) = Epere 1 =M(P)) +
Eper. Ep
nh
n2
Thus remains show
Epep, &x
12 < 0 Od
As shown in Claim D.6, Bp We also note that F. [1 E1Epp, Solla
E Epep. 11 = Ongd and Var EpER 11Ea11]
s dtn,
< O (((onnd) and
Varp,
Σ Epllz < E.
Ep
E.p
Σ
1kr
=nn,d
PEP:
pEP:
PEP:
which implies that EpER, E0ll, O(vOnid) with high probability. Therefore, with high probability, we have:
- (R()) 00
( Od
ng
This completes the proof.
Now prove Lemma D.5.
33

---

Proof of Lemma D.5. For any i E [k], we have
|| E EpEpi ((P))
[p((P)) - =(P))
T4
Epery D Epeo, P Eper, ((P)))
E EpEo, (p- (((P))
((P.))
11
n4
2mput
2m
lpp u(P2)11 +
Σ
1p - (P))(E
n
PEO.
pEt
x (
(Lemma D.11)
By Lemma D.12, with high probability,
Od
< 0 o0=))
74
Thus
Od
( s - - O va
-):
which completes the proof.
D.4 Justifying Assumption D.2: Finding center sets within local balls
Lemmas D.8 and D.12 provide us with control of the clustering cost and location of the optimal
center set C(P) of P. Together with Assumption 3.2, we know that P is ((a)) (oo))-cot-staaleee By [71, 59], we can efficiently compute an O())-apprxximate center set C' E C for such stable P. Partition P into Pı,... Ps of this C. Using similar argument for Lemma D.11,
show that Pn B(c,, Or1; + Vd va-I S P.. Furthermore, by similar argument for D.12, we can show that (P.)) E B(q, O(r, + Vd )tadd). Thus, letting Ö be the collection p p(P.)'s satisfies Assumption D.2.
E Missing results and discussions from Section 3
This appendix provides additional results and clarifications supporting our theoretical analysis. We first examine the necessity of the cost-stability assumption in worst-case settings and then illustrate how to examine Assumption 3.2 in practice. Finally, we show the impact of using an approximate optimal solution of P in the algorithms.
E.1 Necessity of the stability assumption in the worst case
We present an example to demonstrate the necessity of the cost-stability assumption (Assumption 3.2) for ensuring meaningful separation between the traditional error Err and the proposed Err...
Consider the 3-Means problem in R (i.e., k 3, d = 1). Let P R consist of T points each at positions 22. 12 12 and 3.25 A simple calculation shows that the optimal center set C(P) is either {-3.25 - 1..5 2 or (3.25v2, 1.25 -2.25/2), yielding OPT n in both cases. Moreover, for the 2-Means problem, the optimal centers are at (+2.25 2). giving OPT 1) 2n 2 OPT,((). Hence, P 7-cost-stable with 7 1.
Now let P be noisy version of P generated under noise model with 0 1, where each perturbation sampled from ((0, 1). Using the known expectation Ez-N( [|=]| 0] 22/TT, we can approximate the means of the three clusters in P 2 2/ 0. and 2.25 2
34

---

respectively. Thus, the likely optimal center set for P C(S) = (-2.2522 0,2,2,,22222 /2/T), leading to:
Err (P, = cost(P,
0.82.
pkk)
By further computation, approximate P by assuming Ep = =1())) 2 for each point p.
then we observe that OPT p = 1.24n, thus Err(P, = Err(P, S Em PP.
[PT cost( 0.47. This implies
+ ,
This example underscores the importance of Assumption 3.2: in worst-case scenarios without cost-stability, the two errors may become comparable, and the benefit of using Err, may diminish.
Empirical comparison of metrics. To further compare the behavior of Err, and Err, we conduct simulations on synthetic datasets with varying separation levels B.
Let P consist of a 4 points each at positions p1 = 22 8v2
-Bv2 Ps = Bv2 and
2
2
P1 = 2/2 + 2 When 3 2.5, this setup matches the example discussed above. Note that the distances |P2 P1 |P4 Ps| = 2v remain fixed, while only the inter-cluster gap |ps 1 varies. This ensures that OPT, 0nd and y hold for all / 2
8/2
We set 10,000, k = 3, and vary 8 from 2 to in steps of 0.05. The dataset P is perturbed under noise model with 0 = 1 to obtain P.
We compute near-optimal k-means++ centers for P and P, denoted C* and C+ respectively. We approximate Err, (P, P) by computing cost(PP.C*) 1.
To estimate Err Err(P,)) P). we randomly sample 500 candidate k-center sets Ci...., C5oo. each con- structed by uniformly sampling k points from the interval [minn( P), max( We define
Err(P, P) == mix000 (oss((P,C)-coott(
cost(PPC..
proxy for the classical Err metric.
Eny(P, P)
0.7
Emr(. P)
0.5
empirical
separation level
Figure 1: Empirical comparison of error metrics Err, separation level 3 varies. While Err, responds to changing cluster geometry, Err remains nearly constant, illustrating its insensitivity to structural properties in noisy settings.
Err, (P, P) and Err(P, P) synthetic data the
Figure presents the results. 3r 2.5, we observe that Err(P, P) 0.41 and Err, P) RJ 0.74, consistent with our theoretical discussion. The overall trend confirms that Err and Err,, can diverge significantly in value.
35

---

Interpretation. This simulation supports our comparison between the classical error metric Pr and the proposed surrogate Err. (P, P). It shows that Err is relatively insensitive to changes in the structural properties of the dataset, potentially underrepresenting approximation error data becomes less separable. In contrast, Err.. approximated here via Err decreases with & (when 3 2.5), reflecting the growing challenge of summarizing data as cluster separation decreases.
Even when the optimal clustering is unaffected by noise-ie.. OPTp and cluster geometry remain stable-Err remains nearly unchanged, while Err,, adapts to the increased representational difficulty. This divergence (e.g.. 0.41 vs. 0.74 at B 2.5) underscores their differing sensitivities.
These findings reinforce theoretical argument: Err, is structurally aware and more reliable metric for noisy settings. This justifies its use in guiding coreset construction and motivates algorithms such CN that explicitly target this measure.
Interestingly, we observe that Err, remains small even when the separation is minor (e.g., Err, < 0.1 2), suggesting that Erra may also better align with the ideal metric rp in the presence of noise when clusters are close. This opens promising direction for strengthening our theoretical guarantees in low-separation regimes.
E.2 Examining Assumption 3.2 in practice
We detail the process for examining P in CN., whose goal is to estimate whether P meets the data assumptions.
Given P and an ((1)-approximan) center set CR for k-MBANS problem. let OPT(K) :- cost(P, Cx). Correspondingly, compute an (apprxxmmtee center set Čk-1, let OPT = cost (P, For cost stability assumption, we directly verify whether
OPT(K-1)
2 10a) (1+ OPT(K)
Ond (kd//V
(PT(A)
Suppose P does not meet the stability assumption, for example, there exists solution Ck-1 for (k: 1)-Menss problem, such that cost(P.Ci-1) < 1 +yy. Then it's likely that a corresponding solution
OPT,
for P will also violate the stability assumption.
For the assumption that r; 87; consider removing the top 1% of points in P with the greatest distances C, resulting in a trimmed dataset P. Recompute rs, F; for this adjusted dataset and Ö and check if r; S 8r; holds for every E [A:].
E.3 Impact of Cost Estimation of OPT P on Algorithm Performance
We discuss how the estimation of the optimal cost OPT affects the performance of CN, and CN. Generally speaking, a c-estimate (c 2 2) of the optimal cost on P worsens the error guarantee for CN (using Err measure) and hardens the data assumption for CN, (using Err, measure). Below we illustrate these points.
Suppose we are given a center set Ô for coreset construction, whose clustering cost cost (P, OPTp for some >> 1 (c-estimate), where P is the underlying dataset and P is given noisy dataset.
Impact on CN. Let S be a coreset derived from CN. Employing c-approximate estimate Ō can weaken the quality bound of S by up to factor of in the following sense: With an exact estimate of OPTP, Theorem 3.1 provides a bound on the worst-case quality of an a-approximate center set of S as
a)( < (I+5+0
(
Ond OPT
Ond OPT
ar
In contrast, using CN with the approximate estimate Ò yields the following bound for the derived coreset 5:
(
And 2 OPTp
)) a.
rp(S,a) [Ito
0nd OPTP
36

---

Compared to the exact estimation case, this bound increases the error term from E to c E. This arises because the importance sampling procedure from [10]. used in CN, introduces an additional error term (oCt( c its analysis, whereas the term O O P +
0nd
results from OPTp)
Ond
PPT,
Err(P, P) and remains unaffected by the quality of the estimation.
Impact on CN.. Let S be coreset derived from CNa. Using c-approximation estimate Č weakens Assumption 3.2 by factor of c; specifically, the required cost-stability constant y increases by this factor. Consequently, the range of datasets satisfying the theoretical bounds of CN, (as stated in Theorem 3.3) shrinks. This occurs because the performance guarantee of CNa relies on correctly identifying k separated clusters, task complicated by the approximation error in Ò. Increasing by factor of ensures these clusters are accurately identified, restoring the desired guarantees.
Additionally, using a c-estimate may still result a high-qualified coreset as with perfect estimate in practice.
F Extensions of Theorems 3.1 and 3.3
This section extends Theorems 3,1 and 3.3 to other noise models and general (k,z) -.LUSTERNN,GGG
E1 Extension to other noise models
Noise model II. Recall that under noise model II, for every i E [n] and j E [d] P.y = Pt.j + Ep.j where Sp. drawn from Dj. a probability distribution on IK with mean variance a² and satisfying the Bernstein condition. The following Theorem shows the performance of coresct generated using the Err metric under noise model II. The only difference from Theorem 3.1 is that we replace 0 by o
Theorem F.1 (Coreset using Err under noise model II). Let P be drawn from P via noise model II with known o² 0. Let (0, 1) and fix a 2 Let A be an algorithu that constructs a weighted subset C P for k-MEANS of size A(E) and with guarantee Err(S, P) S Then
Err S + O
and OPT
a2nd OPT
and r (S, S (1 + + O gdnd
+
a2nd ))²
OPT
/OTP
Proof. By similar argument as that of Theorem 3.1, we only need to prove the following property:
Ep
Σ 1
O()2nd), and Varp
Σ 112 = O(o2nd)),
pEP
pEP
which again holds by the Bernstein condition.
For the Err, metric, we first give the data assumption under noise model II, adapting from Assumption 3.2.
Assumption F.2 (Data assumption under noise model II), Given and o² 2 assume P is c-cost-stbble with
= O(a) (1+ nnd 2
kd
OPTp
and that S 87, for all i E [k]].
Theorem F.3 (Coreset using the Err,, metric under noise model IT). Let P be an observed dataset
drawn from P under the noise model II with known parameter o² [0. OPTp], Let E (0, 1) and fix [1 Under Assumption F2, there exists a randomized algorithm that constructs a weighted S Sc P for K-MEANS of size O
klogk
(a- (o-11)llop log
Io-Io"nd and with guarantee (Sr P)
Ta-Io-
(c-
aOPTP
aCPTp
Moreover,
Err. P) < ( kd OPT
Va-1
and
OPT
TP(S,a) S (1 (1+ 0
d² Rdd
Va-1
oo4kdOPT p a. OPT
OPT
37

---

Proof. By similar argument as that of Theorem 3.3, we have the following property:
Ep Epep 11&p 1kpp1 O() and Varp EpEp 11pp18 O(o2nd)),
Ep Eperlsp. cs) and Varp Epperlsn.-- - c) = = - (o,)(P,c).
which holds by the Bernstein condition.
Similar to the proof of Lemma D.12, for any E [k], Rp, [I Epep Solla] - 5O(vonnd) and
Varp, Σ
Splla
< Ep
Epl12 = Ep,
Σ
11sp112 = O(orngd),
PE P.
P
PER
|EPEr Sol1z S <O(Vo'n:d), which implies
Then by Chebyshev's inequality, with high probability,
[m(P.) (u(PP))(((e) -((.)( = -iEeer Eo 1 S 00 Ad.
T4e
The remaining steps remain the same in Theorem 3.3.
Non-independent noise across dimensions. For simplicity, we consider a specific setting where the covariance matrix of each noise vector &p is Σ Rdxd Note that under the noise model II, Σ ==02 o². La when each Dj = N(0, r²). In contrast, this setting considers non-independent noise across dimensions.
Note that the above proofs rely on certain concentration properties of the terms Epe 11 and EpeplEp: c). In general, [ trace(E). Hence, by similar argument as in the proof of Claim D.6, one can show that Eper ||Ép 11 concentrates on n (E) and Eper - e) S
O( O(ttrace(E) (E) cost(P, c)). The only difference with Theorem 3.1 and 3.3 is that replace the original variance term Od to trace(E).
Theorem F.4 (Coreset using Err under non-independent noise model). Let P be drawn from P under indeedddenndnt noise model where each E, is drawn from D, [0, E). Let (0, 1) and fix 2 1. Let A be an algorithm that constructs a weighted subset C P for k-MEANS of size A(E) and with guarantee Err(S, S Then
Err(S,P) E O trace E)
n trace OPT
and
OPTp
trace Σ)
trace (Σ)
rr(8, < (1 + 0("
OPT ))²
OPTr
Proof. By similar argument as that of Theorem 3.1, we only need to prove the following property:
E
Σ 11 O(n trace(E))), and Var
Σ 11
= O(n trace(2))?.
PEP
PEP
The remaining steps of the proof remain the same as in Theorem 3.1.
For the Erra metric, also extend Theorem 3.3 this noise model. Assumption F.5 (Data assumption under non-independent noise model), Given a 2 and covariance matrix E E [ddxd assume P is --cost-stable with
7= 0(x) (1 (1+
n-trace (E)-log
Add
OPTP
and that < 87, for all i [k].
38

---

Theorem F.6 (Coreset using the E metric under non-independent noise model). Let P be an observed dataset drawn from P under ion-independent noise model where each Ep is drawn from
Dj = -O, with trace(()) E [0, ndd Let E (0,1) and fix a E [1.2]. Under Assumption
F.5, there exists randomized algorithu that constructs weighted $ C P for k-MEANS of size (a- 1)k log
0 va dPPTp
k log
and with guarantee E P) I E. Moreover,
(2)
va tracea
xOPTp
trace Σ)
va-1
V ( -PPT + (race(2)) and OPT,
Erra S
OPTp
k trace(E)) Σ)
Va-
Vk- (xrrcce(()) OPT trace(2)) a.
OPTp
a
OPTp
Proof. By similar argument as that of Theorem 3.3, we have the following property:
Ep Epep 11sp = On -traceEE),, and Vars Epee [1 = O(n traco (
Ep EpeplKe. of| and Var EpepkSsp c) trace(E) cost (P, c).
which holds by the Bernstein condition.
Similar to the proof of Lemma D.12, for any i [Ac].
Varp,
Slll P;P;
Σ
S Ep.
Σ
1
= Ep.
Σ 11 = =O(n trace (E))
pEP:
LEE
Epep, Eall22 S 50(v n. trace( E)), which
Then by Chebyshev's inequality, with high probability, implies
( | -1
Eper, &x S 0
trace(2))
ni
The remaining steps remain the same in Theorem 3.3.
F22 Extension to (k, -LLUSTERIIGG
The following theorem extends Theorem 3.1 (k:, C)CLISTREI under both noise models and II.
Theorem F.7 ((k, 2)- CLUSTTRRIN coreset using the Err, metric in the presence of noise). Let
P be drawn from P via noise model (or II) with known 0 2 0 (or o² > 0). Let (0,1) and fix 1. Let be an algorithm that constructs a weighted subset P for M--NS of size A(e) and with guarantee Err(S, P) S. e. Then for noise model I,
Err(S, P) S E + 9nd= OPT
And5/2
and (mdrp(S,a) s (1 + O OPT
And:/2
+
Ands// OPT
))² o0.
OPT
For noise model II.
Err(S, P) < 5
(00@@pppl mnd= OPT
g'nd=/2
OPT
and (P( < (1+++ O gnd OPT
+
g'nd=/2
OPT
))2
Proof. The case of k:MMAAS has been proved in Theorem 3.1. Now we show how to extend to (ks -I.UUSTRINN For the upper bound, the main difference is that have
(d C) d' (p, C)I < O2 (1ls, + |lpll2 d' (p,
d C)).
39

---

Table 2: Datasets used in our experiments. y represents the cost stability constant. r2 and T; are as defined in Assumption 3.2. Note that the assumption max; F. < 8 holds for both datasets. The Census 1990 dataset consists of 2458285 data points and we subsample 100000 from them. We also drop the categorical features of the datasets and only keep the continuous features for clustering.
Dataset
Size
Dim
k
7
max;
Adult
41188
10
10
0.07
7.52
Census1990
10
68
10
0.03
5.93
where O2(.) hides constant factor 20(a),
Similar to Claim D.6, we assume Epep 115 S O₂ (0nd=/2) by the Bernstein condition, which happens with probability at least 0.9, Then we have
(P,C) cost (P, (P.C)
cost, co,t,(P.C) (P.C)
O2 Epep 1k + 115p112 dF- dF-1(e,)))
cost:((,,))
O2 PpEPl 11spl12 d= d Cp)
O Ond
(by assumption)
OPT
OPT
O2 (2 ( 15pl)) Eppp (p, C))=-1
O Ond
(Generalized Hölder inequality)
OPT
OPT
Ond
((0ndz/2)
0 OPT
(by assumption)
OPT
And Ond=/2
0 OPT
(Defn. of OPT)
OPT
which completes the proof for (ki, -CLUSTTRRNN under noise model I.
Similarly, for C.LUSTERRG under noise model II, we only need prove the following property:
Ep
Σ 16
Oa(oFndd and Vars
Σ 11 O0(oa²ndd) PEP
PEP
which again holds by the Bernstein condition. This completes the proof.
The extension of Theorem 3.3 to general (k, CLLUSTERRN introduces additional technical chal- lenges, as the optimal center for is not the mean point, making it more difficult to control location of centers. Adapting the use of the Err. metric to general 2 remains interesting direction for future work.
G Additional empirical results
In this section, provide the implementation details of CN and CN and give more empirical results to corroborate our findings in Section 4. All experiments are conducted using Python 3.11 on an Apple M3 Pro machine with an 11-core CPU, 14-core GPU, and 36 GB of memory.
G.1 Implementation details of CN and CN,
Implementation of CN. Given the perturbed dataset P and budget 0, CN first computes an approximate optimal center set Č of P by k-means++ with max_iter and computes OPT cost2(P, (P.C), C). Then it constructs a coreset by the importance sampling algorithm [10] with coreset size |S| 5-- which represents the size bound derived by Err. The runtime of CN is ((ndk).
40

---

Table 3: Result of census1990 dataset under noise model I with Gaussian noise. |S| represents the coreset size, rss represents its empirical approximation ratio, and Kig denotes the ratio its empirical approximation ratio over the theoretical bound.
(a) f = 0
(b) 8 = 0.01
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
[S|
CN
9486
4216
2371
1517
1054
[|]
CN
9486
4216
2371
1517
1054
CN
CN.
1940
CN
CN
Fg
F5
CN.
1,057
1.067
1.079
1,071
1,087
CN.
1,088
1,059
1.063
1.071
1.071
CN
0.849
0.776
0.724
0.673
0.625
CN
0.655
0,602
0.565
0.530
0.498
K.5
CN,
0.961
0.928
0.899
0.857
0.836
Ki8
CN
0.945
0.905
0.872
0.843
0.812
(c)
0.05
(d) 0 0.25
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
[8|
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1317
1054
CN,
6834
3260
1928
1320
960
CN
6708
3176
1922
1320
960
Fgg
CN
1.024
1.036
1.057
1,053
1.059
Fis
CN
1.041
1.041
1.054
1.086
1.088
CN
1.911
CN,
K5
CN
0.893
0.851
0.821
0.815
0.781
Ki
CN2
0.682
0.653
0.656
0.648
0.620
Implementation CN.. Given the perturbed dataset P and budget e > 0, CN, also first computes an approximate optimal center set C of P by k-means++ with max_iter = 5 and computes OPT cost2 (P, C). Next, decompose P into is clusters P. by C. For each i [k], compute
cost (ost(Pl.E) (P.&) Then we compute P P3 Bi, where ball B, B(G, R₂) with R. Pl
F + v log 10(1 + Okd). For each E [k]. take a uniform sample S; of size min( 2 + - as an approximation of theoretical results. Finally, returns Useja S, with w(p) Similarly, the runtime of CN, is O(ndk).
PP| S;
for p E S.
G.2 Results on the Census1990 dataset
The setup has been shown in Section 4. See Table 3 for results. All observations are consistent with that for Adult.
G.3 Results under other noise settings
We present additional results under various noise settings using the Adult dataset, with the same noise levels and tolerance parameters as in Section Tables 4 and evaluate coreset performance under noise model I, replacing Gaussian noise with Laplacian and Uniform noise, respectively. The results are consistent with Table validating robustness of our theoretical findings across different noise types. Table 6 assesses performance under noise model II, illustrating the practical relevance of Theorem F.3, an extension Theorem 3.3. Table considers on-independent noise, as analyzed in Theorem F.6, and again shows consistency with Table 1. Overall, these results further support theoretical analysis, confirming that coreset performance under noise primarily governed by the noise variance.
41

---

Table Result of Adult dataset under noise model I with Laplacian noise Lap ) This choice of Laplacian noise ensures a variance per coordinate, matching that the Gaussian noise. [S] represents the coreset size, Fs represents its empirical approximation ratio, and Kg denotes the tightness ratio of its empirical approximation ratio over the theoretical bound.
(b) 8 0.01
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0,3
[S]
CN
9486
4216
2371
1517
1054
[8]
CN
9486
4216
2371
1517
1054
CN.
6428
3178
1940
1320
960
CN
6445
3178
1940
1320
960
CN
1,048
1.072
1.121
1.179
1,310
CN
1.036
1.031
1.093
1.118
1.243
Fi
F88
CN,
1.138
1.096
1.173
1.158
1.153
CN.
1,083
1.111
1.120
1.188
1.173
CN
0.866
0.810
0.778
0.755
0.775
CN
0.600
0.554
0.547
0.522
0.542
CN,
0.978
Kg
CN.
(c)
0.05
(d)
0.25
0.1
0.2
0.3
0.15
0.25
[S]
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1517
1054
CN.
6445
3178
1940
1320
960
CN
6445
3178
1940
1320
960
CN
1,030
1,078
1.217
1.095
1 1.881
CN
1.036
1.073
1.132
1.167
1.384
Fss
CN.
1.081
1.13
1.174
1.116
1.147
CN2
1.158
1.125
1.183
1.204
1,221
CN
0.370
0.364
0.389
0.331
0.367
CN
0.130
0.130
0.132
0.132
0,151
CN,,
0.855
0.847
0.860
0.789
0.783
CN.
0.603
0.571
0.586
0.581
0.576
Table 5: Result of Adult dataset under noise model I with Uniform noise UI-V3, v3J. This choice of Uniform noise ensures variance of per coordinate, matching that of the Gaussian noise. [S] represents the coreset size, is represents its empirical approximation ratio, and Ks denotes the tightness ratio of its empirical approximation ratio over the theoretical bound.
(a) 0
0
(b) 0 = 0.01
g
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
|S|
CN
9486
4216
2371
1517
1054
|S|
CN
9486
4216
2371
1517
1054
CN.
6445
3178
1940
1320
960
CN
6445
3178
1940
1320
Fi
CN
1.057
1.139
1.043
1,281
1,265
Fs
CN
1.026
1,050
1.128
1.224
1.158
CN.
1.155
1.208
0.724
0.748
CN
68
CN.
1.006
0.954
0.951
0.935
0.889
CN.
0.962
0.951
0.891
0.942
0.848
(c) 0
0.05
(d) 0 0.25
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
[S]
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1517
1054
CN.
6445
3145
1940
1320
960
CN.
6445
3178
1940
1320
960
CN
1.061
1.051
1.092
1.151
1.208
F
CN
1.064
1.061
1.099
1.228
1.295
CN.
1.111
1.33
1.136
1.163
1.111
CN.
1,117
1.136
1.217
1.220
0.381
0.356
0.349
0.346
CN
0.133
0.128
0.128
0.139
0,141
ON,
0.832
0.759
K.S
CN.
0.582
0.589
42

---

Table 6: Result Adult dataset under noise model with Gaussian noise N( o²). Here, o² controls the variance of noise, playing the same role as & under noise model I. |S] represents the coreset size, T' represents its empirical approximation ratio, and Kig denotes the tightness ratio of its empirical approximation ratio over the theoretical bound.
(a) Ø²
(b) x²
0.01
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
|S|
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1317
1054
CN,
6445
3178
1940
1320
960
CN
6445
3178
1940
1320
960
1.133
1,219
1.200
CN
1,039
1,066
1.075
1.104
1,280
Fig
Fis
CN
L.400
CN,
CN
0.845
0.787
0.722
CN
0.515
K5
CN
0.987
0.979
0.975
0.925
0.877
Kg
CN.
0.967
0.947
0.922
0.908
0.871
(c) a²
0.05
(d) a² 0.25
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
0.3
|S]
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1517
1054
CN.
6445
3178
1940
1320
960
CN
6445
3178
1940
1320
960
CN
1.045
1.074
1,218
1.135
1.234
Fs
CN
1,042
1.098
1.127
1.292
1.323
CN.
1.088
L115
1.129
1.123
1.399
CN2
L079
1.125
1.217
1,215
1,231
CN
0.375
0.363
0.389
0.343
0.353
CN
0.130
0.133
0.132
0. 0.1
0.145
CN,,
0.869
0.849
0.828
0.794
0.778
CN.
0.562
0.571
0.602
0.587
0.581
Table 7: Result of Adult dataset under noise model II with non-independent Gaussian noise We first generate the covariance matrix Σ randomly, and then
(0, z with trace(E)) apply it for different noise levels o². This choice of trace(E) ensures variance of a2d d per point, matching that of noise model II. [S] represents the coreset size, ïs represents its empirical approxima- tion ratio, and Ky denotes the tightness ratio of its empirical approximation ratio over the theoretical ratio.
(b)
0.01
0.1
0.15
0.2
0.25
0.3
0.15
0.25
[S]
CN
9486
4216
2371
1517
1054
[S]
CN
9486
4216
2371
1517
1054
ON.
6445
3178
1940
1320
960
CN.
6445
3178
1940
1320
960
CN
1.029
1.051
1.101
1.365
1.227
CN
1.022
1.039
1.133
1.147
1,340
CN.
1.044
1.149
1.136
1.119
1.175
CN
1.077
1.165
1.150
1.088
1.164
CN
0.851
0.795
0.764
0.810
0.726
CN
0.592
0.559
0.566
0.535
0.541
CN.
0.967
0.909
0.947
0.393
0.904
CN.
0.951
0.935
0.933
0.848
0.873
(c) 8²
= 0.05
(d) 0² 0.25
8
0.1
0.15
0.2
0.25
0.3
0.1
0.15
0.2
0.25
[8]
CN
9486
4216
2371
1517
1054
[S]]
CN
9486
4216
2371
1517
1054
CN,,
CN..
3178
1320
CN
CN
Fi5
CN,
1.083
1,066
1,14]
1,165
1.677
1.129
1.202
1.193
1.239
CN
0.373
0.350
0.335
0.348
0.383
CN
0.136
0.138
0.143
0.138
0.142
K.5
CN.,
0.857
0.826
0.836
0.824
0.797
KiS
CN.
0.588
0.609
0.595
0.576
0.584
43

---

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:
Contributions are shown in Sections 2, 3, and 4.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as 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: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in 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 low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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]
44

---

Justification:
See Assumption 3.2, Section C and Section D.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but 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. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: See Sections 4 and G.
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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
45

---

Answer: [Yes]
Justification: See http://hhh....ooocoooaoono///naa g Soaerr--Sochastic-Noisss
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/pu
blic/g guidee/ CodeeSumieiiieee isiiissionn orriiinnoccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not 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 to reproduce the results. See the NeurlPS code and data submission guidelines (https: CoodeSubmiis
httppp.ccppubiic///ecc / ssi asionPolicy 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 experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: See Section 4 and Table 2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: averages.
As mentioned in Section 4, we repeat each setting 10 times and report the
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
46

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
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 com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See Section G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as 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 or 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 NeurIPS Code of Ethics https: //te:///nessseee cc. htte/pullcc/Ehhisoooooooo csGuidel ines?
Answer:
[Yes]
Justification:
All submissions are anonymous.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration 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: [Yes]
Justification: See Section 5.
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 socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
47

---

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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe 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, scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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
Question: 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?
Answer: [Yes]
Justification: We mention that datasets are from the UCI Machine Learning Repository in Section 4.
Guidelines:
The answer NA means that the paper does not 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 is used and, if possible, include URL.
The name of the license (c.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 of use in the package should be provided. For popular datasets, paperswi www.whetood...c com/ ammaattsets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
48

---

If this information is not available online, the authors are encouraged to reach out to the asset'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/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 the main paper.
According the NeurIPS Code of Ethics, 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 an equivalent approval/review based on 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 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
49

---

Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https:/ /ttp://eeeurppeeeeeeeeeeee /ttparripp..eeeooeeeeeeeeeeeeeee /ec/Conffreecce/225////11 for what should or should not be described.
50


Reviews:
[{"review_id": "7N4WNw4naM", "reviewer": "Reviewer_XFgH", "summary": "The paper investigates how to adapt a coreset produced from a noise-corrupted dataset for the underlying clean data in $(k,z)$-clustering. It shows that the classical strong-coreset error $Err$ can become vacuous once noise is added. To address this issue, this paper then proposes a relaxed metric $Err_{\\alpha}$ that considers only center sets whose cost on the coreset is within an $\\alpha$-factor of the optimum. A separation construction illustrates that $Err_{\\alpha}$ can be exponentially smaller than $Err$. Under mild assumptions on cost-stability, balanced clusters and bounded radius, the authors prove that any standard sensitivity-sampling coreset built on the noisy data remains a good coreset for the clean data when evaluated with $\\mathrm{Err}_{\\alpha}$, maintaining an $\\tilde O(k\\log k/\\varepsilon)$ coreset size. Experiments on several public datasets with Gaussian noise confirm that the new metric allows 20–35 % smaller coresets while preserving clustering quality.", "questions": "I would appreciate clarification on the following issues: \n\n1. How does the guarantee degrade when the cost-stability constant $\\gamma$ becomes small and clusters are less well separated?\n\n2. What is the practical impact if the estimate of the clean optimal cost is off by a factor of two or more?", "limitations": "Since this is mainly a theoretical result, there is no limitations and potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "One of the key strengths is the conceptual clarity and practical relevance of the new error notion, which focuses evaluation on solutions practitioners actually search for rather than on all possible centre sets. The theoretical analysis is careful, technically sound and matches empirical observations; the resulting algorithm is simple to implement and inherits the best-known size guarantees. Presentation is clear, with motivating examples, lucid proofs and reproducible experiments that cover multiple noise models and real data sets.\n\nThe main weaknesses stem from the assumptions behind the theory. Cost-stability, well separation and balance may be violated in highly skewed or overlapping clusters, and the noise model is i.i.d. additive with sub-exponential tails, leaving correlated or heavy-tailed settings unaddressed. In addition, the need for a constant-factor estimate of the clean optimal cost is glossed over.", "was_revised": true, "final_justification": "The rebuttal addresses all concerns with solid theoretical arguments and well-supported empirical explanations The clarification on cost-stability effectively explains the trade-off between worst-case guarantees and practical performance, reinforcing confidence in the method’s robustness under challenging conditions. The discussion of how approximate clean-cost estimates influence the analysis is technically sound, demonstrating that while theoretical bounds may loosen, the practical coreset quality remains consistently high. Overall, this is a well-motivated, theoretically solid, and interesting paper, and I recommend acceptance while keeping my initial score.", "rebuttal": "Thank you for your thoughtful and constructive feedback. We are grateful for your recognition of the novelty, clarity, and practical relevance of our proposed error measure. Below, we address your questions and comments:\n\n### Response to questions\n\n> How does the guarantee degrade when the cost-stability $\\gamma$ constant becomes small and clusters are less well separated?\n\nThis is an excellent question. While the theoretical guarantees indeed weaken as $\\gamma$ decreases, we find that the practical performance of our method remains robust even in such regimes.\n\n**Theoretical degradation.**  \nAs shown in Appendix E.1, in the worst case, our new error measure $\\mathsf{Err}\\_\\alpha$ can exceed the classical measure $\\mathsf{Err}$ when $\\gamma$ is small (e.g., $\\gamma = 1$). This illustrates why the cost-stability assumption is essential for our formal guarantees—without it, the superiority of $\\mathsf{Err}\\_\\alpha$ cannot be established in theory.\n\n**Empirical robustness.**  \nDespite this, our algorithm $\\mathrm{CN}\\_\\alpha$, which uses $\\mathsf{Err}\\_\\alpha$, consistently outperforms the $\\mathsf{Err}$-based baseline in practice—even on datasets with significant cluster overlap. For example, on Adult and Census1990, where the estimated cost-stability is as low as $\\gamma \\leq 0.07$, our method still achieves smaller coresets while maintaining clustering quality (see Table 2).\n\nWe will incorporate a brief discussion of this tradeoff in the theoretical section of the final version to clarify the contrast between worst-case bounds and empirical behavior.\n\n\n> What is the practical impact if the estimate of the clean optimal cost is off by a factor of two or more?\n\n\nThank you for the insightful question. A $c$-estimate ($c\\geq 2$) of the optimal cost $\\text{OPT}_P$ on $P$ worsens the error guarantee for $\\mathrm{CN}$ (using $\\mathrm{Err}$ measure) and hardens the data assumption for $\\mathrm{CN}\\_\\alpha$ (using $\\mathrm{Err}\\_\\alpha$ measure). Below we illustrate these points.\n\nSuppose we are given a center set $\\widehat{C}$ for coreset construction, whose clustering cost is $\\mathrm{cost}(\\widehat{P},\\widehat{C})=c\\cdot \\mathrm{OPT}_P$ for some $c>1$ ($c$-estimate), where $P$ is the underlying dataset and $\\widehat{P}$ is a given noisy dataset. \n\n**Impact on $\\mathrm{CN}$:** \nLet $S$ be a coreset derived from $\\mathrm{CN}$. Employing a $c$-approximate estimate $\\widehat{C}$ can weaken the quality bound of $S$ by up to a factor of $c$ in the following sense: With an exact estimate of $\\mathrm{OPT}_P$, Theorem 3.1 provides a bound on the worst-case quality of an $\\alpha$-approximate center set of $S$ as\n$$\nr_P(S,\\alpha)\\leq \\left(1+\\varepsilon+O\\left(\\frac{\\theta n d}{\\mathrm{OPT}_P}+\\sqrt{\\frac{\\theta n d}{\\mathrm{OPT}_P}}\\right)\\right)^2\\cdot \\alpha,\n$$\nwhere $\\varepsilon$ is an error parameter, $\\theta$ is the noise level, and $d$ is the dimension. In contrast, using $\\mathrm{CN}$ with the approximate estimate $\\widehat{C}$ yields the following bound for the derived coreset $S$:\n$$\nr_P(S,\\alpha)\\leq \\left(1+c\\cdot\\varepsilon+O\\left(\\frac{\\theta n d}{\\mathrm{OPT}_P}+\\sqrt{\\frac{\\theta n d}{\\mathrm{OPT}_P}}\\right)\\right)^2\\cdot \\alpha.\n$$\nCompared to the exact estimation case, this bound increases the error term from $\\varepsilon$ to $c\\cdot \\varepsilon$. This arises because the importance sampling procedure from [9], used in $\\mathrm{CN}$, introduces an additional error term $\\varepsilon\\cdot\\frac{\\text{cost}(P,\\widehat{C})}{\\text{OPT}_P}=c\\cdot \\varepsilon$ in its analysis, whereas the term $O\\left(\\frac{\\theta n d}{\\mathrm{OPT}_P}+\\sqrt{\\frac{\\theta n d}{\\mathrm{OPT}_P}}\\right)$ results from $\\mathrm{Err}(\\widehat{P},P)$ and remains unaffected by the quality of the estimation.\n\n\n**Impact on $\\mathrm{CN}\\_\\alpha$:** \nLet $S$ be a coreset derived from $\\mathrm{CN}\\_\\alpha$. Using a $c$-approximation estimate $\\widehat{C}$ weakens Assumption 3.2 by a factor of $c$; specifically, the required cost-stability constant $\\gamma$ increases by this factor. Consequently, the range of datasets satisfying the theoretical bounds of $\\mathrm{CN}\\_\\alpha$ (as stated in Theorem 3.3) shrinks. This occurs because the performance guarantee of $\\mathrm{CN}\\_\\alpha$ relies on correctly identifying $k$ separated clusters, a task complicated by the approximation error in $\\widehat{C}$. Increasing $\\gamma$ by a factor of $c$ ensures these clusters are accurately identified, restoring the desired guarantees.\n\n\n\nAdditionally, we would like to remind that the above analysis considers a worst-case guarantee. In practice, using a $c$-estimate may still result in a high-qualified coreset as with a perfect estimate.\n\nWe will add the above analysis to the appendix in the final version.\n\n### Response to comments\n\n> the noise model is i.i.d. additive with sub-exponential tails, leaving correlated or heavy-tailed settings unaddressed\n\n\nThank you for raising this point. We agree that extending the framework to handle heavy-tailed and correlated noise is an interesting and important direction for future work. Our paper already makes some progress towards this direction by considering a non-independent noise across dimensions where each point $p$ is i.i.d., appending a noise vector $\\xi_p\\in \\mathbb{R}^d$ whose covariance matrix is $\\Sigma\\in \\mathbb{R}^{d\\times d}$. Note that under the noise model II, $\\Sigma = \\sigma^2\\cdot I_d$ when each coordinate-noise distribution $D_j=N(0,\\sigma^2)$ (Lines 1309-1312).\n\n**Theoretical extension:** As shown in Appendix F.1, we formally extend our analysis to this noise model and achieve a bound for $r_P$.\n\n**Empirical robustness:** Appendix G.3 further includes experiments under non-independent Gaussian noise, demonstrating that our algorithm remains robust in such noisy settings.\n\nWe will add the extension to correlated or heavy-tailed noise models as future directions in the final version."}, {"review_id": "rc19j9JiIo", "reviewer": "Reviewer_u3nx", "summary": "The core challenge addressed in this paper is the construction of coresets for $(k,z)$-clustering in the $d$-dimensional Euclidean space, where input points are perturbed by noise. The authors consider a main noise model where each point remains untouched with some probability, and with the complementary probability each of its coordinates is perturbed by noise drawn from a coordinate-specific centered and unit-variance distribution. They then extend this model to a setting where the distribution is allowed to have larger variance $\\sigma^2$, and to noise models where coordinate noises are no longer independent. This perturbation means the algorithm operates without ever seeing the true, original point set. As a result, the traditional error metric, which gauges how much a coreset solution's cost differs from that of the complete data (for every solution), might not be the most appropriate measure when noise is present. \n\nThis paper’s main results are the following:\n\n- First, they show that, in a noisy setting, the canonical error metric used to evaluate coreset quality falls short of being the right one, as it may significantly overestimate coreset error. They, thus, define a new distribution-independent quality measure that does not suffer from the brittleness of measuring absolute cost deviation.\n\n- The second result of this paper consists of showing that, with respect to the canonical error metric, a coreset of state-of-the-art size suffices to guarantee an error of $\\varepsilon$ plus an additive error polynomial in $\\frac{\\theta nd}{OPT_P}$.\n\n- The third and main result is an analog of the second with respect to the new error metric: It shows that, under a cost-stability assumption, the new metric allows for a (up to $poly(k)$) smaller coreset size, and tighter control on the approximation ratio. \n\nFor the second result, its analysis relies on composition bounds to estimate the clustering cost. This involves controlling the deviation of the clustering cost on the true point set from its estimate, using concentration and Bernstein's moment conditions.\n\nThe third result is substantially more challenging to obtain. For instance, the natural composition that used to hold with respect to the canonical metric, no longer holds here, and a composition to an inflated $(1+\\varepsilon)$ version has to be considered. The analysis of the third result first demonstrates that the designed coreset algorithm has a small error on the perturbed point set. Second, it establishes the error gap between the true point set and its noisy counterpart. The algorithm initially constructs a coreset in a noise-free setting by partitioning points into well-separated clusters with uniform sampling. This method is then extended to noisy environments using geometric properties ensured by cost-stability. Noise-induced challenges, such as increased cluster diameter and weakened closeness guarantees, are addressed through a \"cleaned up\" phase for noisy points. This process results in a negligible effect from removed points and achieves the desired error bound.", "questions": "- Reading the paper, I was wondering whether the mergeability property of coresets would be preserved under the new error metric, and I am glad you present this as a challenge in the last section. Do you have some intuition on which kind of instances mergeability might cease to hold?\n\n- Your noise models are currently defined only for Euclidean space. Have you considered extending this framework to general metric spaces, for example, by allowing point perturbations within a ball of a certain radius, where the radius itself is drawn from a distance distribution?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper presents a well-structured extension of coreset construction for clustering problems, specifically when handling noisy input. The exposition is generally clear. I found the simple example comparing the noise-free and noise-aware metrics particularly effective; it plainly shows why the proposed surrogate measure is appropriate. The additional discussion in the appendix is also insightful, demonstrating that the standard error measure can be brittle even without noise.\n\nWhile the analysis for the second result is more standard, it plays a nice role by providing a benchmark against which the third result—which achieves sharper bounds—can be compared. For this third and main result, a key strength is the development of new techniques for the newly defined error metric, better suited for noisy environments. The \"Key Ideas\" paragraphs in the main body are effective in helping readers build intuition and grasp the problem. Despite its technical depth, the treatment maintains conceptual clarity.\n\nOverall, the contributions and presentation are solid. The paper introduces the noisy coreset construction in $d$-dimensional Euclidean space, illustrating the challenges it poses, and providing nice results on the coreset size for this setting.", "was_revised": true, "final_justification": "Thank you for the response to all of my questions and comments. They explain everything I asked clearly and made me understand even better where the additional challenges in future work lie. I, thus, confirm my score.", "rebuttal": "We thank you for your detailed and encouraging review. We especially appreciate your recognition of our technical contributions. Below we provide detailed responses to your questions.\n\n### Questions\n\n> Reading the paper, I was wondering whether the mergeability property of coresets would be preserved under the new error metric, and I am glad you present this as a challenge in the last section. Do you have some intuition on which kind of instances mergeability might cease to hold?\n\nThank you for this valuable question. In the ideal case, mergeability means that if two coresets $S_1, S_2$ for disjoint datasets $P_1, P_2$ each satisfy $\\mathrm{Err}\\_\\alpha(S_\\ell, P_\\ell) \\leq \\varepsilon$, then their union also satisfies  \n$$\n\\mathrm{Err}\\_\\alpha(S_1 \\cup S_2,\\; P_1 \\cup P_2) \\leq \\varepsilon.\n$$\nWith our new metric $\\mathrm{Err}\\_\\alpha$, this guarantee can fail—particularly when $S_1$ and $S_2$ summarize datasets with significantly different cluster structures. In such cases, the optimal center set for $S_1 \\cup S_2$ may differ substantially from the union of the individual optima, and the combined coreset may not encode enough information to capture this emergent structure.\n\n\n**When does mergeability still hold?**\n\nMergeability remains plausible when the two coresets are *structurally similar*. Let us define  \n$$\\mathcal{C}\\_{\\beta}(Q) =\\\\{C : \\mathrm{cost}(Q, C) \\leq \\beta \\cdot \\mathrm{OPT}\\_Q \\\\}.$$\nIf there exists $1 \\leq \\alpha' \\leq \\alpha$ such that  \n$$\n\\mathcal{C}\\_{\\alpha'}(S_1) \\subseteq \\mathcal{C}\\_\\alpha(S_2)\n\\quad \\text{and} \\quad\n\\mathcal{C}\\_{\\alpha'}(S_2) \\subseteq \\mathcal{C}\\_\\alpha(S_1),\n$$\nthen $S_1$ and $S_2$ approximately share the same set of near-optimal solutions. This overlap enables a *weaker* form of mergeability under $ \\mathrm{Err}\\_\\alpha$.\n\n**Claim (Weak mergeability under $\\mathrm{Err}\\_\\alpha$):**  \nSuppose $\\mathrm{Err}\\_\\alpha(S_\\ell, P_\\ell) \\leq \\varepsilon$ for $\\ell = 1,2$, and the overlap condition above holds. Define:\n$$\n\\kappa = \\frac{\\min\\\\{ \\mathrm{OPT}\\_{S_1}, \\mathrm{OPT}\\_{S_2} \\\\}}{\\mathrm{OPT}\\_{S_1 \\cup S_2}}, \\quad\n\\tau = \\max\\\\{\n\\frac{\\mathrm{OPT}\\_{S_1}/\\mathrm{OPT}\\_{P_1}}{\\mathrm{OPT}\\_{S_2}/\\mathrm{OPT}\\_{P_2}},\n\\frac{\\mathrm{OPT}\\_{S_2}/\\mathrm{OPT}\\_{P_2}}{\\mathrm{OPT}\\_{S_1}/\\mathrm{OPT}\\_{P_1}}\n\\\\}.\n$$\nThen:\n$$\n\\mathrm{Err}_{1 + (\\alpha - 1)\\kappa}(S_1 \\cup S_2,\\; P_1 \\cup P_2)\n< \\alpha' \\cdot \\tau \\cdot (1 + \\varepsilon) - 1.\n$$\n\nIn the limiting case where $\\alpha', \\alpha \\to 1$ and $\\tau \\to 1$, this bound recovers the ideal mergeability condition:  \n$$\n\\mathrm{Err}_\\alpha(S_1 \\cup S_2,\\; P_1 \\cup P_2) \\leq \\varepsilon.\n$$\n\nWe will include this intuition, the formal claim, and a sketch of the proof in the appendix of the final version.\n\n\n\n> Your noise models are currently defined only for Euclidean space. Have you considered extending this framework to general metric spaces, for example, by allowing point perturbations within a ball of a certain radius, where the radius itself is drawn from a distance distribution?\n\nThank you for this insightful question. Extending our framework to general metric spaces is a fascinating direction. As you note, directly perturbing points is often ill-defined in a general metric space $M = (\\mathcal{X}, \\mathrm{dist})$ due to the absence of a coordinate system. A more natural alternative is to introduce noise at the level of the distance function itself.\n\nWe outline a potential model below.\n\nLet $\\theta \\in [0,1]$ be a noise parameter, and let $D$ be a distribution on $\\mathbb{R}$ with mean 0 and variance 1. For each pair $(x, y) \\in \\mathcal{X} \\times \\mathcal{X}$, define the noisy pairwise distance $\\widehat{\\mathrm{dist}}(x, y)$ as follows:\n\n- With probability $\\theta$, set  \n  $$\n  \\widehat{\\mathrm{dist}}(x, y) = \\mathrm{dist}(x, y) + \\xi_{(x,y)},\n  $$  \n  where $\\xi_{(x,y)} \\sim D$ i.i.d.;\n- With probability $1 - \\theta$, set  \n  $$\n  \\widehat{\\mathrm{dist}}(x, y) = \\mathrm{dist}(x, y).\n  $$\n\nThis model reflects additive noise in pairwise distances, analogous to our perturbation model in Euclidean settings.\n\nHowever, a significant challenge arises: the perturbed function $\\widehat{\\mathrm{dist}}$ may no longer satisfy the triangle inequality, and thus may not define a valid metric. This opens up a rich and challenging extension—coreset construction for *noisy semimetric spaces*.\n\nAnalyzing how our framework and theoretical guarantees extend under this relaxed setting (e.g., when only approximate triangle inequalities hold) is a non-trivial but important direction for future work.\n\nIn the final version, we will add a section to the appendix discussing this potential generalization, including the proposed distance-noise model and the resulting difficulties. We will also list this as a key open direction in the conclusion."}, {"review_id": "DOyjA7qdy9", "reviewer": "Reviewer_bg4J", "summary": "Clustering is a fundamental machine learning task. For large datasets, coresets -- small, weighted subsets -- are used to approximate the clustering cost while reducing computational requirements. However, most coreset constructions assume noise-free data, which is rarely the case in practice. The paper addresses the construction of coresets for (k, z)-clustering (which includes k-means and k-median) when the observed dataset is corrupted by stochastic (random, additive) noise with a known distribution -- a common scenario in privacy, sensor data, and robustness applications.\n\nThe paper analyzes the traditional surrogate error metric (Err), used to measure coreset quality in noise-free settings, and demonstrates that it may significantly overestimate error when data is noisy due to uniform cost inflation. Next, the authors introduce a new approximation-ratio-based metric, which more closely aligns with the true (unobservable) clustering quality under noise. Then, they show under certain assumptions on the dataset, under certain noisy models, their proposed sampling procedure produces a smaller -- by poly(k) factor -- coreset. The authors complement their theoretical results with empirical evaluations.", "questions": "Could you please comment on whether the additve factors on Err and r_P in Theorem 3.1 are unavoidable or not? Are those additive terms optimal? Are there any natural interpretations of those terms or do they appear solely because of technical reasons?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Coreset construction in the presence of noise is highly relevant for practical machine learning yet underexplored. This paper fills an important gap. The theoretical guarantees under the two natural noise models provided in this paper are quite interesting. However, relying on certain assumptions about the dataset makes the results slightly weak, especially since such an assumption is necessary. Further, I am not sure whether the additive terms in Err and r_P (in Theorem 3.1) are unavoidable or not. Overall, I think this paper shows some nice, interesting results on coreset constructions for noisy datasets.", "was_revised": true, "final_justification": "I thank the authors for their explanation. I did not have any major concern, and I am positive about this paper; thus, I am keeping the score as it is", "rebuttal": "We thank you for your encouraging review. We sincerely appreciate your recognition of the novelty and contribution of our work. We address your question below.\n\n>Could you please comment on whether the additive factors on Err and r_P in Theorem 3.1 are unavoidable or not? Are those additive terms optimal? Are there any natural interpretations of those terms or do they appear solely because of technical reasons?\n\n\nThank you for the insightful question, which motivates us to strengthen our technical contributions. The two additive factors on $\\mathrm{Err}$ and $r_P$ in Theorem 3.1 have different natures: $O\\left(\\frac{\\theta n d}{\\mathsf{OPT}_P}\\right)$ is an unavoidable consequence of the problem setting, while $O\\left(\\sqrt{\\frac{\\theta n d}{\\mathsf{OPT}_P}}\\right)$ is an artifact of our proof technique.\n\n**The unavoidable term: $O\\left(\\frac{\\theta n d}{\\mathsf{OPT}_P}\\right)$.**\nThis term is worst-case optimal and thus unavoidable.\n\n* **Natural interpretation:** Intuitively, this term arises from the inherent \"cost\" of the data perturbation. Each of the $\\theta n$ perturbed points is expected to move by $\\|\\xi_p\\|^2 = d$. This creates a minimum total displacement cost of $\\Omega(\\theta n d)$ that must be paid. When viewed as a relative error against the original clustering cost $\\mathsf{OPT}_P$, this naturally induces the additive error term $\\frac{\\theta n d}{\\mathsf{OPT}_P}$.\n\n* **Worst-case example justification:** We formalize this intuition with a worst-case example. Let $\\theta = 0.1$, $n = 10000$ and $k = n-1$. Let $P =\\\\{p_i = 100 n e_i: i\\in [n\\\\} \\subset \\mathbb{R}^n$ where $e_i$ is the $i$-th unit basis in $\\mathbb{R}^n$. An optimal solution $\\mathsf{C}(P) = \\\\{p_1,\\ldots, p_{n-2}, \\frac{p_{n-1} + p_{n}}{2}\\\\}$, and hence, $\\mathsf{OPT}\\_P = 10000n^2$. Note that with probability at least 0.8, the following events hold: $\\sum_{p\\in P} \\|\\xi\\_p\\|\\_2^2 = \\Theta(\\theta n d)$ and for every $p\\in P$, $\\|\\xi\\_p\\|\\_2^2 \\leq 10d \\log n$. Conditioned on these events, the optimal solution $\\mathsf{C}(\\widehat{P})$ of $\\widehat{P}$ must consist of $n-2$ points $\\widehat{p}\\in \\widehat{P}$ and the average of the remaining two points in $\\widehat{P}$. W.l.o.g., assume $\\mathsf{C}(\\widehat{P}) = \\\\{\\widehat{p}\\_1,\\ldots, \\widehat{p}\\_{n-2}, \\frac{\\widehat{p}\\_{n-1} + \\widehat{p}\\_{n}}{2}\\\\}$. Then we have\n$\n\\mathrm{cost}(P,\\mathsf{C}(\\widehat{P})) \\geq(1 + \\Omega(\\frac{\\theta n d}{\\mathsf{OPT}})),\n$\nimplying that $\\mathsf{Err}(\\widehat{P},P) = \\Omega(\\frac{\\theta n d}{\\mathsf{OPT}_P})$.\n\n\n**The technical term: $O\\left(\\sqrt{\\frac{\\theta n d}{\\mathsf{OPT}_P}}\\right)$.**\nThis term arises from a technical step in our proof, and it's unclear if it is optimal. This term is used to bound the supremum of the total error contributed from all points over all center sets $C$. The error induced by moving a single point $p$ w.r.t. a $C$ can be bounded by $d^2(p+\\xi_p,C)-d^2(p,C) \\in \\pm\\|\\xi_p\\|_2\\cdot d(p,C)$. Summing these bounds across all points leads to the term \n$$\\sum_p \\|\\xi_p\\|_2\\cdot d(p,C)\\leq\\sqrt{(\\sum \\|\\xi_p\\|_2^2) \\cdot (\\sum d^2(p,C))} \\le \\sqrt{\\theta nd \\cdot \\mathsf{OPT}_P}.$$\n\nHowever, this analysis assumes the worst-case scenario where all individual errors $d^2(p+\\xi_p,C)-d^2(p,C)$ compound. It's possible that these errors (which can be positive or negative) partially cancel each other out for every $C$. A more refined analysis that avoids this loose bounding step might eliminate or reduce term $O\\left(\\sqrt{\\frac{\\theta n d}{\\mathsf{OPT}_P}}\\right)$.\n\nWe will add this entire discussion to the appendix of the final version to give readers a clearer interpretation of the bounds in Theorem 3.1."}, {"review_id": "KzPGiagZNC", "reviewer": "Reviewer_RYsn", "summary": "The paper studies coresets for k-means clustering when the input dataset is corrupted by random noise. Specifically, the paper models noise by random perturbation of each data point. It then presents a a surrogate error metric, which is basically an upper bound on the error of the coreset but relative to the unperturbed dataset. The main result is then 2 algorithms for constructing a coreset from the perturbed dataset. The crux is that the algorithm's accuracy/quality is measured wrt the unperturbed points, even though the algorithm cannot see them. The algorithms are analyzed theoretically, showing smaller coreset size, and they are validated via a few experiments.", "questions": "none", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I like the paper's research direction of studying noisy data instead of worst-case data. As a side comment, such models where the input is a combination of adversarial + random choices, are called semi-random inputs or smoothed analysis in related literature:\nDavid Arthur, Bodo Manthey, Heiko Röglin: Smoothed Analysis of the k-Means Method. J. ACM 58(5): 19:1-19:31 (2011)\nJonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian: Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting. NeurIPS 2024\n\nHowever, I find the paper's methodology is unconvincing. First, the main error measure $Err(S,P)$ is only an upper bound on the error (the paper calls it a surrogate), and I doubt it is the correct measure that we would like to minimize. Second, the two algorithms do not bring new insights or methods to the area, in fact the first one (theorem 3.1) simply says to apply any known coreset algorithm, and thus has no new component (the contribution is analysis of the error wrt the unperturbed dataset). The second algorithm (for theorem 3.3) is follows a rather standard recipe, basically computing an O(1)-approximate clustering and sampling from each cluster a carefully chosen number of points. I don't see how or why these algorithms are tailored for a perturbation model. Overall, I don't see a significant technical novelty in the algorithms, and the analysis might be involved but seems (from its overview) to use standard tools.\n\nSimilarly, the experiments do not convince me, primary because I am not fond of the error measure $Err(S,P)$, but also because they do  not evaluate the quality of the coreset directly, i.e., solving the clustering problem directly for the input $P$ vs solving for the coreset $S$ and using this center set. \n\nI have also many comments about specific issues in the paper, but they are minor. For example, line 217 demonstrates the applicability but works for a rather small $\\epsilon=1/poly(k)$ and large stability parameter $\\gamma$.  In addition, theorems 3.1 and 3.3 should probably include WHP somewhere in the statement. In addition, the $r_P$ measure makes a lot of sense for worst-case inputs, so why use them here also in the noisy setting? Finally, the bounds in the two theorems involve many terms and the big picture is lost. Finally, it seems that you use k-means++ experimentally both for the initial O(1)-approximate solution and as a heuristic for finding the optimal solution (because it's NP-hard), which might cause inconsistency in the experimental results (the algorithm \"starts\" at the optimal solution).", "was_revised": true, "final_justification": "I raised my score based on the rebuttal and other reviews, which helped me understand better the goal and contribution of this work.", "rebuttal": "We thank the reviewer for taking the time to evaluate our submission and for the opportunity to clarify key aspects of our work. Below we address your comments.\n\n\n>...semi-random inputs or smoothed analysis in related literature...\n\n\nThank you for pointing us to the literature on semi-random (or smoothed-analysis) models. As you note, these frameworks also consider data formed by adding random perturbations to a clean dataset $\\widehat{P} \\leftarrow P + \\text{noise}$.\n\n**Similarity:**  \nOur setting shares this structural model: $\\widehat{P}$ is formed by applying i.i.d. additive noise to $P$. For example, [Arthur et al., 2011] use Gaussian perturbations for $k$-means, and [Kelner et al., 2024] apply entrywise noise in matrix completion—both analogous to our sub-exponential model.\n\n**Difference:**  \nThe *goal* is different. Smoothed analysis asks: *Can a standard algorithm efficiently solve the problem on $\\widehat{P}$?* For instance, [Arthur et al., 2011] show $k$-means converges quickly *on the noisy data*.\n\nIn contrast, we aim to construct a coreset $S$ from $\\widehat{P}$ that approximates the clustering cost on the *unobserved* dataset $P$. Here, noise is the main challenge—not a tool for tractability. In this sense, our goal aligns more with [Kelner et al., 2024], who also seek to recover latent structure from noisy observations.\n\nWe will clarify this distinction in the related work section.\n\n\n>the main error measure $Err(S,P)$ is only an upper bound on the error (the paper calls it a surrogate), and I doubt it is the correct measure that we would like to minimize\n\nThe main measure we use is $\\mathsf{Err}_\\alpha(S, P)$, not $\\mathsf{Err}(S, P)$. The latter—widely used in the noise-free setting (e.g., [20, 21, 23, 35, 54])—is used in Theorem 3.1 to extend existing coreset guarantees to the noisy setting.  \n\nOur primary contribution is Theorem 3.3, which introduces a new algorithm and relies on the new error metric $\\mathsf{Err}_\\alpha(S, P)$.\n\n>the $r_P$ measure makes a lot of sense for worst-case inputs, so why use them here also in the noisy setting?\n\nBecause we still aim to construct a coreset for the original dataset $P$, even though we only observe $\\widehat{P}$. Thus, bounding $r_P$ remains the goal.\n\n\n>...I don't see a significant technical novelty in the algorithms, and the analysis...use standard tools\n\nThank you for this opportunity to clarify the technical contributions of both our analysis and algorithm.\n\n**Novelty in Theorem 3.1**\n\nTheorem 3.1 does not propose a new algorithm, but it makes a novel analytical contribution: it quantifies the quality of a coreset $S$ (constructed from noisy data $\\widehat{P}$) with respect to the true dataset $P$, using the traditional error measure $\\mathsf{Err}(S, P)$. This analysis reveals that $\\mathsf{Err}(S, P)$ can be an overly conservative estimate of the true quality—especially when noise uniformly inflates the clustering cost (see Lines 184–186 and Section B.3). \n\nTo our knowledge, this is the **first result to study how coreset performance degrades under noise**. It also motivates our introduction of the new metric $\\mathsf{Err}_\\alpha(S, P)$, which we analyze in Theorem 3.3 and show to be a tighter surrogate for the ideal measure $r_P$.\n\n**Novelty in Theorem 3.3 and Algorithm 1**\n\nIn contrast to Theorem 3.1, Theorem 3.3 **introduces a new coreset construction algorithm** (Algorithm 1) specifically designed to be robust to additive noise. It also provides a sharper error guarantee for $r_P$, using our new metric $\\mathsf{Err}_\\alpha(S, P)$ under mild assumptions (Assumption 3.2). As discussed in Lines 216–226, this algorithm achieves up to a $\\text{poly}(k)$ improvement in coreset size over noise-agnostic baselines.\n\n*Algorithmic Novelty*\n\nAlgorithm 1 consists of the following steps:\n\n1. Partition $\\widehat{P}$ into $k$ clusters $\\widehat{P}_i$ using an $O(1)$-approximate center set $\\widehat{C}$ (Line 1).\n2. Construct a ball $B_i$ around each cluster with a carefully chosen radius $\\widehat{r}_i$ (Lines 2–3).\n3. Uniformly sample from $P_i'=\\widehat{P}_i\\cap B_i$ (Lines 4–5), and return the union of samples.\n\nThe key novelty lies in **Step 2**, which does **not** appear in prior noise-free coreset methods. Existing approaches sample directly from $\\widehat{P}_i$, which works in the absence of noise but fails to account for **assignment drift** caused by high-noise points. These noisy points can mislead clustering structure and distort center locations.\n\nBy constructing and sampling from $B_i$, our method explicitly **excludes high-noise points** and focuses the coreset on points whose assignments are reliable. This noise-aware sampling step is critical to preserving geometric stability. An example in Appendix E.1 illustrates the significance of assignment shifts in noisy settings. Lines 250–265 provide further analysis of this step.\n\n\n\n\n*Analytical Novelty*\n\nOur analysis introduces several new components:\n\n- **Step 1**: We prove that every $C\\in\\mathcal{C}_\\alpha(S)$ contains a center in each $B_i$ (Lemma D.3), establishing consistent cluster structure through stability.\n\n- **Step 2**: We bound the deviation between centers of $P_i'$ and its sample $S_i$  (Lemma D.4).\n\n- **Step 3**: Crucially, we bound the shift between centers $\\mu(P_i')$ and $\\mu(P_i)$: separating the effects of internal noise and the excluded high-noise points (Lemma D.5). This step is **novel**, and essential to achieve a tighter bound for the coreset quality $r_P$ compared to $\\mathsf{Err}$.\n\n- **Step 4**: We conclude via a standard composition argument, bounding $\\mathsf{Err}_\\alpha(S, P)$ in Theorem 3.3.\n\nThis is, to our knowledge, the **first analysis to disentangle** the impact of noise on clustering cost (scaling as $\\theta nd/ \\mathrm{OPT}_P$) from its effect on the **location of optimal centers** (scaling as $\\theta d/\\mathrm{OPT}_P$) (Lines 266–279).\n\nWe will reflect these clarifications in the final version.\n\n> ... rather small $\\varepsilon = 1/\\mathrm{poly}(k)$ and large stability parameter $\\gamma$\n\nThank you for raising this point. While Theorem 3.3 depends on the cost-stability parameter $\\gamma$, the result applies for any $\\varepsilon \\in (0,1)$. To illustrate:\n\n- Let $\\alpha = 1 + \\varepsilon$ and $\\theta = \\frac{\\mathrm{OPT}_P}{n d \\cdot \\mathrm{poly}(k)}$.\n- Then Theorem 3.3 yields a coreset size $\\widetilde{O}(k/\\varepsilon)$, improving over $\\widetilde{O}(\\min\\{k^{1.5}/\\varepsilon^2, k/\\varepsilon^4\\})$ by a factor of $\\sqrt{k}/\\varepsilon$ (with a similar analysis as in Lines 221–222).\n- The error bound also improves over Theorem 3.1 by a $\\mathrm{poly}(k)$ factor when $n \\gg \\mathrm{poly}(k)$ (with a similar analysis as in Lines 223–226).\n\nWe will include this example in the final version.\n\n>the bounds in the two theorems involve many terms and the big picture is lost \n\nThanks for pointing this out-each term in the bounds of Theorem 3.1 and 3.3 plays a distinct role. Below we clarify it for (the harder case of) Theorem 3.3. In the final version, we will explain the importance of each term in these theorems. \n\n- $O(\\frac{\\theta kd}{\\mathsf{OPT}_P})$: captures center drift due to noise. Intuitively, each center $c$ in the optimal center set $\\mathsf{C}(P)$ shifts a distance of $\\theta d$ due to noise. Thus, the total movement distance from $\\mathsf{C}(P)$ to $\\mathsf{C}(\\widehat{P})$ is bounded by $\\theta k d$. This implies that $\\mathsf{C}(\\widehat{P})$ is a $(1+\\frac{\\theta k d}{\\mathsf{OPT}_P})$-approximate center set on $P$, introducing the term $\\frac{\\theta k d}{\\mathsf{OPT}_P}$.\n\n- $O(\\frac{\\sqrt{\\alpha-1}}{\\alpha}\\cdot \\frac{\\sqrt{\\theta k d \\text{OPT}_P}+\\theta n d}{\\text{OPT}_P})$: accounts for using $\\alpha$-approximate centers. This term controls the additional error brought by $\\alpha$-approximate center set instead of the optimal one.\n\nThe role of each term in Theorem 3.1 can also be found in our response to Reviewer bg4J (link: https://openreview.net/forum?id=ycCi4SkzPH&noteId=dWrAWSnvVv).\n\n>the experiments...do not evaluate the quality of the coreset directly\n\nWe believe this is a misunderstanding. The metric $\\widetilde{r}_S$ (Line 293) does exactly what you suggest.\n\n- Recall that \n  $$\n  \\widetilde{r}_S := \\frac{\\mathrm{cost}(P, C_S)}{\\mathrm{cost}(P, C_P)},\n  $$\n  where $C_S$ is the center set obtained by running $k$-means++ on the coreset $S$, and $C_P$ is the center set obtained by running $k$-means++ on the full dataset $P$.\n\n- The **denominator**, $\\mathrm{cost}(P, C_P)$, corresponds to solving the clustering problem directly on the input $P$.\n\n- The **numerator**, $\\mathrm{cost}(P, C_S)$, corresponds to solving the problem on the coreset $S$ and then evaluating the resulting solution on $P$—i.e., using the coreset to approximate clustering on the original data.\n\nThus, $\\widetilde{r}_S$ measures how well the coreset solution approximates the true clustering cost on $P$, precisely as you suggested.\n\n\nWe will clarify this interpretation of $\\widetilde{r}_S$ in the final version. \n\n>k-means++...might cause inconsistency in the experimental results\n\nThank you—this was due to a missing detail. Here is how $k$-means++ is used in two distinct roles:\n\n- **For initialization on $\\widehat{P}$:**  \n  We run $k$-means++ with 'max$\\\\_$iter = 5` for a fast $O(1)$-approximate solution (runtime: 0.128s on $\\tt{Census1990}$).\n\n- **For evaluation on $S$:**  \n  We run $k$-means++ 10 times (default settings, varied seeds) on $S$ and select the best solution (runtime: 0.181s on $\\tt{Census1990}$).\n\nWe will clarify this setup in the final version.\n\n\n>theorems 3.1 and 3.3 should probably include WHP \n\n\nThanks, yes, we will fix this. \n\nWe thank you again for your time, and hope our responses convey the novelty and applicability of our work."}]

Author rebuttal:

Meta-review: This paper introduces a new error notion for coreset construction under noise, supported by careful theoretical analysis and strong empirical validation. Reviewers appreciated the conceptual clarity, practical motivation, and technically sound proofs, as well as the fact that the method is simple to implement and reproduces best-known guarantees while adapting to noisy settings. 
The paper is also well-presented, with clear examples, intuitive explanations, and experiments across multiple datasets and noise models.
While some reviewers noted limitations in the assumptions (e.g., stability, noise model) and raised questions about the surrogate error measure, these concerns were largely addressed by the rebuttal, which clarified trade-offs and provided convincing justifications.
Overall, the consensus is that this work makes a meaningful and timely contribution to the clustering/coreset literature, addressing a practically important but underexplored problem.
Decision: Accept (poster)