Distributed Algorithms for Euclidean Clustering
Authors: Vincent Cohen-Addad
Liudeng Wang
David Woodruff
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: clustering
distributed algorithms
communication complexity
Primary area: learning theory

Abstract: We study the problem of constructing $(1+\varepsilon)$-coresets for Euclidean $(k,z)$-clustering in the distributed setting, where $n$ data points are partitioned across $s$ sites. We focus on two prominent communication models: the coordinator model and the blackboard model. In the coordinator model, we design a protocol that achieves a $(1+\varepsilon)$-strong coreset with total communication complexity $\tilde{O}\left(sk + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})} + dk\log(n\Delta)\right)$ bits, improving upon prior work (Chen et al., NeurIPS 2016) by eliminating the need to communicate explicit point coordinates in-the-clear across all servers. In the blackboard model, we further reduce the communication complexity to $\tilde{O}\left(s\log(n\Delta) + dk\log(n\Delta) + \frac{dk}{\min(\varepsilon^4,\varepsilon^{2+z})}\right)$ bits, achieving better bounds than previous approaches while upgrading from constant-factor to $(1+\varepsilon)$-approximation guarantees. Our techniques combine new strategies for constant-factor approximation with efficient coreset constructions and compact encoding schemes, leading to optimal protocols that match both the communication costs of the best-known offline coreset constructions and existing lower bounds (Chen et al., NeurIPS 2016, Huang et. al., STOC 2024), up to polylogarithmic factors.

