FOCUS: Fairness via Agent-Awareness for Federated Learning on Heterogeneous Data
Authors: Wenda Chu
Chulin Xie
Boxin Wang
Linyi Li
Lang Yin
Han Zhao
Bo Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
fairness
data heterogeneity
clustering
expectation–maximization (EM)

Abstract: Federated learning (FL) provides an effective collaborative training paradigm, allowing local agents to train a global model jointly without sharing their local data to protect privacy.
On the other hand, due to the heterogeneous nature of local agents, it is challenging to optimize or even define the fairness for agents, which may discourage valuable participation. For instance, the trained global model may sacrifice the performance of a minority user with high-quality data based on loss optimization over all users.
Existing work usually considers accuracy equity as fairness for different users in FL, which is limited especially under the heterogeneous setting, since it is intuitively "unfair" that agents with low-quality data would achieve similar accuracy.
In this work, we aim to address such limitations and propose a formal fairness definition in FL, fairness via agent-awareness (FAA), which takes the heterogeneous data contributions of local agents into account. In addition, we propose a fair FL training algorithm based on agent clustering (FOCUS) to achieve FAA. Theoretically, we prove the convergence and optimality of  FOCUS under mild conditions for linear and general convex loss functions with bounded smoothness. We also prove that FOCUS always achieves higher fairness measured by FAA compared with standard FedAvg protocol under both linear and general convex loss functions. Empirically, we evaluate FOCUS on four datasets, including synthetic data, images, and texts under different settings, and we show that FOCUS achieves significantly higher fairness based on FAA while maintaining similar or even higher prediction accuracy compared with FedAvg and other existing fair FL algorithms.


Under review as a conference paper at ICLR 2023
FAIRNESS VIA AGENT-AWARENESS FOR FEDERATED LEARNING ON HETEROGENEOUS DATA
FOCUS:
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FI.) provides an effective collaborative training paradigm, al- lowing local agents to train global model jointly without sharing their local data to protect privacy. However, due to the heterogeneous nature of local data, it is challenging to optimize even define faimesss of the trained global model for the agents. For instance, existing work usually considers accuracy equity as fair- ness for different agents in FL, which is limited, especially under the heteroge- neous setting, since it is intuitively "unfair" to enforce agents with high-quality data (e.g., hospitals with high-resolution data and fine-grained labels) to achieve similar accuracy to those who contribute low-quality data (e.g.. hospitals with low-resolution data and noisy labels), which may discourage the agents from par- ticipating in FL. In this work, we aim to address such limitations and propose a formal fairness definition in FL. fairness via different contributions of heterogeneous agents into account. Under FAA, the per- formance of agents with high-quality data will not be sacrificed just due the existence of large amounts of agents with low-quality data. In addition, we pro- pose fair FL training algorithm based on agent clustering (FOCUS) to achieve fairness in FL measured by FAA. Theoretically, optimality of FOCUS under mild conditions for linear and general convex loss functions with bounded smoothness. We also prove that FOCUS always achieves higher fairness in terms of FAA compared with standard FedAvg under both lin- ear and general convex loss functions. Empirically, we evaluate FOCUS on four datasets, including synthetic data, images, and texts under different settings, and we show that FOCUS achieves significantly higher fairness terms of FAA while maintaining similar or even higher prediction accuracy compared with FedAvg and other existing fair FL algorithms.
(FAA), which takes
prove the convergence and
INTRODUCTION
Federated learning (FL) is emerging promising approach enable scalable intelligence over distributed settings such as mobile networks (Lim et al. |020 Hard et al., (2088). Given the wide adoption of FI., including medical analysis (Sheller al.) 2020) Adnan et al. 2022 recommen- dation systems (Minto et al. 2021 Anelli et al.] 2021). and personal Internet of Things (IoT) devices (Alawadi et al. 2021). how ensure the fairness of the trained global model in FL of great importance before its large-scale deployment, especially when the data quality/cottributions of different agents are different the heterogeneous setting.
In general, fairness is defined as the protection of a specific attribute, and fair FL is usually in the form of equity, which means that each individual that joins collaborative learning would not suffer from bad performance due to their identity. Several studies have explored fairness in FL, which mainly focus on the fairness of the final trained model regarding the protected attributes without considering different contributions of agents (Chu et al. 2021 Hu et al. (022) or the accuracy parity across agents (Li et al. 2020b Donahue & Kleinberg, 2022a Mohri et al. 2019). Some works have considered the properties of local agents, such as the local data properties Zhang et al. 2020 Kang et al. 2019) and data size (Donahue & Kleinberg 2022b). However, the fairness analysis in FL under heterogeneous data distributions is still lacking. Thus, in this paper, aim ask: What is the fairness of FL that is able to take different contributions of heterogeneous local agents into account? Can we enhance the fairness of FL by providing advanced training algorithms?

---

