Semi-Variance Reduction for Fair Federated Learning
Authors: Saber Malekmohammadi
Guojun Zhang
Yaoliang Yu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Fairness

Abstract: Ensuring fairness in Federated Learning (FL) systems, i.e. ensuring a satisfactory performance for all of the diverse clients in the systems, is an important and challenging problem. There are multiple fair FL algorithms in the literature, which have been relatively successful in providing fairness. However, these algorithms mostly emphasize on the loss functions of worst-off clients to improve their performance, which often results in the suppression of well-performing ones. As a consequence, the system's overall average performance is usually sacrificed for achieving fairness. Motivated by this and inspired by two well-known risk modeling methods in Finance, Mean-Variance and Mean-Semi-Variance, we propose and study two new fair FL algorithms, Variance Reduction (VRed) and Semi-Variance Reduction (Semi-VRed). VRed encourages equality between clients loss functions by penalizing their variance. In contrast, Semi-VRed penalizes the discrepancy of only the worst-off clients loss functions from the average loss. Through extensive experiments on multiple vision and language datasets, we show that, Semi-VRed achieves SoTA performance in scenarios with highly heterogeneous data distributions by improving both fairness and the system overall average performance at the same time.

Under review as a conference paper at ICLR 2023
SEMI- VARIANCE REDUCTION FOR FAIR FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Ensuring fairness in Federated Learning (FL) systems, i.e. a satisfactory perfor- mance for all of the diverse clients in the systems, an important and challenging problem. There are multiple fair FL algorithms in the literature, which have been relatively successful in providing fairness. However, these algorithms mostly em- phasize on the loss functions of worst-off clients to improve their performance, which often results in the suppression of well well-performing ones. As a consequence, they usually sacrifice the system overall average performance for achieving fair- ness. Motivated by this and inspired by two well-known risk modeling methods in Finance, Mean- Variance and Mean-Semi- Variance, propose and study two new fair FL algorithms, Variance Reduction (VRed) and Semi- Variance Reduc- tion (Semi -Vee)..... VRed encourages equality between clients loss functions by penalizing their variance. In contrast, Semi -VRed penalizes the discrepancy only the worst-off clients loss functions from the average loss. Through extensive experiments on multiple vision and language datasets, we show that, Semi - VRed achieves SoTA performance in scenarios with highly heterogeneous data distribu- tions and improves both faireess and system overall average performance.
INTRODUCTION
Federated Learning McMahan et al. (2017) is a framework consisting of some clients and the private data that is distributed among them, and it allows training of shared or personalized model based on the clients data. Since the invention of FL by proposing the well-known FedAvg algorithm
(McMahan et al. 2017). it has attracted an intensive amount of attention and much progress has
been made in its different aspects, including algorithmic innovations (Li et al.] 2020b Reddi et al.
2020a Pathak & Wainwright 2020 Huo al.)
2020 Wang et al. 2020 Reddi al. |020b] Qu 2020c Mohri et al. [019
ct al.] 2022), fairness (McMahan et al. 2017 Li et al.
Li et al. 2020a
Yue al. [ Zhang et al. (022a). convergence analysis Khaled et al. 2020
Li et
2020
Gorbunov et al. 2021 ), personalization (Zhang et al. 2021 Chen & Chao
2022 Oh et al.
2022
Zhang al. 2022b Bietti et al., 2022).
Due to heterogeneity in clients data and their resources, performance fairness is an important chal- lenge FL systems. There have been some previous works addressing this problem. For instance, Mohri et al. (2019) proposed Agnostic Federated Learning (AFI.), which aims at minimizing the largest loss function among clients through a minimax optimization framework. Similarly, [i et al.) (020a) proposed an algorithm called TERM using tilted losses, Ditto (Li et al.) 2021 is another existing algorithm based on model personalization for clients] [T] Also, q-Fair Federated Learning (q-FFL) (Li et al.) 2020c) is an algorithm inspired by a-fairness in wireless networks (Lan et al. 2010). Recently, Zhang et al. (2022a) proposed PropFair based on the concept of Proportional Fairness (PF). Interestingly, they also showed that all the aforementioned fair FL algorithms be unified into a generalized mean framework. GiFair Yuue et al. 2021) is another recent algorithm which achieves faimess using a different mechanism than the previously mentioned algorithms: by penalizing the discrepancy between clients loss functions, i.c. encouraging equality. FCFL (Cui al. 2021) uses a constrained version of AFL for achieving both algorithmic parity and perfor- mance consistency in FL settings.
In order to have fair comparison with our baseline algorithms, we do not use model personalization in this work.

---

