Jigsaw Game: Federated Clustering
Authors: JINXUAN XU
Hong-You Chen
Wei-Lun Chao
Yuqian Zhang
Venue: Accepted by TMLR ()

Abstract: Federated learning has recently garnered significant attention, especially within the domain of supervised learning. However, despite the abundance of unlabeled data on end-users, unsupervised learning problems such as clustering in the federated setting remain underexplored. In this paper, we investigate the federated clustering problem, with a focus on federated k-means. We outline the challenge posed by its non-convex objective and data heterogeneity in the federated framework. To tackle these challenges, we adopt a new perspective by studying the structures of local solutions in k-means and propose a one-shot algorithm called FeCA (Federated Centroid Aggregation). FeCA adaptively refines local solutions on clients, then aggregates these refined client solutions to recover the global solution of the entire dataset in a single round. We empirically demonstrate the robustness of FeCA under various federated scenarios on both synthetic and real-world data. Additionally, we extend FeCA to representation learning and present DeepFeCA, which combines DeepCluster and FeCA for unsupervised feature learning in the federated setting.

Published in Transactions on Machine Learning Research (07/2024)
Jigsaw Game: Federated Clustering
Jinxuan Xu Department of Electricol and Computer Engineering Rutgers University
jincunn.mcrruggers.ct
Hong- You Chen
chen.9301 @osu. edu
Deportment Computer Science and Engineering The Ohio State University
Wei-Lun Chao
chao.209 2et.209GGsss Gosu. edu
Department of Computer Science and Engineering The Ohio State University
Yuqian Zhang
yqz. uyz.zhanggrrutgersscoo
Depariment of Electrical and Computer Engineering
Rutgers University
Reviewed on OpenReview: https: // optp//vieepr..ew...mmmm net/ forum? id= 8YcUJb
Abstract
Federated learning has recently garnered significant attention, especially within the domain of supervised learning. However, despite the abundance of unlabeled data on end-users, unsupervised learning problems such as clustering in the federated setting remain under- explored. In this paper, we investigate the federated clustering problem, with a focus on federated k-means. We outline the challenge posed by its non-convex objective and data heterogeneity in the federated framework. To tackle these challenges, adopt new per- spective by studying the structures of local solutions in k-means and propose one-shot algorithm called FECA (Federated Centroid Aggregation). FECA adaptively refines local solutions on clients, then aggregates these refined solutions to recover the global solution of the entire dataset in a single round. We empirically demonstrate the robustncss FECA under various federated scenarios on both synthetic and real-world data. Additionally, we extend FECA representation learning and present DEEPFECA, which combines DEEP- CLUSTER and FECA for unsupervisod feature learning in the foderated setting.
1 Introduction
Federated learning (FL) has emerged as promising framework, enabling model training across decentralized data. This approach addresses data privacy concerns by allowing data to remain on individual clients. The goal of FT. to collaboratively train model across multiple clients without directly sharing data. Within this context, FedAvg McMahan al. (2017) has been considered the standard approach FL, designed obtain centralized model by averaging the models trained independently on each client's data.
Although FL has widespread applications in the domain of supervised learning, particularly in tasks like classification (Oh ct al. 2021 Jiménez-Sánchez et al. 2023), its utilization in the unsupervised learning sphere is still largely unexplored, even though it holds significant potential and applicability in numerous practical situations. smartphone users. In such instances, foderated unsupervised learning can be a powerful paradigm, enabling the use of unsupervised learning approaches to leverage the safeguarding user privacy.
notable example the large collections of unlabeled photographs owned by most
t "collective wisdom" " of these unlabeled data while

---

Published in Transactions on Machine Learning Research (07/2024)
In this paper, investigate federated unsupervised learning, particularly focusing on the popular clustering problem of k-means. In prior studies, clustering methods have been applied in FL, mainly focusing on prob- lems such as client selection (Ghosh et al. 2020 Long et al. 2023) and privacy enhancement <Li et al. 2022; Elhussein & Gürsoy 2023). without a deep investigation into the unsupervised learning aspect. Morcover, existing distributed clustering methods overlook the unique challenges in FL,, such as data heterogeneity and communication efficiency, making it difficult to apply in the federated setting. Our study extends to federated clustering, incorporating unsupervised clustering on individual clients within a federated framework.
One key challenge of federated clustering is the inherent non-convexity of clustering problems, presenting multiple equivalent global solutions and potentially even more local solutions. Standard algorithms like Lloyd's am Lloyd (1982) can only find a local solution of the k-means problem, without guaranteeing global optimum. We note that the term "local solution" in this contert refers to a local optimal in optimiza- tion, not the solution learned from a cliend] This challenge is amplified the federated setting, where each client's data is a distinct subset of the entire dataset. Even under the IID data sample scenario, each client's clustering results might be suboptimal local solutions containing spurious centroids far from the true global centroids. And this issue could become even more pronounced under non-lll scenarios.
To this end, we propose a one-shot federated k-means algorithm: Federated Centroid Aggregation (FECA), offering a new approach by exploiting structured local solutions. In the k-means problem, local solutions carry valuable information from the global solution. The proposed algorithm resolves these local solutions and leverages their benign properties within the federated clustering framework. FECA is built upon theoretical studies (Qian et a 2021 Chen et al., 2024) derived in a centralized setting, which suggests that every local solution is structured and contains nontrivial information about the global solution. Specifically, local solution consists of estimates of the k ground truth centers, with subset of these estimates being accurate.
One common concern of FL lies in the potential decrease in performance compared to centralized models due to data heterogeneity across clients. However, from the perspective of local solutions, federated clus- tering could benefit from the decentralized framework. Each client's solution, whether a local optimum or not, carries partial information about the global solution of the entire dataset. By incorporating multiple clients' solutions, the central server could potentially recover the global optimal solution in one shot, akin to assembling a jigsaw puzzle of clients' solutions. For instance, if true centroid is missing from one client's solution, it might be identified in the solutions of other clients.
Therefore, FECA is designed to recover the global solution for k-means clustering in a federated setting by refining and aggregating solutions from clients. First, Lloyd's algorithm for k-means is performed on cach client's 's data. Then, FECA adaptively refines spurious centroids using their structural properties to obtain a set of refined centroids for each client. Then refined centroids are sent to the central server, where FECA aggregates them to recover the global solution of the entire dataset. By exploiting the structure in local solutions, FECA is able to accurately identify the true & centroids of the entire dataset in one shot.
We further extend FECA beyond a pre-defined feature space to the modern deep feature framework Liu et al. 2021). Specifically, we present DEEPFECA, a federated representation learning algorithm from de- centralized unlabeled data. Concretely, we pair FECA with clustering based deep representation learning models such as DEEPCLUSTER Caron et al. (2018 2020), which assign pseudo-labels according to k-means clustering and then train the neural network in a supervised manner. The resulting algorithm, DEEPFECA, alternates between applying FECA to the current features and using DEEPCL.STEE for further training. This iterative process enhances the model's ability to learn meaningful representations from the decentralized data.
We evaluate both FECA and DEEPFECE A on benchmark datasets, including S-sets Fränti & Sieranoja (018)) CIEAR Krizhevsky et al. (2009), and baselines in various federated settings, demonstrating its effectiveness in recovering the global solution. Furthermore, DEEPFECA shows promising performance in federated representation learning.
Le & Yang 20155). FECA consistently outperforms
1 For clarity, throughout this paper, we the client's solution for the result obtained from client. the solution happens to be local solution, we name it the client's 's local solution.
2

---

