Stable coresets: Unleashing the power of uniform sampling
Authors: Amir Carmel
Robert Krauthgamer
Venue: ICLR 2026 Poster (2026)
Keywords: clustering
$k$-median
coresets
uniform sampling
$\ell_1$ metric
Primary area: learning theory
TL;DR: We formulate "stable coresets", an intermediate definition between strong and weak coresets that provides strong theoretical guarantees while remaining compatible with uniform sampling, and demonstrating our approach on the median problem.

Abstract: Uniform sampling is a highly efficient method for data summarization.
However, its effectiveness in producing coresets for clustering problems
is not yet well understood,
primarily because it generally does not yield a strong coreset,
which is the prevailing notion in the literature. 
We formulate \emph{stable coresets}, a notion that 
is intermediate between the standard notions of weak and strong coresets,
and effectively combines the broad applicability of strong coresets
with highly efficient constructions, through uniform sampling, of weak coresets.
Our main result is that a uniform sample of size $O(\epsilon^{-2}\log d)$
yields, with high constant probability,
a stable coreset for $1$-median in $\mathbb{R}^d$ under the $\ell_1$ metric.
We then leverage the powerful properties of stable coresets 
to easily derive new coreset constructions, all through uniform sampling, 
for $\ell_1$ and related metrics, such as Kendall-tau and Jaccard. 
We also show applications to fair rank aggregation and to approximation algorithms
for $k$-median problem in these metric spaces.
Our experiments validate the benefits of stable coresets in practice,
in terms of both construction time and approximation quality.

Published as a conference paper at ICLR 2026
STABLE CORESETS:
UNLEASHING THE POWER OF
UNIFORM SAMPLING
Amir Carmel
Robert Krauthgamer!
Weizmann Institute of Science ami r r44336 gma i com
Weizmann Institute of Science robert. robert.k www.kkatttggeerreeeee... zmann, ac. i
ABSTRACT
Uniform sampling is highly efficient method for data summarization. However, its effectiveness in producing coresets for clustering problems is not yet well understood, primarily because it generally does not yield strong coreset, which is the prevailing notion in the literature. We formulate stable coresets, notion that is intermediate between the standard notions weak and strong coresets, and effectively combines the broad applicability of strong coresets with highly efficient constructions, through uniform sampling, of weak coresets. Our main result is that uniform sample of size O log d) yields, with high constant probability, a stable coreset for 1-median in Id under the & metric. We then leverage the powerful properties of stable coresets to easily derive new coreset constructions, all through uniform sampling. for & and related metrics, such as Kendall-tan and Jaccard. We also show applications to fair rank aggregation and to approximation algorithms for k-median problem in these metric spaces. Our experiments validate the benefits of stable coresets practice, in terms both construction time and approximation quality.
INTRODUCTION
Clustering is a fundamental problem in data analysis, machine learning, and optimization, facilitating various downstream tasks such classification, anomaly detection, and efficient retrieval. In general, the input is a set of points in a metric space, and the objective is to partition this set into disjoint clusters, each sharing high degree of similarity. In center-based clustering, the goal is further assign a representative point, called center, to each cluster. The famous k-median problem, where the number of clusters is denoted by k seeks minimize the sum of distances from each input point to its assigned center.
In the era of big data, clustering often involves huge datasets, where direct processing is computation- ally prohibitive. This challenge has given rise to the sketch-and-son summarization step prior to the desired computational task, i.e., the data is first preprocessed into a compact summary, ideally of size that is independent of the original dataset size, and then the desired algorithms for learning or optimization are applied only to this smaller summary. This approach significantly reduces computational resources, such running time, memory, and communication. but requires balancing between the summary's size and its information loss.
paradigm, which employs
A coreset represents concrete formalization of data summarization, and is typically defined as a small subset of the input that provably captures the relevant geometric properties for a specific objective function. Over the past decades, coresets have been extensively studied and successfully applied to a wide range of problems (see the surveys (Feldman, 2020; Phillips, 2017) and references therein), and two fundamental types of coresets have dominated the literature. weak coreset, which aligns with the aketch-and-solve paradigm, ensures that an optimal or near-optimal solution computed for the coreset is near-optimal also for the original dataset, without necessarily preserving the objective value itself. In contrast, strong coresel provides a more comprehensive guarantee by
Part of this work was completed while the author was affiliated with Pennsylvania State University. TThe Harry Weinrebe Professorial Chair of Computer Science. Work partially supported by the Israel Science Foundation grant #1 #1336/23.

---

Published as a conference paper at ICLR 2026
preserving the objective value, up small error, for all potential solutions, i.e., all centers in the metric space. This notion is indeed stronger and has broader range of applications, In particular, exhibits a powerful property: if a metric space X' admits strong coreset (meaning that every instance in A' admits a small coreset), then every submetric X" C X also admits a strong coreset. It follows that coreset results for one metric space X' extend to every metric that can be embedded isometrically in X. A concrete example here is the Kendall-tau metric on rankings, which embeds into 41.
This property regarding submetrics is very useful also when the optimal solution is constrained to meet specific criteria. One such example is the problem of fair rank consensus, which asks to aggregate multiple rankings into a single ranking. viewed as a center point, that satisfies certain fairness constraints among the candidates being ranked (Chakraborty et al., 2022; Patro et al., 2022; Pitoura et al., 2022). Another example emerges in biological research, where molecular data needs to be aggregated while satisfying structural properties that are critical for maintaining molecular stability (Tian et al., 2021; Zeng et al., 2023). Furthermore, constraints can be modified over time, e.g., to reflect knowledge or demands, effectively restricting the center points each time to a different submetric.
However, the advantages of strong coresets come with nontrivial computational challenges, their construction algorithms must inevitably read the entire dataset.' Can we construct corescts in sublinear time? Weak coresets demonstrate that this is possible, they can sometimes be constructed through uniform sampling (Huang et al., 2023a;b; Marom & Feldman, 2019), a highly efficient method that is easy implement in streaming and distributed settings, and is well-known to be extremely useful in practice. However, uniform sampling cannot reliably capture small clusters, which motivates to study the fundamental case k 1, where uniform sampling can succeed without additional assumptions about the dataset. This case arises naturally in many practical scenarios and serves as an important building block for the general problem.
We formulate stable coresets, notion that captures key properties of strong coresets while avoiding many of their computational pitfalls. More precisely, they are intermediate between strong and weak coresets, and effectively provide sweet spot between these two standard notions. We investigate stable coresets within the framework of the 1-median problem under the & metric. This metric emerges naturally in data analysis, particularly in high-dimensional settings, and also serves unifying framework for understanding numerous distance metrics. Indeed, many important metrics- including Hamming, Kendall-tar Jaccard, tree metries, various graph-based distances, as well as fz-can be embedded into Rd with the & metric either isometricalyy or with low distortion. Yet another application is in computational biology, where the genome median problem seeks to find a consensus genome that minimizes evolutionary distance to a set of input genomes, often using metrics that embed in & space. The upshot is that results for stable coresets in L immediately imply new coreset constructions also for these embedded metrics, in contrast to weak coresets, which would require a separate analysis for each individual metric.
1.1 PROBLEM SETUP AND DEFINITIONS
In k-median, the input is a finite set of points P in the metric space (X, dist) and the goal is to find a set of k centers C C X that minimizes the objective function
cost P) = Σ
min dist(c, p).
eEC
PEP
We focus on the case = 1. For this single-center case, we denote an arbitrary optimal center (which minimizes the objective) by cP X, and the optimal value by opt (P) cost(c., P).
We proceed to define formally the three coreset variants discussed above.? ? a weak coreset, the main idea is that solving the coreset instance optimally, or even approximately, yields an approximately optimal solution also for the original instance. Our definition below uses parameters and 1) to create
'Consider & = 1 and dataset where all points are densely clustered, except for one "outlier" point extremely far away. While this outlier hardly affects the optimal center, its impact on the objective value might be significant, and thus it must examined and even included every strong coreset.
2 Although coresets are traditionally defined weighted subsets, we present our definitions without weights for sake of clarity, as our focus is on coresets obtained through uniform sampling.
2

---