Published as a conference paper at ICLR 2026
DISTRIBUTED ALGORITHMS FOR EUCLIDEAN CLUSTERING
Vincent Cohen-Addad
Liudeng Wang Texas A&M University eureka amu edu
David P. Woodruff Carnegie Mellon University
Google Research
@chenaddad@@ooss com
dwoodruf @andrew........ cmu.
Samson Zhou
Texas A&M University
samsonzhou@gmail. com
ABSTRACT
We study the problem of constructing (1 + e)-coresets for Euclidean ()) clustering in the distributed setting, where data points are partitioned across s sites. We focus on two prominent communication models: the coordinator model and the blackboard model. In the coordinator model, we design pro- tocol that achieves (1 + s)-strong coreset with total communication complexity dk Ô sk + m2++) + dk log(nA)) bits, improving upon prior work (Chen et al., NeurIPS 2016) by eliminating the need to communicate explicit point coordi- nates in-the-clear across all servers. In the blackboard model, we further reduce the communication complexity Ô 8 log((n)) + dk log(nA) + minte""_"""
dk
bits, achieving better bounds than previous approaches while upgrading from constant-factor to (1 + =-)-ppprxiimttionn guarantees. Our techniques combine strategies for constant-factor approximation with efficient coreset construc- tions and compact encoding schemes, leading to optimal protocols that match both the communication costs of the best-known offline coreset constructions and ex- isting lower bounds (Chen et al., NeurIPS 2016, Huang et. al., STOC 2024), up to polylogarithmic factors.
INTRODUCTION
Clustering is the process of partitioning dataset by grouping points with similar properties and sep- arating those with differing properties. The study of clustering dates back to the 1950s (Steinhaus et al., 1956; MacQueen, 1967), and its many variants find applications in fields such bioinfor- matics, combinatorial optimization, computational geometry, computer graphics, data science, and machine learning. In the Euclidean (k, z)-cluttering problem, the input consists of a set X of points 21,..., In E Rd, along with a cluster count & > and an exponent 2 > O. The objective is to find set C of most centers that minimizes the clustering cost:
min CCR1,1Osk
cost(X,C)
min Σ min min CCR
CEC
When and = 2, the (k, clccutrrgi problem reduces to the classical k-median and k-means clustering problems, respectively. These models remain the most widely utilized formulations in practice, with significant research dedicated to their algorithmic foundations (Charikar et al., 1997;
1999; Charikar & Guha, 1999; Meyerson, 2001; Charikar et al., 2003; Feldman & Langberg. 2011;
Cohen-Addad et al., 2020; Braverman et al., 2021; Cohen-Addad et al., 2021; Braverman et al., 2022; Cohen-Addad
al., 2022a; Ergun et al., 2022; Tukan al., 2022: Bucarelli al., 2023;
Cohen-Addad et al., 2023a; Woodruff et al., 2023; Braverman et al., 2025; Cohen-Addad et al., 2025a;b; Karthik C. S. al., 2025).
Due to the substantial growth in modern datasets, focus has shifted toward large-scale computational models that can process data across multiple machines without requiring centralized access to the

---

Published as a conference paper at ICLR 2026
full dataset. The distributed model of computation has become a popular framework for handling such large-scale data. In the distributed setting, the points 21,..., In of X are partitioned across different machines, and given input accuracy parameter ε 0, the goal is for the machines to collectively find a clustering C of X with cost that is a (1 + e)-multiplicative approximation of the optimal clustering of X, while minimizing the total communication between machines. As in other models, a set C' of & centers implicitly defines the clustering, since each point is assigned to its nearest center. Since transmitting the entire dataset or an explicit cluster label for each point would incur communication linear in n = | it is more feasible to design protocols that exchange only succinct summaries, such as small sets of representative points or coresets. We also note that because of finite precision, input points are assumed to lie within the grid (1...., A)", which can be communicated efficiently using a small number of bits per coordinate.
A standard strategy for efficient distributed clustering is to have each machine construct small weighted subset of its local points, i.e., a coreset, that preserves the clustering cost for any choice of k centers. These local coresets can then be merged at coordinator or hierarchically aggregated to approximate the clustering objective over the full dataset. Naturally, smaller coresets correspond to lower communication costs and faster centralized processing. In the offline setting, where the full dataset X is available on a single machine without resource constraints, coreset constructions are k)) weighted points of X (Cohen-Addad et al., 2021; 2022a;b; Huang et al., 2024)12, As is common, we assume A = poly(n) so that each coordinate can be stored in O Thus, offline coreset constructions have size independent of n, an essential feature given that modern datasets often contain hundreds of millions of points.
known that select Ô (min (2 1k2--iz (22++)
bits, allowing efficient communication and storage.
1.1 OUR CONTRIBUTIONS
We study the construction of (1++) (1+e)--oresetss for Fuclidean (k: =llusterni in the distributed setting, focusing on the coordinator and blackhoard communication models.
The coordinator model. In the coordinator (message passing) model, the sites, i.e., servers, communicate only with the coordinator over private channels, using private randomness. Protocols are assumed without loss of generality to be sequential, round-based, and self-delimiting. i.e., each round the coordinator speaks to some number of players and awaits their responses before initiating the next round and all parties know when each message has been completely sent. Given E > O, the goal is protocol II where the coordinator outputs a (1 + e)-coreset for Euclidean (k, 2l-cluttgi that minimizes the communication cost, i.e., the total number of bits exchanged in the worst case. We achieve optimal communication protocols for clustering in this model, matching known lower bounds from Chen et al. (2016); Huang et al. (2024):
Theorem 1.1 (Communication-oppin) clustering in the coordinator model, informal). Given accu- racy parameter (0, there exists a protocol on points distributed across sites that produces (1 + e)-strong coreset for cllusserng that uses Ö sk + min(e* + dk log(nA)) total bits of communication in the coordinator model.
dk
We note that our results also yield the optimal bounds for k-median, matching Huang et al. (2024); Bansal al. (2024); for clarity, we omit this special case in the remainder of the paper. By com- parison, the protocol of Balcan et al. (2013), combined with more recent coreset constructions such as Cohen-Addad et al. (2021; 2022a); Bansal et al. (2024), achieves a (1 + -t-sron coreset using O ekd log(nA)) bits of communication. At first glance, one might expect our bounds to follow by straightforward generalizations of these approaches; however, as we explain in Ap- pendix A, this is not the case. For example, our result shows that no points need to be communicated "in the clear" across sites -thre is no O (sd log(nA)) dependence in the communication. This is surprising, since one might expect the coordinates of a constant-facte approximation to be broad- cast to all users. Moreover, the factors in our bounds do not multiply either the number of sites s or the log(nA) cost of transmitting single coordinate. Finally, our results extend to arbitrary
We write ò (f (n, d, k A, 2)) to denote O (f (n, d, kt A, 2)) polylog (f (n, d, k, A, ))).
The bound further refines to Ö (min
44/3 (
- )) for k-median.
2

---

Published as a conference paper at ICLR 2026
connected communication topologies, even when certain pairs of sites are not allowed to interact. The formal statement is deferred to Theorem E.7 in Appendix E.
Coordinator model
Communication cost (bits)
Merge-and-reddee with (Bansal al., 2024)
minic" cetry log(nA)
(Balcan et al., 2013),
O
d' ef log log(nA) sdk log( log(n
(Balcan et al., 2013) in conjunction with (Bansal et al., 2024)
dt minterd
log(nA) + sdk log( (sk) log(n)))
Theorem 1.1 (this work)
sk + minteh + di log(ns)
de
Blackboard model
Communication
(bits)
(Chen et al., 2016)
O ( + dk)) log (nd))
Theorem 1.2 (this work)
Ô (og((n)) - dle dllog((4) + minte"
Fig. 1: Table of (k: 2) cluustrrn algorithms in the distributed setting. We remark that (Chen et al., 2016) only achieves a constant-factor
approximation, constant-ccoo--ppromtiiioo whereas we achieve a (1 + approximation
The blackboard model. Next, consider the blackboard model of communication, where each of the s sites can broadcast messages that are visible to all of the other sites. Formally in the blackboard model, communication occurs through shared public blackboard that is visible to all servers. Each server again has access to private sources of randomness. Unlike the coordinator model, there is no designated coordinator to relay messages; instead, any server may write messages directly onto the blackboard. All servers can immediately observe the entire contents of the blackboard at any point time. As before, we assume without loss of generality that the protocol sequential and round- based, meaning that in each round, one or more servers write to the blackboard, and all servers can then read the newly posted messages before the next round begins. Accordingly, messages must be self-delimiting that all servers correctly parse when a message has been fully posted.
Given an accuracy parameter e, the objective is to perform a protocol such that a (1+5)-corest for Euclidean (k: z)-clustering is explicitly written onto the blackboard. The communication cost of II is defined as the total number of bits written to the blackboard over the course of the protocol, measured in the worst case. We note that the blackboard model can sometimes yield lower communication costs compared to the coordinator model, as messages need only be written once to be accessible to all servers simultaneously. Indeed achieve distributed protocol for the blackboard model with substantially less communication than our protocol for the coordinator model, tight with existing lower bounds (Chen al., 2016; Huang et al., 2024).
Theorem 1.2 (Communication-opul opttial clustering in the blackboard model, informal). There exists a protocol on n points distributed across sites that produces a (1 + e)-strong coreset for (k, 2)- clustering that uses Ô s log(nA) + dk log(no))
total bits of communication the muin(e" 2
blackboard model.
By comparison, the state-of-the-art protocol achieves constant factor approximation using Ô ((s + dk) log" (nA)) (ng) total communication (Chen et al., 2016). Thus compared to the work of Chen et al. (2016), not only do we achieve a (1 + e)-coreset construction in the blackboard setting, but also we remove extraneous log(nA) factors. Conceptually, the message of Theorem 1.2 is sim- ilar to that of Theorem 1.1: some amount of exact coordinates need to be communicated (perhaps only to a small number of sites in the coordinator setting) for a constant-facto communication. but no further overhead is necessary for improving to (1 + -)paproxximtionnn Finally, we remark that for both the blackboard model and the coordinator model, our coresets have size Ô for the important cases of k-median and k-median due to sensitivity sampling (Bansal et al., 2024) and in general not only match known lower bounds (Huang al., 2024) but also can be further optimized in certain regimes of n and & (Cohen-Addee et al., 2021; 2022a).
Technical and algorithmic novelties. We remark that work introduces several algorithmic and technical innovations that may be of independent interest. For instance, we describe a number of existing approaches and why they do not work in Appendix A.
Traditional sensitivity sampling selects entire data points with probability proportional to their im- portance. While effective in centralized settings, this approach does not translate efficiently dis-
3

---

Published as a conference paper at ICLR 2026
tributed environments: transmitting full points high- sigh-dimensional centers incurs prohibitive com- munication costs, and naive adaptive sampling requires frequent updates from all sites.
To address these challenges, introduce several novel techniques. First, in the blackboard model, we show that adaptive sampling is robust to outdated information, leading to a "lazy" adaptive sam- pling protocol where sites only update the blackboard when their local weight estimates change approxi-
significantly. Sampling from this outdated distribution still guarantees a constant- mation, reducing both the number of transmitting sites per round and the total number of rounds. An additional L1 sampling subroutine further detects significant changes in global weight without querying all sites, improving communication efficiency.
In the coordinator model, we introduce a coammuiicaaionneffiiiie subroutine based on coordinate- wise sampling. Rather than sending full high- seb-dimennsonal centers. the coordinator and site perform a distributed binary search on the site's sorted coordinates to find the closest match. Only small offset transmitted, decoupling communication from the dimension d.
Overall, we combine these techniques with coordinate-wis wise sensitivity sampling: each point is de- composed along its coordinates, and dimensions are sampled based on their significance. This al- lows the coordinator to send compact summaries to each site, with servers requesting additional information only when necessary. However, the reconstructed samples may not correspond to any actual point in the dataset, requiring careful analysis to show that the overall clustering costs are not significantly distorted. We believe these techniques could also benefit other distributed settings, such regression and low-rank approximation. This fits into general body of work on methods for quantizing data for better memory and communication efficiency, which is often a bottleneck for large language and other models.
DISTRIBUTED CLUSTERING PROTOCOLS IN THE BLACKBOARD MODEL
Recall that in the blackboard model of communication, each of the s sites has access to private randomness and can directly broadcast public platform in sequential, round-based steps, with self-delimiting messages immediately visible to all. Throughout this section, we assume without loss of generality that there is central coordinator managing the process. Our goal is to design efficient protocols for cclusscnn in this setting.
2.1 CONSTANT-FACTOR BICRITERIA ALGORITHM
In this section, we present a new algorithm that achieves an (0))), O (1))-bicriteria approxima- tion; we will use it to construct (1 c)coreett in Section 2.2. The resulting scheme yields
a (1 + -paapooxximttion with ò (s logg + dk log n + min(e".." (c"r))) bits of communication and O (log n log k) rounds, with additional optimizations for the case k = O (log given in the ap- pendix. Existing bicriteria algorithms in the blackboard model suffer from communication bottle- necks, e.g., the classical Mettu-Plaxton protocol (Mettu & Plaxton, 2004) and the subsequent adap- tations (Chen et al., 2016) sample O (A) points in each of O (log n) rounds, incurring O ( (dk log" n) bits of communication. These costs are prohibitive for our target guarantees.
To overcome these barriers, we adapt the adaptive sampling framework originally developed for k-median in the centralized setting (Aggarwal et al., 2009; Balcan et al., 2013). The procedure repeatedly samples points in a manner reminiscent of kmeans++ (Arthur & Vassilvitskii, 2007; Bahmani et al., 2012), but now distributed across servers. In each iteration, j with probability proportional to Dj. the sum of the 2-th power of the distances from its points to the current sample, and then sample points within server j according to the adaptive distribution. A naïve implementation requires reporting each Dj after every iteration, leading to O (sk log n) communication, which too expensive. To implement this step efficiently, we design the subroutine
first sample server
LAPYSAMP which draws from the adaptive distribution using only approximate values D; maintained the blackboard. Our key innovation is to update these estimates lazily: each site reports a new value only when its true D, changes by more than a constant factor, which we show suffices for the purposes of adaptive sampling.
4

---

Published as a conference paper at ICLR 2026
Lemma 2.1.
There exists an algorithm LAZYSAMPLING that samples from the adaptive sampling
distribution with probability at least 0.99 provided that DD; S DD < D3 for a fixed constant À > 1. The algorithm uses Ô (log 8 + dl log n) bits of communication.
The LAZY algorithm is a communication-effiienn subroutine for adaptive sampling in the blackboard model, formally described in Algorithm 4 in Appendix B. Each server j maintains an approximate weight Dj for its local dataset, satisfying D2 S D; S >DJ, where Dj is the sum the z-th powers of distances from its points to the current sample. The coordinator first selects a server j with probability proportional to D E: D;, then requests point y E Xj, sampled with probabil- ity dg/Dj. By updating the Dj lazily, i.c.. only when D, changes significantly, LAZYSAMPLING ensures points are drawn close the true adaptive distribution while drastically reducing commu- nication. The algorithm either returns a sampled point or I. and uses only Ô (log s + d logg)) bits per round, enabling scalable execution of the bicriteria algorithm across 8 servers. This ensures that each site communicates only O (log n2) updates, so the total communication for the constant-factor
approximation is reduced to Ô (s log + kd log nt), since each server can only update Dj total of O (logn) times assuming all points lie in a grid with side length poly(n). Because lazy updates rely on approximate values, the protocol must occasionally verify whether the aggregate estimate Σ, Dj is still close to the true sum Σj Dj. For this purpose, we use the subroutine LISAMPLING, which tests whether the two sums differ by more than a constant factor.
Lemma 2.2. There exists an algorithm LISAMPLING that takes input (Di)je()) so that Dj 2 Dj for all j E [s]. Let ò = E]e(ss Dj and D = Eje{s D, and let μ > 1 be a parameter. If pf & D, then L1 AMPLING returns True with probability at least 5. If HD >> D, it returns False with probability at least - 8. The algorithm uses Ô ((log s + log log n) log 1 bits of communication.
L LISMPLINGG checks whether the sum of approximate site costs D is within a constant factor of the true total D by sampling a few sites and aggregating the rescaled sampled values. If the aggregate sufficiently close to D, the algorithm returns True; otherwise, it returns Fa False, providing a high- nigh-probabbiltyy guarantee that the lazy estimates remain accurate; the algorithm is presented as Algorithm in Appendix D.2. While this lazy strategy could require up to O (s log n) rounds, we further reduce the round complexity by delaying all updates until the global sum Ej D2 decreases by constant factor. This event is naturally detected when no new point is sampied in a round, and synchronizing updates in this way brings the total number of rounds down to O (log n log k)). Finally, to reduce communication further, we use the subroutine POWERAPPROX, which encodes each D, to within a constant factor using only O (log log n) bits:
Theorem 2.3. Given m -poly(n) and a constant X > 1, there exists an algorithm POWFRAPPROX((,,) X) that outputs mn encoded in O (log log n) bits, such that m S m- < am.
Given m and a base À > 1, POPERAPPROX computes the smallest integer such that X approx- imates m from above, i.e., m S X < Am, and returns This allows each site communicate a concise representation of its cost using only O (log log n) bits, which can then be decoded to obtain constant-factor approximation of the original value; we give the full details in Algorithm 5 in Ap- pendix B. Combined with AMPLING and LISAMPLNGG this ensures accuracy while keep- ing communication linea. The protocol proceeds by sampling points with LAZYSAMPLING, verifying accuracy with L.MAPIP.NGG, and refreshing estimates via POWERAPPRON only when necessary. To limit round complexity, sites synchronize updates by reporting only when the global sum Σ, D, decreases by a constant factor, detected whenever round fails to sample new point. This reduces the number of rounds from O (s log n) to O (log n log k). Figure 2 informally summa- rizes the procedure, with the formal procedure appearing in Appendix D.3. Altogether, this yields the first (O (1), O -bieriiiiii approximation for (k, =)-ccurteiin in the blackboard model with near-linear communication and polylogarithmic rounds:
Lemma 2.4. There exists algorithm that outputs set S such that |S| = O (k) and (S, X)= S O (1) cost(Copr) X) with probability at least 0.98, where COPT is the optimal (k, clcusstriin of X. The algorithm uses Ô (s logg n + log n) bits of communication and O (log n log k) rounds of communication with probability at least 0.99.
5

---

Published as a conference paper at ICLR 2026
Algorithm: Bicriteria Approximation for 2)) Cluusterg (Simplified)
1. Input: Dataset X; for each site i E [s].
2. Output:
Set S that is an (O (1), (1)) bicrritriaa approximation.
3. Initialize:
Sample one point into S and compute approximate distances {D₃} for each site.
Set counters: N = O (k), M = O.
4. While N (sample roughly points):
Sample new points into S using LAZYSAMPLING,
Check accuracy of approximate distances {D,} with LISAPPLING.
If distances are accurate, sample more aggressively.
Otherwise, refine approximate distances {Dy} using POWERAPPROX.
Update M with the number of points successfully added.
5. Return S.
Fig. 2: Informal version of bicriteria approximation through adaptive sampling.
2.2 (1 + E)-CCRESET CONSTRUCTION
To achieve a (1 + e)-coreset for (k, 2ccluuseing on an input dataset given an (0) (1))- bicriteria approximation S, we the following notion of sensitivity sampling. For each center 8y E S, let C2 c X be the cluster centered at 8y. For a point æ E Cj. let Ap := cost(C,, S) denote the average cost of Cj- For Cj. define
cost A cost(C,,
cost S) cost(X,S) + cost(X, ())
m(x) =
k|C,]
We define sensitivity sampling to be the process where each point is sampled with probability proportional to a constant-factor approximation to jlz)). Then we have the following guarantees:
Theorem 2.5. (Bansal et al., 2024) Sampling Ô (mmt() points from constant-factor ap-
proximations to the sensitivity sampling probability distribution and then reweighting provides a (1 coreeset for Euclidean (k, cllustennn with probability at least 0.99.
We remark that Bansal et al. (2024) obtained optimal bounds for k-median, which immediately extend to our framework as well; we omit further discussion as naturally generalizes. To apply the sensitivity sampling framework, we require constant-factor approximations of the cluster sizes |Cj] and costs cOst(C,, S). given a bicriteria solution S. However, directly uploading these quantities from servers for O (k) clusters would cost O (sk log log n) bits, which is too high. Instead, adapt Morris counters (Morris, 1978) for the purposes of distributed approximate counting:
Lemma 2.6. Suppose each server holds numbers n4.j and we have [Nyl = Σi= Ri, =
(oly( There exists algorithm DISTMORRIS that outputs (N₂} such that Ñ, E N for all j E [k), with probability 0.99 using Ô (s + is klog n) bits of communication.
Our Morris counter protocol collectively maintains counter Tj and increments it with probability for each item in cluster Cj. This provides constant approximation the cluster size |Cyl- Crucially, if a site does not change the global counters [ry], then it only needs to send a single bit to signal no update. Otherwise, each of the (k) counters can only increase most (log n.) times, so the total upload cost for these approximations is O (k log n) bits. We can perform similar protocol to approximate the cost of each cluster cos S). so that overall, the total communication for these
approximations Ō (s + log n) bits. Given these approximations, the servers can then perform sensitivity sampling locally. Finally, we require efficient encoding of each point sampled by sensitivity sampling. Informally, each point x is encoded as x' = xs(x) + y'. where IT (2) is the nearest center in S s, and is the offset vector s(( whose coordinates rounded to

---

Published as a conference paper at ICLR 2026
the nearest power of (1 + E'), where poly (E, log(nA] The formal details are given in
Appendix B. Putting everything together, Algorithm achieves the guarantees in Theorem 1.2.
Algorithm (1+ E) coreset for the blackboard model
Input: A bicriteria set of centers S with constant-factor approximation and ||| = O (k) Output: A (1 + coreset A
1: Use DISTMORRIS to get O a1)-approximation for [Cyl and cost(C;, for all j E [k] on the blackboard
2: m + O [ min(E
Set coreset size
3: for +- 1 to \\ Send local approximations to sensitivities do
4: A; 4
5: Compute (((x) as an O (1)) (1)-approximation of ((x)) locally for all x E X;
6: Upload (x()) ExEx, m((x) blackboard
7: end for
8: Sample site with probability Ei= [(X)) independently for m times. DSensitivity sampling
p(X.)
9: Let m, be the number of times site i is sampled and write my on blackboard
10: for
Iterate through sites produce samples do
11: A, 0
for [m,]] Sample my points from site do
13: Sample æ with probability Ps xXXT
j(xx)
14:
if x is sampled Efficiently encode each sample then
15:
Let x be x efficiently encoded by S and accuracy e' = poly(E)
16:
A U { mp(tz)) where faxx) is (1 (1++))appree))) aapproximmttoon of j(x)
end if
18: end for
19: Upload A; to the blackboard
20:
end for
21:
- U.
22:
return A
DISTRIBUTED CLUSTERING PROTOCOLS IN THE COORDINATOR MODEL
We now turn to the coordinator (message passing) model, where each server communicates only with the coordinator over private channels. A direct simulation of blackboard protocol would require O (dsk n) bits, since O (k) rounds of adaptive sampling would need to be executed across servers. To avoid this prohibitive cost, we design protocol that simulates adaptive sampling without sending points explicitly to all sites. We first apply a Johnson--indenseee reduce the dimension
transformation
d' O (log(sk)), preserving pairwise distances up (1 = E). We can then perform adaptive sampling in the projected space, so that when a point s is selected, only its projection T(s) is communicated. To efficiently approximate such locations, we introduce the subroutine
which transmits an approximate version of any point y using only dl log & polylog (log n, : bits, rather than the (d n) bits required for exact communication:
point y and dataset X, there exists CERCIIATCOMMUNICTIION that uses dlogg polylog(log n, 1. bits of communication and sends ÿ such that ||y Ø12 S min El|x vll2 with probability at least ò
Lemma 3.1.
Given
algoritiu
allows site to locate an approximate version of the co- ordinator's point y using very little communication. For each coordinate i, the site first identifies the closest local value si to (() via binary search using the HiGhPRoeGREATER cOl. If ( does not exactly match, an exponential search determines small offset ( so that (4) + (9 approximates (8) within a factor of (1 +c). By doing this coordinate-wise. the site can efficiently reconstruct a point ÿ that is close to y. guaranteeing y H12 S E|x - y/2 for any local point x E X, while sending only small number of bits. This approach combines the intuition of
Intuitively, ELTICIENT
proto-

---

Published as a conference paper at ICLR 2026
searching for the "nearest neighbor" along each coordinate with controlled, approximate refinement, as illustrated in Figure 3.
Algorithm: BERCCEATCOMMUUNCCTTOOXX,
(informal)
1. Input:
A set of points X (x1,..., It) owned by one site.
A point from the coordinator.
Accuracy parameter E (0. 1) and failure probability 5.
2. Goal: Send approximate location y to the site such that ll Øl1 S E||l vll for any
X with probability 2 1 5.
3. For each coordinate
to d:
Sort points in X by their i-th coordinate.
Use local binary search via HIGH HICHPROBGREATEERTHANN to find the closest point i;, to
y()
If ( equals 22! set Ay
Otherwise:
Determine the direction sign(y - 2.
Use exponential search with HIGIPPROEGREATERTIAN to find a value Ay so that (t)
Tt + Ay approximates (9) within factor (1 + +)).
Set g((+) = 3i + Ay
(8)
4. Return (7 ()))
Fig. 3: Informal version efficient communication in the message-passing algorithm. For full algorithm, Algorithm 15.
Given a bicriteria approximation obtained from the above efficient implementation of adaptive sampling, next perform sensitivity sampling to construct (1 + coresset. Unfortunately, each server can now assign point x to another center instead of the closest center s if cost(2, s') is very close to cost(2r, s). Consequently, the sizes ICj and costs cost(Cj, S) for the purposes of sensitivity sampling may be incorrectly computed by the servers. However, this does not compromise the correctness: the sensitivity analysis of Bansal et al. (2024) only requires that each point be assigned to center whose clustering cost is within constant factor of the optimal assignment. Thus, our procedure still achieves (1 _ coresett by sensitivity sampling. Once points are sampled, each site encodes the coordinates of its sampled points using the same efficient encoding scheme as in the blackboard model, c.f., Lemma 1.13, ensuring that only compact representation sent back coordinator. This combination of approximate center assignments and efficient encoding preserves both accuracy and communication efficiency. We give the algorithm in full Figure 4, which achieves the guarantees of Theorem 1.1, deferring full details to Appendix E.
4 EMPIRICAL EVALUATIONS
In this section, present a number of simple experimental results on both synthetic and real- world datasets that complement our theoretical guarantees. We consider k-means clustering in the blackboard setting, using the previous algorithm of Chen et al. (2016) based on Mettu-Plaxton, de- noted MP, baseline. We also implement two versions of our distributed protocol, with varying complexity. We first implement our constant-factor approximation algorithm based on adaptive sam- pling, denoted AS. Additionally, we implement our constant-factu approximation algorithm based on our compact encoding after adaptive sampling, denoted EAS. All experiments were conducted on Dell OptiPlex 7010 Tower desktop equipped with Intel Core 17-3770 3.40 GHz quad-core processor and 16 GB of RAM. We provide all code at ht htsp:: / hht. com/ samsonann camsonzhou/ distributed- el uster.
8

---

Published as a conference paper at ICLR 2026
Algorithm: (1 + -c-rreett for the coordinator model (informal)
(1) Each site computes a local (1 + =/2)-coreset P.
(2) Coordinator broadcasts a JL transform и to all sites.
Initialize solution set { with a random point.
(4) For i to O (k) iterations (for bicriteria solution):
Using EFTCIENTCOOMUNNCATTONN send approximation (00 of center 8; to site
Sites compute approximate costs D, and send to coordinator.
Coordinator selects next center 8; into using LAZY S AMPLING.
Sites compute cluster sizes and costs, send constant approximations coordinator.
Coordinator computes total approximations and broadcasts sites.
Sites compute approximate sensitivities ((x). send total coordinator.
(8)
Coordinator samples = min(e",,2+z) points across sites based sensitivities; sites sample points and encode with EIFCIENTCCMMUUNIATIN
Merge sampled points into final coreset A' and return.
Fig. 4: Informal version of pessage-passing algorithm. For full algorithm, see Algorithm 16.
Clustering Custs
Communication Costs
1.5
8000
NP fiimis
A4 Cormss
E45 Comme
Communs Compuncatton
40:00
1.0
2000
M4 Ccol
Cokls
1000
E15 Canls
Sampping cooffiliene
Sampling coofficlent
(a) Clustering costs
(b) Communication Costs
Fig. 5: Experiments for clustering costs and communication costs on DIGITS dataset
4.1 REAL-WORLD DATASET
To evaluate our algorithms. we conducted our k-means clustering algorithms on the DIGITS dataset (Alpaydin & Kaynak, 1998). which consists of 1,797 images of handwritten digits (0-9) and thus naturally associates with k = 10. Each image has dimension 8 8, represented by 64 fea- tures, corresponding the pixel intensities. This dataset is available both through seikit-lee and the UCI repository, and is popular choice for clustering tasks due to its moderate size and well- defined classes, allowing for clear evaluation the clustering performance.
For parameter our baseline MP uniformly selects & initial points and then iteratively discards candidates over e clog, n rounds. Our AS algorithm iteratively samples single center in each of ck rounds, with probability proportional to its distance from the previously sampled centers. Finally, EAS quantizes the coordinates of each chosen center of AS to the nearest power of two, mimicking low-precision communication. We compare the clustering costs of the algorithms in Figure 5a and their total communication costs in Figure 5b, both across e E {11, 12, 12,..., 20).
Our results indicate that although adaptive sampling (AS) always outperforms Mettu-Plaxee (MP), when the number of samples is small, the gap is relatively small, so that the rounding error incurred by our efficient encoding in EAS has similar clustering costs for
in Figure 5a. Surprisingly,

---

Published as a conference paper at ICLR 2026
the communication cost of MP did not seem to increase with indicating that all possible points have already been removed and no further samples are possible. Nevertheless, for all c > 11, our algorithm in EAS clearly outperforms MP and therefore the previous work of Chen et al. (2016) for both clustering cost and communication cost, c.f., Figure 5b. Our algorithm EAS also exhibits clear compared to algorithm AS, as the
tradeoff's in the clustering and the communication former is simply rounding of the latter.
4.2 SYNTHETIC DATASET
To facilitate visualization, we generated synthetic datasets consisting of two-dimensional Gaussian mixtures, where the low dimensionality (2D) was chosen to enable visualization of the resulting clusters. Specifically, we created k = Gaussian clusters, each containing n = 100 2 points, for total of 512, 000 data points. Each cluster was sampled from distinct Gaussian distribution with a randomly selected mean in the range [-10, 10]2 and a randomly generated positive-definite covariance matrix ensure diverse cluster shapes.
We implemented the baseline MP by sampling k points uniformly and pruning candidates based on distance threshold that doubles each round, across clog2 rounds, where is hyperparameter. We implemented our algorithm AS by iteratively sampling one center per round across ck rounds, selecting points with probability proportional to their distance from existing centers. EAS then modifies AS by rounding each selected center's coordinates to the nearest power of = 20.25 simulating low-precision communication.
Cholks and Calday
Chocaniig Ctulo
DK
1.6
12:0
115
340
Qutar
5.5
2:4
-.2
Ohiar
5.0
0.8
Corfict
Coffict
(a)
(b)
(c)
Fig. 6: Experiments for clustering costs and communication costs synthetic dataset
We varied the sampling coefficient E (11,.... 20) and measured the k-means clustering cost (i.e., the total squared distance from each point highlight the performance trade-off's between sampling strategies increases. Communication costs were also computed (though not plotted), assuming 32 bits per coordinate MP and AS, and 5 bits per coordinate for EAS due quantization.
assigned center). The results, shown in Figure 6,
Our results for synthetic data echo the trends for the DIGITS dataset. Namely, for e > 2, our algorithm in EAS clearly outperforms MP for both clustering cost and communication cost, c.f., Figure 6c, while also demonstrating clear tradcoff's in the clustering cost and the communication cost compared to algorithm AS. We plot the resulting clustering by EAS in Figure 6a.
ACKNOWLEDGMENTS
David P. Woodruff is supported in part Office of Naval Research award number N000142112641 and Simons Investigator Award. Samson Zhou is supported in part by NSF CCF-233541 Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph E. Powe Junior Faculty Enhancement Award.
REFERENCES
Ankit Aggarwal, Amit Deshpande, and Ravi Kannan. Adaptive sampling for k-means clustering. In International Workshop Approximation Algorithms for Combinatorial Optimization, pp-
10

---

Published as a conference paper at ICLR 2026
15-28. Springer, 2009. 4, 14, 18, 21, 22,
E. Alpaydin and C. Kaynak. Optical Recognition of Handwritten Digits. UCI Machine Learning Repository, 1998. DÔI: https///bi.orr/1022444////33
42
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Pro- ceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp- 1027-1035, 2007. 4, 14
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, and Samson Zhou. Private vector mean estimation in the shuffle model: Optimal rates require many messages. In Forty-first International Conference on Machine Learning, ICML., pp. 1945-1970, 2024. 14
Bahman Bahmani, Benjamin Moscley, Andrea Vattani, Ravi Kumar, and Sergei Vassilvitskii. Scal- able k-means+++ Proc. VLDB Endow., 5(7):622-633, 2012. 4, 14
Muria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median cluster- ing on general communication topologies. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems, pp. 1995-2003, 2013. 2, 4, 14, 16, 41
Nikhil Bansal, Vincent Cohen-Addad, Milind Prabhu, David Saulpic, and Chris Schwiegelshohn. Sensitivity sampling for k-means: Worst case and stability optimal coreset bounds. CoRR, abs/2405.01339, 2024. 2, 3. 6, 8, 13, 15, 16, 18, 34
Vladimir Braverman, Dan Feldman, Harry Lang, Adiel Statman, and Samson Zhou. Efficient coreset constructions via sensitivity sampling. In Asian Conference Machine Learning, ACML, pp- 948-963, 2021.
Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for core- sets. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 462-473, 2022. 1
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H.-C. Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang, and Samson Zhou. Relative error fair clustering in the weak-strong oracle model. In Forty-second International Conference on Machine Learning, ICML, 2025.
Maria Sofia Bucarelli, Matilde Fjeldsø Larsen, Chris Schwiegelshohn, and Mads Toftrup. On gener- alization bounds for projective clustering. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurIPS, 2023.
Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In 40th Annual Symposium on Foundations of Computer Science, FOCS, pp. 378-388, 1999.
Moses Charikar, Chandra Chekuri, Tomás Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. In Proceedings of the Twenty-Ninth Annual ACM Symposium the Theory of Computing, pp. 626-635, 1997.
Moses Charikar, Sudipto Guha, Êva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. In Proceedings of the Thirty-Firs Annual ACM Symposium on Theory of Computing, pp. 1-10, 1999. 1
Moses Charikar, Liadan O'Callaghan, and Rina Panigrahy. Better streaming algorithms for cluster- ing problems. In Proceedings of the 35th Annual ACM Symposium Theory of Computing, pp- 30-39, 2003.
Jiecao Chen, He Sun, David P. Woodruff, and Qin Zhang. Communication optimall distributed clustering. In Advances in Neural Information Processing Systems 29: Annual Conference on
Neural Information Processing Systems, pp. 3720-3728, 2016. 2, 3, 8, 10, 14
11

---

Published as a conference paper at ICLR 2026
Vincent Cohen-Addade Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svensson. Fast and accurate SkS-means++ via rejection sampling. In Advances Neural Information Pro- cessing Systems 33: Anmual Conference Neural Information Processing Systems, NeurIPS, 2020.
Vincent Cohen- Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In STOC: 53rd Annual ACM SIGACT Symposiam on Theory of Computing, pp. 169- 182, 2021. 2, 3, 13
Vincent Cohen-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, 2022a. 1, 2, 13, 17
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. Improved coresets for euclidean k-means. In NeurIPS,
2022b. URL /ttt:://paerrs..o nips. wttppprrrr.ipsscccppppeeeeeeeeee ttsppppscpppppeillleeeeeeeeeeeee
1203955-8b00tt90c322ccee... -aee445AAbbsraccc Contttt-oooeeeeeeeeeeeee html. 2, 13, 17
Vincent Cohen-Addad, David Saulpie, and Chris Schwiegelshohn. Deterministic clustering in high dimensional spaces: Sketches and approximation. In 64th IEEE Annual Sympoxium on Founda- tions of Computer Science, FOCS, pp. 1105-1130, 2023a.
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, 2023b. 14
Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, and Samson Zhou Fair clustering in the sliding window model. In The Thirteenth International Conference on Learning Representations, ICLR, 2025a.
Vincent Cohen-Addad, Silvio Lattanzi, and Chris Schwiegelshohn. Almost optimal PAC learning for k-means. In Proceedings the pp. 2019-2030. ACM, 2025b.
the 57th Anmual Symposium on Theory of Computing, STOC,
Vincent Cohen-Addad, Liudeng Wang, David Woodruff, and Samson Zhou Fast, space-optimal streaming algorithms for clustering and subspace embeddings. CoRR, abs/2504. 16229, 2025. 20
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning- augmented k-means clustering. In The Tenth International Conference on Learning Represen- tations, ICLR, 2022.
Dan Feldman and Michael Langberg, A unified framework for approximating and clustering data. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pp. 569-578, 2011.
Lingxiao Huang and Nishecth K. Vishnoi. Coresets for clustering in euclidean spaces: importance sampling is nearly optimal. In Proccedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC, pp. 1416-1429, 2020. 13
Lingxiao Huang, Jian Li, and Xuan Wu. On optimal coreset construction for euclidean (k, z)- clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, pp. 1594-1604 2024. 2,
Zachary Izzo, Sandeep Silwal, and Samson Zhou Dimensionality reduction for wasserstein barycenter. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurlPS, 2021. 13,
William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. conference in modern analysis and probability (new haven, conn., 1982), 189-206. In Contemp. Math, volume 26, 1984. 17
Daniel M Kane and Jelani Nelson. derandomized sparse johnson johnson-lindensten Iindenstrausss transform. arXiv
preprint arXiv: /506.3585, 2010. 18
12

---

Published as a conference paper at ICLR 2026
Karthik C. S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, and Samson Zhou. On approx- imability of lg min-sum clustering. In 41st Internationaa Symposium on Computational Geometry, SoCG, pp. 62:1-62:18 2025.
Yurii Lyubarskii and Roman Vershynin. Uncertainty principles and vector quantization. 1EEE Trans. Inf. Theory, 56(7):3491-3500 2010. doi: 10. 10.1109/1112201022043222 URL https: / //doi. 10. 1109/TIT 2010 2048848.. 14
J MacQueen. Classification and analysis of multivariate observations. In 5th Berkeley Symp. Math. Statist. Probability, pp. 281-297, 1967.
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Performance johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 5 Annual ACM SIGACT' Symposium on T'heory of Computing, STOC, pp. 1027-1038, 2019. 13, 17
Ramgopal R. Mettu and C. Greg Plaxton. Optimal time bounds for approximate clustering. Mach. Learn., 56(1-3):35-66 2004. 4, 14
Adam Meyerson. Online facility location. In 42nd Annual Symposium Foundations of Computer Science, FOCS, pp. 426 431, 2001.
Robert Morris. Counting large numbers events in small registers. Communications of the ACM, 21(10):840-822, 1978. 6, 31
Noam Nisan. The communication complexity of threshold gates. Combinatorics, Paul Erdos is Eighty, 1(301-315)6, 1993. 18, 35
Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In 59th IEEE Anmual Symposium on Foundations of Computer Science, FOCS, pp. 802-813, 2018. 13, 17
Hugo Steinhaus et al. Sur la division des corps matériels en parties. Bull, Acad, Polon. Sci, 1(804): 801, 1956.
Murad Tukan, Xuan Wu. Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 5391-5415, 2022.
David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding win- dow model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS 2023, 2023.
Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang, and Zengfeng Huang. Space complexity of euclidean clustering. IEEE Trans. Inf. Theory, 71(6):4515 4536) 2025. 13
A TECHNICAL OVERVIEW
In this section, we provide technical overview for our distributed protocols, for both the blackboard model and the coordinator/meessaeeeeea model.
Previous approaches and why they do not work. A natural question is whether simple ap- proaches could achieve similar communication bounds. One might hope, for instance, that com- bining the space upper bounds of Zhu et al. (2025) with existing distributed clustering algorithms would suffice. However, not immediately clear how to translate space bounds into better dis- tributed clustering bounds. For instance, an application of their space bounds, Zhu et al. (2025) achieved distributed protocol with total communication Ô Tdk
g ). for appropriate ranges of k and e, which is actually worse than the third row of Figure and thus worse than our bounds of Ô (sk + dk
e + dk log n)) for the same regime.
Another approach might be that each server computes local coreset, e.g., Huang & Vishnoi (2020); Cohen-Addal et al. (2021; 2022a;b); Bansal et al. (2024), possibly with the incorporation of dimen- sionality reduction, e.g., Sohler & Woodruff (2018); Makarychev et al. (2019); Izzo al. (2021),
13

---

Published as a conference paper at ICLR 2026
and then either broadcasting these coresets in the blackboard model or sending these coresets to the coordinator in the message-passe passing model. However, this uses communication O add bits, compared to our bounds of Ô (sk + de 2 + dk log n.). Similarly, any approach based on locality sensitivity hashing, possibly with the aid of dimensionality reduction or other compressions, e.g., Kashin representations (Lyubarskii & Vershynin, 2010; Asi et al., 2024), would require at least each server computing a local coreset and thus succumbing to the same pitfalls. These limitations high- light that overcoming the inherent overheads in naíve strategies is far from straightforward, and mo- tivate the need for new techniques. Our framework is designed precisely to address these challenges by simulating centralized algorithms through communication-opiiaal primitives, thereby breaking the bottlenecks that defeat such strawman approaches.
g log n)
(1 + ---orestt for the blackboard model. Our starting point is the distributed protocol of Chen et al. (2016), which first adapts the central RAM algorithm of Mettu & Plaxton (2004) to publish a weighted set S of O (k log n) centers that is constant-factor bicriteria approximation for (k: 2)- clustering. It can be shown that constant-factor approximation to (k, 2) -clustrrii on S achieves a constant-factor approximation C' to the optimal clustering on the input set X. Since S is already available on the blackboard, this step is immediate. The total communication cost of their algorithm is O ((s + kd) log² n.).
We observe that the sites can easily calculate the number of points in X served by each center E C. We recall that using this information as well cost(X, C*) can be used to find constant- factor approximations of the sensitivity s(x) of each point æ, c.f. (Cohen-Addad et al., 2023b).
Thus, the sites can subsequently sample Ö (min (ka
(Z min()f.c++))) points of X using sensitivity
sampling to achieve (1 + co-cesstt. We can then use efficient encoding scheme to express each sampled point in O (log k + dlog (2 d, log(nA))) bits. This achieves the desired dependency for the points acquired through sensitivity sampling, but the communication from the constant-face approximation is sub- sub-optimal. Thus, it remains to find more communication-effiiiee. protocol for the constant-factor approximation.
Constant-factor approximation in the blackboard model. Although there are many options for the -onstant-factor approximation in the blackboard model, they all seem to have their various shortcomings. For example. the aforementioned Mettu-Plaxton protocol (Mettu & Plaxton, 2004) re- quires O (log n) rounds of sampling, which results in O (k log n) points. A natural approach would be to form coresets locally at each site so that the total number of weighted points is (sk) rather than Unfortunately, when generalized to weighted points, Mettu- Plaxttn requires O (log W) rounds, where W is total weight of the points, which is poly(n) for our purposes.
Another well-known prototype is the adaptive sampling framework (Aggarwal et al., 2009; Balcan et al., 2013), which can be used to implement the well-known kmeans+ algorithm (Arthur& & Vas- silvitskii, 2007) in the distributed setting (Bahmani et al., 2012). This approach iteratively samples a fixed number of points with probability proportional to the z-th power of the distances from the previously sampled points; adaptive sampling samples O (k) points for O (pprrooxxiiaao while However, since all sites i E [s] must report the sum D; of the z-th power of the distances of their points to the sampled points after each iteration, these approaches naïvely require O (sk log n) bits of communication, which is prohibitive for our goal.
kmeans++ + samples l points for O (log k) ---a-ppoxiimatin
Instead, we perform lazy updating of the sum D, of the z-th power of the distances of their points to the sampled points. The blackboard only holds estimates D, for D., based on the last time the site i reported its value. The sites then attempt adaptive sampling, where the site is sampled with a probability proportional to D.. When sampled, site i uses D, to attempt to sample a point locally, but this can fail because D, 2 D,, which means that randomly chosen integer in D, may not correspond to an integer in D;. Fortunately, the failure probability would be constant D, is a constant approximation of D:. so the total number of rounds of sampling is still O (k) by the Markov inequality. If the site fails to sample a point, we expect D, to be a constant fraction smaller than D., prompting site to update its value D; on the blackboard. This can happen at most O (s log n) times. If each site i rounds D; to a power of 2, then D; can be approximated within
14

---

bits, which Published as a conference paper at ICLR 2026
factor of by transmitting only the exponent of the rounding, using O (log logn) bits. Thus, the total communication for the constant-factor approximation is O (s log n + kdlog
The primary downside is that the total number of communication rounds could reach O (s n)) since each of the sites may update its D, value up to O n) times.
Communication round reduction in the blackboard model. A natural approach to round re- duction would be to have all s sites report their updated D; values when we fail to sample point. However, because we sample O (k) points, this results in communication complexity O (sk).
Instead, we check whether the global weight EiE[el Dj has decreased by 64 compared to the amount Eie(s) D; on the blackboard. To do this, we first perform the L sampling in each round. That is, the blackboard picks the site with probability p: Eieto D.
D. and computes D. Observe that in
expectation this quantity is Eiels] Dj and its variance at most (Eiej4) D:)2, up constant fac- tor. Thus, repeating O (1) times and taking the average, we get a EiE(e) D, additive approximation to Die(s] D.. which is enough to identify whether the sum has decreased by factor of from Eie(s) D;. We can then take O (log log n) instances to union bound over O (log n log k)) iterations.
J Now the other observation is that as long as our sampling probabilities have not decreased by 64 then we can simultaneously take many samples at the same time. Thus, we start at i = 0 and collect 2' samples from the s sites using the adaptive sampling distribution. We then check if the total weight Eietol D, is less than 64 Eiel
Di, and if not, we increment i and sample 2 samples, and repeat until either 2' k or the total weight Eie(o) D; is less than Eiero Dj.
Note that this takes O (log n log rounds of sampling, which is enough for the failure probability of the In sampling procedure. Moreover, since we can use O (log log n) bits of communication to approximate I,1 sampling by rounding the values of D, to a power of 2 and returning the exponent.
D: we require all sites to update their weights, then the communication is Ô (s log n + kd log n) across the (log n log k) rounds of communication.
Since each time the total weight Eie(s] D; is less than ग Eie(s)
Applying sensitivity sampling in the blackboard model. To apply the sensitivity sampling framework of Bansal et al. (2024), constant approximation of the number of each cluster [C] and the cost of each cluster cOst(C,, S) is necessary, where S is a (O (1), O (1))-bicriteria approx- imation of the optimal solution. Each site needs O (log log n.) bits to upload such constant approx- imation for a cluster. Since there are sites and O (k) clusters, it would lead to O (sk log log n) bits of communication, which is prohibitive for goal. Instead, we adapt Morris counters, which are used for approximate counting in the streaming model, to the distributed setting. We use a counter r to store the logarithm of the number/cost of the cluster, and increase the counter by with probabil- 1 for every time we count the number/cost of the cluster. Each site applies the Morris counters sequentially and only uploads the increment on the blackboard. Similar Morris counters, such subroutine can return constant approximation of the number/cost of the cluster. If all counters remain the same after counted by site, that site needs to use O (1) bits to tell the next site that nothing needs to be updated, which would use at most O (1). Otherwise, O (log log bits are needed to update a changed counter. Since each counter can increase at most O (log n) times and there are O (k) numbers of number/cost of the cluster to be counted, it would use O (k log bits to upload all the updates. Therefore, at most Ô (s + i log n) bits are needed to upload a constant approximation of the number of each cluster |C5l and the cost of each cluster cost SS)
ity 3r
Each site apply the sensitivity sampling locally after knowing constant approximation of the number of each cluster |Cyl and the cost of each cluster cost(C;, S). Combined with the efficient
encoding for the (1 (1+22 correset, we can upload the coreset using O [dlog log n+llogkM min(e g.g++)
achieves our desired bounds for the blackboard model.
Guordinator/meessgeeaasst model. For the message-passiggcconeee passing/coordinator model, our starting point is once again adaptive sampling, which can be performed over O (k) rounds achieve
15

---

Published as a conference paper at ICLR 2026
constant-factor approximation C' using O (skdlogn)) total bits of communication (Balcan et al., 2013). We can again use sensitivity sampling on C' along with our efficient encoding scheme to achieve the desired communication for the subsequent (1 + e)-coreset. Thus, the main question again is how to improve the constant-factor protocol.
To that end, we first introduce subroutine EFFICIENTCOMMUNNCAN of the point using low communication cost. The intuition behind BFFCCINTCOOMUNICATTOON is similar the efficient encoding, which uses the points site owns encode the point we want to send. The only difference is that we use different points to efficiently encode the coordinates for each dimension, rather than just using a single point encode the point we want send.
that send the location
Recall that there exists GREATERTHAS protocol, which given two log bit integers, figures out which one is greater with constant probability, using Ô (log log n) bits of communication. More- over, this procedure can be repeated O (log(sk)) times achieve failure probability poly(sk] to union bound over psly(sk) possible steps. With the help of GREATERTHAN we can compare the coordinates of the points in the i-th dimension z
(6) site owns with the coordinate of the point to
receive ( By binary search, can find the closest coordinate ( y(), which requires O (logn) search times, since the site owns at most points. By another binary search, we can further find Ay that is (1 + -aapprooximation of [z) - /. Since |=5 O = poly(n), need O (log log n)) searches to find (y Since the coordinator needs send the approximate coordinates of the points sampled by adaptive sampling to each site, the total communication cost for adaptive sampling is Ô (dsk log n) bits, which is still prohibitive for our goal.
To address this, we first generate a (1 + O (c))-coreset for each site, so that the size of the dataset of each site is O (k), which leads O (log r2) searches to find the closest coordinate x; to y Fur- thermore, we observe that we only need the approximate cost for each point for adaptive sampling. Hence, we can apply
to project the dataset down to O (log( (sk) dimensions. Therefore, the total communication cost for adaptive sampling is sk polylog(log n, s, k) bits.
After achieving an (1). O (1))-bicriteria approximation for the optimal solution, we can commu- nicate a constant approximation of the number and cost of each cluster using a total O (sk log log n) bits of communication. However, each site may assign the points to an incorrect cluster since only has an approximate location of Bansal et al. (2024) still returns a (1 + s)-coreset if we assign each point to a center so that the distance between them is close to the distance between the point and the center closest to it. Therefore, combined with EFFICIENTCOMMUNICTTIN
Fortunately, the sensitivity sampling procedure of
we can upload the (1 E)-coreset using min 2 polylog(log n, k. !) bits, which achieves our desired bounds for the blackboard model.
dk
B PRELIMINARIES
For a positive integer n, we denote by [n|] the set nI. We use poly(n) to represent an arbitrary polynomial function in n. and polylog(n) to denote polynomial function in log n. An event is said to occur with high probability if it holds with probability at least 1/ poly(m).
Throughout this paper, we focus on Euclidean (k, 2) >)>clustering. Given vectors v. E Rd we let dist(ær, y) denote their Euclidean distance, defined as ||æ: - v/l2, where || v11 = Σ - (I; ) For point x and a set S C RR,, we extend the notation dist(rr S) == min.es dist(z, s). We also use ||>|| to denote the Lg norm of æ, given by || = Σi= कद. Given a fixed exponent 2 2 1 and finite sets X, C Idd with X = {- J. we define the clustering cost cost (X, X C) as
cost (X, = Σ dist(z,,C)²
We now recall generalized versions of the triangle inequality.
Fact B.1 (Generalized triangle inequality). For any z 2 1 and any points x, w, y E IRd, it holds that dist(r, 4)² < 2 (x, w) + dist(w, (.... y)²))
16

---

Published as a conference paper at ICLR 2026
Fact B.2 (Claim 5 in Sohler & Woodruff (2018)). Suppose 2 x, 0, and (0, 1]. Then
22 y
(x+ S (1 + x² +
1+
Next, we define the notion of strong coreset for (k, =--ustrterng
Definition B.3 (Coreset), Let > be an approximation parameter, and let {II,..., [nn...,,,,,,.,., c RRd be of points. A coreset for (k, clcssserii consists of weighted set (S, w) such that for every set C C Ra of centers,
(1
Σ dist(zr, cy² S Σ w(q)dist(q оO² S (1++)) Σ dist(a,, C
gES
We will the following known coreset construction for (k, z)cclsstein
Theorem B.4. (Cohen-Addad et al., 2022a; Huang al., 2024; Cohen-Addad al., 2022b) For any E E (), there exists a coreset construction for Euclidean (k, =l-lustriinn that samples weighted points from the input dataset.
① mmin min h22 min(e", miTs)"
We also recall the classical Johnson-Lindenstran Lindenstrauss lemma, which enables dimensionality reduction while approximately preserving pairwise distances:
Theorem B.5 (Johnson-Lindeesttann) lemma). (Johnson & Lindenstrauss, 1984) Let & E (0. and m O 22's l)gn). Given set X C IR of n. points, there exists a family of random linear maps II: Fd m such that with high probability over the choice of II. for all z, y X,
-1-68 (1=e)||æ v112 I || Tyll2 < (1 [))l) 2/12.
We remark that exist more efficient dimensionality reduction techniques for (k, clustering (Makarychev al., 2019; Izzo et al., 2021) though for the purposes of our guarantees, Johnson-Linddestrauss suffices.
Finally, we recall Hoeffding's 's inequality, a standard concentration bound:
Theorem B.6 (Hoeffding's inequality). Let XI...., , Xn be independent rundom variables with ag S X, < b.for each i. Let S, Ei=1 X,, Then for any >> O,
t2
P(S,, - E[S.]] t) S 2 exx
" (b; a02)²
We next recall the following formulation of sensitivity sampling paradigm, given Algorithm 2.
Algorithm SENSITIVITYSAPPUIN
Input: Dataset X {z1..... In) } [Aj and integer k
Output: Weighted set A = {(a, Wa,)
I: Compute an O (1 }-approximation S (81, 82, ....
S.). Let Cj X be the cluster centered denote the average cost of C₁
8j. For point x E C,, let A, == cost(C,. S)/(C,
2: For & E Cj, let
m(x) ( 1
+ cost S)
cost S)
A cost (X, .T))
k|C,| co,st(C,, cost(X,
3: m < (k/62 min(s mine A+
4: for i m do
5: Sample point independently from the distribution A + AU mys(aa)) }
6: end for
7: return A
17

---

k Published as a conference paper at ICLR 2026
Theorem B.7. (Bansal et al., 2024) Sensitivity sampling, c.f., Algorithm 2, outputs (1 E) cooreset of size O min(s*,g***) for Euclidean (k, =cllustiing with probability at least 0.99.
We next recall the following distributed protocol for determining the larger of two integers. Theorem B.8, (Nisan, 1993) Given two O (logn) bit integers X and Y, there exists a protocol GREATERTHAN that uses Ô (log log n) total bits of communication and determines whether X or
We recall the following protocol for applying the Johnson-Lindenstranee transformation using low communication cost.
Theorem B.9. (Kane & Nelson, 2010) For any integer d > O, and any 0 < =,, 6. < 2. there exists family A of matrices in Rexd with & θ log {)) such that for any E Rd
Pr AEA
Axlla & - 1)1==11, (1 e]|1=] <
Moreover, E A can be sampled using O (log (1) log d) random bits and every matrix E A has at most θ (e- 1 log (t) log (1) non-zero entries per column, and thus Ax can be evaluated in O (a | time if A is written explicitly in memory.
Adaptive sampling. We now introduce the adaptive sampling algorithm from Aggarwal et al. (2009) and generalize the analysis to (k, z)-clustering.
Algorithm ADAPTIVESAMPLING
Input: Dataset X fz1..... Rn C [A]; approximation parameter y 2 1
Output: Bicriteria approximation S for (k, 2) cllustrrn on
1: S + 0, N O (k), (())
2: for p to N do
3: Choose 8, be xy E X with probability Σ.. where 1 d4 cost(1;; .. S {ss}
4:
5: end for
6: return S
(Aggarwal et al., 2009) showed that adaptive sampling achieves a bicriteria approximation for k- means, i.e., z = 2. For completeness, we shall extend the proof to show that works for weighted case and any 2 1, though we remark that the techniques are standard.
Theorem B.10. There exists an algorithm, cff,, Algorithm 3 that oulputs set S of O (k) points such that with probability 0.99, c)) I O (1) cost(Copr,,X) X). where COPT is optimal 2k, cluusterig of X.
As stated, the version of adaptive sampling in Algorithm 3 requires updating cost(r; S) after each update, leading to high cost of communication. We will introduce the lazy sampling algorithm. The combination of our updated adaptive sampling algorithm and the lazy sampling algorithm can provide a lower number of updates required, and thus a lower overall communication cost, while still guaranteeing the result of the (0) bier-bicii approximation.
Suppose that we have sites, every site has local dataset X; and every data point has a sampling weight d,, Let D; Σxex, d, and D Σi= D;- Our goal is to sample point æ with prob- ability Pa D In the case of adaptive sampling, dN is just cost(x, S). To avoid a high cost of communication, our strategy is that the coordinator only holds D, an approximation of real D; that
d,
D, < D, AD,, and only updates D, when it deviates far from D. Then we can use de to sample the point, where D Σi=1 D,.
Since D may be larger than D, the site i will send 1 with probability D.-D. Fortunately, the 7.
probability of returning L constant, and the probability that we sample conditioned returning 1. is just 4z. Therefore, by Markov's inequality, can sample least N points under
18

---

Published as a conference paper at ICLR 2026
Algorithm LAZYSSMPLINS
Input: {dz)zex, the sampling weight; (Di constant approximation to (Di)EE()) that D, -
D, & AD where D; = E.ex, du for every site
Output: Either 1 point sampled under distribution 1. where D = Exex dz
1: - I D 1
2: The coordinator generates an index with probability = D.
D
3: The coordinator sends sampling request to site
4: x: < with probability du D.
5: refurn
the distribution of with probability at least 0.99 after repeating LAZYSAMPLING a total of O (N) times.
Lemma B.11. Let x be the result returned by Algorithm and be the event that Algorithm 4 does not return L. If Dj < Dj < >>Ds, Dj. Pr [8] 2 1 and Pr [æ y|E] 3 Furthermore, there exists some constant 7 2 1 such that after running Algorithm a total of &N times, will
return least N points sampled by the distribution o with probability least 0.99.
Proof. Let Fi be the event that the result is sampled by the site i. Since Pr [F] Pr(E]Fi = Ezex,
D. and
d Ds then by the law of total probability, b1 D.
D.
D
D
D XD
Pr Pr[E|
Σ Pr[ Pr|A]
D D
D
-
For any y E X1, we have
Pr 2
D dy D
D
dy dy D
Pr|x = v|8]
Pr
Pr
D
D
D
D
Furthermore, let
0. LAZYSAPINNN returns _
Z:
1. otherwise.
After rumning LAZYSAMPLING for NN times, the number of times LAZYSAMPLING does not return
is just E7, Z.. Since E [2 = Pr [8] N 7. we have EE Σ 1= Z
N I. By Markov's
inequality, there exists some 7 2 such that Pr Σ> 23 < N will sample least points with probability at least 0.99.
< 0.01. Hence, LAZYSAMPLING
Finally, in Algorithm we recall the standard algorithm that provides an efficient approximate en- coding of number by storing the exponent of the number after rounding power of a fixed base X.
Algorithm 5 POPERAPPROX
Input: Number be encoded m, base À >>1 Output: An integer that X is À approximation of m Let be the integer such that m X < Am 2: return i
Theorem B.12. The output from Algorithm 5 can be used to compute a number in such that m <
m
Am.
19

---

Published as a conference paper at ICLR 2026
Efficient encoding for coreset construction for (k,2) -l-lsserri We recall the following effi- cient encoding for a given coreset for (k, zeclutteri given by Cohen-Addad et al. (2025). Given a dataset X, which may represent either the original inputs weighted coreset derived from some larger dataset, we begin by computing a constant-factor approximation C' for the (k, 2)-clsstering problem on X. For every E X, let ne (x) denote the nearest center in C" can then be decomposed as = (π) + (I (c(())) separating it into its closest center and residual vector.
Each point
To obtain (1 + -aprroximmtii for (k, cllustrrrn it suffices to round each coordinate of the offset vector x TC (z) to the nearest power of (1 + E'), where e' = polyy (e, di log(na)): Let y denote this rounded vector.
We then encode each point as x'= =c + y', storing both the index of the center I (2) and the exponent values the rounded offset. T his representation uses (log + d d ( L log(n bits per point. The full algorithm is detailed in Algorithm 6.
Algorithm 6 Compact Encoding for Coreset Generation in (k: =)-Cuuttrrii
Input: Dataset X C [A] d with weights w(.). accuracy parameter e E (0, 1), number of clusters k
parameter
1, failure probability 8 (0, 1)
Output: (1 + E) appproxxiatee coreset for (ki, 2) cluusering
1: e' f- poly(c")
poly(F.log(rd55))
2: Compute a constant-factor (ks z)-clsttering solution C' on
3: for each E X do
4: Set (2)) as the nearest center to C"
5: Compute the residual vector y' xx-'''c c'(x)
6: Round each coordinate of y/ to the nearest power of (1 + E') to obtain y
7: Define x' (c y), where y stores the exponent for each coordinate
8: Add x' to the new set: X' < (2)
9: end for
10:
return (C"
We have the following guarantees for the efficient encoding from Cohen-Addad et al. (2025): Lemma B.13. Cohen-Addad et al. (2025) Let = E (0, 2). and let X' be the weighted dataset S, constructed using the offsets from the center set O' as defined in Algorithm 6. Then, for any set of centers C' C [A] with |C| S k, the following holds:
(1- CO, S cOst(C, X') S (1 (1+E) cost(C,X),
Lemma 1.14. Cohen-Addad et al. (2025) Let X be coreset where the point weights lie within the range [1, (ndy() Then the transformed set X' forms a (1+ s)-strong coreset for X. and its total space requirement is O (dk log(nA)) + [X| polylog (k: 2, log(ndA)),oog 3) bits.
C ADAPTIVE SAMPLING FOR (k: -L..USTEEI
We first give a high-level overview of why ADAPTIVESAMPLING returns a bicriteria approxima- tion. Let (A, 1- be the clusters that correspond achieve ( (1) -pprroooxiitio to the optimal cost if the cost for every cluster A; induced by S already an O (1))-pproximation for cost(A; Aj, CorT), where CoPr is the set of centers for the op- timal solution. We define cluster A, cost(A, (Aj, COPT), and otherwise we call A, bad cluster. We can show that with constant probability, ADAPTIVESAMPLING samples center that can transform a bad cluster Markov's 's inequality, it follows that we can eliminate all bad clusters in O (k) rounds of sampling, resulting in constant-factor approximation.
optimal (As, -elluttrnn, Then we can
good cluster if its cost is an O (1) (pp-ropooxiaation to
good one. Then, by
We use the following definition of good and bad clusters. Definition C.1. Let S, be the sampled set S in the i-th round in Algorithm 3 and let CoPT = be optimal solution for (k, cluusttrri
(c,, .2. C C
20

---

Published as a conference paper at ICLR 2026
For j [k], let A, be the points in X assigned Cj in the optimal clustering. breaking ties arbi- trarily, i.e. A, = {a E dist(2, Cÿ) I dist(r, ct), VE [k]}. We define
Good; = {A, cost(Aj, ( S:) S Ys cost(Aj, Corr)}
Bad; (A1, A2, A&] Good;
where 7 = 22+ (3 + -
By definition, if every cluster a good cluster, we can guarantee that S an bicriteria approximation. We will prove that either S is already (O (1), O (1))-bicriterri approx- imation, or else we will reduce the number of bad clusters after every sampling with some constant probability, which would imply that we can achieve (1)-approximation after sampling O (k) points.
Lemma C.2. Suppose cost (X, > 2n²² CosT), then
Pr Bad [Bad;]] 8
for some constant 8 0.
Lemma C.2 the generalization of Lemma 5 in Aggarwal et al. (2009). We will prove Lemma C.2 by breaking the proof into several lemmas. We first consider specific parameterization of the generalized triangle inequality.
Lemma C.3. For any 5, y: P E R4,
dist(a, u)² 2 dist(r, - + (1+ +2) dist(y, 14)..
Proof. The claim follows from applying Fact B.2 with 1, so that by the triangle inequality, dist(æ, 8)* S (dist(x,,)) dist(y, 1²))
(i)t(y,,))* S 2 dist(r, nu)² + (1 22)² dist(y.
We first show that we will sample a point from a bad cluster with constant probability every round. This statement is analogous to Lemma in Aggarwal et al. (2009).
Lemma C.4. In the i-th round of our algorithm, either cost (X, S.) < 2 7s cost(X, (X, CoPT) or else the probability of picking point from some cluster in Bad; is at least 1 2.
Proof. Suppose cost (X, 27² 7/s cost(X, Copr). Then the probability of picking x from some bad cluster is
Pr [ar Bad:] EA,eBad, EmEA, di Σx,x di
EA, EmEA di Emex di
Here, we remark that di is the distance from Ii S,-1 defined in Algorithm 3. Since St-1)) S To cost(A,, CoPr) if A, E Good,, and cost(X, > 2n² -7s cost(X, CoPT) by the condition we hold.
Pr j E Bad.] 1 72 1/2 EA, Goodd cost(A, COPT)
1
272 7/2 cost COPT)
2'
Consider fixed bad cluster A E Bad; Let m w(A) = ExEA w(x), where w(x) is the weight
of and define = cost( CoPo)))
1/2
Denote μ the center in COPT corresponding to A. Let
be the point closest to in S.-1. We will show that y (and thus every sampled point S,-1) :) is far from μ.
Lemma C.S. dist(y, 11) 2 3r.
21

---

Published as a conference paper at ICLR 2026
Proof. Because A is fixed bad cluster,
Ys cost(A, COPT) I (A, St-1) Σ w(x) min dist(r, 2 Σ (z))dis((z,))) oESt-1
By Lemma C.3,
Σ w(z))dss(z,,)² - Σ (2 w(x) dist(a,,1) (1 22)² w(x) dist(y.,)?))
2 cost(A, COPT) + (1+ 22)* dist(y, p))
Hence
(1 22) x m dist(y, 1²²² 2 (7x= 2) cost COPT). Since 7/= = -3 22)* 2,
7/2 2
cost (A, CoSt) 1/2 S dist(y, p.)
(1)2 m
Define B(a) = {ar A dist(r, μi) S ar) as the points in the fixed bad cluster that are within distance or from μs We will show that the bad cluster A can be transformed into a good cluster if we sample some point r close to the center μ.. This statement is analogous to Lemma 2 in Aggarwal et al. (2009).
Lemma C.6. Let A be any fixed bad cluster defined by CoPr and let b E B(a), for 0 s a s 3. Then
( (b}) S Y2 cost(A, A, Corr).
Proof.
Σ w(x)
min dist(æ, c)² < Σ w(x) dist(æ;,)² cES
FEA
zEA
By Lemma C.3,
Σ (() dist(r, b)2² < Σ (2 w(x) dist(ar f + (1 + 22) w(x) dist(b,
ZEA
AEA
Since b E B(a) and 0 1 a $ 3, dist(b. (b, p.) S ar S 3r. Hence
cost S: U {b}) < cost (A, COPT) m(1 + (3r)*
= 2 cost (A, COPT) + 3 22)* cost(A, (A, COPT)
7/s cost(A, (A, COPT).
We next show that most of the weights of the points of the fixed bad cluster fall into B(a). Recall that we define m = w(A) = Exre A w(x). Let wo( B(a)) = ExeB(a) w(r). This statement is analogous to Lemma 3 in Aggarwal et al. (2009). Lemma C.7.
w(B(a)) 2 m ( 11- 1.) 1 3.
S
Proof.
cost(A, COPT) cost(A)B(a), COPT)
Σ
w(x) min dist(r, c)* cECort
rEA(B(a)
Since for any x E A, ft is the nearest center to x in COPT, then
Σ
w(x)) min dist(ar,c)²
Σ
cECOeT
B(a)
B(a)
22

---

Published as a conference paper at ICLR 2026
Since for any A\B(a), dist(z, p)) ar, then
w(z)dist(z,,1)) 3 w(A\B(a)) (ar)² =(1 w/ vo(((a)) m((rr).
Σ
B(A)
cost(A, Coer) 1/2
Since r
(1- wo (B(())) m((r)² (1 w w(B(a)) a² cost (A, COPT).
cost (A, COPT) 2
Therefore,
w w(((a)) 2
(1-0))
1- 1
We next show that the cost points in B(x) at least a constant fraction the cost the bad cluster A and thus we will sample point near y with constant probability if we sample point from A. This statement analogous to Lemma Aggarwal al. (2009).
Lemma C.8.
((1, 722
(3 a)²
Pr j E B(a))= A and A E Bad,] 2
a²
Y/2
Proof. Recall that is the point closest to f in S We have
= Σ w(x) min dist(ar c) 1
Σ
w(r)dist(r,)) y)a.
ZEA oES.1
wEA
Let = ddsstyy. u). By Lemma C.3,
cost(A,);..)) <
Σ xEA
10)) = 2 cost(A, (mL42))
Since (oCer) 1/=
then cost(A, 2mr + m(1 22
On the other hand, cost (B(a), S = Evc B()) ity, dist(z, c) 2 dist(e, 1) dist(x, p) 2 dist(y, (4) dist(x, u). Since x E A and A is bad cluster, then dist(y, ()) dist(z, ()) 2 0, so that
B(o) wxx) min.es, dist(a, c)², By triangle inequal-
cost (B))
Σ w(xx (diss(i(()) dist(r, m))
Σ
w())(dist(u: 11) dist((:,,)))
zEB(a)
#e B(a)
For E B(a), we have dist(r, μ)) & ar, so that cost S ExEB(a) ((x)((ist(y. 14)
a By Lemma C.7, w(B(a)) 2 m de), so cost (B(a), m 1 o² (dist(y.
ar)².
Since d, I cost(2;, S) n d, cf. Algorithm 3, therefore
EnjEB(a)
cost (B(a), S 7 7 cost(A, S;-1)
Pr E B(a){r e A and A Bad,]
Ez,AA di
m 1
1
(dist(y. (1) ar)=
72
az
m2 + +11 + 22)222) dist dd)tt(y.))))
By computing the derivative, observe that
(dist p)) ar)²
2r + m(1 + 2=)====isse dist 14)=
23

---

Published as a conference paper at ICLR 2026
is an increasing function of dist(y. pi) for dist(y, pt) 2 3r ar. Hence
m
(3r - (3--ar)
Pr [ E B(a)]r E A and A E Bad,]
2
1
72
a=
ml 2r + +11+ 22)=
(3 o)
1
72
a=
7/2
Therefore, we will transform bad cluster A into good cluster if we sample a point in B(a) C A for S 3, and we will sample such a point in A with constant probability, which means that we will reduce the number bad clusters with constant probability.
Lemma C.9. Suppose the point x picked by our algorithm in the i-th round is from A E Bad; and S = S (z)). Then
Pr [rostt S 72 -cos((,, COPr) |o E A and A E Bad:)] 2 6,
where
(1 1- 1
(3 0)
8 max 72
a=
Proof.
The claim follows from Lemma C.6 and Lemma C.8.
cost(X, S.) > 27² Y cost(X, CoPr), we will sample point from a bad cluster with constant probability, and point sampled from bad cluster will transform it to good one with probability. Hence, we will reduce the number of bad clusters with probability.
We have proven that we will sample point from bad cluster with constant probability. We also proved that a sampled center from a bad cluster will transfer that bad cluster to good one with constant probability. These two facts lead to the conclusion that will transfer bad cluster to a good one with constant probability for every sampling, which is what Lemma C.2 claimed.
Lemma C.2. Suppose cost(X, > 2 Ya cost(X, COPT), then
Pr Bad:+1l
[Bad;]]
for some constant 8 >>0 O.
Proof. If cost(X, S,) > 2y² 7 (X, COPT), by Lemma C.4, we will sample a point from some bad cluster with probability at least 1 By Lemma C.9, if x E A is from some bad cluster, cost(A, S,) I 7s cost(A, COPT) with probability at least 8. Hence A will become good cluster in Good with probability at least 2. Therefore, Pr [[ad < Badd &.
Now we justify the correctness of adaptive sampling for general 1.
Theorem B.10. There exists an algorithm, cff., Algorithm that outputs set S. of O (k) points such that with probability 0.99, cSst(S, I ( cost(Corr. X), where Cort is an optimal (k, clusstrrn of X.
Proof. By Lemma C.3, the number of bad clusters will decrease with constant probability every round, unless cost(X, X 5.) < 272.7 cost(X, COPT). Thus, by Markov's 's inequality, with probabil-
ity 0.99, the number of bad clusters will be reduced to after (k) rounds unless cost(X, S.) <
2²² Ys cost(X, Copr). Consequently, either there are bad clusters Y cost(X, (X, CoPr). Both of these cases mean that we have cost(A,, S) < 2y² Y2 cost( (Aj. COPT) for all j [k). so S becomes constant approximation to the optimal (k: cllustrrin
cost(X, St) < 2n
24

---

return S, Published as a conference paper at ICLR 2026
Algorithm 7 INITIALIZATION
Input: Dataset X; given to each site E [s]
Output: set with one sampled point æ; approximate cost D; for every site on blackboard
1: The coordinator samples point and upload it on blackboard, S +- {x}
2: for f- s do
3: f- POWERAPPROX S))
4: Write ry on the blackboard
5: end for
6: D; + 2
7:
D BLACKBOARD MODEL OF COMMUNICATION
D.1 BICRITERIA APPROXIMATION IN THE BLACKBOARD MODEL
We first give the initialization algorithm for (k, cllusttrrn of blackboard model in Algorithm 7, which generates a point a and uploads an 2-approximation D, of the total cost D, of every site on the blackboard.
After INITIALIZATION, we use LAZYSAMPLING to sample O (k) points to get an (0)1, bicriteria approximation for the (k, c-cuutrtri
Algorithm Lazy Adaptive (A: Sammpling for = O (logn)
Input: The dataset X; every site owns, i E [s]
Output: A set that an (O (1), O (1)) -bicritrria approximation for the (k, cclluttring
I: Run INITIALIZATION to get S and D;
2: N +- O (I:)
3: for + 1 to N do
4:
# f- LLZYSAMMPLIN(((OSSS 5)}, (D,)), and upload x on blackboard
5:
S-SU
6:
Every site j computes Dy = cost (X (X;
7:
Tj 5 POWERAPPROX
every site update ry the blackboard if + logz Dj
8:
9:
end for
10: return
We first show that Algorithm 8 returns (O (1), O (1))-bicriteria approximation for the (k clustering with O (sk log logn n + kd logn) bits of communication and (k) rounds of communi- cation.
Lemma D.I. Algorithm 8 oulputs set S with size O (k) using Ô (sk + kd log n) bits of communi- cation and (k) rounds of communication, such that with probability at least 0.98, cost(S, (S,X) s O (1) cost(Copr,,), where COPT is the optimal 2), clusttrring of X.
Proof. We show the correctness of the algorithm, i.e., that the clustering cost induced by S is constant-factor approximation of the optimal (k, 2)cclssteiing cost. We also upper bound the number of points in S.
Bicriteria approximation guarantee. Since we update D, every round, we meet the condition LAZYSAMPLING (coost(a S)}, (Dz}) in the algorithm. Thus, by Lemma 111,, we sample a point æ with probability cost(ar.)) if LLAZYSAMPLING does not return cost(X,9)
D, S Dj < 2D, every time
I. and rounds of lazy sampling. Therefore, we will get O (k) sampled points that satisfy the required con- ditions for adaptive sampling in ADAPTIVESAMPLING (Algorithm 3). Therefore, by Lemma C.2,
get O (k) points which not 1 with probability least 0.99 after N O (k)
25

---

Published as a conference paper at ICLR 2026
reduce the size of Bad; with some constant probability p every round. It follows from Theo- rem B.10 that Algorithm 8 produces a constant approximation for (k, ellssstrii with probability at least 0.99.
Communication complexity of Algorithm 8. INITIALIZATION uses O (s log log + doo n) bits communication. Uploading the location of a sampled point x requires O (dlog n) bits be- cause there are d coordinates that need to be uploaded, and each needs O (log n) bits. Every site needs O (1) bits to return I to the coordinator. Then, all sites need to write r; on the blackboard. Since ri O (log n), and encoding r; requires O (log log n) bits, it leads to O (s log log n) bits of communication. Since we will repeat the iteration for O (k) times, the total communication cost would be O (sk log log n + lol n) bits. Finally, we remark that since we will use two rounds of communication for each iteration of the N O (k) rounds of sampling, the total number of rounds of communication is O (R:).
D.2 L1 SAMPLING SUBROUTINE
In this section, we introduce an In sampling algorithm in Algorithm 9. The main purpose of the L, sampling algorithm is to ultimately improve the communication complexity and the round complex- ity of the adaptive sampling approach for k S2(lo n), c.f., Appendix D.3.
The sampling algorithm I.IIAMPIIIG can detect whether 5) is good approximation of D. When 2² D < D, which means that D is far from good approximation, LISAMPLING will return True to notify us to update the value D. On the other hand, when μD >> D. which means is a good enough approximation of D. LISAMPLING will return False, so save communication cost by avoiding unnecessary updates.
Algorithm -Smplinl L LISAMPLING (D)).
Input: D; = cost(X;, the cost of points in site i; total cost D = Ei= Dj: (D.) and D written blackboard, which are approximations to (Di) and D; / the distortion parameter; 5 > 0, the failure probability
Output: A boolean indicator for whether D is apprrooxxiatioon of D
1: + +0 (log] ,T + 0, A 4,a + 2/1
2: for i + to N do
Di D
3: Sample site j with probability Pr [i]
update ry POWERAPPROX(D); A) on
blackboard
4: T Pr[ X
5: end for
6: a N δ then
7: return True
8: else
9: return False
10:
end if
We justify the correctness of Algorithm 9, i.e. show that if the total mass has decreased significantly, then the algorithm will return True with probability - and similarly if the total mass has not decreased significantly, then the algorithm will return False with probability 1 1-6 5.
Lemma D.2. Suppose D, Z D, for all j E [s], and ò 2 D. If 1 < D. Algorithm LISAMPLING ((D,), {D,} n. 8) will return True with probability at least - 8. If > D, L LISAMPLING((D) ((D,) (D,), (,, 8) will return False with probability least 1 8.
Proof. Let D. = > Since is returned by POWER ",,)),,,, A), then by Theorem B. B.12, we have D, A D. AD,-
26

---

Published as a conference paper at ICLR 2026
Define the random variable
1 Dj. with probability P5
Dj D
Z, Pj
We will evaluate the range of Z, and E|Z,] so that we can apply Hoeffding's inequality later. We
have Dj 2 Dj and Dj < ADj. Hence,
Z = - Dj LD D DAD AD, AD. Pj
Dj D
On the other hand, 2, must be non-negative by definition, so Z, E [0, AD]. For the range of B[Z,], we have
E 755
Σ
1
Dj
Pj
Σ Dj.
j=1 Pj
j=1
Since D, [Dj,ADj] AD2], then we have [E[,] E [D, Similarly by linearity of expectation, since
T E Zi then we have E[T] = N B[Z,] E NAD,. We perform casework on whether 2 S D p2D D. corresponding to each of the cases in the stated guarantee.
Case 1: 12D < D. We first analyze the case 1²2 S D. We define the event A that LISAMPLING( ({D)), (Dj),14 H4, 8) returns False when 1 D S D as the false negative event. OB- serve that this occurs in the algorithm if and only if aT ND when μ² < D.
Notice that aT > ND is impossible if T E AND imply
AND since p.² D s ò and T B[T]] s
2ad 112
1 ND ND
aT S (E + T - E[T]) S a(AND + AND) < ND =
The first inequality is due to the triangle inequality. The second inequality comes from the fact that E[T] E [ND, NXD] and |T B|T]| S XND. The third inequality is due to the condition
4 D <
D. The equality is because of 2p and X = 2. The last inequality is due to μ 1.
Hence under the condition that D < D, the false negative A can only occur if T E[T]] D. Therefore,
Pr [M] Pr [TT NDIn² 2 D S D Then by Hoeffding's inequality, e.f., Theorem B.6,
Pr T E[T]
AND D
(AND)²
Pr T [[[] AND 2 D < 2xxp
N (AD)) 2xxp (-N) 8,
because we have N₂ E [D] and N = O (log }). Since we have shown the probability of the event N of getting a false negative no more than 8, then LISAMPLING (D)), will return True when 1² D <. D with probability at least 1 - 6.
We next analyze the case pD D.
Case 2: JD > D. define the event P that LISAMPLING ((D,), (Dy}, ). μ, 6) returns True when pD D, i.e. a false positive event. Observe that this can happen if and only if aT < ND when uD > D.
Notice that of < ND is impossible [T E[T] < LND. In fact, if JD > D and T - E(T s NDD, then
oT 2 (F IT E[TI) 2 a(ND ] ND) a ND a ND = ND.
24
27

---

Published as a conference paper at ICLR 2026
The first inequality is due to the triangle inequality. The second inequality comes from the fact that E[T] E [NT,, NAP] and IT E|[T]| (,D. The third inequality is due the condition μD D.
The second equality is because of a = 2j..
Hence under the condition that μD > D, false positive P can only occur if [T - E IND. Therefore,
Pr P Pr aT S ND > D
< Pr
T B[T] >
ND HD > D
Then by Hoeffding's inequality, c.f., Theorem B.6,
1 マ NDIuD > D S exxp
(NN (AD)2
NV
Pr [[-]ET]--
2 exp
S o,
4X2
because N₂ [0, AD] and N o (log 1)) Since we have shown the probability of the event P is
no more than 6, then it follows that LIS LISAMPLING( (Dj),u, (,,) will return False if pD > D
with probability at least
D.3 BICRITERIA APPROXIMATION WITH COMMUNCCATIO//RUND REDUCTION
In this section, will introduce another protocol that uses O (log n log k) rounds of communica- tion and Ô (s log + kd log n) bits of communication cost. The protocol will use fewer rounds of communication and total communication than Algorithm 8 when & = 2( nt).
We first apply the Li sampling subroutine LISAMPLING estimate D, which uses low communi- cation cost. We then update D if the estimation of from the L, sampling procedure has decreased significantly. Using such a strategy, we only need to update Dj in very few rounds, saving the communication cost of updating Dj-
However, the communication rounds are still O (k)) which would be too expensive in some settings. To further decrease the rounds of communication, number of points to be sampled in every round until the total cost D drops significantly. can only decrease significantly for at most O (log n) rounds, so we can reduce the rounds of communication to O (log n log k).
use the batch sampling strategy. We double the
Another issue that must be addressed is that we may sample some invalid points because the total cost D may decrease significantly during a round of batch sampling. A sampled point is valid only if is sampled under the condition that 7) is a O (1 >-approximation of D, so some sampled points may be invalid if D drops significantly during that sampling round. To ensure that we sample enough valid points, we need to count the number of valid samples during the sampling procedure. Rather than setting a fixed number N = O (k) of points to sample, we count the number of valid samples and only terminate sampling after we get least N valid samples. Fortunately, although we may sample more than N points in such a strategy, we can prove that the total number of points we sample is still O (k)).
The algorithm appears in full in Algorithm 10.
Algorithm 10 uses LISAMPLING detect whether 1) decreases significantly and needs to be up- dated. Under the condition that D is a O -pprroooxiitio of D, it uses batch sampling to sample points, and verify whether D is still a O (I)-approximation of D after batch sampling. If D is still a O (1) aapproxxmmaioon of D. it means that all the sampled points are valid, and we count them. If D no longer O (1) approxxxiittoo of D, means the O (1) (a)-aporoinnntion condition breaks dur- ing the batch sampling, which leads some sampled points invalid. However, the first sampled point must be valid, since we sample it under the condition that D is an O (I)=approximation. Hence, we can add 1 to our valid sampled points count. We repeat the sampling until we have counted at least N O (k) valid sampled points. Then the returned set S will have O (k) points and is an O (1) approximmatnn. Furthermore, by using LISAMPLING and batch sampling, we can guarantee low round complexity and total communication for Algorithm 10.
28

---

Published as a conference paper at ICLR 2026
Algorithm 10 Bicriteria approximation algorithm for cclusttringg
Input: Dataset X; for each site i E [8]
Output: A set S that is an (O (1), O (1)))-bicriteri) approximation for the (k, =clustrnng
Uniformly sample point into S and compute constant-factor approximations {D,} to Dj
cost(X;;
2: + O (ke, M + 0, 8, -
0
log"
3: while M < N \\ Sample roughly ls points do
4: bool +- False,
5: while bool False \\ Approximate distances {D₂} are accurate do
6: for 1 to 2 \\ Attempt to sample points into S do
7:
21 f- LAZYSAMPLING end for
S)}, (D2)). upload xj on blackboard
8:
9:
5 S-SSUIE ( + # * 1 2
DAdd successful samples to S
M + M +L
11:
Every site j computes = cost ()
DUpddate distances to closest center
bool LISAMPLING (D,), (D 6)
>Check approximate distances {D}
13:
if bool= = False then itz i i+1
More aggressive number of samples to reduce number of rounds
15:
else
r - POWERAPPROX (D. every site j update r, on the blackboard r, * loga Dj
Dj + 2 end if
AAll sites update approximate distances
18:
19:
end while
20:
end while
21: return
We split the proof into three parts. First we will prove that S is an O (1)-approximaaton and |S| = O (k:) Secondly, we will prove that the algorithm uses O (log n log k) rounds of communication. Lastly, we will prove that the algorithm uses Ô (s log n + kd log n) bits of communication with probability least 0.99.
For the purposes of analysis, we define the concept of valid sample. Suppose x is a point sampled by LAZYSAMPLING (cosst S)}, (Di)). Then we define x to be valid sample if it is sampled under the condition D < D r D₃ for some constant 7. Lemma D.3. Algorithm 10 will return S such that |S| O (k) and cost(S, X) S 0 cost(Corr: X) with probability at least 0.98, where Cort the optimal (k:, cl-custtering of X.
Proof. Suppose r point sampled by LAZY (cost(ar (D.)). x is a valid sample, it will reduce the size of Bad, with constant probability by Lemma C.2. If we sample N O (k) valid points by our algorithm, by Theorem B. 10 we will get constant approximation S with probability at least 0.99. We will show that our algorithm indeed samples at least N valid samples for y = !
According to the algorithm, Dj is always a 2-approximation of Dj that D, S D, < 2D, after we update D,. Between two updates of Dj, D, is fixed, but D, may only decrease. This means that D, S D, always holds in Algorithm 10. Since Dj < Dj always holds, < always holds, too.
If D < D after we sample L points, it means that all these L points are valid. We will either add T. to the counter M if SAMPLING returns False, or add to the counter M if SAMPLING returns True. In either case, the number of valid points sample is at least the number add to the counter M.
If D > n² after we sample L points, it means that some points sample are invalid. How- ever, the first point sampled must be valid, it is sampled under the condition D 2DD. If
29

---

Published as a conference paper at ICLR 2026
LISAMPLING returns True, we will only add 1 to the counter M. Then the number of new valid samples in this round is at least the number we add to the counter M.
Therefore, the number of valid points we sample is at least the number we add to the counter M if AMPLING returns True every time D 2 p²D. Since D poly(n) when have only one point in S, and every time we update in Algorithm 10, holds that < D < 2D, D 2 μ²D can only occur at most O (logn) times. We know L1S AMPLING will return True if D 2 μ D with probability at least 1 1- Since 6 = Tog then by a union bound, LISAMPLING returns True
every time D 2 n² D with probability at least 0.99.
Therefore, with probability at least 0.98, we will sample at least O (kk valid points and they form an O (l)-appooxitttion for the optimal solution.
Upper hound on the size of S. We will evaluate the number of sampled points that are not counted as valid samples, and show the total number of such points O (A:). Suppose that we update D3 for m times for total.
Let Np be the total number of sampled points that are not counted as valid samples, and pt as the number of points that are not counted as valid samples between the (i 1)-th and i-th update. Then NVp = Ei= Pt. Let N, be the total number of sampled points that are counted as valid samples, and qi as the number of points that are counted as valid samples between the (i - 1)- th and i-th update. Then Ng = Σm 9-- Since we will terminate the algorithm we count for N O (k) valid samples, Ng 0 (k).. Since the number of points sampled before the i-th update is Pt + and the number of point sampled before these p. + points Put1, therefore, pj S. 2g. Hence N, < 2N, = O (k). The points in S are either counted as valid samples or not, so |S| N, + Ng = O
We next upper bound the round complexity of our algorithm. Lemma D.4. Algorithm 10 uses O (log log k) rounds of communication with probability at least 0.99.
Proof. We need O (1) communication rounds in the initial stage Algorithm 7. For the communica- tion rounds in the remaining part of Algorithm 10, we evaluate how many rounds of batch sampling occurs between two update, and evaluate the times of update. Then the product is just the rounds of total sampling.
For the rounds of batch sampling that occurs between two update, it must be at most O (log k) rounds since we double the number of points to be sampled for every other round if we do not update 7) and the total points be sampled O (k)). For the times we update D, there are two cases: we update an 'unnecessary update' under the condition that D < μD, and we update a 'necessary update' under the condition that D Z pD. By Lemma D.2, LI LAMPLNGG will return True and we will have an 'unnecessary update' under the condition that D < μD with probability at most 8. Since there are at most O (log k) successive batch sampling without an update, we will make an 'unnecessary update' between two 'necessary update' with probability at most O (6 log k). For the 'necessary update",
will update D so that D < D 2D. Since μ 8, means every time we make a 'necessary update" under the condition that π 2 μD, D decreases by least a factor of 4. Hence, such update can occur at most O (log n) times.
Since the probability that we will make an 'unnecessary update' between two 'necessary updates' is at most O (5 log k), and the times of 'necessary update" is at most O (log n), we will make an 'un- necessary update' in Algorithm 10 with probability at most O (ō log log k). Since 6 = Tog we will have no 'unnecessary update' in Algorithm with probability at least 0.99. Since 'neces- sary update" will occur at most O (log n) times, it means we will have at most O (log n)) updates of 7 with probability least 0.99.
30

---

Published as a conference paper at ICLR 2026
Therefore, with probability least 0.99, Algorithm 10 has O (log n log k) rounds of batch sam- pling. Then we need to evaluate how many communication rounds we need for a round of batch sampling. For each round of batch sampling, the coordinator pling at the same time, and every site can respond afterwards. Hence there will be two rounds of communication for each iteration of sampling. To get the result returned by L. L1SAMPLING, the O (log }) = O (log log n) requests can be made simultancously, so that there are O (1) rounds of communication. Hence, the total rounds of communication Algorithm 10 is O (log n log k).
send the request of 2' lazy sam-
Finally, we upload rj when we update Dj- All the sites can update the values of rj in the same round. Since we will update at most O (log n) times, we needs (log n) rounds of communication for total. Summing the rounds of communication across each part of our algorithm, it follows that the total rounds of communication O (log n log k) with probability at least 0.99.
Finally, we analyze the total communication of our algorithm.
Lemma D.5. Algorithm 10 uses Ô (s log n + kd n) bits of communication with probability at least 0.99.
Proof. The Algorithm 7 subroutine INITIALIZATION induces O (d log n + s log lo bits of com- munication because we only write the sample point and r; on the blackboard, and ri O (log log cost(X; S)) = O (log log n).
We will update O (k) samples, which will use O Iod total bits of communication.
Moreover, we will run LISAMPLING at most O (log n log k) times. For each time it runs, the coordinator will choose O (log 3) O (log log sites. It uses O (logs) bits to represent a site on the blackboard, so that site knows it chosen. Each chosen site needs O (log log n) bits to reply. Hence the total communication cost for running LISAMPLING in Algorithm 10 is O (log n log k(log s + log lo) bits.
Updating the values {r, } costs O (s log log n) bits for each iteration. Since the value will be up- dated O (log n)) times with probability at least 0.99, the total cost for updating the values (ry} is O (s log log log n)) bits.
Therefore, by adding the communication cost for all parts of Algorithm 10 and ignore all the poly- logarithm terms for s, k, log n, the total communication is just (s log n + loglog)) n).
We have the following full guarantees for Algorithm 10.
Lemma D.6. Algorithm 10 will return S such that |S| O (k) and cost(S, X) S (1) cost cosr X) with probability at least 0.98, where Corr is the optimal (k, cl-uusttri of X. The algorithm uses (s log + kd log n) bits of communication and O (log n log k) rounds of commu- nication with probability least 0.99.
Proof. The proof follows immediately from Lemma D.3, Lemma D.4, and Lemma D.5.
D.4 CORESSTT VIA SENSITIVITY SAMPLING IN THE BLACKBOARD MODEL
To achieve a (1 (1+ -cooreset for X with the (1), O (1)) -bicritria approximation S, we use sen- sitivity sampling. The challenge lies in determining C and cOst(C;, S) to calculate μ(xx), com- municating the exact values of C3 and cost(C,, S) requires O (sk log log bits, which is impractical for our purposes. However, a constant approximation of C, and cost (C,, S) suffices to approximate u(z) for the sensitivity sampling, and this can be achieved efficiently with minimal communication through Morris counters.
Theorem D.7. (Morris, 1978) Let X MORRIS (0, n). Then E [2x - -1] n. Moreover, there exists a constant y > 0 such that ifl 2 3/ log 1 and Y = El= (2x: - 1), where X1, X2....... ,., X are 1 independent outputs of MORRIS(O, n), then
Y [n - en, n + en],
with probability at least 1 8.
31

---

Published as a conference paper at ICLR 2026
Algorithm 11 (ORRIS(T, m)
Input: Initial count index r, and elements number
Output: New count index m
m 5-
2: for + 1 to do
3: With probability 2m m <- m
4: end for
5: return
We can adapt MORRIS to distributed version DISTMORRIS to reduce the communication cost.
Algorithm 12 DISTMORRIS(E):
Input: Precision parameter e, every site S; owns numbers ni.j. E [k]
Output: Approximation (N1, ,Ne)) for sums Nj = Ei=1 Rig. j E [A]]
1: 1 + O 2a 10g(100k))
2: my.t + for all j E [k) and E [
do 4: m' - MORRIS(M,,,,
3: for +-
for all j E [k] and & E [4]
5: if m/, = mj. for all j E [k] and t [2] then
6: Site uploads 1 on blackboard
7:
else
8:
Site i uploads (m'gee - -mja, 1) for all j E [k] and E [1] that m/j, # mj,
9: end if
10: m,.tt f m/j
11: end for
12: Nj + 1 Ei=1 (2ms.e - -1) for all j E [R]
return (N1, N2,... N&)
Lemma D.8. Let every site i own l numbers n4.j. and [N,| Ei= mig poly(n)) With prob- ability at least 0.99, DISTMORRIS( returns constant upproximations N, that N₂ E NN, for all j E [k] using Ô (s + k n) n) bits of communication.
Proof. Although we split the process of MORRIS into a distributed version. its accuracy does not matter. This because every step of MORRIS only needs know the status of the previous step, and every time a site uses a step of MORRIS, it knows the status of the previous step either because both of these steps occur at this site, or because the status of previous step is accurately uploaded by the previous site. Hence, the statement of the original MORRIS in Theorem D.7 still holds for our distributed version.
By Theorem D.7, N, E N N22 with probability at least 1 100k for any E [k] if we set I = O (log(100k)) Then, by union bound, N, E N, Ny, for all j E [k] at the same time with probability least 0.99.
To evaluate the total communication cost, we introduce M, and Mr,j as follows to facilitate the analysis. We set M, 0 if site uploads 1 on the blackboard and M, as the cost of communication to update all (m',, m, t) for all j E [k] and f E [1] that m , * mj.t otherwise. We set Maj, to be the communication cost required to update (m',e mj,,j,.).
Every site with M, = only needs O (1) bits to upload 1. Since there are & sites in total, the number of sites with M, 0 is at most Therefore, the total communication for these sites is O (s).
For the sites with M, + 0, the communication cost used
M= M,
ΣΣΣ Mejat-
M.
32

---

Published as a conference paper at ICLR 2026
Note that the first equality holds because we only add more terms that all have value zero, whereas the second equality is obtained by dividing M, into My.j.e-
Since N; + (2m 1) E 1,, I, then 2 cannot be greater than 21 N O (logk: poly (n)). Therefore m,, S O (log log log k). Since Maja must at least if nonzero, there at most m2, nonzero Maj.t for given j.t. For every non-zero Mija since the site uploads m/ mia which is at most the final mga: then the site will use no more than O (log m,,1) bits to update mj,, mj and (log k + log() bits to express and Thus,
Mi3a
Σ
Mija mÿ O (logm,,+ m2,t a log k + log().
MEls),,Ma,j..f M.
Since mj,t S O (log log log k) and = O (log k), then Ei=1 Ma S O (logn). Therefore,
Masa S Ô (logn) = Ô (k: log n). M
M,*0
j=
By summing the communication cost of the sites that upload and the communication of the other sites, the total communication will be
than Ô (s llg
Since CC C-==E: Ei [C,nx; and cost(C S) -;= cost cost(C,nx, S) for any j E [k], we can use DISTMORRIS approximately evaluate these terms using low communication cost. Since both [C3] and cost(C). (C,, S) are at most poly(n), the total communication at most Ô (s + k log n) bits. Every site can compute cost(x, S) for X, locally. Then with the constant- factor approximations for IC,l and (Cs S), each site can evaluate constant-factor approximation of the sensitivity p(x) locally.
ge (log t + log 1 log log n)) bits of communication, given our O (1) (L)-approximation with O (k) points and sensitivity μ(r).
Finally, we give an algorithm producing (1+t)-coreset for X with
:
Algorithm 13 (1 + cc-oreettt for the blackboard model
Input: A constant approximation S, [S] = (k)
Output: A (1 + e)-coreset A
1: Use DISTMORRIS to get O ( -ppproxxxitnon for [Cyl and (Ost(C,,S)) for all j e [k] on the blackboard
2: m < Ô ( min(e-2, c-==))
3: for i +-+-1 to do
4:
0
5: Compute (((x) as an O (1 (1)-approximation of p(x) locally for all X;
6: Upload (x()) Σxex, (((x)
7: end for
8: Samples site with probability 7(X))
independently for m times. Let m, be the time site i
Lis p(X,)
are sampled. Write m, blackboard
9: for + 1-16 to do
A; 1-+0
11: for j [m.]] do
Sample with probability Ps
((x)
(XX.]
a is sampled then
14:
Let x' be x efficiently encoded by S and accuracy e' = poly(e)
15:
A + A, m
where (a(x) a (1 + appproxiiiiiion of ((x))
16:
end if
end for
18: Upload A, to the blackboard
end for
20:
A &- - 4
return
We now justify the correctness and complexity of the communication of Algorithm 13.
33

---

Published as a conference paper at ICLR 2026
Lemma D.9. Algorithm 13 returns A such that A is a (1 + e)-coreset for X with probability at least 0.98 if we already have an (1) O bbr)-bici approximation The algorithm uses Ô k log n + mints" mints", (x+))) bits of communication.
Proof. By Lemma D.8, we can get an O (1appppooxiittooon for |Cyl and jo, S) with prob- ability at least 0.99. Every site can also get the precise value of cost(ar, S) locally. Since cost(a.8)
|OJT + [c.5) u(z) = (1)-xxopoxnnaation (((x) of μ(z). Although Bansal et al. (2024) proves Theorem B.7 evaluate an O (1)aaapppooxxxiii
cost(z.S) + cust(X.S] +
cost( and Ap == cost(C,, S)/[Cyl, we can
A.
in the setting that |S| and sample points with probability pzz), they only need |S| O (k) and cost(z,S) co,t(z
M(a] S O (1) max K Ecost(C]..5) cost (XS) cost((X.)] } in their proof. Therefore, Theorem B.7 still valid under the condition that |S| (k) and ī(xx) (1) =(x).
Let B {(x, m)(()))))))) ))}, then B is an (1 + 2 )-corestt for X with probability at least 0.99 if we have O - approximaaio for |Cy] and cost(C),
We have A { mū(z) )}. Since B is (1 + )ccorestt for X, by Lemma B.13, A is (1 + E)- coreset for X. Therefore, Algorithm 13 returns an (1 + s)-ceretet for X with probability at least 0.98.
We need O (s + klogn) bits to get the O apprrxxiiitnnnnnn for |Cy] and cos We need O (s logm) = Ō (s) bits to write m, on the blackboard. We need O (log k + d log log n) bits to up- load a', because bits, and need to upload the power index, which needs O (log log logn) bits. We need O (1 log 1) bits upload mij(=) because we only need upload jix)), which is a (1+ 5)-
need to point out which center in is closest H, which needs O (log k)
approximation of ((x)). Since |A| O (iiineefemmn)) we need Ö (s + k log n + min(c bits in total.
db
We complete this subsection by claiming that we can get a (1++) (L+=)-stronn strong coreset with communication cost more than Ô & log(nA) dk log(nA) +
min[e",e"*s)) (==+.)] bits.
dà
Theorem D.10. There exists protocol on points distributed across sites that produces (1+s)- strong coreset for (k, c)cclustgingg with probability at least 0.97 that uses
dk
δ s (log(n) + dk log(n)) +
total bits of communication in the blackboard model.
Proof. We can Algorithm 10 to generate (O (1) O (1))--bicrtten) approximation S, and then use Algorithm 13 to get an (1 + e)-strong coreset. By Lemma D.6 and Lemma D.9, the returned set A is (1 e)-strong coreset with probability least 0.97 and uses communication cost of δ log(n) + dk log(n) ma
dk
bits for total.
E COORDINATOR MODEL OF COMMUNICATION
In this section, we discuss our distributed algorithms for the coordinator model of communication. Note that if all servers implement the distributed algorithms from the blackboard setting, the re- sulting communication would have (dsk log terms simply from the O (k) rounds of adaptive sampling across the servers.
E. EFFICIENT SAMPLING IN THE COORDINATOR MODEL
To avoid these O (dsk l) terms in communication cost, we need a more communication ef- ficient method so that we apply adaptive sampling and upload coreset with low communica- which can send the lo-
tion cost. We propose an algorithm called EFRCIENTCOMMUNCCTUN cation of point with high accuracy and low cost. Suppose that fixed site has set of points
34

---

Published as a conference paper at ICLR 2026
X {=1,". )1 and another site has point y. To simulate adaptive sampling while avoiding sending each point explicitly to all sites, our goal is to send a highly accurate approximate location of y the first site with low cost. To that end, EPRCIENTCOMMUNCATTON sends the coordinate of a point in every dimension. For the i-th dimension, we use a subroutine HiGHPRoBGREATERRTHEE
approximates and
which detect whether y is greater than zj with high probabil-
(6) ity, where g is the coordinate of the i-th dimension of y and æ is the coordinate of the i-th dimension of 2 E X.
Algorithm 14 HIGH SIGGHPOOGGEAATERTINNAASA
Input: Integer I. y. failure parameter 8
Output: A boolean bool that shows whether x is greater than
I: N O (log
0
2: for +- to N do
3: r3 f- if GREATERTHAN(:, y) tells us æ S y, and r, < otherwise
4:
r+-++, ri
5: end for
6: if N S then
7: return False
8: else
9: return True
10:
end if
The subroutine HiGHPPOBGTEEATTRRTHHA an adaptation of GREATERTHAN by (Nisan, 1993). The main purpose of the subroutine is that by using binary search, we can find the relative location
of ( {a]
.a(() within log comparisons. Then, comparing ( with ( (1 + =)m,
can find the best 2 (6) and to approximate y Our algorithm for the coordinator model appears in full in Algorithm 15.
Algorithm 15 BFFICIENT
y, 8)
Input: A set X {-1.-.. 2i) owned by one site; a point y owned by another site; e, accuracy
parameter; ò, the failure probability
Output: The second site sends ÿ to the first site, which will be an approximate location y that y Vl S =||æ yll2 for any X, with probability least 1 1
1: for + to do
( 2: Sort X { Nit such that on
(6) mi is the i-th coordinate of my si where
(
3:
- A + 8,8 - d1og (0og logg lox +l !)
4: Use binary search and HICH/PROSGGEATERTHHNNGG
(4) 58) to find xy that |o
y0 < |rl y for any i, E 1,, ,1,
5: Use HiGHPROBGREATEERTINN test whether ()) x
(1)
6: if (+)) x then
(
7:
Ay(0 0
8: else
9:
7 + ssignyy (0)
Use binary search and HIGHPROOGREATERTUUNNG 20.0) + (1 (1+5)* (1+5)5,8) to find m
10:
(6) + 7 (1+ I +7 (1 + 8) - y for any t E N
that |
11:
Ay + 7 s)
end if
13:
((t) + Ti
(4) + (1(
end forreturn ÿ (7))) ((1)
We first show correctness of HiGHPRoBGREATERTHAN running multiple times and taking the majority vote if necessary to boost the probability of correctness.
35

---

Published as a conference paper at ICLR 2026
Lemma E.1. If # v,66) 9, returns False, then x S with probability at
least 5. If HHICHPPOOGGEETTRTTHANN (z. y. 5) returns True, then x > y with probability at
least 1 6. Furthermore, the protocol uses O (log log n log }) bits of communication provided that
2. | poly(n), (all:pol(nn) (n)]
Proof. We define random variable E, T4- By Theorem B.8, GREATERTHAN will give wrong
answer with probability at most p < 2. S0
E| S v) = 0- Pr E, = 0|r S v) +1 Pr..PPBD [ = 1/2 S y) Sp
E > yو = 0 Pr E. = 0|r y) +1 +1. [L 1| > y) 2 1-pp. p.
Since E, E [0, 11. by Hoeffding's inequality, c.f., Theorem B.6,
N Σ
N x aΣッ
+ N
Pr
E
> 2
= Pr
Σ E, >
p
Np x S
2
N
N - Np x S
< Pr
Σ
E, NE[E,]
>
2
1=1
N ND) 2
< <2exp(
2
N. 12
8
and
N
N E < 2
N
+ N
Pr
r > y
= Pr
Ej S N(1 -
N(1 - p) x >
2
]
N Np xpx>8 >y y
< Pr
Σ i=1
E, N E[E,]
NN Np) 2 N 12
S 2 2exp(
6.
Hence HICHPPOOGGREAATERTHHANNZZ y. 5) is correct with probability at least 1 - 8.
For the communication cost, since GREATERTHAN uses O (log log n) bits of communication, pro- vided that x. y E |- poly(n), (nly( and we run GREATERTHAN for N O (log !) times, then the total communication cost O (log log log }) bits in total.
EFFICIENT COMMUNICATION y,,,, in Algorithm 15 will send y. a good approximation loca- tion of y with probability at least 1 -- 5. In addition, it only uses d log | polylog( (log log l, 2 8
bits. To formally prove these guarantees, we first show [yy - 7/12 2 S a||x - =il22 with probability and then upper bound the total communication of the protocol.
Lemma E.2. EFFICIENTCOMMUNNCATOONN X, y, e, 6) will send ÿ to the first site such that 1|y - oll S E æ yll2 with probability at least 8.
Proof. We condition on the correctness of HIGHPROOGREETERRIUNG We will prove that 1/
úll2 & =|| yl22- First, we will prove (8) /. S e|1059 - y(0ر for any j E [d] and x. E X.
Let x = (-A, 1 22 ..... .o7 A). Assume _:! E x that |ar6 y0 s (nn)
(() for
any 20(1) E x() If (1)) xxe 77( is just (1), which means (t) glol |m.5 -y(0 =
j(t()
If ( + x. we have y(t = ( + ( and Ay = (1 +1+83 E)m, where 7 = sign(y xi,
Assume ((ر x - (1 + + Then
(0(00 | = (0) -واي) (7(0) x (1)) 1(1 + 8) m+mm +1++)m²
36

---

Published as a conference paper at ICLR 2026
Since l + 7- (1 +.) y S |u?? +7 . (1 +)) -y00 for any N, |mm| must be less than
1. Hence
Iy - / = (1 + 2) m |1 (1 +1) m²
+ 2) mm = =s|=! - y/ S s
Since
lx:!) y00l | ( y for any j. and ly( - J. S E c|=! -/ thus ly - 5/01 s
elaf)) 1. Therefore, for any Iz X,
lly - 512 1 g012
- Σ
10 = ==? -2.11azz - 6² |
1=1
Hence |1 2 S s
v/I for any x X.
Analysis of the failure probability, It remains to upper bound the failure probability by counting how many times HIGHPRORGREATERTHAAN
is run in the algorithm. For every dimension
i, we run HIGHPROBGGEFATTRTTHHHHNC .6) to find the closest i to y(u) and m to approximate
(0)) L..- To find the closest 2. to y(), we can use binary search to find x:()) iip S yy S <x(() "p+1
and
2.9) +o.0 then compare their midpoint "p wil with (+) determine which one closer to (f)), Since there
are + 2 elements in {at, , ... x x R44 }. we need to run HIGHPPROGGRENTTTTTINNN.
for log(2 + 2) + 1 times in this stage.
To find that |=] +y 1. (1+=)m (ma)))-pp y0) S 10, (6) + y for any t N, can binary search to find (1++)9 < -y(0)(()) (. s (1 (1+e)ot1, and then compare their midpoint with (x()) x
to determine which one is closer to (y()) 1. Since we already have Fip S (( S x 1p41 and
(1)
|= < A for all j E 1, + 1), we only need to search q among {0, 1.. ................................ logi+e A}.
Since A = poly(n), we can use binary search to find q in at most O (log log m rounds. Thus we need to run HIGHPPROBGREATETTIANNN Therefore, we will apply HIGHPRRBGGREATERTTIA for at most O (dl (log l + log log n + log !)) will return correct result with failure probability
for O (log log n + log 1) times in this stage.
times. Since
at most and 8' = d(log log no EFFCHENTCOMMMUUNCTIONN, 8, 5) has a
failure probability most 5.
Next, we analyze the communication complexity of our algorithm.
Lemma E.3. EFFICIENTCOMMUNICATTOO of communication for total, where & |X] is the number of points owned by the first site.
y, 6) uses d log E polylog(log) n, log f, t. +) bits
Proof. We need to O (d (log& + log log n + log 2)) times Since HIGHPPOBGGEATEETTHNNG: -,8') cost O (log log nog $) bits for single running, it takes dlog polylog n, log E, g 1) bits to run HiCHPROBGREEATERTHHAN
HICHPPOBGGREATENTHANNN ..8) for at most
for total.
We also need communication to send ÿ (g()) only need to send x/ and (t) to the first site. Since the first site already has the location of all E X, we only need to send to identify ,.()) which takes O (log E) bits. Since (y 7. (1 + s)m we only need send y and m. Sending 7 requires O (1) bits since 7 E (-1,0,1) 1). Sending requires O (log log + log !) bits since (1 + E)"T = (n)y Therefore, it takes at most dlog polyyogg(og n, !) bits send ÿ = ()).... ... .(()).
((d)) to the first site. However, we
Hence Algorithm 15 takes at most d log e polylog(log n, log E, L, () to send ÿ to the first site.
Putting together Lemma E.2 and Lemma E.3, have:
37

---

Published as a conference paper at ICLR 2026
Lemma E.4. EFRCHENTCOMMUNCCTIONNS
will send to the first site such that
My 3122 I E||> - y/22 with probability at least 1 - Furthermore, it only uses d log l polylog(log n, log l, t. (t) bits of communication for total, where l = [X] is the number of points owned by the first sile.
E.2 (1 +
( CORESET VIA SENSITIVITY SAMPLING IN THE COORDINATOR MODEL
Given the analysis in Appendix E.1, follows that we can effectively perform adaptive sampling to achieve a bicriteria approximation at the coordinator. It remains to produce a (1 s)-corsee, for which we again use sensitivity sampling.
EFFRCIENTCOMMUNNCATTOOOO X, 6) can send the location of y using low communication cost.
However, its communication cost is d'log polylog(log n, log E, : }). where = [ For the coordinator model, suppose that each site i [s] has a dataset X,, Since [X O (n), and
the coordinator needs to send the approximate location of all O (k) samples to each site to apply
adaptive sampling, which would still require dsk log polylog(log e 8) bits send the location of samples using BFFICIENTCOMCCNICATAO
X,, U. E, 6). Fortunately, we can generate a (1+ f)-
coreset P. for every X,, which has size of Ô min(ett,2+12) ). Since adaptive sampling also works for the weighted case, enough to generate an (O (1), ; O ( bicriteriia approximation for the weighted coreset P P; Therefore, only dsk polylog(log n, ki 2 4) bits necessary to send the location of the samples to each site.
To further eliminate the multiple dependency of d, notice that only the distance between the data point x E P. and the center generated by adaptive sampling 8 E S necessary to apply adaptive sampling and sensitivity sampling. Hence, we can use the Sonsonn-Lndeenstraus transformation to map to (PP) C Rd where d' located in a lower dimensiina space. but the pairwise distance is still preserved by the mapping. Therefore, we can further reduce the communication cost needed send the location of the samples to each site, which is now sk moolylog(ogg 8, k, 2: 5.8) bits. Hence, we can apply adaptive sampling and send the exact location of the sampled point 8 to the coordinator. The coordinator can then use
(log(sk)). As a result of the transformation, т T(P) is
(s)) E,,) to send the approximate location of T(s) to every site, which accurate enough for every site to update a constant approximation for the cost of points. Thus, we repeat adaptive sampling using low cost of communication and get (O (1), O (1))-bicriteria approximation S for the optimal (k:, cluustrrin
Since every site has an approximate copy of (S), they send a constant approximation of [C n Pj and cost(C) Cy 0 nP S) to the coordinator. However, the site may assign a point to a center in S that nearest it. This is because the site only has an approximate location of x =SS), and therefore can assign æ to another center s' if cost(x, s') is very close to cost(a, s), where s is the center closest æ. Fortunately, the proof of Theorem B.7 does not require that all points be assigned to its closet point. Theorem B.7 is still valid if cost(z, s') < O (1) cost (z, (x.)..)))..)))))))) s). Hence, we can generate (1 -coreset for by sensitivity sampling.
After applying sensitivity sampling to sample the points, each site can send the sampled points to the coordinator using BJFCCIENCCOMMUNICATUUO encoding in Lemma B.13, we can prove that the sampled points form a (1 + )ccoreet A' for P Use(+) P:. Therefore, A' would be a (1 + co-ceetttt for X Usels] X,, and the coordinator
. 8). By a similar discussion of efficient
can solve the (ks ceclustinng based on the coreset A'. Since PP| = Ô (min(e",22=))) we can
run EFFICIETCCOMMUNICTTON P., E, 8) using polylog(log n, k, L. +) bits of communication send each sampled point. We give the algorithm in full in Algorithm 16.
We now show that Algorithm 16 will return a (1 + e)-coreset of X with constant probability and uses low communication cost. We will first show that A' is (1 + e)-ceret of X.
Lemma E.5. Algorithm 16 returns a + E) coreset of X with probability at least 0.96 in the coordinator model.
38

---

Published as a conference paper at ICLR 2026
Algorithm 16 (1 + -ooeestt for the coordinator model
Input: The dataset X; every site owns, [s]
Output: A (1 e)-coreset A' sent to the coordinator
1: Every site generates a (1 + 5) -coreset P. of X;
2: The coordinator send random seed to every site that generate Johnson-Lindenstraun x, such
that [|<(x) T2y)ll2 E 12 vll2. z æ yllاa for any z, E Uie(s)P; and ((x) R
where d' O (log(sk))
3: S + {so}. where so is a point sampled by the coordinator
4: S, + 0 for E [s]
5: N O (k), E' + (=t), m
(2 ,6+ O
sktm (
6: for + 1 to N do
7: Use EFFCCEEN
(P3); (8)-1)) send 8-11 approximation of T(s-11) every site j. Sy + S, U (3
8: Every site updates the cost cost( π (P),, Sz) and sends Dj. a constant approximation of cost(=(P))..5) the coordinator
9: - MECYSAAMLINGG(OoS((((
S,)}, (Dj})
end for
11: Every site j computes |c(²| and ccst(=(C()) S;) for I $ [S], where c( = fx E Ps dist(=(x)), (()) z dist(T((x) sf)) Vp S | 12: Every site j sends constant approximation of |C() and cost ( (c(()) SS to the coordina- tor
13: The coordinator computes Eigis| | and Eigist cost (TT (c(()) Sy)) and sends constant approximation of them every site
14: Every site computes ((x)) (P.P), a constant approximation of (P..) = E.Ep, (((x)) to the coordinator
O (1) (ppppoooxiitation of u(x) locally for all Pj. and send
p(P3) 15: The coordinator samples site j with probability Σ MCP) independently for m times. Let my
be the time site j are sampled. Sends my to site do
for
17:
A; < 0. A + ( for E [m,] do
19:
Sample x with probability
p(x)
[PT
20:
if & is sampled then
21:
4 + A, fr, mpla)) 1, + BFICHENTCOMMUUNCCTTINNS.... + AQU
(G, m J. where (xx) is (1 ( -ppppoooximt of ((x)
22: end if
23: end for
24: end for
25: A' t U 14
26: return A'
Proof. Since we use EETICENCCOMMUNCCTTNEEEE. (()))))))) to send -61
8 by
Lemma E.4, [|;=); 5(5) ll2 I <') 7 =(;- l2 for any x E P.. Hence [| 3 llz
would be (1 + ee) appproximaaoo of [|>(<) - (
Since π is a Johnsonn-Lindenstraan mapping, by Theorem B.9, [x) - E ( | 22 3 J v1lza with probability at least 1 a(s))- Therefore, || - (v)ll2 1 vl12, $ 11 vllal
holds for any x,y E P- Use P. with probability at least 0.99. Since || - T is
constant approximation of any x, y E and (T())=((/ 5(22 l2 is --prro-appooiiiaatinn of [[-)
(st-1))l2, thus [(()) 5(62 ||2 would be 4-approximation of ||ar 1-1
39

---

Published as a conference paper at ICLR 2026
By sending Dj. (1) (11-apppoxiiaaion of cost(= Sy), the coordinator (1)-
approximation of C). Thus, we can apply adaptive sampling, and by Theorem B.10, would be (O (1), O -iic-ticiit approximation of the optimal solution for (k, =)chustrnni of P= -ن=1 Pj with probability at least 0.99.
Since c( for E P3 : dist( 3( I dist(T(2),, 3/") Vp S |ls} and 1/4 dist(r, sp) S dist(T(<)), 5p ) I 4 dist(z, sp). therefore, To dist(x, S (ist(T(x)),) (()) s 16 dist(r, S) cl Hence, if we apply sensitivity sampling with
1 u(x) = 4
1
cost(T(2)),
cost(T(z),,
A
k Uドニ ci
k Eigis D
EissstJet D(
Eis(sTJEls D
where D( = cost T (c()) S)) and Ap = Eicial D
it would return a (1 + + }--coreset for
Uī_1 cisl
P = P3 with probability at least 0.99.
Since we send T to the coordinator by EDTUCIENCCOMMUUCCCTTOSSSSSSS
thus || x|12 S
e'Iss 2/|2, where is the point in S closest to æ. Since I æ||2 S E'| x112. by the proof of Lemma B.13, (1 ) cost A) S cost(C, A') S (1+ i cost(C, A) for any solution |C] k.
Since P is (1 coreset of X, A is a (1 + f) coreset of P. and A' is (1 + cooreet of A, therefore, A' is (I + E) -coreset for X.
Evaluation of the success probability. To apply adaptive sampling, we need to apply CFFICINNCOMMUNICCTTOONTITT = (8x-1)), for every P3 and 8,-1, which would be O (sk) times of running in total. Since we need to apply EPPCCENTCCOMUUNCATOONN every point sampled by sensitivity sampling, it would be m times of running in total. Since
x, x,,', for
8 + O sk the probability that all instances of EFFCCENNTCOMMUNICTTOOO returns an ap- proximate location accurate enough is least 0.99.
Since the Johnson-L Lindenstrauss would preserve the pairwise distance up to a multiple constant factor with probability at least 0.99, the probability that adaptive sampling returns an (O (1), ; (1))- bicriteria approximation is at least 0.99, and sensitivity sampling returns a coreset with probability at least 0.99, therefore, the total probability that Algorithm 16 returns a coreset for X is at least 0.96.
Lemma E.6. Algorithm 16 uses Ö (sh
dk 6243) + dk logn) bits of communication.
Proof. Since we apply Johnson-Lindenssee O (log(sk)), by Theorem B.9, the coordinator needs to send an (log (sk log(sk)) log d) bits random seed to each site that every site generate the map It uses s polylog(s, k. d) bits.
to map P to Rd where d' = O (log Pl)
By Lemma E,4, since |P3| = O (k) and d' O (log(>>))) we need to use polylog(log n, s, +. (P)), (s Since [S] O (k), we need to use d polylog(log n, s, k 3, 1) bits apply ERRCHENTCCOMUUNCCTIOON need to apply SFFICIINCCCOMUUNCTTTTNIEEEEE ((s-)))) for (sk) times to send location of ((s-1) to each site, and apply EPPCHINNCCOMMUNNCTOONN (S, x, s',8) for O min(ee times to send location of points sampled by sensitivity sampling to the coordinator, then the total cost to apply ELFRCIENTCOMMINICCTTOON in bits, is
bits to apply CFFCCENNTCOMUNNICTOOO
E', Since
sk polylog (logn, s, k !)
min(E*, c2tz) polylog loogn s, 1 2)
dk
We need to send the exact location of 8;-1 to the coordinator, which takes O (dk log n)
bits. Every site j sends a constant approximation of |c(² and cost (T (c()) Sy the coordinator, and the coordinator needs send constant approximation of EiS1s) (C() and
40

---

Published as a conference paper at ICLR 2026
.S,) to every site, which costs O (sk loglggn) bits for total. Every site needs to send (P.). to the coordinator, which costs O (s log log n) bits. The coordinator needs to send mi the number of points to be sampled to every site, which costs O (s log k) bits. We need O (1 log log bits to send the weight (x()) to the coordinator.
Eigis cost क (ct))
Therefore, the total communication
for Algorithm is
dk
sk
(anne,,e2tt) + dk log
bits.
We now give our full guarantees of our algorithm for the coordinator model. Theorem E.7. There exists an algorithm that returns a (1 + coreset X with probability least
0.96 in the coordinator model and uses Ô sk min(s 3T dk log n bits of communication.
dk
Proof. The proof follows immediately from Lemma E.5 and Lemma E.6.
E.3 CLUSTERING ON GENERAL TOPOLOGIES
We provide a formal definition of distributed clustering under general topologies. Let
(UI...., ) be set of nodes connected via an undirected graph G = (V, E), where each edge (U;, UU) E represents a direct communication link between sites i; and vy. Each node i; holds a local dataset X,, and the global dataset is X U X,. Communication is allowed only along the edges of G.
The objective is to compute of k centers C ((,,.... Ck) that minimizes the global clustering
cost for a given norm parameter = 2 1:
cost(XXC)=
Σ d(s,C)², ZEX
where d(x, C) min d(x,, (z) the distance from point x to its closest center in C. The goal is to compute an approximate set of centers Ć while minimizing communication over the edges of G.
In Balcan et al. (2013), the clustering problem is studied under this general-topology setting.
They assume s sites are connected by an undirected graph G = (V, E) with m |E] edges. ddk
Their algorithm constructs (1 + e)-coreset, with communication O (m (gt + sk log sk)) words for k-means and O (m (= +k)) words for k-median. Since word requires O (d n) bits in their model, the corresponding costs are (mdk log n (át + s log sk)) bits for k-means and O (mdk log ( + )) bits for k-median.
Our coordinator-model algorithm the coordinator traverses at most m edges, multiplying total communication by m. The resulting communication cost, in bits, becomes
be naturally extended general topologies: each message
dk
m
sk
min(E4,,2+17 + dk log log
Compared to Balcan et al. (2013), our approach improves the dependency on n by replacing a mul- tiplicative log factor with additive term, while preserving the approximation guarantees for general (ks, z)-clustering.
F ADDITIONAL EMPIRICAL EVALUATIONS
In this section, we perform additional empirical evaluations on both synthetic and real-world datasets to further support theoretical guarantees. Unlike the experiments in the blackboard model pre- sented in Section 4, we now focus on assessing our algorithms in the coordinator model. As a baseline, the fonstant-factor approximation algorithm based adaptive sampling, denoted
41

---

Published as a conference paper at ICLR 2026
AS. The second applies a standard dimensionality reduction approach to each of the points, using shared randomness, which can be acquired from public randomness, corresponding with the more coamuuication-efffccee
variant AS-JL. In particular, for dataset with d features, a random matrix of size d' x d, where each entry is drawn from the scaled normal distribution V/ -O 1) and d' is set be constant factor smaller than d, i.e., d' = = or d' = 4. Finally, apply our compact encoding scheme to the sampled points, centers produced by adaptive sampling. representing our coordinator model algorithm, denoted by EAS-JI.
generate
16df
Clustering Cosls
Commoniiaaton Custs
65 Coete Enbji Conts
AS Conne
A5yl Carme
E4G-1 Commrn
1.00
10831
0.90
0.80
Sampping Confiiiier
Sampling Confiiiee
(a) Clustering costs
(b) Communication Costs
Fig. 7: Experiments for clustering costs and communication costs DIGITS dataset
F.1 REAL WORLD DATASET
We first evaluated our algorithms the DIGITS dataset (Alpaydin & Kaynak, 1998), previously described in Section 4. As before, we use the parameters n = 1797, = 64, and k == 10. We set d' o 16 for AS-JL and EAS-JL. We compare the clustering costs in Figure 5a and commu- nication costs in Figure 5b for e E {11, 12, 20}. Our results show that the clustering costs of consistently competitive with the centers returned
the centers returned by our algorithm EAS by the other algorithms AS and AS- ALL-LL, while using significantly less communication across all settings of e E {11, 12, .... 20). For example Figure 7 shows that
11, the clustering cost of EAS-JL is roughly 1.07 times the clustering cost of AS while using 9x less communication. This trend seems to continue throughout the range the sampling coefficient e, e.g., at 20, the clustering cost of FAS-JI. remains roughly 1.07 times the clustering cost of AS while still using roughly 9x less communication.
F.2 SYNTHETIC DATASET
We next evaluated our algorithms synthetic datasets consisting of Gaussian mixtures, as in Sec- tion 4. Specifically, we generated k 3 clusters, each containing 640 points for a total of 1920 points, each with & features. for total dataset size of 15360. Each cluster was drawn from distinct Gaussian distribution whose mean was selected uniformly at random from the range [-10, 10j$, and whose covariance matrix was generated as a random -ositive-definite matrix, producing clusters of varying orientations and shapes.
We compare clustering costs and communication costs across sampling coefficient of e 21, 10). and find that EA consistently achieves clustering performance competitive with both AS and AS-JL while using substantially less communication. For instance, e = 5, the clus- tering costs of EAS JL and AS almost equal, while the communication cost of EAS-JL is more than a factor 4x better. Similarly, at c 10, the clustering costs of EAS-JD JL and AS are al- most equal, while the communication cost of EAS- JL is a factor of almost 8 better. These results parallel our findings on real-world data, demonstrating that our algorithm effectively preserves the clustering quality while significantly reducing communication in the coordinator model.
42

---

Published as a conference paper at ICLR 2026
Communication
2000
7000
50000
1382
60020
2000
40000
1000
Fig. 8: Experiments for clustering costs and communication costs on synthetic dataset
43


Reviews:
[{"review_id": "zWxNoUS2qJ", "reviewer": "Reviewer_w3Z4", "summary": "The paper constructs coresets for the $(k,z)$ clustering problem in distributed setting for coordinator model where a coordinator facilitates the communication between nodes in rounds and also for the blackboard model where communication is using a shared 'blackboard'. For both models, by using the coresets, the paper improves the existing communication complexity for the $(k,z)$ clustering problem. The paper also demonstrates the effectiveness of the coresets with empirical evaluations on real and synthetic data.", "questions": "See Weaknesses", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) The problem is an interesting one and will be of interest to the community.\n2) To the best I could check, the claims in the paper appear sound. The paper is overall written well. \n3) The paper improves on existing communication complexity bounds for both the coordinator and blackboard models.\n4) The way, the usual tools and tricks of coreset literature like JL transform, bicriteria approximation, sensitivity sampling etc, have been modified to fit the requirements of the distributed setting will be of interest to the coreset community.", "weaknesses": "The two minor weaknesses that I see in the paper are:\n1) The structure of the paper makes it a little hard to parse. Also, many ideas like JL transform, bicriteria approximation, sensitivity sampling which are well known are used in a clever way to get the results. However, that technical novelty and challenges are not sufficiently evident from the main body of the paper. The authors should try to highlight them. It may be a good idea to bring the discussion on why the usual techniques are not directly applicable from appendix to main body and also why coordinate wise sampling is required can be elaborated.\n\n2) The experiments are of a proof-of-concept nature and not extensive. Detailed experiments and comparisons on some more datasets and different settings will strengthen the paper.", "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": "bNFX4vUrLy", "reviewer": "Reviewer_DaWp", "summary": "This paper addresses the problem of constructing coresets for Euclidean (k,z)-clustering in distributed settings, where n data points are partitioned across s sites. The authors study two communication models: the coordinator model and the blackboard model. For the coordinator model, they present a protocol that achieves a strong coreset with total communication complexity $\\tilde{O}(sk+dk/\\min${$\\epsilon^4, \\epsilon^{2+z}$}$+dklog(n\\Delta))$ bits, which improves upon prior work (Chen et al., 2016) by avoiding directly to transmit all coordinates. In the blackboard model, they further achieve better bounds of communication cost than previous algorithms. The main contribution of this work is to provide the compact encoding schemes, and sampling operations, and efficient algorithm in message-passing.", "questions": "1.The authors should provide experimental comparisons with existing algorithms in the coordinator model to clearly demonstrate the advantages of their approach.\n\n2.Could the authors include more details and comparative results on how the algorithm performs with varying numbers of machines, in order to assess its scalability in distributed settings?\n\n3.In practical distributed applications, how should the parameters k and s be selected to balance clustering quality and communication efficiency in both the coordinator and blackboard models?\n\n4.Regarding the blackboard model, is the per-machine computational complexity small enough to allow application on resource-constrained edge devices?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper improves the communication complexity for distributed (k,z)-clustering coresets in both the coordinator and blackboard models as illustrated in Figure 1, eliminating the need to send raw coordinates.\n\n2.The paper presents a solid theoretical contribution to the study of distributed coreset construction for Euclidean (k,z)-clustering. \n\n3.The paper is well-written and well-structured, making the technical content accessible.\n\n4.The combination of new coreset constructions, compact encoding strategies, and communication-efficient protocols results in practical algorithms that are easy to implement in real-world distributed systems.", "weaknesses": "1.While the paper proposes distributed algorithms for both the coordinator and blackboard models, the experimental evaluation only includes results for the blackboard model. No empirical comparison or validation is provided for the coordinator-based algorithm. \n\n2.There is no evaluation of how the algorithm scales with the number of distributed machines, which is critical for understanding its practical applicability in real-world distributed systems.\n\n3.The paper provides only communication complexity bounds, without reporting the actual running time and memory on the coordinator or client machines. \n\n4.The paper lacks a clear and formal definition of clustering under general topologies, which is briefly mentioned but not elaborated upon.", "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": "5JCuAhKOgT", "reviewer": "Reviewer_sPGF", "summary": "The paper studies the construction of coresets for Euclidean $(k,z)$-clustering in distributed settings, where the $n$ input points are partitioned among $s$ sites. Two models are considered: the coordinator model, where all sites communicate only with a central coordinator over private channels using private randomness, and the blackboard model, where each site can write on a public blackboard visible to all, but still uses private randomness.\n\nIn the coordinator model, the authors design a $(1+\\epsilon)$-coreset using roughly $O(sk + dk + dk \\log(n\\Delta))$ bits of communication (hiding dependencies on $z$ and $\\epsilon$). In the blackboard model, they further reduce the communication complexity to $O(s \\log(n\\Delta) + dk \\log(n\\Delta))$ bits.\n\nTo achieve these results, the paper first presents a randomized bicriteria algorithm that uses only $O(s \\log n + kd \\log n)$ bits of communication. This is achieved via a lazy sampling procedure based on the adaptive sampling technique from prior literature. The key insight is to sample from a distribution close to the adaptive one, but requiring fewer communication bits. The resulting bicriteria solution is then used to construct the coresets through sensitivity sampling. Finally, the authors present experimental results supporting their theoretical claims. However, the paper lacks technical proofs, making it difficult to verify the correctness of the results (though they appear plausible).", "questions": "1. Could the authors elaborate on the main technical ideas that enable the reduction in communication complexity?\n\n2. What is the size of the constructed coresets? Is there a particular reason why the coreset size is not explicitly stated in the technical results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 3, "strengths": "1. The results are interesting and elegant — unlike prior approaches that required a communication term of $sdk \\cdot \\log(n\\Delta)$ (due to each site transmitting point coordinates), the proposed approach eliminates this per-site dependence.\n\n2. The techniques appear to involve clever ideas and nontrivial technical depth.", "weaknesses": "1. The main concern is presentation quality. The paper does not clearly explain the technical innovations. Moreover, the absence of proofs prevents the reader from understanding or validating the key arguments. This issue is aggravated by theorem statements (e.g., Lemmas 2.1 and 2.2) referring to algorithms that are not actually described in the main text. While the results seem promising, the lack of detail makes it impossible to assess the technical contributions on their merit.\n\n2. Related to the above, several algorithmic components are mentioned (e.g., in Lemmas 2.1 and 2.2) without any accompanying description or pseudocode, making it hard to follow the logic or reconstruct the methodology.", "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": "qsNVvqgZZt", "reviewer": "Reviewer_WL6Z", "summary": "The paper addresses the problem of efficiently constructing $(1+\\varepsilon)$-coresets for Euclidean (k,z)-clustering in a distributed environment, focusing on two prominent and practically relevant communication models: the coordinator and the blackboard models. The authors propose novel distributed protocols that provide strong $(1+\\varepsilon)$-approximation guarantees while simultaneously significantly reducing the overall communication complexity compared to prior best known results.", "questions": "It will be helpful for readers if the authors can elaborate on the computational overhead incurred from the compact encoding and decoding schemes.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The protocols presented almost match the lower bounds ie up to polylogarithmic for distributed $(1+\\varepsilon)$ coreset construction for Euclidean (k,z)-clustering in both the coordinator and blackboard models. Further, \n\n- The work introduces compact encoding schemes that enable coordinators/servers to exchange essential summary information rather than raw point coordinates.", "weaknesses": "- The protocols likely introduce implementation complexity relating to encoding/decoding, and requirements for synchronization among nodes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)