Relative Error Fair Clustering in the Weak-Strong Oracle Model
Authors: Vladimir Braverman
Prathamesh Dharangutte
Shaofeng H.-C. Jiang
Hoai-An Nguyen
Chen Wang
Yubo Zhang
Samson Zhou
Venue: ICML 2025 poster (2025)
Keywords: clustering
weak-strong oracle model
fairness
Primary area: social_aspects->fairness
TL;DR: We give the first $(1+\varepsilon)$-coreset for fair $k$-median in the weak-strong oracle model.

Abstract: We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak oracle providing potentially inaccurate distance estimates at a low cost. The goal is to produce a near-optimal fair clustering on $n$ input points with a minimum number of strong oracle queries. This models the increasingly common trade-off between accurate but expensive similarity measures (e.g., large-scale embeddings) and cheaper but inaccurate alternatives. The study of fair clustering in the model is motivated by the important quest of achieving fairness with the presence of inaccurate information. We achieve the first $(1+\varepsilon)$-coresets for fair $k$-median clustering using $\text{poly}\left(\frac{k}{\varepsilon}\cdot\log n\right)$ queries to the strong oracle. Furthermore, our results imply coresets for the standard setting (without fairness constraints), and we could in fact obtain $(1+\varepsilon)$-coresets for $(k,z)$-clustering for general $z=O(1)$ with a similar number of strong oracle queries. In contrast, previous results achieved a constant-factor $(>10)$ approximation for the standard $k$-clustering problems, and no previous work considered the fair $k$-median clustering problem.

Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman'
Prathamesh Dharangutte 2 Shaofeng H.-C. Jiang Hoai-An Nguyen Yubo Zhang²
Chen Wang
Samson Zhou
Abstract
1 Introduction
Clustering is cornerstone of unsupervised learning and fundamental technique for data science, often used to identify latent structure in high-dimensional and large-scale datasets, thus serving as an essential pre-processing step in numerous downstream applications, facilitating dimen- sionality reduction, feature learning, and data summariza- tion. Informally. the objective of clustering is to partition dataset into k clusters such that intra-cluster similarity is maximized while inter-cluster similarity is minimized. Traditional clustering formulations, such the k-median and k-means problems, have been the focus of extensive study since their inception in the 1950s (Steinhaus et al., 1956; MacQueen, 1967). Formally, in the k-median clus- tering problem, the input is a set X' of n points in a space with metric d, and the goal is to minimize the quantity ming;|cls* ΣzEx mineec d(z,c).
We study fair clustering problems in setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak oracle providing potentially inaccurate distance estimates at low cost. The goal is to produce near-optimal fair clustering on n input points with minimum number of strong oracle queries. This models the increasingly common trade-off between ac- curate but expensive similarity measures (e.g.. large-scale emheddings) and cheaper but inac- curate alternatives. The study of fair cluster- ing the model is motivated by the important quest of achieving fairness with the presence of inaccurate information. We achieve the first (1 -ccoreesssssss for fair k-median clustering using poly & logg n) queries to the strong oracle. Fur- thermore, our results imply coresets for the stan- dard setting (without fairness constraints), and we could fact obtain (1 + -o-cosessss for (k, z)- clustering for general = O(1) with a similar number of strong oracle queries. In contrast, pre- vious results achieved a constant-factor (> 10) approximation for the standard k-clustering prob- lems, and no previous work considered the fair k-median clustering problem.
Fair clustering. Observe that the set of centers C' inher- ently divides X' into clusters by assigning each point x E X to its closest center c E C. Due to this implicit partition- ing rule, standard notions of clustering may produce bi- ased results, leading potentially discriminatory outcomes that perpetuate social inequalities in downstream applica- tions (Dwork et al., 2012; Chhabra et al., 2021). For in- stance, clustering algorithms used for hiring or lending may unintentionally discriminate against certain demographic groups, e.g., race, gender, religion, or socioeconomic status. Such biases are particularly concerning in high-stakes do- mains like healthcare, education, and finance, where data science algorithms making process. To address these challenges, there has been a growing body of research focused on incorporat- ing fairness constraints Ahmadian et al. (2020b;a); Song et al. (2024); Chen et al. (2025), especially into clustering algorithms to ensure equitable outcomes.
The authors are listed in alphahetical order. 'Google Research 'Department of Computer Science, Rutgers University 'School of Computer Science, Peking University 'Computer Science Department, Carnegie Mellon University 'Department of Computer Science, Rice University Department of Computer Science & Engincering, Texas A&M University. Correspon- dence to: Vladimir Braverman <vbraverman @ google.com>> Prathamesh
strongly influential in the decision-
Dharangutte
<ptd39 @ rutgers.edu'>, Hoai- Chen Wang
Shaofeng Jiang <shaofeng, jiang @ Berep@puueeee l.pu..duucnn>.
One such constraint disparate impact, which requires all "protected" subpopulations to receive similar representation in the decision process. To that end, Chierichetti et al. (2017b) introduced (a, fair clustering, where each point x E is associated with one or more subpopulation (or group) j E [C]. across total groups Since the groups could overlap, we let A be the maximum number of disjoint
An Nguyen <hunguyen @ wundeew.cmu.edu. <ehen.wang, www.:/awwg...ereeeoeeeee research gom,, Samson Zhou <sam- sonzhou @ comm.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Relative Error Fair Clustering
groups each x E X' could belong to. The fairness constraints specified by parameters 0 aj S 83 S 1 for each group j. so that the objective is to minimize the clustering cost while ensuring that each cluster has at least an aj fraction and at most a 33 fraction of points from group j- These constraints are designed to prevent subpopulations from being under-represented or over-represented within any cluster, thereby promoting fair and balanced cluster assignments.
points. We assume that the metric d is not directly accessi- ble to the algorithm. In the weak-strong oracle model, we are given two oracles: the weak oracle WO and the strong oracle SO. The properties of the oracles are prescribed as follows.
Weak oracle WO: given a pair of points (a, y) X x X, the query WO y) returns the distance d y) exactly with probability 2/3. With probability 1 1/3, WO y) returns an arbitrary answer. The randomness is drawn exactly once.
Weak-strong oracle model. Up to this point, all formula- tions of clustering discussed assume that the ground-truth similarity measure between each pair of points is given as part of the input, either through implicitly through an under- lying metric explicitly through either oracle access similarity matrix. Recent advancements in modern machine learning have highlighted the importance of large-scale sim- ilarity models, particularly in applications involving non- metric data such as images, text, and videos. These models use embedding functions (Van der Maaten & Hinton, 2008:
Strong oracle SO on points: given a pair of points (a, 1) E X x X. if both SO(r)) and SO(y) are queried, then the value of d(z, y) is (deterministically) re- vealed.
Strong oracle SO on distances: given pair of points (x, E X x X, the answer to the query SO(rr,0 v) (deterministicallyy) reveals d(z,y) y).
Mikolov et al., 2013: He et al.. 2016; Devlin et al., 2019) to provide mechanism to generate real-valued distances for non-metric data, so that each point is transformed into a vector (xr) such that the similarity between data points r and can be inferred from the distance (ff()), (()) in the embedding space. Thus, embedding models, such as those derived from deep learning. have become crucial in enabling downstream tasks such as clustering on non-metric input data.
In this model, the weak oracle distances represent a cost- effective but less accurate approximation of the true dis- tances, whereas the strong oracle provides significantly more precise results at higher computational cost. Con- sequently, our objective is to obtain a high-quality solution to clustering for the underlying metric (X' d), while mini- mizing the number of queries made to the expensive strong oracle. Furthermore, we allow the corruptions introduced by the weak oracle to be adversarial in nature, which captures broad class of "imprecise weak oracles", where the weak oracle may produce arbitrarily poor distance estimates with some probability. Since the randomness is drawn exactly once, we cannot hope to use repeated queries and majority tricks. We also remark that the failure probability of 1 quite flexible, e.g., it can be an upper bound on the failure probability across all oracle queries and simply needs be some constant 2.
However, these embedding models scale in complex- ity and accuracy, the computational resources required to perform pairwise similarity computations also increase sig- nificantly. This has led to the widespread adoption of hy- brid approaches that combine highly accurate but resource- intensive similarity models with more efficient, albeit less precise, secondary models (Kusner al., 2015; John al., 2020; Silwal et al., 2023; Xu et al., 2024; Galhotra et al., 2024) (see Appendix A for additional discussions). These lightweight models, often referred to as "weak" similar- ity models, rely on approximations or auxiliary informa- tion, such as simple feature-based heuristics (c.g., location, timestamps, or metadata) (John et al., 2020; Ringis et al., 2021), compact neural networks, historical similarity data (Mitzenmacher & Vassilvitskii,, 2022).
3 is
Bateni et al. (2024) achieves constant-factor approximations to (k, 2) c>-cussteiigg problems for = = O(1) in the weak- strong oracle model with Ö(k) strong point oracle queries and (122) strong distance oracle queries', They also proved that (2k)) strong point oracle queries are necessary for any bounded approximation, making their bounds tight up to polylog factors. On the other hand, the approximation factor in their algorithm is some C' > 10 for k-means and even bigger constants for general (k:, z). Due to the fact that their algorithm is an adaptation of Meyerson sketch (Meyerson, 2001b), any improvement below a certain con- stant is unlikely. Furthermore, their algorithm does not have any guarantees fairness, which could lead to potentially biased and harmful outcomes. Therefore, there is an open
To that end, Bateni et al. (2024) introduced the weak-strong oracle model, which considers space X' consisting of n = |x' points, equipped with a metric : X' x X' -> R that represents the output of an accurate but computationally expensive similarity model. Although the metric d is not directly available, can be accessed through two types of oracles: weak and strong, prescribed as follows.
Definition 1 (Weak-strown -tronn oracle model). Let (X', d) be a metric space where d is the measure of distance between
"s standard, we use Ō(-) to hide polylog (n) terms.
2

---

Relative Error Fair Clustering
question for efficient clustering algorithms with fairness constraints and (1 + appproxximmaio in the weak-strong oracle model.
subpopulation groups could have overlaps. In the case of A = 1, i.e., the subpopulations are themselves disjoint, the construction of fair clustering coreset is essentially reduced to pasignignt-preservinng coreset that specifies the required number of assignments for each cluster (see Section 2 for the formal definition). The following theorem characterizes our guarantees for the assigament-preserving (A = 1 fairness) case.
Due to hardness results for k-clustering (Guha & Khuller, 1999; Awasthi et al., 2015; Cohen-Addad & Karthik C. S., 2019; Bhattacharya et al., 2021), we cannot hope for time efficiency for (1 + -)aaproxime fair clustering. Nev- ertheless, we could still aim for efficiency on the query complexity of the strong oracle. To this end, a very helpful notion is coresets. Roughly speaking, a (k, s) coreset S of a point set X' is a weighted subset of points of the X' such that the fair k-clustering costs on S and X' are bounded by a (1 + E) factor (see Definition 3 for the formal definition). For our purpose, if we get a coreset of size 8 with a small number of strong oracle queries, we could then perform clustering as post-processing step with at most extra strong point (or s² distance) oracle queries. As such, we could ask the following motivating question: Is it possible to design fair s) coresets with query efficiency in the strong oracle model?
Theorem 2. There exists an algorithm in the weak-strong oracle model that, given a dataset X, with high proba- bility computes (koorett of size O e² for assignment-preservigg k-median clustering using O log" n) strong oracle point queries (or edge queries), Onk log" n) weak oracle queries, and Ö(n + k22/ time.
a- )
Theorem 2 also implies (k; e) coreset for standard k-median clustering (without the fairness assignment constraints). Note that due to the lower bound in Bateni et al. (2024), (2kk) strong oracle queries are necessary to obtain such coresets even for any bounded approximation and without assignment constraints. As such, our algorithm is optimal up to polylog(n) factors.
1.1 Our Contributions
We answer the motivating question in the affirmative by designing the first (1 + 5) fair k-median algorithm with poly(k (oggg//)) strong point (and distance) oracle queries and poly(k n/)) coreset size. Recall that we use A to denote the maximum number of disjoint groups a data point belongs to. The formal guarantees of the coreset algorithm can be given as follows.
One would naturally wonder whether we could similarly get =k coresets for other k-clustering problems, e.g., k- means clustering. Our second result shows that such goal is possible, and if we do not care about fairness, we could obtain (k, E) coresets for (k, 2) clustering with = = O())
Theorem 3. There exists an algorithm in the weak-strong oracle model that, with high probability, computes a (k,,) coreset of size Ö ((E) for (k, cccuuttrnn with any ((1) using Ō(E)) strong oracle point queries (or edge queries), Ö(nk) weak oracle queries, and Ö(nk + +k2/ time.
Theorem 1. There exists an algorithm in the weak-strong oracle model that, given a dataset X such that each e X belong to at most A disjoint groups, with high probability computes a (k, E) fair coreset of size Ö(A 122 for k-median clustering using Ö(A- k) strong oracle point queries (or edge queries), Õ(A nkk weak oracle queries, and Ö(A (nk- + /=2)) time.
Note that the size and query bounds for (k. clustering include 20(=) dependency, although it could be hidden as long as x = O(1). Compared to Theorem 1, the number of strong oracle queries is slightly worse, but we are able to deal with general (k: 2) objectives. We leave the quest of the optimal & dependency for (k: z) clustering coreset as an open problem to pursue in the future.
In addition to the query efficiency on the strong oracle, our algorithm in Theorem also uses the clean uniform sampling framework and enjoys a fast running time, making it suitable for practical purposes. Although getting an actual (1 + aaaproxximtaio clustering might take exponential time, we could run some approximation algorithms, e.g., the algorithms in Chierichetti et al. (2017a); Backurs et al. (2019), as the post-processing to obtain fair clustering. Prior to Theorem 1, no fair k-median coreset with non-trivial approximation guarantees or coreset size under the weak- strong oracle model was known?.
Experiments. To validate the theoretical guarantee of our algorithms, we conduct experiments on real-world datasets: the "Adult" dataset (Becker & Kohavi, 1996) and the "De- fault of Credit Card Clients" dataset (Ych, 2009). The weak oracle is designed to return very small distances if it runs into an erroneous case. We compare our algorithm against a baseline algorithm that uniformly at random samples and re- weighights points. The experiments show that the proposed algorithm in Theorem could significantly outperform the uniform baseline. We defer the experiments to Section 5.
Theorem 1 is stated in the most general form, where the
For trivial solutions, we can always, e.g., return the entire
dataset as the coreset.
3

---

Relative Error Fair Clustering
1.2
Technical overview
coreset algorithm in Section 3 for k-median, which includes the key ideas used in the algorithms. We will then discuss the fair coreset in Section 4.
Our coreset algorithms are adaptations of the ring sampling approaches used extensively in the literature (e.g.. (Chen, 2009; Braverman al., 2022)). Roughly speaking. the ring sampling approach first performs an -pppoxpproinnaooonn "weak" k-clustering algorithm with average cost R. Then, for the points assigned to each center, the algorithm divides the points according to rings with doubling distances, i.c., 2' to 2 R for the i-th ring. It has been shown in Chen (2009) that sampling (kk/=²) points from each ring leads to (e, -oooreet.
2 Preliminaries
k-clustering and coresets. We define the distance be- tween a point z E X' and a set of points S S X as d(S, x) = minses ((8, 2)) or the distance between x and the closest point in S. We define the distance between two sets Si, S2 C as ((S), S2) = min d(S,, 82). Addi- tionally, we say that the diameter of a set diam(S ( S X) = max d(s1, $2). We assume the distances are inte- gers, and the aspect ratio A = poly(n): both assumptions are common in the literature.
In the weak-strong oracle model, a significant challenge for the ring sampling approach is that we do not know the set of points in a ring. Since the weak oracle could give arbitrarily adversarial answers, we cannot assign points to rings based on the weak oracle. On the other hand, if we query the strong oracle for all points, the query complexity will be too high to afford.
Let X' be a set of n points. Every point x E X' has an associated positive integer weight w(z). Note that hav- ing an unweighted set X' is the same as all points be- ing assigned unit weight. We define the total weight of w (XX) = -Erex w(r). We denote clustering of set X' by center C = (cI.-.., c S X' as partition where each x E X' is assigned to the closest E C.
The key idea to resolve the above dilemma is by heavy- hitter sampling and recursive peeling. In particular, in each iteration, we sample k poly pol(())g)))/)) points, and we make strong oracle queries on the sample points to know their exact ring assignments. We then categorize the rings into the heavy ones, i.e., the rings with k (ooy((og(n))/ sampled points, and the light one, i.e., the rings with few samples. The key observation here is that if heavy ring lies on the outside of (possibly multiple) light rings, then with high probability, we could safely ignore the light rings since their costs are negligible compared to the cost of the outer heavy ring. Therefore, we could focus on building coresets only for the heavy rings. Furthermore, after one iteration, we could use a procedure in Bateni et al. (2024) peel off the points in the heavy ring we processed along with the light rings inside. We could then recursively process all the points with a low overhead of iterations.
Definition 2 ((k; z)ccltrter, k-means, and k-median). We denote the cost of the (k: cluusterin of point x e X using center set C as costz 2) = d'C x))(). The overall cost of the (Ie, z)cclstteiing is defined as
cost,(C,,2) = Σ costt(C,.)). JE
For = = 1, the objective is the k-median clustering; for = problem, the objective is called the k-means clustering.
Throughout, we use C* to denote the optimal clustering that minimizes the cost. We now define the notion of (k: e) coreset formally for clustering objectives.
Definition 3 ((k: -ccoesset) Given a set of points X, a weighted subset $ S X is a (k, cooreset for X' for (ks, 2)- clustering if we have
The above gives the idea of the unconstrained (e, k) -coreset. To generalize the idea to assignment- preseevving and fair coresets, we need to adapt the ideas in existing work for fair clustering (e.g., (Cohen-Addad & Li, 2019; Braverman et al., 2022)) in white-box manner. Algorithmically, we introduce an additional sampling step from the points we peel off in each iteration. If the peeled points form a ring,
|cost, cost, (C, (C,2))] S E cost,
for all C C X' satisfying |C| < k.
Fair k-clustering. We formally introduce the notions of fair clustering and susigument--resevvvvee essential for fair coresets. To this end, we first define the notion of assignment function and assignment constraints in clustering.
we could use lemmas from Cohen-Addad & Li (2019) to establish the desired results. However, the peeled points are not necessarily rings in our algorithm; and in light of this, need to open the black-box and prove the assignment- preserving properties still hold in our case, which is part of our technical contributions.
coresets that are
Definition 4 (Assignment constraints in clustering). For any fixed weighted set S C X and C C X, an assignment con- straint is a function I : C + R such that Enec [(c)- = w(S). An assignment function o S x C + R22 is said to be consistent with r, denoted as a r, if Ve C,
To gradually build up the necessary technical tools and for the ease to understand of the readers, we present the results in a reverse order. We will first discuss the unconstrained
4

---

Relative Error Fair Clustering
(S, = : axx r(c). For S S S and C1 C, the connection cost between S1 and Ci under is defined as:
Proposition 1 ((Huang et al., 2019)). Let A be an algorithm (k, E) coreset for
that constructs assigument-presevvin (k, =)-clustering X with size Furthermore, let A be the number of distinct groups each x E X could belong to. Then, the following algorithm
cost (81,C1)
Σ Σ o(z,c) . (z,c). IES1 cEC1
The notion of fair 2ccuuutnn with group faimess is defined using assignment constraints. Conceptually, fairness here means that the assignment from each group to each cluster satisfies a certain range of group disparity constraints.
Computes (k, coreset (k. clclustring for each distinct group;
Take the union of the coresets;
Definition 5. In (arair (k: =) clustering, the input dataset X' is partitioned into _1, Xm groups. The groups are not necessarily disjoint. We are further given m- dimensional vectors a, E [0, 1]"h. The goal is to find an assignment function and a set of centers C S X such that for every group X₂ and center c C, there is
is an algorithm for (o,,3) (k,e) coreset for (k, z)- clustering.
Proposition implies the following lemma for the fair core- set in the weak-strong oracle model.
Lemma 2.1. For a given dataset X. let A be the number of distinct groups each x E X could belong to. An algorithm that constructs an assignment-preservin (k,é) coreset for (k, =.clsttttii with size 81, 82 strong oracle queries, 83 weak oracle queries, and time implies an algorithm for (k, E) fair coreset for (k,2)) z)-ccstteiing with size O(A s1),
- (lg, c)
c) I Br.
Assignment-peeservigg clustering and fair k-clustering. Next, we define (As, cclusteing with assignment straints, which, roughly speaking, specifies the "amount" of assignment each center could get. We will see shortly that their is a strong relationship between clustering with assignment constraints and fair clustering.
O(A 82) strong oracle queries, O(A 883) weak oracle queries, and time O(A
Weak-strong oracle primitives. We now discuss some primitive algorithms in the weak-strong oracle model. We first give one-way reduction from SO on distances to SO on points.
Definition 6 (k, z)- Clustering with assignment constraints). Given weighted dataset S X, center set C C X' with [C| < k and an assignment constraint r : C - R20 the objective for (k, =)Clusttrrinn with assignment constraint I is defined as:
Observation 1. Given a set of points (X, d) in metric space d and any fixed function f(X, d). if there exists an al- gorithm that computes f(X, d) with 9 strong oracle queries on points, then there exists an algorithm that computes f(X, d) with O(q²) strong oracle queries on distances.
min cost, (S,C))) x:SxC=R _
cost (S.
The next notion introduces the assignment--reseevving (k, coresets. It is in the same spirit of (k, correset as in Defi- nition 3 but with (Assignment-ppeeeevvi))
Note that the other way of reduction (points to distance) does not necessarily hold as in Observation 1. Therefore, to a quadratic blow-up, our primary focus is the point queries for the strong oracle SO².
properties.
coresets for (ks, 2) -luusterin) Let X' be (potentially weighted) dataset. A weighted subset S C X' is assignment-preservin (k,, corrsett for (ks, =)-clsstering if w(X) w(S). and for every C C X' with [C] < k and assignment constraint C:C- + IR20
Definition
Next, we give some existing results from Bateni et al. (2024) on which we build our algorithms. The first technical tool from Bateni al. (2024) is an algorithm to construct weak coresels.
Coost,(,,C,)) - cost, (,C,C,) < cost,
Proposition 2 ((Bateni et al., 2024), Theorem 8). There exists an algorithm that given a set of points X such that |X| n, returns an O(1) -appapppoeee solution to the opti- mal (k, z)-clustering for assignment of each point using O(k log? n) strong oracle queries and O(nk log n)) weak oracle queries.
Note that the actual assignment function a that attains cost, (X,C, and of that attains cost, C, r) could be different as they may have different input spaces to begin with.
O(1) X' together with the
There a strong relationship between assignment- preserving coresets and fair coresets. In particular, we have the following established result.
'That being said, coreset algorithms actually enjoy the same asymptotic query efficiency for strong point and distance oracles due to algorithm design.
5

---

Relative Error Fair Clustering
Next, we give distance estimator that is helpful for using weak oracle queries to compute approximate distances.
coreset of size Ö (3) for k-median clustering using Ō K3) strong oracle point queries (or edge queries), ((nk) weak oracle queries, and (nk) time.
Proposition 3 ((Bateni et al., 2024), Lemma 6). Let S be set of points such that |S| Z 10 log n, and suppose that strong oracle queries have been made on all points s E S. Furthermore, let Rg be the diameter of S. Then, there exists an algorithm that given for any x E X and & E S, uses (1) weak orucle queries and returns a estimated distance d(r, S) such that
The algorithm. The main idea of our algorithm is based the heavy-hitter sampling and recursive peeling. Roughly speaking, our algorithm first conducts uniform sampling for the points assigned to a center in the Oappapppronnnation The algorithm then makes strong oracle queries on these points (or strong distance oracle queries between these points and the center) to determine the rings for the sampled point. Crucially, this allows us to identify the heavy-hitter ring that accounts for significant portion of the cost. As such, it suffices to only construct coresets for these heavy- hitter rings, and we indeed would have enough samples from such rings. At this point, we would argue that there is a collection of rings whose points are either added to the coreset or their costs are insignificant enough so that they could be ignored. We will then "peel" these points from the point set and recurse the remaining set. The detailed description of the algorithm is as follows.
d(x, 8) S d(z, S) S d(x,)) Co Rs,
where Co S 5 is a universal constant.
Ring sampling primitives We use the idea of uniform sampling from rings in the same manner of Chen (2009); Braverman et al. (2022). In what follows, we introduce the following definition for ring sampling to introduce our algorithm.
Definition 8. Let X)) S BUOPT denote the clustering v(A.X) cost and let R = 3m be the lower bound on average radius of optimal clustering. Let P. be the set of points
E X' assigned to 6 and let Pú,- = P. [BC,, (2C.)' R) B(q, (2Co)* R)] for j 2 1 and Pt, P. n B(G, R) for j = 0. As a result, we have l8g(3n) rings around each 6 E C and x E X C is part of exactly one ring.
Algorithm 1. The construction algorithm for (1 + 8) coreset
(1) Run the algorithm of Proposition 2 to get the weak approximate clustering WC.
Note that compared to the standard ring sampling-base based algorithms like Chen (2009), our algorithm uses search with Co multiplication. This ensures whenever point is placed in the wrong ring, it could only end up in the next ring.
(2) Initialize all rings P.. as "not processed".
(3) Initialize the strong coreset SC <- 0.
(4) For each center c; of WC:
The aspect ratio and the number of rings. Since the rings are defined by multiplicative factor of Co > 1, for instances with an aspect ratio A, for each center e; of the ((1) approxxpxonnnationn solution, there is at most Ologg,, (A)) rings. It is common to assume the aspect ratio A = poly(n); (n); for the clarity of presentation, we assume there are exactly log n rings in this paper. Any change within the regime of polynomial aspect ratio will only result in constant factor difference in the coreset size.
(a) For each ring Ptj. let Si be some samples from
the ring specified later.
(b) Initialize P3 + P; as the remaining number of points.
(c) For 1 10 log² n iterations:
i. Sample 8, 100C, Alog n points uniformly at g
random from P.. and let the sample set be S,.
ii
Make strong oracle SO queries as follows:
3 A (1 + + for k-median Clustering
For point SO queries, query SO(z) for all points x E S,.
In this section, give our algorithm that produces (1+ coreset (without fairness constraints) for (k:, = =lcuusttgi with Ō(k2 ((k2/e²) points and strong oracle SO queries. We first remind the readers of the guarantees in our theorem. For ease of presentation, we focus on the kt-median case for the analysis, and defer the full proof of (k, =)-clustering to Appendix D. The theorem we aim to prove in this section is as follows.
For distance SO queries, query SO(x, c,) for all points x E S,
ii. Ring assignment: For each point x E S,, add x to Si,, where j is the index of the ring to which x belong.
iv. Find the ring j with the largest index such that |St > 80C, k klog2 n
For each ring é with index e 5 (j* + 1) and k being "not processed"::
Theorem 4. There exists an algorithm in the weak-strong oracle model that, with high probability, computes (k, e)
6

---

Relative Error Fair Clustering
If [St,e] 2 30 Alog run CORESET-UPDATE
(2) Let T.(e) be the set of points such that d(x, Speel (2C,) R.
(Algorithm 2) with inputs S and SC to obtain
an updated SC.
(3) Remove all points in T. from P. ie., P, P. T
vi. Conduct the peeling step based as follows.
If j * O, run PEELING (Algorithm 3) with { and P,.
Otherwise (if) 0):
о If more than [.,ol points has distance at most R/2Co to c; then run CONSERVATIVE- PEELING (Algorithm 4) with Si,0 and P,. Otherwise, run PEELING (Algorithm 3) with {Sto) and P.-
2
Algorithm CONSERVATIVE-PEEELING An algo-
rithm that removes points.
Inputs: Sampled sets (Si,); the current set of surviv- ing points P;
vii. Mark rings as "processed" with the following rule:
Output: An updated set surviving points P:
If CONSERVATIVE-PEELLA (Algorithm 4) is executed (which implies j" 0), mark points in
(1) For each point E P; run the algorithm of Propo- sition 3 with the set Speel as an arbitrary subset of 10 n points in the subset of S.o U {c
Ps.o as "processed".
Otherwise, mark all the points in rings P..e for
(2) Let T((e) be the set of points such that d(æ, Speel < R.
& S +1 as "processed".
(3) Remove all points in T,(7) from P, ie., P,+ T(
Algorithm 2 (COREsET-UPDATT), An algorithm that adds points to coreset.
Inputs: A sampled point set S,G set of existing coreset SC
Due space limits, we only prove the query efficiency and coreset size, and defer the correctness proof to Appendix B.
The analysis.
Output: An updated set of coreset SC
(1) Arbitrarily split the set of sampled points St, to
Lemma 3.1. Algorithm I uses at most k2 log" SO point (or distance) queries and most Onk log n) weak oracle queries. The algorithm converges in Ō(k + - time.
Stat with 1/3 of the points in Si,i sweight with 2/3 of the points in S.,.
3.P.
(2) Let ma,e
Sest be the estimated number of
points in Pr.j-
Proof. By Proposition 2, the number of strong oracle queries required get WC O(k log² n) strong point SO queries O log* n) strong distance queries. In addition, for each center for O(log² n. iterations, the algorithm sam- ples O(k log" n//=²) points and makes strong oracle queries on all of then (or the queries between them and the center c;). Since there are at most i centers in WC, the number of strong oracle queries here is O log n/e")).
(3) Re-weighting: add each point St, e to the coresct
SC with weight mis [..l"
Algorithm 3 (PEELING). An algorithm that removes points.
Inputs: Sampled sets 1 where j" is obtained from line 4(c)iv; the current set of surviving points P. Output: An updated set of surviving points P.
For the number of weak oracle queries, the WC requires Onk log" n) weak oracle queries. Furthermore, each point makes at most Ollog n) queries during one iteration of line 4c in Algorithm 1, There are at most k centers, and each center induces Olog? n)) iteration, which lead to total of Onk log n) weak oracle queries. Finally, the time effi- ciency scales with the total number of weak and strong ora- cle queries, which leads the desired lemma statement.
(1) For each point P;, run the algorithm of Propo- sition with the set gpeel as arbitrary subset of 10 log points in the subset of Sts U {c.).

---

Relative Error Fair Clustering
4 Fair Coresets for + (1+2)-pprooximttio k-median Clustering
Note that in terms of the pseudo-codes, Algorithm 5 is simpler than Algorithm since we do not have handle the charging of rings explicitly with the labels of "being processed". We will handle the argument associated with that part in the analysis.
In this section, we show how to construct fair coresets that preserve the k-means and k-median costs by (1 + s) factor. Limited by the space, we only show the algorithm as in Algorithm 5. We defer the analysis to Appendix C.
Algorithm samples uniformly at random from all the peeled points form coresets (not only the heavy rings). Intuitively, sampling from the entire set of points is neces- sary obtain assignment preserrinn coresets. The actual analysis of the algorithm is considerably more involved. The main roadblock here is that almost all existing algo- rithms for peiignment-preserving coresets only work with rings (e.g., (Cohen-Addad & Li, 2019; Braverman et al., 2022)), but in our case, we need to work with sets of points that could span multiple rings. This requires us open the blackbox in (Cohen-Addad & Li, 2019) and re- re-prove the guarantees for assignment preservation and approximation using the properties of the heavy rings.
Algorithm 5. The construction algorithm for (1 + E) coreset
(1) Run the algorithm of Proposition 2 to get the weak approximate clustering WC.
(2) Initialize all rings Pej as "nol processed".
(3) Initialize the fair coreset FC <- 0.
(4) For each center 6; of WC:
(a) For each ring Pi.j. let Sk,j be some samples from the ring specified later.
In Appendix D, we give a (1 + co-ceeet for general (k; 2)- clustering (without fairness constraints). We remark that the algorithmic approach of sampling and peeling from heavy rings with smaller indices first (therefore not ignoring "low-cost" regions similar to Algorithm 5) appears to be applicable to general (k, =)-cutrerin as well. Furthermore, we believe that this could lead to improvements in the depen- dence on l: in the coreset size as well as the number of weak and strong oracle queries. This would require a white-box adaptation of Chen (2009) to work with the non-ring set of points as in line 4(c)vC, and we leave it as an interesting future problem to explore.
(b) Initialize P; <- P; as the remaining number of points.
(c) For : 10 n iterations:
i. Sample 8, 1000Co log" n points uniformly random from P., and let the sample set be S,.
ii
Make strong oracle SO queries as follows.
For point SO queries, query (O(x) for all points E S,.
For distance SO queries, query SO(x, (z, c:) for all points S...
iii. Ring assignment: For each point Sy, add to St.j. where j is the index of the ring to which belong.
5 Experiments
iv. Find the ring.j" jr with the smallest index such that
We implement and evaluate our algorithm two real-world datasets for fair k-median. We use "Adult" which has about 50, 000 instances and 8 features (Becker & Kohavi, 1996). The second dataset is "Default of Credit Card Clients" with about 30, 000 instances and 9 features (Yeh, 2009). For both we make the sensitive attribute gender.
[St..| 2 llog
1 = Sy.
V. Conduct the sampling and peeling step as fol-
lows.
A. For each point E P. run the algorithm of Proposition 3 with the set speel <- -/ S j {c:).
All experiments were run locally on Macbook Air. The code can be found here. In both datasets, we first turn each instance into an equivalent numerical representation. Due to computational limits, we first subsampled the dataset to size roughly 2000 using Meyerson sampling (Meyerson, 2001a). Meyerson sampling goes as follows. Start with empty set S. Then go through the points in the dataset one by one. Add the first point to S. Now for each successive point, add it to S with probability proportional to how far away it is from S. Here we define distance the euclidean distance. If the point is further away, the probability of it being added to S is higher.
B. Let T,(+) be the set of points such that Speel) < (2C,)"' R. C. Sampling: sample set FC(T!") of m O(ke- log2 n log(ne-))) points from T
uniformly at random with replacement, and weight each sampled points by (((") /m.
D. Add the points in FC(T(1)) with the weights to the coreset FC.
E. Peeling: remove all points in T.T)) from P, i.e.,
P. - P. (t).
We use Meyerson sampling instead of uniform sampling
8

---

Relative Error Fair Clustering
Adult dataset
Credit dataset
0.6
0.25
Relative Cost
0.4
Relative Cos
0.20
Fair Coreset
0.3
Uniferm
0.15
0.10
0.1
0.05
Fair Coreset Uniform
9
10
Number clusters
Number of clusters (k)
(a) Adult dataset
(b) Credit dataset
Figure I. Relative cost of fair h median clustering on real world datasets for different values of &
to better preserve the underlying structure of the original dataset. Uniform sampling may entirely miss smaller clus- ters of points, but Meyerson sampling is more likely to capture them.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
After subsampling the original dataset using Meyerson sam- pling to a smaller dataset, we ran our fair coreset algorithm on this smaller dataset to create coreset of size 100. We also made uniform coreset as baseline which simply uniformly selected 100 points.
References
Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pp. 267- 275, 2019.
Evaluation To evaluate the coresets, we use the fairtree algorithm (Backurs et al., 2019), which uniform and our coreset. We also run the fairtree algorithm on the dataset and report the relative cost, i.e. cost reported on dataset minus the cost reported on coreset scaled by the cost on dataset. For all experiments we use the values of balance parameters p- = 1 and y = 10 (refer to Backurs et al. (2019) for more details) and we report the cost averaged over 10 independent runs. As can be seen in Figure 1, our coreset consistently outperforms for all datasets across all values of k. Moreover, this is achieved by using only about 200 SO queries which forms only 10% of the data. We note that for larger datasets we expect the number of SO queries to be a smaller percentage of the size of the dataset.
top of the
Ahmadian, S., Epasto, A., Knittel, M., Kumar, R., Mahdian, M., Moseley, B., Pham, P., Vassilvitskii, S., and Wang, Y. Fair hierarchical clustering, In Advances in Neural In- formation Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS, 2020a.
Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M. Fair correlation clustering. In The 23rd International Confer- ence Artificial Intelligence and Statisties, AISTATS, pp. 4195 2020b.
Acknowledgements
Anegg, G., Angelidakis, H., Kurpisz, A.. and Zenklusen, R. A technique for obtaining true approximations for k-center with covering constraints. Math. Program., 192 (1):3 27, 2022.
We thank anonymous ICML reviewers for the insightful comments and suggestions. Samson Zhou was supported in part by NSF CCF-2335411. Hoai-An Nguyen was sup- ported in part by an NSF GRFP fellowship grant number DGF2140039, NSF CAREER Award CCF-2330255, Office of Naval Research award number N0001421 and Si- mons Investigator Award. Prathamesh Dharangutte was sup- ported in part by NSF IIS 2229876, DMS-222022 DMS- 231 1064, CCF-2208663, and CCF-2118953.
Angelidakis, H., Kurpisz, A., Sering, L., and Zenklusen, R. Fair and fast k-center clustering for data summarization. In International Conference on Machine Learning, ICML, pp. 669-702, 2022.
Arthur, D. and Vassilvitskii, S. k-means++: the advantages of careful seeding. Bansal, N., Pruhs, K., and Stein,

---

Relative Error Fair Clustering
C. (eds.), Proceedings of the Eighteenth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA, pp- 1027-1035, 2007.
Braverman, V., Ergun, J. C., Wang, C., and Zhou, S. deaming-augmented hierarchical clustering. In Proceed- ings of the 42nd International Conference Machine Learning, ICML, 2025.
Awasthi, P.. Charikar, M., Krishnaswamy, R., and Sinop, A. K. The hardness of approximation of euclidean k- means. In 31st International Symposium on Computa- tional Geometry, SoCG, pp. 754-767, 2015.
C. C. K., Lee, E., Rabani, Y., Schwiegelshohn, C., and Zhou, S. On approximability of & min-sum clustering. CoRR, abs/2412.03332, 2024.
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., and Wagner, T. Scalable fair clustering, In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 405440545 2019.
Charikar, M., Guha, S., Tardos, É., and Shmoys, D. B. A constant-factor approximation algorithm for the k-median problem (extended abstract). In Proceedings of the Thirty- First Annual ACM Symposium on Theory of Computing. pp. 1-10, 1999.
Bandyapadhyay, S., Fomin, F. V., and Simonov, K. On coresets for fair clustering in metric and euclidean spaces and their applications. J. Comput. Syst. Sci., 142:103506, 2024.
Chen, K. 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.
Chen, W., Xing, S., Zhou, S., and Crawford, V. G. Fair submodular cover. In The Thirteenth International Con- ference on Learning Representations, ICLR, 2025.
Bateni, M., Dharangutte, P., Jayaram, R., and Wang, C. Metric clustering and MST with strong and weak distance oracles. In Agrawal, S. and Roth, A. (eds.), The Thirty Seventh Annual Conference on Learning Theory, pp. 498- 550, 2024.
Chen, Ji, S., Wu, C., Xu, Y., and Yang. Y. An approxima- tion algorithm for diversity aware fair kusuppli problem. Theor. Comput. Sci., 983: 023::113000 14305, 2024.
Becker, B. and Kohavi, R. Adult. UCI Machine Learning Repository, 1996.
Chhabra, A., Masalkovaite, K., and Mohapatra, P. An overview of fairness in clustering. IEEE Access, 9: 130698-130720, 2021.
Bera, S. K., Chakrabarty, D., Flores, N., and Negahbani, M. Fair algorithms for clustering. In Advances in Neural In- formation Processing Systems 32: Annual Conference on Neurul Information Processing Systems 2019, NeurIPS, pp. 4955 19556 2019.
Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. In Guyon, I,, von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 5029-5037, 2017a
Bhattacharya, A., Goyal, D., and Jaiswal, R. Hardness of approximation for euclidean k-median. In Approxima- tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 4:1- 4:23, 2021.
Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 5029- 5037, 2017b.
Braverman, V., Jiang, S. H., Krauthgamer, R., and Wu, X. Coresets for clustering in excluded-minor graphs and be- yond. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2679-2696. SIAM, 2021.
Cohen-Addad, V. and Karthik C. S. Inapproximability of clustering in Ip metrics. In Zuckerman, D. (ed.), 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 519-539, 2019.
Braverman, V., Cohen-Addad, V., Jiang, S. H., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M. B., and Wu, X. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science,
Cohen-Addad, V. and Li, J. On the fixed perammeeee tractabil- ity of capacitated clustering. In 46th International Col- loquium on Automata, Languages, and Programming. ICALP, pp. 41:1-41:14, 2019.
FOCS, pp. 462-473, 2022.
Braverman, V., Dharangutte, P., Shah, V., and Wang, C. Scarning-augmente maximum independent set. In Approximation, Randomization, and Combinato- rial Optimization. Algorithum and Techniques, AP- PROX/RANDOM pp. 24:1-24:18, 2024.
Cohen-Addad, V., Saulpic, D., and Schwiegelshohn, C. A new coreset framework for clustering. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 169-182, ACM, 2021.
10

---

Relative Error Fair Clustering
Cohen-Addad, V., Jiang, S. H., Yang, Q. Zhang, Y., and Zhou, S. Fair clustering in the sliding window model. In The Thirteenth International Conference on Learning Representations. ICLR, 2025.
Galhotra, S., Raychaudhury, R., and Sintos, S. k-clustering with comparison and distance oracles. Proc. ACM Manag. Data, 2(5):212:1-222:22 2024.
Ghadiri, M., Samadi, S., and Vempala, S. S. Socially fair k-means clustering. In FAceT 21: 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 438- 448, 2021.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technolo- gies, NAACL-IILT, pp. 4171-4186, 2019.
Gonzalez, T. F. Clustering to minimize the maximum in- tercluster distance. Theoretical computer science, 38: 293-306, 1985.
Dong, Y., Peng. P., and Vakilian, A. Learning -ugmeentd streaming algorithms for approximating MAX-CUT. CoRR, abs/2412.09773, 2024.
Grigorescu, E., Lin, Y., Silwal, S., Song, M., and Zhou, S. aaaming-auggemetn algorithms for online linear and semidefinite programming. In Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurlPS, 2022.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel,
R. S. Fairness through awareness. In Innovations in Theoretical Computer Science, pp. 214-226. ACM, 2012.
Guha, S. and Khuller, S. Greedy strikes back: Improved facility location algorithms. J. Algorithms, 3 31(1):228- 248, 1999.
Ergun, J. C., Feng, Z., Silwal, S., Woodruff, D. P., and Zhou, SkS-means clustering. In The Tenth International Conference on Learning Representa- tions, ICLR, 2022.
S.
Guha, S., Meyerson, A., Mishra, N., Motwani, R., and O' O'Callaghan, L. Clustering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):115-522 5285 2003.
Esmaeili, S. A., Brubach, B., Tsepenekas, L., and Dick- erson, J. Probabilistic fair clustering. In Advances in Neural Information Processing Systems 33: Annual Con- ference on Neural Information Processing Systems 2020, NeurlPS, 2020.
Maar,eeled, S. and Mazumdar, S. On coresets for k-means and k-median clustering. In Proceedings of the thirty- sixth annual ACM symposium on Theory of computing (STOC 04), pp. 291-300, 2004.
Esmaeili, S. A., Brubach, B., Srinivasan, A., and Dickerson, J. Fair clustering under bounded cost. In Advances in Neural Information Processing Systems 34: Annuul Conference on Neural Information Processing Systems 2021, NeurlPS, pp. 14345-14357, 2021.
Haussler, D. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inf. Comput., 100(1):78-155) 1992.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pp. 770-778, 2016.
Feldman, D., Monemizadeh, M., and Sohler, C. A PTAS for k-means clustering based on weak coresets. In Erickson, J. (ed.), Proceedings of the 23rd ACM Symposium on Computational Geometry, pp. 11-18, 2007.
Hsu, C., Indyk. P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. In 7th Interna- tional Conference on Learning Representations, ICLR, 2019.
Forgy, W. Cluster analysis of multivariate data: efficiency versus interpretability of classifications. biometrics, 21: 768-769, 1965.
Huang, L. and Vishnoi, N. K. Coresets for clustering in eu- clidean spaces: importance sampling is nearly optimal. In Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., and Chuzhoy, J. (eds.). Proceedings of the 52nd An- nual ACM SIGACT Symposium Theory of Computing, STOC, pp. 1411-1149,, 2020.
Fu, C., Nguyen, B. G., Seo, J. H., Zesch, R. S., and Zhou, S. augmented search data structures. In The Thirteenth International Conference on Learning Repre- sentations, ICLR, 2025.
Gadekar, A., Gionis, A., and Thejaswi,
S. Fair clustering for data summarization: Improved approximation algorithms and complexity insights. In Proceedings of the ACM on Web Conference 2025, WWW, pp. 4458 4469. ACM, 2025.
Huang, L., Jiang, S. H., and Vishnoi, N. K. Coresets for clus- tering with fairness constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 7587-7598, 2019.

---

Relative Error Fair Clustering
Huang, L., Li, J., and Wu, X. On optimal coreset construc- tion for euclidean (k, 7)-clustering. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, STOC, Pp. 1594-1604, 2024.
Lloyd, S.
Least squares quantization in pem. IEEE transac- tions on information theory, 28(2):129-133 1982.
MacQueen, J. Classification and analysis of multivariate observations. In 5th Berkeley Symp. Math. Statist, Proba- bility, pp. 281-297, 1967.
Indyk, P. Sublinear time algorithms for metric space prob- lems. In Proceedings of the Thirty-First Annual ACM Symposium Theory of Computing, pp. 428-434, 1999.
Mahabadi, S. and Vakilian, A. Individual fairness for k-
clustering. In Proceedings of the 37th International Con- ference on Machine Learning, ICML, pp. 6586-6596, 2020.
Indyk, P., Vakilian, A., and Yuan, Y. Learning- bbase low- rank approximations. In Advances Neural Information Processing Systems 32: Annual Conference on Neural In- formation Processing Systems, NeurlPS, pp. 7400-7410, 2019.
Makarychev, Y. and Vakilian, A. Approximation algorithms for socially fair clustering. In Conference on Learning Theory, COLT, pp. 3246-3264, 2021.
Jia, X., Sheth, K., and Svensson, O. Fair colorful k-center clustering. Math. Program., 193(1):33,-36, 2022.
Mazumdar, A. and Saha, B. Clustering with noisy queries. Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 5788-5788870 5799,, 2017.
John, S., Gadde, A., and Adsumilli, B. Rate distortion optimization over large scale video corpus with machine learning. IEEE International Conference on Image Processing, ICIP, pp. 1286-1290, 2020.
Mettu, R. R. and Plaxton, C. G. Optimal time bounds for approximate clustering. 2013.
Jones, M., Nguyen, H. L.., and Nguyen, T. D. Fair k-centers via maximum matching. In Proceedings of the 37th In- lernational Conference on Machine Learning, ICML, pp. 4940-4949, 2020.
Meyerson, A. Online facility location. In Proceedings 42nd
IEEE Symposium on Foundations of Computer Science, pp. 426-431, 2001a.
Meyerson, A. Online facility location. In 42nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 426-431, 2001b.
Jung, C., Kannan, S., and Lutz. N. Service in your neigh- borhood: Fairness in center location. In 1st Symposium on Foundations of Responsible Computing, FORC 2020, pp. 5:1-5:15, 2020.
Mikolov, T., Chen, K., Corrado, G., and Dean, J. Efficient estimation of word representations in vector space. In 1st International Conference on Learning Representations,
Kleindessner, M., Awasthi, P., and Morgenstern, J. Fair k-center clustering for data summarization. In Proceed- ings of the 36th International Conference on Machine Learning, ICML, pp. 3448 3457, 2019a.
ICIRR Workshop Track Proceedings, 2013.
Mitzenmacher, M. and Vassilvitskii. S. Algorithms with predictions. Commun. ACM, 65(7))33-35, 2022.
Kleindessner, M., Samadi, S., Awasthi, P., and Morgen- stern, J. Guarantees for spectral clustering with fairness constraints. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 3458-3467, 2019b.
Negahbani, M. and Chakrabarty, D. Better algorithms for individually fair k-clustering. In Advances in Neural In- formation Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS, pp. 13340-13351, 2021.
Kumar, A., Sabharwal, Y., and Sen, S. A simple linear time (1+e)--aproximmaton algorithm for k-means clustering in any dimensions. In 45th Symposium on Foundations of Computer Science (FOCS), Proceedings, pp. 454 462, 2004.
Peng. P. and Zhang, J. Towards query-optimal and time- efficient algorithm for clustering with a faulty oracle. In Conference on Learning Theory, COLT, pp. 3662-3680, 2021.
Kusner, M. J., Sun, Y., Kolkin, N. I., and Weinberger, K. Q.
Ringis, D., Pitié, F., and Kokaram, A. C. Near optimal per-clip lagrangian multiplier prediction in HEVC. In Picture Coding Symposium, PCS 2021, pp. 1-5, 2021.
From word embeddings to document distances. Pro- ceedings of the 32nd International Conference on Ma- chine Learning, ICML, pp. 957-966, 2015.
Rösner, C. and Schmidt, M. Privacy preserving clustering with constraints. In 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 96:1 96:1-96:14, 2018
Larsen, K. G., Mitzenmacher, M., and Tsourakakis, C. E. Clustering with a faulty oracle. In wWW 200 The Web Conference, pp. 2831-2834, 2020.
12

---

Relative Error Fair Clustering
Schmidt, M., Schwiegelshohn, C., and Sohler, C. Fair core- sets and streaming algorithms for fair k-means. In Ap- proximation and Online Algorithms- 17th International Workshop. WAOA, pp.
2019.
Silwal, S., Ahmadian, S., Nystrom, A., McCallum, A., Ra- machandran, D., and Kazemi, S. M. Kwikbucks: Core- lation clustering with cheap-weak and expensive-strong signals. In The Eleventh International Conference on Learning Reprexentations, ICLR, 2023.
Song, Z., Vakilian, A., Woodruff, D. P., and Zhou, S. On socially fair low-rank approximation and column subset selection. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024. NeurIPS, 2024.
Steinhaus, H. et al. Sur la division des corps matériels parties. Bull. Acad. Polon. Sci, 18804):801, 1956.
Thejaswi, S., Ordozgoiti, B., and Gionis, Diversity-aware k-median: Clustering with fair center representation. In Oliver, N., Pérez-Cruz, F., Kramer, S., Read, J., and Lozano, J. A. (eds.), Machine Learning and Knowledge Discovery in Databases. Research Track European Con- ference, ECML PKDD, Proceedings, Part 11, pp. 765-780, 2021.
Thejaswi, S., Gadekar, A., Ordozgoiti, B., and Osadnik, M. Clustering with fair-center representation: Parameterized approximation algorithms and heuristics. In KDD) '22: The 28th ACM SIGKDD Conference on Knowledge Dis- covery and Data Mining2, pp. 1749-1759. ACM, 2022.
Thejaswi, S., Gadekar, A., Ordozgoiti, B., and Gionis, A. Diversity-aware clustering: Computational complexity and approximation algorithms. CoRR, abs/2401.05500 2024.
Van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Xu, H., Silwal, S., and Indyk, P. A bi-metric framework for fast similarity search. CoRR, abs/2406.02891, 2024.
Yeh, I.C. Default of Credit Card Clients. UCI Machine Learning Repository, 2009.
Zhang, Z., Chen, X., Liu, L.. Chen, J., Huang, J., and Feng, Q Parameterized approximation schemes for fair-range clustering. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems, NewrIPS, 2024.
13

---

Relative Error Fair Clustering
Additional Related Work
We discuss additional related work in the literature, including results on fairness, k-clustering and coresets, and weak-strong distance oracles.
Fairness. Chierichetti et al. (2017b) initiated the study of disparate impact in fair clustering, which intuitively seeks each cluster to be balanced in representation across all protected subpopulations. Chierichetti et al. (2017b) initially considered two classes of protected groups, though an active line of research generalized to larger numbers of groups (Rösner & Schmidt, 2018), as well as different clustering objectives (Ahmadian et al., 2019; Bera et al., 2019; Kleindessner et al., 2019b; Schmidt et al., 2019; Cohen-Addad & Li, 2019; Ahmadian et al., 2020a; Esmaeili et al., 2020; 2021; Braverman et al., 2022). A related line of work required that each cluster contained a certain number of representatives from each subpopulation, rather than a certain fraction (Anegg et al., 2022: Jia et al., 2022). More generally, there exist other proposed notions of fairness, including but not limited to (1) social fairness, where the cost function is taken across subpopulations (Jones et al., 2020; Ghadiri et al., 2021; Makarychev & Vakilian, 2021), (2) individual faimess, where seeks to balance the clustering costs of each point in the dataset (Jung et al., 2020; Mahabadi & Vakilian, 2020; Negahbani & Chakrabarty, 2021), and (3) representative fairness, where the number of centers from each class is limited (Kleindessner et al., 2019a; Angelidakis et al., 2022). However, our work specifically considers (a, ffair clustering, i.e., disparate impact, these alternative notions of fairness and others (Ahmadian et al., 2020b; Song et al., 2024; Chen et al., 2025) are not the primary focus of this study.
k-clustering and coresets. k-clustering is one of the most fundamental problems that has been extensively studied for over six decades (see, e.g., (Forgy, 1965; Lloyd, 1982; Gonzalez, 1985; Charikar et al., 1999; Guha et al., 2003; Kumar et al., 2004; Arthur & Vassilvitskii, 2007; Feldman et al., 2007; Mettu & Plaxton, 2013)). Covering the vast literature for k-clustering is impossible for our paper, and we instead focus on the results directly related to ours. For k-median and k-means, Charikar et al. (1999) gave the first approxxtotinn in polynomial time, and Indyk (1999) gave the first sublinear algorithms for opp)-xpproiinttion k-median, which was later improved by Mettu & Plaxton (2013). There exist certain PTAS algorithms ((1 + E) -approximation) for k-clustering (Kumar et al., 2004; Feldman et al., 2007), although they are exponentially dependent on k/e. The concept of coresets for k-clustering was first introduced by the seminal work of Har-Peled & Mazumdar (2004) for Rd. Later, the influential work by Chen (2009) obtained coresets of size (roughly) O(k2 log" n for general metrics. The framework of ring sampling used by Chen (2009) is quite elegant, and it is the stem of our (k, E) coreset for general (ks, 2) clustering. Later results by Huang & Vishnoi (2020); Cohen- Addad et al. (2021); Braverman et al. (2021; 2022); Huang et al. (2024) further improved the sizes of the coresets on the dependency of k. log n, and E, and the near-optimal coreset sizes have been proven for certain applications (e.g.. in Huang et al. (2024)).
Coresets for fair clustering. Since the introduction of fair clustering by Chierichetti et al. (2017a), several works have investigated the construction of coresets that respect fairness constraints. Schmidt et al. (2019) presented coreset construction for the fair k-means problem and extended it to the streaming model. More recently, Bandyapadhyay et al. (2024) proposed coreset constructions for both fair i-mmans and k-median clustering using random sampling methods in metric and Fuclidean spaces. Their approach yields a constant-factor approximation for metric fair clustering and a (1 + =) approxximaton in Euclidean space, with running time independent of the data dimension.
Further extensions have considered settings where each data point may belong to multiple, possibly overlapping, sensitive groups For example, data point representing person might be labeled with both race and gender, each treated sensitive attribute. Huang et al. (2019) gave the first coreset construction for fair k-median clustering and also extended it to handle multiple, non-disjoint sensitive attributes. Subsequent works have explored different formulations of fair clustering under overlapping group structures, including Zhang et al. (2024); Gadekar et al. (2025); Thejaswi et al. (2022; 2021; 2024); Chen et al. (2024).
Weak-strong oracle models. In modern ML applications, there have been increasingly common trade-offs between information accuracy and price. For instance, John al. (2020) studied the bitrate-quality optimization in video transcoding by clustering the videos using meta-information and optimization such applications, there has been handful of work investigating learning problems with "weak-but-chens and "strong-but- expensive" information sources. Apart from the model in Bateni et al. (2024) that studied metric clustering, Silwal et al. (2023) studied correlation clustering with the presence of a noisy weak oracle, and Xu et al. (2024) investigated similarity search with two types of oracles. Galhotra et al. (2024) proposed a model that is quite close to Bateni et al. (2024), albeit their weak oracle is based on comparing pairs of distances. Finally, a handful of work also considered learning with only the
subset of videos with actual clips. Motivated by
14

---

Relative Error Fair Clustering
"weak" imprecise oracle (Mazumdar & Saha, 2017: Larsen al., 2020; Peng & Zhang, 2021), and this setting is closely related learning-augmenteed algorithms (see, e.g. Hsu et al. (2019); Indyk et al. (2019); Mitzenmacher & Vassilvitskii (2022); Ergun et al. (2022); Grigorescu et al. (2022); Braverman et al. (2024); C. S. et al. (2024); Braverman et al. (2025); Dong et al. (2024); Fu et al. (2025)).
B Deferred Proofs from Section 3
We now give the proof of correctness for Algorithm 1. Our plan is to show that for each iteration of line 4c, i). each iteration of line 4(c)vi (and therefore line 4c) only affects the rings with the index at most j + 1, and the entire algorithm converges in (log" n) iterations; it). for any ring k with samples more than (2(k log" nn/=",, we could get fairly accurate weights for the points to form a coreset; and kti). for any ring lo with samples less than ( log n/E²), we can "charge" the cost to the adjacent ring j of this iteration.
Step I: the convergence of the algorithm and the structural results. We start with the proof of i) which includes the convergence of the algorithm and some structural results that are useful for later steps. We start with lemma that states the "local" properties of the peeling step.
Lemma B.1. Let j be the index of the ring found by line 4(cliv of Algorithm 1. Then, with probability at least 1- 1/ poly(n). no points in P.e for E >> j + 1 is removed in the peeling step.
Proof. The lemma follows from the guarantees in Proposition 3 and the choice of the multiplicative C. factor in the way we partition the rings. Concretely, let us analyze any fixed index & E>> j" + 1. Note that for the ball formed by points in Speel there are at least 80 Co- have (z a) (2C,)" +1, Therefore, for all points x E Pies we have that
A llng n > 10 log n sampled points. Furthermore, by the definition of rings outside j 5
a(z, d(z, c)) > (20,)*+111 R
with probability at least 1/ (oly(n) by Proposition 3. Therefore, by the peeling rule of our algorithm, no such point x could be removed.
Lemma B.1 ensures that the peeling process never affects the points outside the ring with index j 1. For the purpose of analysis, will need to handle ring j 0 with more care. Next, we show lemma that characterizes the behavior of the peeling for rings with j O.
Lemma B.2. With probability at least 1/ (n)y(n), Algorithm 4 (the CONSERVATIVE- algorithm) could only be executed once. Furthermore, after the execution of Algorithm 4, we have that
all points x such that d(x, os) S
R 20o are removed from P..
no points in P... is removed.
Proof. We let pelose be the of points such that for x E $ d(z,ci S
R 20
and let $,00 be the sampled set from
1,0 Note that for Algorithm 4 to be executed, there must be
A: logg n 2 10 logn, n,
cclose 1,0
|SS.ol 2 40 Co N 2
e3
so that it is possible to find set of 10 10log n points. Therefore, when running the algorithm of Proposition 3, we have Rs < R/2Co. Therefore, conditioning on the high probability of Proposition 3, every point E pelose we have that
d(æ, Spool) I d(x,G) Co Rs S R.
Therefore, all points in pelose is removed. Furthermore, for each point y E Pt. we have that d(y, Speel) 2 d(y,c) R. which means such points will not be peeled. Finally, since all points in pele are pecled after one exccution of Algorithm 4, the condition of invoking Algorithm 4 will never met, which means the algorithm is executed at most once.
15

---

Relative Error Fair Clustering
We further provide another lemma showing that could remove all points within the radius of ring j This lemma is crucial for the fast convergence of the algorithm.
Lemma B.3. Let j be the index of the ring found by line 4(c)iv of Algorithm 1. Then, with probability at least 1 poly(n). all points Pi,e for j are removed in the peeling step.
Proof. Similar to Lemma B.I, 1, Lemma B.3 is an application of Proposition 3. For any ring with level S. j. Let g be the smallest ring index such that the ring has not been marked as "processed". For the ball formed by points in Ug Pg. there are at least 80- Co loog" a 2 10 log n sampled points, and radius the sampled points is at most (2Ca)" -R. As such, by Proposition 3, for any point E Ug-o Pa. with probability at least 1 1/ poly(n), we have that
d(z, Spool z d(z, s) Co (2C,)* R ((2G0)" + Co Co. (2Co)") R (2C6)
Therefore, by the rules of the algorithm, all points in rings Pi,e such that & & j' will be removed by the peeling step with probability at least 1 1/ (n).
There are several consequences of Lemmas B.1 to B.3: by Lemma B.1 and the algorithm design, each ring P.,j added to coreset by exactly one iteration; furthermore, by Lemma B.2 and Lemma B.3, algorithm could converge in Ologg* n) iterations. We formalize this statement the following lemma.
Lemma B.4. With probability at least poly(n), the following statements for Algorithm are true:
Each ring Pig is marked as "processed" by exactly one iteration of line 4c.
After O(log* n) iterations of line 4c, all points P3 is marked as "processed".
Proof. We first observe that for fixed iteration once the algorithm has identified j", there are two cases
(1) either jr has been marked "processed", for which case we should have j = + 1, where j' is the picked ring index of the last iteration r - 1 by line 4(c)iv (i.e.f j' is the "j"" of the last iteration);
(2) or j has is marked "not processed", which means jr > j + 1.
To elaborate the relationship between the cases and the value of j", note that conditioning on the success of Lemma B.2 and Lemma B.3, no points in the rings P..e for j' will survive in P; after round r - Furthermore, by the design of the algorithm, no rings with index é j' will be marked as "processed" before round r.
We now prove the second bullet first since it will be the basis for union-bound argument for the first bullet. We claim that ring j accounts for at least Q(1/ log n) fraction of the points in P,, formalized as follows
Claim B.5. For any iteration let j* be the ring found by line 4(c)iv. Then, with probability least 1 - 1/ poly(n), have that
Pi.- n
P
50 logg
Proof. The claim is simple application of Chernoff bound. Let La be the random variable for point z to be sampled, and the random variable I,. := Ene -.eP,,-nB P. I, is the number of total points we samples from ring j" for the current iteration. Since sample uniformly random, we have that
Pt.-
P.
A: log n
E [--]]
100C
p
3
16

---

Relative Error Fair Clustering
Therefore, if P.g- n n.P.
P.I. we will have E [4 S
On the other hand, by the design of klog" n points. By an application of Chernoff bound, we have that g
2Cp
&log'
50 l0gl
line 4(c)iv, the ring j should have at least 80Cb
k log 2
Pr 1 2 80Cs
Pi p3
P.
83
50 50gg n
log
2 n e
k log 2 n ed
I Pr 1 2 (1+ 8) E [1,-1]
6 E [1 2 78
Co-
E E
S 20p
s 1/ poly(n).
As such, conditioning on the above high-probability event, we have that for j have least 80C, must be P. n P.P.
A &log" 2
points, there Claim B.5 D
P. which is as claimed.
50 log
Note that by a simple averaging argument, since there are at most log n rings for each center, by an averaging argument, there exists at least one ring with least 80Cn &log" samples. Hence, in both cases for j = + and > > 1, as long as the algorithm does not invoke Algorithm 4, peeling step, at least all the points in P.. n P3 are removed. As such, we have that step r, with probability at least 1---oll poly(n). there is
(1
p(r+2)
p!
-
50 logn
where notation p! and p((++) are used to denote the surviving points (P,) for rounds r and (r + 1). Furthermore, by Lemma B.2, Algorithm 4 could be invoked for at most once. Therefore, after Olog" n) rounds, and conditioning on the high-probor bigh-probaability events to happen over all the rounds (which happens with probability least 1 1/ poly(n) by union bound), all points are removed from P. and marked as "processed".
We now turn the proof of the first bullet. Note that in both cases of j =" + and j" 1 for fixed iteration r, the rings that are marked as "processed" are [j' + 2 + 1] j and Algorithm is executed, then only j" marked as "processed"). Therefore, by a union bound the high probability events, with probability at least 1 - 1/ poly(n). each ring Lemma B.4 O
has unique iteration that marked it as "processed""
Step II: handling the rings with many samples. We now handle the rings that are marked "processed" by Algorithm (line 4(c)v). The analysis is similar Chen (2009), except we now need deal with an approximate number of points for weighing the coreset points. First, we show that we can approximate the number of points within these rings with small relative error.
Lemma B.6. Let S with s, O(k log n/e²) be the set of points sampled uniformly at random frommmfrom P. and let Sig
Pi.j NS. For all j such that |Su,] 2 30k log² n/e², let STd be any 1/3 fraction of points from St,j, and ma.5 3|P. |
For all PPall= 2 30log n/e?, with probability at least 1 poly n we have Mi.. E [(1 Pt... (1 [)
Proof. By the design of Algorithm 1, Algorithm 2 is only run on Sky that have at least 30k: log² n/e² points in them. Since we rum SO queries on S. we know the exact set Pt,, S. For l E [|P., let Xe be random variable that has value 1 if point l of [Pt]l was sampled and added to S and let X Σg X₁. We have
E. [X]
8, |Pall
E sest
3
3
[P.
By the definition of majj we have E [ma.j] = pP. Now, applying Chernoff bound we get
Pr (lii IPosl 2 e (Ptpl) S 2 exp
(-113
2 exp
[.30 n
<
poly n
Finally, a union bound over at most Ok polylog n) such Pt,, completes the proof.
17

---

Relative Error Fair Clustering
For coreset guarantees, we need bound the difference in cost for points in ring and the coreset points due to arbitrary of centers. The proof is extension of result from Chen (2009), which itself relies the following result from Haussler (1992).
Lemma B.7. Let M 2 0 and 1j be fixed constants, and let h(.) be function defined on set V such that vj S h(p) S 1 M for all p E V. Let U {p1,-.. .Ps be of samples drawn independently and uniformly form V, and let 8 > 0 be parameter: If's 2 (M²/287 In(2/X) X), then
h(V) M
k(U) D0
Pr
0 S
where h(U) Euee h(u) and h(V) EvEy h(v).
We now prove the approximation guarantee of the coreset points that are added by Algorithm 2.
Lemma B.8. For a ring P.ς that is marked "processed" by Algorithum 2, let C be any set of centers. Let Siee denote the set of points in S n Pi. that are uniformly sampled and Sweightt be any 2/3 points in Sae that are assigned weight mu,e/ | and added SC. Then, with probability least 1-
cost(C, P..e) cost(C, s S 26 2eeeP,e P.,e)
Proof. For a point P. let hpp) = d(C,p). We have,
d(c, Pa.e) hp) d(c,p) S Pte) diam( (P.e).
Let = ((CC M = (i,m(Pr.)) and = EM. For
sweight
2 (M/2/262) 1n2/X, from Lemma B.7 we have
i,t
Eper, d(C,p)
E Siigge d(C,s)
Pr
e
SA
(I)
P.ad
sweight
Using above equation and conditioning on the high probability event of Lemma B.6, we get
CC, Pt.e) cost(C, sywiihht
Σ d(C.p)
Σ d(C, s)w(s)
PEP.r
NE SES swaggtt
Σ Eperie d(C,p)
E. Exe smann (C, s)w(s)
IPrel
Pi.
|Pidl
Epeple d(C,p)
(1 (1-e) Eve Seseonr d(C, 8) Pa.
S |Prd
Piie
|Pacl
sweight S
(From Lemma B.6 and w = m S swiight
Eper, d(C,p)
Exespion d(C, 8)
Σ Exemmon d(C, 8)
|Pux
+ eiPie
[Ptel
S/eigght
S
Pr ediam (Pte) + e (relmii(((P..))
2s P. diimmddmm (P..)
w.p. at least Second last inequality follows from, for E S d(C, 8) S ddiam(P..)
18

---

Relative Error Fair Clustering
The above bounds the cost for rings that have sufficiently many points sampled in them (2 /2/22/2 (n/2))) We show that the number of points added by Algorithm are enough for prove main lemma for the rings with points added to the strong coreset SC.
the ahove lemma (for appropriately chosen A), and
Lemma B.9. Let Pheaay be the set of rings with points being added to SC. Furthermore, let
cost(C, phenyy = Σ
cost(C, Ptg)
E
be the total cost with respect any set of center C X of size most k. induced by the rings in Pheaay, and let
cost(C, phenyy =
Σ
cost(C,
cost(C,s steeight
PLy PLyEplon
Then, with probability at least 1/poly(n), we have
[cost(C, pheary cost(C, pheaay)
2s
Σ
Peul diam diam(P..) (P..).
PiyEPlem
Proof. Fix some set centers C of size at most Let A = A/ (ck log Br)) for some constant c. From Lemma B.8 for particular and f, we have with probability at least 1-1
cost(C, cost(C, S ) $
This holds for the points added to SC by Algorithm 2 as the number of points added for each heavy ring is
weight
i,
30 k log" n/e² 2 (1/2c²) 2/A (1/2=²) (In(en* k log Bn) + I }))
Now, since we have k centers in the approximate solution and each center has at most O(log 3n) rings, union bound over all the rings gives us with probability at least A/n",
cost(C, pheaay cost(C, phenvy
Σ
cost(C, P.e) cost(C, S/, s.weight
< 28
PReldiam(Pa.)
P.rE
As there are at most n choices of & centers C from point set X of size n, the proof concludes with final union bound over the choice of centers C and setting A = 1/n
Step III: handling the rings with few samples. We now turn to the analysis of the rings that are "neglected" by line 4(c)v of Algorithm 1. We do not have any subroutine that handles the cost of the rings with samples less than 30 log" Our plan for these rings is to show that the number of points there must be small, and as such, the contributions to the total cost must be small. Therefore, we can charge the cost of these rings to the cost of the rings with enough samples.
ed
To that end, we show the following lemma regarding the actual size between the rings with a few vs. many points. Lemma B.10. Let ring P.. be marked as "processed" in iteration r without any point x E Pi. being added to the coreset SC. Furthermore, let j be the ring found by line 4(c)iv of iteration r. Then, with probability at least - 1/ poly(n), we have
2Co IP >
E IPr.el
Proof. Let us say that ring Ps.j- has y/ points in P: Therefore, we have that TE [[St.5-1] 1 =1 bound we have that |Sty-1 1 < +)yy & with probability least 1 1/ poly(n). This gives that with high probability
3; Therefore by a Chermoff
19

---

Relative Error Fair Clustering
| V1 2 (I+e)
P. Similarly, let us say that ring Pig has y/2 points in P... Therefore, we have that E [| 1/2 p
Therefore by Chernoff bound we have that y22 S
|5 (1-2) P.
We now from the algorithm that |S 2 S0Co log
and |ر 30 log" Therefore we have the result.
For each ring P.ee marked as "processed" without points being added to SC, we define je( as be the index of ring Pa.j* that marked P.e as "processed".
We now define the following charging scheme for the quantity |Ptel diam(Pr,e), which will distribute the cost to P.el diam( P..e).
Algorithm 6. A charging scheme (a thought process for the analysis purpose only).
For each ring Pi.e such that is marked as "processed" in iteration without any point P.e being added to the coreset SC:
j() * O, write charge of diam(P..e) to all points in (t)
20,
Otherwise, if (e) = (which implies = 1), we write a charge of = Pa. P. = (a E P.. (
(P.1) to all points
20o
R ).
20%
If ring P., receives charges of at most y on each point and is marked as "processed" without any point æ E P.e being added to the coreset SC, then transfer the charges by writing charges of 20% 7 to all points (t))
Continue recursively until all charges are written points of rings Piç such that points Piee are added to the coreset SC.
Note that Algorithm is a thought process: we cannot hope actually perform the operations without making many strong oracle queries. However, such thought process as analytical tool is valid. Also note that Algorithm 6 eventually terminates since there has to be at least ring j" (of the first iteration) that has points added to the coreset SC. We now give two lemmas that characterize the guarantees of the charging scheme.
Lemma B.11. For any ring P.,e. conditioning the hrob--yooyyyllity event of Lemma B.10, the total number of charges Algorithm 6 could distribute is at least |P.el l diam(P, (P,,)-
Proof. The lemma is a direct consequence of Lemma B. B.10. For each ring Pie., we claim that conditioning on the high- probability event of Lemma 10 there is PP.5- Z 50r PP.el The statement trivially holds if j j*(() ()) A 0. On the other Ca.
hand, if (e) = 0, by the rules in Algorithm (which implies = 1), we argue that there are 50E |P.al- In particular, we could treat P., \ pelose (defined Algorithm 6) as a separate ring, and apply Lemma 1.10 to get the desired result. Therefore, the total charge P.,e could write is at least
20, diam(P..) (Pas- (P. 2 diam(Pr,) .Pael
as claimed.
Next, we bound the number charges for any point in ring that could possibly received. Lemma B.12. For any ring Pt.r, conditioning on the high-probubility event of Lemma B. 10, for any point x E Pr.s the total number of charges written on æ by Algorithm 6 is at most 22 (lam(P.eet)) for any E < 1.
Proof. For simplicity let us assume for now that recursive charging happens. Note that for each ring j only rings with indices 9 E [0,j* + 1] could possibly write charges to it. Let charge(j* t q) be the number of charges each point in ring j* could receive from ring For ring j + 1, we have that
charge(j* + + +1) = diam
S
2Cp
20

---

Relative Error Fair Clustering
by the rules of charging. Furthermore, for each ring q E [o, 1]. we have that
1 diam(Pa. ( (2Cu )5 15---1 r+5
charge(j* + 4) 2C,
diam( Pi,g) S 2Cg
where the last inequality follows from the definition of the rings, As such, the total charges ring j could be bounded by
5 +*+1
Σ chargeli + - g) v
Σ
diam(P
2C
-=
5'+1
$
E
diam Pa Pag
Σ
y5
-+11
20
2Co
9=0
c diam(Pa..+1)
Cyz (2200 00011=000 2 for any j 2 0)
Co
which gives us the desired results for non non-recursive charges.
We now handle recursive charges. By our charging scheme in Algorithm and Lemma B.4, only adjacent rings transfer charges. To elaborate, the only case that ring could become j" of that iteration without having added points to SC that was marked as "processed" by the j" of the last iteration (the j = j' + case in the proof of Lemma B.4). Therefore, by our analysis of the non-recursive sharing, the amount of charges ring é could transfer to ring l 1 for one level of recursion most
E diamm(Peee)) s
1
diam(P..)) -C0 S - ddiam(..e)) 20%
2Co Co
Hence, the total amount of charges that could be transferred any such j" at most
log
2-11" -()
(diam(maa)))) s diiam
Therefore, the charge a layer jr could receive due to the transfer from other layers is at most diam(Pa.*+) Combining this with the charging upper-bound of the non-recursive case gives us the desired statement.
We now use Lemma B. I and Lemma B. 3.12 to bound the total cost induced by the rings that are marked as "processed" without points added to the coreset SC.
Lemma B.13. Let P.e be a ring such without points added to SC, and (. be the ring for P.. charge to in the charging scheme of Algorithm 6. Then, we have that
S |..el C |Pss diam (Pam(P..(())..
Proof. By Lemma B. 11, each of such ring P..e could distribute all the costs as the charges. By Lemma B. 12, any point in such ring (e) receives at most 2s diam di.addaam (P...-((0+)) charges. We now claim that diam(P.,--(0=a)) < 2C diam(P..,-()) For all rings except j" j() 0, the statement simply follows from the construction. (() 0, by the rule of Algorithm 1, the charges could only be written on P.o pelose by the charging rule. Therefore, we have diam diam((...-(04a)) 20 (aa and summation over the charges on the points gives the desired lemma statement.
We now use Lemma B. to bound the cost of the coreset. We first present the following lemma that uses the quantity |Pall diam(P..) to bridge the cost between the rings with points in SC and the rings without.
Lemma B.14. Let C be any set of centers. Then, for any ring Paj- and rings Pa. such that j s 5 +1 and IPabl S Sn. 1 we have that
cost(C, Piş) S n cost(C, ) + 2Co |Pa.l diam Pz.)-
21

---

Relative Error Fair Clustering
Proof. The lemma stems from the triangle inequality. Concretely, let æ E Pt.y be point in the ring Pa.j could find corresponding point y E Pa. assigned center C such that
cost(C, 2) < d(c,z)
(cost(C, x)) is the optimal cost for x) (triangle inequality)
d(c, d( v)
cost(C, y) + diam((P,,'
cost(C, y) + 2C% diam (P.m)
(by our construction of the rings and j J + 1)
Therefore, could "reuse" the least-cost point Pig. for Pa.l S (Pa time and argue that
cost(C,Pi.)
Σ
co
$ Σ cost(C, y) + +Co (iam(P..))
xEP
$ 17 cost(C, P...)) + 2Co |P diam(P.,)).
as desired.
Using Lemma B.13 and Lemma B. 14, we now ready to bound the total cost on rings that are marked "processed" without any point being added to SC as follows.
Lemma B.15. Let pliigtt be the of rings that marked "processed" without points being added to SC, and let Pheary be all other rings. For any set of centers C, we have that
cost(C, plight =
Σ
cost(C,PP.). S Sc 20 log n
Σ E
(cost(C, Pc5) + |Pasl diam (Pi))).
P.. Epiitt
The lemma is natural corollary of Lemma B.13 and Lemma B.14 Fix any ring Pa.j Pheavy we let the rings pligh((j*)) be the set of rings with index l such that (C) = = (the notation first defined before Algorithm 6). We apply Lemma B. and Lemma B.13 all rings in plight(j") and obtain that
Proof.
Σ
cost(C, P(s) S
Σ
Co, 2Co
E
|Pasl (Pag(P..)) (by Lemma B.14)
2Co
Piy PPp
Pr ())
P (1*)
Σ
Cos + 20
Σ
PP diam(P.
20.
P., )
(by Lemma B.13)
< log n
cost(C, Paje) + 2C8 - diam(P.s-)
(at most log such rings)
20,
S g 2C8 llogn (cost(C,PP..))) | diam diam(P....))
Finally, since each ring P.e in plight has unique (f), summing over all rings in plight gives the desired lemma statement.
Wrapping up the proof of Theorem 4. natural corollary of the a-approximation of the (a, 3e-k coreset.
We ready finalize the proof of Theorem 4. The following claim is
Claim B.16. Let OPT be the optimal cost of clustering on with centers and let A be the set of centers from B-upproximate solution. Then,
Payl (2Co) < 3C,8 OPT & Σ (lam(Pa.) 6C,3 OPT 1.
22

---

Relative Error Fair Clustering
Proof. Consider any point p P.y. For j o, (2C,) R and for j 2 (2Co) s 2C,d(A,p), Hence, for any have (2Co)² R 2Cod(A A. + R. Now,
Σ PPss 7
Σ E
(200)
Σ Σ 2Cod(A,p) +
1d pEPi,
i. PEP.,
Σ 2Cod(A.p) R DEX
- 30PT + nR - 3C03 OPT
Since ((am) S 2(2Co)) R, we have Eng |Pal (lam(Pr.) S 6Co3 OPT
Lemma B.17. For any set of centers C S of size at most k. it holds that
|cost(C, X) cost(C, SC se 15, C. logn cost(C, X)
with probability at least 1 1/ poly(n).
Proof. Similar to the case in Lemma B.9 and Lemma B. we define plight as the rings being marked as "processed" without points added to SC and pheavy as the other rings. We thus have
CC
Σ bJ Epiu
cost(C, plight
Σ
cost(C, Plymyy.
pllar plist
Define cost(C, plight) and cost(C, pheavy) as the cost induced by SC for Clearly, the total cost induced by the coreset SC cost(C, SC) cost(C, plight) cost(C, phewyy. Furthermore, by construction, there cost(C, plight) O. Conditioning on the high-probon high-probability events of Lemma B.9 and Lemma B.15, we have that
[oost(C, pheavy) co,t(C, phenay
< 2 g-
Σ
PPs (P.)
PLyE
|cost(C, plisht) co,t(C, plight
S cost(C, plight)
2C2 logn.
Σ
(cost(C,Pa.) + |Ptssl diam(P..)).
P P
As such, we could bound the difference of the cost as costt(C, X) - cost(C, SC)]
< coss((C, pheary) cost((C, pheavy)) + cost(C, plight) cost(C, plight)
s e s.2 log n Σ
Pa,l diam(P. Ps,j) + 20 log n.
cost(C, Pt.))
(by Lemma B.15)
Pi
Eplexy
< 3- 1208 logn OPT + 2C2 logn.
Σ
cost(C, Pa.)
(by Claim B.16)
< e 3- 120 logn cost(C, X) + 20 logn co
< 1 C logn X)
(B N 1)
which is as desired.
Finally, to get (1 + apappooxiittioon we let 153-e-C3 Jog 0 log by the constant choices and Co (by Propo- sitions and 3). The size of the coreset and number of SO queries are therefore O log n/E²3) = O log n/=²) = pollyog(n)/e* as desired by Theorem 4.
23

---

Relative Error Fair Clustering
C Deferred Proofs from Section 4
The analysis. Similar to the analysis of Algorithm 1, we need to show that i). Algorithm 5 converges with a small number of strong oracle queries; vi). Algorithm 5 preserves the k-median cost by a (1 + +) factor. In addition, we need to prove that Algorithm is indeed preseevving.....
We first establish the bounded number of strong oracle queries for Algorithm 5. The guarantee and the proof are as follows.
Lemma C.1. Algorithm outputs a coreset of size O(* k2 log" mlggn/s using logg n) strong oracle SO (point or edge) queries, Onk log" n.) weak oracle WO queries, and converges in O(k2 fe² + nk) time. Furthermore, with probability at least 1 - 1/ poly(n), after 10 log' n iteration of line 4c, all point of P: is processed by exactly one of the iterations of line 4(c)v.
c²
Proof. For each iteration, the only points we make strong oracle SO queries on are the points in S,, which is at most Ologg n). All other points in Pa make at most Olog r1) times of weak oracle queries, and the number of points added to FC during each iteration is ((k "log" n log(ne 1)).
We now prove the "furthermore" part using the srobabbbbayllity events of Lemma B.3, Lemma B.4, and Claim B.5. Note that although the choice j" and the number of samples have changed, we still have P.jj n P. 800Co logn, n, which means the guarantees in Claim B.5 continues to hold with a changed constant. Therefore, each point is only processed by one iteration, and each iteration, at least Tn fraction of the remaining points are processed by line 4(c)v. This implies after 100 log" iterations, no point in P. remains not processed by line 4(c)v.
-_
Therefore, the size of the coreset FC follows from the number of O(ke log" n log(ne= samples in each iteration and the k log" n iterations. The number of weak and strong oracle queries follows from the same argument, and the running time scales linearly with the coreset size.
We now move to the analysis of the assigmeent-rreserving (1 + s) coreset. The main lemma for the assignment-preserving approximation is as follows.
Lemma C.2. Let (X, d) be an input set of points in I&, and let FC be the resulting cusignment-presenee coreset as prescribed by Algorithm 5. With high probability, for any set of centers and any given assignment constraint I, there is
|osttFF,, CFC cost((,,,,))) S Co,tt(K,CCC)
To prove Lemma C.2, we first reduce the problem to an easier case that C, is fixed, using a union bound similar to Braverman et al. (2022). We also make dCa bounded by moving centers far from the ring center. Next we bound the additive error for a single set of points T,(*) and FC(T.!)) (recall that T,(7) is the set of peeled points and FC(T,()) is weighted sampled set from T:(r). We construct transformations between assignments of TT((t) and FC(T(()) that suffers small cost. These transformations imply optimal costs of T,(*) and (C() are close.
For the clarity of presentation, in what follows, we use T and e" as short-hand notations for T,(r) and & when the context is clear. Let be the number of rings of c².
Step I: Union bound. Our first step is reducing Lemma C.2 to much easier version, in which C and I' are fixed and C does not contain centers far from c". In particular, we move all centers outside B(c", RRar) to c", where R 60diam(T)/e: The proof of Lemma C.2 requires the additive error
Let the approximation ratio of WC be owc- Define e' 100 owc logn to be less than e 10 cost(T, C,T) g' [T] - dT)m(T).
Lemma C.3. Suppose AT) is an algorithm that outputs assignment-preservvig coresets Tf ffr every S X, Bec*, 60diam(T)/e) of size l and every assignment constraint I,
Pr CosS(ALG(T))C cost(T,C,ff) 2 e' [T] diam(T) 58
10
11
24

---

Relative Error Fair Clustering
for some d E (0, 1), then for every T X, with probability at least On (n ke 1) for every center set X of size k and every assignment constraint
() cost(T, &
cost( (ost(T,C,I)+t + [T] diam(T).
10
Proof. For every center set C and assignment constraint r, we move all centers outside B(c", R (denoted by Crac) to c" and define the center set and assignment constraint after movements as C and Г. For every assignment a, the cost of before movements is upper bounded by
cost (T, cost (TTC,T)+ + + Σ E
((z,)) -((z,,
cECoer
cost (T,Č,T) + Σ Σ
o(x,c)d(aee")
2ET cECoar
= cost cost" (T,Č,T) + Σ T(c)d(c,c')
oECiar
and lower bounded by
cost (T,C,T) = cost (T,C,T)
Σ
E o(a,c)(d(z,c) d(x,c'))
aET eECto.
2 cost" (T,C,T), + Σ
Σ
olx,c) 2d(x, c*))
#ET cECrer
2 cost" (T,C, + Σ Σ
(1 8/20) (x)
#ET cECrar
cost" (T, (1 e/20) Σ ((c)d(c.c').
oEC
In corollary, suppose of and o* are optimal assignments of cost(T, and cost(T, C,F), then we have
Cost S cost"' (T, S cost(T,C,T)) - (1- - e/20) Σ ((c)d(c,e))
cECar
cost(T,C,I) < cost" (T,C,T) cos) Σ T(c)d(c,e").
eECtar
Next we round all capacities in I't to {i/M :1 0}, where M = [600k/s], to get a new assignment constraint i' satisfying I(C) = (C) and [[(c) [') 1/M for every c C.
Suppose the optimal assignment for î is a. There always exists assignment of of F such that for every C. (o(r)) of cx) < 1/M. Hence we have
(oost(TCC,1) C',
Σ (x),c)((xcc) (),
rEd
EET
dC
M
oEc
60k diam(T")
EM diam(T)/10.
Define
:: ((C.T) C c B(c", REGE T.
25

---

Relative Error Fair Clustering
We have [F| ( M).. Applying union bound for every (i", E F, we have
[*) F,
cost(T, 11C log
[7] diam(7)
(2)
holds with probability at least - [F Conditioning on (2), for every C and r, we have
(oss((,C,TT cost (T.C C,
[(cost(S, C, c0 r)) (cost(T, costoo, -cot())) + |cosa(T, C, cost(S, C)
((c)d(e,c') (o,t((S r*) (ost(S,,,,)) + |oott(T, (ost(T,Crr)
10
cEC
+ coost(T, č, )') (S, C
10
((c) 10
diam diam(T) +
- (T) diam(T)
11
cECtar
10 (os [T] diam(T).
Step II: Bounding (T))(FC((T),,,I) cost(T,C,,)) In order to prove cost(T, C, D) and cost(FC C, are close, we show that optimal assignments of T and FT( can transform to each other. Suppose o², T are optimal assignments of and FC(T) respectively.
Fix any set of points T, centers C, and capacity constraint r. We will prove the for diam(C) < Riar (OdiaamT) and apply the union bound by Lemma C.3 afterwards.
Starting with Ø", our first target is to construct an assignment a of T such that cost" (T, I), R cost" (FC(T),C,T). Lemma C.4. For any fixed choice of C, I, and T for some iteration and of line 4(c)v, we have that
cost(T, C, S E (oss)(C
The expectation taken over only the randomness of the sampling in line 4(c)vC.
Proof. Let 5* be the optimal assignment of FC(T). Since ö* is random assignment, we construct a by setting (Ir,e) == E 1 (I, c).. Then we have
(F) E
Σ Σ c(x,c)
(by definition)
Σ Σ (Ix
PET cost" (T,C,T)
(by definition)
cost" (T,C,T),
(optimality of o*)
as desired.
Lemma C.5. For any fixed choice of r, and T for some iteration r and of line 4(chv, with probability at least
O(n -k *(nnnnn k)-k,, we have
cost (FC((), < Cost( 1T) -iamm().
The probability is taken over only the randomness of the sampling line 4(c)vC.
26

---

Relative Error Fair Clustering
Proof. Let a" be the optimal assignment T. We start with an assignment that assigns (x, o² (z( c) fraction of to center c. This assignment satisfies Var E FC(T), Enec (2,, I However, Σxer (1, [(c) for every c E C.
7
m
may not hold
In order to transform (z, e) into an assignment satisfying r, for every center such that Ensy T' c) > [(c), we need to
change some assignments of e other centers x - c', suffering cost of most d(x, c') ( C) S d(c, <) S diam(C).
For every center E C, the difference between assigned weight and real capacity is EzEFO(T) oxx c) every T, we have
M [(c)]. For
C) S ΣΣ o(x,c)
aEC TET
7 m
0'(z, + dCam(C)
Σ
Σ aEc (EFC)
a
[(c)
EET
ΣΣ EEC PET
(x. dC)
Σ
T(c)
m
eEC
IEFC(T)
ΣΣ oxx, c) + (C)
max -E(-1,+1Jc
Σ Sc
Σ xEFCIT)
ozz c)
T
r(c)
RET
SEC
Fix s E {-1,+1}e let x; (1 i < m) denotes the i-th point in T. Then I1, 22, 2m are independent random variables
uniformly drawn from T. Define Y; Ecec 8.0 (2i, c) m Hoeffding's 's inequality,
[T]
For every < i S m, we have Y, E [-|7]/m, [T]/m]. By
122
Pr
Σ
8:0 (xi
Σ
ET
Pr
Y;
E
Σ Yı
E'T
m
CEC
cEC
I exp (-E"mm/2)
Applying union bound for every E {-1, +115, we have
Pr
Σ Se aEc
(Ir
T
I(c)
> 2eT//2
< 2 exp (-el mmmm)))
sEf
-E(-1,+1e
m
(TFC(TT
5 5n 10, (nn=-(mn + ke -))
In summary, C))) < cost(T,C,I)) + + |T) diam(T) holds with probability at least 10 On * (n +
ke -==))-
We now move to bound the error induced by Cost(FFOT), [cost (FCS) (Oo in the same manner of Cohen-Addad & Li (2019): Cohen-Addad et al. (2025).
Lemma C.6. For any fixed choice of C, I, and T for some iteration r and i of line 4(chv, with probability at least
- 10, O(n (n + ks )-=)), we have that
(DTT):CCCDD-((((FF/)))..CCC < (T) di)m(T).
The randomness is only over the sampling in line 4(c]vC.
Proof. Let f t2,...,tt. fm be the m points sampled in FC(T). Define f(1,, 12,...,ttm = cost((fi,...., t, C, For every t, E a and < < m, we have
sup ft ......, tm) f(t.....,, t..... ml) diam(T). Gex
27

---

Relative Error Fair Clustering
By McDiarmid's inequality, Pr(l ,1m) [1(1,, .......... (m)) S S (T) diam(T)) S exp(-e"Pm)
I n O(n fnn Onn=nnn+++
ke ke
1
Step III: Put everything together. We finalize the proof of Lemma C.2. To this end, we need to further establish lower bound for the cost of (T C. r(r) for each iteration as follows. the following discussion, cost(A', WC) and cost (t) denotes the optimal cost of unconstrainted k-median problem. In particular cost(X')) denotes mineçx |c|== cost(X, C).
Lemma C.7. With probability at least n
WCJ 10 logn
cost (X, WC)
80 log Σ
Σ
T
diam(T;
(T)
(3)
Proof. Let p(r) be the remaining points at the beginning of the r-th iteration of line 4c. Let N, ES pp6)
We fix some
r in the following discussion and omit the superscript (r) for convenience.
Let j" follows the definition in line 4(c)iv. Define Jlggn Sr. We have (Sage1 y by the definition of j". Define
sty Pr.il sy be the expected size of St.z
Pick 5 0.1. By Chernoff bound, we have
4
Pr
Pag-l $
N Pr[((1 + +8)s 11
5(1 + 8) logn
S Pr [(1 + 8)825 S 15:5511
When stg 2 170. we have
8² (6 + 2) 8)
Pr Pr 2 (1+
exx
exp
(Chernoff bound)
Sn 10
(7 i(log n))
Otherwise, we have |S,y.1 > (7/s:.)))s..) Since 7/s,," is sufficiently large, this case happens with negligible probability. holds.
We show that with high probability, for every s j < L. satisfying 8t. T |Sa
Pr[[St,p| 2 7] < exp
Sij
(1 = 7 1) 2.,5
1 2
16
< exp
(8i.) < (t8)
(t+ 21 + 8)
< n
(- = A(log n))
Take union bound for every j. have Pr[st.-
イ > 1 110
In summary, with probability at least 2n -10
4 N.
P >
(4)
5(1 8) logn
For rings PaS inside Pa.t, i.c. j j", have [Stl < 7. By symmetry, prove that with probability at least
1 n
4 N.
Vj < |Pul <
(5)
5(1 5) log
28

---

Relative Error Fair Clustering
By the definition of 7 == {o E p() ((,, Speel) s (2Co)" RJ, T( points in -1 Conditioning on (4) and (5), we have
contains every point Psg G jz) and some
1 diam (T
cost (e)
Σ =ET!!)
2 (2Co)" ((P.)"" (Pog
(6)
8CB log
By union bound, (6) holds for every 1 isis |WC| 1 S S 10 log with probability at least 1 n= We conclude the proof by showing (6) implies
[WC] log
WCJ
10 log
Co WC) = Σ Σ
cost(T)"), 80% log n
Σ
Σ
7 diam(T!")).
1=1
Proof of Lemma C.2. By Lemma C.4, C.5, C.6, for every i, C Pij. and for every C C Bla, 60diam(T)/s) P, Algorithm 5 outputs set FC(T) such that co,)((,C,,)) cost(FC(TT,
< E diam(T) with probability 1-n n 10 On fn + Ke )=k). Then by applying union bound to the result of Lemma C.3, with probability at least 1 n $, for every 1 < [WC|, S < 10logn, n. Algorithm 5 outputs FC(T!")) such that for every C,
cost(FO((T")), cT ,c,I)
<
cost (TT"), ,c,I)+ + 10awc Cf logn
|r!-|| diam (TT)))
(7)
10
Let 6* be the optimal assignment of cost(X,C,,)) Define (c) = Emerp o(x,c). Summing up for every i,r, conditioning on (3) and (7), we have
cost(FC, c, r) cost(X &
ΣΣ (cost( (cos()F(( (..)"/
[WC] 10
co ,,,)))) + 10owc CJ log 12' -iia
10
4F
cost( X, C) + cost(X2 WC)
10
5awc
E (o (,,
4E
+ 5 (o))(
10
S cost(t,
By applying the same argument the optimal assignment 8t of cost(FC, C) prove cost(2',C
cost(FC, C, < cost(X' C, holds with probability at least - -- 77, which concludes the proof.
D A (1 +1++ -oCorsstt for general (k, 2) Clustering
In this section, we generalize our analysis k-median algorithm in Section to (k:, =)-clustering for = 0(1) (including k-means). We first remind readers of the stated guarantees as follows.
Theorem There exists an algorithm in the weak-strong oracle model that, with high probability, computes a (k, E) coreset of size Ō for (k, z)-clusteringg with any O(1) using Ö strong oracle point queries (or edge queries), ((nk) weak oracle queries, and Ömk + k2/ (=)) time.
The algorithm is essentially the same as Algorithm 1, and the analysis follows from the same idea of heavy-hitter sampling + peeling combined with the algorithm in Chen (2009). However, we need to change the analysis in the same manner of Chen (2009), and we need a separate charging argument for the "skipped" rings in the (ks z)-clustering setting.
29

---

Relative Error Fair Clustering
Lemma D.I. The coresel produced by Algorithm is a (1 + (())) (k, =l-csserri with size O(k² log n/e²) for any constant with high probability.
Since use the same algorithm (Algorithm 1), we only use Ok log" n/s²) strong oracle SO queries, which leads to (1 + +))-correee for (k, 2)-cluttei with &² polylog (n)/E² SO queries. We will rescale E by polylog (n) factors in the end and argue that the size and number of strong oracle queries are at most k2 polylog (n)/E² for any constant 2.
Additional notation and generalized triangle inequality. We give some self- notation used in the analysis for the (k, z) and the generalized triangle inequality. For the distance between two points I and y, we use d (2, y) to denote the z-th power of the distance. For any center e in a clustering C, the cost of point x assigned to center e could therefore be expressed as cost, x) = dF(c, æ). Similarly, we could use
cost, (ost,(c,PP) P) = Σ d'(c,z)
PEP C(r)=c
for the cost of a center set of points P. Correspondingly, could denote the total cost
cost, == Σ cost, (c, (c, P).
GEC
The following lemma characterizes the generalized triangle inequality. Proposition 4. Let (u, v, w, be points from metric space subset of [A]o. Then, for any 2 2 1, we have
(u, d d' o) 2 (dd w) + d v)).
The lemma could be straightforwardly proved by taking the z-th power of the triangle inequality and using Jensen's inequality. We omit the proof for the sake of conciseness.
The approximation analysis. Similar to the analysis of the k-median case, the proof for the approximation guarantees is divided into the guarantees for the rings with samples added SC and the rings without. For the purpose of conciseness, we omit the proof of many lemmas that directly follow in the exactly same way as in Section 3.
Step I: the convergence of the algorithm and the structural results. We argue that all the results in this step follow in the same way as Section 3. In what follows, we list the lemmas and provide brief justifications for why they continue to hold for general (k, >)ccusstei objectives.
Lemma B.1. Let j* be the index of the ring found by line 4(c)iv of Algorithm 1. Then, with probability at least 1-1/ poly(n), no points in P. 8 >> j + is removed in the peeling step.
Lemma B.2. With probability at least - 1/ (n)y Algorithm 4 (the CONSERVATIVE PEELING algorithm) could only be executed once. Furthermore, after the execution of Algorithm 4, we have that
all points x such that d(x,
R 2Co
are removed from P.-
no points in Pt, is removed.
Lemma B.3. Letj" jr be the index of the ring found by line 4(cliv of Algorithm 1. Then, with probability at least 1 1-1/ 1/pooy(nn. all points for S jr are removed in the peeling step.
The proofs of Lemmas B.I to B.3 are based on the high-proud high-probabilityy success of the distance estimation algorithm of Proposition 3. Therefore, switching the (k, cclustting objective does not affect the proof.
Since Lemmas B.1 to B.3 continue hold, the convergence of the algorithm is similarly true. Lemma B.4. With probability at least - 1/ poly(n), the following statements for Algorithm are true:
Each ring Paá is marked as "processed" by exactly iteration of line 4c.
After Oglog² n) iterations of line 4c, all points P; is marked as "processed".
30

---

Relative Error Fair Clustering
Conditioning the high-probability events of Lemmas B.1 to B.3, the proof of Lemma B.4 only uses the concentration of sampled points, which is independent of the change of the objectives.
Step I: handling the rings with many samples, Similar to the case of k-median, we now handle the rings that are marked "processed" by Algorithm 2 (line 4(c)v). The analysis similarly follows from (Chen, 2009). In the first step, we directly use the lemma that establishes the estimation of the number of points in the ring.
Lemma B.6. Let S with 8, = O(k log' n//²)) be the set of points sampled uniformly at random from P. and let S Po.j NS. For all such that |ريك] 2 30k log n//", let STg be any 1/3 fraction of points promtsfrom St.j, and myg For all [Ptz) 2 30log n//?, with probability at least 1 poly we have Ma.j E - PP) e)(..l
3/
Sest
*r
We now prove the approximation guarantee of the coreset points that added by Algorithm 2.
Lemma D.2. For a ring Pue that is marked "processed" by Algorithm 2, let be any set of centers. Let Si,e denote the set of points in S n Pi.e that are uniformly sampled and sweight be any 2/3 points in Sig that are assigned weight and added to SC. Then, with probability at least 1 - X
= m..e///ea. / |,,e/|S,ee
cost(C,,Pp cost(C, S ( 2 PP.el (d, + (diam((P,.)))
Proof.
We follow the same proof strategy as Lemma B.8. For E Pi.e, let h(p) = dC, We have,
0 h(p) d (C, < Pa,) diam diam(P..)) s 2 [d (C, Pt,e) + (diam((3.x))
Let 17 = 0, M, = (c, (c, Ps,c) + (diam P and 5 = eM. For S
sweight
2 (M2 2/A from Lemma B.7 we
have
Eperie d)(c.p) E Eeesteen s),
Pr
E (c, Ps.e) + (diam (diam(Pr.e))
S
(8)
Pr.el
sweeight j
Using the above equation and conditioning on the high probability event of Lemma B.6, we get
cost, (O,t,(C, Ps,e) cost, (C, s
Σ d'(c,p)
Σ (C((ss)u
SES
PpePrr d dc(c.) Exemman d' dC(C, ()((s)
P.Pdl
Prrel
Pr.
Eper., d²(c.p)
(1 - e) E stnnnn d= (C. 8) (). Pa.e
|Pa.l
Piee
Prel
seegght
i,
(From Lemma B.6 and w m..e/l S | (
Σ EpEPi (c(c.)
Exe d= (C,
Σ Smean
swean d (C,
< P..d
+e(P,d
Pirel
sweight
weigght
i,e < P - 2² (d= (C, Pt.e) + (diam(Pr.)) e|Pall 2 (C, + [diam(P...))
$
< 2 |P.dl (d,(C, Pt.e) + (diam( [(.)))
w.p. at least X. Second last inequality follows from, for E S
d dF(C,)) < 2a (d, P.,e) + (diam(P...))
We now bound the costs for the rings with points added to the strong coreset SC in the same way as in Lemma B.9.
31

---

Relative Error Fair Clustering
Lemma D.3. Let Pheary be the set of rings with points being added SC. Farthermore, let
cost, (C, Phewr))
Σ
cost,(C,PPs.
PayePlon
be the total cost with respect to any set of center C S X of size at most k. induced by the rings in Pheavy, and let
cost' (c, pheary
Σ
cost,(C, Si. Sweeight
E
Then, with probability at least 1/ poly n, we have
costt(CC, Pheary - cost (C, phemay)
S 22 g.
Σ
- (d Pa,e) + ((iam((s,e))
E
Proof. Fix set of centers C of size at most k. Let X = A/ (n* (og. Bn)) for some constant c. From Lemma D.2 for particular and i, we have with probability at least À
(C, cost, (C, Se s
< E PP.el (c, (diam(Pa,))7
This holds for the points added to SC by Algorithm 2 as the number points added for each heavy ring is
S
weightt
30 - k log" r//²²= 2 (1/2=²) In 2/X (1/2=²) (In(cn* k log 8n) + In +)
Now, since we have & centers the approximate solution and each center has at most O(log 3n) rings, union bound over all the rings gives us with probability at least A/n²,
cost, (C, :hhaary- - cost (C, pheary) S
Σ
cost, (C, - cost, (C, S,, sweight
2
PPul (d, + (diam(P..)) (P,)))
As there are at most & choices of centers C from point set X of size n, the proof concludes with final union bound over the choice of centers and setting = 1/n".
Step II: handling the rings with few samples. We now analyze the rings that are marked "processed" without any points added to SC in Algorithm We need define a new charging scheme that works with diam² (Pr,e) and bound the loss by generalized triangle inequality. We first note that the size relationship between the ring Pte and the ring P..j- that marks P. "processed" continues to hold.
Lemma B.10. Let ring Paç marked as "processed" in iteration without any point x E Ps.e being added the coreset SC. Furthermore, let j be the ring found by line 4(c)iv of iteration Then, with probability least 1 - 1/ poly(n), we have
2Co E P..el
P 2
The proof of the lemma only requires the heavy-hitter sampling argument which is independent of the objectives. We now define a generalized charging scheme similar that of Algorithm albeit working with diam" 2 (Pa,e. For each ring P.t marked as "processed"" without points being added SC, define (c) as be the index of ring Pa. that marked p. as "processed".
32

---

Relative Error Fair Clustering
Algorithm 7. A charging scheme (a thought process for the analysis purpose only).
For each ring Piee such that é is marked as "processed" in iteration without any point E Pie being added to the coreset SC:
20, diam (Pt," to all points (t. Otherwise, if j (e) 0 (which implies É = 1), we write charge of 20% diam"(P:.) to all points in
(()) + O, we write a charge of
{o P.D d(x,c) Z 20 }.
If ring e receives charges of at most 7 each point and is marked as "processed" without any point æ E P.e being added to the coreset SC, then transfer the charges by writing charges of 2Co Y to all points in (())
Continue recursively until all charges are written on points of rings P.e such that points Pi.e are added to the coreset SC.
We now give two lemmas that characterize the guarantees of the charging scheme the same way as the k-median case. Lemma D.4. For any ring P.,s conditioning on the high-probbbilityy event of Lemma B.10, the total number of charges Algorithm 6 could distribute al least [P.el I diam" (Pa,))
Proof. The lemma follows from the proof of Lemma D.4 with the change of the z-th power. For each ring P.y, claim that conditioning the high-probability event of Lemma B. there is (()) 2 Co.
50c PP.el- The statement trivially holds if (e) # O. On the other hand, if j (2) = O, by the rules in Algorithm (which implies & = 1), we argue that there Co. 1. In particular, we could treat P.u \ Pelove (defined in Algorithm 7) as separate ring, and apply Lemma B.10
are 50c to get the desired result. Therefore, the total charge P.,e could write to is at least
E diam" (P,t) (e) 2 diam diam"(P,,) IPaels
20
claimed.
Next, again bound the number of charges for any point in ring that could be received.
Lemma D.5. For any ring Pi.s conditioning the high-probability event of Lemma B. 10, for any point E Pie the total "aam"(PP,e4)
number of charges written on x by Algorithm 6 is at most s (2C,)² diam" (Pi,e4)) (P..41).for for any s < 1.
Proof. We refer the reader to Lemma 12 for the full proof, and we only give a concise version here that skips some of the intermediate reasoning steps. Assuming no recursive charging happens, the total charge for P.y- could receive is at most
Σ charge(j" 9)
diam (Pig)
2C,
0=0
51+1
< diam $ (Pr.)42))
Σ
(2
2C,
20,
9=0
< Co
diam (Pam"(PP..-41 (1))
Efa
(20, -1,
- -++1 < 2 for any j 2 0)
On the other hand, if recursive charging happens, with the same argument in Lemma B.12, have that
E diam (P..n)( =² 2C (2Co)* diam(Pre) < (2C))² e² diamm
2C Co
Hence, the total amount charges that could be transferred to any such j" at most
log
Σ
(2C))²
20'00 diam((P.") s =(2Co)* ddia((P.g+4),,
t=j+11
which is as desired.
33

---

Relative Error Fair Clustering
We could now bound the total contribution from the rings that are marked "processed" without points added the coreset SC as follows.
Lemma D.6. Let Pı. be ring such without points added to SC, and (e) be the ring for Pie to charge to in the charging scheme of Algorithm 6. Then, we have that
Piell diam" * (Pr,e) S (2C)) (P diam (P)))
Proof. The proof is similar to the proof of Lemma D.6. By Lemma D.5, any point in ring Pig-(1) receives at most 8 .2Co)* (iam(Pas<(0)z)) charges. We now claim that diam (P... v (2Cn)* diam(Pa,s-ca) (c,) For all rings except (e) 0, the statement simply follows directly from the construction. (c) = by the rule of Algorithm the charges could only be written on P., \ p by the charging rule. Therefore, have (e0))) I (2Co)* diam (()) Furthermore, we could show that the number of points receiving charges in ring P.,j-() is at least the number of points in Pi,. Therefore, we have that
Pr.el diam" ( (P.,)) = (2C)) |Pa diam" diam" (Pis SE. (2Co) PPag
diam" (Pig
as desired by the lemma statement.
The next lemma an analog of Lemma B.14 that bounds the costs between (c, Pi.) and (c, Pi,,) such that P.,, marked Pi.j as "processed".
Lemma D.7. Let C be any set of centers. Then, for any ring P.g. and rings Ptş such that j S +nd [Pal S n P have that
cost. (C, Pc.) 2 2 co, (2Co)2* |Pul diam" (Pt.).
Proof. We use generalized triangle inequality (Proposition to prove the lemma. Let P., be point in the ring Pa.j we could find corresponding point
Pi.j assigned to center E C such that
cost, (C, x) < d=(c.z)
(cost, (C, xr) is the optimal cost for x)
< 2 (d (c, y) + d (x, v))
(by Proposition 4)
< cost, (C, y) + 2 diam (P...)
s 2 cost_ (C, 3) + 2 (2C,)* diam" 2 (Piz).
(by our construction of the rings and j j + 1)
Iterating the argument with the least-cost point y E Pi. for P S n Paa time gives
cost. (C, P..)
Σ (C,
sEP
$ 2
Σ
cost, cost,(C, 1) + 2 (2C))* -
-diam
sEP.s
< 2 17- cost, (C, Pi.c.) + (2C,) 22 |Pyl diam" (P.j).
as desired.
We bound the total cost induced by the "light" rings in the same way of Lemma B.15. Lemma D.8. Let plight be the set of rings that are marked "processed" without points being added to SC, and let phbcary be all other rings. For any set of centers C, we have that
cost,(C, pliiihn
Σ
(C, ( (2C6) log n- Σ Eppayy
(cost, P
|Poal
diam diam²(P.,)).
Proof. Similar to the proof of Lemma B.15, we fix any ring Pa.j E phenay we let the rings plight (j*) be the set of rings with index such that (() j*, and apply Lemma D.7 and Lemma D.6 all rings in plight(j*) and obtain that
Σ cost, Pc.))
2 cost, (Cst,(C,,) Pt.r)) ) (2 P. P..Epii
Σ
2=
Σ
|aal diam diam²(P...)
)
P EPPP))))
(by Lemma D.7)
34

---

Relative Error Fair Clustering
8.2 cost,(C, P(.)) + (2Co)
Σ
|Pag-l diam( Pi.-))
P.sEpllahe)))
Pis ((sEl(l)))))))
(by Lemma B.13)
< logn (e 25 (e, + (2C0) |Pr.-1 diam( diam(Pig-))
(at most log n such rings)
S (2Co) logn (cost(C, P.g.) | diam ((.)))
Once again, since each ring pi in plight has unique j (f), summing over all rings in plight gives the desired lemma statement.
Wrapping up the proof of Theorem 3. We now finalize the proof of Lemma D.I. For (a, -approxiiiiiiiiii for (ke, 2), cluusterri, the approximation lower bound for opt is as follows.
Claim D.9. Let OPT be the optimal cost of clustering on P with centers for (k, 2) clustering and let A be the centers from 3-approximation solution. Then, Eis Pisl ((2C)) RY* (20o)2++1g OPT and Σis [Pasl diam" diam"(P..)) S
(2C6) 32+133 3.04113000 OPT...
Proof. Consider any point E Pag. For j = 0, = we have ((2)))R) I (2C)d(A.p) + R)* < 2 (d + R*). Now,
Rt and for j 2 1, (2C.) 2Cd((A,p)) Hence, for any j
Σ Pull ((2))) Σ EE
E
R22)))R)²
S Σ
Σ
2a (22
1
1 PERS
2 Σ ((2Co) (A.p) +
< (f2Cg)* OPT + +RR & 22+ OPT
Since diam(P..) < 2(2C,) Rt we have Ei, Paol (diam(P:.)) & (2C)) OPT
The following lemma directly establishes the desired guarantees as in Theorem 3. Lemma D.10. For any set of centers C C X of size most k, it holds that
[cost, X) cost, (C)) < 6-00 (2Co)*² log cost, X)
with probability at least 1/ poly(n).
Proof. We define plight as the rings being marked as "processed" without points added to SC and Pheavy as the rings with points added to SC. We have
cost, sost,(C,X) X)
Σ
CO, plight
Σ
cost,(C, Pleaayy.
pide Epil
The Explitt
Define cost(C, plight) and CC, pheavy) as the cost induced by SC for C, and follows that cost(C, SC) = cosi(C, plight) + cost(C, pheawy). Furthermore, by our construction, there is cost(C, plight) 0. Conditioning on the high- gigh-probability events of Lemma D.3 and Lemma D.8, have that
CC, -phaaay cC, pheawy) S 2042
Σ
Pasl. (c, Ptt) + diam (P.c))
P
|ost((C, plight cost(C, plight
< (C, plighty
S e (2C) 25 logn.
(cost, (C, Pt.j) + |Payl diam" (Pt,)).
diam"(P..))
Prieplaay
35

---

Relative Error Fair Clustering
As such, we could bound the difference of the cost
(C, X cost; (C))
< cost((,, (pheary) - cost(C, ) + cost(C, (pligtt) - cost(C,,
E (2Co)²z 2= -logn n. Σ
| (d* Pa,e) + diam (P..)) + +2 llog n
Σ
cost(C, Pij)
E
Ps. EPlayy
(by Lemma D.8) (by Claim D.9)
8 8.. 65211 (2Co) < 2e (2C)) logn 3 cost, (C, X),
llog n cost, (C, X) + (2Co) log n 3 OPT*
which is desired.
Finally, could rescale using 22(20))oz11 log 0 = by the constant choices of 3, Co. and The size of the coreser and number of SO queries are therefore O log n/5 O(h2 log" n//²) k (n))) as desired by Theorem 3.
36


Reviews:
[{"review_id": "AZisSQXw6A", "reviewer": "Reviewer_R956", "summary": "The paper gives coresets for the fair $\\(k,z\\) $ clustering problem using an oracle model which allows for a combination of queries i) that are returned a weak approximation of distances (weak oracle) at a low cost and ii) queries that are returned exact distances between pair of points but at a high cost (strong oracle). The notion of fairness used here is proportionality-based notion where the proportion of points inside every cluster belonging to a particular demographic group (like gender, income level etc.) must be bounded by some specified thresholds. The idea is to minimize the number of queries to the strong oracle to build coresets i.e. subsample of data that satisfies the assignment criteria with a $(1 \\pm \\epsilon) $ approximation.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address their questions below.\n\n\n### Re: Experiments\n\nWe chose a uniformly sampled coreset as a baseline since we wanted to compare our algorithm to a method that uses a comparable number of strong oracle queries.\nWe do not compare our coreset to other coreset constructions as their trivial application would either require $O(n)$ strong oracle queries which is significantly larger than our $\\tilde{O}(k^2 / \\varepsilon^2)$ bound or require non-trivial modifications for using less number of strong oracle queries which is out of scope for this work. \n\n\n### Re: Claim about our result in Theorem 2\n\nOur claim is for the result under the weak-strong oracle model, for which to the best of our knowledge no fair clustering coresets exist and previous results do not extend trivially. We will make this clearer in the next version of the paper. We note that if one wishes to directly apply other algorithms, they would either need to make $O(n)$ strong oracle queries for the trivial application or modify the algorithms to work with fewer queries while providing the $(1+\\varepsilon)$ approximation guarantee. For comparison in the classical setting (no weak-strong oracles), our techniques build on top of Braverman et. al (2022) and as a result, assuming access to accurate distances, the bound should be similar. In the next version of the paper, we will be sure to include a more thorough discussion of the techniques of previous papers with comparison to ours.", "claims_and_evidence": "The ideas in the paper are a mix of bunch of ideas from existing coreset literature. for e.g: ring based coresets, weak coresets etc. The techniques are modified to work for the particular version of the clustering problem", "methods_and_evaluation_criteria": "The experimentation section of the paper is rather weak. There is just a baseline comparison with uniform sampling. It is already fairly well known that uniform sampling is unable to give strong relative error guarantees. The authors must have compared to other sampling techniques.", "theoretical_claims": "There are not many proofs in the main body of the paper. I had a high-level look at the supplementary material for the proofs. They appear ok.", "experimental_designs_or_analyses": "See the section on methods and evaluation. This is mostly a theoretical paper with just a very small set of experiments. There should have been more comparisons with other sampling techniques.", "relation_to_broader_scientific_literature": "The paper proposes coresets for proportionality based fair version of clustering problem. To the best of my knowledge there are some results on coresets for fair clustering and similar ideas like ring based coresets are used. however, I am not sure if there has been a use of a distance oracle model in the existing literature.", "essential_references_not_discussed": "This is my main issue with this paper. The paper claims \". Prior to Theorem 2, no fair k-median coreset with non-trivial approximation guarantees or coreset size was known.\" \n\nThere are at least 3 papers which discuss coresets for fair clustering \n1) Fair Coresets and Streaming Algorithms for Fair k-means, Schmidt et al.\n2) On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications, Bandyapadhyay et al.\n3) Coresets for clustering with fairness constraints., Huang et al.\n\n1) and 3) are cited but not discussed. I am not sure how the authors can make the above claim when nontrivial coresets do exist. It is not at all clear to me how their coreset results compare/contrast with existing results. This is a big weakness. I believe there should not only be a detailed discussion in terms of quality of coresets, techniques etc with these papers but also, they should be compared with in the experiments section too. These papers have similar techniques for coreset construction (though not in the oracle model). Without both theoretical and experimental comparisons, I am not convinced that this paper has novelty.", "other_strengths_and_weaknesses": "see responses to other questions\n\nOverall, the paper is not very unclear. However, the presentation could be improved. Experiments should be strengthened and brought to the main body.", "other_comments_or_suggestions": "see response to \"Essential References Not Discussed\"", "questions_for_authors": "see response to \"Essential References Not Discussed\"", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "lblqrjD8sB", "reviewer": "Reviewer_mTF8", "summary": "The authors study the fair $(k,z)$-clustering problem in a weak-strong oracle model. Each data point may belong to one or more groups, and the goal is to cluster the data points while minimizing a given clustering objective. The fairness requirement ensures that within each cluster, data points from different groups are represented within a specified range, i.e., $\\alpha_i \\leq \\beta_i$ for each group $i$.\n\nIn this setting, querying the strong oracle, which computes the exact distances between data points, is expensive. Instead, a weaker oracle is available, which provides accurate distance predictions for at least $\\frac{2}{3}$ of the data points while returning arbitrary values for the remaining portion. Since it is unknown which data points have inaccurate predictions from the weak oracle, repeating queries to improve accuracy is not applicable. The goal is to minimize the number of queries to the strong oracle and obtain a solution that optimizes the clustering objective.\n\nThe high-level idea of the paper is to construct a coreset of small size while minimizing the number of queries to the strong oracle. If the coreset is sufficiently small, the strong oracle can be used with a quadratic number of queries to compute exact distances for the data points in the coreset. Since the coreset is small, existing clustering methods can be applied efficiently to obtain the final clustering solution.\n\n**[Update after rebuttal]** I am satisfied with the responses of authors and, I will retain my assessment unchanged.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough and encouraging comments and suggestions, and address their questions below.\n\n### Re: Experimental description\nThe experiment considers the (p,q)-fair k-median problem where each data point is assigned a color of either p or q and each cluster should have a balance of at least p/q. We will include more details in the next version of the paper. \n\n### Re: Practical applicability\nThe run time of our algorithms are $\\tilde{O}({nk}+\\text{poly}(k/\\varepsilon))$. In addition, our algorithm uses uniform sampling, which in contrast to importance sampling is easier to implement at large scale in practice. \nWe want to also remark that in our experiments, the bottleneck of the runtime is *not* the construction of the coresets, but rather is to perform fair clustering (which is by the fairtree algorithm by Backurs et al. [ICML’19]). Scaling the algorithm to practical massive scale would require non-trivial engineering efforts, and it is definitely an interesting direction to explore in the future.\n\n\n### Re: References\nWe thank the reviewer for pointing out the literature, and will be sure to include them and provide a more comprehensive overview of prior work in the next version of the paper. \n\n### Re: Other comments\nYes, we will make the change in the newer version.\n\n### Re: Reorganizing to include proofs\nWe primarily did not include proofs due to space constraints and instead opted for high level ideas. We will try to incorporate more explanation for lemmas and theorems wherever possible in the newer version.", "claims_and_evidence": "Though the paper is theory-heavy, the authors do a commendable job of explaining the high-level idea and providing a clear overview of their approach. Additionally, before and after each lemma, the high-level explanations are sufficiently clear to convey the main intuition, assuming one trusts the authors’ claims about the detailed proofs in the appendix.\n\nI have reviewed the main text and parts of the appendix, but given the review timeline, I was unable to verify the proofs in detail. Since most of the proofs and the core contributions of the paper are relegated to the appendix, I question whether a conference publication is the best venue. In conferences, proofs are often reviewed only at a superficial level, and their correctness is not thoroughly verified. It might be more beneficial to submit this work to a theoretical conference or a journal, where reviewers have more time to examine the proofs in depth and provide constructive feedback.", "methods_and_evaluation_criteria": "Not applicable", "theoretical_claims": "See my comments in claims and evidences.", "experimental_designs_or_analyses": "The experiments are not detailed, as the authors conduct only a single experiment to report the relative cost difference. Additionally, the description does not clearly specify the fairness constraints.", "relation_to_broader_scientific_literature": "The paper advances the theoretical understanding of the (fair) clustering problem. The presented approach is non-trivial and requires expertise in the field to develop. While the authors do a commendable job of explaining the method at a high level, I have doubts about its practical applicability to real-world datasets with millions or billions of data points. In my opinion, this work is primarily of theoretical interest.", "essential_references_not_discussed": "I acknowledge that the field of (fair) clustering is vast, making it challenging to cite all relevant references. However, the authors overlook several important works in fair clustering, particularly in the area of representative fairness. Additionally, the citations primarily focus on a specific group of authors, while there are relevant contributions beyond this clique that also deserve recognition. Below, I have listed some relevant references that should be considered to provide a more comprehensive overview of prior research.\n\n[1] Zhang, Zhen, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, and Qilong Feng. \"Parameterized Approximation Schemes for Fair-Range Clustering.\" Advances in Neural Information Processing Systems 37 (2024): 60192-60211.\n\n[2] Gadekar, Ameet, Aristides Gionis, and Suhas Thejaswi. \"Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights.\" In proceedings of the ACM Web Conference, 2025.\n\n[3] Thejaswi, Suhas, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. \"Clustering with fair-center representation: Parameterized approximation algorithms and heuristics.\" In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1749-1759. 2022.\n\n[4] Thejaswi, Suhas, Bruno Ordozgoiti, and Aristides Gionis. \"Diversity-aware k-median: Clustering with fair center representation.\" In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, pp. 765-780. Springer, 2021.\n\n[5] Thejaswi, Suhas, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis. \"Diversity-aware clustering: Computational Complexity and Approximation Algorithms.\" arXiv preprint arXiv:2401.05502 (2024).\n\n[6] Chen, Xianrun, Sai Ji, Chenchen Wu, Yicheng Xu, and Yang Yang. \"An approximation algorithm for diversity-aware fair k-supplier problem.\" Theoretical Computer Science 983 (2024): 114305.", "other_strengths_and_weaknesses": "Given the limited timeframe of the conference review process, it is challenging to provide a thorough review of this paper, as it is theoretically dense and its key contributions are placed in the appendix. The authors should consider reorganizing the paper to include at least some of the key contributions in the main body. If this is not feasible, submitting the work to a journal might be more appropriate, as it would allow for a more detailed review of the proofs. Given these constraints, I cannot vouch for the correctness of the proofs.", "other_comments_or_suggestions": "Line 268: it should be $\\sigma: S \\times C \\rightarrow R^+$ right?", "questions_for_authors": "NA", "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": "QwWhEkUW9p", "reviewer": "Reviewer_6eJr", "summary": "*Background*: This work studies the problem of fair clustering in the weak-strong oracle framework. In this setup, there exists a strong oracle offering precise distance measurements at a higher cost, alongside a weak providing less accurate distance estimates at a lower cost. The goal is to minimize strong oracle queries while achieving a near-optimal fair clustering. Fair clustering refers to addressing faireness concerns in the clustering process – for instance, there are $\\ell$ groups in total, and for each group $j$, set fairness constraints to be parameters  $0\\leq \\alpha_j\\leq \\beta_j\\leq 1$, such that each cluster should have at least $\\alpha_j$ and at most $\\beta_j$ fraction of points from group $j$.\n\n*Main results*: First, when the number of disjoint groups each point belongs to is bounded by $\\Lambda$, the authors designed an algorithm that constructs a $(k,\\epsilon)$ fair coreset of size $\\tilde{O}(\\Lambda k^2/\\epsilon^2)$ in the $k$-median clustering with $\\tilde{O}(\\Lambda k)$ strong oracle point queries. This also implies a corresponding corest for the $\\Lambda =1$ case, i.e., the assignment-preserving $k$-median clustering. Then for the $(k,z)$-clustering without fairness constraint and $z=O(1)$, a $(k,\\epsilon)$-coreset of size $\\tilde{O}(k^2/\\epsilon^3)$ is constructed with $\\tilde{O}(k^2/\\epsilon^3)$ strong oracle point queries. \n\n*Main methodology*: The approach employs a ring sampling technique, improved by heavy-hitter sampling and recursive peeling. During each iteration, the algorithm samples some points, and use strong oracle queries on each sampled points to determine their ring assignments. Then, the rings with more sampled points are denoted as heavy ones, which contribute more to the final solution, so we can build coresets only for these heavy rings. At the end of each iteration, the algorithm peels off the points in the heavy rings. After all the iterations, the union of all coresets constitutes the final fair $k$-clustering. Moreover, to allow assignment-preserving properties hold in the clustering, the algorithm performs an additional sampling step at the end of each iteration.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address their questions below.\n\n ### Re: Runtime claim in Lemma 3.1\nThe bound is indeed accounting for the runtime of subroutines. To see this note that for ``not processed’’ rings we check the size in the sampled set and then perform peeling. If the sample size is large enough, we add it to coreset or ignore otherwise. This takes $\\tilde{O}(k^2/\\varepsilon^3)$ time for $O(\\log n)$ rings for $k$ centers. For the peeling subroutine, we perform $O(\\log n)$ WO queries for at most $n$ points and $k$ centers to estimate the distances, giving the final runtime of $\\tilde{O}(nk + k^2/\\varepsilon^3)$. We will expand to make this clearer.\n\n \n### Re: Lemma B.2\nThe term $\\tilde{d}(y, c_i)$ should be $d(y, c_i)$, thank you for catching the typo. Following this, notice that $c_i$ is part of the set $S^{\\text{peel}}$ by definition and hence the inequality follows from Proposition 13 and definition of rings.\n\n\n### Re: Lemma C.2\n\\alpha_{WC}: Yes, \\alpha_{WC} is the cost of the weak coreset (defined on line 1300~1301). There is a typo in equation (7), which should be eps / (10 alpha_WC C_0^2 log n) instead of eps / (10 C_0^2 log n). So we just need \\alpha_{WC} > 1.\n\nThe first inequality of cost(FC, C, \\Gamma) - cost(X, C, \\Gamma):\nThere is a typo in the RHS of line 1560~1561, should be cost(FC(T_i^{(r)}),C,\\Gamma^{(r)}_i)) - cost(T_i^{(r)},C,\\Gamma^{(r)}_i) (i.e. swap the two terms). Here, we are partitioning T and FC into rings. Summing up the optimal cost of these rings should get a total cost no less than the original cost of the whole set (before partition). This is because we fix the assignment constraint (i.e. \\Gamma^{(r)}_i) during the partition process. So we have cost(FC, C, \\Gamma) <= \\sum_i \\sum_r cost(FC(T_i^{(r)}),C,\\Gamma^{(r)}_i).\n\nSince sigma^* is the optimal assignment of cost(X, C, \\Gamma), letting the assignment constraint be the optimal one does not increase the cost, so we have cost(X, C, \\Gamma) = \\sum_i \\sum_r cost(T_i^{(r)},C,\\Gamma^{(r)}_i).\n\n\n### Re: Lemma C.4\nYes, it should be $\\sigma(x,c)$, we will change it.\n\n\n\n### Re: Experiments\nThe choice of our baseline of uniformly sampled coreset stems from comparing our method to another that uses a comparable number of SO queries. We do not compare it to unconstrained k-median as fairness constraints typically only increase the cost of clustering compared to optimal unconstrained one.\n\n\n### Re: Coreset sizes in Thm 3 and Thm 4\nThe reviewer’s intuition is correct that the value of Theorem 4 is that it applies to general $(k,z)$-clustering for any $z=O(1)$ (instead of only $k$-median). Due to the page limits of ICML, we decided to present the $k$-median version for the $(1+\\varepsilon)$ coreset (without fairness) in the main paper to help understanding. The actual proof of the more general Theorem 4 is in Appendix D: if follows the same algorithm as in Theorem 15, and the analysis is different. At the moment, it is unclear to us how to generalize the analysis of Theorem 3 to the general $(k,z)$-setting. We will clarify this in future versions. \n\n\n### Re: Typos and suggestions\nWe thank the reviewer for the careful reading and their suggestions. We will make the necessary corrections and changes.", "claims_and_evidence": "The claims are supported by rigorous proofs, though some parts are somewhat difficult to follow (see comments below).", "methods_and_evaluation_criteria": "The authors computed the fair $k$-median cost for specified centroids and fairlet decomposition, and compared fair $k$-median cost of their proposed algorithm against uniform coresets. This evaluation criteria appears suitable.", "theoretical_claims": "I performed a sanity check of the proofs for the following: Lemma 3.1, Lemma B.1, Lemma B.2, Lemma B.3, Claim B.5, Lemma B.4, Lemma B.6, Lemma B.7 (B.7 is a result from another paper). The following are some issues that need to be addressed: \n\n- Lemma 3.1: This lemma states that “the algorithm converges in xxx time”. If this refers to the running time of the algorithm, it should account not only for the weak-strong model queries but also for the running time of other invoked subroutines. For example, in Line v of Algorithm 1, there is a “for” loop over $\\ell \\leq j^*+1$, and the algorithm invokes the Coreset-Update subroutine over each $\\ell$. Should the running time include invocations? While the running time might remain unchanged after considering these subroutine calls, it could be beneficial to include this explanation in the proof for clarity. \n\n- Lemma B.2: Line 811~812, the inequality $\\tilde{d}(y,S^{pell})\\geq \\tilde{d}(y,c_i)\\geq R$ is not explained.\n\n- Lemma C.2 (Page 29): \n\t\n-- The authors didn’t explain on $\\alpha_{WC}$; it may refer to the approximation ratio of $cost(X,WC)$ regarding optimal cost $cost(X)$, and thus $\\alpha_{WC}>1$. From Line 1560 to Line 1563, it follows from Equation (7), but it seems that $\\alpha_{WC}<1$; while from Line 1566 to Line 1568, it seems that $\\alpha_{WC}>1$. These two derivations look like a contradiction on the range of $\\alpha_{WC}$.\n\n-- The first inequality of $cost(FC,C,\\Gamma)-cost(X,C,\\Gamma)$ is not explained.\n\n-- Besides, this derivation is not explained: $\\sum\\sum cost(T_i^{(r)},C,Γ_i^{(r)})≤cost(X,C,\\Gamma)$.\n\n- Lemma C.4: Line 1404, need to explain $p$ in the $\\sigma(p,c)$. Perhaps it should be $x$, instead of $p$?", "experimental_designs_or_analyses": "I reviewed Experiments section in the appendix. The authors conducted experiments on only two datasets, which may not be sufficient to show the advantages of their approach. \n\nBesides, the chosen baseline might be too simple. It could be worthwhile to consider a baseline using coresets generated by Algorithm 1 without having fairness constraint. This comparison could provide a clearer understanding of the impact of including fairness constraints.", "relation_to_broader_scientific_literature": "The weak-strong oracle model is motivated by the fact that modern machine learning models often use embedding functions to estimate distances for non-metric data, which can be computationally expensive, and by the applications that involve trade-offs between information accuracy and price. The concept of fair clustering arises from the need of incorporating fairness into clustering. This paper contributes to algorithms in fair clustering within weak-strong oracle model, which is a potential application direction in the filed of modern machine learning.", "essential_references_not_discussed": "I did not identify any essential references that are missing from the discussion.", "other_strengths_and_weaknesses": "Strengths:\n\n- the first $(1+\\epsilon)$-coresets for fair $k$-median clustering using $poly((k\\log n)/\\epsilon)$ queries to the strong oracle. \n\nWeaknesses:\n\n- the experiments are somewhat too simplistic (see comments above).\n\n- The proofs and inequalities are hard to follow and verify, and need clearer explanations. It would be better if inequalities have tags or comments to explain on them.", "other_comments_or_suggestions": "Typos:\n\t\n- Line 145, left col., change “belong” to “belongs”\n- Line 121, right col., delete “such that each $x\\in X$”\n- Line 123, right col. correct \"$\\log^4 \\cdot \\log n$\"\n- Line 140, right col. it is mentioned that \"... with even better efficiency on the number of strong oracle queries\". However, in line 154, right col. it is stated that \"the number of strong oracle queries is slightly worse\". These two statements seem contradicting. \n- Line 256, right col., delete the second $s_3$ in “$s_3$ weak oracle queries $s_3$”\n- Line 333, right col., change “A updated set” to “An updated set”\n- Line 353, right col., change “A updated set” to “An updated set”\n- Line 372, right col., change “A updated set” to “An updated set”\n- Line 397, left col., the repeated “for” in “for each center for $O(\\log^2⁡n)$ iterations” sounds a little unclear. Consider rephrasing it to “for $O(\\log^2⁡n)$ queries per center”, or “for each center, we have $O(\\log^2⁡n)$ iterations, and in each iteration, …”\n- Line 766~767, the sentence “Our plan is to show that in each iteration of line 4c, there are i). each iteration of …; ii). for any ring …; and iii). for any …” has grammatical inconsistencies. Consider rephrasing to: “Our plan is to show that i). in each iteration of …; ii). for any ring …; iii). for any…”\n- Line 354, left col., change $S_{i,\\ell}$ to $S_{i,j^*}$\n- Line 1550, there is a missing “)” of $diam(T)$\n- Line 1306, should it be $Pr⁡[\\cdots\\geq \\cdots]≤\\delta$? (According to the reference on Line 1550~1551)\n\nSuggestions:\n- it will be helpful to discuss the state-of-the-art of the sizes of coreset for $(k,z)$-clustering, in particular, for $k$-median", "questions_for_authors": "In Theorem 4, the coreset for $(k, z)$-clustering has a size of $\\tilde{O}(k^2/\\epsilon^3)$ with $\\tilde{O}(k^2/\\epsilon^3)$ strong oracle queries. In particular, this (Theorem 15) applies to $k$-median clustering. However, in Theorem 3, even with the fairness constraint, you construct a coreset for $k$-median with smaller size $\\tilde{O}(k^2/\\epsilon^2)$ and with a significantly smaller $\\tilde{O}(k)$ strong oracle query complexity.\n\nI understand that the algorithm for Theorem 4 likely applies to a more general problem. However, the discrepancy mentioned above is still somewhat counterintuitive. Could you clarify this?", "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:

Meta-review: The paper considers fair clustering problems with inaccurate information: distance information can be obtained from either a strong oracle providing exact distances---but at high cost---and a weak oracle providing potentially inaccurate distance estimates but at low cost. The weak-strong oracle model is motivated by the fact that modern machine learning models often use embedding functions to estimate distances for non-metric data, which can be computationally expensive, and by applications that involve trade-offs between accuracy and cost.  The goal is to produce a near-optimal fair clustering on with a minimum number of strong-oracle queries.  The paper achieves the first (1 + epsilon)-coresets for fair k-median clustering using poly(k, log n, 1/epsilon) queries to the strong oracle. Results are also obtained for coresets without fairness requirements that beat the previous work with high-constant approximations in the fairness-not-considered model.  

No previous work considered the fairness model here, and the weak-strong model is well-motivated.
Decision: Accept (poster)