Under review as a conference paper at ICLR 2023
To better understand the fairness of FL under heterogeneous data, in this work, we aim to define and enhance fairness by explicitly considering different contributions of heterogeneous agents. In particular, for FL trained with standard FedAvg protocol (McMahan et al. 2017), if we denote the data of agent e as Dr with size ne and the total number of data as n, the final trained global model aims to minimize the loss with respect to the global distribution P = Σe= "y De. where E is the total number of agents. In practice, some local agents may have low-quality di (e.g., free riders), so intuitively it is "unfair" to train the final model regarding such global distribution over all agents, which will sacrifice the performance of agents with high-quality data. For example, considering the FL applications for medical analysis, some hospitals have high-resolution medical data and fine- grained labels, which cost a large amount of money to collect the data from advanced equipment and to crowdsource data labeling. In contrast, some hospitals may have low-resolution medical data and noisy labels. In such a setting, high-quality agents may not be willing to participate in collaborative learning with low-quality agents because they could have achieved higher accuracy by standalone local training. Therefore, proper fairness notion is important to encourage agents to participate in FL and ensure fairness. In this paper, we define fairness via agent-awarenes: in FL (FAA) as FAA([0eFect)
= maxe,, Ee, (Be, Ee, (fez),. measured by the maximal excess risk difference between any pair of agents E1, e1 E E. The excess risk of each agent is calculated as (0.) = (0.) - ming- Le((0), which stands for the loss of user evaluated on the FL model 0₂ subtracted by the Bayes optimal error of the local data distribution (Opper & Haussler 1991). For each agent, a lower excess risk & (02) indicates more gain from the FL model 0g w.r.t the local distribution because its loss (0.) is more closed to its Bayes optimal error. Notably, reducing FAA enforces the equity of excess risks among agents, following the philosophy that each agent should "gain the same" from participating in FL. Therefore, lower FAA indicates stronger fairness for FL.
Based on our faimess definition FAA, then propose a fair FL algorithm based agent clus- tering (FOCUS) to improve the faimness of FL. Specifically, we first cluster the local agents based on their data distributions and then train model for each cluster. During inference time, the final prediction will be the weighted aggregation over the prediction result of each model trained with the corresponding clustered local data. Theoretically, we prove that the final converged stationary point of FOCUS is exponentially close to the optimal cluster assignment under mild conditions. In addi- tion, we prove that the fairness of FOCUS in terms of FAA is strictly higher than that of the standard FedAvg under both linear models and general convex losses. Empirically, we evaluate FOCUS on four datasets, including synthetic data, images, and texts, and we show that FOCUS achieves higher fairness measured by FAA than FedAvg and SOTA fair FI. algorithms while maintaining similar or even higher prediction accuracy.
Technical contributions. In this work, we define and improve FL fairness in heterogeneous settings by considering different contributions of heterogencous local agents. We make contributions on theoretical and empirical fronts.
We formally define fairness via agent-awareness (FAA) in FL based on agent-level excess risks to measure fairness in FL., and explicitly take the heterogeneity nature of local agents into account. We propose fair FL algorithm via agent clustering (FOCUS) to improve faimeess measured by FAA, especially in the heterogeneous setting. We prove the convergence rate and optimality of FOCUS under linear models and general convex losses.
We prove that FOCUS achieves stronger fairness measured by FAA compared with FedAvg for both linear models and general convex losses.
Empirically, we compare FOCUS with FedAvg and SOTA fair FL algorithms on four datasets, including synthetic data, images, and texts under heterogeneous settings. We show that FOCUS indeed achieves stronger fairess measured by FAA while maintaining similar or even higher prediction accuracy on all datasets.
RELATED WORK
Fair Federated Learning There have been several studies exploring fairness in FL. Li et al. (020bb first define agent-level fairness by considering accuracy equity across agents and achieve fairness by assigning the agents with worse performance with higher aggregation weight during training. However, such a definition of faimess fails to capture the heterogeneous nature of local agents. Mohri et al. (2019) pursue accuracy parity by improving the performance of the worst- performing agent. Wang et al. (202l) propose to mitigate conflict gradients from local agents to enhance fairness. Instead of pursuing fairness with one single global model, [i et al. (20TT) propose to train a personalized model for each agent achieve accuracy equity for the personalized models.
2

---

Under review as a conference paper at ICLR 2023
Zhang al. (2020) predefine the agent contribution levels based oracle assumption (e.g., data volume, data collection cost, etc.) for fairness optimization, which lacks quantitative measurement metrics in practice. Xu et al. (2021) approximate the Shapely Value based gradient cosine sim- ilarity to evaluate agent contribution. However, Zhang et al. (2020) point out that Shapely Value may discourage agents with rare data, especially under heterogeneous setrings. Here we provide an algorithm to quantitatively measure the contribution of local data based on each agent's 's excess risk, which will not be affected even if the agent is the minority.
Clustered Federated Learning Clustered FL algorithms are initially designed for multitasking and personalized federated learning, which assumes that agents can be naturally partitioned into clusters (Ghosh al. 2020 Xie al. 2021 Sattler al. 2021 Marfoq et al. 2021). Existing clus- tering algorithms usually aim to assign each agent to a cluster that provides the lowest loss (Ghosh)
al., 2020), optimize the clustering center to be close to the local model (Xie et al. (202I). or cluster agents with similar gradient updates (with respect to, c.g., cosine similarity (Sattler et al. (02T)) to
the same cluster. In addition these hard clustering approaches (i.e., each agent only belongs to one cluster), soft clustering has also been studied (Marfoq et al.) [202]] Li et al. [022] Ruan & Joe- Wong 2022 Stallmann & Wilbik 2022), which enables the agents to benefit from multiple clusters. However, none of these works considers the fairness of clustered FL and the potential implications, and our work makes the first attempt to bridge them.
FAIR FEDERATED LEARNING ON HETEROGENEOUS DATA
In this section, we first define our fairness via agent-awarenee (FAA) in FL with heterogeneous data and then introduce our fair FL based on the agent clustering (FOCUS) algorithm to achieve FAA.
3.1 FAIRNESS VIA AGENT-AWARENES IN FL (FAA) WITH HETEROGENEOUS DATA
Given a set of L' agents participated in the FL training process, each agent e only has access to its local dataset: De = {Ie, T- which is sampled from distribution Pe. The goal of standard FedAvg training is to minimize the overall loss (f( based on the local loss (e) of each agent:
Dr.
min (e) Σ EE[E] π
()).
(e (x..)) (()(())))))
where :) is a loss function given model prediction ho(x)) and label y (e.g., cross-entropy loss), n EeE[E] DDel represents the total number of training samples, and 0 represents the parameter of trained global model.
Intuitively, the performance of agents with high-quality data (e.g., clean or better generality) could be severely compromised by the existence of large amounts of agents with low-quality data (c.g., noisy lower generality) under FedAvg. To solve such problem and characterize the distinctions of local data distributions (contributions) among agents to ensure fairness, we propose faimesss via agent-awareness in FL. (FAA) as below.
Definition 1 (Fairness via agent-awarenes: for FL (FAA)). Given a set of agents E in FL, the overall fairness score among all agents defined as the maximal difference of excess risks for any pair of agents:
FAA(((c)ee(F)) = max E1.F2E[E]
Ee, (0c.) (0e())
(2)
where Og is the local model for agent e E [E]. The excess risk (0e) for agent e given model 9 defined as the difference between the population loss (0e) and the Bayes optimal error of the corresponding data distribution, i.e.,
E. (0e) = Lo(oe)
min (0") 0""
(3)
where 8" denotes any possible models.
Note that in FedAvg, each client uses the global model 0 as its local model 0e. Definition I repre- sents a quantitative dete-dependent measurement of agent-level fairness. Instead of forcing accuracy equity among all agents regardless of their data distributions, we define agent-level faimess as the equity of excexs risky among agents, which takes the contributions of local data into account by measuring their Bayes errors. For instance, when a local agent has low-quality data, although the corresponding utility loss would be high, the Bayes error of such low-quality data is also high, and thus the excess risk of the user still low, enabling the agents with high-quality data to achieve low utility loss for fairness. According to the definition, we note that lower FAA indicates stronger fairness among agents.
3

---

Under review as a conference paper at ICLR 2023
3.2 FAIR FEDERATED LEARNING ON HETEROGENEOUS DATA VIA CLUSTERING (FOCUS)
Method Overview. To enhance the fairness of FL in terms of FAA, we provide an agent clustering- based FL algorithm (FOCUS) by partitioning agents conditioned on their data distributions. Intu- itively, grouping agents with similar data distributions together helps to improve faimess, since reduces the intra-cluster data heterogeneity. We will analyze the fairness achieved by FOCUS and compare it with standard FedAvg both theoretically (Section 4.2) and empirically (Section 5
Our FOCUS algorithm (Algorithm leverages the penectaationMaaimizaiii agent clustering. Define M as the number of clusters and E as the number of agents. The goal of FOCUS is to simultaneously optimize the soft clustering labels and model weights W. Specif- ically, II {Te [l are the dynamic soft clustering labels, representing the estimated probability that agent belongs to cluster m; W = {wm J mE[M] [M] represent the model weights for M data clusters. Given agents with datasets D1,.... DE, our FOCUS algorithm follows a two-step scheme that alternately optimizes II and W.
algorithm to perform
step. Expectation steps update the cluster labels II given the current estimation of (II, W). At k-th communication round, the server broadcasts the M cluster models to all agents. The agents
(t) calculate the expected training loss (s., D. {1x, y; wh)) for each cluster model Wi. m E [M]. and then update the soft clustering labels II according to Eq. (8)
M step. The goal of M steps in Eq. (9) is to minimize weighted sum of empirical losses for all local agents. However, given distributed data, it is impossible to find its exact optimal solution in practice. Thus, we specify concrete protocol in Eq.
Eq. (6) estimate the objective in Eq. At i-th communication round, for each cluster model wm received from server, each agent first initializes its local model 009) em(() as wn, and then updates the model using its own dataset. To reduce communication costs, each agent is allowed to run SGD locally for K local steps e as shown in Eq. (5). After K local steps, each agent sends the updated models (m(K) back to the central server, and the server aggregates the models of all agents by a weighted average based on the soft clustering labels {Tem). We provide theoretical analysis for the convergence and optimality of FOCUS considering these multiple local updates in Section
Clients:
g(+)
wm
(4)
((0) em((++1)
0 em(k)
(logo (c. (o Vk= I....,K- K-1. 1. eme(k)
(5)
(1+1)
g(t) een K2
Server:
Wm
(C+1)
Tem
(6)
π Tefm
Inference. At inference time, each agent ensembles the M models by a weighted average on their prediction probabilities, i.e., a agent predicts ΣM Nem (I) for input x. Suppose a test dataset Drest is sampled from distribution Pe. The test loss can be calculated by
M
Lrest (W,
Tem)i((x),
Drest
(
For unseen agents that do not participate in the training process, their clustering labels IT are un- known. Therefore, unseen agent e computes its one-shot clustering label (1) E [M] according
to Eq. 8). and outputs predictions Σ M (1)
m=1 Htm (1r) for the test sample x.
4 THEORETICAL ANALYSIS OF FOCUS
In this section, we first present the convergence and optimality guarantees of our FOCUS algorithm; and then prove that it improves the fairnsss of FL regarding FAA. Our analysis considers linear models and then extends to nonlinear models with smooth and strongly convex loss functions.
4.1 CONVERGENCE ANALYSIS
Linear models. We first start with linear models for analysis simplicity. Suppose there are E agents, each with a local dataset D. {(<(") ye fe (e E [E]) generated from a Gaussian dis- tribution. Specifically, assume each dataset D, has mean vector Ph E IRdd and (a! ( is
4

---

Under review as a conference paper at ICLR 2023
Algorithm EM clustered federated learning algorithm
Input: Data Dr..... De; E remote agents and M learning models. Initialize weights wm and with 1 for m E [M] and e E [E]. for t = 0 to 7 - do for agent e [ do for model step:
M
[M]] do
(4)
exp
E(D.))DD (1x, yr wm))
Tem
(++1)
M (1)
B...DDDD (1, Us v: (1)
(8)
end for end for for model [M] do
m mem exp(
E
M step:
Wm (++1)
arg min
Rem
(++1)
Σ
(oo(ae (.
(9)
end for end for return model weights 1mm
i=
(T)
(8) 3. = cr where (1) is random vector (0) ~ _N00 1a) and the label yo generated by ye is blurred by some random noise e!" ~ (N o²), Each agent is asked to minimize the mean squared error to estimate pee, so the empirical loss function for local agent given dataset De is
Lemp (De; 2
(w Ie ye )
(10)
The
We further make the following assumption about the heterogeneous agents.
Assumption (Separable distributions). Suppose there are M predefined vectors {w; M.M where for any mı, m2 E [M), I|w,, - w |l 2 R. A set of agents E. satisfy separable distributions they can be divided into M subsets Si,..., SM such that, for any agent e Sm. llfe w ll S R Assumption I guarantees that the heterogeneous local data distributions are separable so that an optimal clustering solution exists, in which [w"..... "ar) } are the centers of clusters.
We next present Theorem I to demonstrate the linear convergence rate the optimal cluster centers for FOCUS. Detailed proofs can be found in Appendix B.1
Theorem 1. Consider the agent set E satisfying separable distributions as assumption [ Given
trained M models and Ve, m. Tem = 1. Under the natural initialization Wm for each model
m E [M]. which satisfies =Ag > 0, || (0) wi I minm' ||l w 112 - 2(r + Ao) and
8 FOCUS converges by Del (d). If learning rate S min 452
(T) Tem
1 (M (.lp))xexp2pee00 exp(-226'A077 We S. KT
(11)
win 112 S (1
2n7mm8
([lw with 11 A) 2M +
M E3
O o2)).
(12)
M
2VT
where T is the total number of communication rounds; K is the number of local updates in each communication round; Tm = 1mml is the number of agents in the m-th cluster, and
2EK (M 1)6²
A
(caused by initial inaccurate clustering).
(13)
2m55 Tm exp( 20)
Proof sketch. To prove this theorem, we first consider E steps and M steps separately to derive corre- sponding convergence lemmas (Lemmas| and In E steps, the soft cluster labels Tem increase for
all E Sm, long as |! w", ll2 < [ w", llz, V'' o m. On the other hand, !|w!! w is guaranteed to shrink linearly as long as Tem is large enough for any e E Sm. We then integrate Lemmas 1 and and prove Theorem using induction statement.
Remarks. Theorem shows the convergence parameters (II, W) to a near-optimal solution. Eq. (11) implies that the agents will be correctly clustered since Tem will converge to 1 as the num- ber communication rounds K increases. In Eq. (12), the first term diminishes exponentially, while the second term 2M Kr reflects the intra-cluster distribution divergence The last term originates
5

---

Under review as a conference paper at ICLR 2023
from the data heterogeneity among clients across different clusters. Its influence is amplified by the number of local updates (O(K3) and will also diminish to zero as the number of communication rounds T' goes to infinity. Our convergence analysis is conditioned on the natural clustering ini- tialization for model weights w/n towards a corresponding cluster center w which is standard in convergence analysis for mixture of models (Yan et al. 2017 Balakrishnan al. 2017).
Smooth and strongly convex loss functions. Next, we extend our analysis to a more general case of non-linear models with L-smooth and μ-strongly convex loss function.
Assumption (Smooth and strongly convex loss functions). The population loss functions (e for euch agent e is L-smooth, i.e., || C. (0)ll2 L. The loss functions are p-strongly convex, if the eigenvalues À of the Hessian matrix L. satisfy Amin( ( j..
We further make assumption similar to Assumption (arriionnoolloooiinn the similar philosophy.
Assumption 3 (Separable distributions). A set of agents F. satisfy separable distributions if they can be partitioned into M subsets , SM with w ....... Way representing the center of each set respectively, and the optimal parameter 0 of each local loss Le (i.e., 0% arg ming ( satisfy
110: - wmll22 S
(14)
In the meantime, agents from different subsets have different data distributions, such that
|| Wmalle lla R. Vml, m2 & [M], m1 # m2.
(15)
Theorem 2. Consider the agent set E satisfying separable distributions as assumplion Suppose loss functions have bounded variance for gradients on local datasets, i.e., ((..)) y; VL. (0)ll²) S a², and the population losses are bounded, i.e. Le S yFR G.ve [E]. If let T( M BAo > 0, 11 -wi S VE+VE r Do, and the learn-
3
ing rate of each agent 1j S min( N Ar), FOCUS converges by
Tem
(T) 2
1+ (M- - exp( PRRATT) Ve Sm
(16)
El[ Bl - - s nA)* (1Iw! win B) + O(Kr) ME30 +)
(17)
/T
where T is the total number of communication rounds; K is the number of local updates in each communication round: Ymm = 1mml is the number of agents in the m-th cluster, and
27 UL
GMTE
p(++L)
(18)
M + (I
AA)K exp( pMA.
related conrerrgncee rate
caused by the offect of mnttial clussering
Proof sketch. We analyze the evolution of parameters (II, W) for E steps in Lemma 3 and M steps in Lemma Lemma 3 shows that the soft cluster labels Tem increase for all E Sm. in E steps as
long I| - - Ju=-VT r; whereas Lemma guarantees that the model weights win get closer to the optimal solution w,, in M steps. We combine Lemmas 3 and 4 by induction to prove this thcorem. Detailed proofs are deferred to Appendix B.2.3
/PR
Remarks. Theorem 2 extends the convergence guarantee of (II, W) from linear models (Theorem general models with smooth and convex loss functions. For any agent e that belongs cluster m (e E S. its soft cluster label 9am converges to 1 based on Eq. (16). indicating the clustering optimality. Meanwhile, the model weights W converge linearly error term O(Kr) in Eq. (17) is expected, since represents the data divergence within each cluster and w,, denotes the center of each cluster. The last term in Eq. (77 implies a trade-off between communication cost and convergence speed. Increasing K reduces communication cost by O (++) but at the expanse of slowing down the convergence.
a near-optimal solution. The
4.2 FAIRNESS ANALYSIS
To theoretically show that FOCUS achieves stronger fairness FL based on FAA, here we focus on simple yet representative case where all agents share similar distributions except outlier agent.

---

Under review as a conference paper at ICLR 2023
Linear models. We first concretize such scenario for linear models. Suppose have E agents learning weights for M linear models. Their local data De(e [E]) are generated by ye" 2e xx=(")= - with 2 (N (100,611 la) and e! ~ (O o²). E - agents learn from normal dataset with ground truth vector f1...... PE-1 and life 14' I r, while the E-th agent has an outlier data distribution, with its the ground truth vector je far away from other agents, i.e., lIKE 1² 12 2 R.
As stated in Theorem the soft clustering labels and model weights (II, W') converge linearly to the global optimum. Therefore, we analyze the faimess of FOCUS, assuming optimal (TT, W) is reached. We compare the FAA achieved by FOCUS and FedAvg to underscore how our algorithm helps improve fairness for heterogeneous agents.
Theorem 3. When a single agent has an outlier distribution, the fairness FAA achieved by FOCUS algorithm with two clusters M 2 is
JAAf (W,11) I $8'22
(19)
while the fairness FAA achieved by FedAvg is
FAAugg (W) ) 2 5² ( 2) 2Rr
+ + 226601002
(20)
E
Remarks, When single outlier exists, the fairness gap between Fedavg and FOCUS is shown by Theorem 3
FAAaug (W)) oou IT) 2 5² IE 2 (
(21)
E
FOCUS is guaranteed to achieve stronger fairness (i.e., lower FAA) than FedAvg. Note that the outlier assumption only makes sense when E > 2 since one cannot tell which agent is the outlier when
As long R
2r
E-2-
2. Also, we naturally assume R > 2r so that the two underlying clusters are at least separable. Therefore, conclude that FOCUS dominates than FedAvg in terms of FAA. Here we only discuss the scenario of a single outlier agent for clarity, but similar conclusions can be drawn for multiple underlying clusters and M > 2, discussed in Appendix C.I
Smooth and strongly convex loss functions. We generalize the fairness analysis to nonlinear models with smooth and convex loss functions. To illustrate the superiority of our FOCUS al- gorithms in terms of FAA faireess, we similarly consider training in the presence of an outlier agent. Suppose we have E agents that learn weights for M models. We assume their popu- lation loss functions are L-smooth, p-strongly convex (as in Assumption ( and bounded, i.e., Lo( S G. E agents learn from similar data distributions, such that the total variation dis- tance between the distributions of any two different agents i, E [E 1] is no greater than r: (P p,) S r. On the other hand, the E-th agent has an outlier data distribution, such that the Bayes error (0,) (0%) > R for any i E [ 1.. We claim that this assumption can be reduced to lower bound on H-divergence (Zhao et al. 2022) between distributions Pi and Pg that LR (See proofs in Appendix
(P,, PB)
4p
Theorem 4. The fairness FAA achieved by FOCUS with two clusters M is
2Gr E-1
FAAsocus (I S
(22)
Let B 2Gr fairness achieved by FedAvg is
E-1 1 R L(F 1)
I.2
2L.
FAAnn (W)
B(R
B)
(23)
μE
12E
pE
Remarks. Notably, when the outlier distribution is very different from the normal distribution, such that R > Gr (which means B < R), we simplify Eq. 23 as
E
FAAsus (W)
RR
(24)
E
RE
Note that FAAfocus (W,II) < B < R. so the fairness FAA achieved by FedAvg is always larger (weaker) than that of FOCUS, as long as E 2 LL/u, indicating the effectiveness of FOCUS.
5 EXPERIMENTAL EVALUATION
We conduct extensive experiments on various heterogeneous data settings to evaluate the fairness measured by FAA for FOCUS, FedAvg (McMahan et al., 2017). and two baseline fair FL algo- rithms (i.c.. F-F (Li et al.) (2206b) and AFL (Mohri et al. 2019)). We show that FOCUS achieves significantly higher fairness measured by FAA while maintaining similar or even higher accuracy.
7

---

Under review as a conference paper at ICLR 2023
5.1 EXPERIMENTAL SETUP
Data and Models. We carry out experiments on four different datasets with heterogeneous data settings, ranging from synthetic data for linear models to images (rotated MNIST (Deng, 2012) and rotated CIFAR (Krizhevsky] 2009)) to text data for sentiment classification on Yelp (Zhagg et al. 2015) and IMDb (Maas al. 2011) datasets. We train a fully connected model consisting of two linear layers with ReI.U activations for MNIST, ResNet 18 model (He et al.) (016) for CIFAR, and a pre-trained BERT-base model (Devlin et al. 2019) for the text data. We refer the readers to Appendix D for more implementation details.
Evaluation Metries and Implementation Details. We consider three evaluation metrics: average test accuracy, average test loss, FAA for fairesss and the existing fairness metric "agnostic loss" introduced by Mohri ct al. 2019).. For FedAvg, we evaluate the trained global model on each agent's s test data; for FOCUS, labels 11 = [Tem (eE(E) me (M]] to make aggregated predictions on each agent's 's test data. We also report the performance of existing fair FL. algorithms (i.e., q-FFL (Li et al. 2020b), AFL (Mohri let at. 2019)). Ditto al. (02T). and CGSV Xu et al. (2021) as well as existing state-of- -ftte-arrt FL. algorithms in heterogeneous data settings (i.e., FedMA (Wang et al. 2020), Bayesian nonparametric FL (Yurochkin et al. 2019) and FedProx (Li et al. 2020a) in Appendix D.2).
train M models corresponding to M clusters, and use the soft clustering
To evaluate FAA of different algorithms, we estimate the Bayes optimal loss min,, (w) for each local agent e. Specifically, we train a centralized model based on the subset of agents with similar data distributions (i.e., the same ground-truth cluster) and use it as a surrogate to approximate the Bayes optimum. We select the agent pair with the maximal difference of excess risks to measure fairness in terms of FAA calculated following Definition 1
5.2 EVALUATION RESULTS
Synthetic data for linear models. We first evaluate FOCUS on linear regression models with synthetic datasets. We set up F = 10 agents with data sampled from Gaussian distributions. Each agent e is assigned with a local dataset of D. = ((xt)) we
(9) (4) )>> generated by y = μe x + c
with 2. ~ (0, Ia) and c. ~ __(00,0)) o²). We study the case considered in Section 4.2 where a single agent has outlier data distribution. We set the intra-cluster distance
0.01 and the inter-cluster distance R = in our experiment. Note that is a regression task, so we mainly report the average test loss instead of accuracy here. T that FOCUS achieves FAA of 0.001, which much lower than the FAA 0.958 achieved by FedAvg, 0.699 by q-FFL, and 0. 0.780 by AFL.
Table 1: Comparison of FOCUS, FedAvg, and fair FL algorithms q-FFL. AFL, Ditto and CGSV, in terms of average test accuracy (Avg Ace), average test loss (Avg Loss), faimeess FAA and existing faimess metric Agnostic loss. FOCUS achieves the best fairness measured by FAA compared with all baselines.
9-FFL
FOCUS
FedAvg
AFL
Ditto
CGSV
q 0.1
9= 10
Avg Loss
0.010
0.108
0.106
0.102
0.110
0.104
0.023
0.260
Synthctic
F
0.001
0.958
0.769
0.717
0.699
0,780
0.012
0.010
Aug Ace
0.953
0.929
0.922
0.861
0.685
0.885
0.940
0.938
Rolated MNIST
Avg Loss
0.152
0.246
0.269
0.489
1.084
0.429
0.210
0.222
FAA
0.363
0.388
0.612
0.220
0.104
Agnostic Loss
0.224
0.616
0.656
1.018
1,271
0,548
0.354
0.331
Avg
0.929
0.908
0.897
0.833
0.365
0.866
0.932
0.861
Rotated CIFAR
Avg Loas
0.217
0. 0.262
0.306
0.704
1,263
0.324
0.202
0.511
FAA
0.365
0.537
0.661
0.542
0.421
0.619
0.424
1.775
Agnostic Loss
0.503
1.238
0.932
0.905
1.413
0.667
0.598
0.904
Avg Ase
0,940
0.940
0.938
0.958
0.909
0.934
0.933
0.701
YelpIMDb
Avg Loss
0.174
0.236
0.188
0.179
0.264
0.187
0.191
0.547
FAA
0.047
0.098
0.052
0.051
0.070
0.049
0.049
0.462
Agnostic Loss
0.349
0.266
0.253
0.242
0.253
0.263
0.700
Rotated MNIST and CIFAR. Following (Ghosh et al.) 2020). we rotate the images MNIST and
CIFAR datasets with different degrees to create data heterogeneity among agents. Both datasets are evenly split into 10 subsets for 10 agents. For MNIST, two subsets are rotated for 90 degrees, one subset is rotated for 180 degrees, and the rest seven subsets are unchanged, yielding an FL setup with three ground-truth clusters. Similarly, for CIFAR, we rotate the images of 3 subsets for 180 degrees, thus creating two ground clusters. From Table we observe that FOCUS consistently achieves higher average test accuracy, lower average test loss and lower FAA than other methods on
8

---

Under review as a conference paper at ICLR 2023
Tent Lowe
Festug Boyes Optimal
FOCUS
4
Client
Index of
(a) MNIST
(b) Yclp/IMDb
Figure 1:
The excess risk of different agents trained with FedAvg and FOCUS on MNIST (a) and Yelp/IMDb
text data (b). C₁ denotes ith cluster.
both datasets. In addition, although existing fair FL algorithms q-FFL and AFL achieve lower FAA scores than FedAvg, their average test accuracy drops significantly. This is mainly because these fair algorithms are designed for performance parity via improving low-quality agents (i.e., agents with high training loss), thus sacrificing the accuracy of high-quality agents. Notably, FOCUS both improves the FAA faimesss and preserves high test accuracy.
Next, we analyze the surrogate excess risk of every agent on MNIST in Fig. T (a). We ob- serve that the global model trained by FedAvg obtains the highest test loss as 0.61 on the out- lier cluster, which rotates 180 degrees (i.e., cluster C3), resulting in high excess risk for the 9th agent. Moreover, the low-quality data of the outlier cluster affect the agents in the 1st clus- ter via FedAvg training, which leads to a much higher excess risk than that of FOCUS. On the other hand, FOCUS successfully identifies clusters of the outlier distributions, i.e., clusters and 3, rendering models trained from the outlier clusters independent from the normal cluster 1. As shown in Fig. [ our FOCUS reduces the excess risks of all agents, especially for the out- liers, on different datasets. This leads to strong fairness among agents in terms of FAA. Similar trends are also observed in CIFAR, in which our FOCUS reduces the surrogate excess risk for the 9th agent from 2.74 to 0.44. We omit the loss histogram of CIFAR to Appendix() [
Table 2:
Comparison of FOCUS and FedAvg with dif- ferent numbers of outlier agents (k) in terms of average test accuracy (Avg Acc) and fairness FAA.
In addition, we evaluate different numbers of outliers in Table [ In the presence of 1, 3, and 5 outlier agents, forming 2, 3, or 4 underly- ing true clusters, FOCUS consistently achieves lower FAA score and higher accuracy than baseline FedAvg.
Rocated MNIST
Romted CIFAR
A 3
A 2-5
k-1
A 3
5
Aug. Ace
FOCUS
FodAug
0.945
0.957
0,953
0.929
0,948
0.910
0,939
0.803
0.908
0.929
0.872
0.857
FOCUS
0.159
0.094
0.153
1.739
0.365
1.403
FedAug
0.515
0.363
0.476
3.456
0.537
In practice, do not know the number of underlying clusters, so we set M 3 true underlying clusters in Table Mon on MNIST. It shows that under different M, FOCUS achieves similar accuracy and fairesss (see more discussion in Appendix AA.
2, while we have
Sentiment classification. We evaluate FOCUS on the sentiment classification task with text data, Yelp (restaurant reviews), and IMDb (movie reviews), which naturally form data heterogeneity among 10 agents and thus create 2 clusters. Specifically, we sample 56k reviews from Yelp datasets distributed among seven agents and use the whole 25k IMDB datasets distributed among three agents to simulate the heterogeneous setting. From Table [ we can see that while the average test accuracy of FOCUS, FedAvg, and other fair FL algorithms are similar, FOCUS achieves lower average test loss. In addition, the FAA of FOCUS is significantly lower than other baselines, indicating stronger fairness. We also observe from Fig. (b) that the excess risk of FOCUS on the outlier cluster (i.e., C2) drops significantly compared with that of FedAvg.
CONCLUSION
In this work, we provide an agent-level fairness measurement in FL (FAA) by taking agents' inherent heterogeneous data properties into account. Motivated by our fairness definition in FL., we also provide an effective FL training algorithm FOCUS to achieve high fairness. We theoretically analyze the convergence rate and optimality of FOCUS, and we prove that under mild conditions FOCUS is always fairer than the standard FedAvg protocol. We conduct thorough experiments on synthetic data with linear models as well as image and text datasets on deep neural networks. We show that FOCUS achieves stronger faimess than FedAvg and achieves similar or higher prediction accuracy across all datasets. We believe our work will inspire new research efforts on exploring the suitable fairness measurements for FL under different requirements.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mohammed Adnan, Shivam Kalra, Jesse Cresswell, Graham Taylor, and Hamid Tizhoosh. Federated learning and differential privacy for medical image analysis. volume 12, 02 2022. doi: 10.1038/
Sadi Alawadi, Yuji Dong Victor R. Kebande, Joseph Bugeja, Jan A. Persson, and Carl Magnus Olsson. A federated interactive learning iot-based health monitoring platform. In European URLhttp:
Conference Advances in Databases and Information Systems, pp. 235- 246, 2021.
//www. diva www.aiiiiaaaaaa...o.oooooo...aa. htt.t//a...cc.ooaaaa/////////aa/
Vito Walter Anellil, Yashar Deldjoo, Antonio Ferrara Tommaso Di Noia, and Fedelucio Nar- ducci. Federated recommender systems with learning rank. In 29-th Italian Symposium on Advanced Database Systems (SEBD), 2021. URL
pdd
Sivaraman Balakrishnan, Martin J Wainwright, and Bin Yu. Statistical guarantees for the em algo- rithm: From population to sample-based analysis. The Annals of Statistics, 45(1):77-120, 2017.
Lingyang Chu, Lanjun Wang, Yanjie Dong, Jian Pei, Zirui Zhou, and Yong Zhang. Fedfair: Training fair models in cross-silo federated learning. 2021.
05662.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
Jacob Devlin, Ming- Wing-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers), pp. 4171-4186, 2019.
Kate Donahue and Jon Kleinberg, Models of fairness in federated learning. 2022a. URL https: //axxiv.crg/pdf//2.
Kate Donahue and Jon Kleinberg. Models of fairness in federated learning. 2022b. URL https:
7/arxiv. org wttp://rrrrbs//12..000..
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances in Neural Information Processing Systems, 33:19586- 19597, 2020.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint arXiv: 18/ I.03604, 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Shengyuan Hu, Zhiwei Steven Wu, and Virginia Smith. Provably fair federated learning via bounded group loss. 2022. /
10190...011..... pdf
Jiawen Kang, Zehui Xiong, Dusit Niyato, Han Yu, Ying-Champ Liang, and Dong In Kim. Incentive design for efficient federated learning in mobile networks: A contract theory approach. 2019. URL https: ptattps://arivve org/
wttp:/o//gp////ootto// pdf /1905. 074 79. .pdf
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Chengxi Li, Gang Li, and Pramod Varshney. Federated learning with soft clustering. 2022. URL https://ieeee: orre. feee. org/ stamp/ stamp/stamp. stt.spttttppp......... jsp?tp=6a rnumber r= r= 991 74890)
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- fems, 454, 2020a.
10

---

Under review as a conference paper at ICLR 2023
Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30. 2020. OpenReview.net, 2020b. URL https::/ net/
forum? 1d=onn SYDr)
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357- 6368. PMLR, 2021.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ling-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys & Tutorials, (233):033-2063 2020.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 201 Association for Computational Linguistics. URL http:
7/www. www.aw.wwwebb.oo wrw.//eb.orrgaattooooo/////////e 1015
Othmane Marfoq, Giovanni Neglia, Aurélien Bellet, Laetitia Kameni, and Richard Vidal. Federated multi-task learning under mixture of distributions. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: httpps://openreveew net forum?id= XCC
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiieen learning of deep networks from decentralized data. 2017.
Lorenzo Minto, Moritz Haller, Hamed Haddadi, and Benjamin Livshits. Stronger privacy for feder- ated collaborative filtering with implicit feedback. In Fiftleemth ACM Conference on Recommender Systems, pp. 342-350, 2021. URL https: /oi. org/ 1ttp://....111/34411
3474262
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. 2019, URL http::/ppoccediiii ngs. ml wwwss/eesvvvv http://99///o///i/////// 19 9 pdd pdf.
Manfred Opper and David Haussler. Generalization performance of bayes optimal classification algorithm for learning a perceptron. Physical Review Letlers, 66(20):2677, 1991.
Yichen Ruan and Carlee Wong. Fedsoft: Soft clustered federated learning with proximal local updating. 2022. URL
http://www...r./p/////222../ pdf
Felix Sattler, Mlaus-Robert Müller, and Wojeiech Samek. Clustered federated learning: Model- agmostic distributed multitask optimization under privacy constraints. 2021. URL https: 91 948999
Teeexplore ieee. wwt//o/g/////ooo /ttp//saapppppp///
Micah Sheller, Brandon Edwards, G. Reina, Jason Martin, Sarthak Pati, Aikaterini Kotrot- sou, Mikhail Milchenko, Weilin Xu, Daniel Marcus, Rivka Colen, and Spyridon Bakas. Federated learning in medicine: Facilitating multi-instinutional collaboration without shar- ing patient data. In Scientific Reports 10, 2020. URL httpps:// http///ii.../1111.........01
s41598- 020-0000000 59250-1
Morris Stallmann and Anna Wilbik. Towards federated clustering: A federated fuzzy c-means algorithm (ffem). 2022. URL Ctl.tttps://// /ttps://aaxiv..om wtt.vvorggpp/f/////0 07316. 6.dff
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. arXiv preprint arXiv:2002.06444 2020.
Zheng Wang, Xiaoliang Fan, Jianzhong Qi, Chenglu Wen, Cheng Wang, and Rongshan Yu. Feder- ated learning with fair averaging. 2021. httt:ttp::
2 7021 /223.pdff
Ming Xie, Guodong Long, Tao Shen, Tianyi Zhou, Xianzhi Wang. Jing Jiang, and Chengqi Zhang. Multi-center federated learning. 2021. htt..https://e
01026

---

Under review as a conference paper at ICLR 2023
Xinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems, 34:16104-16117, 2021.
Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence of gradient em on multi- component mixture of gaussians. Advances in Neural Information Processing Systems, 30, 2017.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. Interna- tional Conference on Machine Learning, pp. 7252-7261. PMLR, 2019.
Jingfeng Zhang, Cheng Li, Antonio Robles-Kelly, and Mohan Kankanhalli. Hierarchically fair federated learning. 2020. URL
pdf Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Advances in neural information processing systems, 28, 2015.
Shengjia Zhao, Abhishek Sinha, Yutong He, Aidan Perreault, Jiaming Song, and Stefano Ermon. Comparing distributions by measuring differences that affect decision making. In International Conference on Learning Representations, 2022. URIhttps httptt:ss///ppeeeeiiieee net/ forum?? id KQ-KBoonoNJJAD
A REVISION UPDATES
If the submission gets accepted, we will exploit the extra page for the main text to add the following contents.
A.1 SCALABILITY WITH MORE AGENTS
To study the scalability of FOCUS, we evaluate the performance and fairness of FOCUS and isting methods under 100 clients on MNIST. Table shows that FOCUS achieves the best fairness measured by FAA and Agnostic Loss, higher test accuracy, and lower test loss than Fedavg and existing fair FL methods.
Table 3: Comparison of different methods on MNIST 100 clients setting, in terms of average test accuracy (Avg Acc), average test loss (Avg Loss), fairness FAA and existing fairness metric Agnos- tic loss. FOCUS achieves the best fairness measured by FAA.
q-FFI.
AFL
Ditto
CGSV
FOCUS
FedAvg
q=1
0.01
À
Avg Acc
0.9533
0,9236
0.8371
0.8813
0.9351
0.8691
Rotated MNIST (100 elients)
Avg Loss
0.157
0.2571
0.5668
0.4355
0.2206
0.6294
FAA
0.5605
1,0652
1.5055
0.8901
0.7459
1.2935
Agnostic Loss
0.5028
0.8894
1.4227
0.7767
0.620
1.5133
A.2 CONVERGENCE OF FOCUS
We report the test accuracy and test loss of different methods over FL communication rounds on Rotated MNIST with 10/100 clients and Rotated CIFAR in Fig, - The results show that FOCUS converges faster and achieves higher accuracy and lower loss than other methods on both settings.
A.3 RUNTIME ANALYSIS
Computation time analysis for proposed metric FAA and its scalability to more clients. In FAA, to calculate the maximal difference of excess risks for any pair of agents, it suffices to calculate the difference between the maximal per-client excess risks and the minimum per-client excess risk, and we don't 't need to calculate the difference for any pairs of agents. We compare the computation time (averaged over 100 trials) of FAA and existing fairness criteria (i.e,, Accuracy Parity (Li et al. 2020b) and Agnostic Loss (Mohri et al. 2019) under 10 clients and 100 clients ANIST.Tabll
12

---

Under review as a conference paper at ICLR 2023
100
FOCUS
90
FedAvg
80
Test Loss
q-FFL
Test Accura
FOCUS
AFL
FedAvg
Ditto
50
q-FFL
40
30
AFL
20
Ditto
CGSV
40
80
120
160
200
240
280
40
120
160
200
240
280
Communication Round
Communication Round
(a) Rotated MNIST with 10 clients.
100
FOCUS
90
FedAvg
80
Test Loss
q-FFL
Test Accura
AFL
FOCUS
Ditto
50
FedAvg
40
30
q-FFL
20
AFL
Ditto
40
80
120
160
200
240
280
40
80
120
160
200
240
280
Communication
Round
Communication Round
(h) Rotated MNIST with 100 clients.
100
FOCUS
90
FedAvg
Test Accuracy
Test Loss
q-FFL
FOCUS
AFL
FedAvg
Ditto
q-FFL
CGSV
40
30
AFL
Ditto
CGSV
30
60
90
120
150
180
210
240
30
60
90
120
150
180 210 240
Communication Round
Communication Round
(c) Rotated CIFAR with 10 clients.
Figure 2: The test accuracy and test loss different methods over FL. communication rounds on different datasets. FOCUS converges faster and achieves higher accuracy and lower loss than other methods.
Table Computation time of different FL fairness metric on Rotated MNIST, The computation of FAA is efficient under 10 clients and 100 client settings.
10 clients
100 clients
Accuracy Parity (Li et al. 2020b)
4.70 e-05 second
6.48 e-05 second
Agnostic loss (Mohri al.
2019
9.41 e-07 second
3.92 e-06 second
FAA
6.09 c-06 second
4.27 c-05 second
shows that the computation of FAA is efficient with large number of agents. Moreover, calculating the difference between maximal excess risk and minimum excess risk (i.e., FAA) even faster than calculating the standard deviation of the accuracy between agents (i.e., Accuracy Parity).
13

---

Under review as a conference paper at ICLR 2023
Table The number of communication rounds that different methods take reach target accuracy on Rotated MNIST. FOCUS requires a significantly smaller number of communication rounds than other methods.
70%
80%
85%
90%
FOCUS
16
20
29
FedAvg
10
51
88
177
q-FFL
28
151
261
>
300
AFL
16
94
180
300
Table The number of communication rounds that different methods take to reach target accuracy on Rotated CIFAR. FOCUS requires significantly smaller number of communication rounds than other methods.
70%
80%
85%
90%
FOCUS
69
92
112
135
FedAvg
81
103
129
164
q-FFI
102
159
>> 250
>
250
AFL
116
159
241
250
Communication rounds analysis. Here, we report the number of communication rounds that each method takes to achieve targeted accuracy on MNIST and CIFAR in Table We note that FOCUS requires significantly a smaller number of communication rounds than FedAvg, q-FFL, and AFL on both datasets, which demonstrates the small costs required by FOCUS.
Training time and inference time analysis. In terms of runtime, we report the training time for one FL round (averaged over 20 trials) well as inference time (averaged over 100 trials) in Table Since the local updates and sever aggregation for different cluster models can be run in parallel, we find that FOCUS has similar training time compared to FedAvg, q-FFL, and AFL which train one global FL model. For the inference time, FOCUS is slightly slower than existing methods by about 0.17 seconds due the ensemble prediction of all cluster models at each client. However, we note that such cost small and the forward passes of different cluster models for the ensemble prediction can also be made parallel further reduce the inference time.
A.4 COMPARISON TO FEDAVG WITH CLUSTERING
In this section, we construct a new method by combining the clustering and Fedavg together (i.e., FedAvg-HardClusten which serves as strong baseline. Specifically, FedAvg-HardClusse works as below:
Step 1: before training, for each agent, it takes the arg max of the learned soft cluster assignment from FOCUS to get the hard cluster assignment (i.c., each agent only belongs to one cluster).
Table 7: Training time per FL round and inference time for different methods on Rotate MNIST.
Training time per FL round Inference time
FOCUS
6.59 second
0.28 second
FedAvg
6.23 second
0. second
FFL
6.32 second
0.11 second
AFL
6.24 second
0.12 second
14

---

Under review as a conference paper at ICLR 2023
Table 8: Comparison between FOCUS and Fedluve-HarClluster on Rotate MNIST under two sce- narios.
Scenario 1
Scenario
(underly clusters are clearly separatable)
(underly clusters are not separatable)
FOCUS
FedAvg-Hard HardCluster
FOCUS
FedAvg HardCluster
Avg test acc
0.953
0.954
0.814
0.812
Avg test loss
0.152
0.152
1.168
1.244
FAA
0.094
0.099
0.449
0.459
Agnostic loss
0.224
0.224
1.333
1.397
Step 2: during training, each cluster then trains a FedAvg model based on corresponding agents.
Step 3: during inference, each agent only uses the corresponding one cluster FedAvg model for inference.
To compare the performance between FOCUS and HoddAv--arrdClsteer we consider two scenarios on MNIST:
Scenario underly clusters are clearly separatable, where each cluster contains samples from one distribution, which is the setting used in our paper.
Scenario 2: underlying clusters are not separatable, where each cluster has 80%, 10%, and 10% samples from three different distributions, respectively. For example, the first underlying clus- ter contains 80% samples without rotation, 10% samples rotating 90 degrees, and 10% samples rotating 180 degrees.
We observe that the learned soft cluster assignments from FOCUS align with the underlying distri- is equal to the underlying
bution, so the hard cluster assignment for Step in ground-truth clustering for both scenarios.
Table presents the results of FOCUS and BedAvg-HardCllssee on Rotated MNIST under two scenarios. Under Scenario 1, the accuracy of FOCUS and FedAve-HardCluster
similar, and FOCUS achieves better fairness in terms of FAA. The results show that the hard clustering for HerdlusHardCluster as good as the soft clustering for FOCUS when the underlying clusters are clearly separable, which verifies that clustering is one of the key steps in FOCUS, and it aligns with our hypothesis for fairness under heterogeneous data. Under Scenario 2, FOCUS achieves higher accuracy and better FAA fairness than clusters are not separatable, soft clustering better than hard clustering since each agent can benefit from multiple cluster models with the soft learned from the EM algorithm in FOCUS.
The results show that when underly
A.5 EFFECT OF THE NUMBER OF THE CLUSTERS M
The performance of FOCUS would not be harmed if the selected number of clusters larger than the number of underlying clusters since the superfluous clusters would be useless (the corresponding soft cluster assignment π goes to zero). On the other hand, when the selected number of clusters smaller than the number of underlying clusters, FOCUS would converge to solution when some clusters contain agents from more than one underlying cluster.
Empirically, in Table 9 we have 3 true underlying clusters while we set M 1, 3.4 in our experiments, and we see that when M = and M 4, FOCUS achieves similar accuracy and fairness, which verifies our hypothesis that the superfluous clusters would become useless. When M = 2, FOCUS even achieves the highest fairness, which might be because one cluster benefits from the shared knowledge of multiple underlying clusters. When M 1, FOCUS reduces to FedAvg, which does not have the clustering mechanism, leading to the lowest accuracy and fairness under heterogeneous data.
15

---

Under review as a conference paper at ICLR 2023
Table 9: The effect of M on Rotate MNIST when the number of underlying clusters is 3.
M=1
M=2
M=3
M=4
Avg test acc
0.929
0.952
0.953
0.953
Avg test loss
0,246
0.167
0.152
0,153
FAA
0.363
0.079
0.094
0.091
Agnostic loss
0.616
0.272
0.224
0.223
B CONVERGENCE PROOF
B.1 CONVERGENCE OF LINEAR MODELS (THEOREM 1
B.1.1 KEY LEMMAS
We need lemmas first before proving Theorem
Lemma 1. Suppose E Sm and the m-th cluster is the one closest to w Assume | (t)
w $
< 3 S minm'mmmm tm [m - w Then the E-step updates as
(6)
(t-1) em
Tem
(25)
(0) + (1
(t) Tem exp
- (B2 -02 a²
2(a + 3)r)82)
Remark. Our assumption of proper initialization guarantees that ||w w while Vm', have ['mm w 1l2 2 || [
[mmm'
Me = R a. Hence, we substitute B R a
and a 2 -r- A, which yields
(++1)
Tem
Ve Sm
(26)
cm
(1 Tem
exp( 2RA822
em
For M-steps, the local agents are initialized with 0 agent use local SGD to update its personal model:
Wm
Then for k = 1,..., K - 1, each
g (++11) fem 7):9em (9em) ((h)
7E V
e( m (1 (.
(27)
To analyze the aggregated model Eq. (6), define sequence of virtual aggregated models (kk)
(k)
Tem
em
(28)
Te'm
Lemma 2. Suppose any agent e E Sm has a soft clustering label Tem SGD updates uin by Eq. (2 if the learning rate TJs
(t+1) 2 p. Then one step of local
T82.
E
(k+1)
w 2/2 <
2m mm 2 Ellia((t+1 wit 112 A1 Ai.
(29)
= 4mm
52
+ 2 F( p), A2 16F(K 1)28 + +0 F((5 8202)
(30)
n
Remark. Using the recursive relation in Lemma 2 if the learning 7)s fixed, the sequence with
has a convergence rate of
E (((()) w 113 (1 2. 2 w nk(A1, 7A22-
(31)
16

---

Under review as a conference paper at ICLR 2023
B.1.2 COMPLETING THE PROOF OF THBOREM
We now combine Lemma Jand Lemma] 2 to prove Theorem |
The theorem restated below.
Theorem
With the assumptions I and 2, n. = (dd), if learning rate lj S min(
&
48
(C) Nem
1+ 1) exp( 2R5= Ve E Sm
(32)
2 jKT (Ill win l1 A) 2M
M EB
Eli Wmmm
w l1 I (1
O(K* ,o²).
(33)
M
2/T
where is the total number of communication rounds; T is the number of iterations each round; Tm
[Smll is the number of agents in the m-th cluster, and
(EK 1)6²
(34)
21y5--m
(mp(-2664A))
M
Proof.
We prove Theorem by induction. Suppose
π cm
(35)
1+ (M - 1) exexp(-3 -2R82 Dot)
E| W (t) -
-w n/,11 S 5(1 21/mm 82
Kt ([Iw - w;)) + A(11
207 82
)kt - exp(-2R6* -2R02A0t)
M
M
nB
+
(36)
1 (1
217 82 yk M
where = [16E8* K3 EK(8* + )8 + 452
Then according to Lemma] 1
(
T em
1++1)
(t) Tem
+ (1 - Tem) exp( 2
Tem
(37)
(38)
1 (M exp( -2R0" exp 2
(39)
1 + (M - 1) exp( 22 1))
We recall the virtual sequence of wm defined by Eq. 28 Since models synchronized after K rounds, the know (2 w/ and (((+1)
(++1)
_ We then apply Lemma to prove the induction.
Note that instead of proving Eq. (33). we prove stronger induction hypothesis of Eq. (36).
B (l w:m 11?
El wnn 1
(40)
< (1 207mpp0 3)x [Ell
w 112 M)((A + +11A2)
(41)
< (1 2m/mp622 K (11
2 82
)k (///1/0000
w 2| + A((1 217
)kl
M
M
BBB
+ 74 + 20122221111 (p) + +1² KA2
(42)
(1
2n 62 yk M8
2m 82
< (1
((+1)
11:100 (0) wi'll 2
M
2m
Aexp( (2 (1) 2nrmm02
+ A(1
(1-1)
)k 282 E(1
M
M
D1
20 82
B
+(1
)k
4mm2 + +n2 12
(43)
M
1 (1
2 63 jK
D2
17

---

Under review as a conference paper at ICLR 2023
Note that 1 1 p (M exp((222xp02)))
217'm 82
20
D1 & A(1
((+1) Acxp( - -2R408
)k E 1) exp( exp(122XA))))))) -2RD
M
M
2 82
< A((1
|(+1) exp
(44)
M
For D2 we have
2
nB
D2 S (1
)k
4m K + """ +
8007)
M
[1
2m M
K
BB
(45)
1 (1 2 8
Finally combine Eqs.
43 to
45
E| ((+1)
-will
wmlll (1
2m 8²
(0+1) Ium
winl + 1(1
2 8²
(1+
exp(-2210
Do + 1))
M
M
nB
(46)
20 M
)k
Since is trivial check that both induction hypotheses hold when 0, the induction hypothesis holds. Note that K 2 1,
so
BB
M5 E3
nB
S
2MKr+
O(K2,8
(47)
(1
2m
82
2VT
M
Combining Eq. (46) and Eq.
(47)
completes our proof.
B.1.3 DEFERRED PROOFS OF KEY LEMMAS
Lemma 1.
Proof. For simplicity, we abbreviate the model weights Wm by wm in the proof of this lemma. The n-th E step updates the weights II by
Tem
(2+1)
Tem exp
E, N) (Wm Tx - y)
(48)
Σ ml π em
expl E E De (wm Tx y)
SO
10) Tem exp
-Ilw (1)
14 12
π
em
(++1)
Σ ml Tem exp
(+)
- |lw (1)
Me 1282
(49)
(t) Tem exp - (33 2))
(50)
Tem exp(e(( - 2)22 ) Σ mm (11)) exp(-(a++ ()
(t)
(t)
(51)
π Tem
+ (1 TTm) exp - (32 a² 12(a +2(a+ 33r)62
Lemma 2.
Proof. Notice that local datasets are generated by X, ~ NO0 x and ye XaHte + 6, with <e (0, a)). Therefore,
18

---

Under review as a conference paper at ICLR 2023
1100 (R+1)
-w == = 1lumm
Wm 11199 1|
(52)
m
w 176 Ne
2
Σ
X X Xc((f Me) +
2m
Σ
Tem X Cel 112
ne
(53)
= |100 win - 1x + ni. 11 - 9x112 + 27kh (wo!
w - 9k.9k
9h
(54)
where 9x- no
2. Ee Tem B(X Xx) p.). Since the expectation of the last term in Eq.
54 is
zero, only need to estimate the expectation of ||@m w n/9x/ and || ga 11?
(R)
|| (8) um 91191111
||:0 w 112 +
1
Σ
Tem (Xx X.)1l0e. - Mell?
47
Σ T
(20 m
wmn 16 X Xe) - -me))
n
The
11
w 11 + on
Tem 10th melll
4n (10/))
wm Σ
Tem 8² (0 [(a))
G
(55)
C1 4mp Σ
Tem (10
(B( 8 (0(( pe)) 4nk Σ
Tem (A(
wn (2(((()) (ee) (56)
< 4
Tem |1
-0 + 48 116 Σ
Tem (10b))
Mell 4m1.02
Tem 10(h) Mell 1l?
41
Σ Tem (Mte
W ((h) ue)
(57)
Since 17 I 1
152.
(k) w - g 1|2
(58)
/ (((h)) wm1 + (85'n n/= 4m) Σ Tem TemBB1000 B|(0(() -ell2 Σ
Tem EI| El ((4) 112
C22
(59)
E (0(
w1 - 2m
Tem E|(((t))))) - Hell + Σ Tem BlmmB112ff - ((k) 1|2 + C2
(60)
Note that
Σ Tem E
e mell 1
(61)
Σ Tem (kk)
em | 1
Σ
[((0)) Mell
(62)
eESm
S
Σ eESm
Tem (E (E())(
w/ 1|2
+ 2r + 2
Tem ((H) meell
(63)
Σ
Tem (E 16 (k) w 1|2 + E
(k)
((k) ||
+ 2r + 72) + Σ
Tem B|[((k)
cm - Me 2|2
(64)
m
S.
eg
19

---

Under review as a conference paper at ICLR 2023
And since Wm (k)
E EE
Tem Temoene Oems have
4E
T Tem
0 2 v
4E Σ
Tem Tem|luj 11
-0( |
cm
(65)
Tem (K - -1 Σ
The 31 x² X (c( - pe)ll
(66)
v 16n E(K - 1
(67)
Thus,
E (1)) win - -1199il' S
2 (1 - 29).0
Tem [E| E| (k) - wmll 112 167/ E(K
161 - 1)
-2
Σ
Tem
EE 1 (44 - Mell2 411:02 02 Σ
Tem (0 Mo: Mp win)
cm
cgSm
C
(68)
Since
C3 S 2m 62 Σ
Tem 1iee w 4n Σ
Tem 11 Mellallme umll2
(69)
cgSm
< 21 FB p) + 5m
(70)
have
El B (1) - - < 02 7mP) 7 -w;
02 (71)
Notice that
E Bl - gxll2
Tem ll? X. - [XX - -Hell? +E Σ
Σ
o Tem X TT EE ||?
n
2
((dne)
O(dne) 0²
8z F.
(72)
n²
n²a
so
B 1100+++11 (k+1)
win 112 < (1
21/ 'm 11 -w---llll w
mi + A
(73)
where
A = 7m
Tmn + -222E(1- -p)
(74)
and
A₂ 16E(K 1)28* + +0 d )E(8* + 800)) mee
(75)
B.2 CONVERGENCE OF MODELS WITH SMOOTH AND STRONGLY CONVEX LOSSES (THEOREM 2
Here present the detailed proof for Theorem
B.2.1 KEY LEMMAS
We first state two lemmas for E-step updates and M-step updates, respectively. The proofs of both lemmas are deferred to the Appendix B.2.3
20

---

Under review as a conference paper at ICLR 2023
Lemma 3. Suppose the loss function Lp, (0) is L-smooth and p-strrongyy convex for any cluster If If
w
VBtVL
vER
r
A for some > 0, then E-step updates as
(t)
Tem
Tem
(76)
(8) Tem +
Tem
(t)
(xp(--RA)
For M-steps, the local agents are initialized with 0em agent use local SGD to update its personal model:
Wm
Then for k: 1,...,
...,, K 1, each
(k+11 = -0em TJ:Aemm (Dem)
C(k:)
em
MJ V
elba.n ).vl)
(77)
To analyze the aggregated model Eq. 66.
we define a sequence of virtual aggregated models w!!
Tem 0 Oem
W (k)
(78)
Tm
Lemma 4. Suppose for any agent e E Sm, its soft clustering label Tem SGD updates wh by Eq. (79. if the learning rate 172 S 2(x+L))
(t+1)
p. Then one step local
1o w 112 s (1 Ti Ao E1
w 112 AK + A2.
(79)
where
27mPpL
Ao + L
(80)
2G
G(1 P)E
A = 2
+
(AL +
+
(81)
1
4E(K - G)LGL2
EO²
1 A2
(82)
The
(k+1) has Remark. Using this recursive relation, if the learning rate m7 is fixed, the sequence w convergence rate of
(K) w 2|2 & (1 - 7700) "Bl wf,,ll nt(AI + mA2)..
(83)
B.2.2 COMPLETING THE PROOF OF THEOREM
2 Suppose loss functions have bounded variance for gradients on local datasets, i.e., E( [ y; VC, (0) & o². Assume population losses are bounded. i.e., L. e G, Ve [E]. With initialization from assumptions 3 and 4, if each agent chooses learning rate
Theorem
77 & min( L)++ } the weights (II, W) converges by
(T) T
+ (M 1) exp( -appp--RAATTT Ve E Sm
(84)
Tem
E Blll (o (T) - " 12 < <1 (1- ([ww - w", 12 B) O(Kr) ME di m. (85)
where T is the total number of communication rounds; K is the number of iterations each round; I' 1mml is the number agents in the m-th cluster, and
2 uL B = GMTE(44 4L
p(++L)
(86)
M μ L' (A-1 exp( pRAa))
21

---

Under review as a conference paper at ICLR 2023
Proof. The proof is quite similar to Theorem for linear models: follow induction proof using lemmas 3 and 4. Suppose Eq. (84) hold for step And suppose
Elju - win 12 - (1-nA) K* "1l
1 12) B((1 (1)) R (ap((-RRAOl))+ 1- (1 11-11111110 nA)K
7C
(87)
where
2G + (2 C An
EKo²
+ 0(())) +
(88)
The
Then for any E Sm,
(t)
T cm
1++1)
2 (1)
Tem
(89)
Tem
+ (1 Tem exp( .RA,))
(90)
(M - expx (R exp(-
(91)
+ (M- - 1) exp((pRRso( + 1))
We recall the virtual sequence tmm defined in Eq. 78 Models are synchronized after K rounds of local iterations, (++1)
um [K) Thus, according to Lemma 4
um # win ll2 = Bl(@0 w 112
(92)
S (1 - -1)) K "!!""
w 112 + (A(Ai + 1/22)
(93)
$ (1 - nu K (11 nA) xt (E|| w'. 12) + B((1 - nA)* Kt - -ep((-)RAut) + 1 (1 - nA)K
7/C
+ +n((A + nAu)
(94)
(1 (2))(+1)( w (1- (1-11141) nA)* B(11 nA)* Kt
exp( + GK(1 E)
(4L
6
1
2G I (1 nA)K (2 Lr
1/C
+ (1 (1-nA) n))**
+ 0(2)) 12
(95)
P
For F1, we use the fact that
((+1) Fem
21 (M - (1-))xxpp-uRRAA +1))
1 1+ (M exp - (uRAo(t+ 1))
SO
G(M (exp(==RAst)
6
Fi S (1 mnn) K (((BB(11 BB11B((11))) -xx((--epppRAAippp +
(4L +
/1 + T.
(96)
= (B(111)A)(tHH expl exp(-1RRdn))
(97)
For F2, we have
9/C
2G 0(22))
77 KE
Fg 51 -1--11 n/)* K
1- (1 - -nAR + (2 Lr
V P
+
(98)
TCC
(99)
1 (1 a))K
Combining Fi and F2 finishes the induction proof. Moreover, since T > 1, we have
c/C
< C
O(Kr) ME3
x²
O(K3
(100)
A
VT n
Combining Eq. 87 and Eq. (100) completes proof.
n
22

---

Under review as a conference paper at ICLR 2023
B.2.3
DEFERRED PROOFS OF KEY LEMMAS
Lemma 3.
Proof. According to Algorithm
D
(E)
(1+1)
Tem
(101)
Tem + Emisin sm T (1)
(5)
Bl(x, yi w - Ex( x, yı 20 umm
Temm
exp
(1)
T cm
(102)
(8) + (1 - Tem exp
maXx' +m (Cp. (wml) ((t)))
Lp (wm
Since Lp, is L-smooth and u-strongly convex,
Lp. (w Lp. (10
(0)
5
L
0,11
1
(1)
0211
2
L
ViR
/R
$
A)
VI + VL + +A)²
2
V
VL
L -- HL A2 -uRA.
S VLVLRR
(103)
Combining Eq. 102) and Eq. 103
completes our proof.
Lemma 4.
Proof. We define gm (k)
L Eo Tem nr
2i=1 Vi(ho.n (xe2), ).ve))) and (b) = = Tem V.((O.))
El w
112
EE| m
w 7mmm (k) 112
(104)
E
(R)
wn - -m:0m (k) 1|2 + El9 1
m
+ B (k) w mm
(k) g/hh
9m
(k))
(105)
E i
(k) m
w - T: 112 + 19
(k)
g 11.
(106)
The first term can be decomposed into
1 (k)
w m.
1
= | (k) w 11 + 11110/ (1) 1|2 277 (10
w Fm g(()))
(107)
Note that
E Σ
|1
12 <
Tem V (P(
(108)
E
(wi (k)
win (1%
Tem
(10
0 cm
V (0(
Tem (0 w V (0( ))
(109)
We further decompose the two terms in Eq. 109 by
2((
(k)
0 (b) eom
V (o(()()
[1
01 + 7/K V (L
(110)
and
(0(k) wi; V Le (A((E))
(0(A)
w V L. (Q(k))
V (L + VL 112100
(111)
w 112 +
V cm - (w
- w.
14 + T.
cm
#
(112)
23

---

Under review as a conference paper at ICLR 2023
Therefore,
H.L.
B (k+)) m W. 112 = -E (0) m
w 11
27th
H + L Σ
T Tem
B ((
w 11 + Σ
T Tem E B 11
E1
2n
Tem B VL. (0 Σ
2m
Tem VLe (0 (0th
(wm))))
Eg
+ 27p; IE Σ
Tem Tem|l0
wmlll
(V + 7 || (1)
Im
kk)
112
E4
(113)
E = Bll
H.L 2116
1e + T. Σ Te 11:0
w 11 + Σ
Tem (0
0 0 I1?
2 2mppLpim
BBllum -w 112 + Ez.
(114)
14 + I.
E2 E Σ Tem [(0hh) 0.6)1 11
E Σ Tem [1
(0)
O(k)) em
+ (0(h) (k) )1?
E
Tem [1
)1
k-1
Tem (K- - 1]
nhe
2 $l1 20())))
k==0
2n E(K - 122
(115)
1
Eg 22 Σ Tem (nh
7kk
][ (0(
27k (V. (V.())
(0()) VLe(w))) 77k
4 ( 112
# L
+
1 +
2q.EE Σ Tem (1/ 1 [L. +
V (0! ( )12
(V ( (L
2( L)
p + L
1 L.
L
2G Nem pll + L.)
6mp Σ
Tem
6nk
1 + T.
e.S..
egSm
G(1 E) p( + L))
< mm,0pp)) + 6n
(116)
E1 = 1 Σ
T Tem 10th) ww
(ww + 21T
Σ
Tem
cm will22 V
(w 1l
e
egs
2G
2G
< 2mk 2m Lr V
+ 2mja - E)L
(117)
24

---

Under review as a conference paper at ICLR 2023
Fs
199m (8)
The Vi(he.m (.()).(())) ((
cm ||
S 1
Σ
Tem
Be
S 1/2
E
(118)
ne
Combining Eq. 114) to Eq.
118
yields the conclusion of Lemma 4
C FAIRNESS ANALYSIS
C.I PROOF OF THEOREM 3
Proof. Let the first cluster mi contain agents pr,.... ME--, while the second cluster contains only the outlier pag. Then, for I,..., E 1,
Ee (Wm,)
82
Me
e'
Me
<
8
(119)
E
And for the outlier agent, the expected output is just the optimal solution, so
{ = 0
(120)
As result, the fairness of this algorithm bounded by
FAAfocuu
max (LL, W) - (L1, W) s 82,2. [E
(121)
E Me so
On the other hand, the expected final weights of of FedAvg algorithm is Wang = = the expected loss for agent shall be
((a.))P. = (0. 104 + x²'xx)² o² + 501 - 1ill (122)
The infimum risk for agent t is of. and after subtracting it from the expected loss, have
ε (Warg)
= 5² 1|111 Ta|
(123)
E
= 5
111
|2
(124)
E 1
|||| PE 2
S 82 r
+
(125)
E 1
R +
R
S (p
)2
62 (r+
(126)
E
E
However for the outlier agent,
(n(
82
|4 Till²
(127)
E
Σ M
=
HE
(128)
E
E
2
E
1
2
82 8222
(129)
E
Hence,
R22 - 2) (
22 12)
F.AAugg (P) En(Warg) Ex(wagg) -82
(130)
25

---

Under review as a conference paper at ICLR 2023
Remark. When there are E > 1 outliers, similarly derive FAA for FedAvg algorithm:
ExR
El ((Wao)))
S (r
)
(131)
E
E Ek
Ex
(g(Wavg) 2 28
R.
r)²
(132)
E
F
so as long as Ea <
E 2
FAAnng 2 Er((ang))
E1 (Wavg) 12)
(133)
The FOCUS algorithm produces result with
& {10m)
5
(134)
(g((m)) 5222p
(135)
Hence we still have
FAA 88422.
(136)
C.2 PROOF OF THEOREM 4
Proof. Note that the local population loss for agent i with weights is
(,( / pile,
(137)
Thus,
(C,(07) (,(0,) (1((t,,)- p) {(Jo; (1)) ddddy
(138)
$ SG. |I ps ddddy & Gr.
(139)
Hence,
(())) < L,(07) + Gr S k,())) - Gr < (,,) + 2Gr.
(140)
For the cluster that combines agents {L...., E 1} together, the weight converges to 0' - DE-1 0g. Then Vi 1,... E the population loss for the ensemble predic- tion
E-1 1-1 0z
(0, = La
(141)
E -
T-1
$ T Σ
2,07))
(142)
j=1
2Gr
$ 2.,)0) +
(143)
E -
Therefore, for any i= = 1,..., T 1,
E, V 2Gr E 1'
(144)
Since Er II) 0,
2Gr
Focue (W, II) <
(145)
Now we prove the second part of Theorem 4 for the faimess of Fedavg algorithm. For simplicity,
we define B = 2Gr in this proof. Also, we denote the mean all optimal weight Σ,= 0;
and Æ
E-1
ΣB-10 0r 0'
26

---

Under review as a conference paper at ICLR 2023
Remember that assume loss functions to be L-smooth,
L 0 1 0.11
Cx(()) S Lx(00) + (VL=(0)),
(146)
Taking summation over 1.... E we get
E-1
E-1
L E-1
LE 2 E
1
CE(O,)
(VLE(O')
Σ (0. 1)
Σ
0 8&ll²)
(147)
E-1
I E-1
= E-1 1
LE(0,)
2 Σ
0 - 0.113)
(148)
LBB
2 (0f + R
(149)
p
The last inequality uses the j--ttrongly convex condition that implies
B2 L.(') (.(0,) 2 " 0 - 0.11
(150)
2
By L-smoothness, we have
CE(B) Cx(0) (VLE(O), -) + 110 01 CE(0E) S (6) + (V (0) 0: 0
(151)
L
10 0| 2
(152)
Note that Ø = 0'+(E-1)0 take weighted over the above two inequalities to cancel the E
dot product terms out. We thus derive
(E 1)Lx(()) + (E()))
[ - 1)]10'
012
L 0
1
(F(()= >
2
(153)
F
E 1
LB
8111
R
+ (87p)
(154)
2E
Note that LF(+) is u-strongly convex, which means
LB
2 Lo(
LE(0E) 2 1100 0'122
(155)
1
2
so
L
E -
1
LB
(0) (1
(R
(E(
(156)
F.F.
E
And
L
E
LB
Eσ(θ) 2 (1
R
(157)
nE
E
On the other hand, for agent i 1,..., E 1 know
L
(i(0) < L,(0') + (V., 0
8¹)
110
812
(158)
2
By L smoothness,
2B
VC,(0)) 0i1 < L
(159)
So
2B
2(R
LB
L(R LB
C.(0) < C,(77) + B L
#
(160)
1
F.
F.F.2
27

---

Under review as a conference paper at ICLR 2023
L(R LB
21. μE
LB P )
( - B +
B(R
(161)
μ.a²2
In conclusion, the fairness can be estimated by
FAAaug (P) 2 ( (
(162)
F. 111
(1+ L(F -1)
1)
1
2L μE
I.
R
B
B(R
B)
(163)
E μE
PE
2
C.3 PROOF OF DIVERGENCE REDUCTION
Here prove the claim that the assumption CE((?) (E(0%) 2 is implied by lower bound of the H-divergence (Zhao et al. 2022).
LR
DH((,,PE) 2
(164)
4p
Proof. Note that
(P PE)
min
(c) + CE(())
+2((c0(0)) + (x((0)))
+ [c((0))
(165)
2 0
2 Cel 0% + +00 +)+ LE(
fr + (++0)) )) 1 (Cc.00)) + L
(166)
2
2
08 8
<
x (24)
112 x 2)
(167)
2
2
1
0Н1
(168)
Therefore,
1110% --
CE(0.) - (E(0))
>
(169)
2
# DD (P PF) R.
(170)
2
L
D EXPERIMENTAL DETAILS
D. EXPERIMENTAL SETUPS
Here we elaborate more details of our experiments.
Machines. We simulate the federated learning setup on a Linux machine with AMD Ryzen Threadripper 3990X 64-Core CPUs and NVIDIA GeForce RTX 3090 GPUs.
Hyperparameters. For each FL experiment, we implement both FOCUS algorithm and FedAvg algorithm using SGD optimizer with the same hyperparameter setting. Detailed hyperparameter specifications are listed in Table [0] for different datasets, including learning rate, the number of local training steps, batch size, the number training epochs, etc.
D.2 ADDITIONAL EXPERIMENTAL RESULTS
Histogram of loss CIFAR. Fig. shows the surrogate excess risk of every agent trained with FedAvg and FOCUS on CIFAR dataset. For the outlier cluster that rotates 180 degrees (i.c., 2rd cluster), FedAvg has the highest test loss for the 9th agent, resulting in high excess risk of 2.74.
28

---

Under review as a conference paper at ICLR 2023
Table 10: Dataset description and hyperparameters.
Dataset # training samples
# test samples
E
size
learning rate
local training epochs
epochs
MNIST
60000
10000
10
6000
0.1
300
CIFAR
50000
10000
10
100
0.1
200
Yelp/IMDB
56000/25000
38000/25000
10
512
5c-5
Cluster
Cluster
Cluster
Cluster 2
Test Losses
Index of Client
Index of Client
Figure 3: The excess risk of different agents trained with FedAvg (left) and FOCUS (right) on CIFAR dataset.
In addition, the agents in 1st cluster trained by FedAvg are influenced by the FedAvg global model and have high excess risk. On the other hand, FOCUS successfully identifies the outlier distribution in 2nd cluster, leading much lower excess risk among agents with more uniform excess risk distribution. Notably, FOCUS reduces the surrogate excess risk for the 9th agent to 0.44.
Comparison with existing fair FL methods. We present the full results of existing fair federated learning algorithms on our data settings in terms of FAA. The results in Tables IT and 12 show that FOCUS achieves the lowest FAA score compared to existing fair FL methods. We note that fair FL methods (i.e., q-FFI. (Li et al. 2020b) and AFL (Mohri et al., 2019) have lower FAA scores than FedAvg, but their average test accuracy is worse. This is mainly because they mainly aim to improve bad agents (i.e., with high training loss), thus sacrificing the accuracy of agents with high-quality data.
Table 11: Comparison of FOCUS and the existing fair federated learning algorithms on the rotated MNIST dataset.
q-FFL
AFL
FOCUS
FedAvg
q= 0.1
Q 3
q
q == 10
X
0.01
Avg test accuracy
0.953
0.929
0.922
0.861
0.770
0.731
0.685
0.885
Avg test loss FAA
0.152
0.246
0.269
0.489
0.777
0.900
1.084
0.429
0.094
0.363
0.388
0.612
0.547
0.419
0.253
0.220
Comparison with state-of-thh-art FL methods. We compare FOCUS with other SOTA FL meth- ods, including FedMA (Wang et al.) 2020). Bayesian nonparametric FL (Yurochkin et al. 2019) and
FedProx (Li al. 2020a). Specifically, the matching algorithm (Yurochkin al.
2019) is de-
signed for only fully fully-connected layers, and the matching algorithm in (Wang al. 2020 is designed
for fully-connected and convolutional layers, while our experiments on CIFAR use ResNet- 18 where the batch norm layers and residual modules
not considered in (Wang et al.
2020 Yurochkin
et al. 2019). Therefore, we evaluate (Li et al. 2020a; Wang et al.) 2020: Yurochkin et al. 2019) on MNIST with fully-connected network, and (Li al. 2020a) CIFAR with ResNet- 18 model.
The results on MNIST and CIFAR Tables and show that FOCUS achieves the highest FL. methods.
average test accuracy and lowest FAA score than SOTA
29

---

Under review as a conference paper at ICLR 2023
Table 12: Comparison of FOCUS and the existing fair federated learning algorithms on the rotated
CIFAR dataset.
9-FFL
AFL
FOCUS
FedAvg
== 0.1
0 0=
9 =
3
5
9 == 10
X = 0.01
Avg test accuracy
0.929
0.908
0.897
0.833
0.778
0.699
0.565
0.866
Avg test loss FAA
0.217
0.262
0.306
0.704
0.876
1.139
1.263
0.466
0.365
0.537
0.661
0.542
0.525
0.494
0.421
0.619
Table 13: Comparison of FOCUS and other SOTA federated learning algorithms the rotated MNIST dataset.
FedProx
Bayesian Nonparametric
FOCUS
FedAvg
FedMA
Jr
/ = 0.1
/ == 0.01
Avg test accuracy
0.953
0.929
0.908
0.927
0.929
0.753
0.517
Avg test loss FAA
0.152
0.246
0.315
0.252
0.246
0.856
2.293
0.094
0.363
0.526
0.378
0.365
1.810
0.123
E BROADER IMPACT
This paper presents novel definition of fairness via agent-level awareness for federated learning, which considers the heterogeneity of local data distributions among agents. We develop FAA fairness metric for Federated learning and design FOCUS algorithm to improve the corresponding fairness. We believe that FAA can benefit the MI. community as a standard measurement of fairness for FL. based on our theoretical analyses and empirical results.
possible negative societal impact may come from the misunderstanding our work. For example, low FAA does not necessarily mean low loss high accuracy. Additional utility evaluation metrics are required to evaluate the overall performance of different federated learning algorithms. have tried our best to define our goal and metries clearly in Section 3 and state all assumptions for our theorems accurately in Section to avoid potential misuse our framework.
Table 14: Comparison of FOCUS and other SOTA federated learning algorithms on the rotated
CIFAR dataset.
FedProx μ 0.1
FOCUS
FedAvg
J 1
/ 0.01
Avg test accuracy
0.929
0,908
0.910
0.922
0.925
Avg test loss
0.217
0.262
0.282
0.245
0.239
FAA
0.365
0.537
0.698
0.700
0.654
30


Reviews:
[{"review_id": "p_v8j_vQrBi", "reviewer": "Reviewer_MUHj", "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 paper studies fairness in federated learning where clients have heterogeneous local data. In particular, the paper introduces a new fairness definition/measure to leverage the excess risk at each local client. Subsequently, the paper proposes an algorithm that provably outperforms FedAvg in terms of this new fairness definition under certain conditions. Empirical results on several real datasets against some baselines are provided.", "summary_of_the_review": "The motivation for the problem (i.e., fairness in FL) studied by this paper can be strengthened. There seems to be some mismatch between what is mentioned in the introduction and the main paper (e.g., contributions of agents are not explicitly/clearly defined). The approach (via Bayes optimal error) and setting (data heterogeneity) can be justified better. Overall, there is certainly merit to this paper, but in its current form, it is not ready to be published.", "strength_and_weaknesses": "### Strengths\n\n- The exposition is generally clear in terms of setting, algorithm, theoretical results.\n\n- Theoretical guarantees (both convergence and fairness analysis) are provided.\n\n- Several real datasets are adopted in experiments.\n\n\n### Weaknesses\n- The motivation for fairness in federated learning can be strengthened. To elaborate, the abstract does not seem to motivate why fairness is important or necessary in FL. Similarly, the introduction does not seem to clearly motivate why fairness is important in FL.\n\n- The specific design choice for fairness via agent-awareness (i.e., the equity among the difference between their excess losses) can be motivated better. To elaborate, why is equity in any form a good notion of fairness? What are the motivating use cases for this notion of fairness? \n\n- Related to the above point, in introduction it says\n    > \"we aim to define and enhance fairness by explicitly considering different contributions of heterogeneous agents\" \n    \n    But it seems the heterogeneity is indirectly defined through the distributions of datasets instead of _explicitly_ via some concrete quantity to measure the heterogeneity. Moreover, it does not seem to provide a clear/explicit definition for the contributions. Following this, how does this fairness relate different levels of contributions of the clients?\n\n- The usage of Bayes optimal error can be elaborated better. For instance, how does Bayes optimal error affect the analysis, especially for regression-based analysis? What would happen if Bayes optimal error is not used? A subsequent question, how are high-quality and low-quality data defined?\n\n- The formalization of the heterogeneity of data can be justified better. In particular, the features of the datasets are assumed to be generated from Gaussian distributions with different means but identical and isotropic covariances. And each dataset has a true underlying mean vector. Is there justification/motivation for this setting (e.g., real use-cases where data are generated in this way, or approximately)? Then, is clustering performed w.r.t. the full model parameters (treated as a high-dimensional vector)? If so, how will the clustering affect the FL performance in such high-dimensional space? \n\n- It seems some other related works (listed below) might also be relevant and can be empirically compared.\n\n#### References\n\nTian Li et al, 2021, ICML, Ditto: Fair and Robust Federated Learning Through Personalization.\n\nXinyi Xu, Lingjuan Lyu, Xingjun Ma, Chenglin Miao, Chuan Sheng Foo, and Bryan Kian Hsiang Low. Gradient driven rewards to guarantee fairness in collaborative machine learning. Advances in Neural Information Processing Systems, 34:16104–16117, 2021. \n\nI believe the second reference is included in the paper", "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": {}}, {"review_id": "O1FTN6gOCGC", "reviewer": "Reviewer_wM5N", "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 studies the problem of training fair models in federated learning with heterogeneous agents. The authors proposed a new fairness metric which is the maximal difference of excess risks for any pair of agents. The authors then proposed an algorithm which is based on the Expectation-Maximization algorithm, that clusters the similar agents into groups and minimize the fairness-violation loss.\n\nTheoretically the convergence guarantee for the proposed algorithm was provided for linear agents, and non-linear agents with smooth and strongly convex loss functions. Empirically the authors compared the proposed algorithm with FedAvg, q-FFL (Li et al., 2020b) and AFL (Mohri et al., 2019), showing that the proposed algorithm performs better under the proposed fairness criteria.", "summary_of_the_review": "Overall this paper studies an important problem ---FL with heterogeneous agents. The proposed fairness metric and algorithm are quite intuitive. The experimental comparisons are missing some necessary evaluations. I also have some concern on the scalability of the proposed approach.\n\n\n---------\nPost-rebuttal: I thank the authors for the detailed response to my questions and concerns! The additional clarifications and comparisons addressed my concerns on the scalability and computation cost of the proposed methods. Therefore I'd like to improve my score based on the author feedback.", "strength_and_weaknesses": "Strength:\n- Learning fair models in federated setting with heterogeneous agents is an important research problem. The proposed fairness criteria minimizes the maximal difference of excess risks for any pair of agents which is a natural criteria to use.\n- The FOCUS is based on the Expectation-Maximization algorithm which is very intuitive.\n- Both the theoretical convergence guarantees and experimental comparisons are studied carefully, and the experimental results demonstrate the effectiveness of the FOCUS algorithm in minimizing the proposed fairness loss.\n\nWeakness:\n- First concern is about the scalability of the proposed fairness criteria and algorithm. The proposed metric minimizes the maximal difference of excess risks for any pair of agents, whose evaluation requires looking at all the pairs of agents --which grows exponentially with the number of agents. It seems that even evaluating such a fairness criteria is computationally-expensive with a large number of agents.\n- Following the scalability concern, the EM algorithm also tends to have a slow convergence.\n- The experimental comparisons are comparing the proposed algorithm ---which is designed to minimize the proposed fairness loss ---to other methods which are not designed for that. I think a fair set of comparisons should include the performance of FedAvg if that is also using the clusters that FOCUS ends up using; and evaluating the results of FOCUS on the fairness criterion proposed in other works, e.g. the agnostic loss in AFL (Mohri et al., 2019). Moreover the runtime and computational costs should be compared as well. From the current evaluations, it is hard to conclude that FOCUS out-performs the existing methods. E.g. FedAvg is not using any clustering and outputs one single model; but FOCUS is allowed to return M models to the agents.\n\nTypos:\n- Equation (2), $\\Epsilon$ missing the subscript $e_1$", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "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": {}}, {"review_id": "Au1WBTyshmX", "reviewer": "Reviewer_p3Qb", "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": "The paper considers a federated learning setting. The idea and novelty of the paper consist in taking fairness considerations into account. Namely, agents that contribute a lot of/little data or lower/higher quality data should not be treated the same way. ", "summary_of_the_review": "I think this is a good paper that studies an important problem and provides a comprehensive (both theoretically and practically) solution to said problem, and as such recommend acceptance into the program", "strength_and_weaknesses": "Strength: \n- the motivation of the paper is clear, and important. It is unfair to give the same outcomes and benefits to agents that barely contribute to the model learned by the federated learning algorithm and simply free-ride. Further, the presence of agents with low-quality data can further compromise the performance of agents with high-quality data. \n- the formal definition of fairness is an interesting proxy to address this issue, by looking at the excess risk of the model seen by population e compared to the best model population e could train on their own data. In turn, if this excess risk is low, it guarantees that a population with low-quality data sees a model $\\theta_e$ that cannot be (much) better than the low-quality model they could have trained themselves. \n- the techniques are interesting, with a 2-step approach: i) clustering agents with similar data distribution together (so that agents with accurate/high-quality data are for example clustered together), then ii) give different weights to different agents as a function of their cluster in the loss minimization problem\n- The authors provide theoretical statement showing that their algorithm performs well for a reasonable/common class of losses (linear + smooth and strongly convex)\n- The authors provide convincing experiments showing that their approach leads to better fairness, but also overall model performance, than previous work. The results are especially good when the data is synthetically generated according to the assumptions of the paper, but the experiments also show that their approach does better than FedAvg and previous work even on real data. \n\nWeaknesses:\n- I found the notations of the main theorem a bit confusing, with K being the number of rounds (which is what I think would typically be called T), and T the number of updates in each round. \n- Theorem 4 and the fairness analysis is a bit hard to understand in the case of smooth + strongly convex losses. It is also a bit weak in that i only looks at 2 clusters. However, this weakness is partially made up for through the experiments. \n- It is possible I missed this, but the authors seem to assume that M is known in advance, since it is provided as an input to the algorithm. How can one estimate/upper-bound the number of clusters? This seems that it would require to run the clustering first, before actually knowing M, and evaluating how close the data distributions are in each cluster. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": {}}]

Author rebuttal:

Decision: Reject