Provably Personalized and Robust Federated Learning
Authors: Mariel Werner
Lie He
Michael Jordan
Martin Jaggi
Sai Praneeth Karimireddy
Venue: Accepted by TMLR ()

Abstract: Clustering clients with similar objectives and learning a model per cluster is an intuitive and interpretable approach to personalization in federated learning. However, doing so with provable and optimal guarantees has remained an open challenge. In this work, we formalize personalized federated learning as a stochastic optimization problem. We propose simple clustering-based algorithms which iteratively identify and train within clusters, using local client gradients. Our algorithms have optimal convergence rates which asymptotically match those obtained if we knew the true underlying clustering of the clients, and are provably robust in the Byzantine setting where some fraction of the clients are malicious.

Published in Transactions on Machine Learning Research (11/2023)
Provably Personalized and Robust Federated Learning
Mariel Werner
Department Electrical Engineering and Computer Sciences, University of California, Berkeley
Lie He
Machine Learning and Optimization Laboratory (MLO), EPFL, Switzerland
Michael Jordan
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley
Martin Jaggi
Machine Learning and Optimization Laboratory (MLO),
EPFL, Swiitzerland
Sai Praneeth Karimireddy Department of Electrical Engineering and Computer Sciences, University of California, Berkeley
Reviewed OpenReview: https: openreview. net/ forum? id= BOBBSSU0G
Abstract
Clustering clients with similar objectives and learning a model per cluster an intuitive and interpretable approach to personalization in federated learning. However, doing so with provable and optimal guarantees has remained an open challenge. In this work, we formalize personalized federated learning stochastic optimization problem. We propose simple clustering-bast based algorithms which iteratively identify and train within clusters, using local client gradients. Our algorithms have optimal convergence rates which asymptotically match those obtained if we knew the true underlying clustering of the clients, and are provably robust in the Byzantine setting where some fraction of the clients are malicious.
1 Introduction
We consider the federated learning setting in which there are N clients with individual loss functions {fi hi who seek to jointly train a model or multiple models. The defacto algorithm for problems in this setting is FedAvg (MeMahan et al. 2017) which has an objective of the form
EEEC M(x).
FodlAv
arg -aaggimn min #EX KE[N]
From [1. that FodAvg optimizes the average of the client losses. In many real-world cases however, clients" data distributions are heterogeneous, making such approach unsuitable since the global optimum I may be very far from the optima of individual clients. Rather, we want algorithms which identify clusters of the clients that have relovant data for each other and that only perform training within cach cluster. However, this is a challenging exercise since 1) unclear what it means for data distributions of two clients to be useful for each other, or 2) how to automatically identify such subsets without expensive multiple retraining (Zamir et al., 2018). In this work we propose algorithms which iteratively and simultaneously 1) identify K clusters amongst the clients by clustering their gradients and 2) optimize the clients' losses within each cluster.

---

Published in Transactions on Machine Learning Research (11/2023)
1.1 Related Work
Personalization via Clustering. Personalization in lederated learning has recently enjoyed Tremendous
attention (see TTan et al. (2022); Kulkarni et al. (2020) for surveys). We focus on gradient- based clustering
methods for personalized federated learning. Several recent works propose and analyze clustering methods.
Sattler et al. (2021) alternately train global model with PedAvg and partition clients into smaller clusters based on the global model's performance on their local data. Mansour et al. (2021) and Ghosh et al. (2020) instead train personalized models from the start (as we do) without maintaining a global model. They iteratively update K models and, using empirical risk minimization, assign each of N clients one of the models al every step. In Section 2 we analyze these algorithms on constructed examples and in Section 3. 1.3 compare them to our method.
Since our work is closest to Ghosh et al. (2020). we highlight key similarities and differences. Similarities: 1) We both design stochastic gradient descent- and clustering-based algorithms for personalized federated learning. 2) We both assume sufficient intra-cluster closeness and inter-cluster separation of clients for the clustcring task (Assumptions 1 and 2 in their work; Assumptions and 5 in ours). 3) Our convergence rates both scale inversely with the number of clients and the inter-cluster separation parameter A. Differences: 1) They assume strong convexity of the clients' loss objectives, while our guarantees hold for all smooth (convex and non-convex) functions. 2) They cluster clients based on similarity of loss-function values whereas we cluster clients based on similarity of gradients. We show that clustering based on loss-function values instead of gradients can be overly sensitive to model initialization (see Fig. 1b). 3) Since we determine clusters based on distances in gradient space, we are able to apply an aggregation rule which makes our algorithm robust to some fraction of malicious clients. They determine cluster identity based on loss-function value and do not provide robustness guarantees.
Recently, Even et al. (2022) established lower bounds showing that the optimal strategy is to cluster clients who share the same optimum. Our algorithms and thcorctical analysis are inspired by this lower-bound, and our gradient-based clustering approach makes our algorithms amenable to analysis à la their framework.
Multitask learning. Our work is closely related to multitask learning, which simultaneously trains sep- arate models for sifferent-but-relen tasks. [Smith et al.] (2017) and Li et al. (2021) both cast personalized federated learning as a multitask learning problem. In the first, the per-task models jointly minimize an objective that encodes relationships between the tasks. In the second, models are trained locally (for per- sonalization) but regularized to be close to an optimal global model (for reskteelat)d These settings are quite similar to our setting. However, we use assumptions on gradient (dis)similarity across the domain space to encode relationships between tasks, and do not maintain a global model.
Robustness. Our methods are provably robust in the Byzantine [Lmport et al. 2017] setting, where clients can make arbitrary updates to their gradients to corrupt
2019
Blanchard et al. the training pro-
Yin et al.; 2018 2022) propose aggregation rules in lieu Damaskinos et al. 2018 Guerraoui & Rouault 2018 Pilluula et al.
oess. Several works on Byzantine robust distributed optimization
[Blanchard et al.]
2017
(2000) show that these of averaging step towards robustness. However, Baruch et al. [2019] Xie et al.
rules are not in fact robust and perform poorly in practice. Karimireddy et al. 2021 are the first to provide provably Byzantinc-robust distributed optimization framework by combining novel aggregation rule with momentum-based stochastic gradient descent. We use a version of their centered-clipping aggregation rule to update client gradients. Due to this overlap in aggregation rule, components of our convergence results are similar to their Theorem 6. However, our analysis significantly complicated by our personalization and clustering structure. In particular, all non- non-malicious clients in Karimireddy et al. 2021 2022) have the same optimum and therefore can be viewed as comprising a single cluster, whereas we consider multiple clusters of clients (without necessarily assuming clients are i..d. within a cluster). The personalization algorithm in Li et al. (2021) also has robustness properties, but they are only demonstrated empirically and analyzed on toy examples.
Recent Empirical Approaches. Two recent works (Wang et al., 2022 Wu et al. 2023) examine the set- ting in which clients' marginal distributions p(x) differ, whereas most prior work only allows their conditional distributions p(ylz) to differ. One of our experiments (Section 4.1 assumes heterogeneity between clients'
2

---

Published in Transactions on Machine Learning Research (11/2023)
assume heterogeneity only between their conditional distributions. In [aang et al. (2022), the server maintains a global pool modules (neural networks) from which clients, via a routing algorithm, efficiently select and combine sub-modulos to create personalized models that perform well on their individual distributions. Exlending the work Marfoq el al. (2021), Wu et al. (2023) model each client's joint distribution as a mixture of Gaussian distributions, with the weights of the mixture personalized to each client. They then propose federated Expectation- -onirtation-aaimiizatiionn algorithm to optimize the parameters of the mixture model. In general, the contributions and style of our work and these others differ significantly. We focus on achieving and proving optimal theoretical convergence rates which we verify empirically, whereas Wang et al. 2022) and Wu et al. 2023 emphasize empirical application over theoretical analysis.
marginal distributions, while the others (Section 4.2)
1.2 Our Contributions
To address the shortcomings in current approaches, we propose two personalized foderated learning al- gorithms, which simultaneously cluster similar clients and optimize their loss objectives in a personalized manner. In each round of the procedure, we examine the client gradients identify the cluster structure well as to update the model parameters. Importantly, ours is the first method with theoretical guarantees for general non-convex loss functions, and not just restrictive toy settings. We show that our method enjoys both nearly optimal convergence, while also being robust to some malicious (Byzantine) client updates. This is again the first theoretical proof of the utility of personalization for Byzantine robustness. Specifically in this work,
We show that existing or naive clustering methods for personalized learning, with stronger assump- tions than ours, can fail in simple settings (Fig.
We design a robust clustering subroutine (Algorithm 3 whose performance improves with the sep- aration between the cluster means and the number of data points being clustered. We prove nearly matching lower bounds showing its near-optimality (Theorem 2), and show that the error due to malicious clients scales smoothly with the fraction of such clients (Theorem
We propose two personalized learning algorithms (Algorithm 2 and Algorithm 4 which converge at the optimal (LL/Vn,] rate T for stochastic gradient descent for smooth non-convex functions and linearly scale with n,, the number of clients client i's cluster.
We empirically verify our thcoretical assumptions and demonstrate experimentally that learning algorithus benefit. from collaboration, scale with the number of collaborators, are competitive with SOTA personalized federated learning algorithms, and are not sensitive to the model's initial weights (Section 4
2 Existing Clustering Methods for Personalized Federated Learning
Our task at hand this work simultancously learn the clustoring structure amongst clients and minimize their losses. Current methods do not rigorously check similarity of clients throughout the training process. Therefore they are not able to correct for early-on erroneous clustering (e.g. due to gradient stochasticity, model initialization, or the form of functions far from their optima). In the next section we demonstrate such failure modes of existing algorithms.
2.1 Failure Modes of Existing Methods
The first algorithm we discuss, Myopic- in order to motivate the design of our method (Algorithm 2 In particular, it is a natural first step towards our method, but has limitations which we correct when designing our algorithm.
Myopie-Clustering, Clustcrinn,, docs not appear in the cxisting literature, but we create it
Myypic-CCustering (Algorithm 1 At every step, each client computes their gradient at their current model and sends the gradient to central server. The server clusters the gradients and sends each cluster
3

---

Published in Transactions on Machine Learning Research (11/2023)
0.6
X1.0
0.5
4-
f2
0.4
3-
f1
0.3-
f
2-
X
0.2-
X1,0
=2,00
f
X2,0
f
0.0
-0.5
0.0
0.5
1.0
1.5
2.0
2.5
-2
0.5
0.5
(a) Myopic-Clustering
Clustering
(b) LFCA/HypCluster.
(c) Clustered Federated
(1) 0.5). Correct clustering:
Correct clustering: (1), (2). Both clients' function values are smaller initialization point 22.0 than 21,0 cansing
Learning. Correct clustering:
[1. and [3]. Client (2) gets stuck
(1}, (2,3) (client 3 not drawn due stochastic gradient details on pg. 5). Clustered FL averages gradients of clients {1} and {2)
not reaching its optimum, and clients {1,3} converge to their optima. All gradients being 0 at this point, the clients are incorrectly clustered together: 21,
IFCA/ HCy//HyCluster to initially cluster them together. Since the average of the clients' gradients at 22,0 is O, the models never update and the algorithm thinks initial erroneous clustering, {1,2) is correct.
0, clustering them together, and with non-O probability clusters (3) separately due to its stochastic gradient. Based on this initial erroneous, the algorithm partitions the clients {1, 2] and each
[3] and recursively group, never recovering the correct clustering.
Figure 1: We show how existing personalized FL. algorithms miscluster and fail to converge constructed examples.
center to the clients assigned that cluster. Each client then performs a gradient descent update on their model with their received cluster center. This is natural federated clustering procedure and it is communication-eficiien (O(N)). However, it has two issues: 1) If it makes clustering mistake at one step, models will be updated with the wrong set of clients. This can cause models to diverge from their optima, gradients of clients in the same cluster to drift apart, and gradients of clients in different clusters to drift together, thus obscuring the correct clustering going forward. Furthermore, these errors can compound over rounds. 2) Even if Myopic-Clusterin clusters clients perfectly at each step, the clients' gradients will approach zero as the models converge to their optima. This means that clients from different clusters will appear to belong to the same cluster as the algorithm converges and all clients will collapse into a single cluster. The following example (Fig, Ia] demonstrates these failure modes of Myopic-Clusterii
Let N = 3 and K = 2, with client loss functions
(x( = 12
6r)
4(x 1)3 3(x 1) +1
x x<1 x 1,
fa(x) =
1 (I 2)2+1
fo(x) 2n 2)
where 7) is the learning rate of the algorithm. With this structure, clients {1, share the same global minimum and belong the same cluster, and client {3) belongs its own cluster. Suppose Myopic- Clustering is initialized at To = 1.5. At step 1, the client gradients computed at 2o = 1.5 are 1/24, 1/24, and -1/2g respectively. Therefore, clients (1,2) are correctly clustered together and client {3} alone at this step.

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 1 Myopic-Clusterin
Input Learning rate: 7). Initial parameters: {21,0 = IN,0 zo}.
1: for round t E [T]] do for client i in [N] do
2:
3:
Client i sends 96(21,--1 to server.
Server clusters (9. generating cluster centers (vK,e)k((RT.
Server sends U to client i, where k denotes the cluster to which client i is assigned.
Client i computes update: Fi,e
Ti,t-1 1
7: Output: Personalized parameters:
ZNTT)
After updates, the clients' parameters will next be æ1,1 = 1,32,1 1, respectively. At this point, clients (2 will be incorrectly clustered together since their gradients will both be 0, while client {1} will be clustered alone. As the algorithm procoeds, clients {2,3] will always be clustered together and will remain at x = 1 and z = 2 respectively, while client {1} will converge to its optimum at I = 0. Consequently, two undesirable things happen: 1) Client {2) gets stuck at the saddle point at x = which occurred when it was incorrectly clustered with client {3} at t= and subsequently did not recover. 2) All gradients converge to 0, so the end of the algorithm all clients are clustered together.
To further motivate the design choice for our algorithms, we now discuss three clustering- based algorithms in the literature on personalized federated learning. In particular, we generate counte-exxmples on which they fail and show how our algorithm avoids such pitfalls.
The first two algorithms IFCA (Ghosh et al. 2020) and HypCluster MMansorr et al, 2021 closely related. They both cluster loss function values rather than gradients, and like our algorithm they avoid the myopic nature of Syoopi-CClusterigg by, at each step, computing all client losses at all current cluster parameters to determine the clustering. However, as we show in the next example (Fig. lb they are brittle and sensitive to initialization.
IFCA Ghosh et al.] 2020). Let N 2, K with loss functions
fx = (x + +-5))² fa(x) (x - 00.))²
and initialize clusters and at #1,0 = -.5 and I2,0 = 0 respectively. Given this setup, both clients initially select cluster since their losses 22,0 are smaller than 01,0-
Option I: At 22,0 O, the client gradients will average to 0. Consequently the models will remain stuck at their initializations, and both clients will be incorrectly assigned to cluster 2.
Option II: Both clients individually run steps of gradient descent starting at their selected model 22,0 (i.e. perform the LocalUpdate function in line of IFCA). Since the clients' individually updated models will be symmetric around 0 after this process, the server will compute cluster 2's model update in line 15 of IFCA as: F2,1 + I2,0- Consequently, the outcome is the same as in Option I: the models never update and both clients are incorrectly assigned to cluster 2.
HypCluster (Mansour et al. 2021 This algorithm is centralized version of Option II of IFCA. The server alternately clusters clients by loss function value and runs stochastic gradient descent per-cluster using the clients' data. It performs as Option II of IFCA on the example above.
Finally, we discuss Clustered Federated Learning, the algorithm proposed Sattler (2021), which runs the risk of clustering too finely, in the next example (Fig. 1cl.
Clustered Federated Learning (Sattler et al., 2021 Clustered Federated Learning operates by recursively bi-partitioning the set of clients based the clients' gradient values at the FedAvg optimum.
5

---

Published in Transactions on Machine Learning Research (11/2023)
Consider the following example. Let N 3 and K = with client gradients
(2) =
92(x) = I - 1/2
x
w.p. 1/2
ga(z)
x x--1 w.p. 1/2.
Therefore the correct clustering here is {1} and [2,3]. The FedAvg optimum is FedAAv 1/4, at which the clients' gradient values are 91 (1/4) = 1/4, 92 = -/aa and 93 = 1/4 w.p. 1/2. Based on this computation, Clustered Federated Learning partitions the client set into [1 and (3} w.p. 1/2 and then proceeds to run the algorithm separately on cach sub-cluster. Therefore, the algorithm never corrects its initial error in separating clients {2] and {3).
The behaviour of these algorithms motivates our method Cheerated-Clusteinggg. which by rigorously checking client similarity at every step of the training process can recover from past clustering errors.
3 Proposed Method: Federated (Algorithm 2)
At a high level, Federated-Chustering works follows. Each client i maintains a personalized model which, at every step, it broadcasts to the other clients j * i. Then each client j computes its gradient on clients i's model parameters and sends the gradient to client i. Finally, client i runs a clustering procedure on the received gradients, determines which other clients have gradients closest to its own at its current model, and updates its current model by averaging the gradients these similar clients. By the end of the algorithm, ideally each client has model which has been trained only on the data of similar clients.
The core of -lisstrrd- is a clustering procedure, Threshold-Cluste tifics clients with similar gradients at each step. This clustering procedure, which we discuss in the next section, has two important properties: it is robust and its error rale is near-optimal.
(Algorithm 3), which iden-
Notation. For arbitrary integer N, we let [N] = {I...,, We take Z b to mean there is sufficiently large constant e such that a 2 cb, a S b to mean there is a sufficiently small constant such that S cb, and a R to mean there is a constant such that a = cb. We write ~ j if clients i and j belong to the same cluster, Lid. j if they belong to the same cluster and their data is drawn independently from identical distributions (we will sometimes equivalently write 2; Lid. Zj, where 2; and æj are arbitrary points drawn from clients i's and j's distributions), and + j if they belong to different clusters. For two different clients and j, same cluster or not, we write # j. Finally, n, denotes the number of clients in client i's cluster, 6; = ni/N denotes the fraction of clients in client i's cluster, and B denotes the fraction of clients that are malicious from client i's perspective.
3.1 Analysis of Clustering Procedure
Given the task of clustering N points into K clusters, at step our clustering procedure has current estimates of the K cluster-centers, U1, UKJ- To update each estimate V4,441 + UR,,, it constructs a ball of radius Tk. around Ug.-- If a point falls inside the ball, the point retains its value; if it falls outside the ball, its value is mapped to the current cluster-center estimate. The values of all the points are then averaged to set 44,41 (update rule (4)). The advantage of this rule is that is very conservative. If our algorithm is confident that its current cluster-center estimate is close to the true cluster mean (i.e. there are many points nearby), it will confidently improve its estimate by taking a large step in the right direction (where the step size and direction are determined mainly by the nearby points). If our algorithm is not confident about being close to the cluster mean, it will tentatively improve its estimate by laking small step in the right direction (where the step size and direction are small since the majority of points are far away and thus do not change the current cstimate).
To analyze the theoretical properties of this procedure, we look at natural setting in which clients within the same cluster have i.dd. data (for analysis of our federated learning algorithm, we will relax this strong

---

Published in Transactions on Machine Learning Research (11/2023)
notion of intra-cluster similarity). In particular, in our setting there are N points {z1..., ... which can be partitioned into K clusters within which points are i.i.d.. We assume the following.
Assumption 1 (Intra-cluster Similarity): For all i
s.i.d 21
2j.
Assumption 2 (Inter-cluster Separation): For all i + j:
E2; - E2yl 2 A2
Assumption 3 (Bounded Variance): For all Zi;
B|i - E2, E 5
Theorem 1. Suppose there N points (ziheNN for which Assumptions [1-3] hold with inter-cluster seporation parameter 2 0/8.. Running Algorithem for
log(%/a)
12 max
1. max
iE[N] log(1 (1 - -6/22)
steps with fraction of malicious clients B, S o, and thresholding radius T Vo,oA guarantees that
o² +
0
El E2ill
n2 A B.A..
(2)
Proof. See A.1
Supposing Br O, if we knew the identity of all points within z,'s cluster, we would simply take their mean as the cluster-center estimate, incurring estimation error of d²/n, (i.e. the mean's variance). Since we don't know the identity of points within clusters, the additional factor of '²/a in (2) the price we pay learn the clusters. This additional term scales with the difficully of the clustering problem. If true clusters are well-separated and/or the variance of the points within each cluster is small (i.e. A is large, o² is small), then the clustering problem is easier and our bound is tighter. If clusters are less well-separated and/or the variance of the points within each cluster is large, accurate clustering is more difficult and our bound weakens.
Sctting To achieve the rate in (2), we set VoA, which is the geometric mean of the standard deviation, a, of points belonging to the same cluster and the distance, A, to different cluster. The intuition for this choice is that we want the radius for each cluster to be at least as large as the standard deviation of the points belonging to that cluster in order to capture in-cluster points. The radius could be significantly larger than the standard deviation A is large, thus capturing many non-cluster points as well. However, the conservative nature of our update rule (4) offsets this risk. By only updating the center with step-size proportional to the fraction of points inside the ball, limits the influence of any mistakenly captured points.
Threshold- Threshold-Clusteriing has two important properties which we now discuss: it is Byzantine robust and has a near-optimal error rate.
3.1.1 Robustness
We construct the following definition to characterize the robustness of Algorithm 3
Definition 1 (Robustness). An algorithm A is robust if the error introduced by bod clients be bounded i.e. malicious clients do not have an arbitrarily large effect on the converyence. Specifically, for specific
objective, let EN be the base error of A with no bad clients, let 3 be the fraction of bad clients, and let Eg be some bounded error added by the bad points. Then A is robust if
Err(A) S E1 3E2.

---

Published in Transactions on Machine Learning Research (11/2023)
Threat model. Our clustering procedure first estimates the centers of the K clusters from the N points and constructs ball of radius тh around the estimated center of each cluster k. Tf a point falls inside the ball, the point retains its value; it falls outside the ball, its value is mapped to the current cluster-center estimate. Following the update rule I the values all the points are averaged to updale the cluster-center estimate. Therefore, a bad point that wants to distort the estimate of the k'th cluster's center has the most influence by placing itself just within the boundary of the ball around that cluster-center, icc at 7x-distance from the cluster-center.
From 2 we see that the base squared-error of Algorithm estimating z cluster-center is S 5//n + f and that the bad points introduce extra squared-error order oλ. Given our threat model, this is exactly expected. The radius around 2 cluster-center is order VoA. Therefore, bad points placing themselves the edge of the ball around 2 cluster-center estimate will be able to distort the estimate by order aλ. The scaling of this extra error by & satisfies our definition of robust and the error smoothly vanishes as B + O.
3.1.2 Near-Optimality
The next result shows that the upper bound on the estimation error of Algorithm 3 nearly matches the best-achievable lower bound. In particular, tight within factor of c/a.
Theorem (Near-oplimaliity of Threshold-CCusstrinng For any olgorithm A, there erists a minture of distributions D1 = (μr o²) and D2 = (12, o²) with || H2ll 2 A such that the estimator ai produced by A
has error
0 a²) A
ElIA1 21 2 Ω
74
Proof. See A.2
3.1.3
Gederated-Clusterrin on Examples Section 2.1
We describe how Sederated-Clusteriie successfully handles the examples in Section 2.1
Fedderated-Clusteriin checks at every step the gradient values of all N clients at the current parameters of all K clusters. This verification process avoids the type of crrors made by Myopic- Clustering. For instance, at f = when Myopic-Clustering makes its error, Federated--husttering computes the gradients of all clients at client {1)'s current parameters: 91 (1) = 1/3n. g2(1) = O, and ga(1) = 1//p. Therefore correctly clusters (1,2) together at this point, and client {2)'s parameters update beyond the saddle-point and converge to the global minimum at 0.
Example 1: Fig. la
Example 2: Fig. lb By clustering clients based on gradient instead of loss value, Federated- Federated--Clusteringg initially computes the clients' gradients of +1 and -1 respectively 22,0 0, and given the continued separation of their gradients around as the algorithm converges, correctly identifies that they belong to different clusters.
Example Fig. 1c Recall how Clustered FL fails on this example. Based on an initial clustering error, it partitions the clients incorrectly early and then evaluates cach subset separately going forward, thus never recovering the correct clustering. Our algorithm avoids this type of mistake by considering all clients during each clustering at every step.
3.2 Analysis of Federated- Cederated-Clusttrrig
We now proceed with the analysis of Federated- Srrratted-Clustringgg First, we establish necessary assumptions: intra- cluster similarity, inter-cluster separation, bounded variance of stochastic gradients, and smoothness of loss objectives.
8

---

Published in Transactions on Machine Learning Research (11/2023)
Assumption 4 (Intra-cluster Similarity): For all i ~ j. and some constant A 2 0,
[V) V[())l) & A
where M1x)) _ Ex)e)())).
Assumption 5 (Inter-cluster Separation): For all x, i +f j, and some constants A, D20, 0,
(V V 2 A {
This formulation is motivated by the information theoretic lower-bounds of Even et al. (0022 who show that the optimal clustering strategy is to group all clients with the same optimum (even they are non-iid). Assumptions 4 and 5 are in fact slight strengthening of this very statement. To see this, note that for a client with loss function fi)),, belonging to cluster fi(z) with first-order stationary points x², Assumption implics that if fz(*)) 0 = Vf((²*) O, and so Æ" is also stationary point for client i. Thus, all clients within a cluster have shared stationary points. Assumption 4 further implies that the gradient, difference elsewhere away from the optima is also bounded. This latter strengthening is motivated by the fact the the loss functions are smooth, and so the gradicnts cannot diverge arbitrarily as we move away from the shared optima. In fact, is closely related to the strong growth condition (equation (1) in Vaswani et al. (2019) ) which is shown be very useful notion in practical deep learning. We also empirically verify its validity
in Fig. 2 (left).
Similarly, Assumption is a strengthening of the condition that clients across different clusters need to have different optima. For two clients i and j who belong to different clusters and with first-order stationary points z and æj, Assumption implies that [+(]]]] 2 A and [ > A. Thus, they do not share any common optimum. Similar the Assumption 4, Assumption 5 also describes what happens elsewhere away from the optima- it allows for the difference between the gradients to be smaller than A we move away from the stationary points. Again, this specific formulation is motivated by smoothness of the loss function, and empirical validation (Fig. 2 right).
In Corollary I we give a setting and precise A, D, and A for which Assumptions 4 and 5 are satisfied.
Assumption 6 (Bounded Variance of Stochastic Gradients): For all
[x]g.(x) Vf(=))
where [=g]()) Vi(x)) and each client i's stochastic gradients g((x) are independent.
Assumption 7 (Smoothness of Loss Functions): For any x,
[V S((ii) s L||a - yll-
Theorem 3. Let Assumptions [4-7] hold with inter-cluster seporation parameter A 2 max(1, max(1, ya/s.. Under these conditions, suppose we run Algorithm g for T rounds with learning rale 1j S 1/1, fraction of malicious clients 3g S 8,, and batch size |Bal Z min( mmmx111 (1) 0²/a= + 3,0 A ),s mc), where my is the size of client i's training dataset. If, in each round E [T], we cluster with radius T ss Vo,o & for
12 max {
1,x max SEN]
log(1 - 6./2) {
steps, then
T
max(1,
/ o'/o+B,01)) (3) m2x(1,A2)(02/)))
V fo (Zi. (x1--)) R
(3)
T
T
Proof. See
A.3

---

Published in Transactions on Machine Learning Research (11/2023)
We note a few things. 1) The rate in (3) is the optimal rate in T for stochastic gradient descent on non-convex functions (Arjevani et al., 2023 2) The dependence on Vo²/n, is intuitive, since convergence error should increase as the variance of points in the cluster increases and decrease as the number of points in the cluster increases. is also optimal as shown in Even et al. (2022). 3) The dependence on /3,0A is also expected. We choose radius T & VoA for clustering, Given our threat model, the most adversarial behavior of the bad clients from client i's perspective to place themselves at the edge of the ball surrounding the estimated location of i's gradient, thus adding error of order v /3,0.. When there are no malicious clients, this exl.ra error vanishes. 4) If the constraint on batch-size in Theorem requires [B; m,; then the variance of stochastic gradients vanishes and the standard (1/r) rate for deterministic gradient descent is recovered (see equation ( in proof). We also note that as long there are malicious clients (i.e. A term is 0); there are a large enough number of clients n, in the cluster, and inter-cluster separation A is sufficiently larger than the inter-cluster-vee variance o², then minimum-bate size will likely be less than mi.
If losses are smooth and strongly convex, the following convergence rate achievable.
Corollary 1. Suppose client losses are L-smoolh and μ-strongly conver, and that clusters are defined by clients with the same optimum. Specifically, let æt be client i's optimum. Define A max V2 1 V (xt)) and assume losses are such that A 1 If we run Algorithm for T rounds with learning rate n S 1/2, fraction of malicious clients 3, S 8,, batch size |B:l Z min (V( + B, m,
where
m, is the size of client i i's training dataset, and cluster in each round t [T] with radius z vo,0 for
12 max {
max log(%/ (og(%v/B..l)) { SEN] log(1 61/2)
steps, then
1
(LW) + / + 3,0A)
E V (
T
Proof. See|
A.4
Privacy. Since Rederated-Clustering requires clients to compute distances between gradients, they must share their models and gradients which compromises privacy. The focus of our work is not on optimizing privacy, so we accommodate only the lightest layer of privacy for federated learning: sharing of models and gradients rather than raw data. Applying more robust privacy techniques is a direction for future work. In the mcantime, we refer the reader to the extensive literature on diffcrential privacy, multi-party computation, and homomorphic encryption federated learning.
Communication Overhead. At cach step, Fodorated-CChustering requires O(N2) rounds of communica- tion since each client sends its model lo every other client, evaluates its own gradient at every other client 's model and then sends this gradient back to the client who owns the model. We pay this communication price to mitigate the effect of past clustering mistakes. For example, say at one round a client mis-clusters itself and updates its model incorrectly. At the next step, due to communication with all other clients, it can check the gradients of all other clients at its current model, have a chance to cluster correctly at this step, and update its model towards the optimum, regardless of the previous clustering error. Recall on the other hand that an algorithm like Myopic-Clusterin may not recover from past clustering mistakes since it doesn't 't check gradients rigorously in the same way. In algorithm, Commentum-Clusteriin (Algorithm d which clusters momentums instead of gradients (reducing variance and thus clustering error) and requires only O(N) communication rounds per step.
(Alg. [], while communication efficient (N rounds per step),
the next section, we propose more communication-efficion
'The batch-size constraint reduces variance of the stochastic gradients (Lemma 0 In Section 3.3 we propose another algo- rithm Momentum-- Momeatuun-Cuustering for which there is batch-size restriction and which reduces variance by clustering momentums instead of gradients.
2 "9:(#,,-1))
Σ, (:,6,, where gi (2z,111;6) the gradient computed using sample in the batch.
10

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 2 Federated- Federated-Clusterrin
Input Learning rate: 7). Initial parameters for each client: (z1,0 IN,O). Batch-size
[B,] (see Theorem 3
for lower bound this quantity
1: for client i E [N] do
Send 05,0 all clients j + i.
for round [T] do
for client i in [N] do
Compute (T(,)=-1) with batch-size [B; Fad send to client j for all j * [N).
6:
Compute Ci,, t Threshold-Clusterre (angtttrrnnnn(gg..eiaii_. (=)(()))))))))( cluster; : (=(,,,11)).
7: Updale parameter: Fi.t = Fi,t-1 - 1/üi,t
8: Send Z4, to all clients #
Output: Personalized parameters: {-I,T, IN,T)
Algorithm Thhreshol-CClustering
Input Points to be clustered: (N....,,]: Number of clusters: K Cluster-center initializations:
(u1,0, UK,0}
for round E [M]] do
for cluster & in [K] do
Set radius Th.t-
4:
Update cluster-cente estimate:
111 - ux.- S TH.)) + 1 -u.--1ll > Tm.))
UK.T N
(4)
Output: Cluster-center estimates
{U1 M..,, UK UK.M). }.
3.3 Improving Communication Overhead with Momentum
Fedderated-Clusteriin is inefficient, requiring N rounds of communication between clients each step (each client computes their gradient at every other client's parameter). Since momentums change much more slowly from round-to-round than gradients, a past clustering mistake will not have much of a harmful impact on future correct clustering and convergence as when clustering gradients.
In Algorithm | al each slep each client computes their momentum and sends it to the server. The server clusters the N momentums, computes update per-cluster, and sends the update to the clients in each cluster. Therefore, communication is limited to N rounds per step.
3.3.1 Analysis of Momentum- Clastteri--
The analysis of the momentum based method requires adapting the intra-cluster similarity and inter-cluster separation assumptions from before.
Assumption 8 (Intra-cluster Similarity): For all i ~~ and t [T].
i.d. mag
mj.ts
where m,, is defined as in 66
Assumption 9 (Inter-cluster Separation): For all i * and e [T].
||Bm,, - Em,,, A2
Note that the intra-cluster similarity assumption in this momentum setting is stronger than in the gradient setting (Assumption 4): namely require that the momentum of clients in the same cluster be i.i.d. at all
11

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 4 Momentum Nomentum-Chusteringg
Input Learning rate: 7). Initial parameters: {01,0 = IN.O).
1: for round t E [T] do
2:
for client i in [N] do
Client i sends
m4,1 = og( + (1 - a)m,,-11
(6)
to server.
4:
Server generates cluster centers
(UK,CeEERK] +
(m,,,) clusters; (eE,A-IkE((K))
and sends UkAt to client i, where k; denotes the cluster to which i is assigned in this step.
Client i computes update: Zi,t = Ti,-11 7)kk,, 5:
Output: Personalized parameters: {-i,T, [2I,T,,,,N,, IN.T).
points.
This stronger assumption is the price pay for simpler and more practical algorithm. Finally, due the fact that momentums low-variance counterparts of gradicnts (Lemma 13 climinate constraints on the batch size and still achieve the same rate.
Theorem 4. Let Assumptions [6-9] hold with inter-cluster separation porameter A 2 9/6.. Under these
B(((a1))-f1). (fi
conditions, suppose we Algorit/om for T rounds with learning rate S min T [T(e"/u;tt""a)) S
is the global minimum of fi), fraction of bad clients Bi S 8,, and momentum parameter a 2 Lm If. in each round E (T), we cluster with radius T no V for
(gg(vor/)) } iEN] log(1 - 61/2)
1 12 max
1. max
steps, then for all E [N]
T
02 + 0
3,0
E (f(E,
(5)
T
T
T Ti o /2)22
Proof. See A.5
We see from 5 that when there are no malicions clients (3: = 0), Momentum Connentun-Clustering achieves the same /orTT.T convergence rate observed in 33, with no restrictions on the batch size.
4 Experiments
In this section, we first use a synthetic dataset verify the assumptions and rates claimed in our theoretical analysis in the previous section; and second, use the MNIST dataset (LeCun al. 2010) and CIFAR dataset. (Krizhevsky) 2009) to compare our proposed algorithm, Maderaated-Clsteeriggg with existing state-of- the-art federated learning algorithms. All algorithms implemented with PyTorch (Paszke et al. 2017
4.1 Synthetic dataset
Construction of synthetic dataset. We consider a synthetic linear regression task with squared loss for which we construct K = clusters, each with n, = 75 clients. Clients in cluster 1: E [K] share the same minimizer at d For each client in cluster k; we generate sample matrix A; _dxa from A Laxx) and compute the associated target y; AJ x E R". We choose the model dimension d = 10 to be greater A, æ is overdetermined and the than the number of local samples such that the local linear system yi
12

---

Published in Transactions on Machine Learning Research (11/2023)
Intra-cluster var. ratio A
leglnter-cluster var. A
Individual client
1.0
Individual client
Cluster
Cluster
Max=10.2
0.8
Min=2.2e+07
4²
0.6
4
0.4
0.2
0.0
0
20
40
60
80
100
0
20
40
60
80
100
Epochs
Epochs
Figure 2: Here, we show empirically on a synthetic dataset that the intra-cluster variance ratio is upper-bounded by constant (left subplot) and the inter-cluster variance constant (right subplot).
that lower-bounded by
K=4 n, n
K=4 n; 16
K=16 n;
10a
FC
Local
Loss
IFCA-M
Global
10
10-5
0
200
400
600
8000
200
400
600
8000
200
400
600
800
Epoch
Epoch
Epoch
Figure 3: The performance of our algorithm vs. baselines a synthetic dataset. When n, is small, the tround-truth outperforms algorithm, but this difference vanishes with increasing n,, This behavior is consistent with the dependence of the convergence rate on in Theorem 3 increasing n, improves convergence.
error ||-" -x information from other clients j ~ the same cluster.
211 is large. A desired federated clustering algorithm determines the minimizer by incorporating
Estimating constants Assumptions and 5. In Fig. 2
using the above synthetic dataset.
we estimate the intra-cluster variance ratio A by finding the upper bound of
[V)(=) V
(7)
we estimate the inter-cluster variance 2 by setting D = 0 and computing the lower bound
(8)
[V - V (x)
(8)
We run Federated- Serratted-CCustriigggg with perfect clustering assignments and estimate these bounds over time. The result is shown in Fig. 2 where grey lines are the quantitics in and S for individual clients, black lines are those quantities averaged within clusters, and red dashed lines are empirical bounds on the quantities. The left figure demonstrates that the intra-cluster variance ratio does not grow with time and can therefore reasonably be upper bounded by constant A². Similarly, the right figure shows that the inter-cluster variance can be reasonably lower bounded by positive constant A These figures empirically demonstrate that Assumptions 4 and 5 are realistic in practice.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Table 1: Comparison of test losses and accuracies for federated personalization algorithms on MNIST. FC
outperforms all non-oracle baselines on two learning tasks.
Rotation
Private label
A%c.(%)
Loss
Acc.(%)
Loss
Local
71.3
0.517
75.2
0.489
Global
46.6
0.631
22.2
0.803
Ditto
62.0
0.576
61.7
0.578
IFCA
54.6
0.588
65.4
0.531
KNN
52.1
2.395
63.2
1.411
FC (ours)
75.4
0.475
77.0
0.468
GT (oracle)
84.7
0.432
85.1
0.430
Performance. In Fig. 3 we compare the performance of our algorithm Federraeed-Chustrringg (FC) with several baselines: standalone training (Local), IFCA (Ghosh et al.) (020), FedAvg (Global) (McMahan et al. 2017), and distributed training with ground truth (GT) cluster information. We consider the syn- thetic dataset from before, starting with cluster paramcters (K) = (4,4) and observe performance when increasing parameters to 74- 16 and K 16 separately. In each step of optimization, we run Threshold- Clustering for / - 10 rounds so that heuristically the outputs are close enough to cluster centers, cf. Fig. 7 We tune the learning rate separately for each algorithm through grid search, but preserve all other algorith- mic setups. Our algorithm outperforms the non-oracle baselines in all cases. While Pederated-Clusterne slightly worse than ground truth when (K, = (4, 4), their performances are almost identical in the middle subplot for n, 16. This observation is consistent with the ny-scaling observed in 33 as the number of clients-per-cluster increases, convergence improves.
is
4.2 MNIST experiment
In this section, we compare Federated-Chusteriig to existing federated learning baselines on the MNIST dataset. The dataset is constructed as follows, similar to Ghosh et al. (2020). The data samples are randomly shuffled and split into K = 4 clusters with n; = 75 clients in cach cluster. We consider two different tasks: 1) the rotation task transforms images in cluster & by k * 90 degrees; 2) the private label task transforms labels cluster with Te(y)) : y + (y + k mod 10), such that the same image may have different labels from cluster-to-cluster.
A Algorithm hyperparameters. For these two experimental lasks, in addition to the baselines from our synthetic experiment, we include the KNN-personalization (Marfoq et al. 2021 and Ditto (Li et al. 2021
algorithms which both interpolate between & local and global model. The oeN-pprroonalization is a linear combination of global model, trained with FedAvg (McMahan al., 2017). and local model which the aggregation of nearest-neighhor predictions in the client's local dataset to the global model's prediction. We set the coefficients of this linear combination to be Aknn 0.5 and Aknn 0.9 for the rotation and private label tasks, respectively. The Ditto objective is personalized loss with an added regularization term that encourages closeness between the personalized and global models. Since tuning this regularization parameter Adiso Icads to a degenerated 'Local" training where Aditto = 0, we fix Aditto = 1 for both rotation and private label tasks. To reduce the computation cost of our algorithm, in each iteration we randomly divide the clients into 16 subgroups and apply Federated- Caaieeedi--uttniinggg to each subgroup simultaneously. The clipping radius Th for each cluster i is adaptively chosen to be the 20th-percentile of distances to the cluster-center.
Porformance. The experimental results are listed in Table I Since an image can have diffcrent labels across clusters in the private label task, a model trained over the pool of all datasets only admits inferior performance. Therefore, distributed training algorithms that maintain global model, such as FedAvg, Ditto, and KNN, perform poorly compared to training alone. On the other hand, our algorithm Federated- Clustering outperforms standalone training and all personalization baselines. This experiment suggests that our am successfully explored the cluster structure and benefited from collaborative training.
14

---

Published in Transactions on Machine Learning Research (11/2023)
50
(Percentile)
Local Steps
0.25
5
40
0.2
10
Algo.
Accuracy
Accuracy
0.1
Accuracy
20
Ditto
30
0.05
40
FC
0.025
20
Global
Local
10
IFCA
GT
100
25 Epoch
Epoch
Epoch
Figure 4: Performance of algorithms CIFAR-10 dataset with the private labels task. Left: Relative accuracy of clustering algorithms. Algorithms optimized for global model performance, such as Ditto, IFCA, Global (FedAvg), perform poorly on personalization. FC outperforms Local training, showing that it benefits from collaboration between clients, and is competitive with GroundTruth. Middle: Impact of thresholding radius т on accuracy. T is the percentile of gradients distances from the cluster-center. Right: Impact of local gradient steps between two clustering calls. Early on in training, clusters are less identifiable so local optimization helps but these gains lessen later on when gradients from different clusters drift apart and clusters are better defined.
4.3
CIFAR experiment
In this section, we evaluate the efficacy of various clustering algorithms on the CIFAR-10 and CIFAR-100 datasets (Krizhevsky 2009
4.3.1 CIFAR-10
For the 10 experiment, we create 4 clusters, each containing 5 clients and transform the labels in each cluster such that different clusters can have diffcrent labels for the same image (the private label task in Section 4.2 We train VGG-16 model (Simouyan Zisserman 2015) with batch size 32, learning rate 0.1, and momentum 0.9. The outcomes are presented in Fig. [ The left subplot illustrates that collaborative clustering algorithms designed for global model training (e.g., Ditto, IFCA, Global) yield suboptimal models, not all participating clients benefit from each other. On the other hand, Local and GroundTruth train- ing are not influenced by the conflicting labels from other clusters so they significantly outperform Ditto and IFCA. Our Federated- -eaatter--luuteiing (FC) algorithm also excludes such adversarial influence and, more importantly, outperforms Local training, showing that FC benefits from collaboration.
In the middle subplot, examine the impact accuracy of varying the thresholding radius (i.e. 7 is set as the plecentile of gradient distances from the cluster-center, smaller percentile corresponds to smaller r). Our findings indicate that adopting more conservative value for 7 (lower percentile) does not substantially compromise accuracy.
The right subplot demonstrates the behavior of Pederateed-Clustenn intermittently. The results suggest that increasing the number of local iterations boosts the learning curve carly in training when gradients from different clusters are close together and clusters are ill-defined. However, this improvement plateaus when gradients become separated and clusters become well-defined.
when the clustering oracle is invoked
4.3.2 CIFAR-100
We consider the CTFAR-100 dataset distributed over 10 clusters so that each cluster contains 10 unique labels. In each cluster, we set 10 clients with IID data. We use a VGG-8 model for training and the same hyperparameters those in the CIFAR-10 experiment (Section 4.3.1 and report the results in Fig, 5 While clients' data within each cluster share similar features, small model like VGG-8 cannot sufficiently benefit
15

---

Published in Transactions on Machine Learning Research (11/2023)
Large gradient attack
Bit-flipping attack
50
Global
Accuracy
Accuracy
Accuracy
30
FC
30
Global
20
20
FC Global
10
0
25
50
75
100
50
100
100
Epoch
Epoch
Epoch
Figure 5: Performance of Federated- Chisttrrid (FC) on the CIFAR-100 dataset. The Global (FedAvg) accuracy plateaus while FC contimually improves.
Figure 6: Performance of -haesstred--llsttiinggg (FC) against a large gradient attack (left) and bit-flipping attack (right). FC is robust to these attacks and significantly outperforms Global (FedAvg) performance.
from intra-cluster collaboration. Therefore the performance of Global training plateaus at very low level while in contrast Iileraated-Cluttrrigg (FC) still benefits from collaboration and continues to improve over time.
4.4 Defense against Byzantine attacks
Byzantine attacks, in which attackers have full knowledge of the system and can deviate from the prescribed algorithm, prevalent in distributed environments (Lamport et al. 2019). There many forms of Byzantine attacks. For example, our private label setting in Sections 4.2 and 4.3.1 corresponds to the label- flipping attack in the Byzantine-robustress literature, since malicious client can try to corrupt the model by assigning the wrong label to an image in training data.
Byzantine workers send either very large gradients gradients with opposite signs. Using the MNIST dataset with the private label task, set 4 clusters with 50 non-malicious clients each (so non-malicious clients from different clusters can have private labels) and add 50 Byzantine works to each cluster. We demonstrate the robustness of Eedeeratdd-Clsteeiin (FC) in Fig. [6] In both cases, Global training suffers from serious model degradation while FC successfully reaches high accuracy under these attacks, demonstrating its robustness.
In this section, we investigate two other attacks:
4.5 Empirical Study on Clipping Iterations in Algorithm
We employ Algorithm 3 (Threhold-Chustering)
datasets to discern the effectiveness of the clipping it- crations in identifying optimal cluster centers. These datasets share the same groundtruth cluster centers, and thus the same A, but vary in their inter-cluster standard deviations, with values of 0.5, 1,2, 4. Each dataset is made up of 90 ten-dimensional samples from 10 clusters, generated using the scikit-learn pack- age (Pedregosa et al., 2011). For cach itcration within cluster k, the clipping radius Tr, is defined as the 10th percentile of gradients' distances from the cluster-center. We repeat this experimental setup len times for consistency.
The outcomes, presented in Fig. show that the average distances initially decrease rapidly, then steadily f()) f(-)-((-1)
approach convergence. To identify the elbow of given curve we use the formula 7(1-1)-min, füj where curves post-elbow are notably flat. These elbows elucidate the correlation between a and I, indicating that for fixed dataset (and its corresponding a), can pinpoint the minimal iterations needed for convergence. Notably, this observation appears to align with the 2 log lower bound stated in Theorem |
16

---

Published in Transactions on Machine Learning Research (11/2023)
20.0
"Elbow" of the curves
Average distance cluster center
17.5
15.0
12.5
std
10.0
0=
0= 1.0
0.5
5.0
2.5
0.0
Number clipping iterations (t)
Figure 7: The average distance to cluster centers function of the number of clipping iterations L. The distance between cluster-centers (A) is fixed while inter-cluster standard deviation a dilfers.
5
Conclusion
We develop gradient-based clustering algorithms to achieve personalization in federated learning. Our algo- rithms have optimal convergence guarantees. They asymptotically match the achievable rates when the truc clustering of clients known, and our analysis holds under light assumptions (e.g,, for all smooth convex and non-convex losses). Furthermore, our algorithms are provably robust the Byzantine setting where some fraction of the clients can arbitrarily corrupt their gradients. Future directions involve developing bespoke analysis for the convex-loss case and developing more communictioon-effiien versions of our algorithms. Further, our analysis can be used to show that our algorithms are incentive-compatibe and lead to slable coalitions as in Donahue & Kleinberg (202I). This would form strong argument towards encouraging participants in federated learning system. Investigating such incentives and fairness concerns is another promising future direction.
References
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. In Mathematical Programming, volume 199, pp. 165 214, 2023.
B. Baruch, M. Baruch, and Y. Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, volume 32, 2019.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainor. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances Neural Information Processing Systems, 30, 2017.
G. Damaskinos, E.M. El-Mhamdi, R. Guerraoui, A. Guirguis, and S. Rouault. Aggregator: Byzantine machine learning via robust. gradient aggregation. Proceedings of Machine Learwing and Systems, 1:81 106, 2018.
Kate Donahue and Jon Kleinberg. Optimality and stability in federated learning: A game-theoretic approach. Aduances in Neural Information Processing Systems, 34:1287-1298, 2021.
Mathieu Even, Laurent Massoulié, and Kevin Scaman. On sample optimality in personalized collaborative and federated learning. Advances in Neural Information Processing Systems, 35:212 12:1122225, 2022.
17

---

Published in Transactions on Machine Learning Research (11/2023)
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586-19577 2020.
Guerraoui and S. Rouault. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning (PMLR), pp. 35213530, 2018.
Sai Praneeth Karimiroddy, Lic Hc, and Martin Jaggi. Learning from history for byzantine robust opti- mization. In Proceedings of the 38th International Conference on Machine Learning, volume 129, pp. 5311 1319,, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In International Conference Learning Representations, 2022.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009. URL https://apt
semanticscholees wwwps/ccchhaa..ooo/oooooeeeoo Orgg/CorpuIID: 18268744
Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. Survey of personalization techniques for federated learning. In 2020 Fourth World Conference on Smart Trends in Systems, Securily and Suslainabibily (WorldS4), pp. 794-797. TEEE, 2020.
L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. In Concurrency: the Works of Leslie Lamport., 2019.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit databasc. ATT Labs [Online]. Available: http:///yaneeecun.coo cow/endll eerdb/mnisl,, 2, 2010.
T. Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Fair and robust federated learning through personalization. In 38th International Conference on Machine Learning, 2021.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personaliza- tion with applications to federated learning. 2021.
Othmane Marfoq, Giovanni Neglia, Lactitia Kameni, and Richard Vidal. Federated multi-task learning under a mixture of distributions. In Proceedings of the 35th International Conference on Machine Learning, volume 34, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Comminieatoon-eficieent learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273- PMLR, 2017.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS- W, 2017.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
K. Pillutla, S. Kakade, and Z. Harchaoui. Robust aggregation for fedorated learning. In IEEE Transactions 2022.
on Signal Processing, volume 70, pp.
Felix Sattler, Klaus-Robert Muller, and Wojciech Samek. Clustered federated learning: Model-agnostic distributed multi-task optimization under privacy constraints. In IEEE Transactions on Neural Networks and Learning Systems, volume 32(8), 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
V. Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet Talwalkar. Federated multi-task learning. In 31st Conference Neural Information Processing Systems, 2017.
18

---

Published in Transactions on Machine Learning Research (11/2023)
Alysa Ziying Tan, Han Yu, Lizhen Cui, and Qiang Yang. Towards personalized federated learning. 1EEE Transactions on Neural Networrs and Learning Systems, 2022.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and laster convergence of sgd for over-parameterized models and an accelerated perceptron. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89, 2019.
Tianchun Wang, Wei Cheng, Dongsheng Luo, Wenchao Yu, Jingchao Ni, Liang Tong, Haifeng Chen, and Xiang Zhang. Personalized federated learning via hetcrogencous modular networks. In IEEE International Conference on Dala Mining, pp. 1197 1202, 2022.
Yue Wu, Shuaicheng Zhang, Wenchao Yu, Yanchi Liu, Quanquan Gu, Dawei Zhou, Haifeng Chen, and Wei Cheng. Personalized federated learning under mixture of distributions. In Proceedings of the 40th International Conference on Machine Learning (PMLR), 2023.
C. Xie, O. Koyejo, and I. Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manip- ulation. In Uncertainty in Artificial Intelligence (PMLR), pp. 261-2700 2020.
Yin, Y. Chon, R. Kannan, and P. Bartlett. Byzantinc-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learving (PMLR), 2018.
Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 3712 3722, 2018.
A Proofs
A.1 Proof of Theorem
1
First. establish some notation.
Notation.
Gj the good points and B, the bad points from point 2,'s perspective. Therefore |9 + [B: N.
ky denotes the cluster to which client i is assigned at the end of Threseold-Clusterrnng
To facilitate the proof, we introduce variable & that quantifies the distance from the cluster- center-estimates to the true cluster means at each step of thresholding. Specifically, for client i's cluster k at round of Wrresold-Chustering we set.
El Ez
For client i's cluster k; at round 1 of Threshold-Cuuserinng we use thresholding radius
T2. =s 22 + 6,0A.
We introduce a variable ya to denote the points clipped by Threshold-Chusteringg
Σ 21( 1R.1-11 S TH.)) + UR.1 [112 Uk.--1ll > Tk.))
JE
19

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Theorem We prove the main result with the following sequence of inequalities, and then justify the labeled steps afterwards
1
Ell B2,11
Σ
Ezy
N
JE[N]
(1 B.)
ViJ
Ezi
+
Bi
1
Σ
EZs) )
[B
JEG.
JEB,
1
1
(1+
3,)
19
Mj.
IEz;
+
33
[Bg]
Σ
Vid
Er;
JEG.
jEB,
3 E
Σ
y3.
+
E
B2;
[g
[
jEB.
jEB,
66)
27
(1- 8,) 0,
+
+
+,, + 6,0
74
A
(88
022
03
x (1 c/2)ch..1
+
1,0A)
111
A
(1)
002
03
2 (1 4/2)/
+ BIOA
1(1 (1 61--//2))
11
A
02 o3
S 61/2 02 +
+ B10
n1
(n4) 0²
n4 A + 3.A.
(9)
Justifications for the labeled steps are:
ii) Young's inequality: ||> + y11 e1x) +
1/Dlll1 for any O.
(ii) We prove this bound in Lemmas and 5 Importantly, it shows that the clustering error is composed of two quantities: ε,, the error contributed by good points from the cluster's perspective, and Eg, the error contributed by the bad points from the cluster's perspective.
(iii) Assumption that 3i $ 8;
(iv) Since E| E2 = oh 141 the inequality forms a recursion which we unroll over / steps.
(v) Assumption that E.,1 El Ezzl1 o². Also, the partial sum in the second term be upper-bounded by largo-enough constant.
(vi) Assumption that 1 2 max {
log(*/a) 1og(1-41/2)
From 9 we see that 22, S g"
I + B.o.. Plugging this into the expression for =h,1 gives Than
+ 5,0 z A for large n4 and A.
Lemma 1 (Clustering Error due to Good Points).
( 1 E
o²
3
E
Ez,
$ (1
(1-
+
C. jES.
n4
A
20

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemmal 1 We prove the main result with the following sequence of inequalities and justify the labeled steps afterward.
IB
1 9i
Σ jEG.
E2,
(Uht (aal)))) E3,)) +
(W5 -Ezs)
)l
Gil
Gi
jESC:jo
2 E.
6e 2
1 +
(Uyl - R2y))
+
1
+
E
(yzt - E2,)
8,
9
jEGigjm
jES:zfi
(1
2
E
(Bys, B2y)
+(11
11
2
B
(Uzz Eyz.)) 2
8,
19il
8
99
jEBi
+
1
6,
Σ
(U3, - Ezi)
2
2
2
1 + 5.
09 (E -2,)11= + (1+
E
(ug, - Eysn))
8,
Gail
jEG::joi
0i
+
1+
(1 6,) E - -Ez;|' ||2
2
2
1
S 8: ||Ejegnsr - 25)11 - 1
I8
(wAa Bys,))
0i
GGil
7.
JEDNiji
T2
1+ (1+
5i)
2)(1 (1-6))² 6,)) EsEsrsseillls. Eail
+
2
Tg
(6i3)
(o + 0200
25
5, 2
+
+
1+
n1
o²
6,4
6,
G
1
1+ 6,
((
6,
0²
3
+ (1 0,)2
1
+
+
2
2
A
A
o²
0²
24
1 8: + 0
+
+
A
0,A0
n2:
A
02
(1 8.)
+
n2
(i), (ii) Young's inequality
(iii We prove this bound in Lemmas 2 3 and Importantly, it shows that, from point i's perspec- tive, the error of its Duuster-center-estimne by our thresholding procedure on the good points which belong to i's cluster (and therefore ideally are included within the thresholding radius); T2, which accounts for the variance of the points in i's cluster; and Ta, the error due to the good points which don't belong to i's cluster (and therefore idcally are forced outside the thresholding radius).
is composed of three quantities: Tı, the error introduced
(iv) Assumption that A 2 %/6..
Lemma 2 (Bound Tj Error due to In- Cluster Good Points).
(c + 02)0
|| - 2,)1 & E +
5,4
21

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemma
By definition of Vj.
Ejegsswilllj 2,1l Ellly,, .11 -20--2y1111 2 - -2yll > TR.,))
E B1 2 (1luk,.1-1 2zy1 > Tk..))
Thisd
18 1k, 111 -2y1
Thgs
E8 Uks.1-1 EEi E ElI 2,11
Tkg
kg + o²
Tku
Finally, by Jensen's s incquality and plugging in the value for Tk..
E 22)111 - (Bllu,,t - 23l1)²
(c + o2)2
Tlal
2 + 1020 0t
kadd
0,00
8.01
(ct 0
= kid +
8,4
Lemma 3 (Bound T2: Variance of Clipped Points).
n4 G 0².
E
jEG:jMi
Proof of Lemma Note that the elements in the sum (0) Ey,a) are not independent. Therefore, we cannot gel rid of the cross terms when expanding the squared-norm. However, for each round of thresholding were sample fresh batch of points to set the new cluster-center estimate, then the terms would be independent. With this resampling strategy, our bounds would only change by a constant factor. Therefore, for ease of analysis, we will assume the terms in the sum are independent. In that case,
E
Σ (U1 EVyND
n1 E 13
Ey,,1 1|
Gil
1
jEG.:JM
n4
Eli,y - E2,1
|
n4 0²
|
where the second-to-last inequality follows from the contractivity of the thresholding procedure.
Lemma 4 (Bound Tg: Error due to Out-of-Cluster Good Points).
6
o3
Ejege 11yj. - E2
x
1
+
+
2
+
6,
A
22

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemma
By Young's inequality,
8
EjeguiAi 1yg - E2
1 1
B
U
Ezil +
1+ 5,
E B - 11
6
x
1 +
+
[+
1 B - 1212
6,
6
1+
Rast
+
|+
6,
1 E - 1 Uk. S TRIT
1 1
+
1+ DE.:PPe00:) - uk S Tk..))
We now have to bound the probability in the expression above. Note that if ||Uk,,1-1 - 2gl1 S Tki, then
[[Ezz E2,11
< || Ezy1 | + ||z Evk, - 11 + [UR, 1-1 E2
|| Ezy 2 + ||z Ez₁ 2| |B2z Eok, 1- Bl UN B2;11 +B112 Ezz
- || - Ezy1| 2 + R + ct + o
By Assumption 2, this implies that
A 2 2g - B22l1 + + + c,,1 o²
which means that
|| E2yl' 12 1724 A - (Th Ckes + 0²).
By Markov's inequality,
2 o²
P(122 B2,11 A - +
+ +z²)) 1 2 (Th + kg
+
0²)
as long as
A A
+ +0² o²
which holds due to the constraint A in the theorem statement. Therefore
6,
2
(c 8,0 2
Bjegиee:llbs -2,
1 +
2
k
+
1+
0
A
6
o²
1
+
8,
Chel
A
Lemma 5 (Clustering Error due to Bad Points).
Mid
- Ez,
S t + 5,00
|B.
jEB,
Proof of Lemma
Mj.
Ez;
< EjeB, /1 - E2;|1
[B
jEB;
3 EjEB, |1 - Uk 1-12 + El Ezi]1²
$ 2 S.oA.
The last inequality follows from the intuition that bad points will position themselves the edge of the thresholding ball, distance Tkt. away from the current center-estinate Uk,1-1- Therefore cannot do better than upper-bounding EyeB. |y 2 by Th. zs et + 6,0 the squared-radius of the ball. J
23

---

Published in Transactions on Machine Learning Research (11/2023)
A.2 Proof of Theorem 2
Proof of Theorem Let
8
w.p. p 0 w.p. 1
D1
and
88 w.p. 1 1-p P
D2
0 w.p. P
and define the mixture M 1 Also consider the mixture M 1D; + 1Dz where Di 0 and D2= = It impossible to distinguish whether a sample comes from M or M. Therefore, if you at least know a sample came from either M or M but not which one, the best you can do to estimate μn with d1 bR half-way between the mean of D1, which is op, and the mean of D1, which is O. In this case
Blp 11l22 dppp
4
If p S 3, then
A (1-p) p6 (1 2p)6.
(10)
Also,
d² = 88 p).
(11)
Equating 8² in
10 and
2
0²
(1 2p)
p(1 p)
which can be rearranged to
(4o² + A²)p² (40² A² p + =²=
Solving for P.
1
A
p= 2
(12)
20
A
Note that,
82
o²p²
4p(1 p)
0²p
(13)
4(1 - p)
Plugging the expression for p from
12 into
13
can see that
p²pp² 0²
+
2
A
q²
(v
402
-1 11=
0²
'20
20 A
4
4
4
2
A
The last step used an immediately verifiable incquality that /1 x > 1 + we can choose 2 > 202 to give the result that
for all E 10, 8). Finally,
82p² 04
E A1 1
4
4A2
Finally, suppose that there is only a single cluster with K 1. Then, given n stochastic samples. standard information theoretic lower bounds show that we will have an error at least.
Ellá1
4n
Combining these two lower bounds yields the proof of the theorem.
24

---

Published in Transactions on Machine Learning Research (11/2023)
A.3 Proof of Theorem 3
First we establish some notation.
Notation.
G3 are the good clients and B, the bad clients from client i's perspective. Therefore [ + [B,] = N.
By denotes conditional expectation given the parameter, e.g. Egg(2) = [R](())))). E denotes expec- tation over all randomness.
X, T Ei= Xx for a general variable X, indexed by L.
We use fi(x) to denote average loss general batch B of samples. That is, if (z; b) is the loss on single sample b, we define fi(x) =
1 [a] ESEB (i(;;)).
[z) 1 mi (i(()
We introduce variable p² to bound the variance of the gradients
(z) (x)
and show in Lemma e how this be written in terms of the variance of the gradients computed over batch size of 1.
the number rounds that Threshold Chasterin is run round of Federated-Clusteriing Clustering.
ky denotes the cluster to which client is assigned.
vat denotes the gradient update for client i in round of Eeleratted-Clsteerigg and round of Crresbold-Clusternng That is, 4. corresponds to the quantity returned in Step 6 of Algorithm
To facilitate the proof, introduce variable Ck.,.t that quantifics the distance from the cluster- center-estimates to the true cluster means. Specifically, for client i's cluster k, at round t of SileeaatedCClsteriie and round I of Threehold-Chsserriggg we set
c = El (.
For elient i's cluster h; at round of Rederated-Clusteriig and round of Threshold-Clustering we use thresholding radius
Thlt ~ C, A'E|Vf((ELLDDII 8,pA.
Finally, we introduce variable Uj..t denote the points clipped by TThreshold-Clustering
Σ JE(N
(x.--) 0z 2. S TKT.) + 0i (1lg) (x1,-11) v1,1-1,1 > T...).
U11.1
95..1
Proof of Theorem 3 In this proof, our goal is to bound E V (Z) for each client i, thus showing convergence. Recall that our thresholding procedure clusters the gradients of clients each round and estimates the center of each cluster. These estimates then used update the parameters of the clusters. Therefore, expect ( to be bounded in terms of the error of this estimation procedure. The following sequence of inequalities shows this.
25

---

((f((z..)) Published in Transactions on Machine Learning Research (11/2023)
By L-smoothness of fi and setting S 1/2,
[((1))) S fi(rie-1) ( (Vii(ii, Tis xi,e-11 1) + 21i 1112-111
2
1111511) WV.VVViaiiiiiiii v(d,)) LTp²
| 1|
= + ! U vf(( 17 V
[1 Lm) [or
Vf((,,,-)))+++ V ( (1 L. 112
(14)
Recall that V is client i's cluster-center estimate at round of optimization, so the second term on the we show that, in expectation,
right side of (14) is the error due to the clustering procedure. In Lemma 7 this error is bounded by
D V (
A + +
p² B.ps)
6 E V
A
Therefore, subtracting fi from both sides, summing [4 over t, dividing by T, taking expectations, applying Lemma 7 to [4]. and applying the constraint on A from the theorem statement, have
fi) + M Vf( + m
p² p² + B.pA).
E V
(15)
T
A
The third term on the right side of [4] reflects the fact that clients in the same cluster may have different loss objectives. Far from their optima, these loss objectives may look very different and therefore be hard cluster together.
In order to bound this term, we use a similar argument as above. By L-soothhesss of fi's and setting E 1/L,
M(xa)) S ((( (Vi((s,,-1)))) - x1,1-1) +
1 - 11,
2
Lni
= -((s,e)))
||
= =((xu--1) + " 1luuee- - F
V (2
(1- -1-Lan Lm)ll
Subtracting Ji from both sides, summing over I, dividing by T, taking expectations, and applying Lemma
B(f((1,,)) [ x
Ji) AP ( +12++00
+ ROA)
(16)
T
Combining 15 and 16 and applying the constraint on A from the theorem statement, we have that
E(f((r,,) fi) AF fi) + n max (1, A3)
_²
p² + B.02).
/ V (2.
+
(17)
n1
A
Dividing both sides of 17 by 7 1/4 and noting that p² === =00/118/ from Lemma
V E(f((0,,0) - f + APE(f((zr.)) - f?) max 11 A3)
p3
+
+
3pp
(18)
nT'
14
A
L(E(f((FL.) - ft) A J:)) (1, max(1,
/n, 0²/ BiO
B
max(1, Maax(1,A2))) (2) + 00/ B,o
T
26

---

Published in Transactions on Machine Learning Research (11/2023)
where the last inequality follows from setting
0² o A9)
B 2 max(1,
_
+
B105)TT T.
n
A
Since m.//B1, this is equivalent to setting
02 (0²
B
max A3)
+
+ B mi.
n
A
Lemma 6 (Variance reduction using batches). If. for single sample b,
Exllg((;;b) Exg. b]12 s o²?
then for batch B of samples,
a² Ex]1g((x) (x))1
|3
Proof of Lemma 0 Due to the independence and unbiasedness of stochastic gradients,
Exllg: (x))(
Er, (x; (x;
B 2
BEB
2
B
Lemma 7 (Bound Clustering Error).
Ur - (00 + P DDEIVA(E,,1D) + (e+ + o² + SLDS))
+
27

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemma 7 We prove the main result with the following sequence of inequalities and justify the labeled steps afterwards.
El Videe
E Blilt (x
Yiulet (x 2
E
Σ
N
JE|N]
E
(1
Bi)
[9
Σ
Wider (esi((iss)))
3:
[B.
Viet
Ennh (302,-
jES.
jEB.
(
(
(1+ 8,)(1 -1)1--))22)
Σ
Wiltet)
9il
jES.
1 +
1
1
+
Σ Vsiled
E. (1T,,-1)))))
[B,
jEB,
1
E
Mileet
+ EE
Midee
B
jEGL
jEB,
E1
82
(1 6, + 1..cc.. (6: + (
('E
A
0²
+ + 3ipA
0
p3
8//2 02/2 keit 8 Vf (T
+
+ BiDA
74
A
(p²
p3
2A
(1
1, + + +
(f
+
+ Baps
77
A
(2
p3
P
2 k. + ( D'
+ 3,pp (199
n2
A
Justifications for the labeled steps are:
ii) Young's incquality: || y/1 (1 c)x2 + (1 + 1/cyy² for any c 0.
(ii) We prove this bound in Lemmas g and 12 Importantly, it shows that the clustering error is composed of two quantities: ε,, the error contributed by good points from the cluster's 's perspective, and Eg, the error contributed by the bad points from the cluster's perspective.
(iii) Assumption that 3, S min(6,,61/a) 5/a²)
(iv) Since El - V = 2 1111 the inequality forms a recursion which we unroll over
4 steps.
(v) Assumption that 4, 2 max Tog( -5,77
lo/(s/a)
28

---

Published in Transactions on Machine Learning Research (11/2023)
Finally, we note that
1, = (l - (B.
S Ellgi (x( -
- Eugh (2
S p² + 1 [
Applying this bound to 19 and applying the bound on A from the theorem statement, we have
B Oidd,t
PA2
(
e2
+ pa
6
E V Vi((
+
BipA))
n
A
+ 3
B
D2
V
+
+ Rups).
n1
A
Lemma 8 (Clustering Error due to Good Points).
E
- (2,(
G
jeG:
(2² (e=+ 22)
$ (1 8,) of te + &.
P
D'E|V/(E,.-)I11+ +
A
29

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemma labeled steps.
We prove the main result in the sequence of inequalities below and then justify the
BeBi 2
1
E
jEG.
E
Vidles)
Engg(1i,1111 -
1
Σ
Eng (210-))
n4
JEGL
jEDig
jEGrijmtt
1
3
E
(Uisen -
+
(Ugtert - Eng. (2i
giil
jEBesjoli
1 +
2
E
Σ
(Ugunt - Exg, (x
+
1+
E
Σ
(Ublen - Exg. (xs,
19
2
|9
jEN:
(60)
2
2
1 5.
E
(Eyssut - (Ti, 1))
+
+
B
(Mitee - Bysser)
5,
jEGCijmi
JEGCJjii
5, (1+
1
+
B
2
Gill
jEGISSA
(18)
1+
2 E
E(ysut (0(()(111)
+ +(1
1+
2
E
1
Σ
(Engg(1ees-1)
Egg (10,,,1))1
8,/
|9
JED.:jms
jEgi:jms
2 8,
6, 2
1
E
Σ
(Widen Bysjdet))
1+
E
(Wider - (xgi(
9il
jEGisjol
(in)
1 5,
2
0,
E
E Blyjieet - 95 (0( 1)]1
+
1
2
m
p²
5,
|g
Ti
(1
2 5,
8i 2
)01 (1 5.)²
+
1+
E
(Uillet Rygne))
+ 1
+1+
R5EGn:s4 (ly - Fng (2it
Ta
T2
(2)
6,
knddi + (
2|
)²4== + (1+ +1+
13
2
|g, 12 p²
ns
6,A
8,
1+
8,
2 (1 - 6,)2
(1=2))
8:
Cri + 8,E
2
V (1
1)12
L A
D'E
VI
(1]
03
2
p²
8, Collent + E V fe (2
8,A
n44
0²
+ (1 (1) Ri + 6, 1D)
2 + P D'
Vf
12
+
A
12
13
< (1 - (1-8))c C.. + & +
+
n₂ A
Justifications for the labeled steps are:
(I) Young's inequality
(iv) First, we can can interchange the sum and the norm due to independent stochasticity of the gradients. Then by the Tower Property and Law of Total Variance for the 1st and 3rd steps
30

---

Published in Transactions on Machine Learning Research (11/2023)
respectively,
El| (E - -Eg (x4,1-)))11
El (G1,--) - E ER (f),1-1)]|?
(ar(E (gs (2i,)-1)))
Var(g) (zi(e- )) B(Var, (2i2 (1g
S Varlgj (2i,,- E (2i Engg (2
Sp.
where the last inequality follows since the two terms above it are both bounded by p².
(v) We prove this bound in Lemmas error of its duster--enter-estinnee is composed of three quantities: Ti, the error introduced by thresholding procedure on the good points which belong to i's cluster (and therefore idcally are included within the thresholding radius); T2, which accounts for the variance of the clipped points in i's cluster; and Ta: the error due to the good points which don't belong to i's cluster (and therefore idcally are forced outside the thresholding radius).
and It shows that, from point i's perspective, the
(vi) (1 + 112) x) z²² s 1 - x for all x E [0, 1]
Lemma 9 (Bound Ti: Error due to In- In-Cluster Good Points).
Ø
E B(gsh, - 93 (x( Ck Vf( + 8
Proof of Lemma g In this sequence of steps, we bound the clustering error due to good points from client i's cluster. By definition of Vidects
Ellyae. - 95 -1
> Tkude.)l > Tkc.
11,,, - 2/ (Xi
Thi.f
U1.,,- 9j (1),t-
Therefore, by Jensen's inequality and plugging in the value for Thideet
E (Vy 9 (
EE Eyliitt 9, (1;,,-))11
(E Ui.lu 1,1 - 93 (x
IE
E.g, (xi,e-111 Bllgy Us,d, -1,1 E. (2:0((1;111))) EE 22
Exgy (
24
(Cryl A [|(
(oo + A f4
p2)2
kedet + A'E V f (2), 12 +.pp
PA3
2 Radiit +
1+
E Ja (
8,A
8,A
3
(20)
A
31

---

Published in Transactions on Machine Learning Research (11/2023)
where the last inequality follows from constraints on A. The second inequality follows from Young's inequal- ity. The second-to-last inequality follows by separating the fraction into a sum fractions and selecting
terms from the denominator for cach fraction that cancel with terms in the numerator to achieve the desired rale.
Summing
20 over and dividing by T, we have
Bjegnd
= El (,(,,,111)
Ru + V
6,A
Lemma 10 (Bound T2: Variance of Clipped Points).
(Ugia Eygaaa)
n2 S
jEGujjii
Proof of Lemma 10 The first thing to note is that the elements in the sum Σ Σeeae,-, (Vss, - are not independent. Therefore, we cannot get rid of the cross terms when expanding the squared-norm. However, if for each round of thresholding we sampled a fresh batch of points to set the new cluster-center estimate, then the terms would independent. With such a resampling strategy, our bounds in these proofs only change by a constant factor. Therefore, for case of analysis, we will assume the terms in the sum are independent.. In that case,
(Widett Byssen)
-
n4 1
lliiet eli
Gi
jEB::jmi
n4
El (2),,1)))
E
9
n2
G
1
where the second-to-last inequality follows from the contractivity of the thresholding procedure. Lemma 11 (Bound T3: Error due to Out-of-Cluster Good Points).
6: C. + & ([ + P ('E
Ø
Byea:syvlllssett ( x 1
2
This sequence of steps bounds the clustering error due to points not from client i's cluster. Using Young's s inequality for the first step,
Proof of Lemma 11
Bjeg.:xilllB).. - (T
8,
E El E. 111 (1+ 2 5,
w
1
+
Eseanssillbait 1,
&
1
+
Raalet +
1+ 8,
Ejeawseillbite - w1 -
8,
+
+
Pleaaw - Uss -1 (1l oil - S Teat
5,
8,
1
+
1-
Pe... Ui u.rl S Think))
6,
1+
2
+
(ch +
(1in)))))))))))) v.d,-ell S Thedee).
32

---

Published in Transactions on Machine Learning Research (11/2023)
The next step is to bound the probability term in the inequality above. Note that if 1 - -g,(21,-111 Teide then
B. (x 1)12 x (1 - Engly (drt,- (199)((11111) walle 1,,1e-1,111 + 1 (x
11 (Zi1)-1) En ( +
11,, Engi (zi 1)11 + [i ( E=
S (X1,--1) Enggy (1i )1( + de.
+ 110,,4111 - B (3i.. 1)1 V
By Assumption 4, the previous inequality implies
A D' < (19((x)e-1) Eegg( Thi + V +1 -20((11,--111
which, summing over t and dividing by T, implies
[gy((ia=1)) - (xi.) + 1ot,, 1.e ( +I -" A -T -k
By Markov's inequality, the probability of this event is upper-bounded by
p Uide EnDi
A Vi(,,,-))))
D
/² K. + A (
(
2
where the second inequality holds due to the constraint on A from the theorem statement. Therefore,
Ejegrifi 1 (xi
6:
P
1² + +c C + A
V
Si
((
(i(
1
A
6,22
2
(p2 + 22 Ch.let + A
f1
E (2
A
6,A2
p² D V
A
A
(' 0²
(f + P
x 1 Teule,t + LE
V
A
where for the last incquality again apply the constraint on A. Lemma 12 (Clustering Error due to Bad Points).
Σ Witee) -Be jEB;
S Chi + (f &
B.
Proof of Lemma 1 This lemma bounds the clustering error due to the bad clients from client i's perspective. The goal of such clients would be corrupt the cluster-center estimate of client i's cluster as much as possible each round. They can have the maximum negative effect by setting their gradients to be just inside the thresholding radius around client i's cluster-cente estimate. This way, the gradients will keep their value (rather than be assigned the value of the current cluster-cented estimate per our update rule), but they will
33

---

Published in Transactions on Machine Learning Research (11/2023)
have maximal effect in moving the cluster-center estimate from its current position. Therefore, in step of the inequalities below, we can not do better than bounding the distance between these bad points and the current cluster center estimate (i.c. llusa,, vu--1,111 by the thresholding radius (Ra))
B
Σ Vole.e Bade(2ne-1) jEB,
s BJEB llus, Ex (21,0_1)1
[.
RJEB ll - Vilee 1,ee- 1 -Rlooo-- (x1=-)))
Thalet + Chi
Aaleet + ( S.pA.
The last inequality applies the definition of Thalets and the result of the lemma follows by summing this inequality over t and dividing by T.
A.4 Proof of Corollary 1
Proof. We will show that there exist A, D, and A for which Assumptions 4 and 5 are satisfied for smooth and strongly-convex losses. Then the result follows directly from Theorem 3
Note that for h L-smooth function and g jestrongly-convex function with shared optimum x", the following incquality holds:
(#) [V((2)]
[V(a)]
(21)
To this, note that by L-smoothness of h
|V Vh(=")) < L2|12 1²1
(22)
By p-strong-con contexiyy and Cauchy-Schwarz inoquality,
# 1 < (Vg(z) Vg(x"), x x²) < [[gg(>)] x=1|.
(23)
Rearranging terms in 23 squaring both sides, and combining with 22
gives 21
We can now apply 21 to show that Assumptions 4 and 5 hold.
For Assumption 4, let h(z) = f(()) ((() and g(x) = f(()). Thus and g have the same optimum. Since the average of j-strongby-convex functions yestrongly-convex, g is p-strongly-convex. By L-smoothness of Si,
(VV V))))) (VΛ() V((i)) < -V VAWI++ -
2T vll.
showing that h is 2L-smooth. Therefore, by 21
(2L
()(()- - <
1
which shows that Assumption 4 is satisfied with A 24/a.
34

---

Published in Transactions on Machine Learning Research (11/2023)
For Assumption 5, let z; be client i's optimum (equivalently the optimum of all clients in client i's cluster).
[V/(x) - [)z(0)] = [V (V]]()) v.5(=)) -
2 [V}(())) - (z) V
(0) [V)(2;) V - 2)l V((0;))
2 2
2 [Vf}(()) VA(4)) 21V 2(4))
2 [Vf((]) -
2 [V - 2(1 (473))111001
(24)
where justification for the steps are:
(i) For all a, it holds that (a 18-by b)2 2 112 a², since this inequality be rearranged to state
(5/2 - 22a)² 2 0.
(ii) Young's inequality.
(iii) Set h(x)) fxx (ff(z)), 2) and g(x) = f((x). Then Vh(x:) = Vf}(z) Vzf(z,,, from which
that h and g have the same optimum of and h is L-smooth (since [|Vh(z) Vh(y)]
(xV (z)()))) (V/s()) (*{())>\ < L|ke vll). Applying 21 gives the desired result.
Therefore
24
shows that Assumption 5 is satisfied with A max
Vfg(2)]ll and D =
/2 + (%)
Applying these values for A, D, and A to Theorem 3 completes the proof.
A.5 Proof of Theorem 4
First we establish some notation.
Notation.
Gj the good clients and B; the bad clients from client i's perspective.
Eg denotes conditional expectation given the parameter, c.g. E.g(z) = E[g(x)(x). denotes expec-
lation over randomness.
k is the cluster to which client i is assigned at round of the algorithm.
X, A 1 E X2 for a general variable X, indexed by t.
T
J((x) A 1 Ejegisen (x)
कप, A 1 Ejesryen Mj.t
We introduce a variable p² to bound the variance of the momentums
Ez || E.m sp²
and show in Lemma 13 how this can be written in terms of the variance of the gradients, d².
1 is the number rounds that Threshold-Clusteringg is run round t of Federated-Chustering
hy denotes the cluster to which client i is assigned.
35

---

Published in Transactions on Machine Learning Research (11/2023)
Jk, denotes the gradient update for client i in round t of Momentum Hemeentu--hhusering Clustering and round of Thressold-Chusteringg. That is, Uhdd, corresponds to the quantity returned Step 4 of A Algorithm 4
To facilitate the proof, we introduce a variable Ckuda that quantifies the distance from the cluster- center-estimates to the true cluster means. Specifically, for client. i's cluster ky at round t of Federated- Feddrated-Clusterring and round / of Sareshold-Clusterinn we set
L = 11,,-111 ..
For client i's cluster h; at round of Federated Pederated-Chustering and round of Threshold- Threshold-Chusteringg we thresholding radius
Thil 1 + S.pA.
Finally, we introduce variable, Ujd,t, to denote the points clipped by Threshold-Clusteringg
1(1my, - S Tk.. + 2k 1 (lima -k..d-1.el > Tk..d.).
N JE[N]
Proof of Theorem In this proof, our goal is to bound ( We use L-smoothness of the loss objectives to get started, and justify the non-trivial steps afterwards.
L
& (f((ar,-11 1z E (V E
2i +
E
21,0-112
2
L1i²
-E/((1111)) - R (V (1.
+
E E.I
2
-Ef((((-11) + 2 (//
)11
7
V
7 Ln) El)
x Eff((11(11) 171E11 Uk: E, r11 M (f((
71 (1 -n)
(04)
0²
p²
(f +
+
+ 3,pp)
1E E (f(
A
71
2 E
)]
" (1 Lyy) E [1c,
(25)
Justifications for the labeled steps
(i) L-smoothness of fa and n I 1/2
iii) Young's incquality
(iii) Lemma 14
Now it remains to bound the E Mi, -/ term.
E - - < E E - (=(
(1 a) 2 1 - V.(((r,.-2) V
Vi((ti,)-2) (f((fir-1)11
(
2
(1 - (1- vf( (1- a)² L EEl uk 1
(1 Lm)
Blllkk de
where justifications for the labeled steps are:
36

---

Published in Transactions on Machine Learning Research (11/2023)
(i) Young's inequality
(ii) Assumption that 2 Ta
Plugging this bound back into
25 summing over =1:T, and dividing by T" gives
T E
B(Ji(11,0) -
1t)
+
L n4
0 +
BPP)
T +
(26)
27
A
By the variance reduction from momentum (Lemma 13 it follows from 26
that
T
B(fi(di.)) - -ii)
(ao²
E
1))
+
+
+ BiVaOS
T,T
A
(() -57)
+
+
+
1/f"
n4
A
+ (( (7) /n,t"
Finally, setting 17 S min
o 0 + +0/1
3,o
E V 1)1l
T
Ti 0 /a)=
Lemma 13 (Variance reduction using Momentum). Suppose that for all E [N] and x,
(x] (x)g(x))1 o².
Then
Bl 5 ao
Proof of Lemma 13
E mi, Em
= (ellaag)((aa1-)) - V V(((aa-1)) + (1 +1- - Bmi,--)
< a R gi (x(1-1) Vi( 1) (1 a))El|mmi.. -Em,,i 112
$ a 2 gi (
Vf( | + (1 - a)) Rma,-11
1-1
$ 000 Σ 0=0
(1 - a)9
0) 1
$ 0000"
a)
< 2000
Lemma 14 (Bound on Clustering Error).
D2 p3 <
UigA E.mi
+ A
3pp
37

---

Published in Transactions on Machine Learning Research (11/2023)
Proof of Lemma
14
We prove the main result, and then justify each step afterwards.
B Wkidest
Ey mi 2
E N
Vjdett
jE[N]
(1
3()
Vident Ex
+ +
E,
9i
B
jES,
JEB,
(
(1 (1+3)(1- -B)
Videet
gil
jEG.
|+
1
8910
Vildeit
|Bg
JEB,
2
(
3 E
Vjdlett
E,
E
+ B.
Σ V5deee)
|B:l
jEG.
JEB
2
(1 6. + B.)
p2
0
+ SipA)
T1
A
(8)
Ø²
$ (1 6/2)
+
+
8:PA
A
28 (6)
p²
P2
41/2)/
2,,
3ip
14
P
12
1
+ R.pa)
A
koll
+
+
A
(27)
We justify each step.
ii) Young's inequality
Importantly, shows that the clustering error is composed of two quantities: E the error contributed by good points from the cluster's perspective, and Eg, the error contributed by the bad points from the cluster's perspective.
(ii) We prove this bound in Lemmas 15 and 19
(iii) Assumption that 3 S min(0;, 6/2²)
(iv) Since Ellea - E.m,e1? = 2 1. the inequality forms recursion which we unroll over 4 steps.
(v) Assumption that 4 2 max(1, log(w/a) log( -/2)
Finally, we note that
El|ma, - E.m,,11
El|m, E.my,el? El|E,m,, E.ma,e! 12
< p².
Applying this bound to
27 gives
< p² p²
Uk.ded E.m.,el
+ + B.p
n2
A
38

---

Published in Transactions on Machine Learning Research (11/2023)
Lemma 15 (Clustering Error due to Good Points).
1
(x=+²²))))
12
)))
E
Villet)
S (00)))c +
gi
n
JEG.
Proof of Lemma
15
We state the main sequence of steps and then justify them afterwards.
E
Vilkee) )
- Eame
JEG.
B
Vited
B
1
Σ jEN::jmi
jEC:
Gell
jESiismmi
14
B
Σ
(Widen Emms)e)) + (9A)
Σ
(Ugdett Enmrrtt))
19
jEG:
JE
di
1+ 0,
(Wideet - mge)
+
1+
E
Σ
(Ujdett - m.
2
Gi
jEGajjmi
(12)
2 E
2
12
1 1 8,
Eyjle, E
+
1
+
E8
(Upient ExHlile)e)
19
8
JEG:jjai
-(1+
8/
+
11
E
(ys4,) E.m
19
++ 5./
2
18
Elysaa ma.e)
+
+(++
1+
2
(Emge Eamgzee)
6,
jEGrijmi
2
( 1 0:
+
(yaun Eysle,))
+
1
+
E
(yhiie - E,
2
jEGIgMi
jEG:oiA
(io)
-
2
6f
EjEstii BBx (Wideet m2
+
1
2
| p²
n
5,
+
( +
2
72
E
1
(yohie Eygnne)
+
+(1+
5;
(1 2)(
6:)2 (eea.ooolllls Bx 11
9
2
G9rl
2
jED:gNi
T2
p²
6,
8,
L.B.eau--illBB - m1
+
+
1
(1 (1-5.) (..))),,cae BjEGsesiill - E.m.r
Tli
(v1)
13
1
de)
(1 - -6,3 ((+
5,
$ 6:
Cullel +
+
+
1+
khele +
2
6,1
2
2
13
+ 1²
Radditt + pz)
$ 6.
+ (1 - 5:)
2
6,A
A
12
p3
& (1 5:)
+
A
Justifications for the labeled steps are:
(i), (ii), (iii) Young's inequality
(iv) First, we can can interchange the sum and the norm due to independent stochasticity of the momentums. Then, by the Tower Property and Law of Total Variance for the 1st and 3rd steps
39

---

Published in Transactions on Machine Learning Research (11/2023)
respectively
E,, - EBmj,el
E. - EE E my.e
(ar((Eum)),
Var(my,1) - IB (Var, (m,,,)
Var(m,,)) Bilm,, E,j 11
S SP,
where the last inequality follows since the two terms above it are both bounded by p².
(v) We prove this bound in Lemmas 16 17 and 18 shows that, from point i's perspective, the crror of its munster-center-ssimmee thresholding procedure on the good points which belong to i's cluster (and therefore ideally included within the thresholding radius); T2, which accounts for the variance of the clipped points in i's cluster; and T3, the error due to the good points which don't belong to i's cluster (and therefore ideally are forced outside the thresholding radius).
composed of three quantities: Tı, the error introduced by our
(vi) (1 + //2) - 2²² x for all E [0, 1]
Lemma 16 (Bound Tj: Error due to In-Cluster Good Points).
p3
Ejeg B(y -m,,))l S hudest 6,
Proof of Lemma 16
By definition of Vo.te.
El Mz,el B1l1v m2, ([P mz,el Tke.e.)))
Uk mj.e 2 (1luk,de- - mye1 Te..
Thi
Therefore by Jensen's inequality,
[Byy,, - my.ell < (E (Vsisee - my,ell)
E3 Uk mi
The
Uk. 1.- E, 112 E4, m2.el13)2
(Bllus, 11-11 Eym,, 21 E,I,E,,,,,,--- m,,
Th.
( + D2
Thikei
(Ch + 22
2 kg. t + 8ip2
1
P
2
+
A
5,A
3
Chubel
d,A
40

---

Published in Transactions on Machine Learning Research (11/2023)
Summing this inequality over t and dividing by T, we have
BjEgni-ii Be m,,,)11 E Yileet mj,ell
2 Kedest + pd
8,A
Lemma 17 (Bound T2: Variance of Clipped Points).
n4 S C 2 p².
(ygde Bysne.))
9
jEGcjjii
Proof of Lemma 17 Note that the elements in the sum (Ubdu Eyja..) are not independent. Therefore, we cannot get rid of the cross terms when expanding the squared-norm. However, for each round of thresholding we sampled a fresh batch of points to set the new cluster-center estimate, then the terms would be independent. With this resampling strategy, our bounds would only change by a constant factor. Thercfore, for case of analysis, we will assume the terms in the sum are independent. In that case,
E
(Usant Eysa..)
74 Bluuja, Eyja,ell
JED:
1 Em
14
El|ma
n;
1
where the second-to-last inequality follows from the contractivity of the thresholding procedure.
Lemma 18 (Bound T3: Error due to Out-of-Cluster Good Points).
Ejeg,s Bymi 12 S
1
2
A
Proof of Lemma cluster. Using Young's 's inequality for the first step,
18 This sequence of steps bounds the clustering error due to points not from client i's
E R
1
6:
Blloagh--1
E
Eymiell 11 + (1
2 E (ll Uk,
2
6
2
1
Codlet +
1+ Byesnoyellls,... 11.12-1,111
2
2
1
Chilitt
2
+
1
Byea || Uk (llma, Uke - 1,ll S Tkule.))
2
2
1+
Chillit
+
1+
Uk. Thr.d.))
2
8; +
1
+
(c
(ch jessja)aa))) uAgu--ll S Tkide.).
2
b,
If |0ogle11 mj S Thidee then
[. E $ [m Eymizel2 || Uk, 1.ll 11 Eym
|[ Exm,,e + 2h. + +1 - E.mii
41

---

Published in Transactions on Machine Learning Research (11/2023)
By Assumption 9,
A ||m,a - Ba +
Teader + 10 Egmm
which, summing over t and dividing by T, implies
Imj.c E,m 1 B
A Th.le,
By Markov's inequality, the probability of this event is upper- by
0² + Uk, -, mil
p² + 2
A Rede
where the inequality holds due the constraint on from the theorem statement. Therefore,
6
P
p² +
p
E Vi Exmi,
1
8,2²
A
6
p²
1 1+
where again we apply the constraint on A for the second incquality. Lemma 19 (Clustering Error due to Bad Points).
(13) [B&
|
E
Σ
2 Chibi + 8,p1
JEB.
This lemma gives a bound on the clustering error due to the bad clients from client i's perspective. The goal of such clients would be to corrupt the cluster-center estimate of client i's cluster as much as possible at each round. They can have the maximum negative effect by setting their gradients to be just inside the thresholding radius around client i's cluster-center estimate. This way, the gradients will keep their value (rather than be assigned the value of the current cluster-center estimate per our update rule), but they will have maximal effect in moving the cluster-center estimate from its current position. Therefore, in not do better than bounding the distance between these bad points
Proof of Lemma 19
step 3 of the inequalities below, and the current cluster center estimate (i.e. Iluj Uk.. - by the thresholding radius Tk,d..t-
Videet Eg jEB,
< Iles - Ey
B
x EjeB, IlVi,eet - 11 Uk E,m,,
< Thil + Ch
S 2 kn.lt + dipA.
The last inequality applies the definition of Teiduts and the result of the lemina follows by summing this inequality over t and dividing by T.
42


Reviews:
[{"review_id": "te973r0fmg", "reviewer": "Reviewer_SJcN", "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": "Pros:\n1. The paper do a lot of theoretical analysis and proposes a new clustering algorithm that could be used into personalized federated learning setting.\n\nCons:\n1. The paper needs major revision on the paper organization. The algorithm is introduced very late however the comparison and discussion have been already discussed, which makes the paper difficult to follow. \n2. The paper presentation needs to be polished. Figure 1 is to small to be viewed. Figure 1 and 2 don't have explanation on the axises. I find myself very hard to understand those results and why the Figure 1(c) is outperformed than (a) and (b).\n3. The examples in page 2,3,4 need further explanation. I don't get it why the gradient on the first page should be $1/2eta$, $1/2eta$, $-1/2eta$. It should include x and it still doesn't make sense if I just take the value into x.\n4. I am not sure the assumption is correct that strongest adversary is near the radius. The malicious users could put a very big value datapoint outside the radius as well since it would be still updated by doing average.\n5. The experiments are pretty weak. As claimed by the paper, the proposed method is a robust algorithm, it should include some malicious users in the simulation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 robust clustering framework on the personalized federated learning setting. Specifically, it first analyzes several failure modes that the current framework experienced and then propose the threshold clustering method. It keeps the data points unchanged under a set certain radius and scales those that are outside the radius. The theoretical analysis have been first conducted under iid data distribution and then extended into client's gradient in the framework. To speed up the procedure, it later proposes to use client's momentum. The experiments have been done on a synthetic data and MNIST dataset to show the proposed method could achieve comparable and even better performance than baselines.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest to move the failure modes/cases into the motivation before the proposed method.\n2. Some description on the Algorithm 1 is needed. Personally I don't think it is a good idea to just introduce the algorithm by only giving the algorithm itself.\n3. Polish Figure 1 and 2. Add description on axises and make the text bigger and visible. Also, consider to optimize the space for the Figure. For example, just put all three figures in Figure 1 in a single row.\n4. Include some malicious users cases in the simulation.", "broader_impact_concerns": "No need for ethical review.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KfImr0ecZ2", "reviewer": "Reviewer_C9QW", "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": "Pros:\n- The paper addresses the challenge of personalization in federated learning, which is a crucial problem in many real-world scenarios.\n- The proposed algorithm clusters clients with similar objectives and learns a model per cluster, which is an intuitive and interpretable approach to personalization.\n- The authors provide optimal convergence guarantees and provable robustness in the Byzantine setting, which is a significant contribution to the field of federated learning.\n- The proposed algorithm outperforms existing federated learning algorithms in terms of both accuracy and communication efficiency, as shown in the experimental evaluation.\n\n\nCons:\n- The experimental evaluation is limited to a few datasets, nly one real datasets are used. and it's unclear how the proposed algorithm would perform on larger and more diverse datasets.\n- The paper does not provide a detailed analysis of the computational overhead of the proposed algorithm, which may be a significant factor in some scenarios.\n- The paper did not provide a comprehensive analysis of related works and highlights the differences and similarities between the proposed algorithm and existing approaches. Some important references are missing such as:\nPersonalized Federated Learning under Mixture of Distributions.\nInternational Conference on Machine Learning (ICML'23), 2023.\nPersonalized Federated Learning via Heterogeneous Modular Networks.\nIn 2022 IEEE International Conference on Data Mining (ICDM'22). ", "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 framework for personalized federated learning that clusters clients with similar objectives and learns a model per cluster. The authors provide optimal convergence guarantees and provable robustness in the Byzantine setting. The proposed algorithm is evaluated on synthetic and MNIST datasets, and the results show that it outperforms existing federated learning algorithms in terms of both accuracy and communication efficiency.\n\nOverall, the paper presents a significant contribution to the field of federated learning by addressing the challenge of personalization and robustness in a provable manner. The proposed algorithm has the potential to be applied in various real-world scenarios where personalization and robustness are crucial, such as healthcare and finance. The paper provided thorough proofs. However, the experiments are not sufficient. Only one real datasets are used. Also, some important references are missing. \n\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The experimental need to include more real datasets, such as CIFAIR10, CIFAIR100, etc.\n- Detailed analysis of the communication overhead of the proposed algorithm is needed.\n-  Provide a comprehensive analysis of related works and highlights the differences and similarities between the proposed algorithm and existing approaches. Compare with more recent SOTA approaches, such as the listed above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fXHXaBdgVx", "reviewer": "Reviewer_Abdu", "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\nThis work is the first approach to combining personalization with Byzantine robustness in a quite general distributed learning setting. In my view, this is a very **exciting research direction** as it allows to provably extend distributed robustness results to heterogeneous settings (essential for Federated Learning), which was hard to do before.\n\n**The writing** is clear, and the presentation makes the paper easy to follow. It has an understandable and well-organized structure, starting from simple examples, then introducing the Threshold-Clustering subroutine, and gradually extending the results to more general and practical settings.\n\n**Theoretical analysis** is based on quite reasonable assumptions. The estimation error of the suggested clustering method is supported with a simple lower bound. Helpful explanatory comments accompany theorems and assumptions. It is commendable that the authors also extend the proposed Federated-Clustering to a more practical momentum-based method.\n\nIn addition, simple **experiments** serve as a good illustrative demonstration of the interesting theoretical results.\n\n# Weaknesses\n\nOne of the proposed algorithms: Federated-Clustering, can be very problematic in **private** federated learning as it requires broadcasting personalized models to other clients, which may be infeasible in practical systems.\n\nMoreover, theoretical guarantees for FC require setting thresholding radius $\\tau$, which depends on (in general) unknown quantities. A similar problem holds for the step size upper bound in Theorem 4, which depends, i.e., on $f_i^*$.\n\nAssumptions 4 and 5 may be problematic from an optimization perspective due to a potential restriction of the class of functions. Empirical estimation on a synthetic non-adversarial problem is not very convincing.", "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": "This work studies the problem in the intersection of personalization and Byzantine robustness. The authors show the failure of previous clustering-type methods on simple constructed examples and suggest a new algorithm: Federated-Clustering (FC). \nThe proposed approach is equipped with rigorous \"clustering\" and robustness guarantees. In addition, the paper extends results to non-convex smooth stochastic optimization under assumptions of Intra-cluster Similarity and Inter-cluster Separation of the gradients. Communication efficiency is improved  by using momentum under stronger assumptions on momentum parameters rather than gradients. \nSimple experiments validate some of the theoretical assumptions and show the benefits of FC on a synthetic quadratic problem and MNIST against other personalization algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I believe this work can be accepted in its current form. However, next, I list some suggestions which, in my view, may improve and strengthen the work.\n\nThe paper needs a more detailed discussion on compatibility with modern Private Federated Learning systems. An explicit limitations section of the obtained theoretical results would also be very beneficial.\n\nThe experiments description is relatively short and does not explain how and why the hyperparameters were chosen (e.g., for Ditto). I am afraid the results are not reproducible due to a lack of details.\n\nIt would be helpful to discuss how big the lower bound for $l$ (from Theorem 1) can be, maybe by plugging some expected values or through experimental evaluation.\n\nI would like to ask the authors to add a more detailed comparison to prior works' theoretical results, i.e., Ghosh et al. (2021). In addition, I suggest putting this work into a broader context of Byzantine-robust optimization. For instance, by adding a comparison to the work [R] and how obtained results build on previos papers, what are the innovations in the analysis, and so on.\n\nIt would be ideal to have a more realistic federated experimental setting, e.g., on a subset of Federated EMNIST.\n\nIt is encouraged to make the proofs in the Appendix more comprehensible by splitting the long sequences of inequalities.\n\nThere are some minor notation issues.\n\n1. The $\\stackrel{i. i. d.}{\\sim}$ sign meaning (in Assumption 1) is not fully clear as this particular notation is not defined. Does it mean that points $z_i, z_j$ are random vectors with the same probability distribution?\n\n2. The main text does not introduce the Batch size $|B|$ (in Theorem 3). Algorithm 2 (FC) does not mention any mini-batching. It seems that the lower bound for $|B|$ may be larger than the size $m_i$ of the client $i$'s training dataset, which may be problematic.\n\n3. Does generating matrices $A_i$ from _\"gaussian distribution\"_ refer to sampling its entries and $y_i$ from __standard__ normal? \n\nTypo in the reference\n> H. Brendan **McMahon**, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th Conference on Artificial Intelligence and Statistics, volume 54, 2017\n\n___\n[R] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. \"Learning from history for byzantine robust optimization.\" International Conference on Machine Learning. PMLR, 2021.", "broader_impact_concerns": "I do not foresee negative ethical implications of the work due to its mainly theoretical nature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work achieves offers significant progress towards the theory of clustered federated learning, and manages to do so while offering robustness as well. The theory is sound, strong, and will likely be of significant interest to the community. The experiments help offer a variety of ablations and empirical validations of the theory, and have become relatively detailed since the initial review phase. This is a clear acceptance in terms of the content of the work.

Before submitting, I would like the authors to clean up their citations. In particular, at least one author name is misspelled (McMahon should be McMahan) and there are multiple instances where authors cite arXiv works instead of the published version of a paper, eg. "Personalized federated learning through local memorization" and "Very Deep Convolutional Networks for Large-Scale Image Recognition".
Decision: Accept (poster)