Structured Federated Learning through Clustered Additive Modeling
Authors: Jie Ma
Tianyi Zhou
Guodong Long
Jing Jiang
Chengqi Zhang
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning

Abstract: Heterogeneous federated learning without assuming any structure is challenging due to the conflicts among non-identical data distributions of clients. In practice, clients often comprise near-homogeneous clusters so training a server-side model per cluster mitigates the conflicts. However, FL with client clustering often suffers from “clustering collapse'', i.e., one cluster's model excels on increasing clients, and reduces to single-model FL. Moreover, cluster-wise models hinder knowledge sharing between clusters and each model depends on fewer clients. Furthermore, the static clustering assumption on data may not hold for dynamically changing models, which are sensitive to cluster imbalance/initialization or outliers. To address these challenges, we propose ''Clustered Additive Modeling  (CAM)'', which applies a globally shared model $\Theta_g$ on top of the cluster-wise models $\Theta_{1:K}$, i.e., $y=h(x;\Theta_g)+f(x;\Theta_k)$ for clients of cluster-$k$. The global model captures the features shared by all clusters so $\Theta_{1:K}$ are enforced to focus on the difference among clusters. To train CAM, we develop a novel Fed-CAM algorithm that alternates between client clustering and training global/cluster models to predict the residual of each other.  We can easily modify any existing clustered FL methods by CAM and significantly improve their performance without ‘’clustering collapse'' in different non-IID settings. We also provide a convergence analysis of Fed-CAM algorithm.

Structured Federated Learning through Clustered Additive Modeling
Jie MA Tianyi Zhou², Guodong Long', .Jing Jiang', Chengqi Zhang'
Australiin Artificial Intelligence Institute, FEIT, University of Technology Sydney
University of Maryland jie mtaddett uus.uuuu edu.au, tianyi @umd [guodong long, jing- jiang, chengqi.zhang Outs. edu.
Abstract
Heterogeneous federated learning without assuming any structure is challenging due to the conflicts among non-identical data distributions of clients. In practice, clients often comprise near- near-homoe sau-hhomgeeeous clusters so training server-side model per cluster mitigates the conflicts. However, FL. with client clustering often suffers from "clustering collapse", i.e., one cluster's model excels on increasing clients, and reduces to angle-model FL.. Moreover, cluster-wit -iite models hinder knowledge sharing between clusters and each model depends on fewer clients. Furthermore, the static clustering assumption on data may not hold for dynamically changing models, which are sensitive to cluster imballace//iitializtion or outliers. To ad- dress these challenges, we propose "Clustered Additive Modeling (CAM)", which applies globally shared model O₂ on top of the cluster-wiss models O1.k. i.e., y = h(x; θg]+ + fz;; θx) for clients cluster-k. The global model captures the fea- tures shared by all clusters 11.k are enforced to focus the difference among clusters. To train CAM, we develop novel Fed-CAM algorithm that alternates be- tween client clustering and training global/cluster models to predict the residual of each other. We can easily modify any existing clustered FL. methods by CAM and significantly improve their performance without "clustering collapse" in different non-lID settings, We also provide convergence analysis of Fed-CAM algorithm.
Introduction
Federated learning (FL) trains global model over distributed clients and enforces data localization, i.e., data only stay local for model training at the client side while the server periodically averages client models' weights to update a global model and broadcast it to all clients. When the local data distributions identical across clients, one global model suffices to serve all clients [I] However, non-identical distributions across clients (i.c., statistical heterogeneity) ( are more common in practical FL scenarios, which leads conflicts between the global objective and local ones. Instead of applying one model to all the m clients, an ideal case for non-lID settings would be training local model per client without any interference from others. However, the local data are usually insufficient so global model trained on heterogeneous clients exploiting all their data can still be helpful to local training. Hence, non-IID FL methods (3-5) usually struggle find sweet spot between the global consensus and local personalization. Without any assumptions on the structure among clients, all clients" distributions be equally different from each other global model is impacted by the conflicts of all clients and may provide limited guidance to their local training.
Clustered Federated Learning. That being said, non-IID clients in practice usually have rich structures that have not been explored by most existing FL methods. common structure clusters, ie., heterogeneous clients can be grouped into several cea--homogeneuus clusters each composed of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

IPCA. wwwet FD
PCG-CAM ciert -0h
PCA. disster non-ID
POACIAL chara-- F0
Figure 1: Cluster sizes during IFCA vs. IFCA+CAM in client/cluster- -ieee non-IlD settings on CIFAR-I0. Legend: cluster ID (cluster size) in the last round. CAM effectively mitigates clustering collapse/imbalncee.
CPWR--1 Ckabrwwtz roe-ED (Dridee))
CIWR-12 Ckaberotie ree-ID (prideet
DIFA--10, Clastratas nen-ID (priceet
CETAR-16, truise nor. perccee
CAM
POAK
KGNK
PHODACES
POAK
POGNT
PHOEAN
PIOEAC
PHOKANN
Figure 2: Test accuracy and macro-F1 (sta of IFCA/FeSMM (w/o CAM) and IFCA/FeSEM (CAM) in cluster/client-wii wise non-lID settings CIFAR- 10 dataset. "IFCA(5)" represents IFCA with K = 5 clusters. CAM consistently brings substantial improvement to IFCA/FeSEM on both metrics and both settings.
clients with similar distributions. In practice, clusters might be associated with goographicaage/nccome groups, affiliations, etc. Hence, we can train server-side model for each cluster, hence mitigating the conflicts caused by heterogeneity. Unfortunately, clients' cluster memberships are usually undefined or inaccessible due to sensitive/private information and have to be jointly optimized with cluster-wise models, as recent clustered FL. 6 approaches do. They maintain K models O1:k for K clusters and assigns one θ2 to each client-i (with local data X; and local model 6,), e.g., by min-loss (O, with the minimum loss on X;) or K-means (the nearest θ2 to 6.) criterion. Hence, 1 S K S m models can accommodate more heterogeneity than single-model FL but also allows knowledge sharing among similar clients, which is lacking if training in client models independently. Hence, may reach better trade-off between global consensus and local personalization in non-llD settings.
However, compared to the general non-IID assumption, clustered FL's assumption might be too restrictive since it prohibits inter-cluster knowledge sharing and enforces every cluster-wise model's s training to only depend on a few clients. This is contradictory to the widely studied strategy that different tasks or domains can benefit from sharing low-level or partial representations. It is due to the gap between the assumption of "clustered data distributions" and the algorithms of "clustering models (represented by loss vectors or model weights)"" : they are not equal and the latter is more sharing.
restrictive. In other words, clients of different clusters can still benefit from
Moreover, clustered FL usually suffers from oplimization instability because dynamically changing models can violate the static clustering assumption and lead to imbalanced cluster assignment, which affects 11:k and local training in the future. In particular: (1) Clustering collapse, i.c., the clients assigned to one cluster keeps growing so "the rich becomes richer (i.c., the cluster-wise model becomes even stronger)" until reducing to single-model FL. This happens because most clients tend to first learn shared features before focusing on client-specific ones; (2) Fragile to outliers such as malicious clients that may dominate some clusters and push all other benign ones to one or few clusters; (3) Sensitive to initialization. The process highly depends on initial and earlier cluster assignments since they determine which clients" local training starts from the same model.
Main Contributions. FL. model termed "Clustered Additive Modeling (CAM)". Compared to clustered FI., CAM trains a global model O, on top of the K clusters' models 11.k. Its prediction for client-i combines the outputs of O, and the associated cluster c(i)'s 's model, i.c., = f((z; 0,,) + fa; O.()). This simple additive model removes the restriction of clustered FL by letting all clients share a base model θg. It enforces θ1.k to focus on learning the different features between clusters, hence mitigating "clustering collapse". Moreover, CAM tends to learn balanced clusters and determine the number of clusters automatically (by starting from more clusters and then zeroing out some of them), as demonstrated in Fig | captured by O1.k and have less impact on the global model Og. In addition, interactions between +i.k and O, make CAM less sensitive to initial cluster assignments since updating O, also changes the clustering.
To overcome the above problems of clustered FL. we propose a novel structured
Furthermore, CAM is less vulnerable to outliers, which can be mainly
2

---

CAM is general model- agnostic method that can modify any existing clustered FL methods. As examples, we apply CAM to two representative methods, ie.. IFCA [6] and FeSEM [8]. In the optimization of CAM, 1.K and 6, aim to fit the residual of each other's prediction. To this end, we propose an efficiently structured Fl. algorithm "Fed-CAM", which alternates between cluster assignment (server), local training (clients), and update of 1I.k and O (server). In experiments on several benchmarks in different non-IID settings, CAM significantly improves SOTA clustered FL methods, as shown in Fig Moreover, we provide convergence analysis of Fed-CAM algorithm.
2 Related Work
Non-IID FL aims tackle statistical heterogeneity across clients. FedAvg (T) is designed for the IID setting, so it suffers from client drift and slow convergence with non-IlD clients (2). To address this challenge, FedDANE [T0] proposed a federated Newton-type optimization method by adapting a method for classical distributed optimization, i.e., DANE, to the FL setting. Instead of synchronizing all clients' models be the same global model periodically, FedProx (3) only adds a proximal term to the local training objective that discourages the local model from drifting away from the global model and thus preserves the heterogeneity. [TT] applies adaptive learning rates to clients and [12] conducts attention-based adaptive weighting to aggregate clients' models. [3] studies the convergence of the FedAvg in non-IID scenarios. Recent work also studies client-wist wise personalized FL [1), which aim to address the non-IlD challenge by training a personalized model per client with the help of the shared global model. Their objectives focus on training local models rather than the server-side model.
Clustered FL assumes that non-III clients can be partitioned into several groups and clients in each group share a cluster-wiss model. It jointly optimizes the cluster assignments and the clusters' models. K-means-basse
methods (8) assign clusters to clients according to their model parameters' distance. CFL [2T] divides clients into two partitions based on the cosine similarity between client gradients and then checks whether a partition is congruent according to the gradient norm. IFCA (6) and HypCluster 7 assign to each client the cluster whose model achieves the minimum loss on the client's s data. Few-shot clustering has been introduced to clustered FI. by [32 FedP2P (24) allows communication between clients in the same cluster. (25) uses cluster-based contexts to enhance the fine-tuning of personalized FL models. [9] proposed the first cluster-wise non-IID setting and
bi-level optimization framework unifying most clustered FL methods.
Additive modeling in FL trains multiple models and adds their outputs together as its prediction. It was introduced FL very recently. Federated residual learning (26) proposed an FL algorithm to train an additive model for regression tasks. [27) applies additive modeling to combining the outputs of shared model and a local model in a partial model personalization framework, However, additive modeling has not been studied for clustered FI..
3 Clustered Additive Modeling (CAM)
In this section, we introduce clustered additive modeling (CAM), which combines a global model and cluster-wise model prediction in FL. CAM conducts a joint optimization of the global and cluster-wise models defined by a cluster assignment criterion. In particular, we provide two examples of CAM using different cluster assignment criteria. i.c., min-loss and K-means, which have been adopted respectively by two SOTA clustered-FL methods, i.e., IFCA and FeSEM. For each of them, we derive alternating optimization procedures (i.e., IFCA-CAM and FeSEM-CAM) that can be implemented in FL setting using two parallel threads of local model training. At the end of this section, we unify both algorithms in structured FL algorithm Fed-CAM.
Notations. We assume that there are m clients and K clusters, where client-i has n; examples and all clients have n = ->m Yi, examples. On the server side, we have a global model O and K cluster-wise models O1-K- On the client side, we train m cluster models 89.m. used to update the global model θ2 in FL. and 01.m used to update the cluster-wise model Ge(s) assigned to each client-i, where c(i) is its cluster label determined by the cluster assignment criterion c(-). We further define will use X, and Y,
C₁ A {i E [m] e(i) k} as the set of clients in cluster-k. For simplicity, to respectively represent the local training data on client-i and their ground truths, and E(Y,, F(X.)) denotes the batch loss of model F(-) on (X,, Yi). A CAM model for client-i can be
Fi(.) h(: θ₂)) + f(: Oe())).
(1)
3

---

For classification, F.(-) produces logits and we can apply softmax to get the class probabilities.
3.1 IFCA-CAM: model performance-drrien clustering
We extend the min-loss criterion used in IFCA [6] to CAM for cluster assignment, i.c., each client-i is assigned to the cluster-k whose model 9 leads to the minimal loss of CAM on client-i's data, i.c.,
c(i)
arg min ((Y, h(;;; ,2)) f(X;; 02)). kE[K]
IFCA-CAM optimizes Og and 1. for minimizing the above minimal loss over all the clients, i.e.,
m
IFCA-CAM:
min
min
+ ((X,; 0x)),
n
KE[K]
where the inner minimization performs the min-loss assignment in Eq. We solve Eq. (3) by the following alternating minimization of cluster membership, cluster-wise models, and the global model.
(i) Cluster assignment by applying Eq. 2 to the latest Gg and O1.x. This yields c(-) and C1:K-
(ii) Fixing Gg we optimize the cluster-wise models 11. by gradient descent:
O O
Σ
Ve, ((Y,,((( + f(X;; A [K].
(4)
SEC2
In FL, the gradient can be approximated by aggregating the model updates of local models 0, from clients, whose training on the client side is: (1) initializing 0g + Oe(sy (2) starting from the initialization, running E local epochs updating 0, by
+
0, EY (X;;; + f(X;; 0,)), vi e [m]:
(5)
and (3) aggregating the local model update 0: O₂ from client E C3 to update On, i.e.
O - 1 Σ Th
1
n4
+
0:-
(6)
n
iEC
iEC
(iii) Fixing O1.k, we can optimize the global model Oy by gradient descent:
θ Og 11 1)
Ve, Ve, (Y; f(X;;
[m]]
In FL, this gradient step can be approximated by aggregating the local models 06 (similar to FedAvg):
(I) initializing 0 + gg: (2) running E local epochs training 0 by
0e - -
((x;;))) + ((X,; (00000)++++X)))))))0000
V [m]:
(8)
and (3) aggregating the updated local models 0 of all the m clients to update θ,, i.e.,
e -
Σ AE[m]
n4 g0.
n
We can run two parallel threads of local training for 0 and for each client-i because their training in Eq. (8) and Eq. (5) does not depend on each other (but they both depend on the cluster assignments (i)). This analogous to the simultaneous update algorithm (FedSim) in [27]. One may also consider an alternative update algorithm (which may enjoy slightly faster convergence) that iterates (i) in each round. However, doubles the communication rounds (() requires one communication round) and does not allow parallel local training. Since the alternative update does not show significant empirical improvement over FedSim in 27 one in the remainder of this paper.
we mainly focus on the parallel

---

3.2 FeSEM-CAM: parameter similarity-based clustering
We follow similar procedure of IFCA-CAM derive FeSEM-CAM, which applies a K-means style clustering to the client models f1.m, whose objective is minimizing the sum of squares of client-cluster distance, i.e.,
min eL.
min min 1 JEKK
(10)
Hence, similar to FeSEM (8) FeSEM-CAM assigns the nearest cluster-wise model to each client and updates the cluster-wise models the cluster centroids (i.e., K-means algorithm), i.e.,
ii) arg min 10: - O& O kE(K]
Σ IEC2
O.. Eiec n
(11)
We iterate the above K-means steps for few times until convergence in practice. FeSEM CAM applies the K-means objective in Eq. (10) as regularization to the loss of CAM model E(Y,, h(X; 0g) + fx),;
FeSEM-CAM:
min B1: Oxemn
Σ (XY,)(X;;0,) f(X;0.)) ((x:0))))))))))))))))) 2 JE[K]
m
The
A min 0
,
(12)
where the minimization w.r.t. 11:k (with fimm fixed) recovers the (weighted) K-means objective in Eq. (TO). Unlike IFCA-CAM, where client model 0, is auxiliary/latent variable for FL not showing in the objective of Eq. (3). it is explicitly optimized in Eq. (12). Similar to IFCA-CAM, we solve
Eq. (3) by iterating the following alternating minimization steps (i)-(ii).
(i) K-means clustering that iterates Eq. (TI a few steps until convergence, which yields c(+),
C1.K, and O1.x. The update of O1.k is analogous to Eq. (6).
(ii) Fixing Gg. we optimize 1m. by client-side local gradient descent:
T2: Vo, (X,, + f(X,0,)), vi [m]] "
0, - (1 - n))0, + 7)0a( 1 Y3
(13)
The first two terms in Eq. 13) compute linear interpolation between 0g and its assigned cluster's model O.(g) This is result of the K-means regularization term in Eq. (12) and keeps 6, close ax(i)-
(iii) Fixing 0 1mms we can optimize Og by gradient descent:
g f O
Σ iE mm
Th
(X) ((x:0.))
(14)
n
In FL, this gradient step can be approximated by aggregating the local models 05 (similar to FedAvg):
(I) initializing 0 + Ogi (2) running E' local epochs training 0 by
8 - p.
M (X;;; 09) + f(X;0,)), ViE [m]]
(15)
and (3) aggregating the updated local models 0f of all the m clients update O2 by Eq.
3.3 Algorithm
In Algorithm | we propose structured Fl. algorithm for CAM, i.e., Fed-CAM, which can unify the derived optimization procedures for IFCA-CAM and FeSEM- -AM and can be easily extended to other clustered FL and clustering criteria.
Warmup. As an alternating optimization framework, it would be unstable if both G, and O are randomly initialized and jointly optimized in parallel since they may capture overlapping information and result in an inefficient competitive game. To encourage them learn complementary knowledge, warmup training for one of them before the joint optimization is helpful. For example, few rounds of FedAvg can produce a "warm" ,,, whose predictions' residuals are more informative to train OI.x- Another warmup strategy could be to run few local training epochs and extract warm θ by clustering the lightly-trained local models 01mm In Fed-CAM, we can apply the former warmup to IFCA-CAM and the latter to FeSEM-CAM.
5

---

Algorithm 1: Fed-CAM
initialize :Randomly initialize 11.x and Gg.
warmup :(1) | rounds of FedAvg get initial 6, (IFCA-CAM) (2) 3 epochs of local training only to get a initial 1mm (FedSEM-CAM), Broadcast θ, and 1 to clients.
while not converge do
/+ Client (in parallel)
for every selected client do
Model performance-driver clustering (c.g., IFCA-CAM): cluster assignment by Eq. 2
Initialize + ee()) and 6 gg: Local training of for E epochs: c.g., Eq. (IFCA-CAM) or Eq.
13
(FeSEM-CAM) CAM)
Local training of 6f for E epochs: e.g., Eq. ( (IFCA-CAM) Eq. 15 (FeSEM-CAM);
Upload 0g and 0. to the server;
Server
Update cluster-wise models 0i.k: c.g., Eq. (6 (IFCA-CAM) or Eq. [1
(FeSEM-CAM)
Update global model 6, by Eq. (9)
10
Broadcast O, and i. to all clients;
output
:Global model og. cluster wise models O1.k and c(t) V E [m]]
Convergence Analysis
Based the convergence analysis presented in 27 which aims to minimize the following objective:
min F(u, V) V.V
F( v.).
(16)
1
em denotes the personalized parame- ters. If we map G2 to and θ 1.K to V respectively, this appears strikingly similar to methods as illustrated in Equations and 12 Provided that the clustering remains stable, we can employ the theoretical framework of [27]. And firstly, we make some standard assumptions for the convergence analysis as below.
where u represents the shared parameters and U1, U2,
Assumption 1. (Smoothness). iori= I, m. the loss function / is continuously differentiable, and there exist constants L that Ve,((O,, θx) is L-Lipschitz with respect to G, and O and Ve, (0 θ₂) is L-Lipschitz with respect to G, and θ₁. Assumption 2. (Unbiased gradients and bounded variance). The stochastic gradients are unbiased and have bounded variance. For all O and θ₁
BiVe, ((0 0x)] (e, θx), B[Ve, 0x)] Ve,
e(G Ok);
and B|| Ve, ( O2) (0,, 1 S So BII (0 Ox) Ve, { ( < oz
Assumption 3. (Partial gradient diversity). There exists constant for @ and θg 0, and θs.
m
n4
((
-0,, 0x) $ 8²
n
L0., 0x) Vol 02 8
Ejelo Th
(E(H)
Assumption 4. (Convexity of cluster models). Fix O,, assume ((Or) convex.
Theorem 1. (Convergence of Fed-CAM). Let Assumptions 7 and hold, and learning rates cho-
as 7 (/(LE) for a depending on the parameters I, g. o 8 m. T, provided clustering stable, we have (ignoring absolute constants),
E 12)
8
V een (0,,, (11)
(17)
T
mL
i=1
(De02
1/2
2m30a.m22 T2/3
11/3
0 7
(18)
71/2

---

where De to f0-- - and we define effective variance terms,
2
o²
o
2
sim,1
L
(82
m L
)
+
m
(19)
2 (82
+ oog +0 =E)
(20)
sim,
L
Remark 1. It is straightforward to prove that the clustering of both IFCA-CAM and FeSEM-CAM
converges, as evidenced by Ma et al. (2022). However, proving the stability of these clustering methods is more challenging due the oscillation phenomenon often in K-means. The stability of clustering will be further demonstrated through experimental analysis Section 5.2
Remark 2. Besides the clustering structure, there is a distinct difference between FedSim 27 and Fed-CAM. In Fed-CAM, we need to aggregate both O and I. while FedAlt (27). only O requires aggregation. The o sim_1 and 2... reflect the impact of sample number and local steps E. Larger or smaller E, better convergence rate. According to the results presented in (27). alternative gradient descent surpasses simultaneous gradient descent in terms of convergence rate. The asymptotic 1/VT rate achieved when each device is seen at least once on average, and the 1 I/T term dominated by the 1/vT term, a situation that occurs when (ignoring absolute constants)
max [ - 2).
T T
sim,1
Experiments
Benchmark datasets and partitions. The proposed methods have been validated using several benchmark datasets. While detailed results for PathMNIST and TissueMNIST from the MedMNIST 28 are provided in the supplementary material, the other datasets used for validation include:
Fashion-MNIST 29 includes 70,000 labeled fashion images (28x28 grayscale) 10 classes, such as T-shirts, Trouser, and Bag, with others.
CIFAR-10 (30] consists of 60,000 images (32x32 color) in 10 classes, including airplane, automo- bile, bird, and truck, among others. The divergence among classes in CIFAR-10 is relatively higher than in other datasets from the MNIST family.
Each dataset split among 200 clients and we create the following non-lID scenarios:
Client-wise non-lID by Dirichlet distribution (a = 0.1): This approach uses the Dirichlet distribution control the randomness of non-lID data, as proposed by (3I). This is standard method used in most personalized FL methods, which are usually client-wise non-IID.
Cluster-wise non-III by Dirichlet distribution (a (0.1, 10)): This strategy divides the dataset into clusters with a 0.1 generate substantial variance in cluster-wise non-IID. Then, each cluster is divided into m/ K clients with = 10 to control the non-lID across clients.
Client-wise non-III by n-class (2): This method randomly selects n-class out all classes in the dataset for each client, as proposed by [ and then samples instances from these datasets.
Cluster-wiss non-IID by n-class (3, 2): This approach randomly assigns classes to each cluster, ensuring relatively balanced number instances per class. then assigns 2 classes to each client.
Baselines. We select baseline methods from four categories as follows:
Single model-based FL: We choose FedAvg and FedProx 3 with a coefficient of 230 and a regularization of 0.95 as the baselines.
Ensemble FL: We train FedAvg and FedProx K times and then learn ensemble model via soft voting to serve all clients, which are named FedAvg+ and FedProx+, respectively.
Clustered FL: We choose FcSEM and IFCA (6), which is similar to HypCluster 7
Clustered FL with additive modeling: We integrate CAM with IFCA and FeSEM, denoting them IFCA-CAM and FeSEM-CAM, respectively.
7

---

Learning-relater hyperparametters. We use the Convolutional Neural Network (CNN) 32] as the basic model architecture for each client, as detailed in the supplementary material. For optimization. we employ SGID with learning rate of 0.001 and momentum of 0.9 to train the model, and the batch size is 32, We evaluate the performance using both miero accuracy (%) and macro F1-score (%) on the client-wise test datasets to better capture the non-IlI nature per client.
FL system settings. We conduct 100 global communication rounds in the FL system, including 30 warm-up rounds if applicable. Each communication involves 10 local steps. For the clustering process of FeSEM-CAM, we measure distance on the flattened parameters of the fully-connected layers, and use K-Means as the clustering algorithm. The coefficient À is chosen from 0.001, 0.01, 0.1 based on the best performance.
5.1 Main Results and Comparisons
Cluster-wise non-IID scenarios make the assumption that there are underlying clustering structures among clients. compares the methods using two benchmark datasets, namely Mishion-MNIST and CIFAR-10. Results using two biomedical datasets are presented in the appendix. The following are some notable observations and analyses:
The application of the ensemble mechanism to FedAvg and FedProx yields minor improvements. This is because the server-side model in FedAvg or FedProx is already relatively strong model, while ensemble mechanisms usually excel with weak models.
The introduction of CAM significantly enhances the performance of IFCA, which typically struggles with clustering collapse in cluster-wise non-IID scenarios. Notably, CAM decomposes the shared components into global model and personalized parts into cluster models. Thus, the clustering collapse is mitigated by isolating the dominant shared knowledge.
FeSEM generally exhibits robust performance on cluster- wise non-III without outliers. Implement- ing CAM in FeSEM further improves the Macro-F1 performance. The clustering process in FeSEM tends to overfit the label distribution (imbalanced classes) of clients to achieve higher accuracy. However, the application of CAM introduces global model with a balanced label distribution by averaging all clients, thereby boosting the Macro-F1 performance while preserving the cluster-wise non-III for high accuracy.
With increase in the number of clusters K, the CAM-based methods show substantial im- provements in Macro-F1. The decomposition of shared knowledge and cluster-wise non-III) characteristics benefit from reasonably larger K, which facilitates fine-grained, cluster-wise personalization.
Table 1: Test results (td) in cluster-wise non-IID settings on Mashion-MNIST CIFAR-10.
Pashion-MNND MNIST
CIPAR-10
Nan-IID setting
Dirichles a (0.1.10)
n-class (3.2)
Dirichlet
(0.1.
D-class (3.
#Cluster
Methods
Accuracy
Macro-F1
Accuncy
Macro-P1
Accumacy
Macno-P1
Accuracy
Micro-FI
FedAvg
36.00-0.70
57 24.244
86.33+0.44
46.09- 1.08
24.38+-1.30
11,09+3115
21.33+383
9.00+0.58
FedProx
86.32=0778
38.08:33.19
86.4250.63
45.86 .2
24.73+.3.68
11.28=2235
22 16:11111
9.23=0.78
FedAuga
25.97
FedProxt
87.94
59.83
86.52
65.73
26.05
12:53
24.83
9.31
IFCA
81.60-22222 22
62 33.00313.01
81.511254
66.50144.43
34.10114.79
22.12:::211
29. 19.80114.49
17.9012.08
IFCA-CAM
93.33-095
79.61.14.09
95. 05.3810.499
77.56.1
58.1311.82
28.0913368
54, 54155613.58
27.27111006
R-EM
94.64:1.54
22:00:2333
17.07:6600
59.0661:1224
32.33::7.25
76.33.555
35.751:2.54
R5SEM-CAM
95.13-1.778
X5.10-3.11
95.69+1005
1.17
64.35+22.33
38.33-1.77
65.58+1.21
38.6++1117
RedAvg+
89.42
67.83
86.91
63.01
28:45
13.79
27.28
9.81
RedProni
89.55
68.02
86.73
63.42
28.33
13.64
26.94
9.64
IFCA
82,10=5
62 0162288.22
86.5824997
66.2215.69
34.8415.82
22.76=:.99
34.06:2.60
18.70 1.31
IAM
95.42-2.54
45.455..66
82.98.1..8
1..9011.11
40.0311128
68.4614.08
41.451.4.00
R-EM
95.73 28
39 1.51
95.54.10.74
11.13
66.89112.18
38.3514.24
71.7612.22
49.72.1.81
F-SEM-CAM
96.19 1.20
92.377:1.85
98.07:1146
22.43::2.00
78.4511.71
49.50:11133
75.04:1.97
55.90112.07
Client-wise non-III Table 2 presents comparative results under client-wise non-IID scenarios and CIFAR-10. Interestingly. IFCA maintains stable performance under client-wise non-llI conditions, primarily because it cannot form a single dominant cluster model a primary cause of clustering collapse in a highly heterogeneous environment. The application of CAM to IFCA and FeSEM shows a significant enhancement, particularly on the CIFAR-10 10 dataset. This improvement is likely due to FeSEM's 's typical restriction on knowledge sharing across clusters. In contrast, CAM utilizes a global model to capture more useful common
using two benchmark datasets:
8

---

cieet--rre 10h-0
FADEV duwlerrs
dusle non-D
230
Roaed
Dound
Cluster sizes during FcSEM vs. FeSEM+CAM in client/cluster- wise non-llD settings on CIFAR- Legend: cluster ID (cluster size) in the last round. CAM effectively mitigates clustering collapse/mbalance.
Figure 3:
knowledge across clusters, thereby substantially enhancing the generalization capability of each cluster. Furthermore, CIFAR- 10, being a relatively complex dataset with diversity of images, underscores the importance of sharing common knowledge.
Table 2: Test results (td) in client-wist non-III settings Fashion- MashSTn-MNIST& & CIFAR-10.
Danasess
MNNIST
CIFAR-10
Non-IID setting
Dirichlet
D-class (2)
Dirichlet
B-class (2)
Methods
Accuracy
Macro-FI
Accurccy
Macro-Fi
Accuracy
Macro-FI
Accuracy
FolAvg
859020466
44.52:2266
26.1000
44.88:11244
25.62::::47
11.38-2022
3023333
8.56100
FedProx
8603-0.58
54.60-3.32
86.47+0.25
44.89+1.38
25.72+33.29
11.14-1.49
24 19+244
8.60+0.74
FedAvg+
86.12
61.07
$6.5
45.39
25.71
12:45
24.83
8.74
FedPruxt
$6.39
56.56
86.15
45.43
25.58
12:43
25.88
8.55
IFCA
90.336881
6847=53
54:5445.04
12.50+5.32
47.21 10.28
22.67=148
46
16.541128
17.78=11299
20.67=1775
92:24
70.2444.33
25.20=1105
73.78-9.88
91,83+1.24
71.05+8.63
54.30+4.500
52.80-4.16
FeSEM-CAM
94.74=1.04
75.12-5.82
93.14+2/03
76.98+2.17
59.71+2.80
40.45-1.33
56.70-168
34.52-1.64
FedAvgt
$6.81
60.33
$6.91
47.12
27.83
13.65
23.71
9.65
FelProx
86.24
56.2
86.78
42.83
25.86
12.84
26.16
9.94
IRCA
01.04-4.33
9144+5.16
72.29+-5.80
47.62-10.15
13.6622.46
47.06
17,88-1
79.17-191
92.57.1.63
76.31
42.86.1116
FoSEM
91.3120
8047.111.0
93.7511
79.3916..77
67_
31.69.8.52
63.6116511
42,97_6008
FeSEM-CAM
15925
81.5::2244
95.15:1148
86.16::3.19
$0.11:1182
59.19:4.67
69.88-117
49.5:1142
5.2 Visualization: CAM combats clustering collapse
Figures [ and 3 demonstrate the effectiveness of applying CAM to mitigate clustering collapse in IFCA and FeSEM under both cluster-wise and client-wise non-lll) scenarios, using the CIFAR-10 dataset with K = 10. Each color represents a cluster, and the X-axis represents the iteration rounds.
In the case of IFCA, we observe severe clustering collapse issue in cluster- wise non- IID scenarios. single cluster can encompass all clients in the client-wise non-lID setting and up to 50% of clients in the cluster non-IlD setting. Furthermore, the clustering remains unstable throughout the process. However, when CAM is applied in IFCA-CAM, it quickly identifies some clustering structures within few rounds, and this structure closely approximates the ground truth.
As for FeSEM, while the phenomenon of clustering collapse not as pronounced, single cluster can still dominate up to 25% of all clients if there are no outliers. CAM can expedite the clustering convergence, sometimes achieving it in just one round. Moreover, under client-wise non-lll) settings, the application of CAM results in lower variance and more uniform cluster size. In the case of cluster-wise non-IID settings, FeSEM-CAM can easily identify the ground truth.
Conclusions
We propose novel structured FL model "clustered additive modeling (CAM)" and an efficient FL algorithmic framework Fed-CAM to address non-llI FL challenges with clustering structure. CAM general mode-agnostic tool that can improve various existing non-IID FL methods. It can capture more general non-lID structures with global knowledge sharing among clients than clustered FL and overcome several weaknesses such as clustering collapse, vulnerability cluster imbal- ance/imitialization, etc. Theoretically, Fed-CAM is capable of achieving an asymptotic convergence rate of O(1/VT), Extensive experiments show that CAM brings substantial improvement to existing clustered FL methods, improves cluster balance, and effectively mitigates clustering collapse.

---

References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fficciee learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMIR, 2017.
[2] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems federated learning. Foundations and Trends in Machine Learning, (4(1-2):1-210, 2021.
[3] Tian Li. Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith, Federated optimization in hetcrogeneous networks. Proceedings of Machine Learning and Systems, 2:429 --029-450, 2020.
[4] Hangyu Zhu, Jinjin Xu, Shiqing Liu, and Yaochu Jin. Federated learning on non-iid data: A survey. arXiv preprint
2021.
[5] Dashan Gao, Xin Yao, and Qiang Yang. A survey on heterogeneous federated learning. arXiv preprint urXiv:2210.04505, 2022.
[6] Avishek Ghosh, Jichan Chung, Dong Yin, and Kanman Ramchandran, An efficient framework for clustered federated learning. Advances Neural Information Processing Systems, 33:19586 19597, 2020.
[7] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personaliza- tion with applications to federated learning. arXiv preprint arXiv:2002.16613 2020.
[8] Ming Xie, Guodong Long, Tao Shen, Tianyi Zhou, Xianzhi Wang. Jing Jiang, and Chengqi Zhang. Multi-center federated learning. arXiv preprint arXiv:2108 08647, 2021.
[9] Jie Ma. Guodong Long. Tianyi Zhou, Jing Jiang, and Chengqi Zhang. On the convergence of clustered federated learning. arXiv preprint arXiv:2202.661 187 2022.
[10] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy, Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1227-1231, IEFF, 2019.
[11] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan Adaptive federated optimization. arXiv preprint (xXiv20003000299 2020.
[12] Jing Jiang. Shaoxiong Ji, and Guodong Long. Decentralized knowledge acquisition for mobile internet applications. World Wide Web, 23(5):2653 2669, 2020.
[13] Xiang Li. Kaixuan Huang. Wenhao Yang. Shusen Wang, and Zhihua Zhang, On the convergence of fedavg non-iid data, arXiv preprint 10XX::9977.02188 2019.
[14] Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Toward personalized federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[15] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems, 33:3557 3568, 2020.
[16] Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik, Personalized federated learning using hypereeworks. In International Conference on Machine Leurning, pages 9489-9502. PMLR, 2021.
[17] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Adaptive personalized federated learning. arXiv preprint arXiv:2003. 204..30003..341,,, 2020.
[18] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International Conference on Machine Learning, pages 2089-2099. PMI.R, 2021.
[19] Canh T Dinh, Nguyen Tran, and Josh Nguyen. Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 13::13944-21400 211055, 2020.
[20] Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, John Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. Advances in Neural Information Processing Systems, 34:11220-11233 2021.
[21] Felix Sattler, Klaus Robert Müller, and Wojciech Samek. Clustered federated learning: Model-agnosite distributed multitask optimization under privacy constraints. IEFE transactions neural networks and learning systems, 2020.
[22] Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogencity for the win: One-Shot federated clustering. March 2021.
[23] Pranjal Awasthi and Or Sheffet. Improved spectral-norm bounds for clustering. In Approximation. Randomization, and Combinatorial Optimization. Algoritiums and Techniques, pages 37 49. Springer. 2012.
10

---

[24] Li Chou, Zichang Liu, Zhuang Wang, and Anshumali Shrivastava, Efficient and less centralized federated learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 772-787. Springer, 2021.
[25] Xueyang Tang, Song Guo, and Jingcai Guo. Personalized federated learning with contextualized gen- eralization. In Lud De Raedt, editor, Proceedings the Thirty- First International Joint Conference Artificial Intelligence, IJCAI-22, pages 2241-2247. International Joint Conferences on Artificial Intelli- gence Organization, 2022. Main Track.
[26] Alckh Agarwal, John Langford, and Yu Wei. Federated residual learning. arXiv preprint arXiv:2003. 12880, 2020.
[27] Krishma Pillutla, Kshitiz Malik, Abdel-Rahman Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. In International Conference Machine Learning. pages 17716-17758. PMLR, 2022.
[28] Jiancheng Yang. Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Binghing Ni. Medmnist v2: A large-scale lightweight benchmark for 2d and 3d biomedical image classification. arXiv preprint arXiv:2110. 14795, 2021.
[29] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 077477777..777, 2017.
[30] Alex Krizhevsky, Geoffrey Hinton,
Learning multiple layers features from tiny images. 2009.
[31] Tzu-Ming Harry Hsu, Hang Qi and Matthew Brown. Measuring the effects of non-identical data distribu- tion for federated visual classification. arXiv preprint arXiv:/90..06:: 2019.
[32] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 444, 2015.


Reviews:
[{"review_id": "DMO9sPUjLL", "reviewer": "Reviewer_dS6T", "summary": "This paper proposes a novel clustered federated learning method using additive modeling to tackle the clustering collapse problem. The paper contributes to advance the research domain of clustered federated learning which is an important and practical solution to solve non-iid problem in federated settings. ", "questions": "1. In Eq.1, why you use two symbols h(.) and f(.) to represent global model and cluster-specific model. Are they using different model architecture?\n\n2. In Eq. 2, why is the additive results is Y rather than 2Y?\n\n3. Please discuss how the proposed method can solve the mentioned challenges in Introduction section.\n\n4. Is it necessary to have a comparison experiments with some personalized FL method, e.g. FedAvg + Finetuning?\n\n5. In Ensemble FL, whatis the different part of K times experiments? \n\n6. How about to add a parameter to adjust the importance weight between two models h and f? Say h(.) + a*f(.).\n\n7. In Notations (line 128), what does the symbol \"0\" represent in the context of the symbol $\\theta_{1:m}^0$ ?\n\n8. Is the performance of the global model or the cluster-level model compared during testing?\n\n9. How many clusters obtained in training phase? Is it necessary to keep the same number of clusters as the CAM method for methods that need to specify the number of clusters?", "limitations": "Yes. The authors have addressed the limitations. There is no negative societal impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is simple yet effective. The overall solution is technique sounds. This work is very likely will become a new baseline of clustered FL.\n\n2. The targeting problem is an inherent challenge of clustered FL. The Introduction section provides insight analysis of current clustered FL. \n\n3. The overall flow description is sufficiently clear.\n\n4. The provided theoritical analhysis is well suited to the clustered FL settings.\n\n5. The claims are well supported by the experiments.", "weaknesses": "1. The readability of this paper could be improved. For example, there are many abbreviation names, e.g. CAM, FED-CAM, IFCA, FeSEM. The symbol system is a little bit complicated. \n \n2. The paper discussed several insightful challenge of clustered FL. However, it is how the proposed method can solve these challenges. \n\n3. Some description needs to be improved. For example, it is unclear how the Figure 1 and 2 link to the Introduction section. Moreover, in Introduction section, there are many symbols without a clear definition.\n\n4. This method may require storing multiple models locally (cluster-level model, global model, and local model), which could increase costs. It would be better to compare and discuss with other methods to explore potentially more favorable alternatives.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback regarding our 'simple-yet-effective method,' 'well-suited theoretical analysis,' and 'well-supported claims.' Below, we provide our responses to the weaknesses and questions you mentioned in relation to this paper.\n\n### Weakness Clarifications\n\n***How does CAM solve the mentioned challenges?***\n- CAM solves the mentioned challenges by introducing a global model $\\Theta_g$ and adding its output to the output of the cluster model $\\theta_{c(i)}$ each client $i$ belonging to. The final prediction is the sum of the global model output and cluster model output $y = h(x; \\Theta_g) + f(x; \\theta_{c(i)})$. This removes any globally shared components from cluster models and thus prevents one cluster model from capturing the globally shared knowledge, which leads to clustering collapse. \n\n- Moreover, this also removes the conflicts between client clustering and global knowledge sharing, where the former moves clusters models away from each other and thus harms global sharing, because CAM optimizes the two objectives separately on two groups of model parameters. Therefore, the global model solely focuses on capturing the globally sharable knowledge, while the cluster models focus on intra-cluster shared but inter-cluster separable knowledge. \n\n- Furthermore, CAM improves robustness against outliers, which primarily impact $\\Theta_{1:K}$ but exert minimal influence on the global model $\\Theta_g$. Notably, the interplay between $\\Theta_{1:K}$ and $\\Theta_g$ renders CAM less susceptible to initial cluster assignments' variations, as adjustments to $\\Theta_g$ induce changes in the clustering scheme.\n\n***Extra cost of CAM***\nPlease refer to the general response.\n\n***Readability***\nFor readability-related Weaknesses 1 and 3, most of them can be found in the introduction section. The full name of CAM can be found in the abstract, while Fed-CAM denotes \"Federated Learning with CAM\". In the introduction, IFCA and FeSEM have been cited in Line 84. Fig 1 and 2 have been discussed in Lines 79 and 89, respectively.\n\n\n### Question Clarifications\n***In Eq.1, why you use two symbols $h(.)$ and $f(.)$ to represent global model and cluster-specific model. Are they using different model architecture?***\n\nYes. The global model can have a different architecture as the cluster-specific model as long as their outputs are addable.\n\n***In Eq. 2, why is the additive results is $Y$ rather than $2Y$?***\n\nThe additive results will be processed by softmax before being compared with $Y$. Moreover, the models are learnable so as the scales of their outputs. So only $Y$ is needed.\n\n***Is it necessary to have a comparison experiments with some personalized FL method, e.g. FedAvg + Finetuning?***\n\nYes, we have included personalized FL methods as baselines in Section 2.2 of the supplementary material, in which Fedavg+Finetuning and some other personalized FL methods have been compared.\n\n***In Ensemble FL, whatis the different part of K times experiments?***\n\nIn Ensemble FL, the different part of $K$ times is the initialization.\n\n***How about to add a parameter to adjust the importance weight between two models h and f? Say $h(.) + a*f(.)$.***\n\nIt is not necessary because the importance weights can be automatically learned by the models, i.e., the model parameters can control the scales of the model output. For inference, an extra importance weight to makes it inconsistent with the training.\n\n***In Notations (line 128), what does the symbol \"0\" represent in the context of the symbol $\\theta^0_{1:m}$?***\n\nBoth $\\theta^0_{1:m}$ and $\\theta_{1:m}$ are local models but they are different: $\\theta^0_{1:m}$ are trained and aggregated for the global model optimization, while $\\theta_{1:m}$ are trained and aggregated for the cluster model optimization.\n\n***Is the performance of the global model or the cluster-level model compared during testing?***\n\nYes. Global models such as FedAvg and FedProx and cluster-level models such as IFCA and FeSEM have been compared during testing in Tables 1-2 of the main paper.\n\n***How many clusters obtained in training phase? Is it necessary to keep the same number of clusters as the CAM method for methods that need to specify the number of clusters?***\n\nAs shown in the first column of Tables 1-2, the chosen number of clusters is $\\{1,5,10\\}$, while the ground truth is $10$. And for the second question, YES, the same number of clusters is kept for comparison.\n\nPlease let us know if you have any further questions. If our responses have sufficiently addressed your concerns, it would be great if you are willing to reconsider your score kindly. Thank you!\n\nBest,\nAuthors"}, {"review_id": "bRcZz30ulH", "reviewer": "Reviewer_WQSD", "summary": "This paper proposes a new federated learning with a specified structure for the prediction produced for each client, called \"clustered additive modelling\", which adds the prediction of a global model to the prediction of the model trained on a local cluster of clients. It is a modification to existing clustered federated learning methods and fixes several critical issues of these methods such as clustering collapse, fragility to outlier clients, and sensitivity to initialization. Some of the issues are fundamental and widely exist in many existing methods. The paper shows that the proposed CAM can effectively address these issues in different clustered FL methods under different non-IID settings, consistently leading to a promising improvement. ", "questions": "1. Can you provide more details and some examples of the cluster-wise non-IID setting?\n2. What is the cost of the warmup stage? How is the performance affected by reducing the warmup rounds?\nOverall, I think this is a solid paper that successfully addressed a widely existing fundamental problem in FL that has not been investigated before. The motivation and proposed idea are principal. Most parts of the paper are clear. The analysis and experiments are convincing. Experiments on more datasets and more guidance on the theoretical analysis can further strengthen the draft. \n", "limitations": "Yes. The authors have addressed the limitations.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This tackles a fundamental problem in clustered FL, i.e., clustering collapse. This problem might be widely observed but has not been well investigated and effectively solved before. Hence, I believe this work can be helpful and have a broad impact on FL problems studying statistical heterogeneity and structures among clients. \n2. The motivation of this paper is clear. The solution provided by clustered additive modelling is principal, easy to understand, effective across different settings, and generalizable to various existing FL methods. \n3. The proposed algorithms in Section 3.1 and 3.2 are intuitive and convincing with detailed explanations per step and theoretical guarantee (convergence analysis). I appreciate the authors for providing two examples of CAM algorithms following the same high-level idea. \n4. The experiments conducted on 2 datasets x 4 non-IID settings show great advantages of the proposed method over existing FL and clustered FL methods. The analysis of clustering collapse also provides a nice explanation and empirical evidence for the improvement. \n5. The code is provided for high reproducibility.\n", "weaknesses": "1. Compared to existing clustered FL methods, the proposed method needs to train an additional model. How much extra computation does it require? It would be helpful to provide the computation complexity of CAM.\n2. While other parts of the paper are easy to understand, the convergence analysis part is limited in length and left many details in the appendix. Can you elaborate a little bit more on the proof idea?\n3. The comparison and experiments on each dataset are thorough to me but the empirical results would be stronger if experimenting on more datasets. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback regarding our 'clear motivation tackling a fundamental problem in clustered FL,' 'intuitive and convincing algorithms,' 'nice analysis for clustering collapse,' and 'high reproducibility.' Below, we provide our responses to the weaknesses and questions you mentioned in relation to this paper.\n\n\n### Weakness Clarifications\n\n***Extra cost of CAM***\nPlease refer to the general response.\n\n***Convergence framework***\nWe will add the main steps of convergence analysis into the main paper in future works. The proof framework of convergence analysis is to bound the error of one communication round first, then add $T$ rounds together. For the error of one communication round, we break it into three parts, local training, clustering and aggregation, and bound each separately.\n\n***Experiments on more datasets***\nWe will test CAM on more cases, such as graph and NLP in future works.\n\n### Question Clarifications\n\n***Examples of cluster-wise non-IID settings***\nIn the real world, clustering is very popular and used everywhere. For example, the Mall Customer Segmentation Dataset includes customer information like age, income, and spending score. Clustering can help identify different customer segments based on their shopping behavior. The 20 Newsgroups Dataset contains newsgroup documents from 20 different newsgroups, covering a wide range of topics. Clustering can be used to group documents with similar content, such as sports, politics, science, etc.\n\n***Impact of warmup rounds***\nPlease refer to the general response.\n\nWe have tried to address most if not all concerns. Please let us know if you have any further questions. Thank you!\n\nBest,\nAuthors\n"}, {"review_id": "ZhusIw4Jt9", "reviewer": "Reviewer_HLnM", "summary": "This paper studied the problem of clustered federated learning. It analyzed the limitations of existing clustered FL algorithms, including clustering collapse and missing shared knowledge among clusters. Then this paper introduced a novel Clustered Additive Modeling (CAM) framework for learning both a globally shared model and cluster-wise models. A Fed-CAM algorithm was proposed to train CAM model parameters iteratively. The experimental results showed that CAM outperformed existing clustered FL algorithms in prediction accuracy.\n\n#######################################\nI appreciate the detailed response from the authors. However, my major concerns regarding the overall contributions still remain. Therefore, I keep my scores unchanged.", "questions": "(1) It shows that CAM tends to learn balanced clusters and determine the number of clusters automatically. Thus, CAM might perform well when the ground-truth of client clustering is balanced. But when the ground-truth of client clustering is highly skewed, would the balanced clusters learned by CAM result in sub-optimal solutions?\n\n(2) Why is there a constant 1/m in Eq. (9) for updating global model parameters?\n\n(3) In Eq. (13), what is the notation “\\eta”? If it denotes the learning rate, why is it only applied to the first term of Eq. (12) with classification loss? \n\n(4) In line 176, should it be “Eq. (13)” instead of “Eq. (3)” regarding the K-means regularization term?\n\n(5) Why do IFCA-CAM and FeSEM-CAM use different warmup strategies? Is the selection of warmup strategy related to the clustering methods (e.g., minimum loss values in IFCA, K-means over parameters in FeSEM) in FL?\n\n(6) What is FedAlt in line 217?\n\n(7) In FL system setting, would the hyper-parameter \\lambda be selected based on the best performance over the validation set? If so, how are the train/validation/test sets splits in the experiments?", "limitations": "Not discussed.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The strengths of this paper are summarized below.\n(1) It proposed a novel Clustered Additive Modeling (CAM) framework for clustered federated learning. Compared to previous algorithms, CAM leveraged a global model to discover the shared knowledge among clusters.\n\n(2) It demonstrated the flexibility of CAM framework by incorporating CAM with two popular clustered FL methods, thus leading to IFCA-CAM and FeSEM-CAM models. Then it provided a unified Fed-CAM optimization method for iteratively updating the clustering and global model parameters.\n\n(3) Experimental results on both cluster and client-wise non-IID settings showed that compared to vanilla IFCA and FeSEM, IFCA-CAM and FeSEM-CAM could achieve better prediction performance in local clients.", "weaknesses": "(1) The rationale behind the proposed CAM framework lacks sufficient justification. As illustrated in the introduction section, existing cluttered FL algorithms suffers from clustering collapse, fragility to outliers, and sensitivity to initialization. However, the techniques regarding how CAM addresses these limitations are not explained.\n(1-1) CAM introduced a global model to mitigate the lustering collapse. As shown in Subsection 3.3, it requires that global and cluster-wise models learn complementary knowledge. One concern is whether the global knowledge shared by all clients always exists in any non-IID FL settings. Furthermore, line 49 states that “different tasks or domains can benefit from sharing low-level or partial representations”. A natural question is whether it is more reasonable to learn partial representations (e.g., common low-level model parameters in FedRep [24]) for discovering the globally shared knowledge among clusters. In addition, the sensitivity of complementarity relationship between global and cluster-wise models can be analyzed with respect to warm-up strategies.\n(1-2) This paper stated that the outlier clients have less impact on the global model, thus enabling the less vulnerability of CAM. But the outliers might have less common knowledge with other clients/clusters. Besides, based on the update rules in Eqs. (9)(14), the outliers can also dominate the training of global model, if they have a significantly large number of training samples.\n(1-3) It is more convincing to quantitively evaluate the sensitivity of CAM to initialization, e.g., showing the clustering results with different random initializations in the experiments.\n\n(2) The optimization of IFCA-CAM and FeSEM-CAM is confusing. Algorithm 1 updates the model parameters \\theta_i and \\theta_i^0 (lines 5-6) separately. This might lead to sub-optimal solutions of local objective functions, compared to optimizing \\theta_i and \\theta_i^0 at each training epoch simultaneously. In addition, it is much more efficient to update \\theta_i and \\theta_i^0 together within E training epochs.\n\n(3) Though this paper focuses on clustered FL scenarios, it is better to compare the proposed CAM framework with other related FL frameworks. This is because learning the shared knowledge with a global model is a common strategy for personalized FL. For example, when each client is considered as a single cluster, the objective function of CAM is similar to [ref 1] and [ref 2]. In addition, the state-of-the-art pFL baselines based on feature sharing can be included to validate the performance of CAM.\n\n(4) The convergence analysis of CAM is provided based on the assumption that clustering remains stable during training. But the results in subsection 5.2 might not validate the clustering stability. This is because Figures 1&3 provides the clustering results using only cluster size. It is not guarantee that clients in each cluster remains the same during training. More quantitively evaluations could be provided to verify the quality and stability of clustering in CAM. \n\n[ref 1] Deng, Yuyang, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. \"Adaptive personalized federated learning.\" arXiv preprint arXiv:2003.13461 (2020).\n[ref 2] Mansour, Yishay, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. \"Three approaches for personalization with applications to federated learning.\" arXiv preprint arXiv:2002.10619 (2020).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your suggestions and positive comments regarding our 'novel framework,' 'flexible framework,' and 'better empirical performance.' Below, we provide responses to the weaknesses and questions in your comments. Should you have additional questions, we are readily available for further discussion.\n\n\n### Weakness Clarifications\n***W1 (1-1) One concern is whether the global knowledge shared by all clients always exists in any non-IID FL settings?***\nAs a fundamental assumption of most FL methods, we assume that there always exists some shared global knowledge. This holds true in practice since FedAvg usually sets up a reasonably good baseline. Most non-IID FL works address non-IID challenges by finetuning a personalised model based on a global model. The raised concern is out of the scope of FL research.\n\n***W1 (1-2) the outliers can also dominate the training of global model, if they have a significantly large number of training samples***\nOur method CAM can handle outliers as long as they are the minority of the training set. If the outliers become the majority, they are not outliers anymore. \n\n***W1 (1-3) It is more convincing to quantitively evaluate the sensitivity of CAM to initialization, e.g., showing the clustering results with different random initializations in the experiments.*** \nWe already reported the results with different random initializations in Table 1-2: the \"Test results (means$\\pm$std)\" are based on 5 random seeds. Moreover, as demonstrated by the low stand deviation, integrating CAM with existing clustered FL methods (e.g. IFCA and FeSEM) can enhance the stability. We will further clarify it in the next version. \n\n\n***W2 Why warmup and alternative optimization?***\nBoth our convergence analysis and experiments demonstrate CAM's advantages over existing methods when using the warmup strategy and alternative optimization. In Fed-CAM algorithm, $\\theta_i$ and $\\theta_i^0$ are two different models that need to be optimized separately in parallel. They contribute to cluster-specific models and global models respectively. Updating $\\theta_i$ and $\\theta_i^0$ together without warmup degrades the performance as shown in Table 1 of the attached PDF in the general response. Moreover, it doubled the parameters to be trained at the same time, which is inefficient.\n\n***W3 Similarity to APFL and MAPPER?***\nThe methods of APFL [ref1] and MAPPER [ref2] interpolate between global and local model parameters, while CAM adds the outputs of global and cluster models as the final predictions. These are very different model architectures leading to different learning algorithms.  \n\nWe compared to pFL methods such as finetuning in Section 2.2 of Supplementary Material and we will add more in the next version. \n\n***W4 Clustering stability analysis***\nThe clustering converges fast as shown in Fig 1 of the attached PDF in the general response: Clients belonging to each cluster remain the same after a few global rounds.\n\n### Question Clarifications\n***Highly-skewed clustering analysis***\nFig 2-3 of the attached PDF in the general response show that CAM still performs well under highly-skewed clustering. \n\n***Warmup strategy*** \nIFCA and FeSEM need different warmup strategies because they are initialized in different ways. The rule of thumb is to train the uninitialized models among the global model $\\Theta_g$ and cluster models $\\Theta_{1:K}$ by warmup stage. For example, IFCA initializes $K$ cluster models so IFCA-CAM's warmup needs to prepare a good global model. In contrast, for FeSEM initializing with $m$ client models whose aggregation already defines a global model, FeSEM-CAM's warmup should prepare $m$ client models for a better clustering.\n\n***Dataset partition and chosen of $\\lambda$*** \nWe split each client's local dataset into disjoint training, validation and test sets with a ratio of $6:2:2$ and tune $\\lambda$ based on the validation set performance.\n\n***Typos*** \nWe will correct typos raised in Questions 2, 3, 4, and 6. FedAlt was proposed in the same paper as FedSim.\n\n***Limitations***\nWe have discussed the limitations of our methods in the later paragraph of Introduction. \n\n[ref 1] Deng, Yuyang, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. \"Adaptive personalized federated learning.\" arXiv preprint arXiv:2003.13461 (2020). \n\n[ref 2] Mansour, Yishay, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. \"Three approaches for personalization with applications to federated learning.\" arXiv preprint arXiv:2002.10619 (2020).\n\nPlease let us know if you have any further questions. If our responses have sufficiently addressed your concerns, it would be great if you are willing to reconsider your score kindly. Thank you!\n\nBest,\nAuthors"}, {"review_id": "ENc4VfEwm6", "reviewer": "Reviewer_VZR1", "summary": "In this paper, the authors study heterogeneous federated learning, an important problem in federated learning, where the goal is to leverage the collective intelligence of multiple clients with diverse data distributions, features, or models to train a global model that can generalize well across all clients' data. In particular, the authors base their method on clustered federated learning and propose Clustered additive modeling to deal with the clustering collapse and dynamically changing models. The proposed method involves training a shared global model on top of cluster-specific models, and prediction results are obtained by combining the outputs from both the global model and the associated cluster model. Empirical results on two well-known datasets show the effectiveness of the proposed method.", "questions": "Questions for authors:\n1. It is unclear which part of the structural clustering leads to the final good performance, as there are several hyper-parameters and assumptions in cluster generation. For example,\n\t1) How does the number of rounds for warm-up affect the quality?\n\t2) Can we dynamically adjust the cluster size K based on some coarse-to-fine heuristic?\n\t3) Can the proposed method be generalized to handle graph data?\n\n2. More existing methods could be compared under more non-iid settings as well as iid settings. For example,\n\t1) more Distribution-based label imbalance setting, feature skew case, and label & feature skew case\n\t2) comparison with knowledge transfer-based methods\n\n3. The authors do not include sufficient discussions about the communication and computational cost, which are suggested to be included.", "limitations": "Clustering-based FL approaches have a common limitation that is how to determine the cluster size. Some analysis on this would be desirable in the revision.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strength\n1. The paper writing is clear and easy to follow\n2. The empirical performance seems promising", "weaknesses": "Weakness:\n1. Comparison with other methods under non-iid data setting needs to be improved.\n2. Ablation study on structural clustering needs to be improved. \n3. Fed-CAM introduces several hyper-parameters, including the number of rounds for warm-up, and the number of cluster size K.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback regarding our 'clear writing' and 'promising empirical performance.' Below, we provide our responses to the weaknesses and questions you mentioned in relation to this paper.\n\n***Impact of warmup rounds***\nPlease refer to the general response.\n\n***Extra cost of CAM***\nPlease refer to the general response.\n\n***Chosen of Cluster Size $K$***\nThe hyperparameter of cluster size $K$ is not introduced by CAM. It is from the original clustered FL methods. On one side, experiments of $K=5,10$ have been conducted under the ground truth of $K=10$. On the other side, While CAM can be an add-on to improve the performance of existing clustered FL methods, chosen of cluster size $K$ is also an independent branch to improve the performance. By the coarse-to-fine heuristic, we can set criteria, such as the loss difference between the local model and cluster model, to determine whether some clients need to be separated from a cluster or more clusters are needed.\n\n***More Non-IID Settings, Datasets and Baselines***\nWe have compared the baselines under four non-IID settings, including label imbalance and label skew, and will involve feature skew in future works.\nCAM can be generalized easily to existing FL methods handling graph data as an add-on. And we will involve more knowledge transfer-based methods in future works.\n\nWe have tried to address most if not all concerns. Please let us know if you have any further questions. Thank you!\n\nBest,\nAuthors"}]

Author rebuttal:
## General response
Our proposed method mentioned warmup stage can improve the performance of clustered FL methods, and the framework is flexible to be integrated with existing FL methods. Reviewers show significant interest in these two points by asking for more details and support to these two points. We respond to them by adding two more analyses as below.

***Impact of Warmup Rounds***
As shown in Table 1 below, we gradually increase the rounds of the warmup stage (from 0 to 50) while keeping the total budget of rounds to 100 (warmup + training), considering the limited capacity of computation and communication for local devices in FL. The best performance is achieved when the warmup rounds are set to 20. However, the performance shows minimal variation when the number is set to 10, 20, 30, or 40. It demonstrates that the performance is stable when we choose warmup rounds in the area from 10 to 40. The choice of warmup round numbers exhibits low sensitivity, like on the parameter plateau.

Notably, with no warmup rounds, performance is substantially decreased due to the impact of worse-performed initial candidates of the FL system. Similarly, when the warmup rounds are increased to 50, indicating insufficient training, the performance will drop accordingly. We need to ensure there are enough training rounds with a proper number of warmup rounds.

In summary, a few warmup rounds can improve the stability of FL optimization and accuracy-related performance. Given a proper area, choosing warmup rounds is low sensitivity to performance.  

***Extra Cost of integrating proposed CAM framework to existing FL methods***
For simplicity, we use 'FedAvg' as the measuring unit or benchmark for the cost of storage, communication and computation on local devices. In general, CAM will bring one extra 'FedAvg' cost to the existing FL methods every communication round.

As for IFCA [ref 1], which needs to transmit $K$ cluster-specific models to each client to compute the clustering, applying our proposed CAM framework with IFCA, we need to transmit $K$ cluster models and one extra global model to the clients, that is $K+1$ models in total. The communication cost and storage cost are listed in Table 1. Moreover, the warmup stage only incurs one 'FedAvg' cost. Therefore, integrating CAM can even reduce the overall cost by increasing the number of warmup rounds.

Lastly, considering the tradeoff between performance and cost, we choose 30 warmup rounds out of 100 as the default experiment setting.

**Table 1**: Ablation study of warmup round numbers for performance and cost using "FedAvg" as the measuring unit (Other settings: CIFAR-10 dataset, IFCA, client-wise non-IID with Dirichlet distribution $\alpha = 0.1$, Cluster number $K=10$). For more details, please refer to Table 1 of the attached PDF.

| Baseline | # Warmup + Training |  Accuracy/% |  Macro-F1/% | Storage cost/'FedAvg' | Communication cost/'FedAvg' | Computation cost/'FedAvg' |
|:--------:|:-------------------:|:---------:|:---------:|:------------:|:------------------:|:----------------:|
|   IFCA   |        0+100        |   47.62   |   23.36   |      **10x**     |         10x        |        10x       |
| IFCA-CAM |        0+100        |   63.75   |   32.17   |      11x     |         11x        |        11x       |
| IFCA-CAM |        10+90        |   72.69   |   41.24   |      11x     |         10x        |        10x       |
| IFCA-CAM |        20+80        | **73.83** | **44.72** |      11x     |         9x         |        9x        |
| IFCA-CAM |      **30+70**      |   72.54   |   42.86   |      11x     |         8x         |        8x        |
| IFCA-CAM |        40+60        |   72.98   |   42.20   |      11x     |         7x         |        7x        |
| IFCA-CAM |        50+50        |   65.74   |   26.63   |      11x     |       **6x**       |      **6x**      |


[ref 1] 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.

Meta-review: This paper introduces a novel approach to federated learning, termed "clustered additive modeling" (CAM), which incorporates a structured prediction framework for individual clients. CAM combines the predictions of a global model with those of locally trained models within specific client clusters. This modification represents an enhancement over existing clustered federated learning techniques, as it successfully mitigates several critical challenges commonly associated with these methods. The paper demonstrates that CAM effectively addresses these issues across various clustered federated learning methods operating in diverse non-IID (non-identically distributed) scenarios, consistently yielding promising improvements.

This paper addresses a critical issue in clustered federated learning, known as "clustering collapse," which has been widely observed but not thoroughly explored or resolved previously. The paper's contribution is expected to be highly beneficial and influential in the field of federated learning, particularly in studying statistical heterogeneity and client structures. The motivation behind this research is clear, and the proposed solution through clustered additive modeling is both fundamental and effective. Nevertheless, one reviewer has concerns on the performance of the algorithms when there exist significant amount of outliers in the network, which potentially break the assumptions in the paper. While this scenario can be potentially considered as future works, I would suggest the authors add discussions in the method limitation section. Overall, I recommend acceptance of this paper.
Decision: Accept (poster)