Published as a conference paper at ICLR 2026
tunable tradeoff in the approximation guarantee, although most literature restricts attention to single parameter by setting rj = O(c) or alternativey c = O.
Definition 1.1 (Weak Coreset). A subset Q S P is weak (c, coorese for 1-median instance P if
Vc E X,
cost(c, Q) & (1 opt(() + cost(c, P) & (1 + 7) opt.
(I)
strong coreset provides more comprehensive guarantee by ensuring that the objective value is preserved for every possible center point in the metric space.
Definition 1.2 (Strong Coreset). A subset Q C P is a strong e-coresel for 1-median instance P if
Vc E X, cost(c, Q) E (1 [1=c e) cost(c, P).
(2)
stable coreset imposes geometric constraints on all points the metric space, similarly to a strong coreset, but with comparative structure like that of weak coreset.
Definition 1.3 (Stable Coreset). A subset Q S P is stable (e, correser for a 1-median instance Xf
V2 E
cost(c1, Q) (1 c) cost(c2, Q) cost P) S (1 + 17) cost(c2, P). (3)
A key difference between strong and stable coresets is that the former preserve the actual cost of every center, while the latter preserve only the relative order of the costs across different centers. For illustration, consider a dataset whose points are clustered together except for one distant "outlier". A strong coreset must include this outlier to preserve its large contributions to the cost, while stable coreset need not. This weaker requirement is crucial for uniform sampling to work effectively, and reveals a natural compatibility between stable coresets and uniform sampling.
While not formalized as coreset notion, the principle underlying (3) and its compatibility with uniform sampling were first used by Indyk (1999; 2001), to compare the costs of two centers in the context of 1-median with discrete centers (i.e., the center must be one of the dataset points). For finite X, Indyk's analysis would yield a stable (0, ec-oreset of size O -2 l"log (X)) (details in Appendix A.1).
We establish some basic properties of these definitions Section 2. In particular, there a strict hierarchy: every strong coreset is also stable coreset, and every stable coreset is also weak coreset, however the opposite direction is not true in general. In addition, the guarantees of a stable coreset transfer every submetric, and thus also to any isometrically embedded metric, which is valuable for analyzing discrete metric spaces that embed into E
1.2 OUR CONTRIBUTION
While uniform sampling offers extensive practical advantages, is often viewed as a heuristic method for constructing coresets, due to limited theoretical foundations. We focus the case A = 1, as requires additional structural and algorithmic assumptions that we avoided for theoretical clarity. Our main theorem shows that uniform sampling yields stable coresets in rather broad setting, namely, in & and thus also in every metric that embeds into l1. Our proof has two parts: first develop framework for constructing stable coresets that is applicable to all metric spaces (in Section 3), and then we instantiate this framework with E fs-spcicfic analysis (in Section 4). Theorem 1.4. Let Idd be finite and let e (0, } Then, uniform sample of size O log d) from is a stable (c/6, 46) 4co-ceee for 1-median in Ef with probability at least 4/5.
extending
Prior work on coresets constructed through uniform sampling works restricted settings. weak (0, c)-coeettt in l is known from (Danos, 2021), however using it would require solving the problem optimally on the coreset. A weak (e, ((e))(((cesse))) in &a is known from (Huang et al., 2023a), however it offers much less generality than ε (recall 62 embeds in & with small distortion but not in the opposite direction). There are also weak coresets in doubling metrics (Ackermann et al., 2010; Munteanu & Schwiegelshohn, 2018; Huang et al., 2023a), which include & and &g spaces, however they are useful only when X' is fow-dimensional. Most importantly, these are all weak coresets and need not extend to submetrics. more comprehensive list of previous results appears in Section 1.4.
3

---

Published as a conference paper at ICLR 2026
Additionally, approach bridges important gap- stable coresets provide almost powerful guarantees as strong coresets, while maintaining the simplicity and efficiency of uniform sampling. It therefore establishes rigorously the broad range of applicability of uniform sampling. We further conjecture that our bound can be improved to be ddmeeniio-inndeeenden,, and our empirical evidence supports this direction.
By utilizing Theorem 1.4 we can establish additional significant results (Section 5). First, we explore implications metric spaces that embed into &, either isometrically or with small distortion, obtaining the first coresets based on uniform sampling for important metric spaces, including Kendall- tau and Jaccard, as well as new bounds for fz. Second, building upon our coreset constructions for 1-median, we derive approximation algorithms for the more general problem of k-median, across all the aforementioned metric spaces. Furthermore, we apply our framework to show that in certain scenarios, uniform sampling actually produces strong coresets, which in turn can speed up approxiaaati algorithms.
Finally, we validate experimentally the performance of our approach in different settings and for various datasets (Section 6). For instance, we show that a uniform sample achieves error rates that are comparable to computationally expensive importance sampling techniques. We also show that when applied to 1-median in the Kendall-tau metric, our coresets effectively preserve the performance of practical heuristic algorithms (which are employed because this optimization problem is NP-hard) We further validate that our coresets for Kendall-tau are effective, í.e., maintain the solution quality, even when constraints such as faimess requirements imposed the solution.
1.3 TECHNICAL OVERVIEW
We now outline the proof of our main theorem, which consists of two parts, a general framework for arbitrary metric spaces (Section 3) and its concrete application to the & metric (Section 4).
Our framework establishes a key condition for a subset Q C P to be a stable coreset for P. called relative cost-difference approximation. It asserts that for every potential center in the metric space, the difference between its cost and the median's is cost remains approximately the same when measured relative to the input P or to subset Q, see (4), This condition is not sufficient by itself and need another condition, which is rather simple and holds with constant probability for a uniform sample.
To prove that uniform sample in E satisfies this condition, we leverage e-approximations, technique from PAC learning that is tightly connected to the range-counting problem in computational geometry. Li, Long, and Srinivasan (Li et al., 2001) provided tight bounds for this problem, which we apply in our analysis. While e-approximations support range-counting queries (i.e., ensures that the proportion of points in any range is preserved), we show through careful analysis that in & metrics, c-approximations for axis-aligned half spaces directly translate to preserving the relative cost structure across the entire metric space. We further establish that the query family of axis-aligned half spaces has VC dimension that is logarithmic in the dimension of the underlying space.
1.4 RELATED WORK
In ép metric spaces, the k-median problem for general is APX-hard visan, 2000), with some recent advances about its inapproximability (Cohen-Adee et al., 2022). In a metric space of bounded doubling dimension D, this problem admits polynomial-time approxima- tion scheme (PTAS), namely, (1 + approximmaiio that runs in time Õ ( n) (Cohen- Addad et al., 2021 a). Clearly this approach only practical when the doubling dimension is very small.
hh (Guruswami & Indyk, 2003; Tre-
Coresets for k-median have been researched extensively over the years, with particular emphasis on strong coresets in Fuclidean space, see (Feldman, 2020; Munteanu & Schwiegelshohn, 2018) for surveys and (Cohen-Adoa) sampling- mualing-bbseed coreset constructions originated in (Chen, 2009), which proposed partitioning the metric space into "rings" and sampling uniformly from each part. This approach was further improved in (Braverman et al., 2022; Cohen-Addad et al., 2021b), and while it yields strong coresets, the overall sampling distribution is non-uniform, and thus the running time is not sublinear.
et al., 2025; Huang et al., 2025; 2024) for the latest results. Uniform-
To enable truly uniform sampling, we must restrict our attention to weaker coresets and the case k = 1. Uniform sampling was shown to yield weak (0, e) -orrestsss for 1-median in Fuclidean space
4

---

Published as a conference paper at ICLR 2026
in (Ackermann et al., 2010; Munteanu & Schwiegelshohn, 2018; Danos, 2021), and these bounds were improved by Huang et al. (2023a) to weak (e, ((e)) -coresets of size O(3), alongside additional results for spaces of bounded doubling dimension and graphs of bounded treewidth (and also an extension general under additional assumptions about the dataset). For 1-median in f uniform sample of size O ( produces weak (0, coreeet (Danos, 2021).
In comparison, strong coresets for k-median & of size poly(k/e) follow implicitly by Jiang et al. (2024), because & is contained in -quuued,,, however, constructing such coresets requires least linear time.
Coresets for 1-center (aka Minimum Enclosing Ball) in & and in related metrics studied by Carmel et al. (2025). was shown that for both strong and weak coresets, the coreset size must depend on the dimension (in contrast 1-median).
PRELIMINARIES
We begin by showing that every strong coreset is also stable coreset, and every stable coreset is weak coreset, forming a clear hierarchy among these definitions.
Proposition 2.1. Let (X, dist) be a metric space and let P S X be a 1 1-median instance.
(a). Every stable (t, -c)orest of P is also weak (e, -cooeset.
(b). Every strong e-coreset of Pofor e E (0, {2), is also a stable (c, (c.oreecoreeet.
We next describe how stable coreset properties are preserved for submetries through isometric embeddings, An isometric embedding between metric spaces (K, dist1) and (22, dist2) is a mapping 1 X2 such that for every x. y E X,, have dist, (xr, v) (f f()).. The following fact is immediate.
Fact 2.2. Let f : X1 + X2 be an isometric embedding between metric spaces (K,,istt) and (22, di Then,
(a). f is injective; and
(b). for every P C X1 and e X1, cost(c. P) cost(f(e).
Observe that when f is injective, every subset of (PP can be written as f(Q) for some Q S P. Proposition 2.3. Let f X1 - X2 be an isometric embedding between metric spaces (N, dist,) and (22, distz). For every Q C P S X,, if f(Q) is stable (c, (c-oreeeeseet of f(P) in X2, then Q is a stable (c. -coorset of P X₁.
A FRAMEWORK FOR STABLE CORESETS
We develop general framework for proving that subsets C P in arbitrary metric spaces X' stable coresets, with detailed proofs provided in Appendix B. We apply this framework to & spaces Section 4, and believe that will lead more results in the future.
We use the notation from Section 1.1, and define also the normalized terms cost(x, P) == [P] cost(x, P) and opt(P) = [P] opt(P). Denoting by μ E X an optimal median point for P. we say that Q is an c-relarive cost-difference approximation (c-RCDA) of P in
[[ [ost((z, cosi(14 P)] cost(x; Q) cost(p,, Q)] < cost(a, P).
(4) Intuitively, this condition requires that Q preserves the gap in cost between every potential center and reference point, ensuring that the ranking of centers remains approximately the same whether evaluated on the original set P or the coreset Q. We remark that it is not crucial for this definition to have y be a median point, and it can substituted by any fixed point in the metric space, up to constant-factor loss in We now use this condition to establish that Q is stable coreset.
Vo E Ex
Theorem 3.1. Let P C X and E (0, t). and suppose cost(μ, Q) S c- cost(μ, P) for some c 2 1. I C P e-RCDA of in X then Q is (g, 4t)-stable coreset of P.
5

---

Published as a conference paper at ICLR 2026
4 STABLE CORESETS IN & THROUGH UNIFORM SAMPLING
In this section we prove the following theorem (some proofs appear in Appendix C). As usual, 4 denotes the metric space (TR I1-11
Theorem 1.4. Let P IRd be finite and let (0, 5)) Then, uniform sample of size O(c log from a stable (e/6, -co-ecet for 1-median in Ef with probability at least 4/5.
For a point x E IR we denote its i-th coordinate by =r[] Let T= [T., : [d], E RJ denote the class of threshold functions with Ti. (2) 1 (x(i)sr) for i [d] and r R.
Definition 4.1 (VC dimension (Vapnik & Chervonenkis, 1971)). Let F be class of functions from X' to {0, 1}. The growth function of F is defined integer m 2 1, G=(m)=
max Zg
f FY),
1Ex
and G=(0)= = 1. The VC dimension of F, denoted by VCdim(F), is the largest m 2 0 such that (r(m) = 2m Furthermore, set (fm such that (()(x)), ((5m-1)) f FF] 2d is called shattering set.
We now bound the VC dimension of the class of threshold functions T, showing that it is essentially logarithmic in the dimension d. While tight bounds appear in (Gey, 2018), we provide shorter proof for completeness.
Proposition 4.2. [log d] < VCdim(T) S 2 log d.
For given P. define the empirical distribution function for the i-th coordinate by edf r) := [PT Epep (p)) (p E P pli] s r) When d parameter i. We use this notation define e-approximation for P.
slightly abuse notation and omit the
Definition 4.3. Let P c Rd be finite and let c E (0, 1). A subset Q S P is an c-approximation for P
Vi E [d]. E,
(edfo(i, edf s.
Using theorem established by Li et al. (2001), we can bound the size of such e-approximation (see also (Har- Peled & Sharir, 2011)).
Theorem 4.4 (Li et al. (2001)). Let F be class of function from to {0, 1}, with finite VC dimension, and let 'D be some probability distribution over P. Then, with probability at least 1 - 8, random sample Q of size O (c= (VCCim((F)) + loo {)) satisfies
YSEF,
Σ f(x) xEQ
1000-EE1((xi E.,((( Se.
Q
We now apply Theorem 4.4, taking F - and D the uniform distribution over P, and the VC dimension bound from Proposition 4.2.
Corollary 4.5. Let P IRdd be finite and let e (0, 1). With probability least 1- 8, a uniform sample Q C of size O log 4) an e-approximation for P.
We now turn to showing how the above machinery can be applied to the 1-median problem under the E metric. Our main technical lemma, shows that an e-approximation subset is also O(E)-CDA.
Lemma 4.6. Let E (0, 1) and let P be finite set in et. If Q is an e-approximation of P. then Q is a 20e-RCDA of
Proof of Theorem 1.4. By Corollary 4.5 and Lemma 4.6, a uniform sample Q of size O log d) yields an e-RCDA of with large constant probability. Observe that
1 Q
E,cos((u, Q)]
1
lp
1 pll1 cost((u, P). PEP
P
TEQ
and thus by Markov's inequality, Pr|cost(μ,, Q) 2 cost((u, < 1.- By a union bound, with probability at least &. we have both that Q is an c-RCDA of and that cost((u,00 Q) < 6 ccos((44 P). To complete the proof of Theorem 1.4, we apply our framework, namely, Theorem 3.1.

---

Published as a conference paper at ICLR 2026
5 APPLICATIONS
Several applications of Theorem 1.4 follow immediately from known isometric embeddings into e In particular, Hamming distance, Kendall-tau, Spearman-footrule and certain graph- metries, such as tree metrics, can all be embedded isometrically into E,, allowing our coreset results to transfer directly to these spaces, see e.g. Corollary D. Another application that arises in computational biology is the genome-median problem, where the goal is to find consensus genome that minimizes the total evolutionary distance to a set of input genomes. The breakpoint distance a common metric for genomic comparison that can sometimes (i.e., under some restrictions) be embedded isometrically in f, with only a quadratic increase in the dimension (Tannier et al., 2009), making our approach applicable. Below, address the Jaccard metric separately, since its isometric embedding requires high dimension; however, low-distortion embeddings can be easily employed instead.
Near-isometric embeddings. We extend our results to metrics that embed into & with distortion close to showing they admit stable coresets with parameters adjusted according to the distortion. As usual, an embedding between metric spaces (X1, disti) and (A2, dist2) is a map f ; Xi - X2. We say that it has distortion D 2 1, if there exists
(scaling factor) such that
Ya, E X1,
b dist (f(). S r. dist, (x, v) S D -dista(((x),((()))
(5)
One can often assume that r = 1 by scaling e.g. when the target X2 is a normed space. We mostly use the case D= = =1+ S for E (0, 1), and then the distortion is D2 = + O()).
Proposition 5.1. Let f: Xi + X2 be an embedding between metric spaces (N2, dist2) with distortion D and scaling factor r. For every Q C X₁ f() is a stable (e. n)- coreset of f(P) in for some E, O, and the values é' := (1+e)/D²-1 -1 land n/ := D2 (1-n)) are positive, then Q is a stable (e', n/ correstt of P in X2.
and
This proposition extends our results in Theorem 1.4 to metric spaces that can be embedded into L with small distortion. For example, our results extend to the Euclidean metric using Dvoretzky's Theorem (Gordon, 1988; Schechtman, 2006), yielding stable coresets of size O( log(d/c) for 1-median in fd see Appendix D.2. We remark that it suffices to have the distortion guarantee (5) only for pairs that involve a point from P. which is known in the literature as terminal embedding, see Appendix D.1.
Corollary 5.2. Let (X,dist) be metric space that embeds in II-Ih) with distortion 1 + 3 for e ta). Then uniform sample of size O log d) from a finite P S X stable (e, (()))-corese for 1-median X with probability at least 5-
Stable coresets in Jaccard metric. Consider the Jaccard metric over d elements, i.e., over ground set [d] without loss of generality. It follows immediately from (Broder et al., 1998) that the Jaccard metric embeds with distortion + Ç into l space of dimension O(c-2 Thus, Corollary 5.2 implies coresets for the Jaccard metric, as follows.
Corollary 5.3. Let P C 2id) and let E (0, 1/). Then uniform sample of size O O log(d/e)) from is a stable (e, ((e)))coreset for 1-median in Jaccard metric with probubility at least $
This result provides the first coreset construction based on uniform sampling for the Jaccard metric. Prior work implies strong coreset of size Ō(c -222), because it holds for k-median in & by Jiang et al. (2024), however its construction algorithm must read the entire dataset.
Approximation algorithms for h-median. In metric spaces that admit stable coresets through uniform sampling, we can employ the framework introduced by Kumar et al. (2004) and further refined for additional metric spaces by Ackermann et al. (2010). These papers design approximation algorithms for k-median in metric spaces that have the property that for every instance P, a 1-median of P is approximated (with high probability) by an optimal, or approximately optimal, solution for uniform sample Q C P. We restate the main theorem in (Ackermann et al., 2010) using the language of stable coresets, and it now be applied to several metrics where it was previously unknown, including Hamming, Kendall-tau and Jaccard, thereby extending existing 1 1-median algorithms to the more general k-median problem.
7

---

Published as a conference paper at ICLR 2026
Theorem 5.4 (Theorem 1.1 in (Ackermann et al., 2010)), Let E (0, and let (X, dist) be metric space such that
X admits stable (e, ((e)(()))cooess through uniform sampling of size 8, with constant probability; and
1-median in X admits (1 caapproximaaioo algorithm that runs on input of size n' in time f(r',c)
Then k-median in X admits (1 + -pproxxappoiinnaiiion algorithm that input of size n in time f( (ks,/e))
An alternative approach for & metrics, proposed in (Jiang et al., 2024), to build a strong coreset of size O(² and then solve the coreset instance by enumerating over all its k-partitions. In both approaches the running time is exponential in the coreset size, and in many reasonable settings, this exponential term is larger than the input size n and thus dominates the total running time.
C-dispersed instances. We can actually refine Theorem 1.4 prove that when the input satisfies certain technical condition, uniform sampling yields strong coreset, rather than merely stable coreset. This refinement is particularly valuable when (1 + -))-approximttion algorithms, for B >> C, available, because applying such an algorithm on the strong coreset achieves (1 3) + O()))- approximation for the original input P. offering a significant speedup with marginal increase in error, compared to applying that same algorithm directly on P. This advantage becomes especially significant for in discrete metric
the median problem is NP-hard. Although PTAS algorithms exist for these metrics, they often complex implement and computationally expensive, making them impractical. In such scenarios, constant- factor approximation algorithms and heuristics offer more accessible and efficient alternative.
such as Kendall-tau and Jaccard-
The technical condition we require is quite simple, and has been used in some literature without defining or stating explicitly. We say that instance C-dispersed for C > 1 if its diameter is at most C times the average distance inside it, that is,
1 PP
||= -vll SC Z.JE
E1-- y111
Z,PEP
Theorem 5.5. Let P C Bd be finite and C-dispersed, and let e E (0, 5). Then uniform sample of
size P2 log 4) from P is strong e-coreset for 1-median in E4 with probability at least 1 5.
EXPERIMENTS
We demonstrate the empirical effectiveness of stable coresets for the median problem through experiments on real-world datasets across different metrics, comparing their performance against apportance-sampliigg methods. Our evaluation measures the relative error between the cost of solution computed on the coreset and the cost of a solution computed by the same method on the original dataset, that is,
È cost(ER, P) cOSt(EP) .P) cost(af, P))
(6)
where @ is a center computed for the coreset Q, and 6 is center computed for the original dataset P. This relative error is expressed as a percentage. In our experiments, we examine points in Rd endowed with the & metric as well as permutations under the Kendall-tau metric. For points in Rd we efficiently compute the optimal median by taking the coordinate-win wise median, while for permutations we employ either heuristic methods an Integer Linear Programming (II.P) approach.
Experimental setup. All experiments were conducted PC with Apple MI and 16GB RAM running Python 3.9.6 on Darwin 22.6.0. For each experiment, we report the average results over 20 independent runs ensure statistical significance. The datasets used in experiments detailed in Table 1. The source code used to run the experiments is available at https: :tts:://giiiee github. com/ ami rea rme - labllaab/ttaaee eetteeetssss..s.
8

---

Published as a conference paper at ICLR 2026
Table Specifications of datasets used in Section
Dataset
Size Dim. d Description
Yellow Taxi NYC (YT) (NYC Taxi and Limousine Commission, 2024)
2.8M
11 New York City taxi trips in Jan. 2024
Twitter (Chan et al., 2018)
1.3M
3 Timestamp, latitude, longitude of tweets
Single-Cell Gene
7,865
33,586 Peripheral blood mononucicar cells
Expression (SCGE) (10x Genomics, 2019) My Anime List (MAL) (Valdivieso, 2020)
gene expression
234K
50 User rankings of anime titles
(a) YT
(b) Twitter
(c) SCGE
Figure 1: Tradeoff between coreset size and relative comparing importance sampling- based coresets with uniform sampling-based corescts across three datasets. Shaded regions represent one standard deviation.
Experiment 1: Comparison with importance sampling. We compare uniform sampling against the importance sampling-basee coreset construction proposed by Jiang et al. (2024). Their method works by iteratively computing sensitivity scores for each point and sampling progressively smaller subsets, with each iteration reducing the size by a logarithmic factor until achieving a dimension- independent coreset. In implementation, we evaluated their approach using both and two iterations of this reduction process. The comparison focuses on the 1-median problem in & metric across three datasets from Table 1; Yellow Taxi NYC, Twitter and Single-Cell Gene Expression.
Figure demonstrates that uniform sampling achieves comparable error rates to importance sampling across all datasets. This efficiency difference is fundamental: importance sampling requires examining the entire dataset, resulting in construction time linear in the dataset size, while uniform sampling requires only constant time per sample and completely dataset-oblivious- or processing of the dataset prior to sampling. In our experiments, importance sampling took approximately 82/1 114/512 seconds for datasets YT/Twiter//CGG respectively, whereas uniform sampling required only 0.0001 seconds to sample 500 points. The shaded regions represent one standard deviation, demonstrating comparable variability between the two methods.
requires no inspection
Experiment Heuristic for Kendall-tau distance. Using the MAL dataset, we aggregated rankings of 234K users over 50 anime titles. We implemented five widely used rank aggregation methods: three Markov Chain-based approaches (MC1, MC2, MC3), Borda's sorting algorithm and scaled footrule aggregation (SFO) (Dwork et al., 2001; Kaur et al., 2017). Figure 2a illustrates the relative error solutions computed on coresets of different sizes. It is important to note that these heuristics do not directly optimize the Kendall-tau cost. Consequently, solutions computed on the coresets can occasionally yield lower Kendall-tan costs than those from the original dataset, resulting in negative relative error values. The results confirm that relatively small coresets achieve results comparable to those obtained on the original dataset, even when using heuristic approaches.
Experiment 3: Fairness constraints. In this experiment, we sampled coresets of varying sizes from the dataset and then applied fairness constraints based on arbitrary partitioning of items into two groups. We implemented the fairness-constraing constrained integer linear programming algorithm by Kuhlman & Rundensteiner (2020) both the original dataset and the coresets. Due to algorithmic constraints, we restricted the dataset to 8,700 user rankings, with each user ranking 16 anime titles. This algorithm optimizes the Kendall-tau cost objective while enforeing the fairness measure as

---

Published as a conference paper at ICLR 2026
05
-03
Conoed
Blzz
(a) Comparison ranking method performance with respect to coresct sizes. The plot shows relative er- for (%) between coreset approximation and original dataset results. Regression lines demonstrate enror trends as coreset size increases, with data points mark- ing actual experimental measurements.
(b) Impact fairness constraints on coresct approx- imation error. The parameter represents the prob- ability of sampling popular anime titles across two distinct groups.
0.5 indicates balanced sampling between groups, while lower p values indicate one group containing predominantly less popular anime. Shaded regions represent the standard error of the mean across multiple experimental runs.
Coreset Size (AAP--0 (skperticcoo)) (skpertb.002))
025
Deratve Ener (%)
0.20
0.19
005
(c) Relative error (%) versus number of dimensions (log scale) for differ- ent coreset sizes. Regression lines demonstrate error trends as the number of dimensions increases. The slope is outlined for each regression line. Note that as the coreset size increases, the variance decreases, making the slope coefficient more statistically meaningful.
a linear constraint. Negative error values occur because the ILP solver might find slightly better solutions the coreset rather than the original dataset. Figure 2b demonstrates that solutions obtained from even small-sized coresets closely approximate those from the original dataset. This confirms that uniform sampling produces stable coresets that effectively support constraint-based optimization, even when those constraints were not considered during the sampling process.
Experiment 4: Dimension dependency. While our theoretical analysis establishes stable coreset size bounds that depend on the dimension d (Theorem 1.4), we conjecture that this dependency is unnecessary. This experiment specifically tests whether the uniform sampling coreset performance remains dimension-inndeeeddett
To test this, we utilized the high-dimensional Single-Cell Gene Expression dataset (7,865 samples across 33,586 dimensions). For given dimension count d, we randomly selected dimensions from the input dataset and then uniformly sampled a coreset for various sizes (150, 300, 500), For each coreset, measured the relative error defined in Equation 6.
Figure 2c illustrates the relationship between dimension count and error rates. We note that the slight upward trend in error is likely attributable to sampling variance rather than dimensional dependency. This demonstrates that the relative error remains stable as dimension count increases, supporting our conjecture that the theoretical bounds could be tightened yield dimension-inndeeedeen bound.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
10x Genomics. PBMCs from healthy donor -protein (v3 chemistry). Single Cell Gene Expression Dataset by Cell Ranger v3.0.0, 2019. URL ptttps::/suppooee Oxxeeomiccsssso.emmom.ooo com/ single-cell -ee--geeeeeeeee eeeeeexxxeeesiiie exp.rssscco/atttsttttts////////e dataaaasssss////eee 0/ 10k
Accessed: March 2024.
Marcel Ackermann, Johannes Blömer, and Christian Sohler. Clustering for met- ric and nonmetric distance measures. ACM Trans. Algorithms, 6(4):59: 2010. 1oi: 14/111144////4777182477779
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In FOCS, pp. 462-473. IEEE, 2022. doi: 1001110...00000555555.2020000 20025444447.22200033
Andrei Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise indepen- dent permutations. In STOC. pp. 327-336. ACM, 1998. doi: 10. 011114766668822777888
Amir Carmel, Chengzhi Guo, Shaofeng H.-C. Jiang, and Robert Krauthgamer. Coresets for 1-center in & metrics, In ITCS, volume 325 of L/Pics, pp. 28:1 1-28220. Schloss Dagstuhl Leibniz-Zentrum für Informatik. 2025. dot:10.4230/LIPICS....
2025.28.
Diptarka Chakraborty, Syamantak Das, Arindam Khan, and Aditya Subramanian. Fair rank aggregation. In NeurlPS, volume 35, pp. 23965-2333 23965-23978. Curran Associates, /
Inc., 2022. URL pictps://papers nips htc//pper_files/papppeppeeeee
T-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Twitter data set. GitHub repository, 2018. Accessed: March
URL http:///gg.saooooccc/e//eeeeee/s 2024.
Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923-947, 2009. 1oi:10.11333 101111777077999007.
Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time ap- proximation schemes for clustering in doubling metrics. ACM, 68-4)44::144 2021a. 1oi:100.145/3477541
Vincent Cddan-Addad, David Saulpic, and Chris Schwiegelshohn. Improved coresets and sublinear algorithms for power means in Euclidean spaces. In NewrlPS, pp. 21085-21098. Curran Asso- ciates, Inc., 2021b. URL https: //ppccecer////oo/pooo ngs. neurips cc/ hoccpappr/20211.11 //a///h//////// Abstraatt.tttt..aaa....... html.
b035d55632addc
Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson coverage hypothesis: Inap- proximability of k-means and k-median in ep-metries. In SODA, pp. 1593-1530. SIAM, 2022.
(60::00.13777..78161197777..4.4
Vincent Cohen-Addad, Andrew Draganov, Matteo Russo, David Saulpic, and Chris Schwiegelshohn. tight VC-dimension analysis of clustering coresets with applications. In SODA, pp. 4783-4808.
SIAM, 2025. doi: 10. / .978161 1978322.162.
Matan Danos. Coresets for clustering by uniform sampling and generalized rank aggregation. Master's thesis, Weizmann Institute of Science, Rehovot, Israel, 2021. URL https www.. wisdom. weizmann. ac il//robi///i//eeee heaooi/fiiiee files
11 11d.:2211111_1....11111111111111
Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pp. 613-622. ACM, 2001. do
Dan Feldman. Core-sets: An updated survey. WIREs Data Mining Knowl, Discow, 10(1), 2020. doi: 10. 133.0/.......335.
Servane Gey. Vapnik-Chiie Chervonenkis dimension of axis parallel cuts. Communications in Statistics- Theory and Methods, (709)2291-22944 2018. doi: 10. 019003666092222071339998
11

---

Published as a conference paper at ICLR 2026
Yehoram Gordon. Gaussian processes and almost spherical sections of convex bodies. The Annals of Probability, (6(1):180-188 1988.
Venkatesan Guruswami and Piotr Indyk. Embeddings and non-approximabiiiy of geometric prob- lems. In SODA, pp. 537-538. SIAM, 2003. URL https: //dl acm. hwtgg/oo//10.. 644108. 644198.
Sariel Har-Peled and Micha Sharir. Relative (p.))-approximatioons in geometry. Discrete & Computa- tional Geometry, (5(3))4462-4999 2011. 11011010007/00445400000002700000
Lingxiao Huang. Shaofeng H.-C. Jiang, and Jianing Lou. The power of uniform sampling for k-median. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 13933-13956. PMLR, 2023a. URL wwwp::ttt////c..ctc pwwoceeoooeeeeee// ngs. ml pressprsssee...................e https//v22////aa// h00000//uaagg3 html.
Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In The Eleventh International Conference on Learning Representationss, ICLR 2023. OpenReview.net, 2023b. URL https: httppa/tww..eeeeeeeeeoeoooaaaaaa
Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for Euclidean (k, 2)-
clustering. In STOC, pp. 1594-1604. ACM, 2024. 66::10011453211126033449400
Lingxiao Huang, Jian Li, Pinyan Lu, and Xuan Wu. Coresets for constrained clustering: Gen- eral assignment constraints and improved size bounds. In SODA, pp. 4732-4782. SIAM, 2025.
Piotr Indyk. Sublinear time algorithms for metric space problems. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 428-434. ACM, 1999. doi: 10.11445//312500001366
Piotr Indyk. High-dimensional computational geometry. PhD thesis, Stanford University, 2001. URL /ttpps://pet https/::/pppppeccccoc csail. mit. eaait...d/nnndkk/tteeeei
html.
Shaofeng H.-C. Jiang, Robert Krauthgamer, Jianing Lou, and Yubo Zhang. Coresets for kernel clustering. Mach. Learn., 113(8):5891-590) 2024. doi: 100.1001007/110994000000
Parneet Kaur, Manpreet Singh, and Gurpreet Singh Josan. Comparative analysis of rank aggregation techniques for metasearch using genetic algorithm. Education and Information Technologies, 22 (3):965-983, 2017. doi: 1007/s10639-01669990
Caitlin Kuhlman and Elke A. Rundensteiner. Rank aggregation algorittt for fair consensus. Proc. VLDB Endow. 13(11))2706-277 2719, 2020. doi: 10. 10011477778/44779904077555
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time aaproxxiitiinittii algorithm for k-means clustering in any dimensions. In FOCS, pp. 454-462. IEEE Computer Society, 2004. doi: 109/0FCC./0000
Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. J. Comput. Syst. Sci., 62(3):516-527, 2001. doi: 10i:10..106//esss 1006//css.2000..1744
Yair Marom and Dan Feldman. k-means clustering of lines for big data. In NeurlPS, pp. 12797-12806, 2019. URL https::/ppocceediiiiiii .nw.eeedddnnnnnnnnis..........pe neurips wccpppape///19////eeeccc 21/22099hhh// 6084e82a08cb977 7c (eeee339555aeeeeeeeeeeeeeee -at.e//aaaadddeddddd----areeette .bst.ract.. html.
Alexander Munteanu and Chris Schwiegelshohn. -oresets-methods and history: A theoreticians
design pattern for approximation and streaming algorithms. Klinstliche Intell., 32(1):37-53, 2018.
doi: 10. 1000//132188 12007753311--11--5119929
NYC Taxi and Limousine Commission. TLC trip record data. NYC.gov Official Website, 2024. URL page. Ac-
https: / www. , nyc. wwt.:/ooo/ssteeeeeeeeeeeooeeee
cessed: March 2024.
Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg. Fair ranking: critical review, challenges, and future directions. In Proceedings of the 2022 ACM conference on fairness, accountability, and transparency, pp. 1929-1942. ACM, 2022. doi: 14.3533333
12

---

Published as a conference paper at ICLR 2026
Jeff M. Phillips. Coresets and sketches. In Handbook of discrete and computational geometry, chap- ter 48, pp. 1269.1288. Chapman and Hall/CRC, 3rd edition, 2017. 10011011201/978111111661..
Evaggelia Pitoura, Kostas Stefanidis, and Georgia Koutrika. Fairness in rankings and recommenda- tions: an overview. The VLDB Journal, 3133)431-458, 2022. 0001100.007//0078-011-0000000
Gideon Schechtman. remark concerning the dependence on in dvoretzky's theorem. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) /987-88, pp. 274-277. Springer, 2006.
Eric Tannier, Chunfang Zheng, and David Sankoff. Multichromosomal median and halving problems under different genomic distances. BMC Bioinform., 10, 2009. doi: 177-11/6//44710--1111
Tian Tian, Jie Zhang, Xiang Lin, Zhi Wei, and Hakon Hakonarson. Model-based deep embedding for constrained clustering analysis of single cell RNA-seq data. Nature Communications, 12, 2021.
Luca Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree. SIAM Comput., 30(2):475-485, 2000. doi: 1001:0...17//0077799999333777
Hernan Valdivieso.
Anime recommendation
database 2020.
Kaggle dataset,
2020.
URL https://www http://www..gggg.ee. com/ comm/dataeet.e mussets/hernan4444
Accessed: March 2024.
Vladimir N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971. doi: 10. 1137/11 6025. English translation by B. Seckler of the original Russian paper published in Dokl. Akad. Nauk SSSR, 181(4):781-78, 1968.
Pengxin Zeng, Yunfan Li, Peng Hu, Dezhong Peng, Jiancheng Lv, and Xi Peng. Deep fair clustering via maximizing and minimizing mutual information: Theory, algorithm and metric. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, pp. 23986-23995, IEEE, 2023. doi: 10. 10111///V22299900200002222
13

---

Published as a conference paper at ICLR 2026
A PROOFS OMITTED FROM SECTION 2
Proposition 2.1. Let dist) be a metric space and let P C X be a 1-median instance.
(a). Every stable (c, coreesee of also weak (e, -orrese..
(b). Every strong e-coresel of P. E (0, }), is also a stable (e, 4e)-eeseset.
Proof. To prove Item (a), let cº, cd denote optimal medians for P, Q in X. respectively, Consider X with (c,t(c, Q) x (e) QQ). Then, cost(e, Q) S (1++) cost(c&, Q) S (1++) cost(c" Q). Then, following Equation cost(c, P) S (1 + 7) cost(c", .P).
To prove Item (b), let c1, E X' such that cost(c1, Q) & (1+c) cost(c2, Q). Following the definition of strong e-coreset, it follows that:
cost(ct, S) cost(cs, Q) (1+ cost(r2, Q)
-- v
1-
(1 + (1 cost(e2, P) s (1 (1+ 4e) cost(e2, P).
Fact 2.2. Let f R1 + 22 be an isometric embedding between metric spaces (N,, disti) and (22, distz). Then,
(a). f is injective; and (b). for every P C X1 and Xi, cost(c, P) cost(f(c),
Proof. For Item (a), if * r2, then dist, (I1, x2) + 0, thus f(x) & f(x2). For Item (b),
cost (c, P) = Epep dist, (c,p) Eppe p dista (c), f()) = (os))
Proposition 2.3. Let f Ri + X₂ be an isometric embedding between metric spaces (Ri, dist1)
and (X2, dist2). For every Q C S X1 f(Q) is stable (e, coroeest of f(P) in X2, then Q
stable (c, -)ocrsse of P in Xi.
Proof. Let C1. C2 E X1 such that cost(c1, Q) < (1+ c) cost(c2, Q). By Fact 2.2, this implies cost(f(ci), f(Q)) < (1 + e) cos)(f(c2), f(Q).. Consequently, have cost(f(c), s
(1 + 11) (((c), Applying Fact 2.2 again yields cost(c1, P) s (1 + 7) cost(c2, P).
A.1 STABLE CORESETS IN FINITE METRIC SPACES
We remind the reader the following result by Indyk (2001).
Theorem A.1 (Theorem 31 in (Indyk, 2001)). Let E (0, 1), and Q be random sample from P.
For arbitrary pair of points a, b E X, if cos P) (1 e) cost(b, P), then
Pr|cost(a, Q) > cost(b, Q) 2 1 (/Q1/64
folklore analysis based on Thoerem A. leads the following result.
Corollary A.2. Fix finite metric space X' and let P C X. Then, for every e, E (0, 1), uniform sample Q C size [Q] > 64c -2 In X + ln(1/5) is a stable (0, e)-coreset with probability at least 1 8.
Proof. Let contain all unordered pairs a, E X' such that cost(a, (a, P) > (1+ e) cost(b, P). For each such pair, let A.,s be the event that cost (a, Q) I cost(b, (,, Q), Then by applying Theorem A.1 and union bound,
Pr[ Q is not stable (c, -)-orestt S Pri
Σ Pr[Auu] < 21x
2 <8.
a.eES
14

---

Published as a conference paper at ICLR 2026
B PROOFS OMITTED FROM SECTION
Theorem 3.1. Let P S X and e E (0, t)), and suppose cost(H, Q) S c. cost(H,, P) for some c 2 I P an c-RCDA of P in X' then Q is (2, 4c)-stable coreset of P.
Proof. Let u, y E such that cost (x, , P) > (1 + 4e) cost(y, P). Using (4), we have
cost(2, Q) 2 (1 - c) cost(2, x. P) - cost (11, P) + cost (4, Q)- costlyy, Q) < (1 + <) cost (y, , P) cost P) cost (11, Q).
We can then derive
cost(x, Q) 2 (1 - <) cost (2. P) cost( (u, P) + cost (Ju, Q)
(1 - <1 4e) cost(yy, P) cost(u, , P) + cost(H, Q)
= (1 + E + 2c(1 - 2c)) cost(y, y, P) cost(M, P) + cost(14 Q)
2 cost(y. (y. Q) 2c(1 - 26) cost(y, (y, P).
(7)
Using (4) again, we can write
(1 costly, P) cost Q) cost( P) cost(H, Q) 2 c
cost(y, Q),
where the last inequality follows from the fact that cost(y; Q) 2 cost(ı, Q) and cost(u, Q) S ccost( P). Consequently,
cost P)
c(1 +c) cost Q).
Plugging this into (7) and using our assumption that 5. we conclude that
cost(xr, (x, Q) 2 1+ 2c(1 2E)
cost(y,, Q) 2 (1 -) cost(y, Q).
c(1 +e)
C PROOFS OMITTED FROM SECTION
Proposition 4.2. [log d] S VCdim(T) S 2og
Proof. For the upper bound, let VCdim(T) m. then there are m points .mm- E Rd such that V {(T(x)).... .... T (()m-1)) т E T} of size 2 We restrict attention to tu- ples (7(20), ..... T (mm-11) E V whose coordinates sum to | denoted V2 E v[t] = 1 J}. For each vector, i.e., such that v = (T(zo).... ..... (Tm-1)) We denote this function by Ti..r., some i, E [d] and E R. We claim that if eı # U2 E V W/m2 then in * iug. To see this, assume without loss of generality that Te, I Tuy If ir, iuz, then for every x E R, They Toy (z) = implies Ti., .r,, (z)=1) 1. Since the coordinate sums of U2 and 222 are equal, we must have U1 02. Therefore, by the pigeonhole m
{u E V Vm/2, we select a threshold function T E T that realizes this
2 we get that principle, /Vm/2l & d. However, using the known bound VV,, \Vm/2 (1 /2m m S 22logd
For the lower bound, we construct shattering set of points zo. .... Im-1 E Rd where m = log d (assuming for simplicity that d is power of 2). We identify each coordinate with binary vector E (0, )mm corresponding to its binary representation, and define 2:[v] - r[i]. To show that Fo, Im is shattering set, consider the functions (Tx, (00)())001))m C T. For every v E (0. 1M
we have:
(Tr.g (2o).... T..3 (2m-1)) = (1 [o(ss 2m- (m]3)) = (1 [0 p/m 1/2 =
15

---

Published as a conference paper at ICLR 2026
Let P R of size we may assume that P contains no repeated points, as duplicate points can be perturbed by an infinitesimal amount. Denote by μ E I' median of P. We will also need the following well-known fact.
|P], and assume for simplicity that is odd. Without loss of generality,
Fact C.I. Let P Rd be finite. Then, is E Rdd is a 1-median for if and only for every i E [d] piii] is a median value of the i-th coordinate of all points in P.
Lemma 4.6. Let E (0, 1) and let P be finite set in E1. If is an e-approximation of P, then Q is a RCDA of
Proof. We first consider d = 1, and without loss of generality assume S μ. To evaluate the difference in average costs, we break the calculation into the three regions L. M, and U (similar
strategy was used in (Danos, 2021)): L == {p P p z), . := {p P : < p S p). and := = (p E P < p}. In each region, we can simplify the expression |x - pl
pl
by expressing the absolute values explicitly, which allows us evaluate cost(2;; P) cost (/s, P)- Notably, in regions L and U. the value of jæ pl 1u pl depends only on æ and μ. not on the specific value of p. Observe that |L| = |P ed)) [M Pl (edf edf ((r) and
|U] =
|P| (1 edf (u))
LPI We can write
2
cost(rr, P) - cost (11, P)
1 P
T
p
pl + Σ x - pl) - -cost P)
PEL
PEM
PEU
(1p- pl - 1x - mI) + Σ
(1x 14| - 111- pl)
P
PET.
PEM
(Iu pl + 1
m1) -xx--1))
cost (1,, P)
PEU
x pl+ Σ
x p + Σ
x pl
PP
DEL
PEM
PEU
2
Σ 1 pl)
PEM
|r ml - 2edfr(x))
2
Σ
1u
pl.
PP
PEM
Similarly for Q (the fact that μ is a median of P is not utilized in the argument above).
cost(x, Q) - cost(u, Q) = x - =1[11 2 2edfo(z))
Σ 11
gl.
[Q1
gEnnQ
and thus
cost(rr, (I,, P) cosi(u, P)) (cost(aa (3r, Q) (1, Q))
= 2/1 11( vl((edf((z)) - edl (x))
2
|l
pl
2
Σ
11
(u-gl. gl.
(8)
PP
Q
PEM
GEMNQ
We will now bound each of the terms in (8). The first term is bounded utilizing the c-approximation property of Q
-2e/ x| < 2/1 nl( (l(edf((x) edfr(x)) < 2e/n ar|.
We now bound the term To, J,,... It. such that each interval contains exactly 2e| PI points, except for the last one which might be smaller. We denote T; = (pc, 1,),,, with po = x and p l and a; + n for = O....,t
1 EnEMno |μ - gl [ EpEn M I1e - pl. Partition M to intervals
I
Here the idea is to partition M into intervals containing a controlled number of points, leveraging the fact that Q approximates the proportion of points in each interval. By bounding each interval's contribution using the interval endpoints and the relative difference in point counts between P and Q.
16

---

Published as a conference paper at ICLR 2026
then applying telescoping sums across all intervals, average distances in Q can deviate from those in P across the entire region M.
establish tight bounds on how much the
Each interval contains at least 0 points from Q and at most 4e points from Q. Consequently, -2e S Di=ji a; S 2e, for every j1 S f2. We can write
1 P
1
Σ gErinQ
gl
1 pl.
Q
Q
[P|
MEMNQ
PEM
M
i=0
1=0 pEtnn
For the upper bound,
1 91
P
1=0 q
1=0 PE PPP
10
p:l
|p - Pi-1l
P
0= qEliNQ
i=0 gEliP
1 Qllu
Pıl
4 Plly P
P
1
(a: +
Pl)
pıl
I1 n Pllp Pit1l
|P|
|P| i=0
1. Pl
0:1l p:l + Σ
(1p - psl - 11p - Pi+1
P|
1=0
i=0
aslu - pıl + 26 Σ
(pi+1 - pp:) S 4e x/b
1=
0=0
Similarly for the lower bound,
1
Σ Σ
1 gl
Σ
1 1P-P) p
Q
[P|
PETiNQ
i=0 gET,NP
1 Pi+1l
Σ
|p Pil
1= gElinQ
1=0 gELinP
as/u Pit1l + 2c Σ
(p: Pi+1)
1=0
2 4E k z/--
We get that
8c/p x 5
2 P
110 pl
2
Σ
1p a 8elu x/.
(10)
Q
PEM
gEMNQ
Thus, by combining both Equation 9 and 10, we obtain
-0eepp < (cost(x, P) - cost(p, P)) (cost(xr, Q) - -cost(u, Q)) S 100epp - x².
The case d = 1 follows because cost (r, P) 2 1
[ EpEU lr -r-pl= 2
1 IP. Epeu xx x pl = T |x 44|
U
1 la nl. where the last equality uses |U| = Pl
The general case d 2 1 follows immediately because cost(r, P) Σin (2, P), where cost, (z. P) = | Eper x0||] plil This completes the proof of Lemma 4.6.
17

---

Published as a conference paper at ICLR 2026
D PROOFS OMITTED FROM SECTION 5
Stable coresets in Kendall-tau metric. To illustrate one concrete example of Theorem 1.4 in & related metric space, consider the Kendall-tau metric on permutations. The Kemeny embedding maps each permutation a Sa to a binary vector in {0, 1) where ( Proposition 2.3 with Theorem 1.4 yields:
[ab]<bb] Applying
Corollary D.1. Let P C Sa be finite and let (0, () Then uniforrm sample of size O log d) from a stable (e/6, cco-esttt for 1-median Sa under the Kendall tau metric with probability least 4/5.
We emphasize that only the existence of an embedding into is necessary; the explicit form of this embedding need not be known to derive these coreset guarantees.
D.I LOW-DISTORTION EMBEDDINGS
Proposition 5.1. Let f X1 + X2 be an embedding between metric spaces (X1,dist) and (X2, dist2) with distortion and scaling factor r. For every Q P S if f(Q) is a stable (c. 7)- coreset of f(P) in N2 for some e, > O, and the values é' := (1+e)/D²-11 Lad == D2 are positive, then Q is stable (c', of -coreset of P in X1.
Proof. Let v.y y E X1 such that cost(2. (z, Q) S (11 cost Q). Using the fact that f has distortion D2 we obtain
cost fost) - Dr cost(r, (r Q) < Dr(1 + c') cost(y. Q)
< D + (ost( - (1 ++++ (ost()())))
Where the last inequality follows by our choice c'. Since f(Q) stable (c. -coreset it follows that cost(f(z), f())) s (1 (1 n) cost(f(y), f(P)). Using the properties of f again
cost(ar, P) s (fs) < D (1 (1+ + n) cost( f(P)
< (1+ P) S (1 + n/) cost(y, P):
where the last inequality follows by our choice of r/'
terminal embedding with distortion 2 2 1 between metric spaces (K, disti) and (X2, dist2) with respect to P is a map f Xi - X2. such that for some > 0,
Vp E P. Vx E X1,
1 dist (f)) & r dist, (p. x) S D dist (is)
(11)
D
Clearly this is weaker guarantee. Note that the proof of Proposition 5.1 holds immediately for this definition as well. Moreover, it is worth noting that in many practical scenarios, the distortion in Equation 5 is one-sided in which case the error propagation would occur only once, improving the approximation guarantees in Proposition 5.1.
D.2 STABLE CORESETS IN EUCLIDEAN METRIC
Gordon refined Dvoretzky's 's Theorem and showed that e embeds with distortion 1 into Ole (Gordon, 1988; Schechtman, 2006). Thus, Corollary 5.2 implies the following.
Corollary D.2. Let P C Id be finite and e E (0, H.) Then uniform sample of size Plggd/o from P is stable (e, (())) ((e))-coreset for 1-median in & with probability at least $
This result provides different tradeoff than prior work (Huang al., 2023a), which showed that uniform sampling of size ((--3) yields weak (c, -coreecorese..
18

---

Published as a conference paper at ICLR 2026
D.3 C-DISPERSED INSTANCES
Theorem 5.3. Lel P C Rd be finite and C-dispersed, and let e E (0, (). Then a uniform sample of size O(Cc-2 i) from P is strong e-coreset for 1-median in Eq with probability at least 1 6.
Proof. As before, let μ denote a median of P. By the triangle inequality,
max
1
yll
Σ
1 x
211 S
2C
Σ
11 x|11 20 2Cop((P)
ZyEP
P|
[P]
Z.YEP
and thus for every I. E
P.
|1 11||
1
Σ
11 y + =11
1
Σ
(1 - 111 - 1 x (l)
PP]
PP]
VEP
yEP
S opt (P) + 2C opt( P) < (2C + opt(P).
Additionally, E clsss (1, Q)] = cost (1,, P) = opt( P), and thus Chernoff's 's bound implies
21 Pr cost( Q) cost (H, P) cost(14, (1, P)] s 2cxp (- 3(2C + 1)
)
$ 6
Following Corollary 4.5 and Lemma 4.6, with probability at least RCDA. By the union bound, with probability at least 5, have that Q is 3-RCDA and (p, P) (os Q) & cost((u, P). In this case, for every Rd.
the subset Q is 5-
(os P) - (2, Q)
< cost((r, P) - cost( u, P)] [cost(I, Q) cost(H, Q)] + cost((,, P) - cost((,, Q)
cost( /u, P) S cost(r, P), 2 cost (I,, P) + c
<
2
which establishes that Q is strong e-coreset.
19


Reviews:
[{"review_id": "s4aMieMRWe", "reviewer": "Reviewer_tpLe", "summary": "The paper proposes the notion of stable coresets which offers a trade-off between the prevalent notion of weak coresets (provide approximation guarantee only for optimal queries) and strong coreset (provide approximation guarantees for all the queries). The authors show that while the notion is much stronger than a weak coreset, a stable coreset can still be constructed using uniform sampling making it much more scalable. This is not usually the case with strong coresets. The paper shows a stable coreset for 1-median in $\\mathbb{R}^d$. Experimental results demonstrate the effectiveness of stable coresets.", "questions": "1. Can you comment on the following: Do you think it is possible to build smaller stable coresets via importance sampling?\n2. Will uniform sampling work in general for other problems?\n3. For theorem 3.1 $\\eta$ is independent of $c$. Why? Please explain the impact of $c$ on quality of approximation in $\\mathcal{Q}$ also.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Strong coresets require finding out importance sampling distribution which is usually tough to obtain. The stable coresets give most benefits of strong coresets. So, the idea is important for scalability in general and will be of great interest to the coreset community. \n2) The paper is overall well written and appears sound. \n3) Experiments are done on variety of real datasets with different dimensionalities.", "weaknesses": "1. The paper only gives results for 1-median. Not clear if such stable coresets can be constructed for other problems.\n2. The presentation of the experimental section appears slightly rushed and can be improved. For. e.g., using Uppercase for first character in title of experiment,", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "80blqmwU7Y", "reviewer": "Reviewer_thES", "summary": "The paper introduces a new variant of coreset, stable coresets, that has guarantees positioned between strong and weak which are known in literature. The work proposes instead of preserving cost for particular centers, we can preserve the relative ordering (in terms of costs) of the centers. The authors then show that for this type guarantee, uniform sampling can be used to construct a stable coreset, specifically, for the 1-median problem in $\\ell^d_1$ a uniform sample of $O(\\varepsilon^{-2}\\log{d})$ samples is a stable coreset. They further characterize the requirement of $C-$dispersed instances, under which uniform sampling actually produces strong coresets. Experiments are provided showing the performances match coresets constructed using importance sampling.", "questions": "Could the authors elaborate on the structural assumptions where extensions to $k$-median is possible and how sample complexity would compare w.r.t. weak coresets?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and the proofs are correct to the best of my knowledge. The formalization of stable coresets is novel. The reason notion of stable coresets is useful is because the guarantees transfer to any isometrically embedded metric. This directly provides coresets (through uniform sampling) for metrics that can be embedded into $\\ell_1$, the ones highlighted in this work are Jaccard and Kendall-Tau.\nThe characterization of $C-$dispersed instance is also nice, and may help explain the effectiveness of uniform sampling in practice.", "weaknesses": "To obtain the stable coreset guarantee for uniform sample, the authors first introduce the notion of relative cost difference approximation (RCDA) and argue that uniform sample of size logarithmic in VC-dimension gives a set that provides the RCDA guarantee, which is then used to prove the stable coreset guarantee.\nThe authors discuss how to use stable coreset for $k-$median but better results are already known in the literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QRPn2GFpdr", "reviewer": "Reviewer_RJA3", "summary": "The paper introduces the concept of stable coresets, which is meant to be an intermediate notion between weak and strong coresets. It is then shown that random sampling suffices to obtain a stable coreset for the 1-media problem in \\ell_1 distance and in metrics that can be embedded in \\ell_1. The significance of the result is that a stable coresets is a simpler proxy to strong coresets.", "questions": "I do not have specific questions. I think that this is a good paper making a solid contribution in the topic of coresets. My only concern is whether having results only for 1-median is somewhat limited.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "S1. A new notion of coresets is introduced, which interpolates between strong and weak coresets. Stable coresets captures some of the properties of strong coresets while being easy to compute via random sampling. The paper may bring some new ideas and may inspire stable coresets construction for other settings, beyond 1-median.\nS2. The paper provides a rigorous analysis.\nS3. Presentation is quite good, by giving insights and explaining the main contributions and results, while the proofs are given in the appendix.\nS4. Improvement over state-of-the-art is quite good, where previous method gives similar error but requires examining the while dataset, while the proposed method requires only constant time per sample.", "weaknesses": "W1. Focusing on the simple problem of 1-median limits the practical applicability of the idea. I have the impression that the paper is a better fit for a venue in theoretical computer science.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6EfppMZ9Gh", "reviewer": "Reviewer_sxjp", "summary": "In this paper, the authors propose an intermediate notion between strong coresets and weak coresets, which they call *stable coresets*. Roughly, stable coresets preserve the relative order of the costs across different centers: this is weaker than strong coresets, which preserve the cost of every center, and stronger than weak coresets, which only ensure that an optimal solution for the coreset is near-optimal for the original dataset, without necessarily preserving pairwise orders or cost values.\n\nImportantly, stable coresets (1) can be easier to construct than strong coresets and (2) inherit a useful property of strong coresets: if a metric space admits a strong coreset, then every submetric also admits a strong coreset, i.e., coreset results for one metric space $\\mathcal{X}$ extend to every metric that can be embedded isometrically in $\\mathcal{X}$. This allows one to indirectly construct coresets for metrics that are embeddable into \"easier\" metrics, even if their direct coreset analysis is complicated.\n\nThe authors give a general recipe for proving stable coresets by showing a uniform bound on the cost difference for all centers (which they call an \"$\\epsilon$-relative cost-difference approximation (RCDA)\".) They then instantiate this by showing that a uniform sample of size $O(\\log d / \\epsilon^2)$ yields a stable coreset for 1-median in $\\mathbb{R}^d$ under the $\\ell_1$ metric with constant probability. Since many metrics (e.g., Kendall-tau, Jaccard, tree metrics, and $\\ell_2$) embed (nearly) isometrically into $\\ell_1$​, they leverage the property of stable coresets to derive coreset constructions for those metrics. In addition, they show applications to fair clustering and to approximation algorithms for k-median in these metric spaces, and provide experimental results demonstrating the performance of stable coresets in practice (in terms of both construction time and approximation quality).", "questions": "Syntactically, the idea of partitioning the range of a coordinate into three different sets and intervals in the main technical proof (Lemma 4.6) appears a bit similar to the proof strategy in [Danos, 2021] (e.g., their proof of Lemma 2.2.6) Was this inspired by that work?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "I like the formulation of stable coresets, especially how it naturally aligns with embeddability between metrics. (While a similar comparative guarantee for coresets appeared previously in [Indyk 1999, 2001], it was presented more as an algorithmic primitive rather than as a standalone definition. I therefore regard the stable-coreset formulation as novel.) The paper already demonstrates the usefulness of this formulation by constructing the first coresets based on uniform sampling for important metric spaces, including Kendall–tau and Jaccard, as well as new bounds for $\\ell_2$. And one can imagine that such a \"coreset-via-embedding\" recipe will lead to further coreset results.\n\n\nThe paper is well written with a nice logical flow: (1) The motivation and goal are clear. (2) In the main body, the paper presents a general framework followed by a concrete instantiation. While the ideas are easy to follow, the proof of $\\epsilon$-RCDA for $\\ell_1$ via $\\epsilon$-approximations is neat and non-trivial.", "weaknesses": "Although stable coresets provide a stronger guarantee than weak coresets (and, as mentioned above, I find the guarantee aesthetically interesting in its own right), at this point the main gain seems to be that given a near-isometric embedding, one can translate a coreset in the “host space” to a coreset in the “guest space.” From this perspective, a stable coreset does not offer additional advantage over a weak coreset *within the original host space* ($\\ell_1$ in this paper), while the required coreset size given shown in this paper is larger compared to the known $\\tilde{O}(1/\\epsilon^2)$ size of weak coresets in $\\ell_1$.\n\n-----------------------------------------\n\nSome editorial notes: \n\n- Fact 2.2 (b) for every $c \\in P$: I think you need for every $c \\in \\mathcal{X}_1$ to show the later Proposition 2.3?\n\n- I'm not sure why it is necessary to include a proof to Proposition 4.2, given that the proposition already appears in (Gey, 2018)?\n\n- In Theorem 4.4 it might be clearer to say explicitly that the random sample $Q \\sim \\mathcal{D}$.\n\n- Equation 8 and 9: $edf_{p} \\rightarrow edf_{P}$ \n\n- Line 811 \"$-2\\epsilon \\leq a_i \\leq 2\\epsilon$\": I suggest replacing this with just the summation bound \"$-2\\epsilon \\leq \\sum^{j_2}_{i=j_1}a_i \\leq 2\\epsilon$ for every $j_2 \\geq j_1$\" on Line 837, since the former is not used and is subsumed by the latter.\n\n- Line 823 and onwards: Is $p_i$ ever defined? One can infer it is the boundary of the ith interval, but since it is the key object in the telescoping, I think it should be defined explicitly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V1wwuxRYl9", "reviewer": "Reviewer_DWK3", "summary": "The paper introduces a new notion of coresets for the 1-median problem, termed stable coresets, whose power lies between that of strong and weak coresets. They construct a stable coreset of size $O(\\log d / \\epsilon^2)$ for the 1-median problem in the $\\ell_1$ metric. Using standard embedding results, they extend these constructions to other metrics such as the Jaccard, Kendall-Tau, and Euclidean metrics. By combining their coresets with existing algorithms, they obtain approximation schemes in the corresponding metric spaces whose running times are FPT in $k$, $\\epsilon$ and the coreset size. Finally, they present experimental results evaluating their constructions and comparing them with existing ones.\n\nThe main construction is based on a simple procedure that produces a uniform sample of size $O(\\log d / \\epsilon^2)$. The proof appears to rely on several existing results combined in sequence. The key motivation for using uniform sampling in constructing stable coresets is its running time---uniform sampling can be performed in sublinear time, in contrast to existing approaches for strong coresets, which examine all points in the input.", "questions": "1. How is designing stable coresets in sublinear time useful? For example, weak coresets can already be constructed in sublinear time. In that case, how does the additional power of stable coresets over weak coresets translate into any practical advantage?\n\n2. In Theorem 5.5, you mention that it gives an approximation scheme for $k$-median in the $\\ell_1$ metric with running time $f(s,\\epsilon) \\cdot (s k / \\epsilon)^{O(ks)} \\cdot n$, for a stable coreset of size $s$. How does this yield an EPAS (FPT in $k$ and $\\epsilon$) for $k$-median in the $\\ell_1$ metric? You mention that existing strong coresets can yield EPASes, but I do not see how the running time of your approach can be made independent of the dimension $d$.\n\n3. You mention potential applications of stable coresets in fair clustering, but I do not see any technical results related to fair clustering in the paper.\n\n4. Regarding Theorem 5.5: does this result come directly from prior literature? It refers to stable coresets, which is one of the contributions of this paper.\n\n5. I am curious if it is possible to extend the notion of stable coresets to the $k$-median problem?\n\n6. Concerning the proof of Proposition 2.1(a), I am unable to follow the argument, particularly the inequality in line 656. Could you please clarify this step?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The newly proposed notion of coresets: stable coresets, lies between weak and strong coresets in terms of power, which makes it appealing both theoretically and practically.\n2. The construction is quite simple: a uniform sample of an appropriate size suffices to obtain a stable coreset.", "weaknesses": "1. The paper motivates the design of coresets in sublinear time and shows that uniform sampling yields a stable coreset for the 1-median problem in the $\\ell_1$ metric. However, it is not clear what stable coresets are useful for beyond designing EPASes—where the sublinear-time motivation is largely lost. For example, why should stable coresets be preferred over weak coresets when aiming for sublinear running time? Furthermore, even if a stable coreset can be obtained in sublinear time, it is unclear how to evaluate the cost of centers on the original dataset in sublinear time.\n\n2. A major weakness, in my view, is the technical writing. It is difficult to identify the key technical challenges and the insights that make the results work. This issue is becomes worse due to the fact that only one proof appears in the main paper, while all others—including one of the main theorems (Theorem 3.1)—are deferred to the appendix. While I understand the page constraints, it is important to at least sketch the proofs or highlight the main ideas behind the crucial technical statements. I also went through the proofs in the appendix, but they too fail to convey the underlying intuition. Moreover, the technical overview section does not highlight any novel contributions. Without this, it is difficult to assess the technical depth of the paper. \n\n3. Related to point #2, the proof of Theorem 1.4 (one of the main results) seems to follow directly from existing results. It appears that this theorem is derived primarily by chaining together prior work. While this is not inherently bad, it gives the impression that the paper is mainly a collection of observations rather than a technically deep contribution, which weakens its case for a venue like ICLR.\n\n4. Strong and weak coresets of size independent of the dimension are already known, whereas the coreset construction in this paper depends logarithmically on the dimension.\n\n5. The proposed coreset result appears to apply only to the 1-median problem. However, most existing coreset results in specific metric spaces are designed to handle the more general $k$-median case.\n\n6. As an application, the paper shows how to obtain approximation scheme for $k$-median in the $\\ell_1$ metric using existing frameworks. However, the authors themselves suggest that such algorithms already exist, so it is unclear what new insight or contribution this application provides.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)