Under review as a conference paper at ICLR 2023
Being designed for fair FL, the aforementioned algorithms usually result in the suppression of well- performing clients, due to the lower weights that the algorithms place on them or due to the equality that is encouraged between clients losses (GiF (.) As consequence, they achieve an overall average performance which is either smaller than or close to that of vanilla FedAvg. This is our motivation for proposing our two new algorithms.
Our inspiration in this paper is a concept in Finance called risk modeling used for portfolio selection. There are two vastly used methodologies for risk modeling: Mean- Vann-Vaianneeeee (MV) (Zhang et al. 2018
Soleimani et al. 2009; Markowitz 1952) and its expansion: Mean-Semi-Variancce (MSV) (Boasson
al.) 2017; Pla- Santamaria & Bravo 2013 Ballestero 2005| [Stuart & Markowitz 1959). which are used for quantifying investment return and investment risk. Motivated by the vast usage of these methodologies and their great success financial planning, we bring the MV and MSV methods to FI, by proposing our Variance Reduction (VRed) and Semi- Variance Reduction rithms, respectively. By conducting extensive experiments on popular vision and language datasets, show that our VRed algorithm achieves performance competitive to existing baseline fair FL algorithms. More importantly, Semi- semi-VRed -Red achieves state-of-the-ar performance in terms both fairness and system overall average performance.
algo-
BACKGROUND
With formal notations, we consider an FL setting with n clients for the task of multi-class classifica- tion. Let x E X C Rº and y E y {l..... C' denote the input data point and its target label, re- spectively. Each client i has its own private data with data distribution P, y). Let h X'x + R be the used predictor function, which parameterized by 0 E S Rd shared among all clients. Also, let é: R x y + R+ be the loss function, which we choose to be the cross entropy loss. Client i minimizes loss function fi) (x..g) [(((x, 8). y)] with minimum value of fr.
There are various fair FL algorithms in the literature, In table in the appendix, we have provided details of the most recent algorithms with their formulations. The existing fair FI. algorithms can be grouped into two main categories:
2.1 ALGORITHMS BASED ON THE GENERALIZED MEAN
This category of algorithms includes FedAvg McMaaan al. 2017 : q-FFL Li al. 2020c>, AFL (Mohri et al. 2019). TERM (Li et al. (2020a). PropFair (Zhang et al. 2022a). It was shown by Zhang et al. (2022a) that this set of existing fair FL algorithms can be unified into a generalized mean framework Kolmogorov 1930), where more attention is paid to the clients with larger losses.
2.2 ALGORITHMS BASED ON ENCOURAGING EQUALITY
The second category of fair FL algorithms, which includes GiFair, is based encouraging equal- ity between clients loss functions. GiF air adds a regularization term to the objective of FedAvg to penalize the discrepancy between clients loss functions (see table 3 in the appendix). In this way, it encourages equality between clients loss functions.
A common feature of all the aforementioned algorithms is their emphasis on the clients with rel- atively larger losses, which usually results in the suppression of the well-performing clients. This might result in the degradation of the overall average performance (measured by the mean test ac- curacy across clients). In the next sections, we will see that Semi-VRed can achieve fairness by regularizing the semi-variance of clients loss functions and improves both faimess and the system overall performance simultancously. In the context of variance regularization. there have been some works the literature: Maurer & Pontil (2099); Namkoong & Duchi (2017) propose regularizing the empirical risk minimization (ERM) by the empirical variance of losses across training samples to balance bias and variance and improve out-of-sample (test) performance and convergence rate. Sim- ilarly. (Shivasaayy & Jebara (2010) propose boosting binary classifiers based on a variance penalty applied to exponential loss. Variance regularization has also been used for distr--disttiuution (do- main) generalization: assuming having access to data from multiple training domains, KKueeer al. (202I) propose penalizing variance of training risks across the domains, as a method of distribution- ally robust optimization, to provide domain generalization.
2

---

Under review as a conference paper at ICLR 2023
3 RISK MODELING METHODS IN FINANCE: Mean- Variance AND Mean-Semi- Seinn-eemi-varinne
Sean-Varaance (MV) and Mean-Semi- Varii-Vaiinnceee (MSV) have been the most popular methods for Mod- eling risks and gains of investment portfolio, which is a first step in financial planning.
Mean-Variance Variance (MV) (Zhagg et al. 2018 Soleimani et al., 2009; Markowitz, 1952). This method treats the return of each security in an investment portfolio as random variable and adopts its pected value and variance to quantify the return and risk of the portfolio, respectively. An investor either minimizes the risk for fixed expected return level maximizes the return for given ceptable risk level. For instance, in the former case, MV results in the following problem:
max
B B[r111 +... Spp
+.....
(1)
0 S1 .... Sn S R. Σn =1 x, 220 0.
Here E and o² denote the expected value and variance operators, respectively. Also, S; and denote the random return from security and the proportion of total wealth invested in security i, respectively. This example has provided basic view of how MV model works. Other closely related measures of risk in the MV model include the standard deviation (σ) and coefficient of variation (o/1E). However, the Vaaan-a modeling of risk is debatable: any uncertain return above the expectation is usually not considered as risk in the common sense, but the MV model does so. This shortcoming is resolved by the Mean-Semi- Variance model.
Mean-Semi- Variance (MSV) (Boasson et al. 2017 Pla-Santamaria & Bravo 2013 Ballestero 2005]
Stuart & Markowitz 1959). Having recognized the importance of the (often) one-side nature risks, MSV model proposed a downside risk measure known as semi-variance, which we denote by o² Unlike variance, it is only concerned with the downside of the return. i.c. only the cases that the return drops below predefined threshold. With this risk modeling method, problem [ changes to the following:
nIx
E|r1S1 +... +.... Sp]
s.t. (2 +.... +zn S R, Σ 1x=1, =1 24 220,
where the operator semi-variance measures the downsides of the return: [2 = [[[[ MSV is a preferable alternative for the MV model as its modeling of the risk more consistent with our perception from an investment risk. Again, the problem above gives a basic understanding of how the MSV model works. More complex variations of MV and MSV models have been developed for complex and unpredictable financial markets (Rigamonti & Lučivjanská 2022 Zhang et al. 2018 Ballestero 2005).
MV AND MSV MODELS FOR FAIR FL
In this section, we propose two fair FL algorithms based on the and MSV models. We use the two models to quantify the inequality between clients performances. Inspired by ZZang et al. (2022a), we take a simple approach and define (0) M f0) as the utility of client i, where M can be treated as utility baseline. The smaller the loss function of a client becomes, the larger its utility becomes: the utility of a client can be used to roughly represent the test accuracy of the shared model, parameterized by 0, on its local data. With this definition, propose to model the inequality between clients by the variance and serianeriance of their utilities, resulting in the VRed and Semi -VRed algorithm, respectively.
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1: VRed and Semi-VRed
Input: global epoch T, client number n, loss function fi. number of samples ny for client i,, number of total samples N, initial global model Op. local step number K; for client i,
learning rate ?)
Let P; N for i E {0, .n....nn111
for t = 0, 7 do
randomly select S [n]
8.0) -, for i ESt, N Eies, R
for in S, do // in parallel
starting from (00) take K; local SGD steps on ((( with learning rate to find 02
compute A (0) 0 (
compute T(0,)) E, (()( and T -EPAA if v/ed then
(0) + 28 ((((())) J( - -x
compute A, = E, 4:4
10
11
else if Semi - then
- compute A, E; 1 + ((f())( =(0 -X
(0)
12
13
update l++1 = 0, - A
Output: global model fr
4.1
THE VRED ALGORITIM
VRed models the inequality between clients utilities by their variance and aims to minimize the following objective function:
min F(0) = =(((()))) (O))Ell Σ (i + & pi (((0) - Σ Ps ps (0)
0
2
= -EI11(++B +3 8 f(00) - Epst(0))
This objective, in addition to minimizing the vanilla FedAvg mean loss, reduces the variance of clients utilities. Let derive the VRed federated learning algorithm. By taking the gradient of equation and multiplying it by the step size we have:
17 (V)( Σ (() + 28 Σ Pe (.(())
E (pff 3
EPPVS (4)
This equation immediately leads an FL algorithm, by replacing the gradient fi with the pseudo-gradien (i.e., the opposite of the local update), denoted by (
nVF(()) = EPA +28
E PP:(((0 ((0) -A.0-
(5)
where F(0) Σ, P.)(0) and A !.P. The corresponding algorithm is included in algorithm There is parameter 3 which tunes the effect of the regularization term, which needs to get tuned for better performance. Note that this is new aggregation rule: instead of simply averaging the local models, it has an additional second term, which relates to the variance of clients losses. If all clients are identical, this term would vanish.
4.1.1 AN INTERPRETATION OF VRED
With the definition of utilities in the previous section (u, M f())). the objective function of VRed algorithm (cquation 3 is aimed to penalize the variance of clients utilities. One poten- tial drawback of this is that it might result in the suppression of well-performing clients (the ones
4

---

Under review as a conference paper at ICLR 2023
with small losses) for reducing the variance, which is the same drawback that GiFair Yue al. 2021) had, Hence, the final model overall performance averaged across clients might get sacrificed for achieving fairness. In fact, GiFair minimizes upper bound of VRed objective function: suming p; = n (i 1,..., n), i.e., all clients have the same number of data points, we have the following upper bound on vRed objective function (see equation 18 in the appendix for derivation):
E f((0) - Σ
-
2 5(0) S
Σ
f++
2 n2
Σ jæز
f((0) 11(0) 2
(6)
where the right hand side is the same as GiFair objective function (except the power 2 used for measuring the pairwise distances between clients losses, see table in the appendix). Therefore, GiFair r in fact minimizes upper bound of VRed's objective function. This might be the reason explaining why our VRed usually outperforms GiFair in terms of fairness our experiments.
weighted sum of clients loss functions, i.e. F()) == Σx= (f), where (0) used by client as surrogate of the global objective and is optimized using the client local data. Also, the weight w; represents the importance of client i loss function the global objective function F(0). For example, FedAvg simply uses (+) = (0) and w; = Ps (p: = Bi see algorithm 1) and q-FFL uses h2( = go+1 (0) and w; P.- A direct consequence of the above summation form for F(0) is:
In typical FL settings, the global objective function can be written
VF(0) Σ (h,
Again, the weight wi represents the importance of the client model updates. In lemma D we show that the gradient of the global objective of VRed in equation 3 can be written in the form of equation 7 For simplicity and easier interpretation, we assume ps clients have the same number of data points.
I,..., n), i.e. all
Lemma 1. For any model parameter 0, the gradient of the global objective F(0) defined in equa- tion 3 can be expressed as
VF(0) = Σ w (())) w,(0) = 23(f.(0)- F(t) = 5())
(8)
n
The proof is deferred to A in the appendix. Lemma[ that, unlike FedAvg that would assign w; , 1,.... n all clients, VRed assigns relatively larger weight (w;) to clients with larger loss functions, and dynamically updates the weights at each communication round. We will provide an interpretation of this finding about VRed the next sections. Importantly, based on equation 8 in order for all clients to get assigned positive weight, the parameter 3 needs to satisfy
the following inequalities: 0 < B < Smaz (0) A
(f:()))
4.2 THE SEMI-VRED ALGORITHM
Inspired by the discussion on the superiority MSV over MV in $ $ for risk modeling, we propose an extension of VRed. Consider the following objective function instead of equation
(1(0))
min P(0) = E(A (02 Pp.h(0) & [100) - E1EEE((00
0
where o2 denotes the semi-variance of clients utilities. This objective, in addition to minimizing the mean loss, reduces the semi-variance of clients losses, meaning that only those clients that have relatively small utilities (0) (or equivalently large losses f()) contribute to the semi-variance regularization term in eq.
5

---

Under review as a conference paper at ICLR 2023
Similar to what we did for VRed, if we take the gradient of equation 9
have:
VV - P.
23 Σ (1.(0) (400 -
(10)
where A0 is the pseudo-grant -raddiett (i.e., the opposite of the local update) of user i. The corresponding Again, we have a tunable parameter 3 which sets the effect of the regularization term and needs get tuned for better performance.
algorithm is included in algorithm| [
4.3
CAN WE INTERPRET WHAT SEMI-VRED DOES?
4.3.1
OPTIMIZATION ASPECT
We will show in lemma 2 that, in contrast to VRed (and GiFair) and thanks to its more efficient formulation, Semi VRed does not suppress the well-performing clients to help the worst-off ones. Similar to lemmaly 7 assume p. (i. for simplicity and casier interpretation.
Lemma 2. In each communication round between the clients and the server, let > denote the set of clients whose local loss function greater than the average loss function f(0). For any model parameter 0, the gradient of the global objective F(0) defined in equation 9 can be expressed as
VF Σ (O)
(11)
where:
23( -(0)) 23 JEEe (fj(0) - [(0))
f(0) En (.)
if E>C
n
n
n²
n
1
23 23 JE> (J T(O))
iff
12
n
(12)
Similar to VRed, there an upper-bound for B to ensure positive weights for all clients in equa-
tion 12 0 < 3 < S
Pemii-Vee vRea
(
First, both of the algorithmss pay more attention to worst-off clients by assigning larger weights to their gradients. However, Semi -VRed assigns relatively larger weights to the well-performing clients. Also, for
Remark 1. Interesting points be observed by comparing lemmal 7 and lemma 2
VRed, w.( = 1. + 2((1)(0)-T(0)) so the better a client performs, the more it is suppressed by the algorithm. contrast Demi- assigns weights to well nell-performing clients depending on how bad the worst-off clients perform compared to the average performance (equation 12). As the performance of worst-off clients improves gradually, the algorithm also lets the well-performing ones further improvement, instead of strictly suppressing them like vRed.
4.3.2 HANDLING EXTREME LABEL SHIFTS
We now provide another interesting interpretation of Semi -VRed, related to data heterogeneity in FL. order for an easier interpretability, we assume P((x, v) (aly)) This means that the class conditional distribution of input æ is identical for all clients. Having made this assumption, we define (0) = Eg>~((riv=/) [,(, 0), as the average loss of predictor on class We have lemma 3 about the objective function of Semi -VRed in equation
P..
Lemma 3. Assuming P. y) (z (z()) P. for i {l...., ,n), for any model parameter 6, Semi -VRed global objective F()) defined in equation 9 can be expressed as
C
F(0) Σ (0)
3
Σ
EPP (P(0)-(0)3(0))
(13)
where P(J) Yon, P(U)) is the marginal distribution class j in the global dataset.

---

Under review as a conference paper at ICLR 2023
P.()) and P(j) show the ratio of class j in the client local dataset and the global dataset, respec- tively. Based on equation 13 Semi-VRes is capable of improving the performance of the predictor h in extreme class imbalance scenarios: consider when a label over-represented in client i's data (i.e. P:( R 1) and under-represented the global data (i.e. P(j) R 0). For a better under- standing of how Semi Semi-VRed does so, example T the appendix.
CONVERGENCE RESULTS: FULL CLIENT PARTICIPATION
In this section, we prove the convergence of our proposed Semi VRed algorithm, when clients fully participate in each round. We make some standard assumptions the objective functions fi. Specifically, we assume the functions are Lipschitz smooth and strongly convex and also their gradients have bounded norm and local variance:
Assumption 1 (smoothness, strong convexity, bounded stochastic gradient and bounded gra- dient variance). Each objective function fo is L-Lipschitz smooth and T T-strongly convex: for any O' E Rd and any i [ml, have [[V V s(("")] S T. 01|| and fa(0)- Σ |011 is convex. Also. for any batch S By of iiid samples from client local data, the following inequalities hold (bounded stochastic gradient and bounded local variance):
[9] Σ
Ve(0, (z. (c. cC²
E S-B3
(a,y)ES
(x,9)s (x,0)) - Vf((o]]/ S
S
Note that, according to algorithm I each client might have a different number (K;) of mini batches of size b, but here assume the same learning rate In order to prove the convergence of assume boundedness and Lipschitzness for the client losses:
and each client takes K; = K local steps. Also all clients use
we also additionally
Assumption boundednes and Lipschitz continuity). For any E [n], 0 0' E Rd and any batch S ~ B of b i.i.d. samples, we have:
0 0s = 1 Σ
(Z.w)es E(0, (x,
v))
M <
2
( - f.66')l S Loll0 A'll
(14)
With the above assumptions, we prove that Semi VRed algorithm converges to the correct solution.
Theorem (Semi -RRed with full participation). Given Assumptions 7 Mand let pi // V
I and 7 = max (8v, K}. Assume the diminishing learning rate T}s 7(1+1) Then Semi Veei with full participation satisfies:
2v
(B
E[F(Or)]
-F
FF
+ 2(L BML 22L -011 -
(15)
( +++7 +7
where F(0) = E,P. (1:(0) + 3 (J(())
- -((1)² and F ming F(0). Also, B
2i2of, + 882 + (LF((0)) + 8(K C)
EXPERIMENTS
In this section, we evaluate our proposed algorithms for training fair models. From the obtained experimental results, we can observe that VRed achieves competitive fairesss performance and Demi- beats almost all the existing algorithms in terms of multiple fairness metrics. Fur- thermore, Semi-VRed achieves the state of the art performance terms of the system overall average performance too.

---

Under review as a conference paper at ICLR 2023
CIFAR-10
CIFAR-100
60
accuracy
worst 10% test sccuracy
20
test accuracy
40
10
FodArg
9.
AFL.
GiFair
TERM
Prop
Vided
Seni VRed
FodAvg
q-FFF
AFL.
TERM
Prop
VRed
VRed
CINIC-IO
StackOverflow
90
40
cest accuracy
80
70
30
60
50
20
Fed.gg
FFL
AFL
GiRai
TERM
PropPui
Vited
Semi- VRed
FedAvg
Q-FFL
APL
GiTair
TERM
Prop
VRted
Figure 1: Average and worst 10% test accuracies. top left: CIFAR-10, top right: CIFAR-100, bot-
tom left: CINIC-10, 10, bottom right: StackOverflow. Due to divergence, results for AFL on CIFAR-10 and StackOverFlow are shown. All subfigures share the same legends and axis labels.
6.1 EXPERIMENTAL SETUP
In this section, we provide some details about the experiments we conducted to evaluate our al- gorithms: the details of the datasets, models and their hyperparameters, and the metrics we evaluate our algorithms. For detailed explanation of the experiments, see $ in the appendix. include:
Datasets We four benchmark datasets existing in the literature. The datasets CIFAR-100 10/100 (Krizhevsky et 2009), CINIC-10 (Darlow et al.) (018)) (task of image classifica- word prediction).
tion) and StackOverflow (The Tensorflow Federated Authors 2019) (task In order to split the data among clients, we use Dirichlet distribution Wang et al. (2019). StackOver- flow has default realistic partition for each client. We follow the same default data distribution.
Train-Tees Test dataset splitting After partitioning the dataset among clients, we split the data of each client into train and sets with ratio for each dataset. Each client uses its test data evaluate the common trained model. For more details of the data splittings, see C the appendix.
Models, optimizers and loss functions For the CIFAR-10/100 and CINIC-10 datasets, we use ResNet- 18 He et al.] (2016). For the language dataset (StackOverflow), we use LSTMs Hochreiter Schmidhuber (1997). In order to optimize the models parameters, We use SGD for minimizing average cross entropy loss. For further details, see i the appendix.
compare our VRed and algorithm existing in the literature including: FedAvg McMahan et al. (2017), AFL Mohri et al. (2019), g C-FFLLL Li al. (2020c) PropF ForFriir Zhang et al. (2022a). TERM ct al. (2020a), GiFair Yue al. 2021 and Ditto
Baseline algorithms
algorithms with various fair
(2021)
Other hyperparameters We implement an FL setting where different clients participate in all com-
munication rounds with local epoch at each round. We use 200 communication rounds for all algorithms on the datasets to ensure their convergence. For CIFAR- 1 and CINIC-10, we parti- tion the data into 50 clients and for language datasets, partition the data into 20 clients.
8

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison between the performance of different algorithms on CIFAR-100. Second col-
umn: the percentage (%) of suffering clients with improved test accuracy. The value in parentheses shows the amount of test accuracy improvement averaged over suffering clients. Third column: the percentage (%) of well-performing clients with degraded test accuracy. The value in parenthe- ses shows the amount of test accuracy improvement averaged over well well-performing clients. Fourth column: the amount of improvement in the overall mean test accuracy
Algorithm
Improved suffering clients Degraded well-performing clients Overall accuracy improvement
Q-FEL
12.08 (+0.69)
54.21 (-0.79)
+0.0440.41
AFL
51.18 (+0,56)
77.25 (-3.50)
-1.22
GiFair
60.55 (+0.86)
68.22 (-2.03)
-0)40
TERM
23.66_5.34 (-1.12)
8..93 (-3.57)
-2,20
PropFair
8.33 (-4.05)
92.41 24.28 (-6.74)
-5.23
VRed
60.50 12.52 (+1.11)
60.62 (-0,94)
+0.21 40.06
Semi-VRed
65.40 (+1.47)
63.17 (-0.42)
+0.64 00.30
Evaluation metrics As we discussed in $4 the ultimate goal of proposing our novel algorithms is to achieve faimesss without compromising the system overall average performance. We measure the overall performance with the mean test accuracy across clients. In order to measure the fairness in the system, fairness in FL e al. 2020a c). In the appendix, we also use other common metrics in the literature for measuring fairness, c.g. the standard deviation of test accuracies (see table ol appendix C).
the worst 10% test accuracies among clients, which is a standard metric for
6.2 COMPARISON OF VRED AND SAMT -VRED WITH OTHER BASELINE ALGORITHMS
From fig- Semi -VRe outperforms almost all the existing baseline algorithms in terms of the fairness in the system. Furthermore, Semi -VRed improves the system overall average performance (mean test accuracy) for three of the datasets results obtained for StackOverflow (see table 6 in $ [ in the appendix for evaluation in terms of various fairness metrics), Semi- -Redd improves both fairness and mean test accuracy by 3% and 2.7%, respectively. Also, we can observe the competitive performance of VRed.
well. For instance, as can be observed from the
6.3 SUPERIORITY OF SEMI- VRED OVER VREE AND THE OTHER BASELINE ALGORITIIMS
As discussed in $ 2 the existing fair FL algorithms usually suppress the well-performing clients in order improve the worst-off clients performance. However, Semi Semi- -Red,, thanks its efficient formulation, tries to avoid this. In order to get better understanding of this, in table [ we have compared different algorithms based on the amount of performance improvement that they provide: after running the simple vanilla FedAvg on CIFAR-100, we divide the existing 50 clients into two sets: suffering clients: those with test accuracies below the FedAvg mean accuracy (22 clients in our experiment) 2. welf-performing clients: those with test accuracies above the FedAvg mean accuracy (28 clients). Then, we run each of the other algorithms and compare their performance improvement with each other. The results clearly delivers two important messages: 1. the existing algorithms either more or less suppress the well-performing clients or cannot improve them, due to the more attention that they pay to the worst-off clients 2. Semi- VRed has the least suppression of well-performing clients 15%.17% with a small average degradation of -0.42), and the highest average improvement of suffering clients (65. 665400% with average accuracy improvement of +1.47), which results in improving both the fairness and the system overall average performance simultaneously.
7 CONCLUSION
In this work, we introduced two novel fair FL algorithms: VRed and Semi-VRed. In order to resolve the drawback of most of the existing fair FL algorithms, which is suppression of well- performing clients, we propose Semi-VRed which uses an efficient method for measuring per- formance inequality in FL system. Our experimental results show that Semi-VRed not only improves the worst-off clients performance, but also improves the system overall average perfor- mance as well. Accordingly, Semi-VRed achieves SoTA performance in terms of both the overall average accuracy and fairness, measured in terms of various common faimess metrics.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Enrique Ballestero. Mlen-semivarianne efficient frontier: A downside risk model for portfolio se- lection. Applied Mathematical Finance, 12:1 15, 2005.
Aharon Bal, Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions optimization problems affected by uncertain probabilities. Advanced Risk & Portfolio Managemenr@) Research Paper Series, 2013.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathemat- 2018a.
ical Programming.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Robust sample average approximation. Math ematical Programming, 171:217-282, 2018b.
Alberto Bietti, Cuen-Yu Wei, Miroslav Dudik, John Langford, and Steven Wu. Personalization improves privacy-aceuracy tradeoffs in federated learning. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learn- ing Research, pp. 1945-1962. PMLR, 17-23 Jul 2022. URL htttss//ppoeeedings.ll...sssss 162/ hietti22a.html
Vigdis Boasson, Emil Bóasson, and Zhaoli Zhou. Portfolio optimization in meca-semivarianee framework. Investment management & financial innovations, 8, 2017.
Hong- You Chen and Wei-Lun Chao. On bridging generic and personalized federated learning for image classification. In International Conference on Learning Representations, 2022. URL/https: pnpemneeieevnettoouunn/ddlllll/d 10Kxn.
Sen Cui, Weishen Pan, Jian Liang, Changshui Zhang, and Fei Wang. Addressing algorithmic dis- parity and performance inconsistency in federated learning. In NeurIPS, 2021.
Luke N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. CINIC-10 is not ImageNet or CIFAR-10, arXiv preprint 1800000555 2018.
Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Distributionally robust federated averaging. ArXiv, 100.21002.1660,0 2020.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In AISTATS, volume 130, pp. 3556-3564, 2021. URL http://prroceedings mlr. press/
1130@gorbunoy2la.hrg
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Zhouyuan Huo, Qian Yang, Bin Gu, Lawrence Carin, and Heng Huang. Faster on-device training using new federated momentum algorithm. arXiv:2002.02090, 2020. URL https://arxiw..rrr/ab/// 2002.02090
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local gd on hetero- geneous data. arXiv: 1eei11999949555 2020. URL http:////aaaii..orgaa/////////// (491
Andrey Kolmogorov. On the notion of mean. Auti della Academia Nazionale dei Lincei, 12(9):388- 391. 1930. URL htt.ss///innk..snggrroo////////e htt.a//e...ommoooo0997777777769 reprinted in "Selected Works I of Andrey Kolmogorov: Mathematics and Mechanics", pp. 144 146, 1991.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images, 2009. Technical report.
10

---

4oxd=4la950472aa8eeeeeeaaaai Under review as a conference paper at ICLR 2023
David Krueger, Ethan Caballero, and Aaron C. Courville. but-of-distrrbuute generalization via risk extrapolation (rex). In JCML, 2021.
Jacobsen, Amy Zhang, Jonathan Binas, Rémi Le Priol,
Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. In 2010 Proceedings IEEE INFOCOM, pp. 1-9, March 2010. doi: 10. (09//NFCO...000..00
ISSN: 0743-166X.
Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith. Tilted empirical risk minimization. In International Conference on Learning Representations, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems, volume 2, pp. 429-4500 2020b. URL http://poceeddngs.lls...ooo/o//p 0aa16663466500110004333484/44444 Papppee Paper.pdf)
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020c.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 6357-6368. PMLR, 2021.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020d. URL
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In ICLR, 2020. htt.l//s//ooooneeeewerrrtomonmnd
Harr Markowitz. Portfolio slection. Journal of Finance, 1952.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample-variance penal- ization. In COLT, 2009.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Ar- cas. Communication-effcccentt learning of deep networks from decentralized data. In AIS- TATS, volume 54, pp. 1273-1282, 2017. URL. http://mooeeddgggniirress//////p 17 mcmahanl7a..dff
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. ICML, volume 97, pp. 4615-4625, 2019. URL http://pwocceddiiiss..mlrsssssss h9.
Hongseok Namkoong and John C. Duchi. Variance-based regularization with convex objectives. J. Mach. Learn. Res., 20:68:1-68::::: 2017.
Jachoon Oh, SangMook Kim, and Se- Young Yun. FedBABU:
Toward enhanced representation for federated image classification. In International Conference on Learning Representations, 2022. URL http:://ooeneeeeeee..////uu/mmla Yfggnnu
Reese Pathak and Martin Wainwright. Fedsplit: An algorithmic framework for fast feder- http://igg..eeeeeees//////pp/p/a
ated optimization. In NeurlPS, 2020. URL Abstract.html
David Pla-Santamaria and Mila Bravo. Portfolio optimization based on downside risk: mean- semivariance efficient frontier from dow jones blue chips. Annals of Operations Research, 205: 189-201, 2013.
Zhe Qu, Xingyu Li, Rui Duan, Yao Liu, Bo Tang, and Zhuo Lu. Generalized federated learning via sharpness aware minimization. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 18250- 18280. PMLR, 17-23 Jul 2022. URL httt:s///poeeddingg.iggrsss/////

---

Under review as a conference paper at ICLR 2023
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečny, Sanjiv Kumar, and H Brendan McMahan. Adaptive Federated Optimization. arXiv:2003.00295, 2020a. URL httplpps//aarx..or//////020.....
Sashank J Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2020b.
Andrea Rigamonti and Katarína Lučivjanská. Mcan-semivariance portfolio optimization using min- imum average partial. Annals of Operations Research, pp. 1-19, 2022.
Zebang Shen, Juan Cerviño, Hamed Hassani, and Alejandro Ribeiro. An agnostic approach to federated learning with class imbalance. In ICLR, 2022.
Pannagadatta Shivaswamy and Tony Jebara. Empirical bernstein boosting, In Yee Whye Teh and Mike Titterington (eds.). Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 733- 740. Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR. UtR//ttt///procceedngns. mir.. press/v9/shiasswmmy h0a.
Hamed Soleimani, Hamid Reza Golmakani, and Mohammad Hossein Salimi. Markowitz- bassed portfolio selection with minimum transaction lots, cardinality constraints and regarding sector capitalization using genetic algorithm. Expert Syst. Appl., 36:5058-5063, 2009.
Alan L. Stuart and Harry M. Markowitz. Portfolio selection: Efficient diversification of investments. Quarterly Journal of Operations Research, 10:253, 1959.
The Tensorflow Federated Authors. Tensorflow federated StackOverflow dataset. 2019. URL
Hongyi Wang, Mikhail Yurochkin, Yuckai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni.
Federated learning with matched averaging. In ICLR, 2020. URL https://penneeviewne///fou
id=BKlugISFDS
Kangkang Wang, Rajiv Mathews, Chloé Kiddon, Hubert Fichner, Françoise Beaufays, and Daniel Ramage. Federated evaluation of on-device personalization. CORR, abs/1910.102255 10252, 2019. URL,
http://arxi..orr///b///111..000
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), pp. 3-19, 2018
Jun ya Gotoh, M. J. Kim, and Andrew E. B. Lim. Robust empirical optimization is almost the same as mean-variance optimization. Mutual Funds, 2018
Xubo Yue, Maher Nouiehed, and Raed Al Kontar. Gifair-ft: An approach for group and individual fairness in federated learning. ArXiv, abs/2108.08 02741, 2021.
Guojun Zhang, Saber Malekmohammadi, Xi Chen, and Yaoliang Yu. Equality is not equity: Propor- tional fairness in federated learning. CoRR, abs/2202.01666, 2022a. URL https///arxiv.or//abs/ 2202.01666
Michael Zhang, Karan Sapra, S. Fidler, Serena Yeung, and Jose M. Alvarez, Personalized federated learning with first order model optimization. In ICLR, 2021. URL hatps://peeneviee.ne//oommn
id=ehlq.(k9cw
Xu Zhang, Yinchuan Li, Wenpeng Li, Kaiyang Guo, and Yunfeng Shao. Personalized federated learning via variational Bayesian inference. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Con- ference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 06293-263100 PMLR, 17-23 Jul 2022b. URL https://proceedings.. mww.s 162//hang22o. htmll
Yuanyuan Zhang, Xiang Li, and Sini Guo. Portfolio selection problems with markowitz's mean-varianee framework: a review of literature. Fuzzy Optimization and Decision Making, 17:125-155 2018.
12

---

Under review as a conference paper at ICLR 2023
Appendix for Semi-Varianee Reduction for Fair Federated Learning
A PROOFS
Lemma 1. For any model parameter 0, the gradient of the global objective F(0) defined in equa- tion can be expressed
VP(0) = Σ wi (i)V(((()),, wi( = 23(f((0)-((0) f(0) E(0(
(8)
Proof. From equation and with p: = n. we have:
ZVF(()) = Σ VI(00) 23 Σ [1:10) ((((0))(00)) )
= Σ Vi((0) + Σ [fF(C) - -(() V.i(0) (F:00- - ((()) VT
Σ (1+22 - I(O1)) V.:(0) - 23 Σ (F(0) - (()0)))))))T1)))
V7
(1+228(f110) - -(00) F(0)))VA(()) VF((0)
(16)
Hence,
+ 23(f((0) - T(O)) v.((0)
VF(0)
(17)
Derivation of equation
6
E5+ B Σ
[1) 550 (5(
ER+B Σ
n --1
8i(0)
1
Σ [5(0)
S#1
3 Σ
(S((0) 15(0)) 2
Σ f +
Σ
n²
$$1
Σ fr
ΣΣ
f((0) 1)
n
j#i
28
Σ fr + n
Σ
5((0) - 15(0)
(18)
3#1
Lemma 2. In each communication round between the clients and the server, let > denote the of clients whose local loss function is greater than the average loss function f()). For any model parameter 0, the gradient of the global objective F()) defined equation 9 can be expressed as
VF(0)= Σ (O)
(11)
where:
13

---

Under review as a conference paper at ICLR 2023
1 -
28 ( -(O))
F(0) = (10) n
n²
if E>C
(0) =
1 23 ΣjE>e (J,(0) ((0)
ifi
n²
(12)
Proof. From equation 9 and with p; 4. we have:
VVF()) = Σ (((00) + 23
Σ
-V1(0)- - v/(0)]
iE>C
Σ (V(()++2 Σ
VS((0) (110)- VT(}]
iE>c
= Σ VA(()) + Σ
(
(+23((1(0) - (())) (I((0) - 2/ Σ
(A(0) - [ -T(0) VT(0)
KE
iE>C
(19)
The last term in the above equation can be written as:
Σ (F.10) - (((0) VF(0)
23
(20)
iE>c
23
Σ fi(0)) x 12 [V1(()) + (E x (V)(()))
n
iE>c
iESC
23
Σ fi(0) - ((0)))(()) (Evs(0)
n
iE>c
Hence,
mFF = Σ
1 + (3( [(0))
23
Σ [1(0) T(0)) VS((0)
(21)
iE>c
JEPC
+ Σ
23
Σ 1 - (.((0)
ig>0
JECC
Therefore,
+ 23( - f(0)) - 20 (() - -(00) f.(())
VF(0)- = Σ
(22)
1E>C
28 7
Ejese f1(0- -(0)) V.((0)
n
iE>
Lemma 3. Assuming P(x)) -()) for i (1....,n)) n), for any model P(xly)
parameter 6, Semi -VRed global objective F(0) defined in equation 9 can be expressed as
C
F(0) = (O), 3
( -
(13)
J=1
1=1
3=1
where P(J) Ynn, P(U)) is the marginal distribution class j in the global dataset.
14

---

Under review as a conference paper at ICLR 2023
Proof. From equation and with Pt n. we have:
I(0)
Σ
"
f((0)
1
Beass 0).
n
n2
==1
1
pi(i) x ((M
11
==1
Σ
ps P;(i)e (
11
1=1
Di -i po(i)
Σ
ye (0)
Σ p()),(0))
(23)
where p()
pi(1 is the ratio of data points with label j the global dataset. Similarly, we
have:
f((0) = Σ (O)
(24)
1=1
By plugging in the above equivalences for (:( and [(0) into equation 9 we get to equation 13
Due to the similarity of Semi VRed's objective function to that of FedAvg, we build its conver- gence proof on top of the convergence proof for FedAvg in Li al. (022d)) We refer the reader to the work for the detailed proof.
We now prove the convergence of our Semi-VRes algorithm.
Theorem (Semi -Red with full participation). Given Assumptions
and 2 let p; N v
L and ς = max 8v, K}. Assume the diminishing learning rate T). -(7+1)- Then Semi- -RRe
with participation satisfies:
B[F(OT)] F" 3
2v
(B
+ BML - - -011))
(15)
(7 + T)
where F(0) = E,p,(1((0) + 3
- (fi(0)-((0)} and F = ming F(0). Also, B
C.=1P:1200 + +88MM33) + 6LF(0)) + 8(K - C)
Proof. We first rewrite a simplified version of the Semi -Redd objective function (equation 9b in the following.
F(0) P [x((10++((() ( -w)
(25)
where G,( fi(0) + 3 ()) - 2 and also, μ = E.pof is fixed during clients local com- putations. In the beginning of each communication round, we update y for the next round of local computations, other words:
M++1 P.f((0
(26)
With these notations, it suffices to find the constants in Assumption for G,(0).
15

---

Under review as a conference paper at ICLR 2023
Smoothness
We have:
f((0) G( - 1:0) -4) = (1:(0)+ B(F(0) n2) if [((0) > P
if S f((0) k
(27)
In the first case, G; is smooth with the same smoothness parameter of (0):
(0) VG, 8'll
(28)
In the second case, we have:
GG,((0) fi(0( + (000000))))3000 +V +(
M V f(0) + V+(())1(())
< 1 2
(29)
where in the last line, we used Assumption 2 and the following:
[VA(OVV1))) 1ap sup sup (VI:(0)VSA(0) u;
|w]|=1 |v||=1
= sup sup (VI:(0) u) V [V S 1g.
(30)
|w||=1 ||||=1
where in the second line we used Cauchy-Schwarz inequality and Assumption Hence, from eq. (28) and eq. (29 we conclude that G,(0) is Lipschitz smooth:
VV. VG, S (T. 3MT 2 0'1-
(31)
Strong Convexity From, eq. 27
we have:
if0 f((0) S v2 f((0) + -) ( if f10) > P
V ((0)
VoG,())
(32)
From the above derivation of (²G,(0) and that /:(0) is 7-strongly convex, we can immediately conclude that G,(0) is also --strongly convex.
local gradient variance constants We have:
For the local variance term, we define pp() = + 3(t 1
- V
(0)l
- vess [.) V(s((0) + 281( - (+)) ( - p) (es(
+ ([V
-1) - 4) v.())
[/V V(s(O)I + (M + (Ms(
& (|V Vés(0)] + +,3MC
(33)
where in line four, we used Assumption and in line five, we used By taking the square both sides and the expectation over 5 ~ B we get:
[V Ves(0)) +2M())
Es-ot (Q) (0)) ESNEy
Egwsy
2l(V
V
=227, +88PMM22
20
(34)
16

---

Under review as a conference paper at ICLR 2023
In the third line, used (a (a+bb² 6)2 2(a² b²). We also used Assumption | in the same line.
B EXAMPLES
We borrow the following example on class imbalance in from Shen al. (2022) to provide better understanding of lemma 3 The following example shows an extreme class imbalance, which Semi -VRe can handle efficiently.
Let be the uniform distribution over the existing C' classes. Also, let 8e be the Dirac distribution of class Now, without loss generality, lets assume that C (binary classification problem). For the n existing clients, we have:
Example 1.
[nn + (1 a')i ifi=1
pi(y)=
(35)
au + (1 a0)2 ifi n
Accordingly, we have:
if
2
(1(
(36)
a
i f2....,
2
ifi
(2(
2
(37)
1
a
if E (2.
2
Therefore,
(1 a ([(())) (2( =i==
2
1:(0)
(38)
(1) +1 (1- " (2( if E (2.....n]
a
2
Hence,
a 1 ( + E1 (0) + ( + (1 a 1) F2(
I(0)
(39)
2 n
7
Clearly, that if O and n is large, then (0), which is the loss over the minority data
will have small weight, which leads E, (0) being larger than (0) and poor performance the minority class 1. Now, if we rewrite the Semi VRed objective function (equation 9. we have:
a 111)2(()) ())(())++ a (n 1) (0)
8(n - 1)) a)²
F(0) 2 n
(Z))
n
n2
(40)
For a = 0:
F(0) ~ [2) (1) Z2(0))
(41)
which improves Zz) thanks to its regularization term. Hence, the performance of client and consequently, fairness in the system will improve.
17

---

Under review as a conference paper at ICLR 2023
C EXPERIMENTAL SETUP
In this section, we provide more experimental details that are deferred from the main paper. For each experiment, we report the average result obtained from three runs with different random seeds. For our experiments, we used internal GPU server with six NVIDIA Tesla P100. The experiments last about weeks in total.
C.I DATASETS AND MODELS
In this subsection, we describe the datasets we use in our experiments. For all the datasets we use batch size of 64,
CIFAR-10/100 (Krizhevsky et al. 2009) are two image classification datasets vastly used in the literature as benchmark datasets. Each of these datasests contains 50000 sample images with 10/100 balanced classes for CIFAR-10 and CIFAR- 100, respectively. We use Dirichlet allocation (Wang al. 2019 to distribute the data among 50 clients with label shift: we split the set of samples from class k (Sp) to n. subsets (Sy S J Sk.2 U... U Sk,n), where is the number of clients and Sk.j corresponds to the client j. We do the split based on Dirichlet distribution with parameter 0.05 (Dir (0. 05)). When the split is done for all classes, we gather the samples corresponding to each client from different classes: assuming there are classes in total S1,j S2.5 U... Sc., is the data allocated to the client j. Having allocated the data of each client, we split them into train and test set for each client. The train-test split ratio is 50-50 and 60-40 for CIFAR- 10 and CIFAR- 100,, respectively.
CINIC-10 (Darlow et al. 2018 is another benchmark vision dataset that we use in our experiments. There are total of 270,000 sample images, which distribute with label shift between 50 clients based on Di (0. 5) distribution Wang et al. 2019). We then randomly split the data of each client into train and test sets with split ratio 50-50.
StackOverflow (The Tensorflow Federated Authors 2019) is a language dataset consisting of Shakespeare dialogues for the task of next word prediction. There is a natural heterogeneous par- tition of the dataset and we treat each speaking role as client. We filter out the clients (speaking roles) with less than 10,000 samples from the original dataset and randomly select 20 clients from the remaining. Finally, we split the data of each client into train and test sets with ratio of 50-50.
Table 2 provides summary of the datasets we used and the models used for each of them.
Table 2: Details of the experiments and the datasets. ResNet-18: residual neural network (He et al, 2016). GN: Group Normalization (Wu & He 20188: RNN: Recurrent Neural Network; LSTM: Long Short-Term Memory layer; FC: fully connected layer.
Dataset
Train samples Test samples Partition method clients
Model
CIFAR-I0
24959
25041
Dir (0.05)
50
ResNet-18 GN
CIFAR-100 100
39445
10555
(1.
50
ResNet-18 18 + GN
CINIC-10
134713
134966
(0.5)
50
ResNet-18 + GN
SterkOverf
109671
109621
realistic partition
20
RNN (1 III.TM FC)
C.2 AL.GORITHMS AND THEIR HYPERPAR AMMTERS
We use most recent fair FI. algorithms existing in the literature as our baseline algorithms, including: FedAvg (McMahan et al.] 2017), FFFFI. (Li et al. 2020c). AFL. (Mohri et al., 2019). P PropFa i Zhang et al. 2022a), TERM (Li et al. (020a),, GiFair Yuue et al. 2222). For each pair of dataset and algorithm, we find the best learning rate based reported the learning rate grid we use for each dataset:
grid search. In the following, we have
CIFAR-10: (1e-3, 2e-3, 5e-3, 1e-2, 2e-2, 5e-2];
CIF:R-100; (1e-3, 2e-3, 5e-3, 1e-2, 2e-2, 5e-2];
CINIC-10: (1e-3, 2e-3, 5e-3, 1e-2, 2e-2, Se-2];
18

---

Under review as a conference paper at ICLR 2023
Table 3: Details of the existing fairfl algorithms, fa is the loss function of the client i.
FL algorithm
Objective
Reference
FedAvg
Ei
McMahan et al. (2017
AFL
max; Sa
Mohri et al.
(2019)
q-FFL
Li et al.
2020c
TERM
Σn ean
Li ct al.
2020al
PropFair
Σ, log(M f()
Zhang et al.
2022a)
GiFair
Σ. X Eits 1/4 -51
Yue et al.
2021)
VRed
E (1:(0)
2
this work
Semi-VRed
E (110) - ΣΣ
this work
StackOverflow: (1e-2, 5e-2, 1e-1, 5e-1, 13.
The best learning rate used for each (dataset, algorithm) pair is reported in Table
Table 4: The best learning rates used for training each algorithm on different datasets.
Datasets
FedAvg
q-FFL AFL
TERM PropFair GiFair VRed Semi-VRes
CIFAR-10
5e-3
5e-3 5e-3 1e-2
1e-2
5e-3
5e-3
5e-3
CIFAR-100
2e-3
2e-3
5e-3 1e-2
1e-2
5e-3
5e-3
5e-3
CINIC-10
1e-2
5e-3
1e-2 1e-2
2e-2
2e-2
be-3
5e-3
StackOverflow
2e-1
5e-2 5e-2 2e-1
5e-1
2e-1
5e-1
5e-1
We now explain the algorithms we use and how we tune their hyperparameters. We adapt TERM with only client-level fairness (a > 0) and sample-level fairness (r = 0). We tune the hyperpa- rameter a for each dataset based on a grid search in the grid (0.01, 0.1, 0.5, 1}. We have reported the best value of for each dataset in Table 5 For AFL, there are two hyperparameters: The and 7 We tune the learning rate The from the corresponding grid and choose the default value 7 = 0.1. For q-FFL, we use the q-FedAvg algorithm (Li al., 2020c). We also tune the hyperparameter q from the grid {0.01, 0.1, 1}. We find that for all the used datasets, q = 0.1 has the best peformance (as reported in Table (5). We also tried larger values out of the grid and they often lead divergence of the q-FFI. algorithm. We adopt the Global GiFair model (Yue et al., 2021). which results in single global model. order to have client-level fairness, we treat each client as a group of size 1. For tuning the regularization weight of GiFair (A), we follow (Yue et al.) (02T). As stated in the paper, there is an upper-bound for À (see $3 in the paper). For our experiments, the upper-bound is A S min; { ]. where w; is the ratio of total samples allocated to the client and n is the number of clients. We try four different values in the interval and choose the best one. When the number of clients large, this upper-bound is small, and for all of our datasets, this upper-bound was the best value, reported in Ta We tune M for the PropFair algorithm based on a grid search in (2,3, 3, 4, 5]. Finally, for our VRed and Semi-VRed algorithms, we tune the regularization weight / based grid search on the grid (0.01, 0.05, 0.1, 0.2, 0.5, 1}. Larger values of , often resulted in the divergence of the algorithms. We have reported the best value of all of the hyperparameters for each dataset in T
C.3 DETAILED RESULTS
In T we report detailed results obtained from the algorithms we study in this work. We use default batch size 64 for all the experiments. The statistics we report include: 1. the average test accuracy across clients (overall average performance) 2. the standard deviation of test accuracies across clients 3. the lowest (worst) test accuracy among clients 4. the lowest 10% test accuracies 5. the lowest 20% test accuracies 6. the highest 10% test accuracies. For each experiment, we report the average result obtained from three runs with different random seeds. As can be observed. our proposed algorithms VRed and Semi -VRed consistently beat almost all the baseline algorithms
19

---

Under review as a conference paper at ICLR 2023
Table The best values of hyperparameters used for different datasets, chosen based on grid search.
Algorithm
CIFAR-10
CIFAR-100
CINIC-10 StackOverflow
q-FFLy
le-1
le-1
1e-1
le-1
TERM a
1e-2
5e-1
5e-1
5e-1
GiFair
60-5
2.60-4
5e-5
2. 2.40-3
PropFair
5
VRed /
5e-1
le-1
2e-1
le-1
Semi-VRed 3
5e-1
1e-2
2e-1
2e-1
CIFAR-10
CIFAR-100
worst 20% test accuracy
14
30
test accuracy
12
20
8
10
FedAvg
g-FFL
AFL
GiFair
TERM
PropFair
VRed
Semi Semi-VRes VRed
FedAvg
g-FFL
AFL
GiFair
TERM
PropFair
VRed
Semi- VRed
CINIC-10
StackOverflow
64
35
test accuracy
62
30
60
58
25
56
FedAvg
g-FFL
AFL
GiFair
TERM
PropFair
VRed
Semi- Semi-V VRed
FedAvg
g-FHL
AFL
GiFair
TERM
PropFair
VRed
Semi- VRed
Figure 2: Worst 20% test accuracies for different algorithms. top left: CIFAR-10, top right: CIFAR-
100, bottom left: CINIC-10, bottom right: StackOverflow. Due to divergence, results for AFL on CIFAR-ID and StackOverFlow are not shown. All subfigures share the same legends and axis labels.
across different datasets in terms of various fairness metrics. Also, Semi Semi-VRed can improve the overall average performance (mean test accuracy) for three of the datsets well.
Following Figure [ we have compared our proposed algorithms with the baseline algorithms in terms of their worst 20% test accuracies as well and the visualized results shown in Figure 2
20

---

Under review as a conference paper at ICLR 2023
Table 6: Comparison among federated learning algorithms on CIFAR-IO, CIFAR-100, CINIC-10 and StackOverflow datasets with test accuracies (%) from clients. All algorithms are fine-tuned. Mean: the average test accuracy across all clients; Std: standard deviation of clients test accuracies;
Worst: the worst test accuracy among clients; Worst (10/20%): the worst 10/20% test accuracies of clients; Best (10%): the best 10% test accuracies of clients.
Dataset
Algorithm
Mean
Std
Worst
Worst (10%)
Worst (20%)
Best (10%)
FedAvg. Ditto 43.45 14.33
9.35
18.86
20.77=0.70
68.97 +0.81 72.3 +2.88
q-FFL
45.4640.74
14.31 #2.03
18.71 #3.36
21.23
25,95
CIFAR-10
AFL
GiFair
45.05 12.93:20.41
16,79
16.79=3.55
22.65
26.52.20.76
65. 65.62:22.59
TERM
45.61 12.24
13.80
24.89
29.34
68.65
PropFair
36.95
15.1641.33
1.14
12.49:0.25
16.66
66.04:44.24
VRed
44.43
13.05
18.61
13.12
24.28
12.22
27. 27.46 1.58
69.31 1:3.48
Semi-VRed
45.47+0.10
12.58
19.04=a.73
27.08
30.34
72.50
FedAvg, Ditto
20.20
6.50
10.36
11.07
12.49
33.88
CIFAR- 100
q-FFI.
20.25
6.30
9.6640.33
11.09
12.52
33.96
AFL
18.98 4.937
9..1
11.31
12.72-0.21
1.76
GiFair
19.31 5.74
9.35
11.19
12.59
32.30
TERM
18.00
6,05
8.8640.50
10.0220.44
11.04_0.51
31.58
PropFair
14.97
6.44
5,40+1.25
7.00+1.11
8.06
28.89 40.91
VRed 20.42
6,08
9.43
11.21
12,81 =0.88
33.59
-Red
20.85
6,26
9.12+1.47
11.8640.74
13.46
34.57 +1.20
FedAvg, Ditto
86.2610.03
15.20
50.48
56.87
62.78
100.0
q-FFI.
86.63+0.04
14.88
51.57=0.82
57.77=0.36
63.62=0.18
100,0
CINIC-10
AFL
86.45 15.10
51.57-0.46
57.58
63,04 28
100.0
GiFair
86.28
15.20
49.66-1.21
40.29
62.74
100.0=0.00
TERM
86.3410.04
15.12
49.90
57.21
62.98 00..:0..44
100,0
PropFair
86.01 10.17
15.34
49.97
56.5340.65
62.27
99.99
VRed
85.79
51.57 15.02 20.50
57.66
62.75
99.98 0.001
Semi-VRed
85.83
14.9540.07
51.59 =0.9
58.00
62.70
99. 99.9640.01
FodAvg, Ditto
40.34 6.98 40.06
25 20.11
27.12
30.35 1.35+a..m
49.70 49.70
StackOverflow
q-FFL
7.
22.54
24.12++1.00
27. 27.14
47.06
AFL
TERM
40.34
6.96
25.5
27.12:20.20
30.41.0.12
49.76
GiFair
40.34.0.04
6.97 10.03
20.11
27.10
30.34
49.71
PropFair
41.7610.01
6.80
27.30
28.75
32.14
50.76.0.08
VRed 42.90
29.08 6.64
0..9
30.39 10.05
33.55
51.66.10.03
Semi-VRed
42.90
6.60
29.10
30.3420.09
35.55
51.70
C.4 RELATION BETWEEN VRED AND ROBUST OPTIMIZATION
Empirical optimization is usually used as a data-driven approach for tuning models for decision making, where expected loss is minimized based on some available train data. The trained model then used for prediction tasks on some test data. However, if the empirical distribution of the train data is substantially different from that of test data, our confidence for doing prediction on the test data with the trained model diminishes. Robust empirical optimization has been used to address this problem (Bertsimas et al., [2018b]a a Ben-Tal al. 2013). The work in (ya Gotoh et al. 2018) formulated a distributionally robust optimization (DRO) problem based on a minimax problem, where model is trained on the given train data against the worst distribution shifts between the train and test data:
1 min max Ble.so-ll 0), Ho(Q + Q
(42)
21

---

Under review as a conference paper at ICLR 2023
where P,, and Q are the train data empirical distribution and the test data distribution. The above problem optimizes against the "worst-case" test distribution Q The deviation of the distribution Q from Ir, is penalized in the regularization term (Q where Ha is a divergence measure between two distributions. The solution this optimization problem is a model which is robust against distribution shifts between the train and test data. It was shown in (ya Gotoh et al. 20188) [see Propositions 3.1 and 3.2] that the above DRO problem equivalent a mean-variance problem, where the empirical average loss on train set is regularized with sample variance of the loss:
min max E (Flas))ll((((e 0), v)] x
min E Beaweee ((h(2,0).v) + (1) B Bleweee e(h(z,)), 0),9) - (a (e(h(z,)) 0), v)]
(43)
This means that variance regularization is equivalent to DRO and can improve out-of-sample (test) performance. Maurer & Pontil (2009): Nammooog & Duchi (017) propose regularizing the empiri- cal risk minimization (ERM) by the empirical variance of losses across training samples to balance bias and variance and improve out-of-sample (test) performance and convergence rate. Similarly, Shivaswamy & Jebara (2000) propose boosting binary classifiers based variance penalty ap- plied to exponential loss.
DRO is also effective approach to deal with imbalanced and non-iid data. Unlike the above sample-wise variance regularization works, the work (Krueger et al. 2021) assuming having access data from multiple training domains proposes penalizing variance of training risks across the domains as a method of distributionally robust optimization to provide out-of-distribution (domain) generalization. The first work propopsing DRO in setting (Mohri et al., 2019), where they minimize the maximum combination of clients local losses to address fairness in FL:
min max f(()).
(44)
Also, the work in (Deng et al. 2020 proposea distributionally robust by minimizing the worst combination of clients local losses via periodic averaging and adaptive sampling:
min max # AEA
xx((O))
(45)
E = 1}. In contrast, our proposed VRed penalizes the variance of losses across clients for improving fairness (performance consistency) in FL settings with high data heterogeneity:
where À A = {
a 2
n
x. + Σ > f((0) Σ {111 J=1
min
(46)
where A; = N is the sample size of client and is fixed. The relation between robust optimiza- tion and variance regularization in non-F'L settings (eq. (43) encourages us to interpret VRed as an equivalent form of DRO. Hence, although the variance regularization used in VRed connects it non-trivially to the previous works AFL (Mohri et al. 2019) and DRFA (Deng et al. 2020) through DRO, it does not use minmax objective function with potential convergence problems. As have reported our experiments, AFL fails to converge in settings with high data heterogeneity. Similarly, the authors of (Deng al. 2020) have evaluated the DRFA algorithm only on Logistic Regression model, which is a convex problem. Furthermore, as reported our results (and also re- ported in (Deng et al. 2020 fig. 3) AFL, thanks to its DRO formulation, can improve the fairness
22

---

Under review as a conference paper at ICLR 2023
(performance consistency) in the system. However, it clearly degrades the overall average perfor- mance. Similarly, DRFA (as reported in fig. 3 of (Deng et al. 20200) can improve the system fairness keeping the same level of global accuracy FedAvg. This our motivation for proposing Semi -VRdd algorithm by solving the following problem instead of the previous DRO-based algo- rithms:
2
" min A.(()) + Σ A 8:(0) Σ x5
(47)
where A; = 24 is the sample size of client i and is fixed. We have shown by lemma 2 and lemma N. and also example that our Semi-VRes has smarter and more efficient formulation for achieving
fairness in FL systems, which results in improvement of faimeess without degrading the system overall performance.
23


Reviews:
[{"review_id": "qy1NP0fwdT", "reviewer": "Reviewer_uqhW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes two new fair federated learning (FL) algorithms, Variance Reduction (VRed) and Semi-Variance Reduction (Semi-VRed), which are inspired by two well-known risk modeling methods in Finance. VRed encourages equality between clients loss functions by penalizing their variance. In addition, Semi-VRed penalizes the discrepancy of only the worst-off clients loss functions from the average loss. Through extensive experiments on multiple vision and language datasets, it is shown that Semi-VRed achieves SoTA performance in scenarios with highly heterogeneous data distributions and improves both fairness and system overall average performance.", "summary_of_the_review": "The proposed algorithm is easy to implement and effective based on the experiments provided in the paper. However, there is still room for improving the theoretical guarantee in section 5.", "strength_and_weaknesses": "Strength:\nThe proposed algorithm has a very intuitive justification, i.e., improving the overall performance without sacrificing the utilities of well-performing clients by penalizing the discrepancy of\nonly the worst-off client’s loss functions from the average loss. The connection between the proposed algorithms and risk modeling methods in Finance is also interesting. The experimental results also validate the proposed algorithm. \n\nWeaknesses:\nThe convergence result in Theorem1 is really hard to digest. It only provides an upper bound for the minimum expected gradient norm, and the second term will not converge to zero as T increases. It cannot show that the proposed algorithm will converge, and it is purely a bound for empirical risk during the optimization process instead of a bound of population risk or generalization error, which is not that informative in practice.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ljYuhO0DAo", "reviewer": "Reviewer_p3GJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper aims to guarantee the performance fairness among different clients in federated learning, while protecting the overall average performance from being sacrificed. The authors propose two algorithms based on variance reduction (in terms of all clients) and semi-variance reduction (in terms of the worst-off clients), respectively. Experimental results show that the proposed method can achieve SOTA performance.", "summary_of_the_review": "This paper investigates a well-motivated problem, and the experimental results show the effectiveness of the proposed method.\n\nHowever, I have some concerns about the technically soundness of the proposed methods. A deep discussion is expected.\n", "strength_and_weaknesses": "Strength:\n1) This paper is well-motivated. Client-level performance fairness is an important topic in federated learning. Most of existing studies improve the fairness with the scarification of overall performance, while this paper focuses on both fairness and overall performance.\n2) This paper is well-organized and the presentation is clear.\n\nWeakness:\n1) (Main Concern) I cannot understand why the proposed algorithm can protect the overall average performance from being sacrificed? According to the objective function Eq. (3) and Eq. (9), the proposed method improves fairness by minimizing the combination of overall risk and variance. Among them, the semi-VRed only penalizes the clients with local risk higher than the average risk. The semi-VRed does not encourage the clients with good performance to be closed to the average performance explicitly, however, it seems that there is also a performance sacrifice. There are always some clients that are up-weighted, which means that other clients are down-weighted relatively.\n2) From the view of distributionally robust optimization, it seems that the proposed method is similar to reweight techniques (but with a smaller uncertainty set), which are widely used in the previous work, such as AFL [1] and DRFA [2]. The relations between this work and distributionally robust optimization-based methods should be discussed more.\n3) The hyper-parameter local step number $K$ should be discussed, and it would be better to add more ablation studies about $K$, since there may be a trade-off between communication cost and performance (fairness). If $K$ is too small, more rounds of communication are needed to guarantee the convergence of federated model. If K is too large, the performance (fairness) may be not guaranteed, since the proposed federated algorithm is an approximation for the proposed objective function. Specifically, the difference between two rounds of local model parameters $f_i(\\theta)-\\bar{f}(\\theta)$ is an unbiased estimation for the true weights (used to penalize the clients with worst performance) of clients, however, the variance of the estimation is very large (O(K^2)).\n\n[1] Mohri M et. al. Agnostic federated learning. ICML 2019.\n[2] Deng Yet. al. Distributionally robust federated averaging. NeurIPS 2020.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2QnSBC8J26", "reviewer": "Reviewer_bZXJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper provides two federated learning algorithms that aim to minimize the gap between the average performance of the trained model among clients and the performance on the worst-performing subgroups. The methods are designed to either minimize the variance or semi-variance of the clients' performance; called VRed and Semi-VRed, respectively. Authors establish convergence guarantees for VRed, and give several lemma to demystify the proposed algorithms. Through experiments, authors show that the performance of the proposed algorithms, especially that of Semi-VRed, is better than the prior state-of-the-arts.", "summary_of_the_review": "This paper gives a simple, concrete, and well-performing federated learning algorithm with a sufficient degree of empirical validation. The paper could be much more impactful with some added experiments, but I do not see a very big reason to reject the paper.", "strength_and_weaknesses": "__Strengths__\n\n- Theorem 1 seems to be a working way of giving convergence guarantees for variance-penalized optimizations under the context of federated learning. The proof idea may be useful for the future works that aim to give convergence guarantees based on alternative risk measures on clients (other than averaging).\n\n- I like how authors compared the empirical performance of the proposed algorithm with a variety of baselines on the experimental setups that, up to my knowledge, has not been popularly used in the literature. From the appendices, I see that authors have put considerable effort in tuning the hyperparameters of the baseline methods, which will be a great academic asset of the community if the code is released.\n\n__Weaknesses__\n\n- It is not clear to me why authors did not consider any model personalization in this context. In footnote 1, authors explain that authors do not use model personalization in this work for a fair comparison with baseline algorithms. Putting a constraint purely for a fair comparison is not a very practical thing to do---if one can have improved (average and worst-case) performance by removing a constraint, why should one even consider a setup with such constraint? Could you provide any practical justification on why it is (at least sometimes) useful to consider federated learning without any model personalization?\n\n- The performance of the trained models seems to be very low overall, which may be due to an excessive number of clients. For instance, the CIFAR-10 performance with ResNet-18 models is quite low; lower than 50% accuracy. It may be useful to have comparisons under such regime, but it will also be useful to have experimental results in a more well-performing regime, where the computation/communication budget is higher and the number of clients is perhaps smaller.\n\n- The discussion about Theorem 1 is rather weak. Is there any helpful knowledge that we could deduce from the upper bound of Theorem 1? Comparing with the discussion on lemma 2, I think that Theorem 1 is way more non-trivial than lemma 1,2 should be treated better.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2LNR9g7yzmG", "reviewer": "Reviewer_YTzx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The authors propose a new fair FL algorithm that penalizes the variance (or semi-variance) of the utilities among the clients.", "summary_of_the_review": "See my comments above.", "strength_and_weaknesses": "-- I am surprised that the most closely related paper is not even mentioned. It seems clear that the authors are not aware that similar risk measures, adopted from mathematical finance, have been proposed in the group fairness literature.  In particular, conditional value at risk (CVaR) has been used in the literature since the following seminal work. \n\nhttps://proceedings.mlr.press/v97/williamson19a.html\n\nThough it's not exactly the variance form, I believe that the CVaR formulation will be very similar when applied in the federated learning setting. The authors should have discussed the similarities/differences between the proposed approach and the CVaR formulation + FedAvg approach. \n\n-- Also, it will be great if the authors can comment on the relationship between robust optimization and mean/variance optimization. According to [Gotoh, Kim, Lim], they are essentially equivalent. This means that the robust federated learning algorithm such as DITTO might be very similar to what the authors proposed.\n\nhttps://www.sciencedirect.com/science/article/pii/S016763771730514X\n\n-- Some baselines are missing: Addressing Algorithmic Disparity and Performance Inconsistency in Federated Learning, NeurIPS'21", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject