Personalized Federated Learning towards Communication Efficiency, Robustness and Fairness
Authors: Shiyun Lin
Yuze Han
Xiang Li
Zhihua Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: personalized federated learning
communication efficiency
robustness
fairness
low-dimensional projection
infimal convolution

Abstract: Personalized Federated Learning faces many challenges such as expensive communication costs, training-time adversarial attacks, and performance unfairness across devices. Recent developments witness a trade-off between a reference model and local models to achieve personalization. We follow the avenue and propose a personalized FL method towards the three goals. When it is time to communicate, our method projects local models into a shared-and-fixed low-dimensional random subspace and uses infimal convolution to control the deviation between the reference model and projected local models. We theoretically show our method converges for smooth objectives with square regularizers and the convergence dependence on the projection dimension is mild. We also illustrate the benefits of robustness and fairness on a class of linear problems. Finally, we conduct a large number of experiments to show the empirical superiority of our method over several state-of-the-art methods on the three aspects.

Personalized Federated Learning towards Communication Efficiency, Robustness and Fairness
Shiyun Lin Yuze Han Xiang Li
Zhihua Zhang 1.2
Center for Statistical Science, Peking University "Scooo of Mathematical Sciences, Peking University shiyunlinsstu, pwu.pdu.c.. edu. en hanyuze87@plu edu. en
1x100770pku edu. zhzhang@math, pku. edu, en
Abstract
Personalized Federated Learning faces many challenges such expensive com- munication costs, training-ting time adversarial attacks, and performance unfairness across devices. Recent developments witness a trade-off between a reference model and local models to achieve personalization. We follow the avenue and propose a personalized FL method towards the three goals. When it is time to communi- cate, our method projects local models into shared-and-fixx random subspace and uses infimal convolution to control the deviation between the reference model and projected local models. We theoretically show our method converges for smooth objectives with square regularizers and the convergence dependence on the projection dimension is mild. We also illustrate the benefits robustness and fairness on class of linear problems. Finally, we conduct a large number of experiments to show the empirical superiority of our method over several state-of- fftte-of-the-arr the--at methods on the three aspects.
low-dimensional
Introduction
Federated Learning (FL. emerges as new distributed computing paradigm that would perform privately distributed optimization in large-scale networks remote clients (51). For the sake of privacy protection, data are generated locally and are kept in the original location during training, which incurs a discrepancy among local data distributions. Furthermore, the nature that FL works as decentralized system poses greater challenges to its communication efficiency, robustness against adversarial attacks, and fairness on resource allocation 32
To detour the data heterogeneity issue, one considers to personalize local models 35 A key feature that any personalization method has to differ local models from the global model. The simplest way for personalization is training purely with local data on each device. Chen et al. [10] showed that when the degree of data heterogeneity above some threshold value, pure local training is minimax optimal; otherwise, the global model is minimax optimal. In practice, we prefer method that intervenes between the two extremes. brings out another popular approach that interpolates between reference model and local models [99 20 12 13 26 64). Recently, Li et al. 44] suggested that personalization can leveraged not only to improve accuracy, but also to allow for competing constraints such robustness and fairness. Inspired by their work, would explore the following question:
Can we balance different constraints of interest (ie., communication efficiency, robusiness and fairness) simultaneously?
In this paper, we give an affirmative answer to the question by proposing personalized FL method named 1p-proj, whose core is (F-regularization and low-dimensional random projection. We
"qqual contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

employ the idea of controlling the dissimilarity between the global model and local models via smoothing kemee of infimal convolution. Towards the three goals, the smoothing kernel is designed to regularize the projection of local models in shared low-dimensional random subspace rather than the original space. In this way, each client only communicates the projected models each time and the server maintains a low-dimensional reference model for regularization. The random subspace is generated once and will not change during training. It makes local models share a similar part in the random subspace and adapt to their local data using components beyond that.
Theoretically, we give convergence analysis for smooth objectives with square regularizer, and show that the convergence dependence on the projection dimension is mild. By analyzing test losses and the corresponding variances across the network on federated linear regression, we show that our proposed
method is at least as good as two SOTA methods [13] 44 in terms of Byzantine robustness [3] and
performance fairness (see Definition
Finally, we conduct a large number of experiments to show the empirical superiority of our method. not only shows expectant personalization but also promotes fairness by achieving higher test accuracy more uniformly over clients. It significantly improves communication efficiency, because the subspace dimension often no more than one-hundredth of the original dimension. Furthermore, it is more resistant to training-time adversarial attacks.
In summary, we propose personalized FL algorithm and explore its performance in aspects of communication efficiency, robustness and fairness. Our results show that dow-dimensional projection brings multiple benefits and is helpful for algorithm design.
2 Related Work
There many works studying personalization and a survey can be found in [35 It has been studied
via multi-task learning (57 (8), meta-learning ( 31 [6], knowledge distillation 41 70 and transfer learning
Hanzely et al. (21) provided convergence analysis for general personalized framework that requires jointly strongly convex and smooth objectives.
63
49
Communication Efficiency To reduce the cost of communication in FL with large-scale networks, existing works could be categorized as gradient compression, model compression and reducing the communication frequency. On gradient compression, sparsification [29] 47]. quantization [1 and low-rank approximation (3 are three main directions investigated the current research. On model compression, Liang et al. (46) suggested learning local representations and global model only operates on the local representations, Li et al. [38] extended the lottery ticket hypothesis and used network pruning in the FL setting. On communication frequency, Wang et al. [62] used momentum to delay the global aggregation; McMahan et al. [51], Karimireddy et al. (3 performed multiple local updates to lessen the communication rounds. Shahid et al. [56] presented survey on current progress on communication efficiency in FL. Our proposed method is a model compression approach. Differing from previous works that compress the model each time with different basis, our work focus on a shared-and-fixed low-dimensional subspace which is determined at the beginning of training and will not change later on.
Fairness in FL Zhou et al. suggested that there are three types of fairesss in FL:: performance
fairees,, collaboration fairness and model fairness. On performance fairness, an FL system usually promotes uniform accuracy distribution across participants, which is closely related to resource allocation by viewing FL as joint optimization system over heterogeneous network. Li et al. [44] gave a formal definition (Definition [ and some efficient methods have been proposed towards this
goal 44 277
Definition (Performance Fairness 44). A model W1 is more fair than W2 if the test perfor- w1 mance distribution 01 across the network with N clients is more uniform than that of w2. i.e. var (Fu(w1)Bse(N) < var (F:(W2))ee(N)) where Fx(.) denotes the test loss of client k E [N] and var denotes the variance
On collaboration fairness, one expects that each participant receives a reward that can fairly reflect its contribution the FL. system, in which way one can build sound incentive mechanism. Lyu et al. (48) formalized this idea; Yu et al. [69]. Xu and Lyu [67] explored on this aspect. On model fairness, one usually concerns ethical issues and seeks protect some sensitive attributes [15 22 36)
Liang et al. [46] suggested learning fair representation for each client to achieve fairness, Du et al.
Equivalently, can the standard deviation (std) measure fairness across the network.

---

14 proposed reweighing the objective functions under faimess constraint. In our work, we focus on performance faireess, illustrating the benefits of our method through theoretical analysis and numerical experiments.
Robust FL Typical adversarial attacks include data poisoning and model update poisoning (Byzan- tine attacks). The former injects abnormal sample points into the training dataset 30 39 55 59
17. while the latter manipulates communication messages by sending arbitrary updates to the server, both attacks hindering the training processes. In this paper, we mainly aim to defend model update poisoning attacks and achieve Byzantine robustness (37. An extension to data poisoning attack is also considered in numerical experiments. Prior works favor Byzantine-rool -oouust SGD variants where the server alleviates the attack of Byzantine clients via robust aggregation rules [T] 68, 66 77. Beyond that, Li et al. [42] developed a robust distributed method by incorporating the L--norm regularizer robustify the objective function. Li et al. 44 used robust aggregation rules to achieve robustness and fairness. Our work leverages the ideas from 24 and 44 but differs from them by embedding the update process in wiw-dimensional fixed random subspace. Theoretical anal- ysis shows that with commonly used regularization parameters, our method is no worse than two SOTA methods 13 (see Figure D.. Extensive experiments manifest our method of achieving state-of-the-ar performance under various types and intensities of adversarial attacks.
65
Methodology
In this section, we present our method which is based on infimal convolution and subspace regular- ization. Conventional FL that trains single global model fit the "average client" suffers from statistical heterogeneity among massive devices. To enhance accuracy performance, we hope not only to leverage the global model, but also stylize it to fit the local data for each client. To this end, we use infimal convolution, which is originally proposed to smooth some extended real-valued convex function f with a sufficiently smooth kernel function g [52] We apply this technique in FL to bridge local models and global model. Here, is the usual objective function in the vanilla case, and is designed to characterize the relationship between local and global models. Given a general function g as the smoothing kernel, the personalized FL using infimal convolution is then formulated as
bi-level problem:
min F(w): = GI,
WEB
where G(-) is the aggregation function at the server side For & E ,N,
Fi Fi(w): = {Jx @ Ag) (w) = min (xx) + Ag(w xx) with fx(xx) = Ee, [x)) (2)
x,ERa
Here, & denotes infimal convolution operator, & is independent sample drawn from the distribution Dr. and fa (x&; Ex) is the loss function corresponding to this sample. w and Xx: represent the global and local model parameters, respectively. À is hyperparameter controlling the degree of personalization. Problem I is pure local training if A O, and is synchronized training when A - 0c.
The smoothing kernel function g is task-spe Many previous personalized methods can be cast into our infimal convolution framework by setting a proper For example, Dinh et al. 13,, Li et al.
4 used Moreau Envelopes as the regularizer, which is equivalent to g(.) = 111 11 Li et al.
42 proposed the - regularization g(.) = || Ipp instead. Motivated by the fact that high- dimensional data usually has low-dimensional representation that retains meaningful properties (60), and random projection would preserve similarity of data vectors (6), we propose to regularize the projection of local models in shared low-dimensional space, which equivalent to the following smoothing kernel
1 P
g(-)
where p 2 and P is a dsub x d random matrix that is generated initially and will not vary anymore. deub is the dimension of the shared-and sereed-nn-ffii and-fixed random subspace. The choice for P is flexible as the only requirement in our theory is that all the singular values of P are bounded from both sides. In this paper, we consider that P is generated with i...d. Gaussian entries and then normalized to have unit 1/2 norm for each row as suggested by [40. We comment that with this g. Fi(ww) W is actually a function
For simplicity, set G(-) as the simple average NV ΣN 1 Fl(w), but it can also generalize to other forms.
3

---

Wea Algorithm 1p-ppro:: Projection-based L Regularized Personalized Federated Learning
1: Input: Communication rounds T, local update rounds R, client sampling size S, regularization coefficient X, lower-level problem accuracy v, step size initial global model Wo. projection matrix P. speeduu control parameter [3.
2: for t T do
3: Server sends W, to all clients.
4: for all k = 1 to N clients do
5:
3 W:.
6:
for 0 to R 1 do
7:
Independently sample a fresh mini-batch Dr and minimize the loss function (4) up to accuracy level get x
8:
Update the local model w Err+1 by 5 end for
9:
10:
end for
Server uniformly samples a subset of clients St of size S. Each client sends W to the server.
12: Server updates the global model via Wr+1 (1 3)w, + Ekes, " s
end for
of = Pw since P(w - Xx) w Pxg. implies we can only focus on the low-dimensional
parameter Rou at the global level for algorithm description and theoretical analysis
3.1
The Algorithm
In this section, we introduce the algorithm 1p-proj (see Algorithm I for the bi-level optimization problem (I) with smoothing kernel 9 given by Eqn. (3).
The algorithm 1p-proj is essentially alternative minimization method bi-level optimization. Each client i maintains two parameters: their local parameter x and a copy of the global parameter wh,r with additional subscript denoting inner iterations and superscript the communication round. At round f, the server broadcasts the latest global model w, to all clients. Then each client initializes their version of global model wio0 as W, (line 5) and starts solve the problem via alternative minimization (lines 6-9).
(line 7) Given a local version global model wh., we use gradient descent (GD) to obtain an approximate solution x that minimizes hy up to accuracy level v, where
1 p | Pxx PI
ha DR.
Σ
D
SR,LEDe
Here Dr is mini-batch sampled uniformly and &x.; refers to sample from Dr. The GD iteration is terminated when (xt.ri DR, wh.
S v satisfied.
(line 8) Given a local parameter xf,,, the local version of global model wh,r is updated by one-step gradient descent:
7 Ow
(5)
krr P
After R steps of the alternative updates, each client has its version of the global model w Then the server accesses random set of S clients and produces the next global model by linear combination the latest W, and the average of (w.,Rkkes, Here, a hyperparameter 3, which could be viewed as a global step-size, introduced to control the global update process. Our theorem shows proper 33 can speed up convergence, but in practice, we find that the test performance only varies moderately for different choices of For simplicity, we only consider 3 in our experiments.
we restrict the global model w, to lie a fixed low- dimensional subspace, only W of dimension deub, instead of the full model x of dimension d, is communicated to the server during each round, which leads to much fewer bits for communication
Communication Efficiency In Algorithm I
Without ambiguity, term w the global model.

---

compared to vanilla FL. Besides, we remark on the difference between our method and other projection/sketching based methods. On one hand, distributed sketching 4. which directly projects the data in low-dimensional space at the start of training, is "one-shot" rather than iterative, while our method projects local models every communication round and the local training proceeds with the full model. On the other hand, sketched-SGDD [29] compresses the transmitted messages with different basis every time, while our random subspace is specified at the beginning and would not change after that.
Robustness and Fairness For one thing, by applying projection into low-dimensional sub- space, our method only requires (near) consensus of model parameters of different clients in the low-dimensional subspace. leaving flexibility for the system towards personalization and better generalization to the local data distribution, which could improve performance fairness and robust- ness when facing adversarial attacks. For the other, introducing 7.P-norm regularized term to the objective function is equivalent to launching an uncertainty set to the model parameter by rewriting the objective constrained optimization problem (e.g., --rmorm is the diamond-shaped uncertainty and L noom is the spherical uncertainty). in which way we can enhance accuracy by searching for model adaptive to the local data distribution in the uncertainty set. Formal analysis on a class of linear problems is provided in Section
Theoretical Analysis
4.1 Convergence
In this subsection, we establish the convergence of our algorithm for the case p = 2. We first present the assumptions and then state our main results.
Assumption 1 (Smoothness). f I-smooth, that is, for any Xk, X E RRd and & we have (x Ek) V S
| xxl12
Assumption (Bounded variance). The variance of stochastic gradients in each client is bounded, - i... Ege V - (x(x)))
S ~
Assumption (Bounded diversity). The variance local gradients to global gradient is bounded, ie., N E [V/((w) - V/(())l3 oz
Assumptions 1 and are standard for convergence analysis. Assumption also guarantees the smoothness of Jk- From the generation of P, we can show that P has full row rank with high probability (see Proposition
7 Then there exists a d x (d- deub) matrix Q such that (PT, Q) an
invertible matrix and PQ
O dema X ddddam).
Assumption 4 Low-dimensional condition). fx has a low-dimensional structure, that is, fa (P yk+ Qixi = f& (PTTP Ek) for any Yk E TRdmub, Sy E Rdd-dab,, As a consequence, the same equality also holds with fR replaced by fu-
Assumption 4implies that min (x Ex) = (col((P) fn Ex), where col( (A) denotes the subspace spanned by the column vectors of A. This means we can focus on the low-dimensional subspace spanned by the row vectors of P. We give an example satisfying the assumption. Suppose En and X& have the same dimensions and fx (Xxi Eu) = ((5) x 5 If EN E col( PT), then there exists an as such that & P ag. Decompose X P Y + Qyx- Then ((S), xx) I(a, P(P ys Qyx)) = I(a PT PTPp) yz). This implies that for linear models with data lying in col( P Assumption holds.
For the general case, it is not easy to verify Assumption directly. Intuitively, we can interpret Assumption 4 that the data concentrate parameters denoted by X = P yk + Qýk, only a low-dimensional linear combination yk = (PPT)-1 -Pxx can affect the value of fx-
a low-dimensional subspace. Then with the total
Recall that we can view FR as function of w instead of w, with some abuse of notation, we write Then we have the following result.
FR as F&(w)) min ERd [xx(x) + || Pxx [
'For example, when we fit generalized linear models via maximum likelihood method, the negative (log) likelihood function has this form.
5

---

Lemma 1. Suppose that Assumptions 7 and 4 hold and X > 4L.
With probability at least
1 2exp( (-ddaub). we have
2(1 CV
daygk 6
(
[F.(W.r) - X( A(Weer - P < 8²²²=
[Dex
1(1 CV dayle x - (1 + C
dayle
2
I
as long as C Vv < 1/30, where C, c are positive constants.
kyy) and the approximate gradient X(w R.r pxt,)) due to mini-batch sampling and optimization error of the inner loop. From the expression of 62, we see that this error has mild dependence dsub.
Lemma 1 quantifies the error between the exact gradient VFF (W.
Based Lemma we can establish the convergence of the global model and personalized parameters of Algorithm !
By the smoothness of fk. we can show that F3 is Lp-smooth with LF X Then
the convergence of Algorithm [ guaranteed by Theorem [
Theorem Suppose that Assumptions 1 hold and daub/ / sufficiently small. Let fl 90121.
with > max v 1012 + ALJ. 8 z and AF F(Wo) weR F(W). If is uniformly sampled (0, 1..... 13, then with probability least 1 exp( exp((cclub), there exists 1j S dt such that
BR
(A (N/S 1)) +0
[VF
S o
TOT
VTN
due to instialization
due cliens sampling )2 + 2
(6)
+ O
+0 =: Ou.
(BT)2/3
cliens drift with multiple local updates and approximation errors
X²a
where is positive constant number, of 8² defined in Lemma 7 is the approximation error of the inner loop, the expectation is w.r.t all the randomness except for P and O hides constants. Moreover, suppose that x/. is solution to
--10 measures the bounded diversity of Fk-
Vha(x; DR, w:) < Then with probability least 2 2exp(-cddaule cdlub)) have
of + 82 88²)
E
Px
W:-
5 + 0 X2
N
2
When there no client sampling, choosing O (L/(TRN))/3)) Eqn. (6) shows the average over indices and of the distance between personalized parameters (after linear transformation) and global model parameters converges to 0 + o + 82). Here À can be chosen to trade off different terms.
((NR) leads sublinear speedup
Our Theorem shares similar forms as Theorem in 13] The constant term O (X²82) appears in both theorems and is caused by biased gradients, i.e., we only get biased estimate of V Fg due to inexact inner optimization (non-zero v) and batch data (small [Dx)).
4.2 Robustness and fairness
In this subsection, we explore the robustness and fairness benefits of 1p-proj on class of linear problems and compare 1p-proj with Ditto [44] and pFedMe [13]. For ease of analysis, we assume the rows of P are orthogonal. In practice, we can directly use the random matrix generated as in Section 3 without explicit orthogonalization, since high-dimensional random vectors are nearly orthogonal.
SSee Proposition in Appendix A.2 for the details.

---

5.531
1'es% Der
5,000
13525
0.010
3,000
13515
3.005
3,004
0.010
5.002
5.180
8.090
0.003
0.5
0.6
0.7
0.0
0.75 aicoo 0.825
0:8 0.835 3,500 TeRLACC
Figure 1: Test losses of pFedMe, Ditto and 1p-proj under different values of A. our settings, the losses of pFedMe and Ditto coincide.
(a) CIFAR
(b) EMNIST
Figure 2: Accuracy- Faimess trade-off of competing methods. (The point closer to the bottom right corner is better.)
Our Setting We focus on a simplified setting where the number of local update steps is infinite, there is only one round of communication and all clients participate in the communication. Then it is natural to set 3 = 1. Suppose that the true parameter on client is Wg. there are n samples on each client and the covariate client le is {
l and fixed. The observations generated by yk,, Ek W. 2k,
where the noises Ex.i iid. (0,00*) For simplicity, we assume E ER = brda. Then the test loss on client l is (xx) 1 (S
=/,i xx, where z (N o
and are
2n
independent of ZR,i.
Three Attacks We examine three types of Byzantine attacks. Denote the message delivered by
malicious client as W (ma) then the attacks are listed as follows.
Same-value attacks: The message sent by Byzantine client k is set w/ (iaa cl deab where Idmas E dod is the vector of ones and (0,
Sign-flipping attacks: The transmitted messages sign-flipped and then scaled, i.e., Byzantine
client & computes the true value W but sends W (ma) = |c| W to the server where ~ NNO,,²)
Gaussian attacks: The message sent by Byzantine client A is set as w (ma) No : Id
The analyses for different attacks are similar, thus we only focus on the same-value attacks here for illustration. Results for other attacks are deferred to Appendix B.3 Suppose that there are N₂ malicious clients, and the heterogeneity is uniform
dimensions in the sense of Eqn. (5) in Appendix B.3] where we define Σ, to measure data heterogeneity in single dimension. Let
J/N
Xi = E Ng (+² (r2))) The numerator of A is the variance noises over the number of samples.
The denominator is the sum of data heterogeneity and variance of attacks. When À = Ai pFedMe, Ditto and jp-proj all achieve their corresponding minimal losses. However, we do not know factors affecting Xj in advance, implying getting the particular value of X is possibly hard. Therefore, we need to compare the performance of these methods under different values of X.
Proposition
(Formal statement Theorem 2, Appendix B.3). Denote the averaged losses on benign
clients of pFedMe, Ditto and lp 1p-pro by Me. and (A), Iondni (A) and L [2 (X) respectively. The
explicit forms of losses are in Appendix B33 Under the same-value attacks, we have (i) M.Me (X)
I Di (A), AA > 0 and (ii) if X; < b. L 12, and (A) S L Me,at (A) if and only if 1-
22"
Porposition D implies lp-proj outperforms both PFedMe and Ditto once À larger than a threshold 2A
value T-X; . which is slightly larger than 2 The pattern is captured by Figure where we set
200, N 100. N. 20, 100, deub 10. 1, a 1, Σ 0.1 and 7 100. Then pretty small value. Even for À < T- /b+ the gap between 1p-proj and pFedMe / Ditto is negligible. Thus, 1p-proj has comparable or beter performance for any X >
Xi ~ 4.9e
2x
Now we turn to the performance fairness defined in Definition T For simplicity, we further assume that the true parameters Wy are i.i.d. and distributed as N N(Hw Ew).
Proposition 2 (Formal statement in Theorem 3 Appendix 3.4.. Denote the variance of test losses on different clients of PFedMe Ditto and lp jp-prjj by V Me
()) (P) and 222 (A) respectively. We
7

---

22
Foand
(a) EMNIST, Train Loss
(b) EMNIST, Test Accuracy
(c) CIFAR, Train Loss
(d) CIFAR, Test Accuracy
Figure 3: Personalization performance of 1p proj-r--- 1p- pp-projj- with other methods on EMNIST and CIFAR.
833
80
81 50
035
3.53
315
1.2
(a) EMNIST, same-value
(b) CIFAR, sign-flipping
(c) EMNIST, Gaussian
(d) Synthetic(O, O), data poisoning
Figure 4: Robustness comparison of different methods, i..., average test accuracy of benign clients. The dashed black line shows the performance of pure local training. line with less than points implies the algorithm collapses because the intensity of the given attack exceeds the limit the corresponding algorithm could tolerate.
have for AA > O, (A) < (A) = (V) More specifically, EV (A) = (dd) and EV12 (A) Oddubb) where the expectation is taken w.r.f. the randomness of Wi-
Proposition 2 shows 1p-proj always brings more uniform test losses, no matter what value À is. In particular, (A) = (d sub. while (V) = O(d)). Since likely that dsub < d, the advantage of 1p-proj could be much larger. It implies 1p-proj is more fair than pFedMe and Ditto. For the formal theorem, see Appendix B.4
Numerical Experiments
In this section, we demonstrate 1p-proj has the desirable properties through numerical experiments. Experimental Setup We test j well as other comparable algorithms six datasets from common ML and FL benchmarks [50 [ We consider both convex and non-convex models. For the latter, consider neural networks including both MLP and CNN. Details about datasets, models and basic information about the FL system are provided in Table 2 in Appendix C To better model the statistical heterogeneity, we distribute the dataset among clients in a non-iid -id fashion such that each client only contains partial classes of the data in muutt-classifiiation problems.
For each client, the training and testing data are pre-specified as in the MI. community, and 20% of training data is randomly extracted to construct validation set, keeping the remaining 80% as the training set. The training set is used for model fitting and parameter estimation. For each competing method, we use the accuracy performance on the validation set as the tuning criterion and conduct grid search to choose the best dyper-parameter combination among prescribed candidate set. All reported results are evaluated on the test dataset. More details about hyperparameter tuning are provided in Appendix C.2] Furthermore, incorporate partial participation [5] 45), randomly select 10% of the clients for aggregation at each communication round. The projection dimension of the random subspace for each dataset is chosen based the full model size and communication budget (see Appendix C.2). Source code for the reproduction of numerical results is available at https://githu: com/ comm/testtennlll//rreeee
Personalization Accuracy Performance order to highlight the empirical performance of our proposed method, we compare 1p-proj with several state-of-the-att personalization methods in the literature, together with global method and a pure local method. Specifically, we consider the case when p (1p-po proj-1) and
(ip-proj-2). For SOTA methods, consider Ditto [44), PFeaMe [3]. Per-fee feeavg [16], LG-FedAvg [66] and RSA 42 A brief description of these approaches is provided in Appendix C.I
Due to space limitations, we only show the comparisons on training loss and test accuracy on two standard datasets (EMNIST and CIFAR) in Figure 3 Results the other datasets are left in Table
8

---

Table I: Communication performance Synthetic 0) and EMNIST datasets. Two aspects considered: test accuracy on given byte budget and bytes used to achieve target test accuracy. A on the column "Test Acc" refers to the situation that bytes used in the first iteration of the algorithm have exceeded the budget, and a * on the column "Used Bytes" means the algorithm could not provide a solution that reaches the target accuracy.
Syathetic(O, 0)
EMNIST
Method
Bytes Budget
Test Ace
Turget Acc
Used Byles
Bytes Budget
Test Acc
Target Acc
Used Bytes
FodAvg
328020
0.625
0.6
597800
4236900
0.7
445851400
Sketch
328020
0.456
0.6
4236900
0.7
1p-proj-1
328020
0.885
0.6
4620
4236900
0.906
174720
Ip-pruj-2
328020
0.888
0.6
4620
4236900
0.906
0.7
196560
LBGM 328020
0.538
0.6
365002
4236900
*
0.7
769902776
QSGD
328020
0.115
0.6
923350
4236900
673302175
DGC
328020
0.6
391800
4236900
0.7
*it
LG-FedAvg
4236900
0.071
0.7
230786010
From these figures, we see that 1p-proj - and 1p-proj -2 have comparable or even superior performance than other methods. Furthermore, the training process is more stable the loss and accuracy curves have less fluctuation.
and Figure 5 in Appendix C.3
Communication Efficiency We compare 1p-proj with the global baseline FedAvg [1 and five standard approaches using gradient and model compression, namely Sketch [29], LBGM 3. QSGD []) DGC [47 and LG-FedAvg [46]. We quantify the communication cost via total bytes written and read by active clients each round and capture the relation between test accuracy and communicated bytes. Due to space limitations, we only show the results on two datasets in Table (Synthetic 0)
and EMNIST) with the full results left in Table 4 in Appendix C.4
is clear that our method is more communication efficient since we only communicate low- dimensional messages. Given a communication budget of bytes, 1p-proj obtains ~ 26.3% and 83.5% test accuracy improvement on Synthetic 0) and EMNIST datasets respectively. On the other hand, given target test accuracy, our proposed method needs much fewer bits than the rest and saves the communication cost by 79x and 1320x on the two datasets compared with the best competing method. Besides, our method owns flexibility on the choice of the projection dimension dsub; because the convergence dependence of our method on daub is mild as predicted by Lemma [ The compression rate of our proposed methods can be 1000x or even higher, while that of sketching or gradient compression methods typically is no larger than tens.
Robustness In addition to the three Byzantine attacks introduced in Section 4.2 we consider a
stronger data poisoning attack in the following experiments.
Data poisoning attacks: The training samples malicious clients poisoned with uniformly randomly chosen noisy labels. Furthermore, when communicating, these clients would scale their transmitted messages dominate the aggregate update.
For the former three Byzantine attacks, the noise variance T is set as 100, 10 and 100 respectively. The corruption levels, i.c., the fractions of malicious clients, are set as (0.1, 0.2, 0.5, 0.8). For data poisoning attack, the scaling factor is randomly sampled from (0, 20a) and the corruption levels are from {0.02, 0.05, 0.1, 0.2). Under different types of attacks and different levels of corruption, we compare the average test accuracy performance on benign clients of 1p-proj- 1 and 1p-proj-2 with various defense baselines, including global training augmented with different robust aggregation techniques, such as median and Krum [7]. Ditto and RSA.
Due to space limitations, we show only representative figure for each attack in Figure 4 results, please refer to Appendix C.5) From Figure we find that under relatively weak attacks, e.g., same-value and Gaussian attacks, the test accuracy of 1p-proj-1 1 and 1p-proj-2 rarely decays as the fraction of malicious clients increases, while we observe senerveiigniffcaat sigmificant drops on the test accuracy for other algorithms once malicious clients exist. On the other hand, under strong attacks, e.g. sign-flipping and data poisoning, an increasing fraction of malicious clients deteriorates the accuracy performance continuously and even collapses the local model if the attack intensity is too large. For example, under the sign- flippiii attack, when the fraction of malicious clients exceeds 20%, only 1p-proj-1, RSA and Flobal+Krum work, while all other methods fail to produce a solution. When the attack intensity further increases to 80%, the only robust methods that achieve the desired accuracy are 1p-proj- and RSA.
For full
The numerical results show that our method is resistant to standard malicious attacks, which roots in the combination of projection and L -norm subspace regularization that attribute to the robustness.

---

Consider an extreme example: if the subspace dimension is chosen as O, then the joint optimization reduced pure local training. No matter how serious the adversarial attack is, the local test performance would not be affected. Therefore, random projection helps alleviate the attacks applied in the original space, while the -nom helps eliminate outliers further 34
Fairness To illustrate the accuracy and performance fairesss trade-off, we plot the variances of accuracies across the system against the corresponding test accuracies for 1p-proj and several other different approaches in Figure 2
To examine the performance fairness in isolation, the numerical experiments are performed without adversarial attacks in this part. Furthermore, for each competing method, we select the optimal achievable test accuracy after the 20th communication round, and the corresponding variance is picked up. Due to space limitations, we show the results on two datasets here with the full results left in Figure Appendix C.6
The results with respect to performance faimess show that 1p-proj-1 and 1p-proj-2 provide accurate and fair solutions that are comparable to other SOTA methods. In particular, on CIFAR, 1p-proj achieves the highest test accuracy of 79.22% with the lowest variance of 0.0097 among all the competitors. Although RSA achieves the same variance as 1p-proj-1, its corresponding test accuracy is only 77.68% which 1.54% lower than 1p-proj-1 On the other hand, on EMNIST, despite the optimal approach is Ditto, with a test accuracy of 90.89% and the corresponding variance of 0.0016, our proposed method shows comparable performance, e.g., 1p-proj -2 achieves a test accuracy of 90. 70% with variance of 0.0016, which is only slightly inferior to the previous method. Theoretical analysis in Proposition 2 implies that under the linear model, the dependence of the variance the projection dimension is of squared order, indicating -iw-dimeniional projection helps reduce the variance of test losses among clients. Numerical results suggest that this conclusion may be generalized to broader settings.
6 Concluding Remarks
In this paper, we have proposed a simple but powerful personalized FL. approach based on infimal convolution and subspace projection that we call 1p-proj. We have presented the convergence results for smooth objectives with square regularizers. Inherent henefits robustness and fairness of our method are also illustrated on a class of linear problems. Empirical results show that our approach could significantly save communication costs, improve robustness under various kinds of adversarial attacks, and promote performance fairness. In future work, we would be interested in establishing convergence results for general L" regularizers and strongly convex objectives, exploring numerical applications on other ML tasks and large-scale datasets, and considering additional constraints, e.g.. differential privacy.
Acknowledgments and Disclosure of Funding
This work has been supported by the National Natural Science Foundation of China (No. 12271011).
References
[1] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication--tticiinnn SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), 2017.
[2] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111-132, 2018.
[3] Sheikh Shams Azam, Seyyedali Hosseinalipour, Qiang Qiu, and Christopher Brinton. Recycling model updates in federated learning: Are gradient subspaces low-rank? In International Conference on Leurning Representations, 2021.
[4] Burak Bartan and Mert Pilanci. Distributed sketching methods for privacy preserving regression. arXiv preprini arXiv:2002.065538, 2020.
[5] Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. arXiv preprint arXiv:1206.00 6389, 2012.
10

---

[6] Ella Bingham and Heikki Mannila. Random projection in dimensionality reduction: applications image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 245-250, 2001.
[7] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 128, 2017.
[8] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konevený, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXi:: 2018.
[9] Fei Chen, Mi Luo, Zhenhua Dong, Zhenguo Li, and Xiugiang He. Federated meta-learning with fast convergence and efficient communication. arXiv preprint (rXivv8802.07876 2018.
[10] Shuxiao Chen, Qinqing Zheng, Qi Long, and Weijie J Su. A theorem of the alternative for personalized federated learning. arXiv preprint arXiv:2103.0199 2021.
[11] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, (2):1-25, 2017.
[12] Yuyang Deng, Mohammad Mahdi Kamani, and Mchrdad Mahdavi. Adaptive personalized federated learning, arXiv preprint arXiv:2003.1346. 2020.
[13] Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen. Personalized federated learning with moreau envelopes. In Advances in Neural Information Processing Systems, volume 33, pages 21394-21405, 2020.
[14] Wei Du, Depeng Xu, Xintao Wu, and Hanghang Tong. Fairness-aware agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 181-189. SIAM, 2021.
[15) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[16] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: model-agnostic meta-learning approach. arXiv preprint 1rX1v:2002.07948, 33:3557-3568, 2020.
[17] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to byzantine-robust federated learning. In 29th (USENIX) Security Symposium (!USENIX) Security 20), pages 1605-1622, 2020.
[18] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In International Conference on Machine Learning, pages 1126-1135, 2017.
[19] Filip Hanzely and Peter Richtárik. Federated learning of a mixture of global and local models. arXiv preprint trXiv:2002.05516, 2020.
[20] Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtarik. Lower bounds and optimal algorithms for personalized federated learning. In Advances in Neural Information Processing Systems, volume 33, pages 2304-2315, 2020.
[21] Filip Hanzely, Boxin Zhao, and Mladen Kolar. Personalized federated learning: A unified framework and universal optimization techniques. arXiv preprint arXiv:2102.0974., 2021.
[22] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29:3315-3323, 2016.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
11

---

[24] Cean-Baptiste Hiriart- Hiriart-Uruuty and Claude Lemaréchal. Convex analysis and minimization algo- rithms. 1993.
[25] Tim Hoheisel, Maxime Laborde, and Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 7(1); 79-96, 2020.
[26] Zeou Hu, Kiarash Shaloudegi, Guojun Zhang, and Yaoliang Yu. Fedmgda+: Federated learning meets multi-objective optimization. arXiv preprint arXiv:2006. 14899 2020.
[27] Wei Huang, Tianrui Li, Dexian Wang, Shengdong Du, and Junho Zhang. Fairness and accuracy in federated learning. arXiv preprint arXiv:2012. 10069, 2020.
[28) Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangehuan Liu, Jian Pei, and Yong Zhang. Personalized cross-silo federated learning non-iid data. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[29] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora. Communication-effie efficieen distributed sgd with sketching. Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 13142-13152,
2019.
[30] Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. 2018 IEEE Symposium on Security and Privacy (SP), pages 19-35. IEEE, 2018.
[31] Yihan Jiang. Jakub Konevený, Keith Rush, and Sreeram Kannan. Improving federated learning personalization via model agnostic meta learning. arXiv preprint arXiv: 1tt.:/9999/248,,,. 2019.
[32] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, al. Advances and open problems in federated learning. arXiv preprint 2019.
[33] Sai Pranecth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learning. arXiv preprint
06378, 2019,
[34] Qifa Ke and Takeo Kanade. Robust 1/sub 1/norm factorization in the presence of outliers and missing data by alternative convex programming. In 2005 IEFE Computer Society Conference on Computer Vision and Pattern Recognition CEVPR'05), volume 1, pages 739-746. IEEE, 2005.
[35] Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant. Survey of personalization techniques for federated learning. In 2020 Fourth World Conference Smart Trends in Systems, Security and Sustainability (WorldS4), pages 794-797. IEEE, 2020.
[36] Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. Counterfactual faimess. arXiv preprint arXiv:1703.0688 2017.
[37] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concurrency: the Works of Leslie Lamport, pages 203-226. 2019.
[38] Ang Li, Jingwei Sun, Binghui Wang, Lin Duan, Sicheng Li, Yiran Chen, and Hai Li. Lotteryfl: Personalized and communication-effiiiee federated learning with lottery ticket hypothesis on non-iid datasets, arXiv preprint arXiv:2008.0337 2020.
[39] Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks on factorization- collaborative filtering. Advances neural information processing systems, 29:1885-1893, 2016.
[40] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.
12

---

[41] Daliang Li and Jumpu Wang. Fedmd: Heterogenous federated learning via model distillation. arXiv preprint arXiv: 1910.0381,, 2019.
[42] Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. Rsa: Byzantine- robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1544-1551, 2019.
[43] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. arXiv preprint 1rXiv:1812.06127,, 2018.
[44] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357-6366 6368. PMLR, 2021.
[45] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the convergence of FedAvg on Non-IID data. arXiv:1907.02//6. 2019.
[46] Paul Pu Liang, Terrance Liu, Liu Ziyin, Nicholas B Allen, Randy P Auerbach, David Brent, Ruslan Salakhutdinov, and Louis-Philipee Morency. Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001.01523, 2020.
[47] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In International Conference on Learning Representations, 2018.
[48] Lingjuan Lyu, Xinyi Xu, Qian Wang. and Han Yu. Collaborative fairness in federated learning. In Federated Learning, pages 189-204. Springer, 2020.
[49] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications federated learning. arXiv preprint arXiv:2002.10619, 2020.
[50] Sébastien Marcel and Yann Rodriguez. Torchvision the machine- vision package of torch. In Proceedings of the 18th ACM international conference on Multimedia, pages 1485-1488, 2010.
[51] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. communication-efffcceen learning of deep networks from decentralized data. In Artificial Intelligence and Statistics (AISTATS), 2017.
[52] Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 93:273-299 1965.
[53] Arkadi Nemirovski, Anatoli B. Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim., 19:1574-1609 2009.
[54] Yurii Nesterov. Lectures Convex Optimization. 2018.
[55] Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph. Shing- Lau, Satish Rao, Nina Taft, and Doug Tygar. Antidote: understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, pages 1-14, 2009.
[56] Osama Shahid, Seyedamin Pouriyeh, Reza M Parizi, Quan Z Sheng, Gautam Srivastava, and Liang Zhao. Communication efficiency in federated learning: Achievements and challenges. arXiv preprint arXiv:2107.1088 2021.
[57] Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. In Advances in Neural Information Processing Systems (NIPS), 2017.
[58] Sebastian Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint axXiv:1907.04232. 2019.
13

---

[59] Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras. When does machine learning [FAIL]? generalized transferability for evasion and poisoning attacks. In 27th {USENIX) Security Symposium ({ ([USENIX) Security 18), pages 1299-1316, 2018.
[60] Laurens Van Der Maaten, Eric Postma. Jaap Van den Herik, et al. Dimensionality reduction: comparative. Mach Learn Res, 10(66-71):133 2009.
[61] Roman Vershynin. Introduction the non-asymptotic analysis of random matrices. Compressed Sensing, pages 210-268, 2012.
[62] Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication-effiiiee distributed sgd with slow momentum. In International Conference on Learning Representations, 2019.
[63] Kangkang Wang, Rajiv Mathews, Chloé Kiddon, Hubert Eichner, Franecoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. arXiv preprint arXiv:1910.1022: 10252, 2019.
[64] Ruiyuan Wu, Anna Scaglione, Hoi-To Wai, Nurullah Karakoc, Kari Hreinsson, and Wing-Kin Ma. Federated block coordinate descent scheme for learning global and personalized models. arXiv preprini 20Xi:: 2.....3000 13900, 2020.
[65] Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is feature selection secure against training data poisoning? In international conference on machine learning, pages 1689-1698. PMIR, 2015.
[66] Cong Xie, Oluwasammi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd. arXiv preprint 1rXiv:1802.10111 2018
[67] Xinyi Xu and Lingjuan Lyu. A reputation mechanism is all you need: Collaborative fairness and adversarial robustness in federated learning. In Proc. ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, 2021.
[68] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine- distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659. PMLR, 2018.
[69] Han Yu, Zelei Liu, Yang Liu, Tianjian Chen, Mingshu Cong, Xi Weng, Dusit Niyato, and Qiang Yang. A falmess--wart incentive scheme for federated learning. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 393-399, 2020.
[70] Tao Yu, Eugene Bagdasaryan, and Vitaly Shmatikov. Salvaging federated learning by local adaptation. arXiv preprini 200x::20002.4755, 2020.
[71] Zirui Zhou, Lingyang Chu, Changxin Liu, Lanjun Wang, Jian Pei, and Yong Zhang, Towards fair federated learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 4100-4101, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The Introduction part (Section I1 summarizes our contribution and the Related Work part (Section 2 discusses the relationship between our work and previous ones.
(b) Did you describe the limitations of your work? [Yes] See the conclusion part. We will consider convergence analysis for more general Lt regularizers and additional constraints our future work.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Societal impacts are not applicable to our work.
14

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results....
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4. for the full assumptions used in convergence analysis and Section 4.2 for the setting considered in robustness and fairness analysis.
(b) Did you include complete proof' of all theoretical results? [Yes] They are deferred in Appendix A
and
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] The source code provided the supplementary material and the experimental details are described in Appendix [
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they chosen)? [Yes] The data split strategy is described in Section and the hyperparameter settings for all the competing methods described in Appendix [C.2
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The complete results are reported in Appendix C
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We use GPU for computing and the type is described in Appendix C
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "RKUB9lm9nal", "reviewer": "Reviewer_RhCc", "summary": "This work aims to tackle three problems in FL: 1) communication efficiency, 2) robustness (Byzantine attacks) and 3) fairness. Specifically, this work projects local models into a shared-and-fixed low-dimensional random subspace and uses infimal convolution to control the deviation between the reference model and projected local models. Theoretically, it shows convergence on strongly convex objectives with square regularizers and mild dimension reduction. Numerical results are presented on synthetic data, MNIST, Cifar10 with MLP and CNN.", "questions": "1. How do we generalize the theoretical results to neural network training (non-convex)?\n2. What is the key technical novelty of using the proposed projection vs sketching-based efficient FL methods?\n3. As the proposed methods seem easy to implement, would it be possible to test them on more complex tasks to make the methods more convincing?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The problems addressed by this work are very important.\n2. Theoretically and empirically show the advantage vs. the existing methods\n3. Extensive experiments are conducted, including comparison and different variants of experiment settings. \n\nWeaknesses:\n1. The presentation of this paper is not easy to digest as multiple components are delivered without sufficient details and support. The authors also include \"due to space limitation.\" I would suggest the authors consider the key messages to deliver in the conference paper. \n2. The theoretical results seem interesting. However, the assumptions (strong convexity and smoothness) are relatively strong and have a clear gap between the real deep neural network training scenarios. \n3. One related work could be included in the comperison:\nRothchild, D., Panda, A., Ullah, E., Ivkin, N., Stoica, I., Braverman, V., ... & Arora, R. (2020, November). Fetchsgd: Communication-efficient federated learning with sketching. In International Conference on Machine Learning (pp. 8253-8265). PMLR.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Discrimination / Bias / Fairness Concerns"]}, "extra_text": {}}, {"review_id": "R26IfesZwl8", "reviewer": "Reviewer_vPmy", "summary": "This paper tackles the problem of providing increasingly uniform performance across devices (fairness) through projection of local models into a shared low-dimensional subspace and infimal convolutions. The paper provides theoretical proofs for convergence and explores robustness and fairness using the proposed method. The effectiveness of this approach is demonstrated through extensive experiments on federated datasets, showing improved performance in personalization accuracy, communication efficiency, robustness and fairness.", "questions": "- Why does `lp-proj` help reduce the variance of performance among clients?\n- Why does infimal convolution help personalized performance of the local model?", "limitations": "- Limited focus on how the model improves personalization performance using this method.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n- The paper is well-written and organized. Algorithms are easily understandable and the code is well-written.\n- Thorough theoretical analysis with extensive proofs that demonstrate the convergence of `lp-proj`.\n- Theoretical analysis and experiments support the method's claim to improve robustness and fairness.\n- Extensive numerical experiments on strongly-convex objectives and heterogenous datasets demonstrate improved state-of-the-art personalization performance. The proposed method significantly reduces communication costs.\n\n**Weaknesses**:\n- Limited technical novelty with many of the ideas coming from `FedProx` and `pFedMe`. Note: extensive comparison analysis gives convincing evidence that the method is sufficiently different from previous work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGt7UzU2dez", "reviewer": "Reviewer_yNQy", "summary": "This paper proposes a personalized federated learning (PFL) method to achieve communication efficiency, robustness and fairness, by projecting local models into a shared-and-fixed low-dimensional random subspace and using infimal convolution to control the deviation between the reference model and projected local models. Theoretical analysis about strongly convex objectives is provided. Experiments on both synthetic data and real data are used for evaluation. ", "questions": "1. Does the method still converge for non-convex objectives?\n2. How is the performance on widely used deep models like ResNet and larger datasets like ImageNet? \n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The studied problem about designing method to achieve communication efficiency, robustness and fairness in PFL is interesting and important.\n2. The paper is well written with good organization.\n3. Experiments show that the proposed method does achieve good performance on the adopted models and datasets.\n\nWeaknesses:\n1. The theoretical analysis is weak due to some ideal assumptions. First, only results for strongly convex objectives are provided. But most models in real practice are non-convex. Second, to analyze robustness and fairness (Section 4.2), the authors assume that the number of local update steps is infinite, which is unreasonable because in non-convex cases the algorithm will not converge if the number of local update steps is set to be infinite. \n2. The datasets are relatively small. \n3. The models, especially deep models, seem to be specially designed. Why not just adopt some widely used models like ResNet?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IBBqmPL42E8", "reviewer": "Reviewer_xiRc", "summary": "This paper formulates the goal to balance different constraints of interest (i.e., communication efficiency, robustness and fairness) simultaneously. The authors propose a personalized federated learning algorithm named lp-proj, which is supported by theoretical analysis. Extensive experimental results show the effectiveness of the proposed method.", "questions": "Please refer to Weakness.\nI will increase my score if the authors can address my questions.\n", "limitations": "1) The theoretical analysis is based on the assumption that the objective function is strongly convex, which is very strong.\n2) The fairness metric used in this paper is in terms of performance. I'm not sure whether it works well on other fairness metrics such as group fairness (DP, EO etc.).\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) This paper proposes a practical problem which has not been studied widely. \n2) The proposed method is technically sound and is well supported by theory.\n3) Extensive experiments on three datasets show the effectiveness of the proposed algorithm. \n\nI also have some questions:\n1) (Main concern) I have noted that the authors show the results of trade-off between average performance and performance fairness. Is there a trade-off between performance and communication efficiency / robustness? How to balance them?\n2) It seems that this paper simulates Non-IID settings only based on the target label. Can this work be applied to other Non-IID settings, e.g. domain shifts.\n3) Is the proposed algorithm robust enough to deal with emergencies, e.g., some clients drop out in the training stage? \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3PAaEhk-ohR", "reviewer": "Reviewer_LhiF", "summary": "The paper proposes a Personalized FL method which aims to achieve robustness, fairness and communication efficiency simultaneously. \nThey achieve fairness through personalization and regularization (i.e., $L^{p}$-regularization) similar to existing works , and propose low-dimensional random projection of the local client updates to improve communication cost. The experimental results show the improvement of these metrics compared to existing baselines. ", "questions": "The Robustness performance of Ditto for EMNIST dataset seems a little bit surprising to me, because the results reported in Ditto for FEMNIST does not suggest this poor robustness performance on EMNIST, can you elaborate on this ? have you performed hyper parameter fine-tuning for Ditto Algo ?\n", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n*  The paper appears to be theoretically sound as well as the claims seem to be supported by theoretical justifications as well as numerical experiments.\n* The paper addresses three important challenges in Federated Learning Settings (Communication Efficiency, Fairness, Robustness) altogether, which seems to me that there is a gap in existing works. \n\nWeakness\n* The Novelty seems to be a little low compared to existing works ,  the embedding of local updates to lower dimension seems to be main novelty here. \n* In terms of Personalization Accuracy Performance, the results are mixed between Ditto and new approach (Table 3 Appendix), however in the main body of the paper (i.e. Sec 5), it is claimed the new approach is better the competitors. \n* In terms of communication performance, lack of comparison with some existing works such as the one proposed here [1]. \n* No experiment or discussion around the robustness of the proposed approach vs other attacks such as Backdoor attacks [2] is mentioned in the paper. \n\n1. Federated Learning with Buffered Asynchronous Aggregation, 2022, Nguyen et al. \n2. Attack of the Tails: Yes, You Really Can Backdoor Federated Learning, NeurIPS 2020, Wang et al..", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept