Fusion of Global and Local Knowledge for Personalized Federated Learning
Authors: Tiansheng Huang
Li Shen
Yan Sun
Weiwei Lin
Dacheng Tao
Venue: Accepted by TMLR ()

Abstract: Personalized federated learning, as a variant of federated learning, trains customized models for clients using their heterogeneously distributed data. However, it is still inconclusive about how to design personalized models with better representation of shared global knowledge and personalized pattern. To bridge the gap, we in this paper explore personalized models with low-rank and sparse decomposition. Specifically, we employ proper regularization to 	extract a low-rank global knowledge representation (GKR), so as to distill global knowledge into a compact representation.  Subsequently, we employ a sparse component over the obtained GKR to fuse the personalized pattern into the global knowledge. As a solution, we propose a two-stage proximal-based algorithm named \textbf{Fed}erated learning with mixed \textbf{S}parse and \textbf{L}ow-\textbf{R}ank representation (FedSLR) to efficiently search for the mixed models.  Theoretically, under proper assumptions,  we show that the GKR trained by FedSLR can at least sub-linearly converge to a stationary point of the regularized problem, and that the sparse component being fused can converge to its stationary point under proper settings. Extensive experiments also demonstrate the superior empirical performance of FedSLR. Moreover, FedSLR reduces the number of parameters, and lowers the down-link communication complexity, which are all desirable for federated learning algorithms. Source code is available in \url{https://github.com/huangtiansheng/fedslr}.

Published in Transactions on Machine Learning Research (02/2023)
Fusion of Global and Local Knowledge for Personalized Federated Learning
Tiansheng Huang" Georgia Institute of Technology
edu
Li Shen
mathsseenki@gmaillccom
JD Explore Academy
Yan Sun" The University of Sydney
yaam:8899@unissyddee..oo
Weiwei Lin
linww@scut.co edu.cn
South China University of Technology Peng Cheng Laboratory
Dacheng Tao
dacheng. too taw.lgaallal.mmmmmmmmmmmmmmmmlte
JD Explore Academy
Reviewed on OpenReview: https: openreview. net/ forum? id= dd-ttrgVVIZa
Abstract
Personalized federated learning, variant of federated learning, trains customized mod- els for clients using their heterogeneously distributed data. However, it is still inconclusive about how to design personalized models with better representation of shared global knowl- edge and personalized pattern. To bridge the gap, we in this paper explore personalized models with low-rank and sparse decomposition. Specifically, we employ proper regulariza- lion to extract low-rank global knowledge representation (GKR), so as to distill global knowledge into a compact representation. Subsequently, we employ a sparse component the obtained GKR to fuse the personalized pattern into the global knowledge. As solution, propose two-stage proximal- based algorithm named Federated learning with mixed Sparse and Low-Rank representation (FedSLR) to efficiently search for the mixed models. Theoretically, under proper assumptions, we show that the GKR trained by Fed- SLR can at least sub-lincarly converge to a stationary point of the rogularized problem, and that the sparse component being fused can converge to ils stationary point under proper settings. Extensive experiments also demonstrate the superior empirical performance of FedSLR. Moreover, FedSLR reduces the number of parameters, and lowers the down-llnk communication complexity, which are all desirable for federated learning algorithms. Source code is available in https: //gt thub. www/houageeeecocccoocceecc http://aannnnaihnnnnggaaa anwhaag fedslr.
1 Introduction
Federated Learning (FL) (McMahan et al., 2016) has emerged as a solution to exploit data on the edge in a privacy-preserving manner. In FL, clients train global model collaboratively without sharing private data. However, the global model may not produce good accuracy performance for each client's 's task due to the existence of Non-IID issue (Zhao et al,, 2018).
"Wor done during internships JD Explore Academy. İT.i Shen the corresponding author.

---

Published in Transactions on Machine Learning Research (02/2023)
To bridge the gap, the concept of Personalized Federated Learning (PFL) is proposed as remedy. PFL deploys customized models for each client, which typically incorporates a global component that represents global knowledge from all the clients, and a personalized component that represents the local knowledge. The main stream of PFL can be classified into four genres, i.c., layer-wise separation (Arivazhagan et al., 2019), linear interpolation (Deng el al., 2019), regularization (Li et al., 2021c; Wang et al., 2023), and personalized masks (Huang et al., 2022b; Li al., 2021a; 2020; Dai et al., 2022). All of these studies either explicitly or implicitly enforce a global component and a personalized component to compose the personalized models. this topic having emerged in sight, PFL is still far from its maturity. Particularly, it is still unclear how to better represent the global knowledge with the global component and the personalized pattern with the local component, and more importantly, how to merge them together to produce better performance.
Despite plethora of research
Morcover, existing PFL studies usually involve additional personalized parameters their local models, e.g., (Deng ct al., 2020). However, the local knowledge should be complementary to the global knowledge, which means it does not need dominating expressiveness in the parameter space. On the other hand, the global knowledge, which represents clients' commonality, and is complemented by personalized component, may not need a large global parameter space to achieve its functionality. All in all, we are trying to explore:
Do we need such amount of parameters to represent the local paltern, as well as the global knowledge? Can the expressiveness of local models be optimized by intersecting the param- eter space of the personalized and global component?
To answer above questions, we utilize the idea of decomposing personalized models as a mixture of a low- rank Global Knowledge Representation (GKR) and sparse personalized component, wherein the GKR is used to extract the core common information across the clients, and the sparse component serves reprosenting the personalized pattern for each client. To realize the low-rank plus sparse model, we employ proper regularization on the GKR and the sparse component in two separate optimization problems. The regularization-involee problem, for which there is not an existing solution to our best knowledge, are alternatively solved via the proposed two-stage algorithm (named FedSLR). The proposed algorithm enjoys superior performance over the personalized tasks, while simultaneously reducing the communication and model complexity. In summary, we highlight. the following characteristics that FedSLR features: (i) The GKR component can better represent the global knowlodge. Its accuracy performance is increased compared to general FL solution (e.g., FedAvg). (ii) The mixed personalized models, which are fused with local pattern represented by their sparse components, obtain SOTA performance for each client's task. (iii) Both the two models being generated can be compressod to have a smaller amount of parameters via factorization, which is easier to deploy in the commonality hardware. Besides, down-link communication cost in the training phase can be largely reduced according to our training mechanism.
Empirically, we conduct extensive experiment to validate the performance of FedSLR. Specifically, our exper- iments CIFAR-100 verify that: (i) the Global Knowledge Representation (GKR) can better represent the global knowledge (GKR model achieves 7.23% higher accuracy compared to FedAvg), and the mixed models can significantly improve the model accuracy of personalized tasks (the mixed model produced by FedSLR achieves 3.52% higher accuracy to Ditto). (ii) Moreover, both GKR and the mixed models, which respec- tively represent the global and personalized knowledge, are more compact (GKR model achieve 50.40% less parameters while the mixed model pruned out 40.11% parameters compared to a model without pruning). (iii) The downlink communication is lowered (38.34% fewer downlink communication in one session of FL). Theoretically, we establish the convergence property of GKR and the sparse personalized component, which showcases that both components asymptotically converge to their stationary points under proper settings.
To the end, our contributions are summarized as follows,
We derive shared global knowledge with a low-rank global knowledge representation (GKR), which alone may not represent personalized knowlodge covered by local data. Therefore, we propose to perform fusion of personalized pattern via merging sparse personalized components with GKR, which only incurs minor extra parameters for the mixed models.
2

---

Published in Transactions on Machine Learning Research (02/2023)
We propose new methodology named FedSLR for optimizing the proposed two-stage problem. FedSLR only requires minor extra computation of proximal operator on the server, while can significantly boost performance, reduce communicatin size, and lighten model complexity.
We present convergence analysis to FedSLR, which concludes that under the assumption of Kurdyka- Lojasiewicz condition, the GKR produced by FedSLR could at least sub-linearly converge to a stationary point. Also, the sparse components can asymptotically converge to their stationary points under proper settings. Extensive empirical experiments also demonstrate the superiority of FedSLR.
2 Related Work
Federated learning. FL was first proposed in (McMahan et al., 2016) to enable collaborative training of a network model without exchanging the clients' data. However, the data residing in clients are intrinsically heterogencous (or Non-IID), which leads to performance degradation of global model (Zhao et al., 2018). Many attempts have been proposed to alleviate the data heterogeneity issue. SCAFFOLD (Karimireddy et al., 2020), for example, introduces variance reduction technique to correct the drift of local training. Similarly, FedCM (Xu et al., 2021) uses client-level momentum to perform drift correction to the local gradient update. Another genre, the prox-based algorithm,, e.g,, FedProx (Li et al., 2018), incorporates a proximal term in the local loss to constrain the inconsistency of the local objective. In addition to the proximal term, a subsequent study, (Acar et al., 2021) further incorporates a linear term in its local loss to strengthen local consistency. FedPD (Zhang et al., 2021), FedSpeod (Sun et al.) and FodAdmm (Wang et al., 2022) explore the combination of the method of ADMM into FL to counter the Non-IID issue.
Personalized federated learning. PFL is a relaxed variant of FL. In PFL, the goal is to train customized models for cach client, and each customized model is used to perform an individual task for each client. We classify the existing PFL solutions in four genres. The first genre is to separate the global layers and personalized layers, e.g., (Collins et al., 2021; Liang et al., 2020; Arivazhagan et al., 2019), which respectively contain global knowledge and personalized pattern of each specific client. The second genre is linear interpolation. To illustrate, (Deng et al., 2020; Mansour et al., 2020) and (Gasanov et al., 2021) propose to linearly interpolate personalized and global component to produce the personalized models. The third genre, inspired by the literature on multi-task lcarning, is to introduce proximal regularizer to constrain the proximity of global model and personalized models, e.g., (Li el al., 2021c; Yu el al., 2020). The last genre is to personalize the global model with a sparse mask, see (Huang et al., 2022b; Li et al., 2021a).
Robust PCA and low-rank plus sparse. In robust PCA (Candès et al., 2011; Xu et al., 2010), a data matrix X is decomposed to a low-rank matrix L and sparse mairix S, in which is the principal component that preserves the maximum amount of information of the data matrix, and S is used to represent the outlier. The low-rank plus sparse model formulation is known to increase the model expressiveness compared to the pure low-rank and pure sparse formulation. In recent years, the idea of low-rank plus sparse is also adopted in statistical model (Sprechmann et al., 2015), deep learning models, e.g., CNN (Yu et al., 2017), and more recently, Transformer (Chen et al., 2021a;b). Motivated by the existing literature, we aim to preserve the model expressiveness from compression by mixing the two compression techniques. Analogous to robust PCA, in our PFL setting, we use the low-rank component to represent the global knowledge order to preserve the maximum amount of knowledge shared by clients, and we use the sparse component to represent the local knowledge, which is like an outlier from the global knowledge.
In this paper, we apply the idea of sparse plus low-rank decomposition to bridge FL and PFL. Specifically, we train the low-rank GKR via proximal-based descent method. Then, along the optimization trajectory of GKR, each client simultaneously optimizes the personalized sparse component. using their local data. In this way, the GKR shares the commonality among all user's data, and the personalized component captures the personalized pattern, which facilitates the mixed model acquire better local performance. We emphasize that our proposed idea, that the personalized model can be decomposod to a low-rank GKR and sparse personalized component, is novel over the existing literature.
3

---

Published in Transactions on Machine Learning Research (02/2023)
① Server update
Auxiliary variable update server and clients
Prox
Avg(
) "g Avg(Viirt)))
fi,t+1 = Vf
LR GKR Local model
De-compose send the GKR (communication reduction)
Local model is sent server
Local training with proximal term
Local fusion with sparse component
Fix LR GKR Trainable Sparse
Receive and reconstruct GKR
Upload to server
Train
Train
Mixed Personalized model
Illustration of FedSLR. Firstly, the server performs proximal operator over the average of local models to enforce low-rank global knowledge representation (GKR). Secondly, each layer weights of GKR are decomposed into two smaller matrices and are distributed to clients. Clients reconstruct the GKR using these matrices and start local training with it. Thirdly, clients fuse the personalized sparse component with respect GKR. Finally, the local gradient (equivalently, the auxiliary variable Ya,1) is updated on both servers and clients according the local models communicated by the clients.
Figure 1:
3 Problem Setup
We first assume there are clients (indexed by i) the system. Each client hosts n, pieces of data. Classical FL problem. The FL problem in (McMahan al., 2016) is formulated as follows:
1 w = arg min { [(1n) = M
M Σ M(w)
(1)
where f(()) 1 Ej= Loss(w; (w; (.,, yj)) is the the empirical loss (e-g., average of cross entropy) of the i-th clicnt. However, the global model obtained by minimizing global consensus may not perform well in personalized lasks, in other words, is incapable of minimizing each specific fi(.).
nu
Alternatively, under the assumption that the model deployed in each client can be not exactly the same, our PFL formulation can be separated into two sub-problems, as follows.
Global knowledge representation (GKR). To compress the global knowledge into a smaller size of model, we alternatively establish the following global knowledge representation problem.
(P1) Find a stationary point r0* such that 0 E Of(#=*)
(2)
where f(w) = [(w) = M
Si(w)) + R(w)= = Will
Here, we use R(w) to impose low-rank regularizer for model with L layers, where -| is the nuclear norm. Prior enter the model weights into the regularizer, follow scheme in (Idelbayev & Carreira-Porpinán. 2020) to do the matrix transformation for different layers of neural network, i.e., W; E xdd, 2 7 (wi), where x(w)) maps the original weights of (-th layer into the transformed matrix By factorization, one can
Here show the detailed implementation for this matrix transformation. We apply different trausformations for different layer architecture of deep ncural network. For the convolutional layer, reshape the original vector weights of convolutional layer wi xxd matrix goxdiix, where i, respectively represents the output/inppn channel and kernel size. For linear layer, map vector uy Roxi matrix wy Ro., where and are output /inpuut neuron
4

---

Published in Transactions on Machine Learning Research (02/2023)
decompose matrix weights of each layer Wi into Wi U,V," where Uj E BRa., Vi E R and r is the rank of matrix. With sufficiently large intensity of the regularizer, could be reduced to sufficiently small number such that the number of parameter of the compressed model can be much smaller than that of the full size model, ic., r x (di,1 + d1,2) & di, x d1.2. In this way, we distill the global knowlodge into a compact model with fewer parameters.
Fusion of personalized pattern. Constructed upon the low-rank GKR obtained before, we further establish formulation to merge the personalized pattern into the global knowledge, follows:
(P2) {p.) = mig {f(p.) == f + +p:)} + (R(p:) == pllp:111..
(3)
P.
In this formulation, we use a sparse component to represent the personalized pattern, so as to complement and improve the expressiveness of GKR. Or more specifically, we use a low-rank global plus sparse personalized model to do inference for the personalized task. The sparsity of the personalized component controls the degree of local knowledge to be fused. As show later, properly sparsifying the personalized component enables belter merge between global and local knowledge, while simply no sparsification too much sparsification would both lead to performance degradation. Moreover, the sparse component would only introduce minor extra. parameters upon GKR. Here we use L1 norm to sparsify the personalized component.
Remark 1.
Our proposed problem formalation is seporated into two sub-problems. The objective of the first sub-problem (P1) is to train global knowledge representation, aiming to derive the global knowledge, and that of the second sub-problem (P2) is to fuse the personalized pottern into GKR that we obtain in the first problem. Our problem definition is unorthodoz to the main stream of PFL research, most of which can be generulized to a bi-variable optimization problem (see the general form in Eq. (3) of (Pillutla el al., 2022) ), and therefore the methods FedSim/ FFedltt in (Pillutla et al., 2022) can not be directly applied to our problems.
4 Methodology
We now derive our FedSLR solution, which can be separated into two phases of optimization.
Phase I: represent the global knowledge with a low-rank component. To mitigate the communi- cation cost and the computation overhead in the local phase, we propose to postpone the proximal operator to the global aggregation phase. Prior to that, we switch the task of local training of i-th client to solve a sub-problem as follows:
1 21/g
(Local Phase) W1,441 arg min fi(w) - (Nr,ts w) +
w. w||
(4)
where My is the global learning rate used in the aggregation phase, Th. is an auxiliary variable we introduce to record the local gradient., which essential the aggregation phase to recover the global proximal gradient descent. This sub-problem could be solved (or inaccurately solved) via an iterative solver, e.g., SGD,
After the local training is finished, the client sends back the local model after training, i.e., Wi,+1 to server?. Then, with W7,++ ready, we introduce an update to the auxiliary variable in each round on both server and client sides, as follows:
(Auxiliary Variable Update) 78,+1 = 7/. + 1 1(w, 1lg
(w, - wt,(+1)
(5)
With auxiliary variable ((r,41 } and local weights (wit+1) ready, we take a global proximal step in server,
M
M
(Aggregation) Wi+1 = Prox, All-II Il+
Wi+t1
77
Σ
7,++1
(6)
M
M
1=1
2Tee upload from elients {wr,++1} are sparse/low-ranks and therefore FedSL. cannot reduce the uplink communication. However, one can apply commmication--edleeee technique, e-g,, sparsification, here. We leave this future work.
5

---

Published in Transactions on Machine Learning Research (02/2023)
Remark 2. The inspiration of our proposed method stems from the LPGD method (a direct opplication of prozimal descent. algorithm into local steps, sec. Appendiz A.2). Firslly, observed from the oplimality condition of Eq. (4) that we have V fi(wee+1)) - Vi, _ (w; - -.,,,1) 0. Combining this with (5) it is sufficient to show that Yt,++ = vf((w)1+1). Then, plugging this relation into aggregation in Eq. (6), we show that if the local iterates converge, i.e., Wi,t+ Wt, Vfi(ws,t-1) can indeed approzimate V(((w.) and thereby the global ileratice update can reduce to W++1 P (w, "l V V (w:)), which is the update form of vanilla prozimal gradient descent. In addition, our solution excels the direct application of LPGD method in two aspects: i) We postpone the prozimal operator with intense computation to the aggregation phase, which only need to perform once in one global iteration, and is computed by the server with typically more sufficient compulational resources. ti) The downlink commumication can be saved. This can be achieved vio layer- wise de- composing the low ronk global weights into two smaller matrices, and send these matrices in replacement of the dense GKR.
"i
Phase II: Local fusion with a sparse component. After the GKR wi is updated in the first phase of optimization, we train the personalized component to acquire fusion of the personalized pattern into the global knowledge. This can be done by performing a proximal step as follows,
(Local Fusion) Pi,,k+11 Proxmull-ll (Pea. - Ty V2Ji(w: + PL)
(7)
where Proxmalll I-l (.) is used to sparsify the personalized component, di is the local stepsize, V2 takes the differentiation with respect p, and & is the stochastic sample from the i-th client's local data.
Remark 3. Our phase II optimization relies the classical prozimal stochastic GD method. It freezes the GKR w, oblained in the previous global round, and oplimize p; lowards the local loss in order to absorb the local knowledge. The prozimal operator for L1 regularizer is performed in every local step, but the overhead should not be large (compared to operator for low-rank regularizer), since only direct value shrinkage over model weights needed to be performed (see Appendeix A.1).
A Algorithm Federated learning with mixed Sparse and Low-Rank representation (FedSI.R
Input Training iteration T; Local stepsize m,; Global stepsize da Local step K;
1: procedure SERVER'S MAIN LooP
2: for 0, T do
3: Factorize w, to (Ur,} and [V.} by applying layer-wise SVD.
for i [M] do
5:
Send {U,,}} and { {Vii} to the i-th client, invoke its main loop and receive w.,+1
7e.41 = %o, By (w: w..41)
Update auxiliary variable on server
7:
Wh+1 = P1- ( EM W5,441
# EM 7.411)
b Apply the update
procedure CLIENT'S MAIN LooP
9:
Receive (U.i} and [V.,} from server and recover w.
10:
Call Phase I OPT to obtain w1,++1 and 71,+11
11:
Call Phase II OPT to obtain Pt,,K.
12:
Send 11,44 to Server, and keep P.A,K and Ti,41 privately.
13:
procedure PIASE I OPT (GKR)
14:
Wi,++1 arg miny fe(wx) (TH,s, w) + 24g || w||
Train GKR in Local
15:
7Mt+1 = Yi,t + 1 (we- wi.++)
> Update the auxiliary variable on clients
16:
Return W5,++1 and 78,+1
17:
procedure PHASE TI OPT (PERSONALIZED COMPONENT)
18:
Pi,t, = Pt,t-1KK
Warm-start from the last-called
19:
for k= 0,I,,..,KK d
20:
P.,.141 Prox (P...A 1// 2ff(w. P..AA E))
Local fusion
21:
Return P...K
The entire workflow of our FedSLR algorithm formally captured Algorithm 1. Note that in line of Algorithm 1, the layer-wise SVD is not necessarily be performed in real implementation. We can reuse the SVD results in line 7 to obtain (U.) and (V,)). We add this line of code for better readability.
6

---

Published in Transactions on Machine Learning Research (02/2023)
5 Theoretical Analysis
We in this section give the following basic assumptions to characterize the non-convex optimization landscape. Before we proceed, we first set up a few notations. We use || to represent the L2 norm unless otherwise specified. 8R(()) is a set that captures the subgradient. for function R(.). dist(C, D) = inf x - yll x E C E D) captures the distance between two sets.
Assumption 1 (L-smoothness). We assume L-smoothness over the chient's loss function. Formally, we assume there erists a posétive constant L such that [VV -f,(w")) s Lilw-w''l
holds for w, w' E Rd. Assumption 2 (Bounded gradient). Suppose the gradient of local loss is upper-bounded, i.e,, there exists positive constant B such that [(w)]l &
holds for w E RRd.
Assumption 3 (Proper closed global objective). The global objective f(-) is proper 3 and closed 4.
Remark 4. Assumps and are widely used to characterize the convergence property of federated learning algorithmss e.g.,Xu el al., 2021; Li et al., 2019; Gong el al., 2022) By Assumplion 3, we inlend to ensure that i) the global objective lower bounded, i.e., for w Rd, f(w) z Eie f((w) > -0, and ti) the global objective is lower semi-continuous. The assumption is widely used in analysis of prozimal algorithms. e.9, (Wang et al,, 2018; Li & Pong, 2016; Wu el al., 2020).
Theorem 1 (Subsequence convergence). Suppose that Assumplions 1-3 hold true, the global step size is chosen as 0 < Tl I 2T and that there erists subsequence of sequence (w,, Wi,s Vaa) converying to cluster point (w", w., ). Then, the subsequence generated by FedSLR establishes the following property:
lim (Wp-1. w +1), (13++13)) = lim (wy, (wo }. (r }} = , [ {) 1-000
(8)
1
Moreover, the cluster point is indeed stationary point of the global problem, equivalently,
0 E (R(ww)
Σ vi(w")
(9)
Remark 5. Theorem 1 states that if there exist a subsequence of the produced sequence that converges to a cluster point, then this cluster point is indeed a stationary point of the global problem (P1). The additional assumption of converging subsequence holds if the sequence is bounded (per sequential compactness theorem).
Under the mild assumption of Kurdyka-Lojasievins (KL) property (Attouch et al., 2010), we show the last iterate global convergence property of the whole sequence.
Then, we define the potential function, which serves keystone to characterize the convergence.
Definition 1 (Potential function). The potential function defined as follows:
M
M Σ 1m1
M
1
Σ + D, (z, (y:))())) = M
+ R(x)+ +
mr. x - -y)) +
Σ
|
yilla.
(10)
M
M
27g
We then make an additional assumption of KL property over the above potential function.
Assumption 4. The proper and closed function D,,, (x, (y.), {ri) satisfies the KL properly with function (p))) = c- given 0 E [0,1)
Remark 6. Given that f is proper and closed as in Assumption 3, Assumption 4 holds true as long as the local objective fa(.) is a sub-anabylic function, logarithum function, an exponential function, or a semi- algebraic function (Chen et al., 2021c). This assumption rather mild, since most of the nonconver objective functions encountered in machine learning applications falls in this range. The definition of KL property is moved to Appendia C.1 due to space limilations.
A function f is proper it never takes the value -oo and also is not identically equal +00.
4 A function f is said be closed for each TR, the sublevel set (ar E (ff(() ai) is closed set..
7

---

Published in Transactions on Machine Learning Research (02/2023)
Under the KL property, showcase the convergence property for GKR in the phase optimization.
Theorem (Glocal convergence of phase-one optimization). Suppose that Assumptions 1-4 hold, the global step size chosen as 0 < Ty S Σ. and that there ezists subsequence of (w,, Wi,t, Yi,)) converging to cluster point (w", w.,")) Under different settings of 0 of the KL property, the generated sequence of GKR eslablishes the following converyence rale:
Case = O. For sufficiently large ileration T > la,
dist 0,
1
Vi((w)) +R((w)) =0 (finite itcrations)
(11)
Case (0, 5)1 Por sufficiently lorge ileralion > t/-
M
Cing
dist 0,
((((T) V S
(1 -C)) (linear convergence)
(12)
M
C2 C2
1=
Case 0 (2, 1). For all T > 0, we have:
dist (0,
1 M
Σ i=1
M
Vi(wT)+
C3T- ((R(UT)))R((UTT)) -
BR(OTT)
(sub-linear converyence)
(13)
where C1 = 4(ng + n
1 + C2 = L' + 1
+ 1, C4 = C---1--033 C3 = L + ngL + 1 no 2n."
91
Cs
G. C2 122--/22 120 1)C4 are all positive constants.
Moreover, the iterate w, converges the stationary point of problem (P1) with any initializaaion, i.c., lim Wi = w where it" satisfies 0 E @R((b) + M EM Vf(("").
Remark 7. The converyence rate to stationary point is heavily determined by parameter 0 in the KL property. A smaller f implies that the potential function is descended faster in its geometry, and therefore guaranleeing a Jaster convergence rale. Specifically, for 0 = 0, the stationary point could be reached within finite iterations. For E (0, [0, linear convergence rate can be achieved. While for 0 E (2,1), 1), only sub-linear convergence rate can be achieved. In summary, as long as the potential function satisfies the KL property with [0, 1), the GKR always converges to stationary point with respect to in Eq. (2) if oc.
Then we use Theorem 3 to characterize the convergence of local fusion phase. Here we apply gradient mapping for the personalized component as convergence criterion (same in (Li & Li, 2016), (Metel & Takeda, 2021)), which is formally defined as Gy, (w,, Pt.t,)) 1 m V2fi(w.,, pt), where V2f.(w,, Pt,t,k) is the gradient respect to the second parameter i.c., p.
et al.,
q (Pi,c.k Prox IH (Pr.ck
Assumption 5. The variance of stochastic gradient with respect to for any E Rd and p E Rd is bounded follows, E 22f((w + p: V2fi + +)11 0²
Theorem 3 (Convergence rate of local fusion phase). With assumptions for Theorem and an extra as- sumption 5, suppose that local step size is chosen 0 m 22, FedSLR in its local fusion phase exhibits the following converyence guarantee:
Elllg (we, Pi., (2(2:(0' .p.o,.) 0i .p)))
C7 + CCo
2 2 +1)0²)
(14)
TK
TK
where Cs
m $ 1 CT = (NIN11) + 1)((wo - 2t 1 + N(N+1)
ng (D,, (wo, (wooh, (rrol)
2
Dn, (wr, {w]), (x)))) 1 constants, and dz p)) [u( p) R(p) is the loss in (P2).

---

Published in Transactions on Machine Learning Research (02/2023)
Remark 8. The gradient mapping 1|9 (wr, Pi,,,)) can be viewed a projected gradient of the fusion loss in (P2). If m1 (w,, pil S 6, the personalized component Pi,t, is indeed an approzimate stationary point for the loss of local fusion, i.e., 1/V2f((w, + Pi,t) + VR(p;,))l O(e). where VR(p(t) E OR(pLt), Takeda, 2021) Theorem 3 showcases that both the first and second term in the upper bound diminiish as T + oo. Therefore, if the variance o² + 0, which holds if laking full batch size, the stationary point is reached at the rate of (++)
see Eq. (8) in (Metel
6 Experiment
In this section, we conduct extensive experiments to validate the efficacy of the proposed FedSL.R
6.1 Experimental Setup
Datasets. We conduct simulation DIFARIO/CTFAR100/TIII Imagennt,,, with both ITD and Non-ITD data splitting, respectively. Specifically, for IID splitting, data is splitted uniformly to all the 100 clients. While for Non-IID, we use a-Dirichlet distribution to split the data to all the clients. Here a is set to 0.1 for all the Non-ITD experiments. Datails of the setting are given Appendix B.1.
Baselines. We compare our proposed FedSLR solution with several baselines, including some general FL solutions, e.g., FedAvg (McMahan et al., 2016), FedDyn (Acar et al., 2021), SCAFFOLD (Karimireddy et al., 2020), some existing PFT. solutions, e.g,, FedSpa (Huang et al., 2022b) Ditto (Li et al., 2021c), Per-FedAvg (Fallah et al., 2020), FedRep (Collins et al., 2021), APFL (Deng et al., 2020), LgFedAvg (Liang et al., 2020) and a pure Local solution. We tune the hyper-parameters of the baselines to their best states.
We consistently use ResNet18 with group norm (For CIFAR10/100, with kernel size 3 in its first conv, while for tinyimagenct, use an SGD optimizer with weight decay parameter 1e-3 for the local solver. The learning rate is initialized as 0.1 and decayed with 0.998 after each communication round. We simulate 100 clients in total, and 10 of them are picked for local training for each round. For all the global methods (i.e., FedSLR(GKR) 5, FedDyn, FedAvg, SCAFFOLD). local epochs and batch size are fixed to 2 and 20. For FedSLR and Ditto, the local epoch used in local fusion is 1, and also with batch size 20. For FedSLRR, the proximal stepsize is f2 = 10, the low-rank penalty is 0.0001 and the sparse penalty is μ = 0.001 in our main experiment.
Models and typer-parameters.
instcad) in all set of experiments. We
6.2 Main Results
CIFAR10
CIFAR100
Tinylmagenet
0.8
0.6
(Non- IDD
Top-1 Acc
0.0
0.6
0.4
0.4
0.4
0.2
Fediig
APR
0.2
0.2
Loca
0.0
0.0
200
400
600
800
1000
200
400
600
800
1000
200
400
600
800
1000
0.4
0.8
0.6
Top-1 Acc
0.3
0.6
0.2
0.4
0.2
0.1
0.2
Tedite
0.0
0.0
400
800
800
1000
200
800
1000
Communication Rounds
Communication Rounds
Communication Rounds
Figure 2: Test accuracy communication rounds over TTD and Non-IID.
Performance. We show the accuracy in Figure and Table 1, and discuss the performance comparison by separating IID and Non-IID cases. The performance evaluation could also be interpreted by its representation visualization, see Figure& 4 in Appendix B.3.1.
We the performance of GKR model obtained by Phase optimization deploying all the clients.
9

---

Published in Transactions on Machine Learning Research (02/2023)
Best accuracy performance in Non-IID. Our personalized solution FedSLR(mixed) significantly outperforms all the other personalized baselines in all the three datasets. Particularly, FedSLR achieves 3.52% higher accuracy to Ditto, 8.32% and 18.46% accuracy gain to FedSpa and Per-FedAvg in the Non-IID CIFAR100 task.
Most resilient to performance degradation in IID. We observe that all the personalized solutions experience performance degradation in the IID setting, i.., their performance usually cannot emulate the SOTA global solution, e-g,, FedDyn. However, we see that FedSLR (mixed) is the most resilient one. Though it experiences an accuracy drop (1.45% accuracy drop compared to the non-personalized GKR modcl), still maintains the highest accuracy compared to other personalized baselines.
Competitive convergence rate. FedSLR maintains a competitive convergence rate compared to other personalized solutions, though we still observe that in some experimental groups (e.g., IID tinyimagenet) its convergence rate seems be slower than other baselines the initial rounds.
Test accuracy (%) on the CTFAR-10/100 and TinyImagenet under ITD and Non-ITD setting. The first 4 solutions are global solutions, and the others are personalized solutions.
Table 1:
CIFAR-10
CIFAR-100
Tinylmagene"
Method
ITD
Non-IID
ITD
Non-IID
Non-ITD
SCAFFOLD
91.33
82.91
66.68
59.48
43.13
34.11
FedDyn
92.61
90.14
68.68
64.29
43.52
38.02
FedAvg
90.25
82.89
61.92
55.78
35.17
30.56
FedSLR (GKR)
91.73
87.52
66.40
64.22
41.32
35.13
Avd-FedAvg
89.37
91.55
57.10
63.73
34.41
37.52
LGFedAvg
38.32
81.35
12.96
49.90
5.34
35.68
FedRep
89.28
93.41
15.36
60.42
46.42
Ditto
89.16
94.39
59.36
78.67
34.78
58.30
APFL
75.11
87.11
30.99
61.14
20.16
48.02
Local
38.30
82.17
10.97
47.99
3.86
34.28
FedSpa
88.31
93.19
48.00
73.87
30.39
53.76
FedSLR (mixed)
89.72
95.30
64.95
82.19
38.20
59.13
Communication and model parameters. Table 2 illustrates the communication cost and model plexity with different methods. As shown, GKR model of FedSLR has smaller model complexity with smaller commuication overhead in the training phase (approximately 19% of reduction compared to full- model transmission). In addition, our results also corroborate (hat, built upon the low-rank model, FedSLR acquires personalized models with only modicum parameters added. The mixed personalizd model acquires 17.97% accuracy gain with 29% more parameters added upon the global GKR model.
Table 2: Communication cost (GB) and # of params (M) on the Non-IID splitting of three datasets. FedAvg(*) refers to a class of algorithms with no communication coluuction/increnn e.g., FedDyn.
CIFAR-10
CIFAR-100
TinyImagenet
Method
Comm cost. # of params.
Comm cost # of params]
Comm cost. # of params!
FedAyg (+)
893.92
11.17
893.92
11.17
893.92
11.17
SCAFFOLD
1787.83
11.17
1787.83
11.17
1787.89
11.17
FedSLR (GKR)
626.89
3.51
722.60
5.54
730.00
5.34
APFL
893.92
22.35
893.92
22.35
893.92
22.35
FedSpa
446.96
5.59
446.96
5.59
446.96
5.59
LG-FedAvg
0.41
11.17
4.08
11.17
8.13
11.17
FedRep
893.51
11.17
889.84
11.17
885.78
11.17
FedSLR (mixed)
626.89
3.96
722.60
6.69
730.00
7.59
10

---

Published in Transactions on Machine Learning Research (02/2023)
Sensitivity of hyper-parameters. We postpone the ablation result to Appendix B.3.2. Our main ob- servations are that properly adjusting low-rank penalty for the GKR facilitates a better knowledge rep- resentation, and that ii) properly sparsifying the local component facilitates better representation of local pattern, and thereby promoting personalized performance. These observations further verify that our choice of low-rank plus sparse models as personalized models can further boost performance. Moreover, we perform the sensitivity analysis of the local steps in Section B.3.2. The results show that sufficiently large K, e.g-. two local epochs, required guarantee the empirical performance of FedSLR, since our algorithm requires accurate solution for solving the local sub-problem.
7 Conclusion
In this paper, present the optimization framework of FedSLR to fuse the personalized pattern into the global knowledge, our solution not only acquires better representation of the global knowledge, promises higher personalized performance, but also incurs smaller downlink communication cost and requires fewer parameters in its model. Theoretically, our analysis on FedSLR concludes that the last iterate of GKR could converge to the stationary point in at least sub-linear convergence rate, and the sparse component, which represents personalized pattern can also asymptotically converge under proper settings.
to achieve personalized federated learning. Empirical experiment shows that
Acknowledgments
LS is supported by the Major Science and Technology Innovation 2030 "Brain Science and Brain-like Re- search" key project (No. 20212D0201405), WL is supported by Key-Area Research and Development Pro- gram of Guangdong Province 00221000112000022 National Natural Science Foundation of China (62072187). the Major Key Project of PCL (PCL2021A09), and Guangzhou Development Zone Science and Technology Project (2021GH10).
11

---

Published in Transactions on Machine Learning Research (02/2023)
References
Durmus Alp Emre Acar, Yuc Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N Whatmough, and Venkatesh Saligrana. Federated learning based on dynamic regularization. arXiv:2111.04263, 2021.
ar preprinl
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Federated learning with personalization layers. arXiv preprint Xrve: 991.00818 2019.
Hédy Attouch, Jérôme Bolte, Patrick Redont, and Antoine Soubeyran. Proximal alternating minimization inequality.
and projection methods for nonconvex problems: An approach based on the Mathematics of operations research, 35(2):438 457, 2010.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. arXiv preprint wwXiv1807.00455 2018.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning on user-held data. arXiv preprint orXiv:6611004482 2016.
Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 58(3):1 37, 2011.
Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re. Pixelated butterfly: Simple and efficient sparse training for neural network models. arXiv preprint arXiv:2112.0002 2021a.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention approximation. arXiv preprint 1rXiv:2110.15848 2021b.
Ziyi Chen, Yi Zhou, Tengyu Xu, and Yingbin Liang. Proximal gradient descent-ascent: Variable convergence under k {LL} geometry. arxiv preprint arXiv:2102.0440 04653, 2021c.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint vrXim:2010.02245. 2020.
Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In International Conference on Machine Learning, pp. 2089 2099. PMLR, 2021.
Rong Dai, Li Shen, Fengxiang He, Ximmei Tian, and Dacheng Tao. Dispfl: Towards communication--lliiee personalized federated learning via decentralized sparse training. In International Conference Machine Learning, pp. 4587-4604. PMLR, 2022.
Shuiguang Deng, Hailiang Zhao, Jianwei Yin, Schahram Dustdar, and Albert Y. Zomaya. Edge Intelligence: the Confluence of Edge Computing and Artificial Intelligence. arXiv:1909.0054 [cs), September 2019. 1909000660.. 00560. arXiv: 1909.00560.
URL http:// /wwxiv.vvvvv www.ai.orraabsa....a...aa....aae 19t///999..oo
Yuyang Deng, Mohammad Mahdi Kamani, and Mchrdad Mahdavi. Adaptive personalized foderated learning, 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Sys- tems, 33:3557 3568, 2020.
Elnur Gasanov, Ahmed Khaled, Samuel Horváth, and Peter Richtárik. Flix: A simple and communication- efficient alternative local methods in federated learning. arXiv preprint arXiv:2111 21. 1 11556, 2021.
12

---

Published in Transactions on Machine Learning Research (02/2023)
Jonas Gciping, Liam Fowl, Gowthami Somepalli, Micah Goldblum, Michael Moeller, and Tom Goldstein. What doesn't kill you makes you robust (er): Adversarial training against poisons and backdoors. arXiv preprint arXie:2102. 13624, 1(7), 2021.
Saced Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1):266738)) 2016.
Yonghai Gong, Yichuan Li, and Nikolaos M Freris. Fedadmm: A robust federated deep learning framework with adaptivity to system heterogeneity. arXiv preprint orXic:2204.05550 2022.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arxiv preprinl arxiv: 1 0009063335 2019.
Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang Hc, Keqin Li, and Albert Y Zomaya. An efficiency- boosting client selection scheme for federated learning with fairness guarantee. IEEE Transactions Parallel and Distributed Systems, 32(7):1552-1564, 2020.
Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, and Albert Y Zomaya. Stochastic client selection for federated learning with volatile clients. IEEE Internet of Things Journal, 2220))20055-00770 2022a.
Tiansheng Huang, Shiwei Liu, Li Shen, Fengxiang Hc, Weiwei Lin, and Dacheng Tao. Achioving personalized federated learning with sparse local models. arxie preprint urXiv:2201.11380 2022b.
Yerlan Idelbayev and Miguel A Carreira-Perpinal Low-rank compression of neural nets: Learning the rank of each layer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 1049-8059, 2020.
Wonyong Jeong and Sung Ju Hwang. Factorized-fi: Agnostic personalized federated learning with kernel factorization & similarity matching. arXiv preprint or arXiv:2202.002: 00270, 2022.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradien methods under the polyak-tojasiewiez condition. In Joint European conference on machine learning and knowledge discovery in databases, pp. 795-811 Springer, 2016.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic rolled averaging for federated learning. In International Conference on Machine Learning, pp. 5132 5143. PMLR, 2020.
Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Personalized and commuicattion-ffiiieett fodorated learning with lottery ticket hypothosis on non-iid datasots. arXiv preprint 2000 03377, 2020.
Ang Li, Jingwei Sun, Xiao Zeng, Mi Zhang, Hai Li, and Yiran Chen. Fedmask: Joint computation and commmication-efiiieen personalized federated learning via heterogeneous masking, In Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems, pp. 42-55, 2021a.
Guoyin Li and Ting Kei Pong. Douglas rachford splitting for nonconvex optimization with application to nonconvex fcasibility problems. Mathematical programming, 159(1):371-401, 2016.
Qinbin Li, Bingsheng He, and Dawn Song. Model-contrastive foderated learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 10713 10722, 2021b.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Amoct Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXie preprint 1rX2: 06127, 2018.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization, 2021c.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. arXiv preprint xrxi:19077.0119 2019.
13

---

Published in Transactions on Machine Learning Research (02/2023)
Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. Aduances in neural information processing systems, 31, 2018.
Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach, David Brent, Ruslan Salakhut- dinov, and Louis-Philippe Morency. Think locally, act globally: Federated learning with local and global representations. ar Xiv preprint 1ii:2001000122. 2020.
Jie Ma, Ming Xie, and Guodong Long. Personalized federated learning with robust clustering against model poisoning. In International Conference on Advanced Data Mining and Applications, pp. 238-252. Springer, 2022.
Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personaliza- tion with applications to federated learning, arXiv preprint 2XXi:2002.10619, 2020.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communicationn-ffiiennt lcarning of deep networks from decentralized dala. arxiv preprinl N4:2:600.005222 2016.
Michael R Metel and Akiko Takeda. Stochastic proximal methods for non-smooth non-convex constrained sparse optimization. J. Mach. Learn. Res., 22:115-1, 2021.
Fan Mo, Hamed Haddadi, Kleomenis Katevas, Eduard Marin, Diego Perino, and Nicolas Kourtellis. Ppfl: privacy-preserving federated learning with trusted execution environments. In Proceedings of the 19th Annual International Conference on Mobile Systems, Applications, and Services, pp. 94-108, 2021.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for lederated learning. arXio preprint (rXic:1912.13445, 2019.
Krishna Pillutla, Kshitiz Malik, Abdel- Mohamed, Mike Rabbat, Maziar Sanjabi, and Lin Xiao. Federated learning with partial model personalization. In International Conference on Machine Learning, pp. 17716 17758. PMLR, 2022.
Jinhyun So, Corey J Nolet, Chien-Sheng Yang, Songze Li, Qian Yu, Ramy E Ali, Basak Guler, and Salman Avestimchr. Lightsocagg: a lightweight and versatile design for secure aggregation in federated learning. 2022.
Proceedings of Machine Learning and Systems,
Pablo Sprechmann, Alexander M Bronstein, and Guilleroo Sapiro. Learning efficient sparse and low rank models. IEEE transactions on pottern analysis and machine intelligence, 37(9):1821-1833, 2015.
Yan Sun, Li Shen, Tiansheng Huang, Liang Ding, and Dacheng Tao. Fedspeed: Larger local interval, less commmication round, and higher generalization accuracy. In International Conference on Learning Representations.
Vale Tolpegin, Stacey Truex, Mehmet Emre Gursoy, and Ling Liu. Data poisoning attacks against. federated learning systems. In European Symposium Research in Computer Security, pp. 480 5011 Springer, 2020.
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop Edge Systems, Analytics and Networking, pp. 61 66, 2020.
Dui Wang, Li Shen, Yong Luo, Han Hu, Kehua Su, Yonggang Wen, and Dacheng Tao. Fedabc: Targeting fair competition in personalized federated learning. arXiv preprint orXiw:2302.0044 074500 2023.
Fenghui Wang, Wenfei Cao, and Zongben Xu. Convergence of multi-block bregman admm for nonconvex composite problems. Science China Information Sciences, (111::11-,, 2018.
Han Wang, Siddartha Marella, and James Anderson. Fedadmm: A federated primal-dual algorithm allowing partial participation. Xixiv preprint arXii:2203.15100 2022.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. JEEE 2020.
Transactions on Information Forensics and Securily,
14

---

Published in Transactions on Machine Learning Research (02/2023)
Baoyuan Wu, Li Shen, Tong Zhang, and Bernard Ghanem. Map inference via fz-sphere linear program reformulation. International Journal of Computer Vision, (28(7):1933-1938) 2020.
Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. Dba: Distributed backdoor attacks against federated learning- In International Conference Learning Representations, 2019.
Chulin Xie, Minghao Chen, Pin-Yu Chen, and Bo Li. Crfl: Certifiably robust federated learning against backdoor attacks. In International Conference on Machine Learning, pp. 11372 11382. PMLR, 2021.
Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust pea via outlier pursuit. Advances in neural information processing systems, 23, 2010.
Jing Xu, Sen Wang, Liwei Wang, and Andrew Chi-Chih Yao. Fedem: Federated learning with client-level momentum. ar preprint arXiv:2106.1000 10874, 2021.
Chaojian Yu, Bo Han, Mingming Gong, Shen, Shiming Ge, Bo Du, and Tongliang Liu. Robust weight perturbation for adversarial training. arXiv preprint urXiv:2205. 14826, 2022.
Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. arXiv preprinl Xix:::0002. 04758, 2020.
Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In Proceedings of the IEEE conference computer vision and pattern recognition,
pp. 7370-7379, 2017.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning frame- work with adaptivity to non-iid data. IEEE Transactions on Signal Processing, 0966055-6070, 2021.
Yue Zhao, Mong Li, Liangzhen Lai, Naveon Suda, Damon Civin, and Vikas Chandra. Federated learning
with non-iid data, Xiv preprinl 1rx: 00582, 2018.
15

---

Published in Transactions on Machine Learning Research (02/2023)
Organization of Appendix
A Implementation details
17
A.1 The proximal operator
17
A.2 Alternative designs of solving problem (P1)
17
A.3 Alternative designs sparse/low-rank formulation
A.4 FedSLR under partial participation
18
A.5 FedSLR with memory-cfficient refinement
19
A.6 Further consideration on privacy&roobustnes
19
A.6.1 Privacy
19
A.6.2 Robustness
B Missing contents experiment
20
B.1 Data splitting
20
B.2 Baselines
................................
21
B.3 Additional experimental results
21
B.3.1
Additional visualization for performance evaluation
21
B.3.2
Hyper-parameters sensitivity FedSLR
21
B.3.3
Pure global versus pure personalization
23
B.3.4 Wall time of commuiiation
24
B.3.5 Wall time of inference latency
24
C Missing contents in thcoretical analysis
24
C.1 Definition of KL, property
24
C.2 Facts
25
C.3 Missing proof of Theorem
25
C.3.1 Key lemmas
26
C.3.2 Formal proof
28
C.4 Missing proof of Theorem
31
C.4.1 Key lemmas
31
C.4.2 Formal proof
31
C.5 Missing proof of Theorem 3
35
C.5.1 Key lemmas
35
C.5.2 Formal proof
36
16

---

Published in Transactions on Machine Learning Research (02/2023)
A Implementation details
A.1 The proximal operator
The proximal operators mentioned in the main paragraph (for muclear and L1 regularizers) have the following closed-form solution.
Proximal operator for nuclear regularizer. The computation of this operator involves singular value decomposition (SVD) of the weights matrix. After SVD, the operator performs value shrinkage of the singular value. The explicit form is shown below,
Prox Anall (X) U diag(SA,, (d)) (d))
(15)
where X = U diag(d)V" V is the SVD of the averaged matrix, o(X)) = d is the singular value, and the soft threshold operation So (a: defined as follows:
2; >
(Sa())) =
3i +
2; <
(16)
0
otherwise
Note that the computation needed for this operator non-trivial, since SVD over the target matrix may requires intense computation.
Proximal operator for L1 regularizer. This operator involves value shrinkage over the target vector, with closed-form as follows,
Prox (x) = Sx)
(17)
where the (xx is the same soft thresholding operator defined above. This operator used the second phase of FedSLR, which only introduces negligible computation, since only additive on each coordinate is required for deriving the closed-form of the operator.
A.2 Alternative designs of solving problem (P1)
Proximal gradient descent is a classical solution with sufficient theoretical guarantee to solve problems with non-smooth regularizer, and specially, regularizer with nuclear norm. We now present two alternative solutions that might potentially solve problem (P1).
Direct application of proximal gradient in local steps (LPGD). One alternative solution for problem (P1) is to merge the classical proximal gradient descent into local step of FedAvg. Explicitly, show the following the local update rule for solving problem (P1), as follows.
Firstly, for local step & E 1.....,K' 1, clients do
(Local Phase) Wi.ck++ PRox,Ai -|l (Wii. - V/
(18)
i is the standard proximal operator for nuclear norm, which is guarantced to have closod-form solution (See Appendix A.1).
Here, ProxAIIII (X) A arg minz - - 1 + Z||+
After K steps of local training, the server performs the general average aggregation over the obtained low rank model, or formally,
1
(Aggregation) wi++1
w..KK
(19)
M
However, this intuitive solution comes with two main drawbacks: i) Proximal operator may be computa- tionally prohibitive perform in every step of local training, especially the training surrogate does not have enough computation resources. ii) The method cannot produce real low-rank model until the model
17

---

Published in Transactions on Machine Learning Research (02/2023)
converges. To see this, notice that the GKR w1+1 cannot be low rank unless for all possible pairs i.j E [M]. wi,++1 wj,++ In other words, the GKR distributed from server to clients cannot be compressed by factor- ization, and therefore the downlink communication cannot reduce. However, this solution might potentially ensure a reduced uplink commmication,, since the local model after training guaranteed to be low-rank, and therefore can be lactorized to smaller entities to transmit.
Direct Application of proximal gradient in global step (GPGD). Our second alternative solution is to apply the proximal step directly in the server aggregation phase, but the client follows the same local training protocol with FedAvg (without the auxiliary parameter we introduce in FedSLR).
Formally, for local step k E 001....,K K - 1, clients do:
(Local Phase)
wiikk+1 = Wiitk - f
(20)
After local models are sent back to server, server does the following proximal step:
M
(A (Aggregation)
W1+11 = Prox
1
Σ
W.LK
(21)
M
This alternative design shares the same computation and communication efficiency with FedSLR. How- ever, this solution might not produce the desired convergence property as the general proximal GD al- gorithm. To see this, first notice that the aggregation step Eq. (21) can be re-written to W++1 Prox,A||---- ww EM nus))) where UZ, é E Vfi(w,,.)) is the gradient update from the i-th client. However, if directly apply proximal gradient descent to the global problem (P1), the update rule should be W++11 Prox,AAl-II- W MI MM E (V)(w))) Notice that U, + fi(w); unless Wi,ck w. (which is not true even t + 0o due to the presence of client drift in local step, see (Li et al., 2018)). Therefore, the structure of proximal GD cannot be recovered, which means the convergence property of this method cannot be guaranteed using the proximal GD framework.
A.3 Alternative designs of sparse/low-rank formulation
In this paper, enforce the global component to be low-rank while enforcing the personalized component to be sparse (i.e., LR+S). However, note that can easily adapt our algorithm to solve other combinations of our two-stage problem, e.g., enforce Sparse global component + LR personalized component (S+LR). We now discuss some potential combinations as follows.
S + LR LR + LR. For enforcing the personalized component 20 Algorithm with a proximal operator for the muclear norm to project out some sub-spaces. However, to achieve this goal, we need to perform SVT) towards the weights in every personalized step, which would be extremely computationally inefficient.
low-rank, we can simply replace Line
S + To achieve a sparse dobaa//personalized component, we can modify Line 7 in Algorithm with proximal operator for L1 norm. Though this alternative is also computationally efficient with FedSLR, its expressiveness is limited compared to our LR+S design. Recent studics (Yu et al., 2017; Jeong & Hwang, 2022) suggest that combining two compression technique could promote the expressiveness of the model. Some further studies (Chen et al., 2021a;b) show that attention matrix for transformer can only be approximated well by sparse + low-rank matrices, but not pure sparse low-rank matrices.
A.4 FedSLR under partial participation
Partial participation, i.e, only a fraction of clients are selected in each round of training, is a common feature for federated learning. In Algorithm 2, we implement partial participation into the framework of FedSLR. In our experiment, we would consistently use Algorithm 2 for partial participation. Here we can apply arbitrary client selection schemes to further improve the practical performance of FedSLR, e.g., Huang et al. (2020; 2022a); Cho et al. (2020).
18

---

- is the last time the i-th client is called b Local Fusion with SGD Published in Transactions on Machine Learning Research (02/2023)
Algorithm 2 FedSLR under partial participation
Input Training iteration T; Local learning rate mi; Global learning rate fg Local steps K;
1: procedure SERVER'S MAIN Loop
2: for t= 0, --1 do
3: Uniformly sample a fraction of client into St
Factorize w, to {Ur,1} and (Vi,) by applying layer-wise SVD. for E St do
Send (UL,} and {Vi,} to the i-th client, invoke its main loop and receive w1,++1 Yi++1 = Yitt + Ma (wi wi,++1)
8:
for i St do
7, = Vitt
10:
W1+1 Pnal [. Eies, Wi,+1
Ei M 2he+1
Apply the update
"i
11:
procedure CLIENT'S MAIN LOOP
12:
Receive {Ur,} and [Va,} from server and recover wr
13:
Call Phase I OPT to obtain wi,+1 and 7i,+1.
14:
Call Phase OPT to obtain Pit..-
15:
Send Wi,++ to Server, and keep Prr, and 7 privately.
16:
procedure PHASE T OPT (GKR)
17:
wi,++1 arg min fi(W) (Yi,,, w)
27g 1 ||0, w||
Train GKR in Local
18:
Y1,+1 Yi. + 1 (w: ws.++1)
Update the Auxiliary Variable
No
19:
Return 11,++1 and 711+1
20: procedure PHASE II OPT (PERSONALIZED COMPONENT)
21:
Pi,t, = PP,c-,K KK
22:
for k 0, 0,1....... K - do
23:
Pitck+1 = Proxpel 1l1 (Pi,.k m1 22fi(w; + Pi,,iiE)
24:
Return Pi,,K
A.5 FedSLR with memory-efficient refinement
In Algorithm 1, the server needs to track the auxiliary variable Ti for each client, which may not be memory-efficient, especially when the number of participated clients is large. We rewrite a memory-efficiett algorithm in Algorithm Algorithm only tracks the average of auxiliary variables on the server side (Line 6), which will then be applied in the server aggregation Line 7. This mefoey-efficient implementation is identical to Algorithm 1, as they produce the same global iterates in every round.
A.6 Further consideration on privacy&rrobuttness
A.6.1 Privacy
Federated learning venerable to data leakage even though data is not directly exposed to other entities. The attacker reverso-engincer the raw data using the gradient update transmitted from the client, especially when the adopted batch size and local training step in the local training phase are small. In our setting, the same privacy Icakage issues might exist when transferring the GKR between the server and clients. Besides, notice that our FedSLR solution involves additional auxiliary parameters Ti, which can indeed approximate the real gradient when training round + so. It is interesting to investigate if using Yh, can better reverse- engineer the original data with the gradient inversion technique since known that when the local step is large, the gradient update of the global model (GKR in our case) cannot preciscly recover the real gradient from clients. We leave the evaluation of the extent. of data lea lagkage towards FedSLR future work.
19

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm 3 Memory-elficient FedSLR
Input Training iteration T; Local stepsize yR; Global stepsize Ml Local step K;
procedure SERVER'S MAIN Loop
2:
do Factorize we (Utr} and {Vi,) by applying layer-wise SVD. 4: for iE [M] do Send {Ur,}} and (Vi.c) to the i-th client, invoke its main loop and receive w1,44
for t=0,1,...,2
6:
7++1 7 + # EE 1 (w, wi,++1)
D. Update auxiliary variable on server
w1+11 = PH + EM Wi,4+1 7+41)
b Apply the update
procedure CLIENT's MAIN LoOP
9:
Receive (U.,) and (V.,} from server and recover wes
Call Phase I OPT to obtain w1,441 and "1,41
11:
Call Phase II OPT to obtain P...K-
12:
Send 11,4411 to Server, and keep PiA, and 78,44 privately.
13:
procedure PHASE OPT (GKR)
14:
W0,++1 arg min fc(w) (Tea; w) + 2ng 1| w||
Train GKR in Local
15:
7e+++ = Yi.t + 1 (w: w((+1)
b Update the auxiliary variable
16: Return W1,++1 and 7i,++
17: procedure PHASE TI OPT (PERSONALIZED COMPONENT)
Pi,t,0 = Pt,t-1.K
19:
for k= 0,,..,.... 1.......' K do
Pi,,441 Pr (Pr..k 1/ Vaf((w: -...AEE))
Local Fusion with SGD
21:
Return Pi..K
To further promote the privacy-preservnng ability of our method, defense solution, e.g,, differential privacy (Wei et al., 2020; Truex et al., 2020). secure aggregation (Bonawitz et al., 2016; So et al., 2022), trusted execution environment (Mo et al., 2021) can potentially be adapted and integrated into our training protocol.
A.6.2 Robustness
Federated learning is vulnerable to data poisoming attack (Tolpegin et al., 2020; Xie et al., 2019; Bagdasaryan et al., 2018). Malicious clients can modify the data used for training to poison the global model such that the model experiences substantial drops in classification accuracy and recall for all (or some specific) data inputs. For personalized federated learning, the poisoning attack is still effective (Ma et al., 2022) by poisoning the global component, which is shared among all the clients. It is future work to compare the resilience of data poisoning attacks using low-rank plus sparse formulation among existing personalized solutions.
Some potential defense solutions, e.g., adversarial training (Geiping et al., 2021: Yu et al., 2022), certified robustness (Xie et al., 2021), and robust aggregation (Pillutla et al., 2019) can potentially be applied in the training phase of the global component to further promote robustness of the personalized models.
B Missing contents in experiment
B.1 Data splitting
There totally M = 100 clients in the simulation. We split the training data to these 100 clients under IID and Non-IID setting. For the IID setting, data are uniformly sampled for each client. For the Non-IID setting, we use a-Dirichlet distribution on the label ratios to ensure uneven label distributions among devices as (Hsu et al., 2019). The lower the distribution parameter a is, the more uneven the label distribution will be, and would be more challenging for FL. After the initial splitting of training data, we sample 100 picces of testing data from the testing to each client, with the same label ratio of their training data. Testing is performed on each client's own testing data and the overall testing accuracy (that refer to Top-1 Acc
20

---

Published in Transactions on Machine Learning Research (02/2023)
in our experiment) is calculated the average of all the client's testing accuracy. For all the baselines, consistently use 0.1 participation ratio, i.e., 10 out of 100 clients are randomly selected in each round.
B.2 Baselines
We implement three general FL solutions compare with the proposed FedSLR, which all produce one single model that is 'versatile' in performing tasks in all clients. Specifically, FodAvg (McMahan et al., 2016) is the earliest. FL solution. SCAFFOLD (Karimireddy correction technique. FedDyn (Acar et al., 2021) applies dynamic regularization to maintain local consistency of the global model. We use Option 2 for the update of control variate of SCAFFOLD, and the penalty of the dynamic regularization in FedDyn is set to 0.1.
al., 2020) applies variance-reduction based drift
We also implement several PEL solutions for comparison of FedSLR. Specifically, Ditto (Li et al., 2021c) applics proximal term constrain the distance between clients' personalized models and global model. Per- FedAvg (Fallah al., 2020) applies meta learning to search for global model that is "easy" generalize the personalized tasks. APFL (Deng al., 2020) utilizes linear interpolation to insert personalized component into the global model. FedRep (Collins et al., 2021) and LGFedAvg (Liang et al., 2020) separate the global layers and personalized layers. In our implementation, algorithm- best-states. Specifically, the proximal penalty of Ditto is 0.1, the finetune step-size and local learning rate (i.c., a and () are set to 0.01 and 0.001, the interpolated parameter of APFL is set to 0.5. For FedRop, we the convolutional layers of our model to shared layers, while leaving the last linear layer as personalized layer. For FedAv, the convolutional layers are personalized, and the linear layer is shared.
are tuned to their
B.3
Additional experimental results
B.3.1
Additional visualization for performance evaluation
We show relative accuracy performance of different schemes Figure 3, where the median of cach violin plot demonstrates the median relative accuracy among the clients, and the shape of the violin demonstrates the distribution of their relative accuracy.
Personalized Natheds (Nan-ID)
Perzonalized Methods
0.10
8.0%
8itm
Teriqua
Non-Personalized Methods (Non-183)
Mon-lensomlzeed Methods (iD)
0.10
0.3
9.05
-0.2
2253
-2.00
FacSL IOaR)
SCAFFOLD
Rodbyn
Fects (Ca0)
SCAFFOLD
Redbyn
Figure 3: Relative accuracy (FedAvg bascline) CIFAR100. Accurcay is tested each client's local data distribution. Wider sections of the violin plot represent higher portion of the population will take the given relative accuracy. Population above red line means that the accuracy is improved (compared with FedAvg ) for this population of clients, otherwise, is degraded.
We also show the t-SNE 2D illustration the local representation in Figure. 4, to further visualize how the personalized classifier and feature extractor promote classification performance.
B.3.2 Hlyper-prammter sensitivity of FedSLR
We conduct experiment CIFAR-100 to evaluate the hyper-parameters sensitivity of FedSLR.
21

---

Published in Transactions on Machine Learning Research (02/2023)
Global extractor
classitier
Global extractor classifier
Global extractor ground
(acc:
(acc: 88.19%)
40
20
20
-20
-20
-20
-10
-20
20
40
-10
-20
20
40
-40
-20
20
40
Fer extractor Global classifier (acc: 89.59%
Per extractor + Per classifier (ace: 92.09%)
Per extractor ground truth
-20
-20
-20
-40 -20
20 40
20
-20
Figure t-SNE illustration of the local representation of random client. Following (Li et al., 2021b), the representation is derived from the last hidden layer of a Resnet18-GN model trained by FedSLR. Per extractor/classifee contains the low-rank plus sparse weights in its convolutional/linea layers. Global ex- tractor/clan classsiferr only contains low-rank weights in its convolutional /lincar layers, but the sparse personalized component is discarded. We see that via inserting the sparse component over the extractor, the points with different labels are more separated, and therefore are easier to classify. Moreover, via local fusson on both the extractor and classifier, data points have less chance be mis-labeled (see the rod circle, among which some points are mis-classified to label 2).
Table 3: Parameter sensitivity of low-rank penalty on CIFAR-100.
FedSLR (GKR)
FedSLR (mixed model)
Acc
Comm cGBt
# of params(M) +
Acc t
Comm cost(GB) +
of params(M)
le-5
63.63
819.44
7.33
81.89
819.44
8.54
5e-5
64.27
770.39
6.56
81.20
770.39
7.83
le-4
64.22
722.60
5.54
82.19
722.60
6.69
5e-4
61.81
568.43
3.09
80.10
568.43
4.04
le-3
54.26
498.20
1.27
74.33
498.20
2.24
Sensitivity of low-rank penalty X. We adjust different values to À while fixing proximal stepsize 7y 10
and sparse penalty / 0.001, whose results are available in Table 3. As shown, the communication cost and number of parameters of both the mixed and GKR model are largely lowered as the low-rank penalty escalates. Notably, there a significant drop of accuracy the penalty is set too large (e.g., 0.001), however, we also see that with proper low-rank penalty (e.g., 0.0001), the accuracy performance improves for both the GKR and mixed models. This concludes that making global component to be low-rank can help better represent global knowledge across clients.
Table 4: Parameter sensitivity of sparse penalty i on CIFAR-100.
FedSLR (mixed model)
Acc f
Comm cost (GB) $
# of params (M) 1
le-4
79.15
720.60
8.50
0.79
5e-4
81.78
722.60
7.12 + 0.65
1e-3
82.19
722.60
6.69 + 0.56
5e-3
81.82
722.60
5.78 0.17
le-2
80.81
720.60
5.56 1 0.08
22

---

Published in Transactions on Machine Learning Research (02/2023)
Sensitivity of sparse penalty μ.. Then fix fl 10 and low-rank penalty to À == 1c while adjusting μ.. As shown in Table 4, via enlarging the sparse penalty, the number of parameters of the personalized models could be lowered, but would sacrifice some accuracy performance. However, we also observe that proper sparse regularization would induce even better performance for the personalized models. This further corroborates that the personalized component to be sparse can belter capture the local pattern.
Table 5: Parameter sensitivity of proximal step size fg on CIFAR-100.
FedSLR (GKR)
FedSLR (mixed model)
Tl
Acc f
Comm cost +
# of params
Acc f
Comm cost +
# of params
2
60.74
894.06
10.65
80.37
894.06
12.36
10
64.22
722.60
5.54
82.19
722.60
6.69
20
61.02
668.94
5.16
80.60
668.94
6.15
100
58.69
559.88
2.99
78.33
559.88
3.90
Sensitivity of proximal step size Tg- We then tune the proximal step size f2 while fixing X = 1e- and μr 0.001. As can be observed, choosing fl to a proper value is vital to the accuracy performance of FedSLR. Additionally, we see that with a larger 'ly, the obtained model size and communication cost can be reduced, which can be explained by looking into the proximal operator. Specifically, for Π2 that too large, the proximal operator would prune out most of the singular value of the model's weight matrix. Therefore the parameter number along with the communication cost would reduce with a larger 7g. but the accuracy performance would probably degrade simultaneously.
Table 6: Parameter sensitivity of local Steps on CIFAR-100 under Non-lID setting.
Methods') local Steps
25 (1 epoch)
50 (2 epochs)
75 (3 epochs)
100 (4 epochs)
FedSLR (GKR)
58.20
64.51
63.86
64.17
FedSLR (mixed)
78.82
81.46
81.97
82.20
Sensitivity of local steps. In algorithm 1, we requires each client to exactly solve the local sub-problem in line 14, which may not be realistic due limited local steps. We show Table how applying different epochs would affect the empirical accuracy performance of FedSLR. Results show that with sufficiently large local epochs, e.g., ; 2 local epochs, the accuracy performance can be well guaranteed.
B.3.3 Pure global versus pure personalization
solution, we tune the low-sparse/sparse penalty respectively to extreme cases to recover the pure global and personalized component. Specifically, we first tune the low-rank penalty to 10 (a very large value) to zero out the global component, and adjust the sparse penalty to see how the sparse intensity would affect the personalized component's performance. The results are shown in Table Additionally, we tune the low-rank penalty, while fixing sparse penalty to large value to see how the pure global component performs. The results shown in Table 8.
To motivate our www-rank-plus-spa
Table 7: Accuracy performance pure personalized component on on CIFAR-100 under Non-lID setting.
Sparse Penalty (и)
1e-3
1e-4
le-5
Acc of pure personalization
37.14
44.16
44.54
Table Accuracy performance of pure global component on CIFAR-100 under Non-III setting.
Low-rank Penalty (A)
1e-3
1c-4
1c-5
Acc of pure global
54.26
64.22
63.63
23

---

Published in Transactions on Machine Learning Research (02/2023)
Our results show that i) too much sparsity/low-rant penalty would hurt the model's performance, and ii) pure local component cannot perform better than the pure global component due to lack of information exchange between clients, which justifies the necessity of collaborative/fedrraat training.
B.3.4 Wall time of communication
Tec@n Feslig SCAFFOLD
0.8
0.5
0.3
Figure 5: Wall-clock time of communication.
To demonstrate the communication reduction effect of the proposed solutions. We measure the wall time of each round communication using a local WLAN, as shown in Fig. Our results show that as communication round goes, the communication wall-time of FedSLR drops significantly, since the rank the model weights is decreasing. Other two baselines, FedAvg and SCAFFOLD maintain the same scale of communication time throughout the training, and SCAFFOLD requires twice communication since need to transmit the drift control parameters in addition to the model weights.
B.3.5
Wall time of inference latency
We measure the inference latency of the low-rank GKR on a Tesla M60 GPU. The batch size of each batch of testing data is weights can indeed accelerate the GKR model's inference speed.
20. The result is shown in Table 9, Our results indicate that factorizing model
Table 9: Inference latency (uilliseconds/battc)) of GKR under different low-rank penalty.
Low-rank Penalty (A)
le-5
5e-5
le-4
5e-4
1e-3
# of params (M)
11.17 10.98
7.33
6.56
5.54
3.09
1.27
Inference latency (ms)
10.12
9.30
9.24
7.62
6.53
C Missing contents in theoretical analysis
In this section, shall introduce the details of our theoretical results.
C.1 Definition of KL property
We first show the definition of KL property, which has been widely used to model the optimization landscape of many machine learning tasks, e.g., (Attouch et al., 2010).
Definition (KL property). function g TR. + R. is said have the Kurdyka- Lojasiewicz (KL) property at ā if there exists v (0,+)o), a neighbouhood U of x, and a function & (0,v) 12,, such that for all U with fx : g g(x) < g(z) + v), the following condition holds,
o ('((x)) g(ā)) dist(0, 0g(x))
where (pu) col-8 for 0 E [0, and 0.
24

---

Published in Transactions on Machine Learning Research (02/2023)
The KL property is useful analysis tool to characterize the local geometry around the critical points in the non-convex landscape, and could be viewed as generalization of Polyak-Tojasiewicz (PI.) condition(Karimi et al., 2016) when the KL parameter is 0 = (Chen et al., 2021c).
C.2 Facts
For sake of clearness, we first provide the following facts that can be readily obtained per the workflow of our algorithm.
Fact 1 (Property of solving local subproblem). Recall that Eq. (4) gives, for E [M],
10 arg min fi(w) (Yi,,, w) + - -1 w
(22)
21a
Moreover, from the optimality condition of the aboue equation, the following holds true for i E [M].
Vi((wi,)))) - 7i.t -(w; wr,++1) =0
(23)
"l
Fact. 2 (Property of auxilliary variable). The update of aurilliary variable gives, for E [M],
Ra++ Vi,t - w(,+1)
-w,
(24)
11g
Moreover, combining Eq. (23) and (24), for E [M],
K = (((Witt)))
(25)
Fact 3 (Property of global aggregation). Aggregation in Eq. (6) gives:
2
1 M
0++1 arg min wr 2
w
Σ
11,141
"1 M
18,41
+ 11 (ur)
M
iE[M]
i=1
(26)
1
arg argminn R(w)
+
(1,,11, w)
W
wi,+1
M
211
The oplimalily condition shows that:
1 (wi41
E @R(w(41 +
E B.++ +
wi++1
(27)
Fact. (Global optimality condition). Combining Fig. (25) and Eq, (27), we have:
1 M
(
M
0 E OR(w++) + vf((w.41)) + Ug 1r+1
Σ 1=1
Wit
(28)
M
M
Fact 5 (Gradient mapping between steps of local fusion). Recall that the gradient mapping is defined as Gm, (we, P..ck) = 1 (Pr.eA - Proxppnllll (Dr.e mn (eSi((e,.PP..))) Per Eq. (7) the following holds,
1 m
gn, (w:, po.t,))
(pr..k Pi.,kt1)
(29)
C.3 Missing proof of Theorem
Now we proceed to give the proof of Theorem 1.
25

---

Published in Transactions on Machine Learning Research (02/2023)
Proof sketch. Our proof sketch can be summarized follows: i) We showcase in Lemma 3 that the potential function is non-decreasing along the sequence, and its descent is positively related to || w.ell and ||++11 - w Telescoping its descent along the whole sequence to infinite, we can prove that the final converged value of the potential function is the infinite sum of the above two norms. ii) By Lemma 2, we see that converged value of the potential function can not lake negatively infinite, and therefore, we further conclude that wi++1 - wist and W1+11 - wt. Combining this with Lemma 1, 7i,+1 + Tit immediately follows, which corroborates our first claim in the theorem. iii) Then we start our proof of stationary property of the cluster point. Conditioned on the sequence convergence property obtained before, we sequentially show that the residual term in the RHS of the condition is eliminable, that the local gradient at the cluster point and iterates point are interchangeable, and that the subgradient of regularizer at iterates point is a subset of that at the cluster point. iv) Plugging these claims into the global optimality condition Eq- (28), the stationary property follows as stated.
C.3.1 Key lemmas
Lemma 1 (Bounded gap between global and local models). Combining Eq. (24) and L-smoolhness assump- tion, the following relation immediately follows: l|w; - wi,++ill S Lng Witt +1 wi
Proof. Eq. (24), together with Eq. read:
Vf((w,)+1)) V)((wr))) 1 (w. w1,(+1)
(30)
7g
Then, we arrive at,
ww, wi,++1l || nal (V((w))))))) - V[((::
wi.ell
(31)
where the last incquality holds by L-smoothness Assumption 1. This completes the proof.
]
Lemma 2 (Lower bound of potential function). the cluster point ((w", [ww]), (x()) erists, the potential function at the cluster point exhibits the following lower bound:
00 < Dny (w= (w 1x
(32)
Proof. By definition of the potential function, we have
M
M
M
1
1
(w, (w", fwi (x())
f((w)) + R(ww) +
r w -ww) +
w
w
M
M
M
277
im
im
(33)
1 M
M
M
1
f((w;) + R(w")
1w0 w + Yo 11
na
M
M
211/
M
i=
Moreover, by the definition of cluster point, we have lim VE 7/. Combining this with Eq. (25) and Assumption 2, it follows that:
-1 lim -noll 12 lim -1h V || _| -11 B² 5-000
(34)
10000
This together with Assumption 3, the fact that R(-) can not be negative value, complete the proof.
Lemma 3 (Sufficient and non-increasing descent). The descent of the potential function along the sequence generated by FedSLR can be upper bounded as follows:
D (w1+1, (w.,t41) (mr,+1)) -Dn, (we, (we,c) (m.)))
M
(L' n +
_11, - -w,, || -well
1
1
(35)
M
2119
2
Moreover, if fg is chosen as 0 f19 2r, the descent is non-increasing along t.
26

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. To evaluate the non-increasing property of potential function along the sequence (wi, fws,ets (ria))
we first show the property of the gap between two consecutive iterates, and notice that:
D (Wi+1, (wi,t+1) (%,++1)) Dng (we, fwo,th (x.e)) Dn (w++1, , (wi++1) (7i,++)) - Dno (we, (wirtth (me++1)
+ Dno (wi, (wirt41 J. (%,,+1)) (wn, (wi,++ i (3s,))
(36)
+ Dip (wi, (w0, (ma))) Dn, (ere, (wis), (mr,))
73
Bounding T1. By definition of potential function, term T1 can be expanded and upper-bounder as follows:
D (W++1, (wir+1) h. (mme+1)) Dn, (wi, (wi,t (ma+11)
-R(w(+1) R(wr)) + Ma41, w1+1 we)
1 -111; ws,c+1l13)
|10+11 01,4+112
M
2na
2ng
iEM
=R(u)(+1) R(wn)) + Σ
M1141 1141
we)
1
(w++11 + wt -20,, c- u1+11 un)
27g
(EM
since a² -2- (aa((at)(a-)))
M
(37)
=R(w)+1) -R(un)) 'M Σ
Σ Ng (wi+1 Wi,++1), W141 w))
Yett1
M
| - -wel' weel
M i=1
21gg
M
1
R(w:) + R(w++1) +
g
w. w++1)
|
we|l
M
211g
by (2.
i=1
1
W1+11 w
M
211
where g E (R(we))) one of the sub-gradient such that equation holds for Eq. (27). The last inequality holds since for convex function f(-) and any subgradient g point x, claim f(x) + g x) s f(y) holds.
Bounding T2. Now proceed to give upper-bound of term T2, as follows,
D, (wi, (wi,t1), (7,441)) Dy, (we, (w.,tt)) (r.)))
M
(7,41 Kits ut wt,t+1)
M
1
(( -
f. -
we Wi,++1)
M
(E[M]
See first case of Eq. (25)
(38)
Σ
Mgl V Vi(ww.e)1) (i(i,.)))) ||
M
[E[M]
See Eq. (23)
Σ 12 [1 wa 2
M
VE[M]
smoothness, Assump
27

---

Published in Transactions on Machine Learning Research (02/2023)
Bounding T3. Term T3 can be bounded as follows,
Dn (wte (10,++1), (m,,)) Dny (wee, (wij)) : (7x,))
M
M
Σ (f((w),+1) f((ws,))) + M
Wa Wie - wii++1)
M
M
1
1 1|w, w.,1 1
w|w, wr,t+112
M
21g
27g
i=1
M
1
(f((w),11)) - f((ws,)) +
(i,es Wi,t wi,(+1)
M
(39)
(2w: Wi,t 0i,+++ wix w(.++)))
M iEM
27g
(a-=b(aa
M
(1( f((ws,)) +
(Ti + n1 (w ws(+1))
wii: - wi,++1
M
M
M
|10,1+11 - w.,ell
M
2/1g
1=1
By L-smoothness, we have -(w,)) < - -(wi++1)) (V -i,e- wiet (0 21 -iit:: wi,++1l2. this into the above equation gives:
Plugging
Drg (wi, (wist1h, (rr,t)) - Dno (w,, (weeh fonit..77... (76,)))
Vfi(wa))1) + Vi.t + +ng(w: Wi,++ 1)) Wi,t wi,1+1
M
M
L
1 -1l wi,,el
(40)
M
2
271g
M L
W||111111
wr,ell?
M
2
27g
1=1
where the last incquality holds by plugging E2.(
Summing the upper bound of Eq. (40), Eq. (38) and Eq. (37), reach the following conclusion:
Dr (Wi+1, (wo,t1) 3. (Te++1)) Dn, (we, fwirth (rt)))
M
L 1
1
(41)
(L'mn +
||les,,e wi,ll2
||
well
M
2119
211g
Further, if fly is chosen as 0 < 11 S property follows immediately.
21: such that 1,2 + L 2 2ng
1
1 < 0
and
1
< 0, the non-increasing
2%
C.3.2 Formal proof
Now we showcase the formal proof of Theorem 1. We derive the complete proof into two parts.
The first part is to prove claim i)
lim (w (wo+1) (m3441))
lim (wy, (wo)) }. (ri }) (w", (w)), (x)
(42)
10000
28

---

Published in Transactions on Machine Learning Research (02/2023)
Telescoping the descent. Lemma 3 shows that the descent of potential function satisfies nice property (i.e., non-increasing) if properly choosing learning rate. To proceed from Lemma 3, we telescope the iterated descent from f = O...., T 1, which gives,
Dag (wr, (ws,r), ((r,T)) Dn (wo, (wi,o);(7,,.)
T (1,3gg
L 1 1| ws,ell
|1 we 1l2
(43)
M
2
27g
27g
On the other hand, by assumption, a cluster point (w", (wf}, {nt)) of sequence (wx, (wast) (ria)) exists.
Then, there exists a subsequence (wy, fwaye J. (75,5) }) satisfies:
lim (wo, (wiy) } (Tr,e) (w", (w,] (763) 1-000
(44)
By the lower semi-continuous property of D-) (given that the functions f(-) and R(-) are closed), we have: Dny (w", (w,). (nf & lim inf Day (wp. fao h, (Tr,)) 1)
(45)
50000
This together with incquality (43) yiclds:
Dn (w", (wi), {x53) Dno (wo, twaoh). (x,o))
S lim Dno (wii (ww) (,,,) }) Dn, (wo, (wr,)), (w.))))(mo)))
10000
(46)
M
(L'ng + 1|/,,,11111111 wi
120+11 -well3
M
2na
2
Lower bound the potential function at cluster point. Since Dn, (wo {wit J. (xft) is lower bounded per Lemma 2, the following relation follows immediately:
20
(I'm
1 2Mg
Wi 11
1
|10 uor1²
(47)
2ng
Derive the convergence property. Recall that I.2ng --
1 0 per choice of ng- It follows,
2n
lim |1,,411 wi,e 0 Wi,+1 Wiss. lim || will = - wi+1 - wt
(48)
Combining the above result with Lemma 1, we further obtain that,
lim ||w, Wi,t1ll = = wi,t11 + Wi. 800
(49)
By the update of Eq. (24), we obtain that l - Kr.ell nollw; w.rtill and therefore,
lim 11 Yr.ll 0 Rett + n.t
(50)
1000
Plugging the above results into Eq. (44), have:
lim (wp+1 twp (To = lim (wy, (we) ), (ri,e = (w", (w().(7)) 5
(51)
The second part of proof is to verify Claim ū): the cluster point is a stationary point of the global problem. Choosing t 1 in (28) and taking the limit
Starting from the global optimality condition. j- 00, follows that:
M Σ
M M
lim [.((w.)) + lim 1 w. Σ i=l
E lim OR(wp) + 1-+00
wis
(52)
M 1000
3 ng
29

---

Published in Transactions on Machine Learning Research (02/2023)
The residual term is eliminable. Since limj-+o |a w,-11 =0 and limy-+zo 1 wa,' 0, we obtain that limj->x Wy = -immj-o wi.i Subsequently, by eliminating the residual, we reach this conclusion:
M
1
0e lim OR(ww)
lim (iwss
(53)
70000
M
((W,,) and V(i(w;;) are interchangeable. By L-smoothness and convergence of iterates, we obtain: lim ()((w))))) - Vf((w") v L1 - =w"l 700
- L T(llwr w + || well + 11ee w=Il)
(54)
where the last equation holds by Eq. (48) and Eq. (49). Subsequently, we indeed have Vi V Vi((w)) i.., they are interchangeable within the limit, and plugging this into Eq. (53), we obtain that:
M
0 lim (R( ) + j-cc
Σ f((w")
(55)
M
i=1
Subgradients (R(w)) is a subset of @R(w)), As per Eq. (26), we have:
M
wy arg min R(w) +
1
Σ
(1441 w) +
2
1
Wi++1
(56)
w
M
f1
M
Therefore, it follows that:
M
R(w,) ) + M 1=1
Σ
Mas w. )
1
Wis
Σ
Wiss
2ng
M
sE[M]
(57)
M
1
1
S R(w")) +
(ho w")
w"
Wis
M
27g
[E[M]
Taking expectation over randomness, extending j + oo to both sides, and applying wy + w", it yields:
lim sup R(wp) S R(w*) 10000
(58)
On the other hand, since nuclear norm R(-) is
it immediately follows that:
lim inf R(wp) Z R(w*)
(59)
+0000
This together with Eq. (58) we have:
lim R(w;) = R(w") +
(60)
Applying Eq. (60) into the robustness properly of sub-differential, which gives: we further obtain that
euER": 3x + x, f(*') + f(x),tt + u, E c()())))))))
(61)
lim aR(ws) C OR(w"), 3
(62)
which showcases that the subgradients at point we is indeed a subset of those at cluster point w".
Derive the property at cluster point w² Plugging this into Eq. (55), we arrive at our final conclusion as follows:
M
E lim OR(w") +
V((w")
(63)
+0000
M
This completes the proof.
30

---

Published in Transactions on Machine Learning Research (02/2023)
C.4 Missing proof of Theorem 2
Then we show the proof of Theorem 2. Before the formal proof, we give a proof sketch for sake of readability.
Proof sketch. The milestone of the proof can be summarized as follows. i) We first define an auxiliary term called residual of the potential function, and find that it has some very nice property (Lemma 4), i.e. Ty + O and ri 2 0. ii) We find that the squared sub-differential of the global loss can be bounded by term with ||,,,+1 wr,ell On the other hand, we derive that Tr can also be lower bounded by || - W.,ell Combining both derivation, we connect the local loss's sub-differential with rt. iii) Then we further derive the upper bound of ry is connected with the sub-differential of the potential function, which is also related to the term || 1 w. iv) By jointing all the derived factors, we derive the recursion rt - r++1 Cari Jointing the property of Tr, we derive the analysis of final convergence rate under three cases of 0, which completes the proof of our first statement. On the other hand, we derive the global convergence of wi, by showing that it is summable. Combining this with the convergence result between w, and Wi,t, and the conclusion in Theorem 1, we show that w, can indeed converge to its stationary point.
C.4.1 Key lemmas
Lemma 4 (Limit of residual). Under the same assumption of Theorem 2, the residual rt == (n () establishes the sollowing properly: i) v. 2 0 for > 0, 6)) Dn, (wi, (w.,), (ma)) - -Dn (w",(,)) [w]), lime =0 0.
Proof. We first show that re 2 O for / 2 0. From the lower semi-continutty of Da (-), we obtain that:
lim inf Pn, (wo, (wr,), {7) Dn, (w", w, y):) 0. J
(64)
Further, by the non-increasing descent property shown by Lemma 3, for t 0, we have
Dno (we, (wi), (7,,3) 2 lim inf Dr, (WH, (we) {7 -0000
(65)
Combining Inequality (64) and (65). we obtain that for 6> 0:
Tt = Dno (w,, (we). (x.,e)) - Dn, (w", wi, 7/) 2 0,
(66)
which shows our first claim.
Now we show the limit of Since r, is lim4-+o0 rt cxists. On the other hand, by Eq. (60), we have lim R(wp) = R(w*). By the convergence of sequence Eq. (8) and the continuity of f((),, we have lim f((w,s) )- = fi(w*). Therefore, we prove that,
by 0, and is non we see that the limitation
lim
Dn, (wss (wbt) ( 1 M
f((w)) + R(ww) +
1 M
Σ
Mis was wi,e) +
1
M
2
1w
wi 11?
j 10000
M
M
M
M
M
M
<
Dr (w", (w",""") M f((w)) + R(w") (wo')+ + M 2
1
Σ
(h w
-w +
1
2
1
w
11?
M
199
(67)
which indeed shows limy-+x sup S 0. Combining this with Eq. (64), we arrive limy-se Tu 0. Given that lime-soo Tt. exists, reach the conclusion lim Ft 0.
C.4.2 Formal proof
Proof. Let Ft = Dng (we, (wr,),, (mr,)) - Dy, (w", {wi), }. (xt,e) captures the residual of potential function between an iterated point (we, (w:), (x,,)) and the cluster point (w", w0,7?)
31

---

Published in Transactions on Machine Learning Research (02/2023)
Derive the upper bound of subgradient. By incquality (28), we have:
1 -w
(R(w))
v((())))
M wal1
(68)
M
119
which in turn implics that:
M E
Vf((w))) [.(.)
1 (w,
1
w
[((,), + @R(w,)
(69)
fgg M
M
Recall that the definition of distance between two sets is dist(C, D) inf ق|ا E C,y D}. Viewing the LHS of the above inequality point in the set (i.e., the RHS), the following relation follows,
dist? (0.
[(((w)) + OR(w.))
1 (w:
1
Vf((w))) (V.(::.)(V(((
wi,r
1/g
M
f=1
M
M
2
2
(((w))) - vi(ww,,)))
1w - wi,1 11
M
M
2
+ -27) [ ww,,ll
(70)
M
7g
IEM
4
1
+ L L [lll:::-w;i++ll
wi.++111 |is++ wwirl1?))
M
flg
REM
4
(Vig + ((V V.i + +--- + 12),110 -w,,ll3)
M
119
iEM
Σ
Cillwi,411- - w
M
REM
where C1 4(ng + n3
+ L2). The second-to-last inequality holds by Lemma
4a
Connect the subdiffercntial with rı. On the other hand, by Lemma 3, we have:
M Σ
M
T - r2-1
C2llwa,e11 - w.,ell + 2ng
[ - w 2
M Σ
Wallwiet1 - w,,ell
(71)
M i=1
where C2 LL + 2
1. is positive constant by assumption.
2nd
Since T141 2 0 for any (See Lemina 4), the following relation holds true:
dist. (,,
M
C OR(w))) s SVC. Vrr
Σ (V((w:+++R(( M E
(72)
Notice above that the subgradient of the global loss can be upper bound by rt. In the following, we shall introduce KL, property achieve an upper bound of rt.
Upper bound r, with KL property of the potential function. Since the potential function satisfies KL property with @(v) co -0 we know for all that satisfies ra 0, the following relation holds true,
c(1 0)r," dist((0, AD,, (wn, (wi,),, (xx,))) 2 1,
32

---

Published in Transactions on Machine Learning Research (02/2023)
with its equivalence form follows,
r S c(1 - 0) d0st((0, SDn, (w;, (w:s (r,,))),
(74)
Upper bound the subdifferential of the potential function. We show that the sub- gradient of the potential function can indeed be upper bounded. Note that ay (Ow, Dr, (5..))) Vun, Pa (5:)), V.n. Dno (s:;-)) Now we separately give the subdifferential with respect to different groups of variables.
M
M M
Ow, Dr, (wi, (wat), (mx+)) = (R(w:) +
Σ 7a.t + M
(we
wr,e) 3 0
(75)
where the last incquality holds by the optimality condition (27).
Then we proceed show the gradient with respect to wi,t as follows,
Vws, Dm, (we) {w.,,), (31,e))
1
( (i(wss.)) Yi,t
- (w. w;,+))
M
f7g
1
V V.((ww,,t1)) Yi.1
- (wo wri++1) + +- (wi. wh,++1) V.l(w,)))) - vf((ws,+1))
(76)
M
1/g
11g
=0, by Eq. (23)
M (V.is - Vf((w.)-1) +
(wi, w1,++1)
1l
Finally, the gradient with respect to Th.t has this equivalent. form:
V nc. Dr, (wi, (wicc (1t,a))
M (w, wi,e)
1
M (we, w1,c+1 + wi,t+1 Wi,))
Ta M
(76,+1 Yiet + 7g
(Wi,t+1 - wi,))
(77)
by Eq.
"1 (Vii(Weet))) (((we))) f7g
(witt4 wi,e))
M
Note that d0 0D,, (:..)) V dist? (0, Pw, Dno (..,, Vo,, Dno (.. 112 VT.,, Dno (.,,,))11 ming the above sub-differentials, we arrive at,
Sum-
+ ng M
1 -(w,e w1,++1)l
dOst(O, aD, (w,, (waat (xx,e))
(I
Vi((w,,(+1) +
M
+ ng
<
(II V.l - ||20, w.
(78)
M
11g
1=1
1
Σ
Callaaa wis+1ll
M
where C3 = + 11
+ 1. 1
Upper bound to r, with the subdifferential of the potential function. This together with Eq. (74) show that, Ft can be bounded as follows.
M
0
< Σ c(1 80 w wastall
(79)
M
1=1
33

---

Published in Transactions on Machine Learning Research (02/2023)
Recall that the norm term |,,,, w1,++1l? is bounded as Inequality (71). We first taking square of both sides of (79), yielding
1 M
2
M
1
ri" 1
dl 0) C's Callu,, whe+1ll
e1 011-1)031100 wi. w1,++1l?
0)03|
(80)
M
M
Plugging Eq. (71) into the above results, under the case that Tt > 0 for all L O, we can ensure:
C2 20
Te+1 2
C3 0)2
(81)
Cart
C. where C4 C3a(1-0)3 is positive constant for 0 E 1).
Separate into three cases. We then separate our analysis under three different settings of O.
Firstly, assume Dng (x, y. 7) satisfies the KL property with 0 = 0. As per Eq. (81), if r, > 0 holds for all >> O, we have rı 2 Cs for all > 0. Recall from Lemma 4 that lim r2 = O, which means rr 2 C4 cannot be true when T sufficiently large number. Therefore, there must exist a lo such that Ito = 0. If this is the case, observed from Lemma 4 that r; 2 0 for all t > O, and that r, is non-increasing. sufficient to conclude that for a sufficiently large mumber T tor TT must hold true. Inserting this result into RHS of Eq. (72), the desired rate follows immediately.
is
Then, consider the case Dr, (x), y, 7) satisfies the KL property with E (0, () First we assumee that 7t > 0 for all t > O. From Eq. (81), it follows that: Tz+1 S, Car?". Since lim, Pr = 0, there must exist to such that, rT rr hold for all T > ty,, and equivalently, rr+1 S (1 Ct)rT. This further implies that rT I (1- CA- Now consider another case that there exists to such that re 0 for all T> > to, following the same analysis given in the previous case we reach the same result rr 0 holds for all sufficiently large T 2 t. These together with Eq. (72) implying that for sufficiently large T > to. /Cry
20
dist. (0, EN V(((w)) + @R(WT)) S max Cing (1 Ca)T. S V C2 (1 Ca)
Finally, suppose Dn (x, y. 7) satisfies the KL property with 12. 1). We first evaluate the case that rs for all > 0. Define continuous non-increasing function g (0, +00) R by g(x) x-
-0-r! 28
Plugging this definition into Eq. (81), we have C₁ S (r: - ((+1) I SM g(z)dz holds for all t 2 O. Since 20- > 0, we have 1-20 n!- I (20 - 1)C4, Summing from = 0 to 1= T - 1, have S </T(20 - 1)C4. Moreover, same the previous analysis, we have rr for all 12 0. Thus, these logether with Eq. (72) show that for T 2 0, dist (0 + ΣM V/((w)) + oR(wT)) S
28-1
max( 22220 1)C,,) (40-() where C₃-
C 2 / (20 1)C4. C2
Now we try to showcase that the iterate w, can globally converge the the stationary point v="
Define D = Dra (w", , } 3). By construction, we derive that,
1 M
M Σ - wi.+ill (D (w,, (wir). (xxe)) - D²) :p p(Dng twreti (ma+1)) -D")
2 dist(0, DD,, (wi, (wi,t), (x),))) (D,, (wi, (wes), (m,))) DD)
(D (we+1, (mn,)4)), (mu+1)) D)))
2 dist(0, 0D, da (wi, (ws,e), (xxt))) (D, (we, (wrth (xt))) - D")
(Dng (w) (ws,,), (mree)) - Dno (Wo+1, ( (m,41)))
2D,, (w,, (wit) (7,,)) D,, (W ( (1 (x(+1))
(82)
34

---

Published in Transactions on Machine Learning Research (02/2023)
where the second to last inequality holds by concavity of yp and the last one holds by KL property. Plugging Eq. (71) into the above inequality, it yields,
M
1
Calluasa - wi,e+1ll (Dr(Dn (we, (wit)) (%1,)) - D*) p(Dn, (w0-11 (wa++)) (m,+1)) -D")
M
M
C2l - wo,ell
M 1=1
(83)
Therefore, by reorganize, obtain that,
Wiit wi++1ll
(84)
C3 (D (wi, (wirh ( "D(Dn (o(Dno(urt,,, (w (3),413) D)))
C2
By lelescoping from / = 1 to oc, we have,
|,,,e w/,+1ll
M
(85)
(p(( (wo: (wr, (%,0)) -D") - (p(Dn, (w (wi (M, -D*))
C3 (D( (wo: (wro). (m,o)) - D*)) 0c
C2
where the second inequality holds by lim Tt 0, as stated in Lemma Therefore ||w,, wr,c+1 1 is summable, which mcans the whole sequence wi, is convergent to its cluster point w i... lim4 Wi,t w. Moreover, based the convergence result between w1,+1 and w, in Eq. (49), also that lim,440 w, w". Note that in Theorem 1, we observe that the cluster point is indeed the stationary point, and therefore lim Wr = u This concludes the proof.
C.5 Missing proof of Theorem
Let stochastic Proximal GM as G 2 1 (p- proxm.te x m ( which serves as an auxiliary variable in the proof.
Proof Sketch. Our proof starts with the L-smoothness expansion at the iterative point. For the linear term in the expansion, treat it with Lemma 5 to recover the 12-norm between sequential iterates, i.e., | -Pt..l Then we mcasure the crror brought by stochastic proximal gradient by constructing the term (V2fi(w, + P..) - V + Piz: Pi,ii -Ptz) which can indeed be bounded by the variance o². By reorganizing, the stochastic gradient mapping (GM) can be directly bounded. Finally, we leverage the smoothness of gradient mapping, i.c., Lemma 7 to track the error between stochastic/ren gradient mapping.
C.5.1 Key lemmas
Lemma 5. The following relation holds true,
(Vefilw: + (). Pi..k P..t.ttt) 2 (R(p..k41)) R(p |P - Pi.e.1?
(86)
m
Proof. By the optimality condition of the prox function, we know that there exists sub-gradient e @R(p such that Pit Pirkk V2l(ww, + PLLk)) ms = O. Further, we obtain that, (peLkt)
35

---

Published in Transactions on Machine Learning Research (02/2023)
Pi,t + n1 V2f + PL. + m. Pitck P..Ck+t) O, which further implies that,
(V2fi(wr + (PLLKE)) Pt. PiLA+1) Pa,,A41 Pickk) 1 m
pi,,,t+ - PLaxll
(87)
2 (R(pL.ex11+ R(p().))) + |pp.cKt1 - Pr..al?
where the last incquality holds by convexity of R(-).
Lemma 6 (Young Inequality).
(a. b) - 2 |1aa12 |b|
(88)
Lemma (Smoothness of Gradient Mapping). The gradient mapping and a stochastic one exhábits the following smoothness property,
1 (9m. - Gm (we, Pi,,k)) = (prox n. x Tn Viwww + pp)
(89)
-roxx R2 V. p)))I
[V - VSi(w p)ll
where the inequality holds due to the nonerpansinitty of the prozimal operator of proper closed conver func- tions, see Property 5 in (Metel & Takeda, 2021).
C.5.2 Formal proof
Proof. By L-smoothness, we obtain that,
Bx + Pi.cA--1)
L " Sf((0" + P.LK) + FeA (V2fi(1" + +...k)) - Picak) + Fe, Pi,18t1 Piexk11
Sf(("" + P..ck + ELA (Vefi + +....)) Vefi(w: + PLIktt - Pi.ck)
TI
(90)
+ Ei (V2f( + P..N)) V2fi(w, + P.P.AE) PoicttI - P(.N))
To
L P...)) + Be,ellee -P...
Ee, (V2/i + Pi,AaiE) P PreN4
By Young's inequality and T-smoothness, we obtain that,
1 Ti < E., L + +i.ck) V2fi(w, + 11. Bo 1. -Pi,c.
(91)
1
< =,,00l00 - w.ll BeallPeAAt - Pi.a
2
Besides, T2 can be bounded follows,
T2
E., (Vzfilw; + Pi.,ki E) V2fi(w; + P..,))) 9m. Pi.,,)))
< ELA (V2fi(u: + Pi,cKi 5) V2f((w; + P.L,k)) 9m. Pi.t,k) ) - Gry (ur,, Pi.t,k) + Gmy (wn, Pi.,,)))
EEA (Veii + Pt,, Vefi(w, Pt...)) Gm (w,, P),,,)))
(92)
+ E, k 22f((w, + P..AAiE) Vefc(w: + Pt.,,)) (1l (mlllm..s.... (ww, Pit.k) (w...t...)))
(un, Pi..k))l
< E, V2fi w. + Pi) V2fi(w, + P..)) 1mm. (w Ph...) - G, (2)).....))
F4,
V2fi(w; (w. + (i.e,aEE) V2fi(un + 11
36

---

Published in Transactions on Machine Learning Research (02/2023)
where the second-to-last and the last inequality respectively holds by Lemma 7, and assumption 5. Finally, term T3 can be bounded with Lemma 5, as follows,
1 m -A,,llle,,,411 P..e
T3 S R(PG..)) Re, R(Pi..4t)))
(93)
By re-arranging Ti and T2 into Eq. (90), and let o,(w,p) fi(w + +p) + R(p), we have,
E Pia.441) S di(w"" plink) + +1 Ec Pi.,,
L2 E E
well +02
(94)
S Solw"" PPe.k) + ( 1)f (
m Er, mm ( 1i,
2
12 + 18 1/000 - we 11 +
2
0 < 11 < I it follows that,
2 (0:(10" .P.A.)) 01(10" -Pi,,&++)) T,2 T,2,,,,ll00 2m1 - (L + 1)m}
wel12 + 0
Ei, fm. 11? 2
(95)
Taking expectation over the condition and telescoping the bound from k = 0 to K - and t= 0 to T - it gives,
T-1K-1
Σ
E| gm (we, 1=.
TK
(10 (p....))) (: -P..T + - I.2 -w,l12 0²
(96)
2m - (L + 1)mi
2B(di(10" Po.0.0) 2,6"0 p))) Dto I.PEE/10 -w,l,
w.l1 -
-
+ 0
2m (L + 1)mi
Then we shall expand the term 1 Σt 13 w. using the global convergence result given by Theorem 2, and the epsilon definition of limits. Specifically, by w, w" there exists positive constant N such that for any 2 N, I|w, r0 & holds for <> O. Then plugging this result into the expansion, we have:
T EL 20
N L B - 20 +
T-1
10"12
Σ
L2| w0 r0"
T
T
1=0
t=0
N=
(97)
N
T-1
I L w:
2b-12
Σ
1222)
t=
N=
Choosing == 1 V we have:
T
Eimo L'E
20
12
w. 201 <
+
(98)
T
T
37

---

Published in Transactions on Machine Learning Research (02/2023)
Notice that || w. 112 2ng (D,, (wi, (wi,)), (r,)) Dno (Wi+1, (wa+t1) (7),++))) per Inequality (41). Utilizing this fact, the following inequality holds for 2 1
Bl -00112 <t B(llw0 -00"11
+
1wy1 -w, -0,l1²)
j=1
<t B[llw0 - 20 20"112 + Σ
| - -w, w2l1²)
(99)
j=1
St B(1lw0 ~0 11 2 + M/ (D, (wo, (woro), (%v,0) D,, (wi, (w.,)), (ma)))
St. w0 10= Mng (D,, (wo, (wr,)) (7,,0) - Dr (w= {w])) (n())
where the last inequality holds by Inequality (66). Plugging this into Inequality (97), we obtain that,
T
L' ww - 20"
1=0
(100)
N(++1) 2
1)] W0 10 NIN-1) 1)
Ng ( (Dro (wo. (w..). (Y,o)) (w", (w Dn (xt L
T
Let C7 =
2
M(++1 + +1]|
~00 =0= M(N+1)
11 (Dr, (wo, twio) (7..0) DD (wo", ( (7))))) Plugging
2
2
Inequality (98) into RHS of (96), we arrive at,
K-1K-1
2(0)(10 Pr.0.0) - 25 pt))
ΣΣ
El Gm.e w. p1.
7
(101)
TK
2m (L 1)m
k=1
Further notice that the real gradient mapping can be bounded as follows,
T K-1
En (we, 111
TK
2
[ml P.t,,)) + Ellg,, (wr, (i.,,))
TK
[ (w., P...)) E + PL..k) Vef((w; + +P.A,A:)) E)11)
(102)
TK
E 9m (w. 1=
TK
k=1
2(0:(10" ,Pt0,)) oe(20" .P:)) + G (2m (L + 1)mi 1)o²
m L+1 m
where the second inequality holds by Lemma 7. This completes the proof.
38


Reviews:
[{"review_id": "ywvqv6cBSS", "reviewer": "Reviewer_ykqj", "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": "Personalized federated learning is an important research direction in training customized models of clients. This paper proposes a new method that answers how to design personalized models with better representation of shared global knowledge and personalized components. The theoretical and experimental results are convincing. \n\t\t\nHowever, I still have several questions and suggestions as follows. First of all, why should the global knowledge be low-rank and the personalized components be sparse? I suggest the authors give some intuitions and comments on this.   My next concern is about the computation overhead of FedSLR. Albeit FedSLR allows a smaller amount of global and personalized model parameters, the computation overhead of FedSLR seems heavy since it needs to solve a sub-problem when training GKR in local. I wonder what the running time of FedSLR is and if it has advantages in computation.  One minor issue is that I think line 5 in Algorithm 1 is not needed since the clients have updated the auxiliary variable $\\gamma_{i, t}$ in line 14 and they can send $\\gamma_{i, t+1}$ to the server in line 11. I suggest the authors carefully check if line 5 is necessary. And I think $p_{i, t^-, K}$ in line 17 should be $p_{i, t-1, K}$. The authors should also check on this.", "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 paper focuses on the personalized federated learning problem and employs the nuclear-norm regularization and $\\ell_1$-norm regularization on the global and local optimization problem respectively to extract the low-rank global knowledge representation and sparse personalized component. To solve the two regularized optimization problems, this paper proposes a two-stage proximal-based algorithm named FedSLR. The theoretical analysis guarantees the convergence of the global model and the personalized model. The experimental results show the empirical performance of the proposed FedSLR. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My detailed requested changes are listed in the last paragraph of the previous section; please refer to it.  My major concerns concentrate on the necessity of global knowledge's low-rank property and personalized components' sparsity. I also wonder about the computation overhead of FedSLR and if it is efficient in computation.", "broader_impact_concerns": "There are no concerns on the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wdSgmADvn9", "reviewer": "Reviewer_hp2V", "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: \nThe paper's formulation of personalized Federated Learning which merges the personalized pattern into the global knowledge is novel. The theoretical analysis is solid and the experiments are extensive, including a wide range of baselines.\nQuestions (Weaknesses):\nHowever, I have some questions about the algorithm design and some advantages of FedSLR claimed by the paper.\nQ1: I wonder whether it requires such a sophisticated procedure to solve (P1). Consider the following algorithm to solve (P1): \nAt round t\nClient: (1) download global parameter $w_t$ from the server; (2) compute (stochastic) gradient $\\nabla f_i(w_t)$ (3) communicate the gradient back to the server\nServer:  perform proximal gradient descent by the following update rule\nIf the clients use tha same method to update the local paramters $p_i$, how does the above algorithm compare to the proposed FedSLR? If such a sophisticated procedure as FedSLR is indeed necessary, the paper should clarify the necessity and the advantage of FedSLR over simple algorithms as above. \nQ2: In Appendix A.1, the authors pointed out two main drawbacks of one potential method and I am confused with the second point. The local solution $w_{i, t, K}$ given by $K$ steps of (15) should be sparse if $K$ is not too small, and therefore the upload communication can be saved. It seems that the paper only considers the download communication and claims the advantage of FedSLR over this method for reducing download communication. \n\nQ3:  The analysis of FedSLR algorithm relies on the exact minimization of (4). Note that how accurately the client solves (4) depends on the number of local steps. I am confused about the criterion for choosing the number of local steps $K$ in the experiments and how $K$ affects the performance of the model generated by FedSLR. \nQ4: It is easy to understand that sparse and low rank solutions can reduce model complexity and communication complexity. However, FedLSR also yields higher test accuracy than a bunch of baseline algorithms in the experimental section. Since forcing the model to be low rank and sparse restricts the expressiveness of the model, can the authors explain more about where the improvement of test accuracy comes from? \n", "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 paper decomposes Federated Learning models as a common global representation and personalized local parameters, and imposes sparsity penalties to seek sparse and low-rank solutions. They propose a proximal-based algorithm named FedSLR to efficiently solve the optimization probelm. By regularizing the model parameters to be sparse, FedSLR reduces the model complexity and downlink communication complexity.  They further provide convergence guarantees for this algorithm. Finally, they empirically verify the superior performance of FedSLR. \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "About the algorithm design (major):\nAs explained in detail in Q1 and Q2 above, the author should reason more about the key idea behind FedSLR and its advantage over some naive solutions.\nDiscussion of the effect of the number of local steps (major):\nThe number of local steps is one of the key hyperparameters in Federated Learning. As explained in detail in Q3 above, the paper should include the effect of the number of local steps on the model performance. \n\nAbout memoery consumption of FedSLR (minor):\nIn Algorithm 1, the server is required to maintain the auxilliary variable $\\gamma_{i}$ for each client but memory consumption to maintain such variables is huge. In fact, the memeory consimption can be easily reduced by only tracking the averaged auxilliary variables. The authors should consider methods to save memory consumption. \n\nSuggestions to make the paper more self-contained (minor):\n1. The authors should give the definition of a \"closed and proper\" function, at least in the appendix.\n2. The authors should explain more about the additional assumption of a convergent subsequence in Thm. 1.\n3. The authors should specify what is uploaded from the client to the server in the caption of Figure 1 and Section 4. \n\nGrammatical mistakes / typos (minor)\nWhat does the last sentence of the first paragraph in Section 1 \"feature a good adaption for each client’s task per\" mean?\nLine 2 of the first paragraph in Section 2: data resided in -> data residing in \nThe second line below Eqn. 2, prior->prior to\nRemark 1: bi-varaibles->bi-variable\nLine 2 in Theorem 1: converges -> converging\nLine 3  of Paragraph 3 in Section 6.1: a SGD optimizer -> an SGD optimizer; weight decayed -> weight decay; initialized with -> initialized as\nLine 5 of Paragraph 1 in Section 6.2: degradation -> degrades\nLast line of Section 7: could -> can; under proper setting -> under proper settings\nThe authors should check through the paper for all such mistakes.\n", "broader_impact_concerns": "The authors can discuss how FedSLR can be combined with some privacy preserving techniques to avoid privacy leakage.\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yz3kRF9muy", "reviewer": "Reviewer_HSnF", "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": "Overall this is a strong paper, with clear innovation that is supported by both theoretical analysis and empirical evaluations. The core idea of FedSLR makes sense, and the two optimization problems as well as Algorithm 1 are presented cleanly.\n\nThe theoretical analysis can be further improved. For example, the definition of KL property is explicitly used in Theorem 2, but $\\theta$ in the KL property is never given in the main paper. (I understand that there is a space limitation, but the main paper itself has to be coherent.)\n\nIn addition, I wonder if the authors can explicit show two extreme cases, both theoretically and experimentally: (1) Fully global, no personalization. This should be the IID case in the current paper. (2) (Nearly) fully personalization, no global common information. This would be an extreme non-IID case. Furthermore, would you be able to show a tradeoff across these two extreme regimes, via adjusting the parameter of FedSLR?", "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 paper proposed FedSLR, which is a new personalized federated learning (PFL) method. The new idea is to decompose the personalized model as a mixture of (1) a low-rank global representation, and (2) a sparse personalized component. The former is to extract the common information across clients, while the latter is to capture the individual pattern that may be different for different clients. Technically, this general idea is realized by formulating two optimization problems by involving proper regularization. Theoretical analyses of the convergence are provided for both global and personalized models, and the advantages of FedSLR are demonstrated in experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The last two paragraphs of the previous section are my \"wishlist\" for the authors to address in a revised paper. The first is mostly a presentation issue and not critical. The second, however, is something I believe to be valuable for this work. Global common information and local personalized feature are two different aspects, and the tradeoff between them is interesting, but not well captured in the current paper.", "broader_impact_concerns": "There is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ynOVGGgpoW", "reviewer": "Reviewer_Up9C", "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- The paper is well-written. The research direction of improving personalized federated learning is important.  \n- Both theoretical analysis and empirical results are shown to justify the convergence guarantees and empirical performance of the proposed FedSLR algorithm.  \n\nWeaknesses:\n- The proposed techniques' motivations are unclear and not justified. Specifically, why enforce the global knowledge representation to be low rank? Do those learned model weight updates tend to low rank? Why not enforce the global knowledge representation to be sparse or structured sparse? Those questions are important to be answered to justify the motivation of the proposed method. And the same concern applies to the local personalized parameters, why sparse? Can they also be low rank?  \n- The proposed method is motivated by parameter efficiency and communication efficiency. But I do not believe in practice the algorithm will be any faster than FedAvg. For instance, although the global knowledge representation is enforced to be low rank when communicating it among clients and the server, the dense representation is used rather than the low-rank representation. Then where does the communication efficiency come from?  \n- The sparse local personalized parameters seem to be sparse, but the random sparsity does not enjoy any computation/memory efficiency in practice as I am afraid. Thus the proposed FedSLR's practicality is limited.  \n- By looking at the main experimental results in Figure 2, the convergence rate of FedSLR does not seem to outperform other popular baselines significantly, especially for CIFAR-10 and TinyImageNet, which harms the importance of the proposed method. The same pattern is also observed in Table 1 and Table 2, i.e., FedSLR is not always the best (even for the mixed version).  \n-  There are no running time results presented in the experiments. Will FedSLR actually lead to any speed gains over the other methods? What are the actual computation and communication times of FedSLR?  \n- All experiments are conducted on vision tasks, if the authors can add some language tasks, e.g., BERT pre-training/finetuning experiments, the empirical study can be stronger.  ", "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 paper proposes FedSLR, an algorithm that seeks to enhance personalized federated learning. The key components of FedSLR are (i) it constraints the global knowledge representation to be low rank; and (ii) it allows the personalized local weights to be sparse.  \n- Using FedSLR effectively reduces the number of parameters required for both global knowledge representation and local personalized parameters.  \n- Theoretical analysis has been conducted to demonstrate the convergence guarantees of the proposed FedSLR algorithm.  \n- Empirical results are provided to show the convergence performance and the parameter efficiency of the proposed FedSLR algorithm, which demonstrate that it outperforms a few popular baseline methods.  ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weakness part for a more detailed discussion. The requested changes are summarized below:\n\n- The authors are expected to add justifications and motivations for enforcing low rank and random sparsity on the global knowledge representation and local personalized weights.  \n- Practical analysis and experiments are required to demonstrate the speedup gains of FedSLR, e.g., its communication cost and computation cost (all measured in wall-clock running time).  \n- Adding justifications on when the proposed FedSLR algorithm can significantly outperform the other baselines.  \n- All experiments are conducted on vision tasks, if the authors can add some language tasks, e.g., BERT pre-training/finetuning experiments, the empirical study can be stronger.  ", "broader_impact_concerns": "There are no concerns about the ethical implications of the work. And I thus would not request the authors to add a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed FedSLR, a personalized federated learning algorithm that decomposes the model into a low-rank global representation and a sparse personalized component. The paper presented theoretical analysis and experimental results to demonstrate the convergence and parameter efficiency of the algorithm. Reviewers found the paper to be well-written and the research direction to be important. However, reviewers had concerns about the motivations behind the low-rank and sparse constraints, as well as the practicality and effectiveness of the algorithm compared to other methods. The reviewers suggested that the authors provide further justification for the algorithm's design, demonstrate practical speed gains, and clarify when the algorithm outperforms other baselines. The authors added explanations and experiments, and the reviewers agreed that the concerns of the reviewers are addressed. Thus I recommend acceptance. 
Decision: Accept (poster)