Published in Transactions on Machine Learning Research (07 2224)
2 Related Work
Fedcrated learning. Mainstream FL algorithms (McMahan et al. 2017 Khaled et al. 2020 Haddadpour & Mahdavi 2019 adopt coordinate-wise averaging of the weights from clients. However, given the limited
performance direct averaging, other approaches have been proposed: Yurochkin et al. (2019); Wang et al.
(2020g; Zhang et al. (2023b); : TTan et al. (2023) identify the permutation symmetry neural networks and
then aggregale after the adaptive permutation; Lin et al. (2020) He al. (2020); Zhou et al.
(020 Chen
& Chao (2021) ;;
Zeng et al. 2023) replace weight average by model ensemble and distillation. These studies
enhance the performance of the synchronization scheme but overlook the impact of local solutions clients.
Federated Clustering. Many distributed clustering methods (Balcan et al. 2013 Bachem et al. 2018 Kargupta et al. 2001 Jamuzaj et al.) 2004 Hess et al.) 2022) have been proposed, but they overlook the heterogeneous challenge in FL. For synchronizing results returned from different clustering solutions, con-
sensus clustering has been studied widely (Monti ct al., 2003 Goder & Filkov 2008 Li et al.) (2021). But it
works on the same dataset, unlike FL. In the context of FL, Qiao et. al. [2021 Li al. (2023); Xia et al.)
22000g Lu et al. 22033); Li et al. (2022) focus communication efficiency or privacy-preservngg A recent federated clustering study Stallmann & Wilbik (0022) proposes weighted averaging for Fuzzy e-means but requires multiple rounds. The study most relevant to ours introduces k-FED Dennis et al. (2021), one-shot
federated clustering algorithm, under a rather strong assumption that each client only has data from a few true clusters. It is still underexplored for federated clustering and usage of local solutions.
Federated representation learning. FEDREP [oolins al. (2021) studies supervised representation learning by alternating updates between classifiers and feature extractors. JJeong et al. (2020); Zhang et al. (2020) study federated semi-supervised learning with the server holding some labeled data and clients having unlabeled data. For federated unsupervised learning, ZZhuag et al. (2021) proposes sell-supervised learning in non-lll settings with a divergence aware update strategy for mitigating non-llD challenges, distinct from our clustering focus. Zhang et al. (2023a) adopts the contrastive approach for model training on clients. A Lubaaa Lubana et al. [202)) introduces federated unsupervised learning with constrained clustering for representation learning, while our focus lies on exploring federated clustering via local solutions.
recent framework
3 Background
Clustering. Given a d-dimensional dataset D {aı E Ed R UN [d], the goal of k-means problem is to identify k centroids C = {cr Rd ,.... Cj Rd that minimize the following objective
N
min I G(C) = Σ
cg112-
(1)
jE[K] n=
Federated clustering. In the federated setting, the dataset is decentralized across M clients. Each client m [M] possesses a distinct subset D,, of the entire dataset D. Despite different data configurations, the goal of federated clustering remains the same to identily à centroids C {ci,..., C& J for D = Um Under this federated framework, the optimization problem in Equation 1 can be reformulated as
min G(C) C
Σ Gc,,C), y7L
(2)
where Gm is the k-means objective computed on Dm- Due to privacy concerns that restrict direct data sharing among clients, the optimization problem described in Equation 2 cannot be solved directly. Thus, the proposed algorithm FECA utilizes collaborative approach between clients and a central server. Initially, each client m independently minimizes (C) ) to obtain a set of k centroids ((m) = (1)) ...., (..,,(()) their dataset Dm-- Then the server aggregates centroids Cmm)(m) to find a set of centroids C for D.
((m)) from
We note that when clients perform standard Lloyd's algorithm for k-means clustering, they usually end up with local solutions C(m)) resulting in suboptimal performance even with IID distributed data Dm These local solutions can significantly complicate the aggregation process the central server. Thus, the key
3

---

Published in Transactions on Machine Learning Research (07 2024)
Centralized Data
Non-lID Client's Data
one-fit-many
many-
global solution
local solution1 local solution2
global solution
global solution
Figure 1: Clustering results. (Left): global and local solutions centralized client's data; (Right):
global solutions for non-lID client's data sharing similar structures.
challenge in federated clustering lies in effectively resolving the client's local solutions and appropriately aggregating them on the central server.
3.1 Structure of Local Solutions
To better resolve the federated clustering problem, we propose to take a deeper look at local solutions in k-means, which often significantly differ from the global minimizer. Recent theoretical works by [iian et al. b2021;; Chen et al. (2024) have established a positive result that under certain separation conditions, all the local solutions share a common geometric structure. More formally, suppose local solution identifies ccntroids (c). Then, there exists a one-to-one association between these centroids and the true centers (c.,..,,( from the global solution. This association ensures that each centroid c; belongs to exactly one of the following cases with overwhelming probability
Case 1 (ona-fit-many association): centroid is associated with (s > 1) true centers .ch...... Sj Case 2 (one/many htt//mmaa--fooots fit-one association): t (t 1) centroids (ct,....,, } are all associated with one true center cj.
Namely, a centroid 6; in a local solution is either a one-fil-many centroid that is located in the middle of multiple true centers (case 1, when s > 1), or one/many-fite
centroid that is close to a true center (case 2). Notably, when G; the only centroid near true center (case 2, when = 1), it considerod a correctly identified centroid that closely approximates a true center. An illustration is provided in Figure I] Next, we will introduce how our algorithm utilizes such local solution structures to obtain unified clustering results in the federated setting.
4 Jigsaw Game FeCA
Algorithm 1 Federated Centroid Aggregation (FECA)
input cluster number & for each client m 1,..., M do
((m), ((m) +- Client Update (k)
4: R(m) + Assign (C(m), D(m))
5: end for
6: C U
C(m)
R M ((m)
C*
+ Server AerverAggooottion (k, R)
9: return C*
The proposed federated clustering algorithm FECA is built upon the collaboration between clients and a central server. Fach client shares its refined centroid solution ((m) with the server, where each ((m) carries partial information of the global solution, similar pieces of jigsaw puzzle. The server then aggregates
Such structure of local solutions holds even when # k*, where is the number true clusters the dataset.
4

---

Published in Transactions on Machine Learning Research (07 (27/2
Clieni
Cliemi
Client
Centralized dataset
Server aggrogation
Clustering results
Removing one-fit-many
Sending to the server
Figure 2: FeCA roadmap. 1st column: The centralized dataset distributed to clients. 2nd column: The k-means clustering results on different clients under non-lID data sample scenario, where black triangles and squares represent centroids. 3rd column: Eliminating one-fit-many centroids in Algorithm [ indicated by hollow squares and triangles. 4th column: Centroids sent to the server. 5th column: Aggrogation received centroids on the server where red crosses represent recovered centroids.
received controids Um,((m) to obtain a unified complete solution C*, akin to assembling puzzle picces in a jigsaw gume. FECA only requires one communication between clients and the server, thanks to adaptive refinement of local solutions on the client side. The detailed procedure is presented in Algorithm and illustrated in Figure 2
Privacy concern. While privacy is crucial in FL, it is not main focus. However, advantage of our one-shot algorithm is its minimal information exchange compared to standard iterative approaches like distributed clustering. In FECA, sending refined centroids to the server is viewed as no more privacy risk than mainstream FL approaches of sending models with classifiers, which more or less convey class or cluster information.
4.1 Client Update Algorithm
Algorithm 2 FECA- Upicte
input cluster number &
2: Apply Lloyd's algorithm on the data of client m to obtain & clusters D(m) (D(m), ...., D(m) and
corresponding & centroids ((m) (c(m) (m²)
while ((m) & Ø do
Detect fit-mit-many centroid clm) whose cluster D! has the largest standard deviation and calculate the objective value (! of the cluster (mm))
Delect many-fit-one centroids cp (m) (m) of clusters D(m) and DIT)) with the smallest pairwise distance.
cq
Merge D(m) and ((m) into cluster Dfm) to obtain centroid c and calculate the objective
value mfm) of the merged cluster D(m)
if G! 2 =fm²) then
((m) C(m) \ (c(")))
9: D(m) + D(m) (()))))
10: else
11: Terminate the loop.
12: end if
13: end while
14: return centroids ((m), clusters (m)

---

Published in Transactions on Machine Learning Research (07/2024)
This step aims to refine the spurious local solutions of k-means clustering on clients. Each client first performs standard Lloyd's algorithm obtain set of centroids ((m) {cl_m) :..... ......:.)), and this solution is only guaranteed to be a local solution. As discussed in (subsection 3.1] despite the variations in solutions across different clients, each ((m) always possesses some centroids Jone/many- one that are proximate to
subset of ground truth centers. To facilitate the aggregation process on the server, we propose retaining only centroids from ((m) that are positioned close to true centers.
The client update step in FECA focuses on refining the solution ((m) by eliminating one-fit- manyfit-many centroids that are distant from any true center. Specifically, a one-fit-many centroid is always located in the middle of multiple nearby true clusters, making distant from most data points in those clusters and leading to a high standard deviation for its cluster. Conversely, many-fit-one centroids, which fit the same true center, are close to each other and thus have a small pairwise distance. As presented in Algorithm 2 we first use these properties to detect the candidate one-fit-many d()) and many-fit-on op Cq likely from spurious local solution.
(m) (m) centroids, which are
Next, for further refinement, need to confirm if these candidate centroids indeed originate from local solution. To this end, for detected one-fit-many centroid d'm), we first calculate the objective value G!m²) of its cluster D(m) as
G! = -E m
|| c: 12.
!mm)
(3)
For detected many-fit-on centroids, we merge their clusters D(T)) D((") to form a new cluster D.m)) with the corresponding centroid c/m) And then we calculate the objective value G/m)) as
Gimi> EEEE(p/" || -|=-
(mm) 12.
(4)
If the current solution ((m) is only locally optimal, D(m) should contain data from multiple true clusters with large c!m), while D(TT) only contains data from true cluster with small Gfm) Thercfore, if a(m) is greater than Gfm), it confirms that these candidate centroids stem from local solution. In such
cases, Algorithm 2 removes c; ((m)) from ((m) for not being close to any true center. Otherwise, if G is loss than Gom)) these centroids are regarded as the correct portion with no need for further refinement.
Notably, there may be multiple groups of centroids that possess the local structure. The algorithm is designed to iteratively identify and refine the local solution. Our theoretical analysis (Lemma A.T in the appendix) demonstrates that Algorithm 2 effectively removes all one-fit-many centroids from local solutions under the Stochastic Ball Model. In this model, we assume that each client's data is sampled independently and uniformly from one of k disjoint balls centered al the ground truth centers. A formal definition is provided in Appendix A
4.2 Radius Assign Algorithm
After removing one-fit-many centroids in the ClientUpdate phase, only centroids near true centers (one/many-it-one) would be sent to the server. This RadiusAssign step prepares these centroids for server- side aggregation by assigning a specific radius to each. This setup allows the server to utilize these radii for effective aggregation. The primary goal of this step is to determine the radius that best approximates the true cluster radius of the entire dataset. In this section, we presont two algorithmic variants for the Aasius step. The first variant Algorithm 3 designed for theorelical validation purposes, while the second variant Algorithm 4 is tailored for empérical experimentation.
Through the theoretical variant, we establish Theorem 4.1 that characterizes the performance of our al- gorithm FECA under the Stochastic Ball Model. This theoretical variant generates a tentative solution ((m) by discarding any potential many-fit-one centroids within C(m), Following this, a radius f((²) then calculated according to the minimum pairwise distance among centroids C(m), and this radius is assigned to every centroid in the original solution ((m) from Algorithm 2 We note that the method for identifying many-fit-one centroids utilized in this theoretical variant is only applicable under the Stochastic Ball Model.
6

---

However, in real-workd applications, especially under non-llD data sample scenarios, it is both challenging and unnecessary to eliminate all many-fit-one centroids from clients' solutions, as they often align closely Published in Transactions on Machine Learning Research (07/2024)
Algorithm 3 FECA- RasiusAssign (Theoretical)
input centroids C(m), clusters D(m)
Initialize new set of centroids ((m) C(m),
3: Determine r for each centroid a/m) E ((m) the maximum distance from any data point in ((m) to
d(h) of = max, (m)) ||=;
(m) - c.
p!m)) 1|2.
for each centroid e!Th))
((()) do
5: Identify the nearest centroid c//pts ((m) to a(m) with the pairwisc distance denoted as dıj.
6:
if r 1/+1% > dij then
7: ((m) - C(m) \ (4
( d())
8: end
end for
10: Calculate the minimal pairwise distance between centroids in ((m); Å (in)
min
m 16: E
11: Determine the uniform radius f(m) Amm and assign it to each centroid (m) c(m).
12: R(m) -U (m) r(())
13: return ((m)
Algorithm FECA- RadiusAssign (Empirical)
1: input centroids c(m), clusters D(m) Determine rf for each centroid c(m)) E ((m) the maximum distance from any data point in D( to (m))l 11.
(m), rf = max, ((") ED!") ||= - cf
for each centroid c: (()) ((m)) do
Identify the nearest centroid (m) calculate r." = =dg
(z4 E ((m) to c()) with the pairwise distance denoted as day. and then
Determine the unique radius r!t²) min( r!?) and assign it to the centroid c!m) end for 7: R(m)
U, (c (m) (r()))))
return ((m)
with true centers. Accordingly, we develop an empirical variant, Algorithm 4 which assumes only one-fit- many centroids are excluded and assigns unique radius (m) to each centroid (m) E C(m), As for remaining many-fit-one centroids, their radii are estimated as half of their pairwise distances, which are typically much smaller compared to those of correct centroids. The server then groups all received centroids based on these radii, prioritizing the largest ones first. This ensures that the smaller radii associated with many-fit-one centroids minimally impact the aggregation process. in-depth analysis of Algorithm 4 is provided Appendix B. showcasing its offectiveness across varicty of experimental scttings, including those with high data heterogeneity.
It is worth noting that the theoretical variant is designed for theoretical analysis under the Stochastie Ball Model assumption. This assumption enables casy identification of many-fit-one centroids for clcarer cluster separation approximation and accurate radius assignment. In contrast, the empirical variant does not need to remove many-fit-oe -ne--fit-oe centroids, as they are close to true centers and aid in reconstructing the global solution on the server side. This approach allows the empirical variant to assign distinct radii cach remaining centroid, enhancing the algorithm's effectiveness and practicality without relying on limited assumptions. A detailed comparison of the theoretical and empirical variants provided in subsection C.4

---

Published in Transactions on Machine Learning Research (07 (07/2024) /224)
4.3 Server Aggregation Algorithm
Algorithm 5 FECA- ServerAggregattion
1: input cluster number k, centroids C, radius n n=1
while C + 2 do Pick (c, R with the largest Ti.
Let S, = (a: a C, l|e cill2 ri)
6: Set ++ |
7: n= -=
8: end while
9: Select top k sets S. containing the largest number of elements.
10: C + me)n((S), E [A]
11: return C*
At the server stage, the goal is to aggregate all received centroids C = (C())..., ,..., C(M) from M clients into unified set of & centroids C*, This task presents apparent challenges: due to the preceding refinement stage, clients may contribute varying numbers of centroids, and the indices of these centroids often lack consistency across clients. However, assuming the refinement phase in Algorithm / effectively removes spurious one- fit-many centroids far from true centers, the returned centroids on the server would be closely grouped around true centers. This phenomenon enables a straightforward classification of all returned centroids into & distinct groups, each aligned with one of the & true centers, as presented in Algorithm 5 Equivalently, this another clustering problem based returned centroids under high Signal-to-Noiss Ratio (SNR) scparation condition. Finally, the server calculates the means of centroids within each group obtain C*.
In some extreme cases where the number of groups n might be less than k, such as when all clients converge to the same local solution. In such cases, Algorithm 2 removes one- one-fit-many centroids associated with the same true clusters from all clients. This renders impossible for Algorithm to reconstruct corresponding true centers without receiving any associated centroids from clients. Tt important to note that this scenario is trivial within the federated framework, where all clients share the same local solutions. Essentially, is akin to having only one client encountering local solution. Further discussion cases when < is provided in the Appendix E
4.4 Theoretical Analysis
We now state our main theorem, which characterizes the performance of FECA under the Stochastic Ball Model. Assume the data (m) of client m is sampled independently and uniformly from one of & disjoint balls I. with radius r, each centered at a true center 0% s E [k]. Each ball component under the Stochastic Ball Model has a density
[a(x) = Vol(B.) 1 (x).. (z).
(5)
Additionally, we define the maximum and minimum pairwise separations between the true centers {0:).ejk
Amaz max ||0] 0% ll2, Amin := min |0; - exe'
afss
Theorem 4.1. (Main Theorem) Under the Stochastic Ball Model, for some constants À 223 and vj 2 5, iʃ
Aman 2 4 and Amin 2 10mAk² VrAmoz,
is close to then by utilizing the radius determined by Algorithm any oulput centroid e from Algorithm some ground truth center:
4 Amin-
||c 83 112 S
(6)
5n
8

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Theorem 4.1 characterizes the performance of our main algorithm FECA, utilizing the radius from Algorithm The proof, provided in Appendix A builds on the infinite-sample and high SNR assumptions established in Qian et al. (2021) which characterizes local solutions of centralized k-means. Next, we will provide a discussion of both conditions.
Separation Condition: the separation between true centers Ami and Amaz cannot be too small is generally necessary for local solution to bear the structural properties described in [subsec- tion 3.1 Qian et al. (2021). Additionally, the ratio Amar indicates how evenly spaced the truc centers are, with the ratio approaching! 1 when the true centers are nearly evenly spaced.
Amin
main theorem heavily depends the Stochastie Ball Model and infinity sample assumptions. We would love to note that the local solution structure also holds when the data follows the Gaussian mixture model or has finite data samples Chen et al. (2024). We view these technical assumptions as less important than the above separation condition and will corroborate using both synthetic and real clustering data to demonstrate the effectiveness of our algorithm.
Technical Assumptions:
Note that above assumptions often not met in practice. Thus, develop another variant, Algorithm which does not require the elimination of many-fit-one centroids and assigns unique radius to each returned centroid from the client. A detailed empirical evaluation of these radii determined by Algorithm is presenled in Appendix B. showcasing their effectiveness in supporting our algorithm FECA.
4.5 Discussions on Heterogeneity
We assume that the client's s local solution for its dataset D. is also a local solution of the entire dataset D UnDm, which allows us to leverage the structures discussed in ssbsecctio 3.1, This assumption holds when Dm is an IID-sampled subset from D. Our experiments showcase non-ITD conditions. Here we provide an explanation in Figure 1 where right plots illustrate two clients' non- IID sampled data and the corresponding global solutions (achieve a global optimum when k = k We found that despite the data heterogeneity, the clients' global solutions share similar structures as described in ssbsectionn 3.1 We attribute these observations to the fact that under non-IID conditions, clients' data tend to concentrate on some of the true clusters. This increases the chance that clients' global solutions contain many-fit-one centroids for those true clusters, which can be aggregated together on the server by our algorithm FECA. This scenario also suggests that even if client can recover the global solution its non-llI data, such global solution coincides with local solution on IID data and we still need to deploy FECA to produce the final solution.
algorithm's 's robustness even under
5 DeepFeCA
With FECA, we can learn centroids C* in the pre-defined feature space collaboratively with multiple clients. In this soction, we extend F&CA to unsupervised representation lcarning Liu al.) (2021), aiming learn feature extractor fe parameterized by 0 from the unlabeled data set D, such that the extracted feature better characterize its similarity dissimilarity to other data instances.
(o( of data
Some studies (Asano et al. 2020 Caron et al. 2020
2018 integrate clustering approaches with unsupervised
representation learning. For instance, Caron et al. (0018) proposed DEEPCLUSTER, which learns fe( from
an unlabeled dataset. = {x,) N by repeating two steps:
Perform Lloyd's algorithm on {fo(En)) to obtain set of i centroids {c
Create pseudo-labeled set D = (I ) where û. arg miny || -2ll2, and learn so with linear classifier in a supervised fashion for multiple epochs.
3R indicates the number of centers in the entire dataset.

---

Published in Transactions on Machine Learning Research (07/2024)
Algorithm 6 DEEPFECA for Representation Learning
Input: cluster number k, total number of clients M, round number T Initialization: server model 0
3: for round t= 1, ,T do
4: Perform FECA with M clients to obtain k aggregated centroids C (k-means clustering is performed
on features extracted by fe on each client).
5: Broadcast and C to all clients.
for each client m E [M] do
7: Create Dm [[rn [m)
Di ) where yn
(m) arg miny || (m))) - cylle and dj E C
Train together with a lincar classifier D,,. for multiple epochs obtain the client model p(m).
end for
10:
+- Em=1 [D]
(())
11: end for
12: Return the model 0
DEEPCLUSTER is known for its simplicity and has been shown to perform on par with other more advanced self-supervised learning methods for representation learning Eriesson et al. (2021). In this paper, we extend DEEPCLUSTER to the federated setting and propose DEEP BCA,, which integrates DEEPCLUSTER within the AvD McMahan et al. (2017) framework. Namely, DEEPFECA iterates bet ween local training of So fo(x) on each client and global model aggregation for multiple rounds. At the end of each round, DEEPFECA applies FECA to update the centroids that are used to assign pscudo labels. Algorithm c outlines our approach, where the red lext. corresponds to FECA, the blue text corresponds to DEEPCI.USTER, and the green lext corresponds to the element-wise weight average of FEDAVG.
6 Experiments
We first evaluate FECA on benchmark synthetic datasets, which have well-established true centers. Then we extend our evaluation to frozen features of real-world image data extracted from pre-trained neural networks. Additionally, we assess the representation learning capabilities of DEEPFECA by training a deep feature extractor network from scratch in the federated framework.
To simulate the non-IID data partitions, we follow Hsu et al. (2019) split the data drawn from Dirichlet(a) for multiple clients. Smaller indicates that the split is more heterogeneous. We also include the IID setting, in which clients provided with uniformly split subsets of the entire dataset. Furthermore, we have standardized the number of clients to M = 10 for all experiments in this section. A detailed discussion on the impact of varying the number of clients is provided in Appendix D
Baselines. We mainly compare three baselines:
Match Averaging (M-Avg): matches different sets of centroids from clients by minimizing their fadiistances and returns the means of matched centroids.
the onc-shot federated clustering method Dennis et al. (2021 designed for hetcrogencous data, assuming that each client's 's data originates from k S V true clusters. The method utilizes a small K' for k-means clustering on clients. In the following experiments, we select a single for each dataset, with detailed tuning experiments provided in isubsection C.5)
k-FED:
FFCM: Stallmann Wilbik (2022) focuses on fuzzy e-means clustering and presents two versions of aggregation algorithms, which are weighted averaging centroids (vl) and applying k-means on centroids (v2). Since this method is not designed for a one-shot setting, report its results for both round 1 and round 10 in the following experiments.
Additionally, we include a centralized benchmark, representing the performance of k-means clustering on the entire dataset without foderated splits. In the following experiments, we set k' for all methods except for &FF..
10

---

Published in Transactions on Machine Learning Research (07/2024)
Evaluation metric. For synthetic datasets with known true centers, assess recovered centroids by calculating the fz-distance wetween output centroids and true centers. In contrast, for real datasets where true centers are unknown, we adopt the standard clustering measures including Purity and Normalized Mutual Information (NMI). The average Purity for all clusters is reported. NMI mcasures the mutual information shared between clustering assignments X and true labels Y defined as NMT(X,Y) (H(X)))((H()) + H())), where I denotes the mutual information and is the entropy.
6.1 FeCA Evaluation
On synthetic datasets. We evaluate FECA on benchmark datasets in Fränti & Sieranoja (2018) with known truc centers. Specifically, focus S-sets, comprising synthetic data characterized by four different degrees of separalion. S-sets includes four sels; S1, S2, S3, and S4, each consisting of 15 Gaussian clusters in R.2 Visualizations of S-sets are provided in Appendix C
We assess recovered controids by calculating the lg-distance to ground truth centers, with mean results and standard deviation from runs reported in (Table 1] Additionally, the Purity and NMI of clustering assignment quality are presented in suubsection C.1 We investigate three data sample scenarios the federated setting: IID, (OrichlettO.3)). and (1richlet And select k' for k-FED after careful tuning (detailed in subsection C.5
Results in Table indicate that our algorithm FECA consistently outperforms all basclines in recovering the global solution across all experimental settings. Figure 4 provides a visualization of these results, demonstrat- ing that even under the challenging non-IID scenario (1richlet(0.3). FECA's recovered centroids closely approximate the true centers.
Table 1: fz-distance (scaled by 104) between recovered centroids and true centers S-sets under three data sample scenarios. Dirichlet(O.3) and (irichlet(O.1)) are denoted as (0.3) and (0.1), respectively. Rd indicates rounds for FFCM. We report mea from 10 random runs.
G-distance x10
S-scts (S1)
S-scts (S2)
Method
IID
(0.3)
(0.1)
IID
(0.3)
(0.1)
M-Avg
7.2
45.8+5.00
63.0+2.8
14.747.1
51.418.9
64.0#11.1
FRd=11
12.2+15.8
80.7+13.3
81.1+15.7
16.7+20.4
70.9+13.3
89.7+16.0
(Rd=11))
3.3+1.4
50.318.8
66.1112.4
9.6119.11
56.9+12.3
60.31:1.2
FFCMv2(Rdl=1)
23.1419.4
75.7+16.8
77.0+14.4
16.1416.9
71.9+13.5
79.9+12.6
FRCMv2(Rd=10)
2.640.4
42.9+14.8
54.2114.6
32.940.5
18.1
59.4125.8
{-FED(K=5)
84.6+15.8
59.4+12.3
59.8+16.9
75.9+17.7
64.1+13.1
63.9+11.6
FECA
1.0+10.1
6.8.13.7
22.3+11.6
1.910.11
13.6
38.843.4
Centralized
14.3+18.7
8.4+-14.7
f-distance x10
S-sets (S3)
S-sets (S4)
Method
TID
(0.3)
(0.1)
IID
(0.3)
(0.1)
M-Avg
16.4+6.8
35.5
46.7+5.3
14.2+3.7
28.7+3.3
40.146.4
(Pd=11(Rd=1)
16.6
58.1
77.4
11.449.5
45.0+8.9
63.1
(Bd=11)
11.4+15.5
45.918.8
66.6+12.9
4.811.3
45.0
52.0+11.9
FFCMv2(Rd=1)
18.2+12.6
62.7+12.6
79.1+10.2
13.0+11.4
48.9
60.419.6
FRCMv2(Rd=10)
4.5400.7
49.4+19.3
56.7+11.7
4.940.6
44.649.11
49.947.3
k-FED(K==5)
73.1+14.3
65.6+15.2
68.8+12.8
52.7++0.8
43.446.3
47.5+
FECA
3.640.7
23.618.8
33.216.7
4.740.77
24.547.2
31.545..8
Centralized
15.4
20.1+10.0
Remark 6.1. Note that Table suggests that FECA (and some other federated clustering methods) can even out perforrmm the centralized k-means. From the perspective of federated learning, this may look odd.
11

---

Published in Transactions on Machine Learning Research (07 (27/))
S-ects(S1) - LID
S-9cis(S1) (0.3)) (0.3)
S-sots(S1) - (0.1)
(-3)ts(S3)
(-sets(S3) (0.3)
S-gets(S3) (0.1)
d-diittance
125
125
188
3t 38
100
5
50
M-Arg
FRCM)I(Rd-1)
(Rd-11(
S-ects(S2) LID
S-scts(S2) (0.3)
(-2c (0.1)
S-sets(S4) HID
S-scts(S4) (0.3)
S-9cts(S4) (0.1)
FFCMv2(Rd-1)
fy-distance
125
125
50
s0-
FFCMv2(Rd-10)
60
kFFE(EE
FeCA
scods
seeds
seeds
sceds
10 seods
10 seeds
Figure 3: Illustrations of l-distance results in Table with 10 random seeds.
S-scts (SI)
M-Avg
(RC=)I(Rd=I) FRCMVI(Rd-10) FFCMv2(Rd=1) FFCMv2(Rd=10)
K-FED (K-5)
FeCA
S-sets (S4)
M-Avg
FFCMvi(Rd-I) FRCMv1(Rd-10) FFCMv2(Rd-1) FFCMv2(Rd-10) k-FED (K'-))
FeCA
Figure 4: Visualizations of S-scts (S1&S4) and recovered centroids by different methods. Results are showcased under the (0.3) data sample scenario. Blue dots represent recovered centroids, and red crosses indicate the ground truth centers.
But it makes perfect sense from the local solution point of view of k-means. Solving centralized k-means likely leads to local solution with suboptimal performance. However, with multiple clients independently solving k-means, their solutions together have a higher chance to collaboratively recover the global solution. To explore this advantage of FECA, we conduct experiments on the impact of varying numbers of clients on the synthetic dataset, as detailed in Appendix D
On frozen features. We evaluate FECA on features extracted from pre-trained neural networks using real datasets CIFAR10/100 Krizhevskk al. (2009). And the frozen features are generated from the ImageNet pre-trained ResNet-50 He et al. (2016) model. For A-FDD algorithm, k' = 10 for CIFAR100, following the suggestion k'' V from their paper. In Table 2 we present the average Purity and NMI calculated from three random runs. Our algorithm FECA demonstrates robust performance across different data sample scenarios. And it outperforms all baseline models in most cases.
select. k 3 for CIFAR10 and
Under the extreme non-IID scenario - Dirichlet(O.1), the k-FED algorithm tends to outperform others. This is because &-FED designed for high heterogeneity, assuming each client. possesses data from k' S v true clusters. Without considering local solution structures in k-means, k-FED relies on an accurate selection of k to reduce the chance of occurrence of spurious centroids in scenarios of high hetcrogeneity, in Figure 1 right). This strategy makes its performance highly sensitive to the choice of k', and it tends to decrease rapidly in less heterogeneous cases. This situation highlights the importance of addressing local solutions in federated clustering.
illustrated
6.2 DeepFeCA Evaluation
We validate DEEPFECA on the CIFAR10/10 1000 and the Tiny-ImageNet dataset with 64 x 64 resolution. We randomly initialize a ResNet-18 model and train for 150 rounds, with 10 clients fully participating the process. Each round we train 5 local epochs for clients' models with batch size 128. We modified the official implementation of DEEPCLUSTERR- Caron et al. 2020 and followed their training details.
12

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Table 2: Purity and NMI on C0F0R-10/100. We present mean results from three random runs under four data sample scenarios. For k-FED method, we select =' on CIFAR-10 and =-100 on CIFAR-100.
CIFAR-10
CIFAR-100
Purity
NMI
Purity
NMI
Method
ITD (1.0) (0.3) (0.1) ITD
(1.0) (0.3) (0.1)
ITD (1-0) (0.3) (0.1)
TID
(1.0) (0.3) (0.1)
M-Avg
0.48 0.45 0.41 0.39
0.43
0.41 0.35 0.34
0.20 0.19 0.19 0.18
0.37 0.37 0.36 0.36
FFCMv1(Rd=1)
0.24 0.32 0.37
0.36
0.33
0.37 0.38 0.36
0.06 0.07 0.07 0.07
0.24
0.25 0.24 0.25
FFCMv1(Rd=10)
0.20 0.20
0.23
0.24
0.31
0.31
0.32
0.31
0.03 0.03 0.04
0.03
0.13
0.13
0.15 0.14
FFCMv2(Rd=1)
0.32 0.44 0.53
0.56
0.27
0.43
0.48 0.50
0.10 0.11 0.11 0.12
0.27
0.30
0.30 0.32
FFCMv2(Rd=10)
0.32 0.43 0.53
0.56
0.27
0.43
0.48 0.50
0.10 0.10
0.10
0.12
0.26
0.28 0.29 0.31
k-FED
0.28 0.41
0.47 0.51 0.30
0.39
0.47 0.52
0.10
0.22
0.34
0.48
0.27
0.37
0.49 0.62
FECA
0.61 0.60
0.58
0.57
0.53
0.51
0.49 0.50
0.37
0.37
0.37
0.34
0.49
0.49
0.49 0.47
Centralized
0.64
0.53
0.39
0.50
The test. accuracy is reported using linear evaluation, with the mean results of three runs presented in Table 3 Since each round of FFCM requires one communication between the server and clients, we only perform FFCM(Rd=1) given the computation resource constraint. And we set k' = 20 for k-FED on Tiny- ImageNet. We first confirm that the centralized training of DEEPCLUSTER-22 reaches reasonable accuracy on three datasets. Also, we see that the performance federated framework drops sharply compared centralized learning, showing the challenges of learning deep representation on decentralized data. One possible reason could be the limited performance of k-means clustering results on noisy features, especially in the early rounds, leading to unreliable pseudo labels in the following supervised training step.
However, our method shows encouraging improvements. The DEEPFECA outperforms the baselines signif- icantly and consistently across all settings on three datasets. From experiments, we demonstrate: (1) is challenging for applications DEEPCLUSTER-22 in federated settings to match its centralized performance; (2) it possible for current basclines to learn mcaningful features in foderated representation lcarning: (3) the proposed DEEPFECA serves as strong baseline, which oulperforms current algorithms by notable gain.
Table 3: Top-1 test accuracy (%) with linear evaluation. We present mean results from 3 runs on three datasets.
Accuracy (%)
CIFAR-10
CIFAR-100
Tmag-ImageNet
Method
IID (0.3) (0.1)
IID (0.3) (0.1) HID (0.3) (0.1)
M-Avg
53.6 48.2 45.1
25.2
24.8
23.6
16.4
15.1
13.5
FFCMv1(Rd=1)
44.6 48.5
45.5
22.5
25.0
25.9
12.1
16.9
12.5
FFCMv2(Rd=1)
47.7
50.1
49.1
21.9
22.9
22.9
14.9
14.1
14.0
k-FED()'=20
46.8
50.0
47.1
27.5
28.9
29.7
15.3
18.9
23.4
DEEPFECA
55.3 63.7 59.9
35.3
34.9
35.2
26.7
26.4
26.1
Centralized
80.9
50.1
36.6
13

---

Published in Transactions on Machine Learning Research (07/2024)
7 Conclusions and Future Works
We investigate federated clustering, important yet under-cxplored area in federated unsupervised learn- ing, and propose one-shot algorithm, FECA, by leveraging structures of local solutions in k-means. We also adopt FeCA for representation learning and propose DEEPFECA, Through comprehensive experiments on benchmark datascts, both FcCA and DecpFeCA demonstrate superior performance and robustness, out- performing established baselines across various settings.
Towards other challenging settings. Throughout the whole paper, we consider cither the infinite sample scenario (for theory) or the large sample scenario (for experiments), where a considerable large data sample size is still required for the local solution to have the desired structure. This corresponds to the cross-silo federated learning as introduced in the review paper Kairouz al. (2021), where the number of clients is limited but sufficient data is available on each client. The other pross-device federated learning setting, where limited data is available each client, can be adapted to tentatively mimic the cross-silo setting. One could group all the clients into a few groups to guarantee sufficient data samples in cach group, and then apply FedAvg McMahan et al. (017)) or other federated algorithm over the clients within each group, and at last deploy our federated k k-means algorithm on solutions returned by different groups.
Acknowledgments
J. Xu and Y. Zhang acknowledge support from the Department of Electrical and Computer Engineering Rutgers University. H.-Y. Chen and W.-L. Chao supported in part by grants from the National Science Foundation (IIS-2107077 and OAC-2112606) and Cisco Research.
References
Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self-labelling via simultancous clustering and representation learning. In TCLR, 2020.
Olivier Bachem, Mario Lucie, and Andreas Krause. Scalable k-means clustering via lightweight coresets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1119-1127, 2018.
F Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general topologies. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems. Curran Associates, Inc., 2013.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsu- pervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006.09% 2020.
You Chen and Wei-Lun Chao. Fedbe: Making bayesian model ensemble applicable to federated learning. In ICLR, 2021.
Yudong Chen, Dogyoon Song, Xunei Xi, and Yuqian Zhang. Local minima structures in gaussian mixture models. IEEE Transactions on Information Theory, 2024.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized foderated learning. 2021.
Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. arXiv preprint or Xic:2103. 200,00777,0 2021.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Ahmed Elhussein and Gamze Gürsoy.. Privacy-preservinc patient clustering for personalized federated learn- ings. In Machine Learning for Healtheare Conference, pp. 150-166. PMLR, 2023.
Limus Ericsson, Henry Gouk, and Timothy M Hospedales. How well do supervid models transfer? In CVPR, pp. 5414-5423, 2021.
Pasi Fränti and Sami Sieranoja. K-means properties on six clustering benchmark datasets, 2018, URL http://cs. uef. http:///es..ff..t/sspp// wtt..eee....s..pdaaaatttttttteee
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586-19597, 2020.
Andrey Goder and Vladimir Filkov. Consensus clustering algorithms: Comparison and refinement. In 2008 Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX), 109-117. SIAM, 2008.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv: 1910.. 1910.1422,, 2019.
Chaoyang He, Murali Annavaram, and Salman Avestimehr. Group knowledge transfer: Federated learning of large cmns at the edge. In NeurIPS, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Tom Hess, Ron Visbord, and Sivan Sabato. Fast distributed k-means with a small number of rounds. arXiv preprint Xrv:222001. 13217, 2022.
Jiazhen Hong, Wei Qian, Yudong Chen, and Yugian Zhang. A geometric approach to k-means. anXiv preprint arXiv:2201.048 2022.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint 1r0t:0999900335, 2019.
Eshref Januzaj, Hans-Peter Kriegel, and Martin Pfeifle. Dbde: Density based distributed clustering. In International Conference on Eztending Database Technology, pp. 88-105. Springer, 2004.
Wonyong Jeong, Jaehong Yoon, Eunho Yang, and Sung Ju Hwang, Federated semi-supervised learning with inter-client consistency disjoint learning. 2020.
Amelia Jinénez-Sánchezz Mickael Tardy, Miguel A González Ballester, Diana Mateus, and Gemma Piella. Memory-awan curriculum federated learning for breast cancer classification. Computer Methods and Programs in Biomedicine, 229:107318, 2023.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends@ in machine learning. 14(1-2):1-210, 2021.
Hillol Kargupta, Weiyun Huang, Krishnamoorthy Sivakumar, and Erik Johnson. Distributed clustering using collective principal component analysis. Knowledge and Information Systems, 3(4):422-444 448, 2001.
A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In AISTATS, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 2015.
Guangrui Li, Guoliang Kang, Yi Zhu, Yunchao Wei, and Yi Yang. Domain consensus clustering for uni- versal domain adaptation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 7767-9766, 2021.
15

---

Published in Transactions on Machine Learning Research (07/2024)
Songze Li, Sizai Hou, Baturalp Buyukates, and Salman Avestimchr. Secure federated clustering. preprinl or Xrv:22205. 15564, 2022.
anXiv
Yiwei Li, Shuai Wang, Chong- Chong-Yung Chi, and Tony QS Quek. Differentially private federated clustering over non-iid data. arXiv preprint 0tt:2300000055. 2023.
Tao Lin, Linging Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. In NewrIPS, 2020.
Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang. Self-supervised learning: Generative or contrastive. JEEE Transactions on Knowledge and Data Engineering, 2021.
Stuart Lloyd. Least squares quantization in pem. TEEE transactions on information theory, 28(2):129- 137, 1982.
Guodong Long, Ming Xie, Tao Shen, Tianyi Zhou, Xianzhi Wang, and Jing Jiang. Multi-center federated learning: clients clustering for better personalization. World Wide Web, 26(1):481-500, 2023.
Lin Lu, Yao Lin, Yuan Wen, Jinxiong Zhu, and Shengwu Xiong. Federated clustering for recognizing driving styles from private trajectories. Engineering Applications of Artsficial Intelligence, 118:105714, 2023.
Ekdeep Singh Lubana, Chi Tan Tang, Fahim Kawsar, Robert P Dick, and Akhil Mathur. Orchestra: Unsu- pervised federated learning via globally consistent clustering. Xiv preprint arXiv:2205.11506 2022.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Commmiictiion-fffiict learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp.
PMLR, 2017.
Stefano Monti, Pablo Tamayo, Jill Mesirov, and Todd Golub. Consensus clustering: a resampling- based method for class discovery and visualization of gene expression microarray data. Machine learning, 52((): 91 118, 2003.
Jaehoon Oh, Sangmook Kim, and Se- Young Yun. Fedbabu: Towards enhanced representation for federated image classification. arXie preprint arXiv:2106. 000:0006600642, 2021.
Wei Qian, Yuqian Zhang, and Yudong Chen. Structures of spurious local minima in k-means. IEEE Transactions on Information Theory, 68(1):395-4222 2021.
Cheng Qiao, Kenneth N Brown, Fan Zhang, and Zhihong Tian. Federated adaptive asynchronous clustering algorithm for wireless mesh networks. IEEE Transactions on Knowledge and Data Engineering, 2021.
Morris Stallmann and Anna Wilbik. Towards federated clustering: A lederated fuzzy c-means algorithm (ffem). arXiv preprint orXiv:2201.07 2022.
Yue Tan, Yixin Liu, Guodong Long, Jing Jiang, Qinghua Lu, and Chengqi Zhang, Federated learning non-iid graphs via structural knowledge sharing. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 9953-9961, 2023.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. Tn ICL.R, 2020.
Chang Xia, Jingyu Hua, Wei Tong, and Sheng Zhong. Distributed k-means clustering guaranteeing local differential privacy. Computers & Security, 90:101699, 2020.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Trong Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric foderated learning of neural networks. In ICML, 2019.
Dun Zeng, Siqi Liang, Xiangjing Hu, Hui Wang, and Zenglin Xu. Fedlab: A flexible foderated learning framework. Journal of Machine Learning Research, 24(100):1-7, 2023.
16

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Fengda Zhang, Kun Kuang, Long Chen, Zhaoyang You, Tao Shen, Jun Xiao, Yin Zhang, Chao Wu, Fei Wu, Yueting Zhuang, et al. Federated unsupervised representation learning. Prontiers of Information Technology & Electronic Engineering, 24(8):1181 1193, 2023a.
Jianqing Zhang, Yang Hua, Hao Wang, Tao Song, Zhengui Xue, Ruhui Ma, and Haibing Guan. Fedala: Adaptive local aggregation for personalized federated learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pp. 11237-11244, 2023b.
Zhengming Zhang, Yaoqing Yang, Zhewei Yao, Yujun Yan, Joseph E Gonzalez, and Michael W Mahoney, Improving supervied federated learning by reducing the gradient diversity of models. arXiv preprint 11364 2020.
Yanlin Zhou, George Pu, Xiyao Ma, Xiaolin Li, and Dapeng Wu. Distilled one-shot federated learning. arXiv preprint arXie:2009.07999 2020.
Weiming Zhuang, Xin Gan, Yonggang Wen, Shuai Zhang, and Shmai Yi. Collaborative unsupervised visual representation learning from decentralized data. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4912-492) 2021.
A Proof of Theorem 4.1
In this section, prove Theorem 4.1 Under the Stochastic Ball Model and high Signal-to-Noise Ratios (SNR) condition, will demonstrate: (1) all the clients returned onemmany-fi-oom centroids corresponding to the same ground truth center are bounded within ball of some radius (determined by Algorithm 3 (2) for the final output centroids C = fci....,co c from Algorithm [ the distance between any centroid c E C
s E [k]] and its corresponding true center is upper bounded. Specifically, the proof is composed of the following three steps:
Step 1 (Proof of the effectiveness of removing one-fit-many in Algorithm 2 On the client end, we prove the offectiveness of removing all onc-fit-many controids by Algorithm 2
Step 2 (Proof of the effectiveness of assigning radius in Algorithm 3 On the server end, we prove that the radius assigned by Algorithm 3 effectively encloses all the centroids (returned from the clients) associated with the same true center;
Step 3 (Proof of Theorem 4.1 On the server end, under the assumption that there does not exist any one-fit-many centroid (proved in Step 1), we first prove Algorithm 5 correctly classifies all the returned centroids C = {C (....,((MM from M clients using radii assigned by Algorithm 3 and then derive the error bound between recovered centroids and their associated ground truth centers.
For completeness, outline some notations used in the following proof and formal description of the Stochastic Ball Model below.
Stochastic Ball Model and Notations. Let or...., 8% E Rd represent h distinct true cluster conters, and fe be the density of a distribution with mean 93 for each s E [k]. We assume each data point x((m) e Rd of client m e [M] is sampled independently and uniformly from a mixture f of distributions (fs)ee()) with the density
[(x) - M - M(x).
(7)
The Stochastic Ball Model is the mixture f where cach ball component has density
fa(x) Vol(B,) 1 1x, (x), [k],
(8)
17

---

Published in Transactions on Machine Learning Research (07 (07/2024)
where IB, denotes ball component centered at 0 with radius In the context of the k-means problem, to identify a set of & centroids ((m) following objective:
(c(")) (m)) ,..,, (m)) on client m, we consider the goal as minimizing the
G(Clml) -N
N -NJ min (m) iE
(m)) c; |2 (x )drlm) (m))
min 1E(A)
(m) 12 (m)))))
(9)
The above objective function represents the infinito-sample limit of the objective following proof, we denote the objective G(Clm) in 99) on client m G(m), Given set of k centroids
client m. In the
Cim), we denote the associated Voronoi set as (v(m)) ...., v(m)), where D)(m) is the region consisting of all the points closer to (m) than any other centroid in Cim), Formally, for each j [k], we define
m = { : || - 1 1l2 I || (mm) 2l2, Al # j, [+]].
(10)
In addition, we define the maximum and minimum pairwise scparations between true centers {0])se(M) as
mas
max 10- 0g lll
and
Amin
min 10 -2-112-
(11)
A.1 Step 1 (Proof of the effectiveness of removing one-fit on-fiit-may in Algorithm 2
In this section, we prove the effectiveness of Algorithm 2 in eliminating all one-fit-many centroids under the
Stochastic Ball Model. Specifically, on each client m E [M], after applying Lloyd's algorithm, we obtain a set of centroids C(m)) ((m) is a non-degenerate local minimum that is not the global optimum, then it must contain both one-fit-many and many-fit centroids, discussed in subsection 3.1
Next, the algorithm identifies a candidate one-fit- centroid c.m)) E ((m) whose corresponding Voronoi set !!(T)) contains data points with the largest standard deviation of distances to c!m)). In this proof, with the infinite-sample limit, we derive the objective G!m) in Equation as
Glm)
(m)) 12f(2dd...
(12)
In addition, the algorithm pinpoints two candidate many-fit-one centroids (m) and ci from C(m), charac- terized by the minimal pairwise distance. Then we tentatively merge the respective Voronoi sets v/!") and v)(m) to form new region D)m) and subsequently obtain a corresponding centroid c.m) The objective G.m) in Equation is then calculated as
[ D(m))
||r c
(m)) (2f))dd where D/m) v(m) u up(m).
(13)
, (m)) are one-fit-many and many-fit-one centroids, re- spectively, Algorithm compares G!m) and G If c! 2 G) then c!"") is confirmed as one-fit-many centroid be removed, and (c(m), dmm) are many-fit-one centroids to be kept. This is proved in the following Lemma A.1
To Lest if these candidate centroids of (m) and (cp (m)
Lemma A.1. Under the Slochastic Bull Model, for some constants À 223 and 1 5, if
Aman 2 A and Amin Z 10mAk2 V VrAmaz:
(14)
then Algorithm eliminates all the one-fit-many centroids in local minimizer ((m) on client m.
Proof. If ((m) is non-degencrate local minimum that is not globally optimal on client m, then it must contain both one-fit-many and many-fit-one centroids. Without loss of generality, assume that cg (m) C(m)
18

---

Published in Transactions on Machine Learning Research (07/2024)
is associated with multiple true centers oi,.... 0f, where 2 2. Additionally, let (cem) :c cm)) C(m) (potentially along with other centroids) are associated with the same true center 0241. Then the objective G(m) of ((m) is
G(m) G(m)) + Ti B, where Ti Nymoo min min( 1 || (f))),
(15)
and Gfm) is defined in 12 B denotes the objective value contributed by the Voronoi set other than
(M(")) m) v( J.
We construct hypothetical solution cm by: (1) merging Voronoi sets v and vg into new region
D with the centroid c)m" (2) dividing the Voronoi set y!!) into two regions D (m)) and ((m) with new centroids (( and (m) respectively:
D E E v( || d1'll2 |x 2 (2))
D(m fo E v((m) -|1 -
c 1l2 s || c (m))
(3) keeping the remaining centroids in C(m). Thus, we have
c( h = c(m) \ (ep (m) olm) emm) ut (m) : .2 , cgg }.
(m) (m)
(16)
The objective (lm) for this hypothetical solution cl
(mm) = G.m + T2 B, where T3
Aam minl(l
o/ 112 || (
(x)))
(17)
and ((m) is defined in 13). By selecting centroids
(m) (m) and 022 arg max
#Ev(m) |
c. (m and
applying Lemma A.2. we have
2
((m) - -G(m)
(()))
min
(18)
36k
This inequality implies that ((m) is a local solution with a suboptimal objective value G(m), In Algorithm instead of comparing ((m) and G(m²) we evaluate G(m) and Gfm) to determine whether ((m) is local
solution. The difference between objective values ((m) and Gf is
((v))_ (()) ((m) G (T2 - (T).
(19)
Following the selection of centroids (() and c,2 as above, have the proved claim that [|c()")
(m)
0/2
(mm)
Amin r from the proof of Lemma A.2 in Hong et al. (2022). For the term T2, it follows that
T2 =
|| (m) (2)))xx
|| (m)) 1 (11a(()ddc
(20)
D(m)
D(m)
(I((m) (mm)
(111 1|2 111x--ee (1m) d1))l2)) f(x)dr
(21)
D(m)
Amin
r 2r f(x)dx
(22)
/y(m))
2
1
Min
3r
2
(23)
1
2
min
(24)
k
5
19

---

Published in Transactions on Machine Learning Research (07/2024)
Equation (20 follows from v((m) D
UD
(m)
Inequality (21) uses the triangle inequality, and 22 follows
from the choice of 11
(m) and C22
(m)) Inequality
23
stems from the ball component's volume being k Inequality
(24) follows the claim that r S 20
Amin.
which is derived from the separation assumption in 14
30
For the term Ti, we have
7
1 1ym)
|| - o (Tm) (1/ + [agm |1
d( (x)
(25)
L ((m)
[1 |1 + |10 - -m))ll)) f(x)dxx + I Lugn (12- 0it1ll2 + +100+11 (1x--6talle
dmilla) f(z)dx (26)
+AR2 Vr rmAmar)) f(x)dox 1 |yAm (r+ (r+8AA Vrev/e f(x)dr
(27)
-/pmm (r+ 8AR2 V (
f(x)dx= I (r+ 4Amin 5n
2
A min
2
(28)
3
Equation (55 follows from the definition of the term Ti. Inequality (26) follows from the triangle inequality.
Inequality [27 utilizes the error bound from Theorem (many/one-fit oon--ft-oon association) in Qian et al. (2021)
with each ball component's 's radius as r. Inequality (28) is based on the volume of each ball component being
I. the proved claim
- Amin and the assumption that 17 2 5.
k.
30
Combining the above inequalities, we have T2 - Ti 0. Thus, the equation
19
can be derived as
(m)) G! - -..m) G(m) - ) + (T2 TT)) (m))
Gh
(m)
min
0.
(29)
364
Therefore, if G (m)) 2 G.m)) it implies that ((m) is a local solution with a suboptimal objective value ((m)..
Subsequently, by comparing G( and (lm) for each candidate centroid (m)) Algorithm eliminates all one-fit me-fit-many centroids from C(m).
2 can effectively
Lemma A.2. Under the Stochastic Ball Model, for some constants 223 and n 1 5, if
A Amaz 4 and Amin 10nAK2 Vr
(30)
then when c(TT) = c.)
(m) and C2
(m) arg max mE || - (m))), the following holds:
A min
(mm) -G(m))
(m))
(31)
36k
Proof. The difference between objective values of the solution ((m) and the hypothetical solution ((()
((m) G(()) (G!m)) T2) - (G)m)) - Ti).
(32)
Lemma A.2 in Hong et al. 2002
establishes that by choosing centroids C = cim) and
(m)
(m)
arg max DEv(m) || c; [m)] ||, we have
2 min and - Ti -T
4
G!())
(33)
18k
k.
which follows from the volumes of the ball components under the Stochastic Ball Model, each equating to Then, we derive
I
k.
2 min
2r
Gim)
G((
>
mine
(34)
18k
k
36k
The second inequality in (34 follows the claim that < assumption in 330
A Amin <
Amm which is derived from the separation
20
20

---

Published in Transactions on Machine Learning Research (07 (074))
A.2 Step 2 (Proof of the radius assignment in Algorithm 3)
In this section, present theoretical analysis demonstrating the effectiveness of the radius assignment in Algorithm 8 ensuring coverage of all centroids associated with one true center. On one hand, following the removal of all one-fit-many centroids by Algorithm 2 (proved in step 1), all returned centroids C (c.),....ctt C(M} on the server end are concentrated around true centers {6) {.]]. Thus, this is equivalently another clustering problem on centroids C with (extremely) high SNR separation condition. Tet (Si...., St) be the ground truth clustering sets of all returned centroids C, where for each [K], centroids within S are all associated with the one true center 0% Algorithm 5 classifies these returned centroids C into k sets Se,,, using the radius in R {R(1), ..... R R(M) determined by Algorithm 3
On cach client E [M], Algorithm 3 first generates new set of centroids ((m) by discarding any potential many-fit-one centroid from C(m), then identifies the minimal pairwise distance Å (m) min in ((m) aiming
approximate Amin formulated as:
(m7) min
= min
| - èz1l2.
(35)
B. C.EjECim),jfs
(m) Subsequently, Algorithm calculates uniform radius ((m) 1 mini and assigns to every centroid in c(m), These centroid- pairs are then sent to the server. Lemma A.3. Under the Stochastic Ball Model, for some constant A 2 3 and 2 5, if
A Amax Ar and Amin 2 107Ak2 VrAmaz:
(36)
then for centroids in S which are associated with the true center 0% E [k], we have the following inequality holds on all clients m [M]:
1 (m) |1, cill2 S -
max e,yyS,
min
Vs E [k].
(37)
Proof. For centroids in S which are associated with one true center 02,8 E [ki], we upper bound their maximum pairwise distance using the triangle inequality:
max S.e
|ej cill2 - max (1ee - 02]12 + 110 -ill2)
< 2 max - 0/
|c--0; c.S.
(38)
Under the Stochastic Ball Model with radius r, we apply the error bound from Theorem 1 (mantoone-ii--onee
association) in Qian et al. 2021 to the above inequality, and for some constant À 2 3 we have
max 6.
||e - cill S 2 max ||c, - 0 S 16A12 2 Ammar.
(39)
(#)
c:S;
By combining the above inequality and the assumption Amin 10yAk2 v /rrmaa maz in 36
obtain
max [0 - call2 - G.ejESt,14
A minz
(40)
5n
where the constant 2 5. Next, we derive the approximation error between
A (m) min
and A Amin as:
A (m) min
Amiul S max ||c, - 0: + max ||cer - 83 122
[k]. s E [k) s' E [k], +
e,ES;
eyES"
2 max ||c, 0,11,
(41)
ES;
21

---

Published in Transactions on Machine Learning Research (07/2024)
Given that all clients follow the same mixture distributions under the Stochastic Ball Model, the above inequality holds for all clients m [M]. Similar to inequality (38) we again utilize the error bound from Theorem 1 imany/one-fitoon association) in Qian et al. 2022p, and obtain:
(m) min
minl
mini
Vm E [M].
(42)
5m)
Reorganizing the terms in inequality
42 gives
5m
(m)
A
5n
A (m) min
Vm E [M]]
(43)
min
5n
8
5n
Then by combining inequalities
40 and
43
for each [k:], we obtain
max EueyEE; 1
|ej
4 12
S
5n
8
min
(m)
2
(m) mön:
Vm E [M];
(44)
where the last inequality follows from the assumption that 17 2 5.
A.3 Proof of Theorem
In this section, complete the proof of our main theorem by demonstrating: (1) Algorithm correctly classifies all returned centroids in alignment with their corrosponding true centers, utilizing the radius as- signed by Algorithm 3 (2) we derive the error bound between the final output centroids C from Algorithm and the corresponding true centers.
Proof- Let cluster labels be ,. During the grouping process of all returned centroids the server end, Algorithm 5 first selects centroid in C with the largest radius. Without loss of generality, we assume that this selected centroid C, E C is returned by the client m and associated with the true center 02. Thus, this centroid belongs to the ground truth clustering set as c, E S; and its assigned radius is r, -. min- Algorithm 5 then groups the centroids located within the ball centered at c, with radius rs: resulting in the formation of the grouped cluster S, {c c C, 1|cl rr))
On one hand, Lemma A.3 implics that for each s E [k), the maximum pairwise distance between centroids [m]] in S bounded by 2 min definition of S,,
for any client m. Consequently, S E S, can be readily inferred based on the
On the other hand, for other centroids cr Sg s' E [k]] s + s', we have
||e/ cal12 2 110 0,112 ||.,- 0% ll2
||c, - 0,
A min |c.,' 071122 ||2 ||c, 0 11.
(45)
Utilizing the error bound from Theorem (many/one-fit-one association) in Qian et al. (2021) gives
8
||e coll2 2 Amin 16 Vr max
Amin
min:
(46)
5m)
where the last step follows from the assumption Amin 2 10mAR² to the above incquality, for any client m [M], it follows that
Vrr//rAaaaaa man- Applying the lower bound in (43
|c., - - 2
5n (m)
- A {mm) (m)
(47)
5n 8 min
2 min'
where the constant 77 2 5. Thus, following the definition of S,, the above inequality implies that centroids Ce' E S # s' do not belong S,, Combining the proved claim that S E S,, this suggests that S, = S [k], up to a permutation of chuster labels. This further implies that Algorithm correctly classifies all returned centroids in C according to their associated true centers.
22

---

Published in Transactions on Machine Learning Research (07 (07/2024)
For each [kc, Algorithm 5 computes the mean of Sz. denoted co mS) The collection of these mean centroids, C* = (G...... (.), constitutes the final set of centroids output by Algorithm 1 Then the proximity of c, to its associated true center 0r can be bounded as:
||c - 00'll2 I max ||c 0% I max ||c 0%112, Vs [K]
(48)
eES,
cES;
4
SAA Vrraar I
min-
(49)
517
for some constants v) 2 5. The inequality (48) follows from the proved statement S, = S E [k] The
inequality (49) first utilizes the error bound from Theorem (many/one-fit association) in QQan et al. (2021), followed by the application of the separation assumption Amin 2 10pAk? Vr Thus, any output centroid eg E C from Algorithm is close to some true center 0% as:
4 Amint
|1cg 1 S 5T)
(50)
thereby proving Theorem 4.1
B Evaluation on the radius assigned by Algorithm 4 (Empirical).
This section evaluates the radius produced by the empirical algorithm variant, Algorithm While the proof of our main theorem characterizes the performance of the Algorithm 3 is important to note that most real-world scenarios do not satisfy a homogeneous data sample assumption. Consequently, we have implemented an empirical procedure that assigns unique radius each returned centroid. In this context, it is also not necessary to remove many- nat centroids on clients, as these centroids typically concentrate around true centers and will be grouped together via the aggregation algorithm on the server. This empirical algorithm variant is specifically designed to adapt our main algorithm FECA for more general scenarios.
In this section, we empirically assess the radius assigned by Algorithm under both IID and non-lID scenarios, demonstrating its effectiveness for the proceoding aggregation step in Algorithm 5 Specifically, our objective is to empirically show that utilizing the selected centroid-radius pair (c,, rs).r)). [k] (assigned
by Algorithm 4 Algorithm can effectively group all returned centroids corresponding to the same true center 0, on the server end. Recall that we denote set of returned centroids associated with one true center 8 as S
Essentially, we aim to validate that the distance between any centroid c E S to c, is bounded by the assigned radius Ta- Our goal is thus formulated as follows:
||: call2 S r.. c.
max
(51)
The left side of the above inequality indicates the maximum distance between any two centroids in S and it can be further elaborated as
max c:
||q: colll <
max (1le, 0,112 110; csl1z) s 2 max ||e; - 0,
(52)
c,ES;
GES;
Then our goal in 51 can be reformulated as
||. 8illa
max CEE.
(53)
T.
2
Next, we present empirical results on the synthetic dataset, S-sets (S1), with known ground truth centers
[0])<e())- These results demonstrate that the incquality 53 holds across both IID and non-IID cases. For
this purpose, we define a new parameter a as
c 0:12 22
0
GES, SE [k].
(54)
Ts
23

---

Published in Transactions on Machine Learning Research (07 (07/2024)
This parameter ds represents the distance between the returned centroid c and its fitted true center 8 scaled by the radius rs. Our empirical results demonstrate that values of o; remain below 0.5 for all returned centroids in C = {c(1) C(M., }. in accordance with our goal inequality (53)
Results. Figure 5 illustrates the evaluation of d;, determined using the radius assigned by Algorithm in varied inhomogeneous settings on S-sets (S1). This figure presents values for all returned centroids across three random runs, categorized according to their respective true centers in different colors. Result consistently indicate that 0, values stay below 0.5, thereby empirically substantiating the validity of the inequality (53) our analysis. Consequently, demonstrates the efficacy of aggregating centroids using the radius assigned by Algorithm| 4 on the server end.
0.5
0.273
Sigma
0.211
0.202
0,177
0,146
0.158
0.153
0.146
0.138
0.153
0.145
0.153
0.156
0.153
0.111
0
Cluster
Cluster
Cluster 3
Cluster 4
Cluster
Cluster 6
Cluster
Cluster
Cluster Cluster
Cluster
11 Cluster 12 Cluster Cluster 14 Cluster 15
S-sets (S1) IID
0.5
0.434
00.49
0.410
*0.480
0.468
0.494
0.479
0,484
0,489
0.487
0,479
0.480
0.445 *
0.384
0.337
Sigma di
0
Cluster
Cluster
Cluster
Cluster 4
Cluster Cluster 6
Cluster
Cluster
Cluster Cluster Cluster 11 Claster Cluster Cluster 14 Cluster
S-sets (S1)
Dirichlet (0.3)
0.5
0,469
0.470
0.444
0.492
004887
0.495
0.477
0.491
0.497
0.452
0.479
0.472
0.435
0.493
Sigma 0z
Claster
Cluster
Cluster Cluster 4 Cluster Cluster 6
Cluster Cluster Cluster Cluster Cluster Cluster 12 Cluster Cluster Cluster 15 S-sets (S1) Dirichlet (0.1)
Figure 5: Evaluation of on S-sets (S1) across three data sample scenarios. σ; for k clusters is represented in different colors. The values of o, for all returned centroids a are reported over 3 random runs, with the red star marking the maximum o; observed in three runs. A a; value below 0.5 indicates that, the server effectively groups centroid e, utilizing the radius re assigned by Algorithm
24

---

Published in Transactions on Machine Learning Research (07/2024)
We note that the number of returned centroids associated with each true center may vary. It is because selectively remove one-fit-many centroids on the client side, while it is possible for many-fit-one centroids to be present. In some extreme non-llD cases, assuming a client only contains a few secluded data points from one true cluster but they all far deviate from the true center, it may occur that a returned centroid is not covered by the radius. Then will be considered noisy and discarded by Algorithm 5 Concretely, the recovered centroids of this cluster will be contributed by returned centroids from other clients.
C Supplementary experiments on the synthetic dataset
This section presents additional experimental results on the synthetic dataset S-sets Franti & Sieranoja (0018). The S-sets comprise four sels: S1, S2, S3, and S4, each consisting of 15 Gaussian clusters in dimensional data with varying degrees of overlap, specifically 9%, 22%, 41%, and 44%. For the visualization of S-scts, refer to Figure 6 from their paper Fränti & Sicranoja (2018).
S
S2
S
S
Figure 6: Visualizations of S-scts.
C.1 Evaluations on the clustering assignments
This section shifts focus the evaluation of clustering assignments on the synthetic dataset S-sets, diverging from the analysis of recovered centroids. While Table 1 in the paper assesses the fg-distance between recovered centroids and known ground truth centers, we herein present the average results of Purity and
Table 4: Purity and NMI on S-sets under three data sample scenarios.
Purity
S-scts (S1)
S-scts (S2)
S-scts (S3)
S-scts (S4)
Method
IID (0.3) (0.1)
IID (0.3) (0.1)
IID (0.3)
(0.1)
IID (0.3) (0.1)
M-Avg
0.99
0.79
0.69
0.93
0.74
0.68
0.80
0.66
0.61
0.75
0.64
0.57
FFCMv1 (Rd=1)
0.97
0.69
0.66
0.95
0.68
0.58
0.83
0.60
0.54
0.79
0.60
0.53
FFCMv1 (Rd=10)
0.98
0.78
0.68
0.96
0.74
0.71
0.85
0.66
0.37
0.80
0.61
0.55
FFCMv2 (Rd=1)
0.95
0.69
0.66
0.95
0.63
0.61
0.83
0.58
0.52
0.78
0.57
0.54
FFCMv2 (Rd=10)
0.99 0.80
0.76
0.97
0.70
0.72
0.86
0.65
0.61
0.80
0.60
0.59
&-FDD (k==5)
0.62
0.76
0.75
0.60
0.71
0.71
0.55
0.61
0.60
0.55
0.62
0.58
FECA
0.99 0.98
0.96
0.97
0.95
0.90
0.86
0.80
0.78
0.80
0.73 0.65
Centralized
0.97
0.96
0.83
0.77
NMI
S-scts (S1)
S-scts (S2)
S-scts (S3)
S-scts (S4)
Method
IID
(0.3) (0.1)
IID
(0.3) (0.1)
ITD
(0.3)
(0.1)
IID
(0.3)
(0.1)
M-Avg
0.98
0.85
0.79
0.92
0.80
0.78
0.77
0.71
0.69
0.70
0.65
0.62
FFCMy1 (Rd=1)
0.98
0.80
0.78
0.93
0.77
0.71
0.78
0.67
0.64
0.72
0.63
0.60
FFCMv1 (Rd=10)
0.98
0.85
0.80
0.94
0.80
0.78
0.79
0.71
0.66
0.72
0.64
0.61
FFCMv2 (Rd=1)
0.97
0.80
0.78
0.93
0.75
0.72
0.78
0.67
0.63
0.71
0.62
0.60
FFCMv2 (Rd=10)
0.99
0.87
0.85
0.95
0.78
0.79
0.79
0.70
0.68
0.72
0.63
0.63
&-FD (k'=5)
0.80 0.84
0.83
0.75
0.80
0.80
0.66
0.69
0.68
0.62
0.65
0.63
FECA
0.99 0.96
0.95
0.95
0.94
0.90
0.80
0.77
0.75
0.72
0.69
0.66
Contralised
0.98
0.94
0.79
0.71
25

---

Published in Transactions on Machine Learning Research (07/2024)
NMI across 10 random runs in Table under three different data sample scenarios. The findings consistently demonst.raee that our algorithm FECA surpasses all baseline algorithms in performance across every tested scenario, underlining its effectiveness in federated clustering tasks.
C.2 More visualizations of recovered centroids by different methods on S-sets
To further demonstrate the superior performance of our algorithm, we present more visualizations corre- sponding to the results detailed in Table 1 for S-sets(S2) and S-sets(S3). Figure 7 displays the centroids recovered by various federated clustering algorithms under the non-ITD condition (0r3chlet(0.3). Our al- gorithm's ability to resolve and leverage the structures of local solutions enables it to outperform other baseline methods that fail to address these critical aspects, especially in challenging non-IID settings. This emphasizes the critical role resolving local solutions for enhanced algorithmic performance.
S-sets (82)
M-Avg
FFCMv1(Rd
FRCMy1(RR-10) FFCMv2(R(-1) FFCMv2(Rd-10)
k-FED (K--5)
FeCA
S-ects (S3)
M-Avg
IRCMV)(Rd=I) FFCMv1(Rd=10) FFCMv2(Rd=1) FFCMv2(Rd=10) k-FED (k'=5)
FeCA
Figure 7: Visualizations of S-sets (S2&S3) and recovered centroids by different methods. Results are showcased under the (Orichlet(O.3) data sample scenario. Blue dots represent recovered centroids, and red crosses indicate the ground truth centers.
C.3 Ablation study on eliminating one-fit fit- tae-fit-many centroids Algorithm
Removing aae-fit-many centroids Algorithm 2 plays a crucial role enhancing the algorithm's perfor- mance. These centroids are typically far from any true centers. By climinating ono-fit-many controids at the client end, we effectively prevent the transmission of these problematic centroids to the server. It significantly simplifies the task of Algorithm 5 on the server side, which involves grouping received centroids close to the same true center.
In this section, we conduct an ablation study on eliminating one-fit-many centroids in Algorithm 2 In the following experiments, one-fit-many centroids are not removed on clients and then sent to the server. We present mean square errors between recovered centroids and ground truth centers in Table 5) The comparative results clcarly demonstrate a performance degradation when these centroids are not removed, underscoring the significance of eliminating the one-fit-many step in Algorithm 2
Table Mean square errors between recovered centroids and true centers on S-sets(S1) under IID data sample scenario. Values of MSE are scaled by 106, We report mean results from random runs.
Method
MSE x00
FECA (not removing one-fit-many centroids) FECA (removing one-fit-many centroids)
12977.2
6.7
Not enough output centroids. Not removing one-fit-many centroids can lead to scenario where the number of reconstructed centroids is less than k. This occurs because the cluster of one-fil-many centroid typically contains data points from multiple true clusters, resulting in a significantly larger radius than that assigned to the true cluster. Consequently, the server may prioritize these centroids with large radii during the grouping process, forming a large group erroncously containing centroids associated with different true centers. In Figure provide visualizations of reconstructed centroids woth removing one-fit-many,
26

---

Published in Transactions on Machine Learning Research (07/2024)
demonstrating notable decrease in performance. This emphasizes the necessity of their removal in algorithm.
output 13 centroids
output 14 centroids
output 14 centroids
output 15 centroids
Figure 8: Visualizations of recovered centroids by FeCA (not removing one-fit-many centroids).
Results showcased under the IID condition S-sets(S1) with k- 15. Blue dots represent recovered centroids, and red crosses indicate the ground truth centers.
C.4 Comparison between Algorithm 3 (theoretical) and Algorithm (empirical)
Algorithm (theoretical) is designed for theoretical analysis only under a strict setup, specifically the Stochastic Ball Model assumption. This assumption allows for the straightforward identification and re- moval of many-fit-one centroids. However, practical scenarios, climinating many-fit-on is challenging and unnecessary, as they often carry crucial information about the global solution.
In this section, we explore the applicability of Algorithm (theoretical) beyond its constraints by conducting experiments on S-sets under various heterogencous conditions. Table G presents results, revealing that the performance of Algorithm 3 is suboptimal when assumptions of Stochastic Ball Model are not met, particularly in non-lID cases. This suboptimal performance is due to its reliance on specific assumptions for identifying many-fit-one centroids. Consequently, in practical scenarios, this approach may erroneously eliminate true centroids, leading less effective outcomes.
Table 6: ly-distance (mean=std) between recovered centroids and true centers on S-sets(S) under different data sample scenarios. Values fa-distance are scaled by 10a
Method
IID
(0.3)
(0.1)
FECA (theoretical) 1.1 #0.1 31.8 + 23.8
58.9 + 15.1
FECA (empirical)
1.0+0.1
6.8
22.3+15.6
C.5 Tuning N for k-FED the synthetic dataset
In this section, we provide the results of experiments conducted to select k' for k-FED Dennis et al. on the synthetic dataset. Given that all four subsets of S-sets have the same number of true clusters here we utilize S-scts(S1) for tuning V', which has the largest degroe of scparation. This choice is based on the separation condition mentioned in their paper. We present the fg-distance between recovered centroids and true centers for K' values ranging from 2 to 15. And results (mean=std) from 10 random runs are reported in Table 7. Additionally, we evaluate clustering assignments generated from the recovered centroids using Purity and NMI metrics. The mean results from 10 random runs are included in Tabll
2001
15,
Considering f-FED is designed for heterogeneous cases, we adopt a Dirichlet(O.3) data sample scenario in our experiments. It is also important note that when k' k*, the aggregation step the k-FED algorithm essentially becomes redundant, and the recovered centroids are equivalent the set of centroids returned by randomly chosen client.
27

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Table fz-distance (meantstd) between recovered centroids and true centers, Purity, and NMI on S-scts(S1) under (Or3chlctt data sample sccnario. Values of ég-distance are scaled by 10*.
&-FED
k' =
k' =
k' =
==5
k' =
=
W
22-dittance
63.317.0
65.9111.9
60.8116.8
58.1110.7
60.31
59.4111.1
62.5+11.0
Purity
0.71
0.72
0.79
0.79
0.78
0.79
0.76
NMI
0.83
0.83
0.89
0.88
0.87
0.88
0.87
&-ED
k/ =
I' 10
M 11
k' 12
V = 13
k' 14
k' = 15
Ei-distance
77.3111.2
69.4113.88
77.7.15.2
76.4.110.7
72.1
69.8 115.7
67.419.5
Purity
0.72
0.74
0.71
0.72
0.74
0.75
0.78
NMI
0.83
0.84
0.83
0.85
0.85
0.86
0.85
12-distance
Purity NMI
c0
1.00
k'=4
k==5
k'=5
0.0
k'
k'
Figure 9: Illustrations of l--distance means, Purity and NMI detailed in Table 7
C.6 Presence of local solutions in k-means
In this section, we perform centralized k- k-means on 50,, 75%, and 100% of data from S-sets. In Figure 10 we illustrate objective values calculated as Equation I] using 10 random seeds. As depicted, Lloyd's algorithm frequently converges local solutions with objective values significantly larger than that of global solutions. This empirical result. demonstrates the presence of local solutions with poor performance is independent of the data sample size. Also, it highlights the necessity of our algorithm, which is specifically designed to address and resolve these suboptimal local solutions.
S-eets (S1)
S-sets (S2)
S-sets (S3)
(S4)
100%
75% 80%
Objective Values
200-1
1
10 seeds
10 seeds
scods
10 seeds
Figure 10: Objective values of centralized k-means using 100%, 75%, and 50% of data from S-sets.
To better understand the structures of local solutions, visualize some local solutions of centralized k- means on S-sets, shown in Figure 11] This visualization reveals that despite variations in data separations, spurious local solutions exhibit structures as discussed in [subsection 3.I. containing both one-fit-many and many-fit-one roids This emphasizes the necessity of the steps in our algorithm that discard one-fit-many and aggregate many-fit-one centroids.
Almost-empty cases. As outlined in Qian et al. (2021), local solutions of k-means can be composed of one mee/many-fit-one, one-fit-many and almost-empty centroids. The first two have been discussed in detail
28

---

Published in Transactions on Machine Learning Research (07/2024)
Local Solutions of Centralized k-means on S-sets
S2
94
Figure 11: Visualizations of structured local solutions of centralized k-means on S-sets.
in subsection 3.1
Addressing almost-empty cases involves identifying centroids that are far from any true centers and its cluster is almost empty with small mcasure. This typically occurs when the dataset contains isolated points that are significantly far from the true centers. It is worth noting that almost-emply cases are more theoretical than practical, with rare occurrences empirical experiments.
However, if such a case does occur, our algorithm can handle Centroids from almost-emply clusters be treated noisy data and discarded during the grouping process. Since they distant from true centers and other received centroids, they do not contribute meaningfully to the final grouping.
the aggregation step by Algorithm
D Discussion on varying numbers of clients
In this section, we explore the impact of varying client numbers on our federated approach. We conduct ex- periments by allocating fixed dataset portion (5% randomly sampled from the entire dataset) to each client and then perform algorithm FECA across varying numbers of clients. We first evaluate the recovered centroids by calculating fz-distance between these centroids and the ground truth centers. Subsequently, we apply a one-step Lloyd's algorithm using the recovered centroids for initialization and then evaluate the clustering assignments by calculating Purity and NMI. Results for the S-sets (S1) are presented in Table It noteworthy that only centralized k-means clustering is performed when the number of clients is one. In such cases, cantralized k-means often results large fz-distance due convergence to local optima with suboptimal performance.
The findings presented in Table are visually depicted in Figure 12 (left), where trend of decreasing fz-distance is observed as the number of clients M increases. This trend indicates that collaboration among multiple clients can significantly mitigate the negative impact of local solutions. Specifically, when client encounters a local minimum, integrating benign results from other clients can help alleviate this issue. This collaborative mechanism underscores the effectiveness federated approaches improving performance by leveraging the distributed nature of client contributions.
Additionally, assess the impact of varying client numbers in standard federated setting, particularly under IID data sample scenario for S-sets(S1). In the following experiments, with A denoting the number of clients, cach client is allocated M of the data points from S-scts(S1). We note that contralized k-mcans is performed when M = 1 on the entire dataset. We evaluate the performance of our algorithm FECA by reporting the ly-distance between recovered centroids and true centers, alongside the Purity and NMI of clustering assignments, detailed in Table 9 Morcover, Figure 12 (right) features visual representations of the le distance results, emphasizing the robustness of our federated algorithm FECA across varying numbers of clients.
29

---

Published in Transactions on Machine Learning Research (07/2024)
Table 8: fz-distance (meantstd) between recovered centroids and true centers, Purity, and NMI with different numbers of clients M. Values of fz-distance are scaled by 10 Each client possesses 5% data of (-1)
FECA
M ==1-
=
M 3
M =
M =
=
=
M= =
M = 9
M = 10
fg-distance
10.7:14.3
3,140.6
2.610.4
2.140.3
2.040.3
1.7.0.3
18400.
1.640.4
1.410.2
1.400.3
Purity
0.98
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
NMI
0.98
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
FECA
M == 11
M = 12
M = 13
M
14
M
15
M
16
M 17
M = 18
M 19
M 20
fg-distance
1.320.2
1.40.3
1.340.2
1.40..2
1.240.2
1.240.1
1.100.1
1.1-0.1
1.010.1
1.0::0.1
Purity 0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
NMI
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
Table 9: fz-distance (meantsttd) between recovered centroids and true centers, Purity, and NMI with different numbers of clients M. Values of lz-distance are scaled by 10a. Each client possesses M data of (S))
FECA
M = M=
M =
= 4
=
M
=
M =
M =9
9.
M = 10
Eg-distance
14.3118.7
1,140.3
1.240.3
1.140.2
1.100.2
1.40..
1110.1
1.100.1
1.040.1
1.0:0.11
Purity
0.97
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
NMI
0.98
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
FECA
M ==ll 11
M = 12
M = 13
M
14
M 15
M
16
M 17
M = 18
M 19
M 20
f2-distance
1.1:0.1
1.140.1
1.140.2
1.140.1
1.100.1
1.0:0.2
1.100.2
1.1-0.1
1.1:0.1
1.1:0.11
Purity
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
NMI
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
Each client has 5% data of S-sets (SI)
Each client has data of S-scts (S1)
Contralized k-means
Centralized k-means
L2 -diitttece (x10*)
(M=1)
22-distance (x10*)
(M=1)
10
20
Number of Clients M
Number of Clients M
Figure 12: Illustrations of fg-distance in Table and Table 9
E
Discussion on varying k
The selection of le an important aspoct of the k-mcans problem. In this section, we present supplementary experiments investigating the performance of our algorithu with varying k. For clarity, in this study, we use k to denote the number of recovered centroids desired by algorithm, which is also the mumber of output centroids by Algorithm 1 k' denotes the parameter used to perform k-means clustering on clients in Algorithm 2 while An' indicates the number of true centers. In the following, we present experiments with varying values of K' and k, respectively.
Varying values of K'. We perform FECA on S-scts(S1) under three data sample scenarios, varying values of k. We chose K' 10 (undershoot case) and k' 20 (overshoot case) with k* 15. Mean square errors between recovered centroids and ground truth centers are shown in Table 10 Note that for undershoot cases,
30

---

Published in Transactions on Machine Learning Research (07/2024)
the number of recovered centroids might be less than k" In these instances, we identify the top l matching centroids with recovered centroids from k* true centers and calculate the mean square error between them. Visualizations of clustering results on different clients and FECA's 's recovered centroids are illustrated in the following figures.
Table 10: Mean square errors between recovered centroids and true centers on S-sets(S1) under three data sample scenarios. Values of MSE are scaled by 10 Dirichlet and Dirichlet are denoted as (0.3) and (0.1), respectively. We report mean results from 10 random runs.
Methods
k'
MSE IID
MSE (0.3)
MSE (0.1)
FRCA- Varying K (undershoot case)
15
10
15
34599.4
21055.7
19311.6
FRCA- Varying V (overshoot case)
15
20
15
9.9
5960.4
8738.6
РECA- Varying
10
15
8.4
551.2
7532.7
FECA
15
6.7
308.3
3315.3
When A + kt, even if clients converge to the global solution, this global solution exhibits similar structures (one-fit many and many-fit-one) to those observed in local solutions when k' = k" As shown in Figure 13, when = 10, clients' clustering results demonstrate the presence of onc-fit-many, while k' = 20 showcases many-fit-one structures illustrated in Figure 15, Therefore, this underscores the necessity our algorithm, as it effectively addresses such structured solutions.
In the undershoot case (K' 10 k*), clients' clustering results might contain multiple one-fit-many but no many-fit-one centroids. This complicates the elimination of one-fit-many centroids in Algorithm 2 because identifying one-fit-many becomes challenging without many-fit-one centroids for reference. Under non-IID conditions, this might occur in extreme undershoot cases with rather small k', as clients' data may concentrate on partial true clusters. As discussed in subsection C.3 if man-fit-aany centroids are not eliminated on clients, the number output centroids & may be less than k", shown in Figure 13.
In contrast, in the overshoot case (k' 20 k*); the clients' clustering results include multiple many-fit-one centroids but no one-fit-many many centroids. Since algorithm effectively addresses many-fit-nne centroids in the aggregation step the server, FECA can still accurately approximate the true centers, demonstrated in Figure 15 This is becanse the climination of many-fit-one centroids on the clients' side is unnecossary; these centroids can contribute meaningfully to the grouping process on the server side, as discussed in subsection 4.2
Varying values of k. We perform FECA on S-sets(S1) under three data sample scenarios, selecting M = k 15, and k 10. Mean square errors between recovered centroids and ground truth centers are reported in Table 10 When & < k", Algorithm (araimmjouuuuutt [ooupuus the mean centroids of the top & groups containing the largest number of elements. As illustrated in Figure 17 and Figure 18 with & k*, the recovered centroids can still accurately approximate partial true centers.
31

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Clustering results on different clients when k' 10.
Recovered centroids when = k 15.
output centroids
output 10 centroids
output centroids
output centroids
Figure 13: Clients' clustering results and FeCA's outputs under IID condition.
Clustering results on different clients when k' = 10.
Recovered centroids when k k* 15.
output 12 centroids
output 13 centroids
output 14 centroids
output 15 centroids
Figure 14: Clients' clustering results and FeCA's outputs under non-lID condition (0.3).
32

---

Published in Transactions on Machine Learning Research (07 (07/2
Clustering results on different clients when k' = 20.
Recovered centroids when = kt 15.
output centroids
output 15 centroids
output 15 controids
output centroids
Figure 15: Clients' clustering results and FeCA's outputs under IID condition.
Clustering results on different clients when k' = 20.
Recovered centroids when k k.' 15.
output 15 centroids
output 15 controids
output 15 centroids
output 15 centroids
Figure 16: Clients' clustering results and FeCA's outputs under non-lID condition (0.3).
33

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Clustering results on different clients when k' = k" 15.
Recovered centroids when 10.
output 10 centroids
output 10 centroids
output 10 centroids
output 10 centroids
Figure 17: Clients' clustering results and FeCA's outputs under IID condition.
Clustering results on different clients when k' = k* 15.
Recovered centroids when = 10.
output 10 centroids
output 10 centroids
output 10 centroids
output 10 centroids
Figure 18: Clients' clustering results and FeCA's outputs under non-lID condition -0.3).
34


Reviews:
[{"review_id": "AgpSatYJE8", "reviewer": "Reviewer_GuQL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n+ Unsupervised learning, in general, and clustering methods in particular have been less explored in the research literature on federated learning. In this sense, the authors tackle an interesting problem, proposing an algorithm capable of learning the centroids in one shot. Overall, the algorithm is reasonable and the extension for unsupervised feature learning with DeepCluster is a nice addition to the paper. \n+ The experimental evaluation with synthetic and real datasets is convincing and show a notable improvement with respect to previous state-of-the-art techniques. \n+ The authors strived to provide some theoretical analysis on some aspects of the proposed method. \n\n\nWeaknesses:\n+ Although, overall, the algorithms seem reasonable, the motivation and justification of some of them is not very clear and, in my opinion, the narrative of the paper could be improved and there are aspects that require some clarification. \n\n\nComments: \n+ In Section 3.1 the definition of the cases needs to be more rigorous. For example, what mapping means here? What does it mean that a centroid is mapped to s true centers? The intuition is provided with the figures, but a more formal definition is required. \n+ The description of Algorithm 2 is a bit unclear and needs a bit of context. For example, this algorithm usually returns a smaller number of clusters than k, because of the merging and elimination of centroids. This elimination of centroids can have a negative impact on the local solution. However, when reading Section 4.3 (the server aggregation algorithm), the reader can realize that this is not a problem and the global solution returns k clusters. Then, I think it would be convenient to provide more context and clarity throughout the Section 4 to understand better the flow of the algorithms in the clients and the server. This would make the paper more readable. \nthe one being removed) chosen at random, can help to alleviate the problem. \n+ Similarly, Lemma A.1 shows that Algorithm 2 eliminates one-fit-many centroids, but whether the solution after removal of these centroids improves upon the existing solution is unclear. It would be convenient to clarify the message that the authors want to convey there. \n+ The justification about why the algorithm works well in scenarios with data heterogeneity is not well supported. In this sense, Algorithm 5 (aggregation of the centroids) is not well justified and discussed. \n+ In Algorithm 5, what happens if n < k?\n+ In the experiments it looks a bit odd to report the average and the standard deviation in different tables (Table 1 and Table 4).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a novel federated clustering algorithm, FECA (Federated Centroid Aggregation), based on K-Means. First, the algorithm refines the centroids computed with K-Means locally, removing and grouping certain types of centroids. Then, the server is capable of aggregating the centroids in a single training round, i.e., FECA is a one-shot algorithm. Then, the authors also propose an extended algorithm that combines FECA with DeepCluster for unsupervised feature learning with federated learning. The experimental evaluation shows notable improvements with respect to other federated clustering methods in scenarios with varying degree of data heterogeneity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See my comments above. Overall, I think that the paper makes some nice contributions, but it would be necessary to make an effort to improve the readability of the paper and to motivate and justify a bit better some of the choices made for the algorithms.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YLT5gjB7OO", "reviewer": "Reviewer_mSnm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper's structure is well organized. It is intuitive and easy to follow (only few parts seem to be confusing to me; see later). \n- The authors provide many empirical results: on synthetic dataset FeCA (with Dirichlet-type of heterogeneity simulations) outperforms several benchmarks in all cases significantly. Besides, provided visualizations clearly show that FeCA finds really good approximations of ground truth centroids. The algorithm seems to handle Non-IID case as well. \n- The authors provide convergence guarantees under Stochastic Ball Model showing that under curtains conditions between ground truth centroids and number of clusters k.\n- Proposed algorithm is FL-friendly, i.e. it requires one time connection with the server. DeepFeCA follows the style of of FedAvg that also makes it FL-applicable. \n- The proofs seem to be correct to me and well written. \n\nWeaknesses:\n\n- The proposed algorithm hugely relies on the interaction between local and global solutions. There is a lack of discussion on this in the paper. It is not clear if this kind of structure holds for real world applications where Stochastic Ball or Gaussian Mixture models. Adding a discussion on this would improve the paper.\n\n- Theoretical algorithm is created to remove all one-fit-many local centroids. However, then the authors claim that is not necessary to do and provide empirical version. This confuses me a lot. Especially considering the convergence guarantees for theoretical version. Why shouldn't it work in practice? I believe adding discussion on this with potential practical comparison would strength the paper. If the authors could also provide examples when theoretical version works and fails, it would be also great. \n\n- Under Stochastic Ball model there can also be almost-empty case which is not discussed in the paper while it sounds logical to me in FL case (e.g., client has small portions of each cluster and is not able to recover any of centroids locally, so all local centroids are from true).\n\n- There is no theoretical explanation behind good performance in practice of two empirical versions of the algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes FeCA algorithm which is a one-shot k-means-type algorithm for Federated Clustering. The algorithm is based on the structure of local solutions (one-fit-many, many-fit-one [Qian et. al, 2021]). The theoretical algorithm in the first step removes all one-fit-many centroids from local solutions based on local datasets. Then it performs radius assigning process locally on each dataset, and finally the server aggregates all this information from the clients (many-fit-one local centroids and assigned radii) to obtain global set of centroids. The authors propose convergence guarantees under Stochastic Ball Model for theoretical algorithm. Besides, they propose two empirical versions that are then tested on synthetic and Deep Learning experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Notation $\\mathcal{D}^{(m)}$ for clusters is a little bit confusing as one can think about it as local dataset $\\mathcal{D}^m$. Is it common notation to use? If not, I would encourage to use maybe $\\mathcal{C}^m$ for clusters. \n\n- Discussion on the structure of local and global solutions is needed. When is Stochastic Ball or Gaussian Mixture models are relevant and when they are not. The case of almost-empty should be also discussed. Can we observe it in some extreme practical cases?\n\n- The discussion on why we need empirical version and why theoretical fails is needed. It would be good to have empirical comparison between then and examples when theoretical version works and fails. \n\n- The authors should specify that the proof of theoretical version is given in infinite-n case. How large n should be?\n\n- It would interesting to know the effect of choosing k in FeCA: when we overshoot it and undershoot. Is FeCA robust to this choice (e.g., if we overshoot k, will some centroids be close to each other meaning that k should be decreased?). I think it is one the most interesting questions for k-means-type algorithms.\n\nOverall, I enjoyed reading this paper even though never worked on k-means algorithms. The paper's results are interesting for TMLR readers, and the requested changes would improve the paper further.", "broader_impact_concerns": "No ethical concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "W6Av4Z8Ago", "reviewer": "Reviewer_puDn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strong aspects\n\n#### Strength 1: Theoretical Guarantee\nIn Theorem 4.1, the authors theoretically demonstrated that under the assumption that the data follows the Stochastic Ball Model and each cluster is sufficiently separated, the proposed method FeCA can estimate true cluster centers with small errors.\n\n#### Strength 2: Impact of Results\nThrough experiments using artificial data S-sets and CIFAR-10/100, the authors demonstrated that the proposed method FeCA outperforms existing methods (M-Avg, k-FED, FFCM).\n\n### Weak aspects\n\n#### Weakness: Assumption Strength\nIn Theorem 4.1, the authors assumed that all clusters have the same radius under the Stochastic Ball Model, and that each cluster is sufficiently separated.\nAdditionally, while not explicitly stated in the theorem, the proof assumes the limit as the number of data points $n \\to \\infty$.\nUnfortunately, the paper lacks discussion on whether these assumptions are reasonable for distributed k-means.\nFor instance, if assuming $n \\to \\infty$ is valid, obtaining sufficiently good clustering results by executing k-means in each local environment might suffice.\nIn this case, what is the purpose of executing k-means in a distributed environment?\nMoreover, the Stochastic Ball Model assumes that all clusters have the same radius, which will not be the case in most of real-world data.\nIt seems essential to discuss the validity of these assumptions and the robustness of the proposed method's dependency on these assumptions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors proposed a k-means algorithm for distributed environments.\nThey focused on the observation that the results of k-means exhibit a structure of either one-fit-many or many-fit-one, and propose a three-step algorithm. \nIn the first step, k-means is executed in each local environment and one-fit-many clusters are removed.\nIn the second step, adjacent clusters are merged in each local environment, and the radius of each cluster is estimated.\nFinally, in the third stage, clusters collected from each local environment are integrated to form the final clustering result.\nThe authors theoretically demonstrated that under the assumption that the data follows the Stochastic Ball Model and each cluster is sufficiently separated, the proposed method FeCA can estimate true cluster centers with small errors.\nFurthermore, the authors also proposed DeepFeCA, which combines FeCA with DNN to sequentially execute feature extractor learning and k-means in a distributed environment.\nIn experiments, the authors demonstrated that the proposed method outperforms existing methods (M-Avg, k-FED, FFCM).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness above.", "broader_impact_concerns": "There is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall this paper presents an interesting and effective method for one-shot federated clustering, which would be of interest to the TMLR community. I recommend that the paper be accepted assuming that the revisions discussed above are addressed (i.e., restructuring the paper to discuss the key assumptions earlier on and in more detail, and adding experiments with heterogeneous data to Appendix E).
Decision: Accept (poster)