Fair Clustering in the Sliding Window Model
Authors: Vincent Cohen-Addad
Shaofeng H.-C. Jiang
Qiaoyuan Yang
Yubo Zhang
Samson Zhou
Venue: ICLR 2025 Spotlight (2025)
Keywords: fair clustering
sliding window model
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et al. (2017), in the sliding window model. We show that although there exist efficient streaming algorithms in the insertion-only model, surprisingly no algorithm can achieve finite ratio without violating the fairness constraint in sliding window. Hence, the problem of fair clustering is a rare separation between the insertion-only streaming model and the sliding window model. On the other hand, we show that if the fairness constraint is relaxed by a multiplicative $(1+\varepsilon)$ factor, there exists a $(1 + \varepsilon)$-approximate sliding window algorithm that uses $\text{poly}(k\varepsilon^{-1}\log n)$ space. This achieves essentially the best parameters (up to degree in the polynomial) provided the aforementioned lower bound. We also implement a number of empirical evaluations on real datasets to complement our theoretical results.

Published as a conference paper at ICLR 2025
FAIR CLUSTERING IN THE SLIDING WINDOW MODEL
Vincent Cohen-Addad
Shaofeng H.-C. Jiang
Google
School of Computer Science, Peking University shaofeng. jiang@pku wang@pku.edu.com
cohenaddaalggoogee.ccom
Qiaoyuan Yang
Yubo Zhang
School of Computer Science, Peking University qi acyaanyangastt wtwpaaanggsuuuuu.eeee.. .ku.euu. edu.cn
School of Computer Science, Peking University z zhangyubol 80stu. pku. edu. cn
Samson Zhou
Texas A&M University
samsonzhou@gmaii com
ABSTRACT
We study streaming algorithms for proportionally fair clustering, notion originally suggested by Chierichetti et al. (2017), in the sliding window model. We show that although there exist efficient streaming algorithms in the insertion-only model, surprisingly no algorithm can achieve finite ratio without violating the fairness constraint in sliding window. Hence, the problem of fair clustering is rare separation between the insertion-only streaming model and the sliding window model. On the other hand, we show that if the fairness constraint is relaxed by a multiplicative (1 + E) factor, there exists a (1 =)-approximate sliding window algorithm that uses poly(ke log n) space. This achieves essentially the best parameters (up to degree the polynomial) provided the aforementioned lower bound. We also implement number of empirical evaluations on real datasets complement our theoretical results.
INTRODUCTION
Clustering is a fundamental technique used to identify meaningful patterns and structures within data. Typically, the objective of clustering involves grouping similar data points together into distinct clusters. Due to extensive research conducted over the years, clustering has become a well-established and deeply understood field. In the standard notion of clustering. the input is set P of points in space equipped with metric dist, a cluster parameter k >> O, and an exponent > 0 that is a positive integer and the objective to minimize the quantity minc,r: Epe min dist c)a. The
problem is called (k, :--clustering when the metric space is R2 and dist is the Euclidean distance and particular, the problem is called k-median for z 1 and k-means for 2. Note that the center set C' implicitly partitions / by grouping together the points E / closest to each center c E C.
Fair clustering. When applied user data, traditional clustering methods may produce biased outputs, leading to discriminatory outcomes that can perpetuate social inequalities in the downstream applications (Dwork al., 2012; Chhabra al., 2021). For example, clustering algorithms used in hiring or lending tasks may inadvertently discriminate against certain groups based on factors such as race, gender, or socioeconomic status. This particularly problematic in domains where clustering is used to make decisions with significant consequences, such as healtheare, education. and finance. Hence, there has been a large line active work focusing on various notions fairness for clustering; we defer overview of this work to Section 1.2.
In (a:, -fair clustering, each item E P is associated with a subpopulation (often also called group) [8] across possible subpopulations and additional constraints 0 a, I B3 1 for each i E [4]. Then the goal is to minimize the clustering objective over all possible clusters where each cluster has at least og fraction and no more than B3 fraction of items in group L., Thus,

---

Published as a conference paper at ICLR 2025
these assignment constraints are designed to capture faimesss by ensuring that subpopulation is under-represented or over-represented in each cluster.
The sliding window model. The sliding window model (Datar et al., 2002), which focuses on analyzing recent data points rather than the entire dataset, offers a unique perspective on this challenge. In many real-world applications, recent data is more relevant and informative than historical data (Babcock et al., 2002; Manku & Motwani, 2012; Papapetrou et al., 2015; Wei et al., 2016). For example, in social media analysis, understanding current trends and discussions requires focusing on the most recent posts. In these scenarios, the sliding window model can provide a more dynamic and responsive approach to clustering.
The sliding window model is particularly relevant for applications in which computation must be restricted data received after a certain time. Laws regarding data privacy, including the sweeping General Data Protection Regulation (GDPR), explicitly require that companies must not retain certain user information beyond a specified time. Consequently, Facebook retains user search data for 6 months (Facebook), the Apple retains user information for 3 months (Apple), and Google stores browser information for up to months (Google). The sliding window model captures these retention policies with the appropriate setting of the window parameter W and thus has been considered across a wide range of applications (Lee& & Ting, 2006a;b; Braverman & Ostrovsky, 2007; Chen et al., 2016; Datar & Motwani, 2016; Epasto et al., 2017; Braverman et al., 2018; 2021; Woodruff & Zhou, 2021; Jayaram et al., 2022; Blocki et al., 2023).
However, the sliding window model also introduces challenges for fairesss As data streams in continuously, the composition of the window can change rapidly, potentially leading to biased or discriminatory outcomes. Therefore, it is essential to develop clustering algorithms that are not only accurate but also fair in the context of the sliding window model. Formally, points arrive sequentially in the sliding window model and the dataset P implicitly defined as the last n points of the stream. The goal is to perform fair clustering using space sublinear in the size n of the dataset.
1.1 OUR RESULTS
In this work, we study fair clustering in the sliding window model. In particular, our goal is to achieve (1 + e)-multiplicative approximation to the optimal fair clustering for the dataset implicitly defined by the data stream in the sliding window model, while using the minimal amount of space (and then minimizing the update time as secondary priority). Surprisingly, there no existing work on fair clustering in the sliding window model.
On the other hand, recent work has achieved (1 + -)aapproximation for the standard formula- tion of (k, =cclustringg in the sliding window model using min(e" polylog "A words of space (Woodruff et al., 2023), which was shown to be space-optimal up factors polylogarith- mic in the input size and the aspect ratio A (Cohen-Addad et al., 2022; 2023; Huang et al., 2024). particular, we can assume without loss of generality that each coordinate of each point can be represented in log A bits of space, so that after normalization, all points lie within the grid [A] = (1,2,.... Ajd. Similarly, results by Braverman et al. (2022) can be adapted using the well-known merge-and-reduce framework to achieve (1 + eaapprooinotiion streaming algorithm for fair clustering using min()=_22+=) polylog nd words of space, which is also space-optimal up to polylogarithmic factors (Cohen-Addad al., 2022; Huang et al., 2024). Therefore, we ask:
=
Can achieve similar space-optimal results for fair clustering in the sliding window model?
Surprisingly, our first result is a strong impossibility result:
Theorem 1.1. Any algorithm for fair (k, cllusstrrig in the sliding window model that either achieves any multiplicative approximation or additive - error, with probability at least 2, must use ((n) space.
The proof of Theorem 1.1 utilizes tools from communication complexity and is fairly standard. Specifically, we show that fair clustering in the sliding window model can solve version of Augmented Index, where one player has a binary string x E {0, 1 of length 2n and weight n, while the second player has index i and must guess the value of v;, given the values of ;1,-.., Ti-1,
2

---

Published as a conference paper at ICLR 2025
as well message passed from the first player. The main intuition is that the two players copy Ti...., 2;-1 to the end of the stream, as well as guess 2; = 0, so that the sliding window contains 2 Z2, ......... 1 0. well as n additional points at the origin and n additional points at the point 1 on the real line, which the players subsequently insert. Now if the guess 24 0 is correct, this window will contain precisely 2n points that zero and 2n points that are one. Otherwise, it will contain 2n points that are one and 2n + 1 points that are zero. Hence by setting the fairness constraint require half of the points at each center to be from the last 2m points, and half of the points from the first 2n points, the fair clustering objective is zero if and only the guess z; = 0 is correct. Otherwise, the objective nonzero, which allows any finite multiplicative approximation to fair clustering to distinguish between these two cases. The lower bound then follows from known communication lower bounds of the Augmented Index problem. We defer the formal proof to Appendix A. We now discuss the main implications of Theorem 1.1.
precisely the elements I++1: I............................... P2n, 22n
Whereas our goal was to achieve (1 + appprxxiiia for fair clustering in poly (A: _. (og()))) space, Theorem 1.1 states that any multiplicative approximation requires linear space, even an arbitrarily large multiplicative approximation, e.g.. polynomial or exponential n.
Due to the aforementioned results, Theorem 1.1 shows several separations. Firstly, it shows separation between fair clustering and the standard clustering formulation in the sliding window model, due the sliding window algorithm for (k: =>-clutteiig that achieves (1 + apprroxiimtao using mintz polylog _ words of space (Woodruff et al., 2023), Secondly, it shows a separation between the insertion-only streaming model and the sliding window model for fair clustering, due to the streaming algorithm for (ke, 2)-cstrtri that achieves (1 + e)-approximation using mi polylog _ words of space (Braverman et al., 2022). Theorem 1.1 therefore has an important informal message:
&
Fairness and recency are not compatible in sublinear space!
The natural follow-up question is, what actually can be achieved toward some notion of fair clustering in the sliding window model? To that end, show that there exist sublinear-space algorithms for fair clustering in the sliding window model if we permit a small slackness on the fairness constraints:
There is a sliding- window streaming algorithu that returns a center set C after every insertion operation, such that with high probability, there exists ((1 - EE)=, (1 E)3)-fair k-clustering whose cost with center set C is at most 1 + times the optimal (a, 3f-rrrr clustering on the sliding window. This algorithm uses space L -poly(e log A) where L < 2 is the number of distinct combinations of groups that any point may belong to.
Theorem 1.2.
We remark that the guarantees of our algorithm are slightly stronger than those stated in Theorem 1.2. In particular, not only does our algorithm produce (1 ->approximaaionn to the optimal fair clustering, but it also produces& a (1 + e)-coreset i.e., a dataset that can be used to obtain a (1 + e)- approximation to the cost of any query consisting of k centers under the fairness constraints. To that end, we further remark that the space used by Theorem 1.2 matches the best known bounds for offline coreset constructions up to polylogarithmie factors (Braverman et al., 2022).
Experimental evaluations. Although the (1 +c) ratio which our Theorem 1.2 achieves is powerful, it mostly theoretical since the running time must be exponential because of -PX-hardssss. However, our algorithm actually maintains coreset of the sliding window whose construction is very efficient. Hence, we plug in practically efficient downstream approximation algorithm by Backurs et al. (2019) to achieve better empirical performance. We validate the performance of our algorithm, compared with three baselines, on five real datasets. Our algorithm offers overall best tradeoff' regarding time/space and accuracy compared with all baselines.
1.2 RELATED WORK
In this section, we describe number of related works, both in the context of fair clustering and sliding window algorithms for clustering.
Fairness. Fairness in algorithmic design has recently received significant attention (Kleinberg et al., 2017; Huang et al., 2019: Chen et al., 2024; Song et al., 2024). Chierichetti et al. (2017) initiated the study of fairness in clustering, specifically in the context of disparate impact, which demands that
3

---

Published as a conference paper at ICLR 2025
any "protected" subpopulation must receive similar representation in the decision maniing process, in particular by the output of an algorithm. Although Chierichetti et al. (2017) initially considered two classes of populations, subsequent works generalized to multiple subpopulations by Rösner & Schmidt (2018), 8), as well as different clustering objectives (Ahmadian et al., 2019; Bandyapadhyay et al., 2019; Bercea et al., 2019; Bera et al., 2019b; Kleindessner al., 2019b; Ahmadian et al., 2020b;a; Esmacili et al., 2020; 2021; Böhm et al., 2021; Schwartz & Zats, 2022; Ahmadian & Negahbani, 2023). A similar notion studied clustering where each cluster required certain number of representatives from each subpopulation, rather than a certain fraction (Anegg et al., 2022; Jia et al., 2022).
Other proposed notions of fairness include (1) social faimess, where the clustering cost is considered across subpopulations and then minimized (Jones et al., 2020; Ghadiri et al., 2021; Makarychev & Vakilian, 2021), (2) individual fairness, where each point should have center within a reasonably close distance that is a function of the overall dataset (Jung et al., 2020; Mahabadi & Vakilian, 2020; Negahbani & Chakrabarty, 2021; Vakilian & Yalçiner, 2022), (3) representative fairess, where the number of centers of each class is constrained (Kleindessner et al., 2019a; Angelidakis et al., 2022), and (4) number of other notions (Micha & Shah, 2020; Abbasi et al., 2021; Hotegni et al., 2023; Gupta et al., 2023). However, as we focus on disparate impact in this work, these notions of fairness somewhat orthogonal to the main subject of our study.
Clustering in data streams and the sliding window model. While a general framework for sliding window algorithms are histogram- based approaches (Datar al., 2002; Braverman & Ostrovsky, 2007), the clustering objective is not smooth and thus not suitable for these frameworks. Hence, there has been an active line of work studying (k, z)ccusttein the sliding window model. Babcock et al. (2003) first introduced an algorithm for k-median clustering in the sliding window model that used O (5m2 log" m) words of space and gave 20(1/)) -mull//ilmulilicattiiee approximation algorithm, where m is the size of the window and E E (0. :)) is an input parameter. Braverman et al. (2015) subsequently gave a bicriteria algorithm for the k-median problem in the sliding window model that achieved an O (1) multipiipliea approximation using A²2 polylog(m)) space, but at the cost of 2k centers. Braver- man et al. (2016) achieved the first poly(k log m) space algorithm for k-median and k-means on sliding windows, achieving an O (1) (I)-appoxximation using O (k3 log 6 m) space. Afterwards, Borassi et al. (2020) achieved a linear dependency in h. giving an O -t>-appooximtoion for k-clustering using k polylog(m, A) space. Epasto et al. (2022) introduced the first (1 + -aapproximation algorithm for [kd+td")
(k, =>-clssterigg using 23 was subsequently optimized by Woodruff et al. (2023) to 22+t polylog mA words of space.
polylog (m, A, !) words of space, for some constant C' 2 7, which
k
It should noted that all of these results consider the standard formulation of (ks cluusterin in the sliding window model. That is, no previous works considered fair clustering in the sliding window model. The most relevant works are offline (1 + e)-coreset constructions by Braverman et al. (2022) for fair clustering that sample min(e".e2- polylog e points, and can be adapted to the insertion-onle -nlly streaming model at the cost of multiplicative factors polylogarithmic in n, using a standard werge-and-reduce technique. As this coreset size matches the bound for (A,, 2)-clustering in the sliding window model, one might hope to achieve similar bounds for fair clustering in the sliding window model. Unfortunately, our results show that is not the case.
PRELIMINARIES
Notations. We assume the input comes from [A] for some integer A 2 1, and let C C IRd be the candidate center set. In our analysis, many statements also hold for general Rd, but we may still state them for [A] for consistency of presentation. Throughout, when we talk about a point set in Rd, we assume each point associated with a unique time step. Importantly, we use this time step to identify a point, which means two identical points in Hd with different time steps are considered different points (and set operations, such as intersection, are performed with respect to the time step). For a general function f: U + V, define f(Y): == Eyer f(v) (for Y C U in the domain U).
Definition 2.1 ((a, fair clustering). Given P C TRd, l groups Pi,..., Pe C P and 3 E 10, 175, k-clustering (Ci...., Ck), i.e., k-partition of P, is called (a, fair if IP,ncal [ay, 8,], every [c.
4

---

Published as a conference paper at ICLR 2025
i E j E [4]. (a, fair (ke (.,22-CCUUU -LUUSTERRER asks to find an (a, B)-fair clustering (C1, Ck) and center set C' C R of k points, such that EiE[M] Exec, (dist(z, c))) is minimized.
Notice that there are at most 2 possible combinations of groups that point p E P may belong to. In practice, this 2 upper bound is rarely achieved. Hence, it is often useful to consider the actual number of distinct combinations of groups that point p E P may belong to, denoted L throughout. Namely, L = kW S [4] 3p E P. such that vjj E W. p E P/H.
Streaming model. The window size m and the fairesss constraints a, 3 E Re are given in advance. The input point set p S [ and the groups , Pt _ P of (a, 3)- clustering is presented as a stream of insertion operations, each consists of a point p E P and the group IDs that belongs to. The algorithm must return a center set C C Rd after each insertion, which is supposed be an approximate solution to the dataset defined by the last m operations.
weighted point set S C [A] is a point set S equipped with a weight function ws | R+ such that supp(us; (ws) = S. Notice that for weighted point set S and a (weighted or unweighted) point set T, set operation S n T is performed only on the point set, and the weight should be defined separately. When the context is clear, we drop the subscript S in the weight function ws.
We use a generic notion of assignment-preserving which we rephrase follows. We notice that ussignment-preservin coresct that preserves the fair clustering objective, but it is possible to obtain one by taking a union of several pesserient-rreeervingg coresets a partition of the input dataset (and the detailed argument can be found in Section 4, proof of Theorem 1.2).
coresets as introduced Braverman et al. (2022),
coreset is not immediately
Definition 2.2 (Assignment constraints). Consider some weighted point set P [A]d dd and center set C C C. An assignment constraint with respect to P and C is function I C - R+ such Eoec ['cc.. An assignment function with respect to P and C is a function P + R+ such that Vp E P. P.E.cc op, = =wp(p). We call a consistent with I, i.e. T. if E C. EpEP (pp c) = [(c).
that EpEp wp(p)
Definition 2.3 ((k. z)-clustering with assignment constraints). Given a weighted point set P S [A]] a center set C C and an assignment constraint r, for every assignment function a with respect to P. C and consistent with 1,, the cost of a is defined cost" (,,,, Eppp Ecec o c)d(p, c)². The cost function (K. --LULUEEEIING with assignment constraint is
min cost cost(P, D)C o: o:PXC=3,.nD a
cost (P,
As in Braverman et al. (2022); Huang et al. (2023), our coreset is defined with respect to assignment constraints, and aim for coresets that can preserve all assignment constraints simultaneously.
Definition 2.4 (Assignment--reeerviing coreset). Given weighted point set P C [A] and 0 < é < 1, an Dessgimmntt-rreeerinn E-coreset for (k, CLLSSTRTRG of P is a weighted point set S P such that wg( ws(S) (S) (P), and that for every center set C C C and assignment constraint r, cost (S, C)T) E (1 ee) (P,
ONLINE ASSIGNMENT-PRESERRNE CORESETS
As we mention, our framework is based on that of Woodruff et al. (2023), which reduces the sliding window algorithm to constructing an online coreset. In their definition, given a point set P = P2.,P2..... ... Pa). listed in the increasing order of time steps, an online s-coreset S for (k, 2)- CLUSTERING is a weighted subset such that every prefix S U (P1, Pi} is an e-coreset for (k, CLUSTERRNN of prefix fp1.P2....,pe )P.).
However, this definition of online coreset does not easily generalize to our setting, and it is even trickier due to our lower bound in Theorem 1.1. Hence, we need use a slightly relaxed notion, coresets
defined in Definition 3.1. Roughly, the prefix property of our online feiigmment--reserviii can tolerate a + æ relative error in the weights. This relaxed guarantee leads to an efficient coreset. bound, stated in Lemma 3.2, which is the main claim of this section.
Definition 3.1 (Online assignment-presset preserving coreset). Given a weighted point set P = (p..P,......1 } listed in the increasing order of time steps and 0 < 1, weighted point
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 Online asiignment-preserving coreset construction
procedure ONLINECORESET((::: 6)
Compute an (a, -ppppoxxiee solution Q = {qi, ,2....,......................... ge) C P for -lusstrn of busing e.g., Meyerson sketch, where O(2²). 3 O(2 poly(log A))
S + 0 f- Ta 8' [[1a(Avd)+11)
8
for i = 1. do
Qi (p E P: NNO 4:) (p) is defined as the nearest neighbor of in set Q
for j 0, 1,2..... [g(Av do
P.j - P; P.n 21-1,27)
S. f (..CCR
return U UISIStoS/STT<AAVn) Sijj
Algorithm 2 Coreset for single ring
procedure RiNGCORESET(P,E,
List P in the increasing order of time steps as pr, .h.P......PP.
8' (k/e))owa)>> T t p2 dkk Nog(w(P)As -))-)))-1)))_ 2, sumg 0
for i 1.2..... n do sum; sum,-1 + wp(p:)
prob; + min (T' (p:)) /smm,,
add p, to S with probability prob, and weight wp(p))) < -prob, (lob;)-p((p))) return S
set S is online ferignmentt-reservvinn s-coreset of P for (ke, --LUSTERRR, if P and for every L E [n]. there exists some weighted point set Sy such that the following holds:
Let P: = (PI,-..,Pe) and wp, p - wp(p). Then St. is assigument-preservne e-coreset for the weighted set Pt-
Let S, == S Pt and ws, : p + ws(p). Then St and for every p S, ws, (p)
(1 + (c)ss)p)).
Lemma 3.2. There exists algorithm that takes input weighted set P C [A]d (with unique time steps) of n points, < < 1, 2.22. 1 and integer k 2 computes weighted set with |S] = (2 kd (og(w())e=T)) such that $ is online assignmment-preservinn e-coreset for (k) CLUSTERING with probability 0.9. The algorithu uses poly hnd (olloo((((() (P) space.
kd
coreset is listed in Algorithm This construction based on similar sampling-bast based framework as in Woodruff al. (2023), which is also widely used in the coreset literature in general (Chen, 2009; Cohen-Adde Addad Li. 2019; Braverman et al., 2022). In this framework, one starts with computing a bi-criteria approximation Ô for (unconstrained) (k, 2) CLLUSTERING denoted as Ō = (G..... G.). We say Ö is an (a, (9) bi-criteria approximate solution for (unconstrained) (k, 2)- CLUSTERING if cost( P, C)= Epep dist(r, Ō)= I a- OPOPT and [č] < Bk. For purpose, the Meyerson sketch proposed by Borassi et al. (2020) that outputs an (O (2²) O (2 log log A)) approximation center set Ō ç P with probability least y7. Next, take the natural clustering defined by Ò (according to nearest- neighbt rule), and decompose each cluster into rings centered at C. The coreset is constructed by simply drawing (o poly(c=kk)) uniform samples from each ring, re-weight, and take the union.
Algorithm for Lemma 3.2. The algorithm for our online assignment-preserve
et al., 2021; Cohen-Addad
However, it is nontrivial to draw exactly uniform samples while still maintaining the online property, especially in the streaming setting. Hence, in Woodruff al. (2023) they turn to sample the i-th element in ring with probability 1/i (and it gets more complicated when running on a weighted dataset, which we need). Our algorithm also has this part as key subroutine, which we call RINGCORESET. The RINGCORESET algorithm is presented in Algorithm 2, and its guarantee is summarized in the following Lemma 3.3.

---

Published as a conference paper at ICLR 2025
Lemma 3.3. Consider 9 E [A] > E, E (0.1),k, 2 1, and weighted set P (p1, ........PPP. Pn)) S | n ring(g.r/2.r) listed in the increasing order of time steps. Ler N := w(P) and S be the output RINGCORESET(P, (in Algorithm 2). We have E||s|] poly(2*ke" (og(NAe-16-1) and with probability at least 1 - 6, there exists weighted set S such that
=
For every p S, ws (p) (1 + e)ws(p),
For every center set C C R |C| S k and every assignment constraint I with respect to P, C, we have cost((S', ,,,) cost (P. c,r)l s {cost(( C.T) + cost(S',C.I) Nr*).
The proof of Lemma 3.3 is postponed to Appendix C, and we first finish the proof of Lemma 3.2 assuming Lemma 3.3 holds. In the following discussion, for every P [A] , C C Rd |C| = k and assignment constraint I with respect to P. C, we say 0² is the the optimal assignment function of cost (o, if arg Px0::
Eper Ecec Epp c) dist c).
Proof of Lemma 3.2. By the definition of Algorithms 1 and 2. we have ONLINECORESET(() n (p1, (P1.P2..... P2. PP) ONLINECORESET( (PI:22.- . .P)) when the randomness is fixed. Hence it is sufficient to show that for every P, there exists some ssiignment-reserving coreset S' of such that S S and for every p S", ws (p) (1 + ())s(p).
Let a, result of Lemma 3.3, with probability at least - 8, for every S i S 8,0 j < [log( (V)()))), there exists a weighted point set Sy,, satisfying S = Sky. Vp E S/,j. wst (p) (1 = e)ws,, (p).
P.. follows their definition Algorithm By applying the union bound on the
such that for every center set and assignment constraint I with respect Pt,j C, we have
cost(S C,T) cost(Pi.j I)
(Pas))) + E' _ (cost(S)) C,T) + wp(p) dist(p. qi)² + (cost( + costP,,,,C,,
< 4a
Σ
PEP
Let weighted set S" be the union of all 5 Let o be the optimal assignment for cost(P, We fix the assignment constraint for every P.ς with (c) = Eper,, o² (p.c). c). Define NR == [l(AAd] as the number of rings. We have cost(P, C,T) = cost" (P,C,I)= = E Σnn cost(P.., c,I,,) and (S' ,),, < E Σner cS riz) Summing up together, we have
Nu
rost(S,,c,1) I,,
Na cost(S C,T.,) -ost C,1,,))
dist(p q:)² _ (coot((S' C,I) + (ost(P,,,,,))
4a
1
1= pEP:
S cosl. + (ost(PP,C,T)) cost((", CCT))
4a
S e cost(P,
where costo denotes the cost of solution Q. By symmetric argument we have cost C,T) cost(S' C,1') < e cost(P, C, 1). The expectation size of the coreset can be bounded by
NR
E|Sl|| =
S S 3k Ig(Avd) poly(2 dke dok log (og(u(()Ae--t-1))
i= 0=
polyy22 dks
log( w (P
In summary, when we run ON e, 0.01), it returns an online assignment-preseet e-coreset S such that |S| poly dke (og(w(P)A2 -18 (1---1) with probability 0.9.
7

---

Published as a conference paper at ICLR 2025
Table Specifications of datasets
dataset
size
d
attribute
window size
coresct size (benchmark)
coresct size (ours)
Adult
50k
6
gender
500
231
150
Bank
45k
10
marital
500
234
150
Diabetes
100k
gender
1000
485
300
Athlete
200k
gender
2000
1058
750
Census
2500k
13
gender
5000
1988
1500
STREAMING ALGORITHMS
Our sliding window algorithm framework introduced by Braverman al. (2020); Woodruff et al. (2023). This framework reduces clustering on sliding windows to an online coreset problem, via a standard werge-and-reducs algorithm maintains a coreset for the sliding window, and its guarantee is summarized in Theorem 4.1. The key idea is that every window can be viewed as a suffix of the input stream at some time step f, and if we build online coreset for all elements in the entire I.....f time steps in the reverse order of time steps, then the prefix of the online coreset (which is the key query that the coreset provides) precisely gives a coreset for the sliding window.
method, and the detailed algorithm listed in Algorithm 3. This
Algorithm 3 Sliding window coreset algorithm based on online assignment preeeeevn--- coreset
procedure MERGEANDREDUCHE(P)
t 0, < [1g m]
sets initialize + point sets Bo. .I.... + Ø
while input stream not empty do
( < 1
p f- the next element in input stream, timel(p) --
ponline coresets is defined on the reverse stream
let j be the smallest index with B, = 2, set f- m if such index does not exist
By + ONLINECORESET {p) Bo U... U.... 2 m 2mn
clear the block B,, i.e., BN < Ø, for all E (0.1...... 1} the coreset of the current window (i.e. the f
1, m + 1-th element in input
stream) is {p E Bg U B1 U... Be time(p) E ([+,-1+m) m)}
Theorem 4.1. There exists an algorithm that takes as input P C [ presented as point stream, < < 1 2 1, integer k Z and window size m 2 computes a weighted subset of the sliding window after each point insertion, such that there exists e-coreset S' of the sliding window for (k, 2)-CCLSTTRIIN with assignment constraints, that has (1 E1 (p). The algorithm uses space poly(E 1a led log( (od((gm))) A))), and succeeds with high probability.
and Vp S, ws(p)
Proof. Consider Algorithm 3. Observe that for each i (0, I,.... l). B; an assignment--rreerviini online ((1 + 2logm ) co-crsttt for sequence of 2' consecutive points and the sequences of all B, (i E {0, 1, ... e}) are disjoint. Every time set B, ONLINECORESET((O) U Bo .... 5
By-1, 2log 2m By, B,.... B,-1 must be non-empty. By induction, {p) U U.....UBB ..
1+ -+ 2 2$ and the distortion of B, is at most (1 + 21og )
Suppose the input stream is (pt)-21 For every time after we have inserted the newly arrived point Pt. Bo B U...UB.. UB is an peeegnmmnnt-peeeeviine online e-coreset of {Pt, Pt-1..... "ttt--s...,Pp.-ee Pr-24+ (sorted by time steps). By the definition of online coreset, {p BBUB, U..UUBB time(p) is an assignment preservvni e-coreset of {Pt. Pt-l..... Pt-m+11 most 2 times of merge-and- -ed-uc is involved Bo U... B,-1. the failure probability for each time is at most 5. This finishes the proof of Theorem 4.1.
.UB
[-t, (t+m)
+11 }. which is the current window. Since
Proof of Theorem 1.2. Our algorithm employs the following standard steps obtain fair clustering from assignment prepett--reeeeiingg. coresets. Huang et al. (2019); Braverman et al. (2022) shows that, if dataset P is partitioned with respect to the combinations of groups that each point belongs to, and
8

---

Published as a conference paper at ICLR 2025
Ours
Benchmark
Uniform baseline
Borassi baseline
1.6 "300
Cost evaluation for Adult dataset
1.4
1.2
1.0
0.8
0.6
step
Ours
Benchmark
Uniform baseline
Borassi baseline
Cost evaluation for Bank dataset
objective velue
1.0
0.8
0.6
0.4
0.2
5000
10000
15000
20000
25000
30000
35000
40000
time step
Ours
Benchmark
Uniform baseline
Borassi baseline
Cost evaluation for Diabetes dataset
objective valuve
1.6
1.2
0.8
20000
40000
63000
80000
100000
time step
Ours
Benchmark
Uniform baseline
Borassi baseline
3.5 218
Cost evaluation for Athlete dataset
Objective value
2.5
2.0
25000
50000
75000
100000
125000
150000
175000
200000
time step
Ours
Benchmark
Uniform baseline
Borassi baseline
Cost evaluation for Census dataset
1.75
1.50
1.25
1.00
0.75
0.50
0.25
500000
1000000
1500000
2000000
2500000
time
Fig. 1: Fair k- 4-MEDIAN cost curves for all datasets.
suppose one takes the union of the assignment-pressee preserrinreeeeeeeeeeeee e-coresets on each part, denoted as S, then the value of the optimal (o,, faarr clustering on S is (1 Epapproxinnttion to that of P.
Our algorithm. Our algorithm follows similar steps. We apply Theorem 4.1 on the partition of P. then take the union to obtain some set S". This S" has size most L. times that of the coreset

---

Published as a conference paper at ICLR 2025
Total execution time
Addh
113
Oues
Bonasii baseline
Dabetes
53
152.77
Caness
U80 36
Execution Time (scounds)
Fig. 2: Total running time for our algorithm and Borassi baseline over all sliding windows.
size in Theorem 4.1, and this dominates the space complexity. Finally, in the last step we find ((1 e)), (1 + 8) clustering S' (which has relaxed fairness constraint).
To see why this clustering has value at most (1 + E) times the optimal (a, 33-rfir clustering on P. consider the optimal (a., fair solution on S (the set defined in the first paragraph), then this solution (1 + +1++)--pppp --approxiiatte to that on P. Now, by the guarantee of Theorem 4.1, this same solution (with the same objective value) is feasible ((1 - s)xx, (1 --firr clustering with respect to St. Notice that what our algorithm finds no worse than this solution on S', and hence we conclude the clustering has cost at most (1 + =) times the optimal solution. This finishes the proof.
EXPERIMENTS
We implement our coresets and evaluate their performance for solving fair k-MEDIAN in sliding window. The evaluation requires down-stream approximation algorithm for fair k- k-MEDIAN which is run the coreset. We choose to use Fairtree (Backurs et al., 2019) in our experiments, which achieves competitive performance practice.
Baselines. We employ three baselines. Two of the baselines are based on coresets, called "Benchmark" and "Uniform", which construct the coreset in an alternatively way than ours but still apply Fairtree as the down-stream approximation algorithm. Specifically, in "Benchmark", large coreset from the sliding window (see Table for the coreset sizes), and serves as a benchmark for the accuracy; and in "Uniform", ours, as a natural heuristic. The last baseline is previous sliding-window window algorithm designed for clustering without fairness constraints (Borassi et al., 2020), and we call it "Borassi".
construct a considerably
uniform sampling build coreset of the same size as
Datasets. We evaluate the algorithms on 5 real datasets: Adult (Becker & Kohavi, 1996), Bank (Moro S & 2014), Diabetes (Kahn), Athlete (Barshan Altun, 2010), and Census (Meek et al., 2001), which have also been used in various previous studies on (fair) clustering (Bera et al., 2019a; Chierichetti et al., 2017; Schmidt et al., 2018; Huang al., 2019). For each dataset, extract numerical features to construct a vector in IR for each record, and we select a binary sensitive attribute. We set the window size
x2 We list the detailed parameters of the datasets Table 1.
100
Experiment setup. We choose k = 10 in all experiments. When implementing our coreset, we directly specify a target coreset size instead of using the worst-case bound as we established in previous sections. Due to variations in dataset sizes and corresponding window sizes, we assigned different coreset sizes for each dataset.
We set this target size 150 for both Adult and Bank, 300 for Diabetes, 750 for Athlete, and 1500 for Census. All the experiments are run on a MacBook Air 15.3 with an Apple M3 chip (8 cores, 2.22 GHz), 16GB RAM, and macOS 14.4.1 (23E224).
Experiment results. We run all algorithms on the five datasets, and we depict the cost curves in Figure I over the time steps. These curves show that our algorithm obtains comparable cost to Benchmark and Uniform, while using lower space than Benchmark and achieving lower variance than Uniform (which is expected, since the variance of uniform sampling even without fairness constraints). Finally, compared with Borassi, our algorithm performs better in accuracy, and as can be seen from Figure 2, we also achieve better running time larger datasets.
be unbounded
10

---

Published as a conference paper at ICLR 2025
ACKNOWLED
Research of Shaofeng Jiang was supported in part by a national key R&D program of China No. 2021 YFA 1000900 and startup fund from Peking University. Samson Zhou is supported in part by NSF CCF-2335411 1. The work was conducted in part while Samson Zhou was visiting the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program. We thank the anonymous reviewers for insightful comments.
REFERENCES
Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In FAccT '21: 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 504-514, 2021.
Sara Ahmadian and Maryam Negahbani. Improved approximation for fair correlation clustering, In International Conference on Artificial Intelligence and Statistics, pp. 9499-9516, 2023. 4
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD, pp. 267-275, 2019.
Sara Ahmadian, Alessandro Epasto, Marina Knittel, Ravi Kumar, Mohammad Mahdian, Benjamin Moseley, Philip Pham, Sergei Vassilvitskii, and Yuyan Wang. Fair hierarchical clustering. In Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS, 2020a. 4
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Fair correlation clustering. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 4195-4205, 2020b.
Georg Anegg, Haris Angelidakis, Adam Kurpisz, and Rico Zenklusen. A technique for obtaining true approximations for k-center with covering constraints. Math. Program., 192(1):3-27) 2022.
Haris Angelidakis, Adam Kurpisz, Leon Sering, and Rico Zenklusen. Fair and fast k-center clustering for data summarization. In International Conference on Machine Learning, ICML, pp. 669-702, 2022. 4
Apple. http:///ngg.aapppcccmmmrrrr/eees
Diivacy-Overview.pdee
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In Proceedings of the Twenty-first ACM SIGACT-SIGMOD SIGART Symposium Principles of Database Systems, pp. 1-16, 2002.
Brian Babcock, Mayur Datar, Rajeev Motwani, and Liadan O'Callaghan. Maintaining variance and k-medians over data stream windows. In Proceedings of the Twenty-Second ACM SIGACT: NIGMOD-SIGARY Symposium Principles of Database Systems, pp. 234-243, 2003. 4
Arturs Backurs, Piotr Indyk, Krzysztof Onak, Baruch Schieber, Ali Vakilian, and Tal Wagner. Scalable fair clustering. In International Conference on Machine Learning, pp. 405-413. PMLR, 2019. 3,
10
Sayan Bandyapadhyay, Tanmay Inamdar, Shreyas Pai, and Kasturi Varadarajan. A constant approximation for colorful k-center. In 27th Annual European Symposium on Algorithms, ESA, pp. 12:1-12:14, 2019.
Billur Barshan and Kerem Altun. Daily and Sports Activities, UCI Machine Learning Repository, 2010. DOI:
10
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI:
hups://doi.org/100 wttp:/i..rrr111224221. 0.24432/C5XX22. 10
Suman K Bera, Deeparnab Chakrabarty, and Maryam Negahbani. Fair algorithms for clustering, corr,
abs/1901.
tos//9901.02933. 02393.. arXiv preprint 1001002300002999 2019a. 10

---

Published as a conference paper at ICLR 2025
Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Advances in Neural Information Processing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurIPS, pp. 4955-4966. 2019b. 4
Ioana Oriana Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, volume 145 of LIPlcs, pp. 18:1-18:22. Schloss Dagstuhl Leibnniz-7ennrrum für Informatik, 2019.
Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private 1z- heavy hitters in the sliding window model. In The Eleventh International Conference on Learning Representations, ICLR, 2023. 2
Matteo Böhm, Adriano Fazzone, Stefano Leonardi, Cristina Menghini, and Chris Schwicgelshohn. Algorithms for fair k-clustering with multiple protected attributes. Oper. Res. Lett., 49(5):787-789 2021. 4
Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghad- dam. Sliding window algorithms for k-clustering problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020. 4, 6, 10
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Proceedings, pp. 283-293, 2007. 2, 4
Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering on sliding windows in polylogarithmic space. In 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS, pp. 350-364, 2015.
Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering problems on sliding windows. In Proceedings of the Twenty-Sevente Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1374-1390, 2016. 4
Vladimir Braverman, Elena Grigorescu, Harry Lang. David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Techniques,APPROOIE APPROX/RANDOM, pp. 7:1-7:22,
2018. 2
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61 IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 517-528, 2020.
8
Vladimir Braverman, Viska Wei. and Samson Zhou. Symmetric norm estimation and regression on sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, pp. 528-539, 2021. 2
Vladimir Braverman, Vincent Aaden-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 462-473, 2022. 2, 3, 4, 5, 6, 8,
Jiecao Chen, Huy L. Nguyen, and Qin Zhang. Submodular maximization over sliding windows. CoRR, abs/1611.00 1.00129, 2016. 2
Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923-947, 2009. 6
Wenjing Chen, Shuo Xing. Samson Zhou, and Victoria G. Crawford. Fair submodular cover. CoRR, 0is/24007.08044, 2024.
12

---

Published as a conference paper at ICLR 2025
Anshuman Chhabra, Karina Masalkovaite, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 9:130698 -300200, 2021.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 5029-5037, 2017. 1, 3,4,, 10
Fan R. K. Chung and Lincoln Lu. Survey: Concentration inequalities and martingale inequalities: doi: 10. 10.100///422751.222 10129115. URL
A survey, Internet Math., 3(1):79-127, 2006.
hetps://doi.oor
10129115. 25
Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In
ICALP, volume 132 of L/Plss, pp. 41:1-41:14, Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019. full version: https: arxiv. org/ abs 14129. 20
Vincent Cohen-Addad, David Saulpie, and Chris Schwiegelshohn. new coreset framework for clustering. In STOC, pp. 169-182. ACM, 2021. 6
Vincent Coden-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In STOC '22: 54th Annual ACM SIGACT Symposium Theory of Computing, pp. 1038-1051, 2022.
Vincent Cohen-Addad, David P. Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log n) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 883-908, 2023.
Mayur Datar and Rajeev Motwani. The sliding-window computation model and results, 2016.
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput., 31(6):1794-188 2002. 2,4
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science, pp. 214 226, 2012. 1
Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam. Submodular optimization over sliding windows. In Proceedings of the 26th International Conference on World Wide Web, WWW, pp. 421 430- 2017. 2
Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. Improved sliding window algorithms for clustering and coverage via bucketing- sketches. In Proceedings of the 2022 ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 3005-3042, 2022.
Seyed A. Esmaeili, Brian Brubach, Leonidas Tsepenekas, and John Dickerson. Probabilistic fair clustering. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS, 2020.
Seyed A. Esmaeili, Brian Brubach, Aravind Srinivasan, and John Dickerson. Fair clustering under a bounded cost. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS, pp. 14345-1438 2021. 4
Facebook. https//wwww.ficcooo.cmm/pllyyyyp
2
Mehrdad Ghadiri, Samira Samadi, and Santosh S. Vempala. Socially fair k-means clustering. In FAccT '21: 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 2021. 4
Google. https://pbiceegggogge...omccccch goggl...m//cchoooogssseeennn.... 2
Shivam Gupta, Ganesh Ghalme, Narayanan C. Krishhan, and Shweta Jain. Efficient algorithms for fair clustering with new notion of fairness. Data Min. Knowl. Discov., 1959))1959-1999 2023.
Sèdjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. International Conference on Machine Learning, ICML, pp. 13270-13284, 2023. 4
13

---

Published as a conference paper at ICLR 2025
Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with faimesss constraints. In NeurIPS, pp. 7587-7598, 2019. 3, 8, 10
Lingxiao Huang, Shaofeng H.-C. Jiang, and Jianing Lou. The power of uniform sampling for k-median. In International Conference Machine Learning, ICML, pp. 13933-13956 2023.
Lingxiao Huang. Jian Li, and Xuan Wu. On optimal coresct construction for euclidean (k, z)- clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, pp. 1594-1604 2024.7 2
Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '22 International Conference on Management of Data, pp. 29-40,
2022. 2
Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorful k-center clustering. Math. Program., 192 (1):339-360, 2022. 4
Matthew Jones, Huy L. Nguyen, and Thy Dinh Nguyen. Fair k-centers via maximum matching. In Proceedings of the 37th International Conference Machine Learning, ICML, pp. 4940 4949, 2020. 4
Christopher Jung. Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness center location. In Aaron Roth (ed.), 1st Symposium on Foundations Responsible Computing, FORC 2020, pp- 5:1-5:15, 2020. 4
Michael Kahn. Diabetes. UCI Machine Learning Repository. DOL: 400..ttts///bbboog//22233331//10 10
Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS, pp. 43:1-43:20 30
Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 3448-3457, 2019a. 4
Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstem. Guarantees for spectral clustering with fairness constraints. Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 3458-3467, 2019b. 4
Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. Comput. Complex., 8(1 j:21-49 1999. 15
Lap-Kei Lee and H. Ting. Maintaining significant stream statistics over sliding windows. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 724-732, 2006a. 2
Lap-Kei Lee and H. F. Ting. A simpler and more efficient deterministic scheme for finding frequent items over sliding windows. In Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGARTT Symposium on Principles of Database Systems, pp. 290-297, 2006b. 2
Sepideh Mahabadi and Ali Vakilian. Individual faimess for k-clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML, pp. 6586-6596, 2020.
Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering. In Conference on Learning Theory, COLT,, pp. 3246-3264, 2021. 4
Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. Proc. VLDB Endow, 5(12):1699, 2012.
Chris Meek, Bo Thiesson, and David Heckerman. US Census Data (1990). UCI Machine Learning Repository, 2001. DOI:
httpooooorrrrr.2222////5544 10
Adam Meyerson. Online facility location. Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 426-431. IEFE, 2001. 17
14

---

Published as a conference paper at ICLR 2025
Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In 47th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 85:1-85:16, 2020. 4
Rita P Moro S and Cortez P. Bank Marketing. UCI Machine Learning Repository, 2014, DOI:
10
Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k-clustering- In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informa- fion Processing Systems 2021, NeurIPS, pp. 13340-13351, 2021.
Odysseas Papapetrou, Minos N. Garofalakis, and Antonios Deligiannakis. Sketching distributed sliding-window data streams. VLDB J., 24()):45-368, 2015. 2
Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In 45th International Colloquium Automata, Languages, and Programming, ICALP, pp. 96:1-96:14, 14, 2018.
Melanie Schmidt, Chris Schwiegelshonn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means clustering. arXiv preprint urXiv:/8/22 10854, 2018. 10
Roy Schwartz and Roded Zats. Fair correlation clustering in general graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 37:1-37:11 2022. 4
Zhao Song, Ali Vakilian, David P. Woodruff, and Samson Zhou. On socially fair low-rank approxi- mation and column subset selection. Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS, 2024. 3
Ali Vakilian and Mustafa Yalçiner. Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 8758 1758-8779, 2022. 4
Zhewei Wei, Xuancheng Liu, Feifei Li, Shuo Shang. Xiaoyong Du, and Ji-Rong Wen. Matrix sketch- ing over sliding windows. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference, pp. 1465-1480. ACM, 2016." 2
David P. Woodruff and Samson Zhou Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1196, 2021.
David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding window model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS, 2023. 2, 3, 4, 6,
A LOWER BOUNDS
In this section, show that fair clustering cannot be performed in the sliding window model in sublinear space, up to any finite multiplicative error.
We first define the one-way two-party augmented indexing communication problem. Formally, in the Augind, problem, Alice receives a vector e E {0, 13" and Bob receives an index i E [m]. as well as the values of Uj, U;-1- The goal is for Alice to send some message II to Bob, that Bob may 3. We recall the following communication complexity lower bounds for the augmented indexing problem.
compute v with probability at least 2
Theorem A.1. (Kremer et al., 1999) Any protocol that solves Augind, with probability at least 2 requires (m)) bits of communication.
We now show that the augmented indexing communication problem is hard even if it is promised that half of the entries of Alice's 's imput vector are nonzero. Formally, in the Augind problem, Alice receives vector E 1), which has exactly n nonzeros, and Bob receives index E 22], as well as the values of v,...., U;-1. The goal is again for Alice to send some message II to Bob, so that Bob may compute i with probability least 2
15

---

Published as a conference paper at ICLR 2025
Corollary A.2. Any protocol that solves AugInden with probability at least requires (2()) bits of communication.
Proof. Suppose there exists protocol II that solves Augind with probability at least 2 Given an instance of AugInd
3. the number of nonzero entries Alice's input vector o {0, 13 Then Alice create vector {0, 1 with exactly nonzeros by appending to a total of n coordinates that are 1, followed by s coordinates that are Since the number of nonzero entries in v is and Alice appends n nonzero entries afterwards, then follows that has exactly nonzero coordinates. Alice and Bob can then run the protocol II for Augind on u to find u4 where E [n] is the input to AugInd.. 2. By construction, we have u4 ey and thus the protocol solves AugInd, with probability at least 3. due to the correctness of II. Hence, II requires M(n) bits of communication by Theorem A.I.
We now prove our lower bound for fair clustering in the sliding window model.
Theorem 1.1. Any algorithu for fair (k, cluusterrn in the sliding window model that either achieves any multiplicative approximation or additive error, with probability at least z. must use (n)) space.
Proof. Let v E {0, 1)2n 2m with exactly n nonzero entries and i [2n] be an input to Augind Alice creates an instance of fair (k, =llusterii on IR, with k = 2. There are two groups C1, C2. The fairness constraint that every cluster should contain at least 0.5-fraction of points from Cz. For each i E [2n]. Alice adds point at U; A, all points in sequence (including those points which are defined later) belong to C1. There are exactly n points at the origin and exactly n points at A. Alice then creates stream S by inserting the points T1, ................................ I2n in order.
2n-
Let II be any algorithm for fair (k, 2)-clustering in the sliding window model, with window size 4n. Alice then runs II on S and passes the state of the algorithm to Bob, who has Vi..... 8 and thus also ,1....,;;--. I1 Bob sets F2n+j = Ij for E i stream. Then Bob sets T2n++ 0 and inserts the point into the stream. Finally, Bob inserts points that are located at the origin and belong to C2, another n points that are located at A and belong C2. By construction, the active points in the window are precisely the 2n points from C₁, i.e. Ti+1...... T2n+i and 2n points from C2.
and inserts the points into the
Since all points are located at {0, A}, the optimal center set is {0. A}. The number of points from C1 that are located at the origin equals to Hti E [i + 1, 2n + i] I, = 0}| = n + I [ = 1).
If x; = 0. then both location 0 and A contains points from C₁ and points from Cz. The optimal solution to assign every point p to the center at the same location as p, which requires zero cost.
points from C1 and n points from C2. In the optimal solution, either one of the points from C₁ and located at is assigned to center A, one of the points from C2 and located at A is assigned to center O. For either case, the cost of optimal solution is no less than A.
If r, then location 0 contains
Thus if IT achieves either any multiplicative approximation or additive error ă - with probabil- ity at least 3. then II can distinguish between these cases, thereby solving Augind Hence by Corollary A.2, II uses 1(2) bits of space.
We can slightly modify the proof of Theorem 1.1 to obtain a lower bound of arbitrary additive violation 8.
Theorem A.3. Any algorithm that, with probability least 2/3, either achieves any multiplicative approximation or additive A/2 error, even using 8 additive violation in the fairness constraints must use (nn/6) space.
Proof. Using the construction in the proof of Theorem 1.1, we can obtain a point sequence of length ]. such that any algorithm for fair (k, cllusttrii in the sliding window that either
J.
16

---

Published as a conference paper at ICLR 2025
achieves any multiplicative approximation or additive 4/2 1 error on instance A with probability at least 2/3, must use ((n/6) space.
Next construct sequence B by repeating cach point in A for ò + 1 times, i.. B (A1: Al....,A A2...., A2, + A,....,AA
In the proof of Theorem 1.1, we reduce AugIndz, to fair clustering in the sliding window by running the fair clustering algorithm on A to distinguish zeros (æ is defined the proof). Now suppose we have a fair clustering in the sliding window algorithm A which outputs solu- tion with most additive violation and at most A/2 1 additive error (to the optimal solution with no violation). Similar to the proof of Theorem 1.1, we can also distinguish whether window (I++11 2 I2n+i-1, 0) has a zeros or n + zeros by running A on B, which completes the zfr!
whether window (I/+1, 24+2...... 22n+i-1. 0) has n zeros or
reduction from AugInd 2[zid to fair clustering in the sliding window with additive violation. This implies A must use (2n/8) space.
B MEYERSON SKETCH
We provide a brief overview of the Meyerson sketch (Meyerson, 2001) and its key properties relevant to our work. The Meyerson sketch achieves a bicriteria (C₁, -pp-opimoonnn for (k, 2)- clustering on data stream consisting of points 21..... In E [A]", where C1 2 and C2 = O (2 log n log A), i.e., it provides a Ci Ci-approximation while using at most C2k centers. An important feature of the Meyerson sketch that we shall utilize is that upon the arrival of each point z;, the algorithm permanently assigns 2; to one of the C2k centers, even if there is subsequently center closer to v; that opened. Moreover, the clustering cost at the end of the stream determined based on the center to which z; was assigned at time i.
To simplify the discussion, we describe the Meyerson sketch for the case where 2 1, noting that the intuition extends naturally to other values of z. The Meyerson sketch operates using guess-and-dee ann-ooble strategy, where begins by estimating the optimal clustering cost. Based on this estimated cost, it randomly converts each point v, into a center, with probability proportional to the distance of the point o; from the existing centers at time i. If the algorithm opens too many centers, concludes that the estimated optimal clustering cost was too low and doubles the value of the guess.
C PROOF OF LEMMA 3.3
Lemma 3.3. Consider q E [A]d r A 0, E,8 E (0,1),k, 2 1, and weighted set P = (p1, .h.PP2...,P.. Pn) C [A]d n ring(q.r/2,r) listed in the increasing order of time steps. Let N: == w( and S be the output of RINGCORESET 8) (in Algorithm 2). We have Eljsi] = poly(2"ke= ke log(NAe 1 and with probability at least 1 8, there exists weighted set S such that
S
For every p e S. (s)(p) E + e)ws(p),
For every center set C Rdd |C| < k and every assignment constraint T with respect to P, P,C, we have cost((",, CC,T) cost (P, C)) s [[cost(P, C,T) + cos C,T) + Nr*).
To prove Lemma 3.3, start with showing the following Lemma C.1 which has the online coreset error guarantee only for one center set C' and assignment constraint I, and only holds when all centers close to q. The condition of Lemma C. is guaranteed by Lemma C.3, which reduces infinitely many pairs of (C, l') with unbounded diam(C) to finite pairs with diam (C) = O (z/e) diam(P). We will conclude Lemma 3.3 by combining Lemma C. and Lemma C.3.
Define Rior == 102r/E and Cfaar : =cE C: :(qg c) > R.ar.. Lemma C.I assumes the point set P lies in Big, R.ar).
Lemma C.1. For every r > 0,E,8 E (0.1). > 1.g E [A]d, weighted set P C [A] n ring(g.r/2,r) center set C C B(g, CCI < k. and assignment constraint I with respect to P.C. let = w(P) and S be the output of RINGCORESET(P), We have E[SS]] p2ly(2 - log( NAe -18-1)) and with probability at least 1 - 8' (let 8 follows the definition
17

---

Published as a conference paper at ICLR 2025
in Algorithm 2). there exists weighted set S' with cost(S', C,T) cost (P, S eNrs, such that S' and for every p E S. wgr (p) E (1=
Pick any _ r-net of ball gg. Risr), denoted by C.. In Lemma C.3, we reduce arbitrary center sets 12s to subsets of Cy. For assignment constraints, we discretize every value [(c) into == {i : 0, 11....,y) 4,, where / = h² (10z/s+ 1)
Define
==((CTT: S. C E,T(C) =c(P)
We have [F| S ( ((l)--owMe kO(kd) (2/E))
We introduce the following generalized triangle inequality for the proof of Lemma C.3. Lemma C.2. (Braverman et al., 2022) For every d, z 2 1, (0, 1], a, b IR, the following inequality holds,
d(a.b) S (1 + (1++t)= c) + +1+
Lemma C.3. For every weighted set P S ring(y,r/2,r), k-center sei C R.d and assignment constraint I' with respect to P, C, let N = w(P), there exists k-point center set and assignment constraint (C", E F such that
cost(P, C,T) E cost (")
Nr + cost(P,C,,)+ Σ r(c)d(c, CE
10
Proof. First, we move every center outside Big, Rear) (i.e. c Cffrr to q, and move every center inside B(g, Riar) (i.e. Cthar to its nearest neighbor in C.. Suppose e is moving to C,(c), for every center Let Ò CC) (C)(c) :c C). Let I be the assignment constraint after movements, i.e. [(c) (e) r(c).
For every assignment function we call (a, ō) is corresponding if ö(r q) = Eeeor (Ix,'') and o c) = olr, c) for every P. C',C In order bound the difference between cost(P, (P, C,T) and cost (P, Č, F), consider the cost difference of every corresponding pair (a, i,.
P, C' and assignment function w.r.t C, I,ō I,
Σ ZEP
Σ LEC
ol, c))(,,)) - E Eo ()d,,))( = olx -f
AEC
CEC ZEP
ZEP
Define E' (1 -1=+ to q. By Lemma C.2, we have
For every center ff and point ø E P, c moved
cls,c)(d(x, - ((t ( d(x,g)))))
$ (1 (1+ (1+ (dc,,)== + +
d(c, 9)
10z
< (1+=//)
1+ { d(c,g)²
10;
(1 ((++2/5)oz,,))dccc.
From the opposite direction, o(z, (] d(z, is lower bounded by
cdz,))d((z c)= d(x, )) 2 a ((z,c) -(z, d(z, d(x,g)²)
a (1)()) ( ((e/1==)d(c.4)))
v ((1 (E/10=)) ((/)))/(())))(////dllcc...
N (1 - (1)
For every center e E C', and point æ E P, when c(xx,e)) > d(0, c). moving to e' = Cy(c)
increases the cost by c d')² < (10(((1111)))01 +
(o(x,
1)d(x, -(c))-
18

---

Published as a conference paper at ICLR 2025
s0(2,)) c)) (1 I < ( d( + + $122" =²²=)
12
When d(x, > d(z,,c), by the same argument we have,
()) a(, ()((( + + - 1)d(s, +1+
5 o((2,0) ( c)) +
12 -12=))
In summary,
df -(x,,,,()))
xEC
(1=
Σ
Σ
a(. c)d((.)))
+ E
E Σ (((a,c)d(ec)) = Nr
4
12
CEntar
CEC ZEP
Σ I(c)d(c.g)*
Σ
Σ
eECfe
oEc PEP
E
Σ
Σ
(ll, c)a Nr
12
CET DEP
Σ I(c)d(c.g)*
Σ E (1=16/10)))xxxx
cECRer
CECie xEP
+
E
Σ Σ (o(r,c)d(a, c)* + Nr
4
12
CEC PEP
Σ [(c)d(c.g)* cost(P,C,T)= & Nr 12
E
Since the bound holds for every corresponding o, o', let a² be the optimal assignment function of cost (P, C) and o be some corresponding assignment function of a", have
cost(P, C.T) cost"" " (P,C,T)
2 cost (P,Č,T)
Σ
I(c)d(c,g) 4
cost cost(P,,,,T) E
Ny
12
eECte
cost(P (P,C. + Σ r(c)d(c.g) cost (,C,)) Nr
(1)
cECiee
On the opposite side, let 5* be the optimal assignment function of cost Č, and a be some corresponding assignment function of Ø*, we have
(ost(P,,,)) cost. "' (P,
cost (P,C,T) E T(c)d(c, 4
cost (o,t(P,,,T) ê N
12
cost Most(P,CC.) P,C.T) - Σ I(c)d(c.g)* cost(P,C,r P,C,C)
12 2
(2)
Combining (1) and (2), we have
cost(P,C,D) - cost (P,C Σ r(c)d(c,g)* cost((, + _ 2
(3)
12
CEC
Next, we find F' : Ò such that i'(Ō) = N and for every e Č, [T(c) -i((c) < 1/t, which
always exists. On the other hand, there also exists assignment function o' I' such that for every
19

---

Published as a conference paper at ICLR 2025
c, (o(2, c) d' < 1/t. The difference of cost between a and o' is bounded by
(cost(P,C,T)) cost (P,C,T'
( d' o((,,,))-((
CE ZEP
(a(x, d' d' (d)cmmm()m 2r)²
cEC'EP
x (10z/E + 1)² k
(4)
Now we are able to give a error bound between cost (P, T, and cost Č, (") by summing up (3)
and (4),
cost (os,C,)))
Σ ((c)d(c.g)
& cost(P,C,,T) - cost cost(P...... P,C,
Σ
T(c)d(c, + cossttP, - cost(P, C
eECte
( N + 9) rd cost(P.C,I)
&
12
M E Ny* + e cost(P,C,I).
10
4
conclude the proof by picking C' -,,'==
Proof of Lemma 3.3. By union bound, with probability at least the statement of Lemma C.1 holds for every F.
For every (C, let (C) E F be the center set and assignment constraint stated in Lemma C.3 with respect to (C, We have
cost((S, r) cost (P, C,T)
< cost(S, I') cost +
Co,
(cost(P,, C,)) cost cost(P,C',,'))
(", cost
E Nr + E (so, cost C,
(Nr (Nr* cost C, cost (ost)))tC.CCCC... (P,C.)))
Since the size of S is independent of C and I, the upper bound of E[[S]] is the same as the result in Lemma C.I. This finishes the proof of Lemma 3.3.
C.1 PROOF LEMMA C.1
Lemma C.I. For every 0, E (0,1), > 1.g [A]d weighted set P. C [A]d ring (q r),, center set C C B(g, Reac), S k. and assignment constraint with respect to P.C. let N w(P) and S be the output RINGCORESET( p2ly(22 dke (og(NNe-)8-1)) and with probability at least 1 - 8' (let follows the definition in Algorithm 2), there exists weighted set S' with cost(S', C, cost (P, (P,CCT) eNr such that S' = 5 and for every E S, ws (p) E (1 + ()ws(p)-
We have E||S||
Some parts of the proof of this lemma inspired by Cohen- Addad & Li (2019), but compared to Cohen-Addat & (2019), our proof needs to handle additional difficulties, such as dealing with weighted input points and non-uniform sampling probabilities.
20

---

Published as a conference paper at ICLR 2025
As w(S) may not equal to w(P), cost(S, C,T) is not well-defined since I' is not assignment constraint with respect to S. Before discussing the cost of (S, C,T), we need to generalize the definition of the cost function to the case that w(S) *[C)). Then prove Lemma C.I by showing that both cost P, C, r) cost' (S, C, [)] and (Ss
cost' (S, C, [)] are small.
Definition C.4. For weighted point set P S [ and a center set C S RR a partial assignment function with respect to P and C is a function a with respect to P,G. C and an assignment constraint T with respect to P', C. where P' is some arbitrary weighted point set (P' is only used in (CC)= -ww(()))) say is partially consistent with I if the following property holds, denoted by ~ r.
P C + R20. For a partial assignment function
For every E P. EcEo (p.c) E wp(p).
For every C. Epep cp, T(cc.
Ifw(P) 2 T(C), then satisfies for every c e C, (p.)) = I(c).
lfw(P) & r(C), then satisfies that for every p E P, Eeec olp = wp
partial assignment function can be viewed as a maximum flow of the following flow network.
For every p P. there is edge from source node to p with capacity wp(p).
For every c C, there is an edge from to sink node with capacity I(c). For every p P. C, there is an edge from p to e with infinite capacity.
Now can define the cost of S with respect the constraint T.
cost' (S, C,T) 0:9xC-Ra0
min
ΣΣ
a(p,e) dist(p,c)** PEPEEC
Lemma C.5. With probability at least 8/2, (S, - cost-cotssPtP,,))) cost SeNr1/2
Proof. The proof is postponed to Appendix C.2.
Lemma C.6. With probability least 1 8/2, there exists weighted point set S' with Joost'(,, (,T) cost(S', & eNr /2, such that S" = S and for every E S, wg (p) e (1 (p))
Proof.
The proof is postponed to Appendix C.3.
Lemma C.7. Let T,
the definition in Algorithm 2, E prob, S Tln + 1.
Proof. Notice that
up((p)
sum, II
= wr(p)).
sumn
1=2
wp(p;)" -1 sum
sum wP(P1)'
wp(p))
wP(p))
In N In sum, wr(p))
In
sum;
sum,
So have
T (Twp(l),))
sum, .1 SThN+1
prob;
+ Σ min
2
21

---

Published as a conference paper at ICLR 2025
Proof of Lemma C.I. By applying union bound the results of Lemma C.5 and Lemma C.6, can show that with probability at least 1-d 6, there exists a weighted point set S' with CIT) cost(8', C,T) 1 <Nr*, such that S" S and for every p E S, ws (p) E [1= (1=))ws(p).
By Lemma C.7, B||S|] = Ei= prob; - N +1.
C.2 PROOF OF LEMMA C.5
To prove Icost' (S, C.T) cost(P,,,,)) & /2, we show that given an optimal assignment function of cost C, C)T,, we can always construct a partial assignment function with cost no more than Co, D) + eNr* /2, vice versa.
In the following discussion, let n. T, P....... Pa. sump summ, prob ................................ prob, follow the defi- nition in Algorithm and let S be the output of RINGCORESET(P. d). For every I S n, let indicator variable X; denotes / (p= S).
We first prove a concentration inequality used in the following proofs.
Lemma C.8. For every 0 e, 1, W > a1, 02....., On such that V1 S i n, S 04 S
W (p))), as long as = (e log 10-1 "10g (NW))) we have
Pr
aaprob; Xx,- Σ aq > 5
a4 +ENW
5.
Proof. Here assume all points p. satisfy prob; 1, otherwise always have a,prob; X, a and eliminate these points from P without changing |E/=1 a,prob, X; E 0j Hence we always have prob; = Twep(p.) As result, for every 1 S i S n, we have
sum;
asprob; 1 < www.wwwee wp(p)) T Tppp
sum;
NW
T
Let 1y=1 1=t==++ 8lnN divide P into L = 0 (0-5(111))) log Nog. Nooo(=looo-ni)))
groups jum jim +1
Gimux C [ where Jmin [log, (s/n)] Jmax = [log, (NW/T)). Group Gj contains the indices of all points ps such that a,prob, E (,5-1, ""),, particular, Gi.... contains all points ps
such that a; S glmin.
For every Junn <j S Imax, we have
Σ asprob, 1 X, LGG
Σ aj S
Σ iEG,
X₂ Σ
prob;
+ (7 - 111-111-111 Σ (X, + prob;) (5) iEG,
iEG;
iEG;
For j = juin we have Eieg,an asprob; S.
For the second term of (5), is sufficient to bound Eveo, prob; since by Chernoff bound we have
X max 2 prob, 4l(21/))))) )
Pr
< 5/2.
By Lemma C.7, with probability at least 1 -8/2, we have
Jmax
(r 5
(prob, + X2) < (r 1)
(prob, X,)
j=imin
< ( 1mm -1
2 _
prob, + +1m(118)
i=1
NW
< ( 1)
(2T + 4lm()/ + +2)
T
22

---

Published as a conference paper at ICLR 2025
ENW
(6)
Next consider the first term of (5), Let 24 LiEo, prob; A, Eieo, Og notice that
ai
Aj
Mj =
prob, S
iEG
EEG,
By Chernoff bound, let = max (jA Aj, 3
1n (2T,/))), we have
8²
Pr
Σ iEG,
X;
14 2 レ
S 2exp
31
t2
< 2 exp
330+1
1 2L
By a union bound, with probability at least 1 - 6/2, we have
Jmax
Jmax
Smax
Xi
Σ
prob;
S
Σ
Aj + 3=-1
Σ
(1+ ln(L/00)
J=min
iEG,
iEG,
j=mmin
j=im
+ 35 -2 2 +1 lnL2//88)
(=1
aj + 35 222 (n(22/6)) max a prob," iE|n
i=1
3r 222 In (2L/6)) NW
aj
T
S + NNW.
Combining (6) and (7) by a union bound, we have
Pr
approb; 1 Xx,
Σ aj > E
aj + ENW
Define R = (20z/s+2)r diam diam(C)) P). For every pair e C,p E P, dist(p, c) is bounded by R. Let So = (s/22z)-= < (20z/s + 2)=>s. In the following proofs, we show these errors are bounded by N 8t and that implies err N R E
Lemma C.9. Pr[costt(S, (, S cost C, + eNr 2 1-168 5/4.
Proof. To imply cost signment function o P C + Rzo of cost cost(P, C) there always exists a partial assignment function d' S x C R2z for cost' C) such that Epes Ecec c)) (p, e) s EpEp Eesc dist(p, (p, + /2.
cost(P, + /2, we show that given optimal as-
natural way for constructing o' is assign a(pc)) ws(()) units of weight from p to e, denoted by assignment 7. Let the cost of this assignment be
wr(p)
(N,c) c)
cost, ΣΣ
ws(p) d(p.c) c)².
PES CEC wp(p)
23

---

Published as a conference paper at ICLR 2025
However, may not be consistent with T. Since S is random point set, centers may receive more than [c) units of weight, denoted by center set C* and some may receive less than [(c) units denoted by center set C We transform into assignment consistent with by collecting the surplus weights from C+ and send them to C so that o' is partially consistent with r. Re-routing weight started point p from to e' costs most wddist(pp c')² dist(p; c)*) w R Hence this step costs at most
apis c) wp (p:)
n o (pc, c)pb X;
Σ
T(c)
ws us(pi)
R²
Σ
[(c)
EEC
PES
OEC
Taking s' CE C.
8
5
W = 1, vA S sis S. n, = opis c) in Lemma C.8, we have for every
8k
5h
((c) - Σ opi, c)prob, X;
Eo (T(c) + +N)
Pr
< 4k
8k
i=1
By taking union bound over every c C, with probability at least 5/8, we have
|cost, costt(S,,,,,))
R²
Σ
r(c)
Σ
opi cpr,o) Xi S 60
NN..
4
CEC
Next, we show that the cost of r is close to the real cost of P.
(olpic) ws(ps) - (prne) wp(p,)
lcost, (O,Tt(,
dist c)²
IEE
Taking E' 50_ every CE C,
8k W R spisisnon n,a; sis
cist(pp.c)o in Lemma C.8, we have for
Pr
dist(p,, c).
(ppi.c) c)
(p((p)) - σ (p:..) c)
50
(cost
8
wr(p:)
8k
8k
By taking union bound over every e C, with probability at least 1 8/8, we have
Σ
dist(pr, c)*
(p(psc) ws(p.) (pr wp(p;)
Eo NRE.
REC
In summary, with probability at least 8/4, we have cost' C,, cost(P,C,I)) < (cost' (S, (S, cost,) + (cost,
< Ep R
< E NNr.
2
2
Since is a random set and contains much fewer points than P. constructing an assignment function with respect to P, C' from a partial assignment function of cost' (S, C, is difficult. Hence we first compare cost P, C, ) to the expectation of cost' (S, C, T) and then show the concentration bound of cost' (S, C)
Lemma C.10. cost(P, C) < Elcost' (S, +
Proof. Let : x C + R>o be assignment function with respect to P, C. Let o" be random partial assignment function that denotes the optimal assignment function for cost' cost'(S, 1").
Since o* ~ P. we have Vo E C, EpEp Ela (p,c)) < I(c) and Vp E P. Ecec Elo"(p,)) < wr(p). We construct a by initializing a (p, e) (p,c)), then arbitrarily assigning the
24

---

Published as a conference paper at ICLR 2025
remaining weights of data points to the remaining capacities of centers. This assigning step costs most
ΣΣorre 1)
Rd N ΣΣ
Elo"(,,c))
R²
N - E
PEP
PEPCEC
R min (S), NY
(0* I)
R² ( w(S), 0))
R²
w wr prob, X; - Σ wr(pi)
Taking 8' = 8:0 = Pm W = 1, S i a, = wp(p:) in Lemma C.8, we have
n
Pr
wp(p:)prob," X,
Σ wp(pi)
ED S
N
Eo Nwr(P)
8
which implies
R E
Σ wp wp(p))prbb X; - Σ wr(ps)
S R²=
EoNN
+
Eon summ Nw((P)
Eu NR
< ENN
8
4
4
We use a concentration inequality based on martingales (Chung Lu, 2006) to show the concentration bound of cSst'(S, C) For convenience, we use Tt...r to represent (II, I.t1,..., (rr) for every vector of dimension d, SIsssrs d. This notation is also used for function arguments, e.g.
f represents fz1 (2.,,)
Lemma C.11. (Chung & Lu, 2006) Ler V = X1 X x Nu X2......... Xn S R) be set of n-dimensional real vectors. Suppose there is a function f V - and n distributions D1, D2..... , Dn over X N2, X2.... Nn respectively and 'D is the joint distribution over V, Define (() 22, 22, 2i) = F (x) 31 = ,;, 21).
Fof,02.... oo, satisfies for every 1 siss, E M...... 2i-1 E X;-1
Var ( (5 (21, 22, --1, S of
and M satisfies that for every
< i < n, 2 E V, 2 E X, such that PIx~D (x = 2] > 0, PrxwD [41
21...., F4 2/1 In 2n] 0, we have
1-11 12 Fn) f( 1- 2/1 #411..n) S M,
then for every t > 0,
-t2 2( o. + MM/3))
Pr [1(()x Ex-D[f(x)] > t] < 2 x
Lemma C.12. Pr[]cost (S, C,T) - Elcost' (S, (,C, < =N /4| 2 1- - 6/8.
Proof. Define function R2 + Rzo as f ,2,..,, xn. cost' (Rt C,I') where R == {p, i e [n],2; 24 0} and wR(P:) := Zz.
Define random vector x (I1, T2, In) be the vector representation of S, i.c.
2; (s(pps) P. E S
Pi $ S
Let DD be the distribution of the weights where
ww((p))
p; E S
T;
0
Pi $ S
25

---

Published as a conference paper at ICLR 2025
and S is the output of RINGCORESET(P).
By the definition x, 12,322.... 2n are independent random variables. prob, 1, then xz always equals to (p:). Otherwise, I; has two-point distribution
suma T
w.p. prob;
I2
0
w.p. prob;
We assume prob; < in the following discussion since the conclusions obviously hold when prob,=11 1.
Suppose every 21. , is fixed except z;. f(1 (2,.,42...... Fn). adding z; by corresponds to adding (p:))) by 1, which increases cost' C,) by at most R (recall that every partial assignment function can be viewed as a maximum flow of certain flow network). Hence the difference
of f(11....,2;11..00 ,n, In) and ([11,...,24--)
..... Fn) most R sum, I R
Define (21, 22 , zi) [ I1 ; z/]. To give an upper bound of 0), first consider the difference between
(2r (z R" Prx
Fo ( 0) and Fi f (21. sum, /T' By the arguments above, we have
FFo Fils Σ
Pr( 2441..
- [
O, z44 1...a) (11...111
sum,
Zit I...
sum
T
Then we have
Var( (21...-1,;;)) prob, + (1 Frob,) (prob,Fi (1 Fo)
prob, (Lob,(1-prae) pro,; F1)
S prob,(R'summ//7))
R2* N S T wp(p:).
Taking M N/N/T and of n²-N wp Lemma C.11, we have
Pr costtts(S, C,T) < Elcost' (,,,
Ea
R
4
2 R
exx
32(E (=
NR +
RR2
c
eex
5/8.
Lemma C.5. With probability at least 1-8) 8/2, |cost' -ost /N
Proof. By applying union bound to results of Lemma C.9, Lemma C. and Lemma C.12, we get Pri[costt C) - cost P, C)T S eNr 2/2 2 1 8/2. This concludes the proof.
C.3 PROOF LEMMA C.6
Lemma C.6. With probability at least 1 - 8/2, there exists weighted point set S' with roost'(S C,T) - cos CC,))l & =2r²/p /2, such that S' = and for every p E S, ws (p) (1 {p))
Proof. Taking e' = 50 2. = 8/2 = sissiinnnnnnm = =wp(p:) Lemma C.8, we have
Pr
w
E +
Eu
= Pr
Σ
up(p -x, (1# Eo 4
Σ wp(p.)
N
4
P.ES
P.EP
26

---

Published as a conference paper at ICLR 2025
2 1 5/2.
Let a Eo_N R² /2 always holds, where S" contains all elements in S and the weights defined by ug (z)
w(S) N Conditioning on a E + 2,, we show that |cost" C,T) - (Ost C)
(2(x)) for every E S.
For every partial assignment function a with respect to S, C and partially consistent with I, and assignment function o' with repsect to S", C and consistent with I, we have EeEp Eeec oz, c) N and Exer Exec (ar, c) = min(w((), N) = min(a, 1)N. In the following construction, we use min(a, 1) to normalize the weight of a.
First we prove that cost' C,T) S cost(S', C,T) + /2r Let o' be the optimal assignment function in cost(S', C,T). We define the partial assignment function o as (p, c) = min(a, 1)o for every p P. E C. We can verify that is partially consistent with r.
cost' (S,C,T) < E E
(p, c) cis
pEP dEC
min(a, 1) cost(S', cost(S' C,,).
Next we prove that cost(5', C) I (S, + &Nr Let a be the optimal partial assignment function in cost'(S, max(a -1 (p, c). However, o' may not be consistent with I. In order to obtain an assignment function consistent with r, we apply the following modifications to o'.
We initialize the assignment function of o' cppp.)
Let S² = (x E d' c) > (es S = for E S' EE <
(x)). For every center c E C, we re-assign weights from o' cx, (1 E St) to d'(''c)) (x' E E5")). Repeating this process until Ecec o' (æ. c) us (x) for every P. This
step costs most RR Exes (w))(() - -Ene maxxa=
Let C+ = f Exer > r(c)). = fc C: - (x, < r(c)). Notice that the previous step does not affect E o' For every point x E S', we re-assign weights from o' c) (c E C+) to (I,,)) (d' E C-). Repeating this process until Loes o' o'(x, e) I(c) for every E C. This step costs at most R² Eeec [[(c) max(a 1 11) (x,e)).
After these modifications, the cost of o' is bounded by cost (P,C,T) cost' (P,
S R Σ
(x) max(a 1,, Σ (xx R²
Σ T(c)
max(a-1,1)
DES'
oEC
cEC
wES'
(F( 2 N (i.e. a S 1), then Exes ol,, = T(e) holds for every center e E C. cost" (P.C,T) cost' (P,C,I)
< R
(x)(
+ R
Σ ((c)
CEC
CEC
xES'
R Σ
(s)(
Σ ((),
S
cEC
< R
(ws(x) us: (x))
(w(()) - Eo(z,
FES
cEC
< (w N) < 50 NR
27

---

Published as a conference paper at ICLR 2025
If (S) N (i.e a= > 1), then ( ws(x) holds for every P.
cost (P, cost (P,
< R²
Σ
Wg (x) a (
+ Rt² Σ
[(c)
a Σ ((xcc)
2E8'
OEC
OEC
zES
Ria
Wg( (z)
Σ (I)
+ R
Σ
[(c) 1
(
OEC
OEC
ZES
R
((c) a- c(T,c)
CEC
BES'
R
Σ
- - +a [(c) - Eo(u,
CEC
ZE8'
(a- 1)N v 0 NR
2
Summing up together get cost(S', C,,,)= S cost' + This concludes the proof.
28


Reviews:
[{"review_id": "FP5DA4owwK", "reviewer": "Reviewer_hpoL", "summary": "This paper studies the fair clustering problem in the sliding window model, where the goal is to maintain an approximation for clustering the most recent data points while satisfying proportional fairness constraints. Specifically, given a $k$-clustering instance in the form of a data stream, the goal of this paper is to achieve a $(1+\\epsilon)$-approximation to the optimal fair clustering for the dataset defined by the sliding window with minimum space complexity. However, ensuring fairness under strict space constraints in a data stream poses significant challenges. To tackle the challenges in sliding window model, this paper proposes an online assignment-preserving coreset construction method. The proposed method first reduces clustering in the sliding window model to an online coreset construction via a standard merge-and-reduce technique. Then, this paper introduces an algorithm for assignment-preserving coreset construction that processes each window as a suffix of the input stream at a particular time $t$. Finally, by constructing the coreset in reverse order across all time steps from $1$ to $t$, the resulting prefix of this online coreset serves as a valid coreset for the sliding window, achieving $(1+\\epsilon)$-approximation for the fair clustering problem in sliding window model. This paper shows that if the fairness constraint is allowed to be violated by a multiplicative factor, there exists a $(1+\\epsilon)$-approximate sliding window algorithm that uses only $poly(k\\epsilon^{−1}log n)$ space. Empirical evaluations on real-world datasets further validates the effectiveness of the proposed framework, complementing the theoretical results.", "questions": "Q1: The proposed algorithm violates the fairness constraint by a multiplicative factor, which is slightly different from previous fair clustering algorithms with additive violations. Does multiplicative loss lead to better approximation ratios than previous algorithms with additive loss? What happens when only additive violation is allowed for group fairness constraints in the sliding window model, as achieving an approximation ratio of $1+\\epsilon$ for group fair clustering is challenging.\n\nQ2: As mentioned in the paper, the prefix property of online assignment-preserving coresets can tolerate a $1±\\epsilon$ relative error in the weights. Does this property make the proposed algorithm easier to implement compared to the algorithm in [1]?\n\nQ3: The comparison algorithms used this paper are limited, which makes the numerical experiments not convincing enough. The authors should add more sliding window algorithms, fair algorithms or heuristic algorithms as comparisons to make the experimental parts better.\n\nQ4: How to determine the value of parameter $k$? Does different choices of $k$ influence the experimental results of the proposed algorithms? What are the choices of the values for $\\alpha$ and $\\beta$.\n\n[1] Woodruff, David, Peilin Zhong, and Samson Zhou. \"Near-Optimal k-Clustering in the Sliding Window Model.\" Advances in Neural Information Processing Systems 36 (2024).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The strengths of this paper can be summarized as follows.\n\n1. The theoretical results of the paper are solid.\n\n2. This paper establishes lower bounds for the fair clustering in sliding window model.\n\n3. The proposed method achieves near-optimal clustering performances with  $(1+\\epsilon)$-approximation on clustering quality guarantees while the space complexity nearly matches the lower bound provided.\n\n4. The proposed method uses sublinear space in sliding window model, which can be used for handling large, dynamic datasets that require efficient memory usage.", "weaknesses": "1. The proposed algorithm uses a multiplicative relaxation rather than an additive violation for fairness constraints, which is slightly different from previous fair clustering algorithms.\n\n2. Although the theoretical results nearly match the lower bound, the space complexity still depends on the aspect ratio of the given clustering instances. \n\n3. The paper lacks a sufficient number of comparison algorithms, making the experimental results less convincing. Additionally, the parameter choices and values for $\\alpha$ and $\\beta$ are not specified, limiting the reproducibility and clarity of the experimental parts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xA4y2aqM5q", "reviewer": "Reviewer_cQ32", "summary": "This paper studies the fair clustering problem within the sliding window model, where the goal is to maintain approximation for the most recdent data points in a stream with minimum space compelxity used. This paper first identifies a unique separation in clustering performance between the insertion-only and sliding window models, specifically for fair clustering, where no algorithm can achieve a bounded approximation ratio under strict fairness constraints without requiring linear space. To address this issue, ths paper then introduces an approximation algorithm that achieves a $(1 + \\epsilon)$-approximation for fair clustering by allowing slight relaxation in fairness constraints, using sublinear space in $poly(k, \\epsilon^{-1}, log n)$. Theoretical contributions include a strong lower bound proof, supported by communication complexity techniques, establishing the necessity of linear space for strict fairness in the sliding window model. Complementing these theoretical findings, this paper presents empirical results on real-world datasets, demonstrating that their approach significantly improves clustering cost and stability over a uniform sampling baseline, supporting the algorithm’s practical effectiveness in dynamic, fairness-sensitive applications.", "questions": "1. What impact does the window size $W$ have on performance? Since sliding windows dynamically retain recent data, it would be insightful to see more analysis on how varying $W$ affects the clustering quality and computational efficiency of the proposed algorithm.\n\n2. Is there any methods that can remove the dependence of aspect ratio on the space complexity? How to deal with the case if the aspect ratio of the given clustering instance is large. In previous work, it was pointed out that the log function of aspect ratio can be linearly dependent on the data size $n$ [1]. Additionally, the method in [1] provides an efficient way for reducing the aspect ratio of any arbitrary clustering instance to bounded $poly(n, d)$ in static setting.\n\n[1] Draganov A, Saulpic D, Schwiegelshohn C. Settling Time vs. Accuracy Tradeoffs for Clustering Big Data[J]. Proceedings of the ACM on Management of Data, 2024, 2(3): 1-25.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. Novelty and Insight: The paper identifies a crucial separation between fair clustering in different streaming models, offering new theoretical insights into the limitations of fair clustering in the sliding window model without any fairness violations.\n\n2. Theoretical Contributions: The lower bound result is strong and well-supported by communication complexity arguments, which can have positive impact on the theoretical understanding of fair clustering.\n\n3. Approximation Guarantee: The proposed approximation algorithm provides a $(1+\\epsilon)$-approximation with sublinear space, which is a valuable contribution in the context of fair clustering and sliding windows.\n\n4. Clear Presentation of Methods: The algorithms, particularly the coreset construction, are explained with clarity, and the theoretical proofs, while complex, are well-structured.", "weaknesses": "1. The space complexities used for the proposed method are dependent on the aspect ratio of the given clustering instances (an $O(\\log\\Delta)$ term, where $\\Delta$ is the aspect ratio). Although, the aspect ratio can usually be assumed to be bounded by a polynomial function of the data size, it can be arbitrarily large in the worst case. \n\n2. The empirical comparison primarily involves a uniform sampling baseline. A more comprehensive evaluation with other clustering or local search methods would strengthen the experimental section and provide a clearer picture of the proposed method’s effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "THu1FZ6P32", "reviewer": "Reviewer_RZvP", "summary": "In the paper, the authors consider solving the problem of achieving (1+\\epsilon) multiplicative approximate fair clustering in the fixed-size sliding window model. The author proved that there exists a sublinear space algorithm to solve the ((1-\\epsilon)\\alpha, (1+\\epsilon)\\beta) clustering problem. The core solution builds on top of online corset algorithms. At a high level, it first constructs a set of sketches to approximate the cluster, then decomposes the clusters into rings, and lastly union the uniform samples from the rings.", "questions": "See weakness.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper studies an important problem with praticial impacts.\n\nIt not only presents novel theoretical insights but also implemented the algorithm. The evaluation showcased that the proposed algorithm consistently achieves better results compared to a uniform sampling baseline.", "weaknesses": "It would be nice to introduce a bit more on the (Augemented) Meyerson Sketches.\n\nPlease add more discussions and implications of multiplicative/additive approximation error on applications..", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J0wO9djoD0", "reviewer": "Reviewer_5dNf", "summary": "This paper investigates the problem of fair clustering in the sliding window model. First, it presents the inapproximability of the problem. Then, it proposes a new coreset-based approximation algorithm for the problem by relaxing the fairness constraint. Finally, some experimental results are provided to show that the proposed algorithm is better than trivial uniform sampling.", "questions": "See the questions listed in W1.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. This paper addresses an open theoretical problem - whether the proportional fairness constraint and the sliding window model are compatible in sublinear space - by providing the inapproximability result.\n\nS2. The proposed algorithm is the first known one with an approximation guarantee for fair clustering in the sliding window model.\n\nS3. The theoretical results are thorough and solid.\n\nS3. The paper is generally well-written and organized.", "weaknesses": "W1. Although the theoretical part of this paper is sound and solid, the experimental part is highly insufficient.\n- At least, two additional types of baselines should be compared: (1) the algorithms for sliding-window clustering without fairness such as those in [Borassi et al., 2020; Epasto et al., 2022;  Woodruff et al., 2023], which indicates \"the price of fairness\", and the algorithms for offline and insert-only streaming with fairness such as those in [Chierichetti et al., 2017; Schmidt et al., 2018; Huang et al., 2019], which provides lower bounds of clustering costs and presents the challenge of the sliding-window model. Uniform sampling is a too-weak baseline for coreset-based clustering.\n- How about the performance of the proposed algorithms on datasets with higher dimensions (e.g., [Census](https://archive.ics.uci.edu/dataset/116/us+census+data+1990) and synthetic data in about 10-100 dimensions)?\n- Details about experimental setup and implementation (such as dataset preprocessing and code availability) are concise.\n- The efficiency results (e.g., running time and coreset size) and scalability (e.g., performance w.r.t. k and d) are not provided. For example, the clustering cost, runtime, and coreset size w.r.t. different values of k and d can be presented in figures or tables.\n- According to the theoretical results, it seems that the proposed algorithms can work for multiple $l>2$ attribute groups. However, the experiments only use a binary attribute for each dataset.\n\nW2. Minor presentation problems. Please double-check the paper carefully. Just one example is presented here.\n- In the abstract, \"*we show that if the fairness constraint by a multiplicative $\\varepsilon$ factor, ...*\" missing \"is relaxed\"?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)