FedEBA+: Towards fair and effective federated learning via entropy-based model

Firstname1 Lastname1equal,yyy
Firstname2 Lastname2equal,yyy,comp
Firstname3 Lastname3comp
Firstname4 Lastname4sch
Firstname5 Lastname5yyy
Firstname6 Lastname6sch,yyy,comp
Firstname7 Lastname7comp

Firstname8 Lastname8sch
Firstname8 Lastname8yyy,comp

yyyDepartment of XXX, University of YYY, Location, Country
compCompany Name, Location, Country
schSchool of ZZZ, Institute of WWW, Location, Country

Firstname1<EMAIL_ADDRESS>Firstname2<EMAIL_ADDRESS>
Machine Learning, ICML

"Ensuring fairness is a crucial aspect of Federated Learning (FL), which enables the model to perform consistently across all clients.
However, designing an FL algorithm that simultaneously improves global model performance and promotes fairness remains a formidable challenge, as achieving the latter often necessitates a trade-off with the former.

To address this challenge, we propose a new FL algorithm, FedEBA+, which enhances fairness while simultaneously improving global model performance. Our approach incorporates a fair aggregation scheme that assigns higher weights to underperforming clients and a novel model update method for FL. Additionally, we provide a theoretical analysis of fairness and demonstrate the convergence rate of our algorithm, and experimental results reveal that FedEBA+ outperforms existing state-of-the-art fairness FL methods in both fairness and global model performance.

§ INTRODUCTION

Federated Learning (FL) is a distributed learning paradigm that allows a group of clients to collaborate with a central server to train a model <cit.>.
To learn models without any data transfer,
clients must process their own data locally and only infrequently communicate some model updates
to the server which aggregates these updates into a global model <cit.>. A major challenge for FL is to treat each client fairly to achieve accuracy parity <cit.>, in which the performance of the trained model is similar among clients. However, due to data heterogeneity, intermittent client participation and system heterogeneity, the model is prone to be unfair <cit.>, which decreases FL's generalization ability and hurts clients' willingness to participate <cit.>.

While there are some encouraging results of addressing fairness challenges in FL, such as objective-based approaches <cit.> and gradient-based methods <cit.>. To be fair, these methods will inevitably sacrifice the performance of the global model. Meanwhile training a good global model is the core goal of FL <cit.>. Although <cit.> have achieved good results in balancing fairness and robustness of the global model, they both need personalized models and are ineffective in improving the performance of global model in non-attack scenarios.
Hence, this inspires us to think about the following problem:

Can we develop an effective algorithm in FL (non-personalized FL) that significantly improves FL fairness without compromising global performance, accompanied by theoretical guarantees?

To this end, we propose a novel $FedEBA+$ algorithm as the first attempt on addressing this problem, which consists of a fair aggregation method and a new model update strategy.
By leveraging the principle of constrained maximum entropy,

1) FedEBA+ assigns
underperform clients with high aggregation probability, thereby making the aggregated model biased towards these clients, resulting in uniform performance among clients.
In particular, our aggregation strategy is called $FedEBA$ with $p_i \propto e^{F_i(x)/T}$,
which comes from the maximum entropy distribution.

Maximum entropy has been successfully employed in furthering fairness in data preprocessing <cit.> and resource allocation <cit.>, as it reduces the amount of prior knowledge of distribution and thus eradicating any inherent bias <cit.>. However, it remains untapped in promising fairness in FL, in which fairness is ensured by integrating constraints into the model to promote maximum entropy while satisfying specific FL fairness conditions.

Figure <ref> shows that compared to existing aggregation fairness aggregation algorithms, such as uniform aggregation (FedAvg) or q-fairness reweight aggregation (qFedAvg), our entropy-based aggregation (EBA)We introduce EBA here. better ensures fairness. The computational details are in Appendix <ref>.

2) FedEBA+ presents a novel model update method for FL which incorporate the global model alignment and fair gradient alignment, thus improving the global model's performance while enhancing fairness.

Thus, combining the proposed aggregation and model update methods, we develop an Entropy Based Aggregation plus novel model update algorithm for Federated learning termed FedEBA+.  It is worth noting our proposed algorithm is the first non-personalized FL
Since Ditto is a proposed method to balance the fairness and model robustness, that latter can be seen as an improvement of global model under setting of user attackWe also have emphasized this in our problem/motivation....still, what's the the advantage of non-personalized FL?The implementation of state-of-the-art personalized federated learning typically necessitates distinct models for both the global and local contexts, however, the limited data availability to the user can impede the fine-tuning of the local model, thereby exacerbating the issue of undergeneralization, resulting in poor performance of the global model.I got it, mention non-personalized seems always strange..I propose to delete this sentence
algorithm that simultaneously guarantees the performance of the global model and the fairness among clients, with theoretical guarantees.

A toy case of two clients with regression models $F_1(x)=2(x-1)^2$ and $F_2(x)=\frac{1}{2}(x+4)^2$ respectively. Assume at round $t$,  $x^t =0$, then $x^{t+1}_{uniform} = 0.5$, $x^{t+1}_{q-fedavg} =-0.4$ and $x^{t+1}_{eba} =-0.1$. The zoomed-in view of the window shows $|F_2(x) - F_1(x)|$ for $x=0.5, -0.4, -0.1$ which represent the diversity of loss by FedAvg, q-FedAvg, and FedEBA+. we have not defined diversity of loss. The figure shows $F_2(x) - F_1(x)$ for $x=0.5, -0.4, -0.1$ which represent the diversity of loss by FedAvg, q-FedAvg, and FedEBA+.fixed: The smaller the diversity of loss, the more uniform the distribution of losses, and therefore the fairer. Thus, EBA is the fairest with the smallest diversity of loss.

need to check the figure

Our major contributions can be summarized as below:

* We propose FedEBA+, an effective FL algorithm for advocating fairness while guaranteeing globle model performance. In particular, FedEBA+ includes a fair aggregation method we need introduce Energy Based Aggregation (EBA) somewherewe mention this in describing Figure 1 and a new model update method. The aggregation method tends to assign underperformance clients with higher aggregation probability to achieve uniform performance. The model update method can further enhance fairness by gradient alignment and improve the global model's performance by model alignment.

* We provide the convergence analysis for FedEBA+, which is provable to converge to the nearby of the optimal solution in rate $\mathcal{O}\left(\frac{1}{\sqrt{nKT}}+\frac{1}{T} \right)$. Besides, we demonstrate our algorithm can enhance fairness for FL since we use a class of regression model to show the variance of performance under FedEBA is smaller than uniform aggregation.

* We examine the effectiveness of our FedEBA+ over other SOTA baselines in MNIST, FMNIST, CIFAR-10, and Cifar-100 datasets, and provide comprehensive ablation experiments to demonstrate the effectiveness of our algorithm.

§ RELATED WORK

FedAvg is proposed by <cit.> as a de facto algorithm of FL. Usually, the model's performance can differ significantly among clients due to statistical/objective heterogeneity <cit.> and system heterogeneity <cit.>. It is important to ensure fair/uniform distribution across the clients <cit.>.

§.§ Fairness in FL

To enhance fairness for FL,
some works propose objective function-based approaches. For example, <cit.> consider a min-max optimization problem to achieve the good-intent notion of fairness, while inspired by $\alpha$-fair allocation scheme, q-F<cit.> reformulate the objective with parameter $q$ to control the weight of clients' loss. For the gradient-based method, FedFV <cit.> mitigates gradient conflicts among FL clients before averaging the gradients in the global objective function.

Recently, reweighting methods encourage a uniform performance by up-reweighting the importance of underperforming clients <cit.>.

However, these aggregation methods improve fairness by sacrificing the performance of the global model <cit.>. Although <cit.> and <cit.> have achieved good results in balancing fairness and robustness, they both require additional personalized models and are ineffective in improving the performance of the global model in non-attack scenarios. Therefore, we develop an aggregation-based algorithm with theoretical guarantees, and the algorithm significantly improves the global model's performance while enhancing fairness.

§.§ Aggregation in Federated Optimization

FL relies on effective algorithms for aggregating decentralized data to train a global model <cit.>. Many approaches have been proposed in the literature for achieving this goal, including federated averaging (FedAvg) <cit.>, robust federated weighted averaging <cit.>, importance aggregation <cit.> and federated dropout <cit.>.

The averaging technique is a wide-used algorithm that involves iteratively averaging model updates from each client. However, it has been shown to be sensitive to the number and quality of clients participating in each round of training <cit.>. Moreover, the average aggregation will lead to performance fairness <cit.>. <cit.> propose flexible sample reweighting methods and <cit.> allocate different models to clients according to their contributions.
Yet, no work has been done to give aggregation strategies from the perspective of maximum entropy. This paper will show that a fair aggregation policy can be obtained using a constrained maximum entropy model.

§ PRELIMINARIES AND METRICS

Notation.  In this paper, we let $m$ be the total number of workers and $S_t$ be the set of active workers for the $t$-th communication round with size $\left|S_t\right|=n$ for some $n \in(0, m]$.  We use $K$ to denote the number of local steps per communication round at each worker. We let $T$ be the number of total communication rounds. In addition, we use boldface to denote matrices/vectors. We let $[\cdot]_{t, k}^i$ represent the parameter of $k$-th local step in the $i$-th worker after the $t$-th communication. We use $\|\cdot\|_2$ to denote the $\ell^2$-norm. For a natural number $m$, we use $[m]$ to represent the set $\{1, \cdots, m\}$. The performance of a model refers to the accuracy or the loss.

Before going into the details of the proposed method,
we begin by introducing standard FL setup <cit.>, and then introduce the key notions of fairness in FL.

§.§ FL Setting

Consider a standard FL setting, there are $m$ clients collaborating with a central server to find the model parameter $\theta$, which minimizes the weighted average of the loss across all clients. In particular,

\begin{align}
\label{objective of FL}
\min_{\theta} f(x) = \sum_{i=1}^m p_i  F_i(x) \, ,
\end{align}

where $F_i(x) \triangleq \mathbb{E}_{\xi_i \sim D_i}\left[F_i\left(x, \xi_i\right)\right]$ is the local loss function associated with a local data distribution $D_i$, and $p_i$ denotes the aggregation weight of client $i$, $p_i\geq 0$ and $\sum_{i=1}^m p_i = 1$. To optimize this objective, <cit.> proposes FedAvg, an iterative algorithm where the server broadcasts the global model to each client, to perform local training for $K$ steps on their own datasets and aggregate their model updates $\Delta_i^t = x_{t, K}^i - x_{t,0}^i$ into a global update $\Delta^t = \sum_{i=1}^mp_i\Delta_i^t$, where the aggregation probability $p_i$ is proportional to the data ratio, $p_i = \frac{n_i}{\sum_{i}^m n_i}$. FedAvg has been shown to be effective in minimizing the objective with low communication costs while preserving privacy. However, it may lead to an unfair result where accuracy distribution is imbalance among different clients <cit.>.

§.§ The Aim for Fairness FL

In this paper, we aim to provide a new aggregation scheme to minimize Equation <ref> while achieving a fairer accuracy distribution among the clients.
In particular, we mainly have two aims: (1) fairness  and (2)global model performance.

Fairness: Following <cit.>, we first provide a formal definition of fairness in the context of FL below:

A model $x_1$ is more fair than $x_2$ if the test performance distribution of $x_1$ across the network with $m$ clients is more uniform than that of $x_2$, i.e. $\operatorname{var}\left\{F_k\left(x_1\right)\right\}_{i \in[m]}<\operatorname{var}\left\{F_i\left(x_2\right)\right\}_{i \in[m]}$, where $F_i(\cdot)$ denotes the test loss of client $i \in[m]$ and var denotes the variance.

There exists a tension between variance and the performance of global model. Different from the goal of lowering the variance while maintaining acceptable average performance  <cit.>, we aim to improve the global model's performance and enhance fairness. Specifically, our goal is to significantly increase the performance of global model by using our fairness enhance algorithm, even under no-attack scenarios.

Global model performance:
As we have discussed before, it is crucial to improve the global model's performance in the fairness FL algorithm.
For example, one can achieve uniform accuracy by lowing all clients' performance to the worst client's performance. Though it has promised fairness, this poor model accuracy usually means that the training fails or does not meet the requirements <cit.>. Therefore, when considering fairness, the average accuracy should be taken into account as well.

In FL, Pareto optimality refers to a state where it is not possible to improve the performance of one participant without degrading the performance of another participant <cit.>. This concept can be formally defined as follows:

Let there be a set of $m$ participants in a FL setting, where each participant $i$ has a performance measure $f_i$. Pareto optimality is achieved when there exists no participant $i$ such that the performance of participant $i$ can be improved without degrading the performance of at least one other participant $j$:

\begin{align}
\forall i \in [1, m], \exists j \in [1, m], j \neq i \text{ such that } f_i \leq f_i' \text{ and } f_j > f_j' \notag
\end{align}

where $f_i'$ and $f_j'$ represent the improved performance measures of participants $i$ and $j$, respectively.

As long as the fairness algorithm achieves Pareto optimality, we can say we have improved the average accuracy as much as possible under the given fairness constraint.

§ PROPOSED METHODS: FEDEBA+

We aim to propose a method that can improve fairness and global model performance simultaneously. We first explore the application of maximum entropy in FL aggregation to develop a fair aggregation method.

Then based on our maximum entropy problem, we define a novel objective function for FL. By analyzing the new objective function and expressing the constraint according to different purposes, we propose a model update method with model alignment and gradient alignment.

Finally, we provide practical strategies for choosing hyperparameters.

§.§ Fair Aggregation Method: analysis of variable $p$

A natural idea to achieve fairness as defined would be to reweight the objective—assigning higher weights to devices with poor performance so that the distribution of accuracy in the network shifts towards more uniformity <cit.>.

improve the presentation.rewrite this paragraph
The application of maximum entropy has yielded promising outcomes in the fair allocation of resources<cit.>, however, its implementation in FL poses its own set of distinct challenges. Specifically, fairness in FL necessitates that the composite model achieves uniform performance across all clients, rather than simply redistributing resources. To attain fairness in FL, it is essential to impose a constraint on the mean performance of clients to a predefined constant, such as ideal global model performance or the fairest average performance. By incorporating this specific constraint in federated learning, a unique maximum entropy model can be formulated.

Drawing inspiration from the Shannon entropy solution for fairness <cit.>, an optimization problem with unique constraints on aggregation of FL is given by:

We propose the aggregation strategy for prompting fairness performance in FL.

\begin{align}
\label{Aggregation probability}
p_i=\frac{\exp [f_i(x) / T)]}{\sum_{i=1}^N \exp [f_i(x) / T]} \, ,
\end{align}

where $T>0$ is the temperature.

$T$ affects the fairness level because $T$ controls the spreading of weights assigned to each client.
In particular,  a higher $T$ leads to more uniform aggregation weights,
and a lower $T$ leads to more concentrated aggregation weights. When $T$ is infinitely large, this aggregation strategy recovers FedAvg, while when $T$ is extremely small, this aggregation strategy recovers AFL <cit.>.

The proposed aggregation strategy comes from the optimal solution to the following constrained optimization problem:

\begin{align}
&  \max\limits_{p} \mathbb{H}(p) := -\sum_{i=1}^N p_i \log(p_i)\\
& s.t.  \sum_{i=1}^N p_i = 1, p_i\geq 0, \sum_{i=1}^Np_i f_i(x) = \tilde{f}(x) \notag  \, ,
\end{align}

where $H(p)$ is the entropy of probability distribution $p$ and $\tilde{f}(x)$ is the ideal result for $\sum_{i=1}^m p_if_i(x)$.

The physical meaning of maximum entropy is that for the given constraints to be as certain as possible (close), and for the unknown part to make no assumptions, retaining its maximum uncertainty. Thus, by choosing the solution with the maximum entropy value with constraints, we actually choose the solution that fits our information with the least deviation.

The Lagrangian objective over variable $p$ is given by:

\begin{align}
L(p_i, \lambda_0, \lambda_1) = -\left[\sum_{i=1}^N p_i\log p_i + \lambda_0\left( \sum_{i=1}^N p_i -1 \right)  \notag  \right.\\
\left. + \lambda_1\left(\tilde{f}(x) - \sum_{i=1}^Np_if_i(x) \right) \right]\, ,
\end{align}

where $\lambda_0>0$ and $\lambda_1>0$ are Lagrangian multipliers

The $\tilde{f}(x)$ in constraint $\sum_{i=1}^Np_i f_i(x) = \tilde{f}(x)$
corresponds to the constraints that we want to impose on the aggregation model. For example, if we want the model after aggregation to approximate the global model, then $\tilde{f}(x)$  represents the ideal global model for the current round; if we want the model after aggregation to be the fairest model, then $\tilde{f}(x)$ represents the ideal global optimal model for the current round.

By solving this Lagrangian optimization problem,  we get our aggregation probability distribution.
Intuitively, giving higher aggregation weight to underperforming clients means making the aggregated global model focus on underperforming users, thus improving the performance of these users to reduce the gap between them and good performers, and thus achieving fairness.

When considering the prior distribution of aggregation probability <cit.>, which is $q_i = \frac{n_i}{\sum_{i\in S_t}n_i}$, the original entropy formula can be directly extended to entropy with a priori distribution $\mathcal{H}(p)=-\sum_{i=1}^m p_i \log(\frac{q_i}{p_i})$, and it can be seen that this expression is the same as the KL scatter. This implies. Under this prior distribution, the solution of the original problem becomes $p_i=\frac{q_i\exp [f_i(x) / T)]}{\sum_{j=1}^N q_j\exp [f_j(x) / T]}$.

§.§ New Update Method: analysis of variable $x$

Based on the aggregation method we proposed before, we can reformulate the objective of FL, which takes the entropy as a Lagrangian constraint. The objective of FL over variable $x$ and $p$ is:

\begin{align}
L\left(x, p_i, \lambda_0, \lambda_1\right):= \sum_{i=1}^N p_i f_i(x)+
\beta \left[\sum_{i=1 }^N p_i \log p_i  \right.\notag\\
\left. +\lambda_0\left(\sum_{i = 1}^N p_i-1\right)+\lambda_1\left(\tilde{f}(x)-\sum_{i = 1}^N p_i f_i(x)\right)\right] \, ,
\end{align}

where $\beta>0$ is the penalty coefficient of the entropy constraint for the new objective.

The new optimization problem is a bivariate optimization problem where the conclusion of the optimization for weight $p_i$ remains the same.

As for variable $x$, we can derive a novel model update method:

\begin{align}
\frac{\partial L\left(x,p_i, \lambda_0, \lambda_1\right)}{\partial x} = (1-\lambda_1\beta)\sum_{i=1}^m p_i \nabla f_i(x) + \lambda_1\beta \nabla \tilde{f}(x)
\label{gradient of new objective}
\end{align}

To simplify the symbolic representation, w.l.o.g., in the next paper, we will use the  penalty coefficient $\alpha=\lambda_1\beta>0$.

For different purposes, we define different $\tilde{f}(x)$. And thus we get different update steps.

§.§.§ Enhance the performance of global model

From equation (<ref>), we can introduce a new model update strategy on the server side.

In particular, the ideal gradient $\nabla \tilde{f}$ is used as a constraint. Recall our aim, we want to guarantee fairness without sacrificing the performance of the global model. Therefore, in this section, we let the  $\nabla \tilde{f}$ represent the global gradient, which can be approximated by the average gradient of all clients.

based on the SGD $x^{t+1} = x^{t} - \eta \frac{\partial L(x)}{\partial x} $ and the model update $x_{t+1} = x_t-\eta \Delta_t$, we have $\Delta_t = \sum_i p_i \nabla f_i(x) + \nabla \tilde{f}(x) $. Since
$\nabla \tilde{f}$ represent the global gradient, we approximate it by:

\begin{align}
\label{global model update}
\tilde{\Delta}_t = \frac{1}{|S_t|}\sum_{i\in S_t}\Delta_t^i= \frac{1}{|S_t|}\sum_{i\in S_t}(x_{t,1}^i - x_{t,0}^i)
\end{align}

Thus, we get a new model update method on the server side to improve fairness while boosting the global model's performance:

\begin{align}
\Delta_t=(1-\alpha) \sum_{i\in S_t}p_i\Delta_t^i +\alpha \tilde{\Delta}_t \, ,
\end{align}

as shown in Algorithm <ref>.

[1]
initial weights $x_0$, global learning rate $\eta$, local learning rate $\eta_l$, number of training rounds $T$
trained weights $x_T$
round $t = 1, \ldots, T$
Server randomly selects a subset $|S_t|$ from $m$ clients, and sends the model $x_t$ to those clients.
Server receives gradient $g_i^t$ and the loss $f_i(x_t)$ from all selected clients.
$arccos(\frac{L,p}{\|L\|\cdot \|p\|})>\theta$
each worker $i \in S_t$,in parallel
Server receives  $g_i^t$ and $l_i^t$ from each client
Server calculate $\tilde{p_i}$ based on equation (<ref>) and the received loss $f_i(x_t)$
$\tilde{g} = \sum_{i\in S_t}\tilde{p_i} g_i^t$
$g_{k,t}^i \gets (1-\alpha)g_{k,t}^i  + \alpha \tilde{g}^t$
Let $\Delta_t^i=x_{t,K}^i-x_{t,0}^i=-\eta_L\sum_{k=0}^{K-1} g_{t,k}^i$

At Server:
Receive $\Delta_t^i,i\in S_t$

Let $\Delta_t=\sum_{i\in S_t}p_i\Delta_t^i$, where $p_i$ follows (<ref>) and loss $f_i(x_{t,k}^i)$
each worker $i \in S_t$,in parallel
Server randomly selects a subset $|S_t|$ from $m$ clients, and sends the model $x_t$ to those clients.
compute $g_{t,k}^i = \nabla F_i(x_{t,k}^i,\xi_{t,k}^i)$
Local update:$x_{t,k+1}^i=x_{t,k}^i-\eta_Lg_{t,k}^i$
Let $\Delta_t^i=x_{t,K}^i-x_{t,0}^i=-\eta_L\sum_{k=0}^{K-1} g_{t,k}^i$ and $\tilde{\Delta}_t^i=x_{t,1}^i - x_{t,0}^i$
Send model update $\Delta_t^i$ and $\tilde{\Delta}_t^i$ to server
Let $\Delta_t=(1-\alpha) \sum_{i\in S_t}p_i\Delta_t^i +\alpha \tilde{\Delta}_t$,
where $p_i$ follows (<ref>) and and loss $f_i(x_{t,k}^i)$, $\tilde{\Delta}_t$ follows (<ref>).
Server update: $x_{t+1}=x_t+\eta\Delta_t$
Broadcast $x_{t+1} $ to clients

§.§.§ Enhance fairness

Gradient alignment corrects the gradient of each local step so that it does not deviate too much from the fair direction and falls within the tolerable fair area. In particular, gradient $g_t^i$ is the gradient of global modal on each client in round $t$, and fair gradient $\tilde{g}^t$ is the ideal fair gradient for model $x_t$. Gradient $g_{k,t}^i$ corresponds to the gradient of client $i$ in round $t$, at local epoch $k$. In each local step, the alignment gradient $g_{k,t}^i$ will always lie in the tolerable fair area.

From the expression of equation  (<ref>), we notice it is naturally a gradient-based fairness method as long as the constraint $\nabla \tilde{f}(x)$ is the ideal fair gradient of the global model.
Then, in each local epoch, we use $\nabla \tilde{f}(x)$ as a gradient alignment to enhance fairness.

Per the definition of fairness, the more homogeneously the model performs across each client, the fairer it is. Therefore, to gauge the need for fairness enhancement in the current model, we employ the arccos function to assess the uniformity of user performance. The arccos function and uniform distribution are commonly considered equivalent conversions <cit.>.
If the arccos of client's performance $\mathbb{F_i(x)}$ and guidance vector $r=[1]^m$ is larger than the threshold angel, we consider it to be unfair, and vice versa, we consider it to be within the tolerable fair area.

Based on equation (<ref>) and our fairness enhance purpose, $\nabla \tilde{f}(x)$ represents the ideal fair gradient of the weight aggregation of all clients' gradients. Specifically, in each round, the server will calculate the model performance on each client with $g_i^t$ and $f_i(x_t)$.

Once we get the loss $f_i(x_t)$, we can evaluate the importance of each client with $p_i$ according to equation  (<ref>). Therefore, the ideal fair gradient $\tilde{f}(x)$ is:

\begin{align}
\tilde{f}(x)=\tilde{g}^t=\sum_{i\in S_t}\tilde{p_i} g_i^t \, ,
\end{align}

where $\tilde{p_i}=\frac{\exp [f_i(x^t) / T)]}{\sum_{i=1}^N \exp [f_i(x^t) / T]}$.

Thus, based on the above discussion and equation  (<ref>), the fair update will be:

\begin{align}
g_{k,t}^i \gets (1-\alpha)g_{k,t}^i + \alpha \tilde{g}^t \, .
\end{align}

In this way, we make the gradient update direction of each client closer to the fair direction to enhance the parity fairness of FL, as shown in Figure <ref>.

This whole process is summarized in Algorithm <ref>.

§.§ Choosing $T$

Tuning the temperature $T$ in our aggregation formulation (<ref>) is arguably a better way to control fairness since $T$
affects the spreading of the assignments of weights.
In particular,  a higher $T$ leads to more flat assignments, and a lower $T$ leads to more concentrated assignments.

Intuitively, the hyper-parameter $T$ should be larger at the initial stage to make the clients have a uniform aggregation weight. Instead, when
the aggregation weights are biased towards a particular client, resulting in a large model bias, which is further exacerbated by the training results in subsequent rounds.

Following the idea of annealing training for energy based model,  <cit.>, we propose to use the following annealing manner for $T$ in FL:

\begin{align}
T_K = T_0/(1+\beta (K-1)),
\label{Annealed temperature}
\end{align}

where $K$ is the total communication rounds and hyperparameter $\beta$ controls the decay rate.

We call this annealing manner a linear schedule since $T$ decreases in a constant step. Other common used schedules in machine learning <cit.>, such as $f / T_k=(1+\beta(k-1))^{\frac{1}{2}} f / T_0$ and $f / T_k=(1+\alpha(k-1))^3 f / T_0$, can also be employed and are respectively referred to as concave and convex schedules. Visualizations of the temperature schedule and potential schedule are presented in Section <ref>.

§ ANALYSIS OF FAIRNESS AND CONVERGENCE

In this section, we analyze the behavior of FedEBA+ from both the convergence and fairness perspectives.

§.§ Convergence analysis of FedEBA+

In this section, we provide the convergence rate of FedEBA+ with two-side learning rates. To ease the theoretical analysis of our work, we use the following widely used assumptions:

The client's aim is to find a Lipschitz smooth function, such that there exists a constant $L>0$ satisfying $\norm{\nabla F_i(x)-\nabla F_i(y)} \leq L \norm{x-y},\forall x,y \in \mathbb{R}^d$, and $i = {1,2,\ldots,m}$.

[Unbiased Local Gradient Estimator and Local Variance]

Let $\xi_t^i$ be a random local data sample in the round $t$ at client $i$: $\Eb{\nabla F_i(x_t,\xi_t^i)}=\nabla F_i(x_t), \forall i \in [m]$. There exists a constant bound $\sigma_{L}>0$, satisfying $\Eb{ \norm{ \nabla F_i(x_t,\xi_{t}^i)-\nabla F_i(x_t) }^2 }\leq \sigma_L^2$.

[Bound Gradient Dissimilarity]

For any sets of weights $\left\{w_i \geq 0\right\}_{i=1}^m, \sum_{i=1}^m w_i=1$, there exists a constant $\sum_{i=1}^m w_i\left\|\nabla F_i(x)\right\|^2 \leq (A^2+1)\left\|\sum_{i=1}^m w_i \nabla F_i(x)\right\|^2 + \sigma_G^2.$ When all local loss functions are identical, $A^2=0$ and $\sigma_G^2=0$.

The above assumptions are commonly used in both non-convex optimization and FL literature, see e.g. <cit.>.
For Assumption <ref>, if all local loss functions are identical, then we have $A=0$ and $\sigma_G = 0$.      =-1

Under Assumption <ref>–<ref> and the aggregation strategy (<ref>), and let constant local and global learning rate $\eta_L$ and $\eta$ be chosen such that $\eta_L < min\left(1/(8LK), C\right)$, where $C$ is obtained from the condition that $\frac{1}{2}-10 L^2\frac{1}{m}\sum_{i-1}^m K^2\eta_L^2(A^2+1)(\chi_{p\|w}^2A^2+1) \textgreater c \textgreater 0$ ,and $\eta \leq 1/(\eta_LL)$,
the expected gradient norm of Algorithm <ref> is bounded as follows: =-1

\begin{align}
&\mathop{min} \limits_{t\in[T]} \E\|\nabla f(x_t)\|^2 \leq \notag \\
&2 \left[\chi_{\boldsymbol{p} \| \boldsymbol{w}}^2A^2+1\right] (\frac{f_0-f_*}{c\eta\eta_LK T}+\Phi)+2 \chi_{\boldsymbol{p} \| \boldsymbol{w}}^2 \sigma_G^2 \, ,
\label{convergence equation}
\end{align}

\begin{align}
\Phi
= \frac{1}{c}[
\frac{5\eta_L^2KL^2}{2}(\sigma_L^2 +4K\sigma_G^2)
+ \frac{\eta\eta_L L}{2}\sigma_L^2 \notag \\
+20L^2K^2(A^2+1)\eta_L^2\chi_{p\|w}^2\sigma_G^2] \, .
\end{align}

where $c$ is a constant, $\chi_{\boldsymbol{p} \| \boldsymbol{w}}^2=\sum_{i=1}^m\left(p_i-w_i\right)^2 / w_i$ represents the chi-square divergence between vectors $\boldsymbol{p}=\left[p_1, \ldots, p_m\right]$ and $ \boldsymbol{w}=\left[w_1, \ldots, w_m\right]$.  In this paper, we use $p=\frac{1}{m}$ to represent uniform aggregation. Observe that when all clients have uniform loss distribution, we have $p = w$ such that $\chi^2 =0$.

From Theorem <ref>, we derive the following convergence rate for FedEBA+ with a proper choice of two-side learning rates:

Let $\eta_L=\mathcal{O}\left(\frac{1}{\sqrt{T}KL}\right)$ and $\eta=\mathcal{O}\left(\sqrt{Kn}\right)$. The convergence rate of FedEBA is:

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2 \leq \mathcal{O}\left(\frac{Lm(f^0-f^*)}{\sqrt{mKT}} \right)+\mathcal{O}\left(\frac{\sigma_L^2}{2\sqrt{mKT}} \right) +\notag \\
\mathcal{O}\left(\frac{5(\sigma_L^2+4K\sigma_G^2)}{2KT} \right) + \mathcal{O}\left(\frac{20(A^2+1)\chi_{p\|w}\sigma_G^2}{T} \right) + 2 \chi_{\boldsymbol{p} \| \boldsymbol{w}}^2 \sigma_G^2
\label{convergence rate equation}
\end{align}

From the Corollary <ref>, we note that Algorit<ref> achieves a standard FL nonconvex convergence rate. In particular, FedEBA+ will converge to a nearby of the optimality in a rate of $\mathcal{O}\left(\frac{1}{T}+\frac{1}{nKT} \right)$, the same order as that of the SOTA FedAvg <cit.>.

The convergence analysis is suitable for any non-uniform aggregation algorithm. Specifically, the non-vanishing term $\chi_{\boldsymbol{p} \| \boldsymbol{w}}^2 \sigma_G^2$ in equation  (<ref>) means the aggregation error from unbiased aggregation distribution.

That is, there is always an error term that exists in the convergence rate result, as long as the aggregation algorithm is biased. This phenomenon has also been observed in previous work of FL  <cit.>.

§.§ Fairness Analysis

Some works <cit.> have intuitively shown a fact: Assigning high weights to clients who perform poorly can increase fairness. However, there is a lack of theoretical analysis to show the validity of weighted aggregation. need these words?
In this section, we focus on a simplified setting where the client's model is a general regression problem, as used in  <cit.>. We demonstrate our proposed aggregation method can enhance fairness for FL since the variance of performance under FedEBA+ is smaller than uniform aggregation.

The following theorem shows our FedEBA+ is more fair compared with uniform aggregation. Specifically, our method has a smaller variance than uniform aggregation.

Denote the variance of test losses on different clients of uniform aggregation by $\mathbf{Var}_k^{uniform}(F_1(x),F_2(x),\dots,F_K(x))$ and FedEBA+ by $\mathbf{Var}_k^{ebm+}((F_1(x),F_2(x),\dots,F_K(x)))$ respectively. We have $\mathbf{Var}_{eba+}\leq \mathbf{Var}_{uniform}$ in the regression setting.

The proof details are shown in Appendix <ref>.

Besides the variance of fairness analysis of FL, following Property 1 of <cit.>, we show that the proposed maximum entropy-based aggregation strategy described in Proposition <ref> satisfies Pareto optimality and uniqueness.

The aggregation strategy $\varphi(p)=\underset{p \in \mathcal{P}}{\arg \max }~h(p(f))$ achieves Pareto optimal if $h: \mathbb{R}^n \rightarrow \mathbb{R}$ is a strictly monotonically increasing function.
Here $p(f)$ corresponds to the performance under the aggregation weights $p = [p_1, p_2, \dots, p_m]$ of the loss function $f=[f_1,f_2,\dots,f_m]$, and $h(\cdot)$ is the entropy function.
As the maximum entropy model is a monotonically increasing function, our aggregation strategy achieves Pareto optimal.

The detailed proof can be seen in Appendix <ref>.

Our maximum entropy-based aggregation strategy is guaranteed to be unique, as we prove the strategy is derived from a concave function.

The proof for the maximum entropy model is concave is given in Appendix <ref>.

just a monotonicity is not quite suitable to be a proposition?but it's hard to find them in one proposition. Maybe combine the last two statements in one corollary or proposition.I set pareto and monontonicity in one proposition while let the uniqueness due to concave be a corollary

§ EXPERIMENTS

In this section, we first demonstrate that $FedEBA+$ can enhance fairness for FL more effectively than other fairness FL baselines (Section). We then show it results higher global model performance than  other fairness FL work and optimization FL work (Section). The ablation experiments demonstrate that every trick of $FedEBA+$ is beneficial and we give experimental results for $FedEBA+$ with different parameters (Section). We explore
additional beneficial properties of $FedEBA+$ in Appendix??.

§.§ Setup

For all experiments, we measure the global model's test accuracy and accuracy variance. We split the real datasets into non-iid datasets following the setting of <cit.>, including MNIST, Fashion MNIST, CIFAR-10 and CIFAR-100. We use MLP and CNN models to test the performance for all baselines.
Detailed datasets and models  are provided in Appendix ??.
We compare FedEBA+ with several advanced FL fairness algorithms, and the hyper-parameters of each baseline for ensuring performance in line with the previous studies are listed in Table ?? in Appendix ??.
We further assume the tolerable fair angle $\theta$ in our fairness experiment refers to zero for fairness enhancement; while in the experiment of global model's performance, it refers to $\frac{\pi}{2}$ to improve the global model's accuracy. The experimental results of different fairness angel are provided in Appendix. As for $T$ and $\alpha$, we report the best result in each experiment, and we give the ablation study of $T$ and $\alpha$.

§.§ Fairness of FedEBA+

To verify the fairness of FedEBA+, we first compare the variance fairness defined in Defination <ref>. We list the test accuracy of global model, variance, the worst $5\%$ and the best $5\%$ of test accuracy on both FMNIST and CIFAR-10 datasets. The result is shown in Table 2 and Table 3.

Form Table 2 and Table 3,we observe that FedEBA+ can effectively reduce the performance variance and thus achieve a uniform accuracy. Besides, it greatly improve the under-performance client's accuracy, as shown by that of worst $5\%$ clients in Table 2   3.

In Figure ??, we compare the performance of variance of different algorithms. It shows that our aggregation strategy FedEBA is a fair aggregation strategy as it improve the variance while significantly improves the worst clients' performance.
In addition, our fairness enhance strategy FedEBA+ can make it better because in each local epoch because it enforces the client's update toward the tolerable fair area, thus lead to more uniform accuracy.

[CIFAR-10 ]

The comparison of test variance of different fairness algorithms on (a) MNIST and (b) CIFAR-10.The results are average over 5 runs with different random seed.

Method                             Global Acc.    Var.           Worst 5%      Best 5%
FedAvg                             46.85±0.65     12.57±1.50     19.84±6.55     69.28±1.17
$qFedAvg|_{q=0.1}$                 47.02±0.89     13.16±1.84     18.72±6.94     70.16±2.06

$qFedAvg|_{q=0.2}$                 46.91±0.90     13.09±1.84     18.88±7.00     70.16±2.10

$qFedAvg|_{q=1.0}$                 46.79±0.73     11.72±1.00     22.80±3.39     68.00±1.60

$qFedAvg|_{q=2.0}$                 46.36±0.38     10.85±0.76     24.64±2.17     66.80±2.02

$qFedAvg|_{q=5.0}$                 45.25±0.42     9.59±0.36      26.56±1.03     63.60±1.13
$Ditto|_{\lambda=0.0}$             52.78±1.23     10.17±0.24     31.80±2.27     71.47±1.20

$Ditto|_{\lambda=0.5}$             53.77±1.02     8.89±0.32      36.27±2.81     71.27±0.52
$AFL|_{\lambda=0.01}$              52.69±0.19     10.57±0.37     34.00±1.30     71.33±0.57

$AFL|_{\lambda=0.1} $              52.68±0.46     10.64±0.14     33.27±1.75     71.53±0.52
$TERM|_{T=1.0}   $                 45.14±2.25     9.12±0.35      27.07±3.49     62.73±1.37
$FedMGDA+|_{\epsilon=0.01}$        45.65±0.21     10.94±0.87     25.12±2.34     67.44±1.20

$FedMGDA+|_{\epsilon=0.05}$        45.58±0.21     10.98±0.81     25.12±1.87     67.76±2.27

$FedMGDA+|_{\epsilon=0.1}$         45.52±0.17     11.32±0.86     24.32±2.24     68.48±2.68

$FedMGDA+|_{\epsilon=0.5}$         45.34±0.21     11.63±0.69     24.00±1.93     68.64±3.11

$FedMGDA+|_{\epsilon=1.0}$         45.34±0.22     11.64±0.66     24.00±1.93     68.64±3.11
$FedFV|_{\alpha=0.1, \tau=1} $     54.28±0.37     9.25±0.42      35.25±1.01     71.13±1.37
$FedEBA|_{\alpha=0.9, T=0.1}$      53.94±0.13     9.25±0.95      35.87±1.80     69.93±1.00

$FedEBA+|_{\alpha=0.5, T=0.1}$     53.14±0.05     8.48±0.32      36.03±2.08     69.20±0.75

$FedEBA+|_{\alpha=0.9, T=0.1}$     54.43±0.24     8.10±0.17      40.07±0.57     69.80±0.16

CIFAR-10 devided by labels. All experiments are running over 2000 rounds on the MLP model with full batch size, learning rate $\eta$ = 0.1 and local epochs E = 1. The reported results are averaged over 5 runs with different random seeds.

Method                             Global Acc.    Var.           Worst 5%      Best 5%
FedAvg                             67.79±0.35     10.18±0.51     45.00±2.83     85.13±0.82
$qFedAvg|_{q=0.1}$                 67.35±0.61     9.70±0.31      46.80±0.33     84.70±1.31

$qFedAvg|_{q=0.2}$                 66.75±1.31     9.43±0.62      46.73±2.41     82.80±1.84

$qFedAvg|_{q=1.0}$                 60.69±0.56     8.93±0.49      43.87±2.04     78.27±1.57

$qFedAvg|_{q=2.0}$                 54.34±0.49     9.55±0.58      38.20±0.59     71.47±1.70

$qFedAvg|_{q=5.0}$                 45.47±0.74     8.44±0.47      29.47±2.39     62.20±1.18
$FedMGDA+|_{\epsilon=0.01}$        53.47±3.30     11.40±1.37     31.20±7.46     75.80±0.91

$FedMGDA+|_{\epsilon=0.05}$        53.67±3.16     11.25±1.33     31.53±6.70     76.00±0.99

$FedMGDA+|_{\epsilon=0.1}$         53.43±3.34     11.09±1.61     30.80±8.21     74.67±0.82

$FedMGDA+|_{\epsilon=0.5}$         53.50±3.32     11.23±1.60     30.47±7.97     75.93±0.81

$FedMGDA+|_{\epsilon=1.0}$         53.49±3.36     11.21±1.59     30.00±7.16     74.53±0.57
$Ditto|_{\lambda=0.0} $            60.11±4.41     9.28±0.37      42.20±2.20     77.90±4.90

$Ditto|_{\lambda=0.5} $            62.65±1.96     10.13±0.57     42.67±3.45     81.27±0.82
$AFL|_{\lambda=0.01} $             68.46±0.33     9.45±0.49      48.93±1.33     84.07±0.98

$AFL|_{\lambda=0.5} $              65.11±2.44     9.27±0.51      44.73±3.90     82.10±0.62
$FedFV|_{\alpha=0.1, \tau=1} $     68.94±0.27     9.52±0.15      50.53±4.33     86.00±1.23
$TERM|_{T=1.0}   $                 55.30±1.96     8.94±0.70      39.67±1.80     73.87±1.54
$FedEBA|_{\alpha=0.9, T=0.1}$      69.38±0.52     9.46±1.01      50.40±1.72     86.07±0.90

$FedEBA+|_{\alpha=0.5, T=0.1}$     72.39±0.47     8.36±0.14      55.27±1.18     86.27±1.16

$FedEBA+|_{\alpha=0.9, T=0.1}$     72.75±0.25     8.29±0.26      55.80±1.28     86.93±0.52

CIFAR-10 devided by labels. All experiments are running over 2000 rounds on the CNN model with local batch size = 50, learning rate $\eta$ = 0.1 and local epochs E = 1. The reported results are averaged over 5 runs with different random seeds.

Method                             Global Acc.    Var.           Worst 5%      Best 5%
FedAvg                             86.57±0.22     6.97±0.10      71.27±1.14     95.84±0.35
$qFedAvg|_{q=0.1}$                 85.91±0.25     7.05±0.17      70.48±1.36     95.37±0.24

$qFedAvg|_{q=0.2}$                 85.34±0.27     7.61±0.24      67.08±1.52     95.12±0.33

$qFedAvg|_{q=1.0}$                 81.67±0.66     8.45±0.27      64.19±0.15     93.12±0.24

$qFedAvg|_{q=2.0}$                 78.97±0.75     8.71±0.46      60.49±1.22     91.68±0.39

$qFedAvg|_{q=5.0}$                 74.10±1.12     9.89±1.10      52.39±3.13     88.13±0.34
$FedMGDA+|_{\epsilon=0.01}$        79.94±0.13     11.67±0.12     48.80±1.28     94.08±0.36

$FedMGDA+|_{\epsilon=0.05}$        79.98±0.14     11.57±0.04     49.08±0.80     94.12±0.36

$FedMGDA+|_{\epsilon=0.1}$         79.87±0.14     11.30±0.02     50.38±0.46     93.94±0.38

$FedMGDA+|_{\epsilon=0.5}$         79.45±0.02     10.77±0.14     54.46±0.26     93.44±0.40

$FedMGDA+|_{\epsilon=1.0}$         79.40±0.05     10.78±0.15     54.38±0.18     93.44±0.40
$Ditto|_{\lambda=0.0} $            86.37±0.13     7.44±0.37      69.20±0.37     95.79±0.38

$Ditto|_{\lambda=0.5} $            86.29±0.25     7.52±0.14      69.05±0.76     95.85±0.36
$AFL|_{\lambda=0.01} $             83.91±0.28     9.42±0.20      60.41±1.01     95.89±0.16

$AFL|_{\lambda=0.5} $              84.14±0.18     9.53±0.17      60.11±0.58     96.00±0.09
$TERM|_{T=1.0}   $                 75.71±1.63     11.46±1.36     48.76±3.28     91.26±0.18
$FedFV|_{\alpha=0.1, \tau=1} $     86.51±0.28     7.03±0.18      71.33±1.16     95.89±0.23
$FedEBA|_{\alpha=0.9, T=0.1}$      86.70±0.11     7.09±0.34      71.13±0.69     95.47±0.27

$FedEBA+|_{\alpha=0.5, T=0.1}$     87.21±0.06     6.33±0.12      73.07±1.03     95.81±0.14

$FedEBA+|_{\alpha=0.9, T=0.1}$     87.37±0.18     6.58±0.33      72.07±1.47     95.91±0.19

Fashion-MNIST devided by dirichlet distribution($\alpha$=0.1). All experiments are running over 3000 rounds on the MLP model with local batch size = 50, learning rate $\eta$ = 0.1 and local epochs E = 1. The reported results are averaged over 5 runs with different random seeds.

§.§ Global performance of FedEBA+

As table 1 and 2 shows, compared with existing fairness FL algorithms, FedEBA+ significantly improves the global model's performance while promising fairness. Even compared with Ditto who aims to improve the global model's performance to attacks while enhancing fairness using the personalized FL algorithm, FedEBA+ achieves significantly better results in terms of fairness and global model performance.

As shown in Figure <ref>, compared with learning a  global model, fairness algorithms either achieve fairness while sacrificing the global model's performance (with lower variance, lower accuracy), or not even fairness (higher variance than FedAvg) FedEBA+ lies at the lower right corner, which is our perferred region.

We also show that FedEBA+ outperform previous works in term of convergent efficiency. Figure <ref> visualizes part of the curves for the global model's test accuracy over rounds in MNIST and CIFAR-10. All methods are tuned to their best performance, the results of the best $5\%$ and worst $5\%$ are available in Appendix??

We demonstrate that

Complete results of fairness vs global model's test accuracy. (The point closer to the bottom right corner is better.

[CIFAR-10 ]

The comparison of global model's test accuracy of different fairness algorithms on (a) MNIST and (b) CIFAR-10.The results are average over 5 runs with different random seed.

§.§ Ablation Study

We conduct and ablation study to answer three questions:

* Can each trick of FedEBA+ effectively enhance fairness/global model's performance?

* How does temperature $T$ in (<ref>) and penalty coefficient $\alpha$ in Algorithm <ref> influence the fairness and global model's performance?

* How does the annealing schedule influence the performance?

Ablation for FedEBA+.

Table  <ref> shows that each trick in our algorithm is benificial. Specifically, we show AA is most efficient in improving fairness while AB has advantage in improving global model's performance.

Ablation study for FedEBA+

2*Algorithm     2cFMNIST $\alpha = 0.9$     2cCIFAR10 $\alpha = 0.9$

(lr)2-3 (lr)4-5
global acc     var           global acc     var

FedEBA+ ($\theta=0$)     87.50±0.19     7.00±0.16     72.75±0.25     8.29±0.26

FedEBA+ ($\theta=\frac{pi}{2}$)     86.75±0.22     7.21±0.07     71.32±0.45     8.64±0.54

FedEBA(FedAvg+reweight aggregation)                        86.43±0.12     7.58±0.23     69.38±0.52     9.46±1.01

FedAvg                                                     86.49±0.09     7.90±0.29     67.79±0.35     10.18±0.51

consider change to Cifar100 as C100 is visually appealing; double check the second case, is it the same as FedEBA?Then the result should be the same?

Ablation for coefficient $\alpha$.
$\alpha$ is a convex combinatorial coefficient that controls the assignment of weights over the aggregated model and the ideal global model, or over the local gradient and the ideal fairness gradient. Thus, it is crucial in improving fairness and global model performance.
For each $\alpha$, we run experiments with five random seeds. To justify the importance to use $\alpha$, we evaluate the performance for $\alpha = [xx,xx,xx]$. And we report the accuracy under setting $\theta = 0$ and global performance under $\theta =\frac{\pi}{2}$.
Figure <ref> shows that best $\alpha= $ works best for enhancing fairness, while $\alpha=$ works best for improving global model's performance.

[Accuracy ]

Ablation for $\alpha$

Ablation for $T$ and Annealing schedule.
For temperature $T$ that controls the spreading of the aggregation weights of each client. We first evaluate the performance of fairness for $T=[0.05, 0.1, 0.5,1.0,5.0]$. We report the result in Figure <ref>.
We can see that the temperature $T=?$ has the best performance in both accuracy and variance.
When $T>1$, the weights become more smooth thereby reduce the fairness performance, but "improve the global model's performance".
When $T<1$, it focus on underperforming clients and assign them relative much higher weights so that the model is more focused on learning from these users.

[Accuracy ]

Ablation for $T$

Then, we use the schedule for $T$ in Section <ref> to improve the performance. The visualization of the temperature schedule and the potential schedule is given in Figure <ref>.Besides schedule, the initial temperature is also an important hyperparameter. We evaluate
the initial temperature $T_0 = {xx,xx,xx}$. We report the results in Figure <ref>.
We can see that the performance is robust for whatever convex, linear, or concave schedule used. The more important factor is the initial temperature τ0. The performance is reduced when τ0 is too small as the energy based model (3) is not smooth enough and the performance is robust when τ0 is large.

Ablation for $T$.

Method                                      shirt        pullover       T-shirt         Ave.           Var.
FedAvg                                   64.26±1.07     87.03±1.40     89.97±1.30     80.42±0.76     11.50±0.95

$AFL|_{\lambda=0.01} $                   71.09±0.91     81.89±1.30     84.29±1.23     79.09±0.73     5.76±0.75

$AFL|_{\lambda=0.1} $                    76.34±0.63     79.00±1.04     79.06±1.21     78.13±0.72     1.27±0.66

$AFL|_{\lambda=0.1} $                    76.57±0.58     78.77±0.99     79.09±1.15     78.14±0.71     1.12±0.61
$qFedAvg|_{q=5} $                        71.29±0.85     81.46±1.08     82.86±0.97     78.53±0.64     5.16±0.69

$qFedAvg|_{q=15} $                       77.09±0.88     75.40±2.07     60.69±1.79     71.06±0.81     7.46±0.88

$FedMGDA+|_{\epsilon=0.05}$              44.63±1.63     57.77±5.72     99.09±0.23     67.16±1.65     23.39±0.57

$FedMGDA+|_{\epsilon=0.1}$               72.26±3.12     79.71±4.47     86.03±4.27     79.33±1.11     6.45±2.21

$FedMGDA+|_{\epsilon=1.0}$               72.46±3.32     79.74±4.48     85.66±4.88     79.29±1.14     6.42±2.23
$FedFV|_{\alpha=0.0, \tau=0} $           61.06±1.21     89.31±1.38     91.06±1.29     80.48±0.68     13.76±1.02

$FedFV|_{\alpha=\frac{1}{3}, \tau=0}$    77.09±1.35     80.69±1.53     81.06±0.53     79.61±0.85     1.91±0.57

$FedFV|_{\alpha=\frac{2}{3}, \tau=0}$    77.91±0.80     81.46±1.99     81.46±1.51     80.28±1.09     1.77±0.87
$FedEBA+|_{\alpha=0.9, T=0.05}$           77.14±0.71     84.81±0.70     82.52±1.90     81.54±0.98     3.30±0.85

$FedEBA+|_{\alpha=0.9, T=0.02}$           79.19±0.88     84.14±0.87     80.14±1.65     81.16±0.88     2.32±0.58

$FedEBA+|_{\alpha=0.9, T=0.01}$           83.57±1.46     80.05±1.46     72.81±1.38     78.81±0.51     4.52±1.20

FASHION-MNIST, on LR model with full batch size, learning rate $\eta$ = 0.1 and local epochs $E = 1$.

§ CONCLUSION AND FUTURE WORK

We have presented an energy-based treatment of the aggregation scheme, in order to improve fairness in FL. It is very worthwhile to explore more in the following directions: 1) Choosing the temperature $T$. The temperature controls the level of fairness since when $T \rightarrow \inf$, all clients have equal importance, when $T \rightarrow 0$, a client has either 0 or 1 importance. As we discussed, one can use an
annealing-style algorithm in order to control the fairness level: starting with a high temperature and gradually decreasing it, one can obtain a series of importance values under different fairness levels. In addition to the linear or quadratic annealing approach proposed in this paper, we believe that there are other more efficient annealing algorithms that can be used to improve fairness.
2) This work can be easily extended to personalized federation learning, e.g., each client has a different classification layer that can be personalized finetune while using our algorithm to improve the fairness of the shared model part.
3) It is also interesting to develop a strategy  based on our algorithm to user attacks. We will leave this in our future work.

§ ENTROPY ANALYSIS

§.§ Derivation of Proposition <ref>

In this section, we present the derivation of the maximum entropy distribution for the aggregation strategy of FedEBA+.

One may wonder why we propose an exponential formula treatment of loss function $p_i \propto e^{F_i(x)/\tau}$ instead of formulating the aggregation probability as something else, say, $p_i \propto F_i(x)$.
In one word, because our aggregation strategy is the maximum entropy distribution.

Being a maximum entropy means minimizing the amount of prior information built to the distribution and guarantee that the selected probability distribution is devoid of subjective influences, thereby eradicating any inherent bias <cit.>. Meanwhile,
many physical systems tend to move towards maximal entropy configurations over time <cit.>.

In the following we will give a derivation to show that $p_i\propto e^{F_i(x)/\tau} $ is indeed the maximum entropy distribution for FL.  The derivation bellow is closely following <cit.> for statistical mechanics. Suppose the loss function of the user corresponding to the aggregation probability $p_i$ is $F_i(x)$.
We would like to maximize the entropy $\mathbb{H}(p)=-\sum_{i=1}^mp_i\log p_i$, subject to FL constrains that $\sum_{i=1}^mp_i=1$,$p_i\geq 0$, $\sum_i p_if_i(x) =\tilde{f}(x)$, which means we constrain the average performance to be a constant, such as ideal global model performance or the ideal most fair average performance, independent of $p_i$.

\begin{align}
L\left(p, \lambda_0, \lambda_1\right):=-\left[\sum_{i=1 }^N p_i \log p_i \notag +\lambda_0\left(\sum_{i = 1}^N p_i-1\right)+\lambda_1\left(\mu-\sum_{i = 1}^N p_i f_i(x)\right)\right],
\end{align}

where $\mu = f(x)$.

By setting

\begin{align}
\frac{\partial L\left(p, \lambda_0, \lambda_1\right)}{\partial p_i}=-\left[\log p_i+1+\lambda_0-\lambda_1 f_i(x)\right] =0 \, ,
\end{align}

we get:

\begin{align}
p_i=\exp \left[-\left(\lambda_0+1-\lambda_1 f_i(x)\right)\right] \, .
\end{align}

According to $\sum_i p_i =1$, we have:

\begin{align}
\lambda_0+1=\log \sum_{i=1}^N \exp \left(\lambda_1 f_i(x)\right)=: \log Z \, ,
\end{align}

which is the log-partition function.

\begin{align}
p_i=\frac{\left.\exp \left[\lambda_1 f_i(x)\right)\right]}{\mathrm{Z}}\, .
\end{align}

Note that the maximum value of the entropy is

\begin{equation}
\begin{aligned}
H_{\max }& =-\sum_{i=1}^N p_i \log p_i \\
& =\lambda_0+1-\lambda_1 \sum_{i=1}^N p_i f_i(x) \\
& =\lambda_0+1-\lambda_1 \mu \, .
\end{aligned}
\end{equation}

So one can get,

\begin{align}
\label{T equation}
\lambda_1=-\frac{\partial H_{\max }}{\partial \mu}=: \frac{1}{\tau} \, ,
\end{align}

which defines the inverse temperature.
So we reach the exponential form of $p_i$ as:

\begin{align}
p_i=\frac{\exp [f_i(x) / \tau)]}{\sum_{i=1}^N \exp [f_i(x) / \tau]} \, .
\end{align}

When taking into account the prior distribution of aggregation probability <cit.>, which is typically expressed as $q_i = \nicefrac{n_i}{\sum_{i\in S_t}n_i}$, the original entropy formula can be extended to include the prior distribution as follows:

\begin{align}
\mathbb{H}(p)=\sum_{i=1}^m p_i \log(\frac{q_i}{p_i}) \, .
\end{align}

Thus, the solution of the original problem under this prior distribution becomes:

\begin{align}
\label{aggregation probability with prior}
p_i=\frac{q_i\exp [f_i(x) / \tau)]}{\sum_{j=1}^N q_j\exp [f_j(x) / \tau]} \, .
\end{align}

\begin{align}
L\left(p, \lambda_0, \lambda_1\right):=-\sum_{i=1 }^N p_i \log \frac{q_i}{p_i}
+\lambda_0\left(\sum_{i = 1}^N p_i-1\right)+\lambda_1\left(\mu-\sum_{i = 1}^N p_i f_i(x)\right) \, .
\end{align}

Following similar derivation steps, let

\begin{align}
\frac{\partial L\left(p, \lambda_0, \lambda_1\right)}{\partial p_i}=-\log(q_i)+\log(p_i)+1+\lambda_0-\lambda_1 f_i(x) =0 \, ,
\end{align}

we get:

\begin{align}
p_i=\exp \left[-\left(\lambda_0+1-\log(q_i)-\lambda_1 f_i(x)\right)\right] \, .
\end{align}

According to $\sum_ip_i=1$, we have:

\begin{align}
\sum_ip_i = \sum_i\exp \left[-\left(\lambda_0+1-\log(q_i)-\lambda_1 f_i(x)\right)\right]=1 \, .
\end{align}

Therefore, we get:

\begin{align}
\lambda_0+1=\log \sum_{i=1}^N q_i \exp \left(\lambda_1 f_i(x)\right)=: \log(Z) \, .
\end{align}

Then substituting $\lambda_0+1=\log(Z)$ back to $p_i=\exp \left[-\left(\lambda_0+1-\log(q_i)-\lambda_1 f_i(x)\right)\right]$, we get $p_i=\frac{q_i\exp \left[\lambda_1 f_i(x)\right]}{\mathrm{Z}}$.

By setting $\lambda_1=: \frac{1}{\tau}$, we obtain (<ref>):

\begin{align}
p_i=\frac{q_i\exp [f_i(x) / \tau)]}{\sum_{j=1}^N q_j\exp [f_j(x) / \tau]} \, .
\end{align}

§ CONVERGENCE ANALYSIS OF FEDEBA+

In this section, we give the proof of Theorem <ref>.

Before going to the details of our convergence analysis, we first state the key lemmas used in our proof, which helps us to obtain the advanced convergence result.
To make this paper self-contained, we restate the Lemma 3 in <cit.>:

For any model parameter $\boldsymbol{x}$, the difference between the gradients of $f(\boldsymbol{x})$ and $\tilde{f}(\boldsymbol{x})$ can be bounded as follows:

\begin{align}
\|\nabla f(\boldsymbol{x})-\nabla \tilde{f}(\boldsymbol{x})\|^2 \leq \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\left[A^2\|\nabla \tilde{f}(\boldsymbol{x})\|^2+\kappa^2\right] \, ,
\end{align}

where $\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2$ denotes the chi-square distance between $\boldsymbol{w}$ and $\boldsymbol{w}$, i.e., $\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2=\sum_{i=1}^m\left(w_i-p_i\right)^2 / p_i$. $f(x)$ is the global objective with $f(x)=\sum_{i=1}^mw_if_i(x)$ where $\boldsymbol{w}$ is usually average of all clients, i.e., $\boldsymbol{w} = \frac{1}{m}$. $\tilde{f}(x)=\frac{i=1}{m}p_if_i(x)$ is the surrogate objective with the reweight aggregation probability $\boldsymbol{p}$.

\begin{equation}
\begin{aligned}
\nabla f(x)-\nabla \tilde{f}(\boldsymbol{x}) & =\sum_{i=1}^m\left(w_i-p_i\right) \nabla f_i(\boldsymbol{x}) \\
& =\sum_{i=1}^m\left(w_i-p_i\right)\left(\nabla f_i(\boldsymbol{x})-\nabla \tilde{f}(\boldsymbol{x})\right) \\
& =\sum_{i=1}^m \frac{w_i-p_i}{\sqrt{p}_i} \cdot \sqrt{p}_i\left(\nabla f_i(\boldsymbol{x})-\nabla \tilde{f}(\boldsymbol{x})\right) \, .
\end{aligned}
\end{equation}

Applying Cauchy-Schwarz inequality, it follows that

\begin{equation}
\begin{aligned}
\|\nabla f(x)-\nabla \tilde{f}(\boldsymbol{x})\|^2 & \leq\left[\sum_{i=1}^m \frac{\left(w_i-p_i\right)^2}{p_i}\right]\left[\sum_{i=1}^m p_i\left\|\nabla F_i(x)-\nabla \tilde{f}(\boldsymbol{x})\right\|^2\right] \\
& \leq \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\left[A^2\|\nabla \tilde{f}(\boldsymbol{x})\|^2+\sigma_G^2\right] \, ,
\end{aligned}
\end{equation}

where the last inequality uses Assumption <ref>.
Note that

\begin{equation}
\begin{aligned}
\|\nabla f(\boldsymbol{x})\|^2 & \leq 2\|\nabla f(\boldsymbol{x})-\nabla \tilde{f}(\boldsymbol{x})\|^2+2\|\nabla \tilde{f}(\boldsymbol{x})\|^2 \\
& \leq 2\left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right]\|\nabla \tilde{f}(\boldsymbol{x})\|^2+2 \chi_{\boldsymbol{p} \| \boldsymbol{w}^2}^2 \sigma_G^2 \, .
\end{aligned}
\end{equation}

As a result, we obtain

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2 & \leq \frac{1}{\tau} \sum_{t=0}^{T-1}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2 \notag \\
& \leq 2\left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] \frac{1}{\tau} \sum_{t=0}^{T-1}\left\|\nabla \tilde{f}\left(\boldsymbol{x}_t\right)\right\|^2+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \notag\\
& \leq 2\left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] \epsilon_{\mathrm{opt}}+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, ,
\label{global convergence}
\end{align}

where $\epsilon_{\mathrm{opt}}$ denotes the optimization error.

§.§ Analysis with $\alpha =0$.

For any step-size satisfying $\eta_L \leq \frac{1}{8LK}$, we can have the following results:

\begin{align}
\E\|x_{i,k}^t-x_t\|^2 \leq 5K(\eta_L^2\sigma_L^2+4K\eta_L^2\sigma_G^2) + 20K^2(A^2+1)\eta_L^2\|\nabla f(x_t)\|^2 \, .
\end{align}

\begin{align}
&\quad \E_t\|x_{t,k}^i-x_t\|^2 \notag \\
&=\E_t\|x_{t,k-1}^i-x_t-\eta_Lg_{t,k-1}^t\|^2   \notag\\
&=\E_t\|x_{t,k-1}^i-x_t-\eta_L ( g_{t,k-1}^t-\nabla F_i(x_{t,k-1}^i)+\nabla F_i(x_{t,k-1}^i) -\nabla F_i(x_t)+\nabla F_i(x_t) ) \|^2     \notag\\
&\leq (1+\frac{1}{2K-1})\E_t\|x_{t,k-1}^i-x_t\|^2+\E_t\|\eta_L(g_{t,k-1}^t-\nabla F_i(x_{t,k}^i))\|^2 \notag \\
& +4K \E_t[\|\eta_L(\nabla F_i(x_{t,K-1}^i)-\nabla F_i(x_t))\|^2] + 4K\eta_L^2\E_t\|\nabla F_i(x_t)\|^2              \notag\\
& \leq (1+\frac{1}{2K-1})\E_t\|x_{t,k-1}^i-x_t\|^2+\eta_L^2\sigma_{L}^2+4K\eta_L^2L^2\E_t\|x_{t,k-1}^i-x_t\|^2\notag  \notag\\
&+4K\eta_L^2\sigma_{G}^2+4K\eta_L^2(A^2+1)\|\nabla \tilde{f}(x_t)\|^2   \notag \\
&\leq (1+\frac{1}{K-1})\E\|x_{t,k-1}^i-x_t\|^2+ \eta_L^2\sigma_{L}^2+4K\eta_L^2\sigma_{G}^2+4K(A^2+1)\|\eta_L\nabla \tilde{f}(x_t)\|^2  \, .
\end{align}

Unrolling the recursion, we obtain:

\begin{align}
&\quad \E_t\|x_{t,k}^i-x_t\|^2 \leq \sum_{p=0}^{k-1}(1+\frac{1}{K-1})^p\left[\eta_L^2\sigma_{L}^2+4K\eta_L^2\sigma_{G}^2+4K(A^2+1)\|\eta_L\nabla \tilde{f}(x_t)\|^2\right] \notag\\
&\leq (K-1)\left[(1+\frac{1}{K-1})^K-1\right]\left[\eta_L^2\sigma_{L}^2+4K\eta_L^2\sigma_{G}^2+4K(A^2+1)\|\eta_L\nabla \tilde{f}(x_t)\|^2\right] \notag\\
&\leq 5K(\eta_L^2\sigma_L^2+4K\eta_L^2\sigma_G^2) + 20K^2(A^2+1)\eta_L^2\|\nabla \tilde{f}(x_t)\|^2 \, .
\end{align}

Thus, we can have the following convergence rate of FedEBA+:

Under Assumption <ref>–<ref>, and let constant local and global learning rate $\eta_L$ and $\eta$ be chosen such that $\eta_L < min\left(1/(8LK), C\right)$, where $C$ is obtained from the condition that $\frac{1}{2}-10 L^2\frac{1}{m}\sum_{i-1}^m K^2\eta_L^2(A^2+1)(\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1) \textgreater c \textgreater 0$ ,and $\eta \leq 1/(\eta_LL)$,
the expected gradient norm of FedEBA+ with $\alpha=0$, i.e., only using aggregation strategy <ref>, is bounded as follows:

\begin{align}
\mathop{min} \limits_{t\in[T]} \E\|\nabla f(x_t)\|^2 \leq 2 \left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] (\frac{f_0-f_*}{c\eta\eta_LK T}+\Phi)+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, ,
\end{align}

\begin{align}
\Phi
&= \frac{1}{c} [
\frac{5\eta_L^2KL^2}{2}(\sigma_L^2 +4K\sigma_G^2) + \frac{\eta\eta_L L}{2}\sigma_L^2 +20L^2K^2(A^2+1)\eta_L^2\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2] \, .
\end{align}

where $c$ is a constant, $\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2=\sum_{i=1}^m\left(w_i-p_i\right)^2 / p_i$ represents the chi-square divergence between vectors $\boldsymbol{p}=\left[p_1, \ldots, p_m\right]$ and $ \boldsymbol{w}=\left[w_1, \ldots, w_m\right]$. For common FL algorithms with uniform aggregation or with data ratio as aggregation probability, $w_i=\frac{1}{m}$ or $w_i=\frac{n_i}{N}$.

Based on Lemma <ref>, we first focus on analyzing the optimization error $\epsilon_{opt}$:

\begin{align}
\E_t[\tilde{f}(x_{t+1})] & \overset{(a1)}{\leq} \tilde{f}(x_t) + \left \langle \nabla \tilde{f}(x_t),\E_t[x_{t+1}-x_t] \right \rangle + \frac{L}{2}\E_t[\left \| x_{t+1}-x_t \right \|^2] \notag\\
&=\tilde{f}(x_t)+\left \langle \nabla \tilde{f}(x_t),\E_t[\eta \Delta_t+\eta\eta_L K\nabla \tilde{f}(x_t)-\eta\eta_L K \nabla \tilde{f}(x_t)] \right \rangle+\frac{L}{2}\eta^2\E_t[\left \|\Delta_t \right \|^2]\notag \\
&= \tilde{f}(x_t)-\eta\eta_L K\left \|\nabla \tilde{f}(x_t)\right \|^2 + \eta\underbrace{\left \langle \nabla \tilde{f}(x_t),\E_t[\Delta_t+\eta_L K\nabla \tilde{f}(x_t)] \right\rangle}_{A_1}+\frac{L}{2}\eta^2\underbrace{\E_t\|\Delta_t\|^2}_{A_2} \, ,
\end{align}

where (a1) follows from the Lipschitz continuity condition. Here, the expectation is over the local data SGD and the filtration of $x_t$. However, in the next analysis, the expectation is over all randomness, including client sampling. This is achieved by taking expectation on both sides of the above equation over client sampling.

To begin with, we consider $A_1$:

\begin{align}
A_1&=\left \langle \nabla \tilde{f}(x_t),\E_t[\Delta_t+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle  \notag\\
&=\left \langle \nabla \tilde{f}(x_t),\E_t[-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\eta_Lg_{t,k}^i+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle \notag\\
&\overset{(a2)}{=}\left \langle \nabla \tilde{f}(x_t),\E_t[-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\eta_L\nabla F_i(x_{t,k}^i)+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle \notag\\
&=\left \langle \sqrt{\eta_LK}\nabla \tilde{f}(x_t),-\frac{\sqrt{\eta_L}}{\sqrt{K}}\E_t[\sum_{i=1}^mw_i\sum_{k=0}^{K-1}(\nabla F_i(x_{t,k}^i)-\nabla F_i(x_t))]\right\rangle \notag\\
&\overset{(a3)}{=}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_L}{2K}\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}(\nabla F_i(x_{t,k}^i)-\nabla F_i(x_t)) \right\|^2  \notag \\
&- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \notag\\
&\overset{(a4)}{\leq}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_L}{2}\sum_{k=0}^{K-1}\sum_{i=1}^mw_i\E_t\left\|\nabla F_i(x_{t,k}^i)-\nabla F_i(x_t) \right\|^2 \notag \\
&- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \notag \\
&\overset{(a5)}{\leq}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_LL^2}{2m}\sum_{i=1}^m\sum_{k=0}^{K-1}\E_t\left\|x_{t,k}^i-x_t \right\|^2 - \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \notag \\
&\leq \left(\frac{\eta_LK}{2}+10K^3L^2\eta_L^3(A^2+1)\right)\|\nabla \tilde{f}(x_t)\|^2 + \frac{5L^2\eta_L^3}{2}K^2\sigma_L^2+  10\eta_L^3L^2K^3\sigma_G^2\notag \\
&- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \, ,
\end{align}

where (a2) follows from Assumption <ref>. (a3) is due to $\langle x,y\rangle=\frac{1}{2}\left[\|x\|^2+\|y\|^2-\|x-y\|^2\right]$ and (a4) uses Jensen's Inequality: $\left\|\sum_{i=1}^m w_i z_i\right\|^2 \leq \sum_{i=1}^m w_i\left\|z_i\right\|^2$, (a5) comes from Assumption <ref>.

Then we consider $A_2$:

\begin{align}
A_2&=\E_t\|\Delta_t\|^2 \notag \\
&=\E_t\left\|\eta_L\sum_{i=1}^mw_i\sum_{k=0}^{K-1}g_{t,k}^i\right\|^2 \notag \\
&=\eta_L^2\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}g_{t,k}^i-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2 +\eta_L^2\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2 \notag \\
&\leq \eta_L^2\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\E\|g_i(x_{t,k}^i)-\nabla F_i(x_{t,k}^i)\|^2 +\eta_L^2\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \notag \\
% &\leq     \frac{\eta_L^2}{n}V(\frac{1}{mp_i}\hat{g_i^t})        + \eta_L^2\frac{1}{m^2}\sum_{i=1}^m\sum_{k=0}^{K-1}\E\|g_i(x_{t,k}^i)-\nabla F_i(x_{t,k}^i)\|^2  + \eta_L^2 \E\|\frac{1}{m}\sum_{i=1}^m\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2   \notag \\
& \overset{(a6)}{\leq} \eta_L^2K\sigma_L^2
+ \eta_L^2 \E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2    \, .
\end{align}

where (a6) follows from Assumption <ref>.

Now we substitute the expressions for $A_1$ and $A_2$ and take the expectation over the client aggregation distribution on both sides to make $\tilde{f}(x)$ to $f(x)$. It should be noted that the derivation of $A_1$ and $A_2$ above is based on considering the expectation over the sampling distribution:

\begin{align}
& f(x_{t+1})
\leq f(x_t)-\eta\eta_LK\E_t\left \|\nabla \tilde{f}(x_t)\right \|^2 + \eta\E_t\left \langle \nabla \tilde{f}(x_t),\Delta_t+\eta_LK\nabla \tilde{f}(x_t) \right\rangle +\frac{L}{2}\eta^2\E_t\|\Delta_t\|^2 \notag \\
&\overset{(a7)}{\leq} f(x_t) -\eta\eta_LK\left(\frac{1}{2}-20 L^2 K^2\eta_L^2(A^2+1)(\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1) \right)\E_t\left\|\nabla \tilde{f}(x_t)\right\|^2
\notag \\
&+\frac{5\eta\eta_L^3L^2K^2}{2}(\sigma_L^2 +4K\sigma_G^2)
+\frac{\eta^2\eta_L^2KL}{2}\sigma_L^2 + 20L^2K^3(A^2+1)\eta\eta_L^3\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2 \notag\\
&-\left(\frac{\eta\eta_L}{2K}-\frac{L\eta^2\eta_L^2}{2}\right)\E_t\left\|\frac{1}{m}\sum_{i=1}^m\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2 \notag \\
&\overset{(a8)}{\leq} f(x_t) -c\eta\eta_LK\E\left\|\nabla \tilde{f}(x_t)\right\|^2
+\frac{5\eta\eta_L^3L^2K^2}{2}(\sigma_L^2 +4K\sigma_G^2)  \notag \\
&+\frac{\eta^2\eta_L^2KL}{2}\sigma_L^2 + 20L^2K^3(A^2+1)\eta\eta_L^3\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2
-\left(\frac{\eta\eta_L}{2K}-\frac{L\eta^2\eta_L^2}{2}\right)\E_t\left\|\frac{1}{m}\sum_{i=1}^m\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2  \notag \\
&\overset{(a9)}{\leq} f(x_t) - c\eta\eta_LK\E_t\|\nabla \tilde{f}(x_t)\|^2 +\frac{5\eta\eta_L^3L^2K^2}{2}(\sigma_L^2 +4K\sigma_G^2) \notag \\
&+ \frac{\eta^2\eta_L^2KL}{2}\sigma_L^2 +20L^2K^3(A^2+1)\eta\eta_L^3\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2 \, ,
\end{align}

where (a7) is due to Lemma <ref>, (a8) holds because there exists a constant $c \textgreater 0$ (for some $\eta_L$) satisfying $\frac{1}{2}-10 L^2\frac{1}{m}\sum_{i-1}^m K^2\eta_L^2(A^2+1)(\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1) \textgreater c \textgreater 0$,
and  the (a9) follows from $\left(\frac{\eta\eta_L}{2K}-\frac{L\eta^2\eta_L^2}{2}\right) \geq 0$ if $\eta\eta_l\leq \frac{1}{KL}$.

Rearranging and summing from $t=0,\ldots,T-1$, we have:

\begin{align}
\sum_{t=1}^{T-1}c\eta\eta_LK\E\|\nabla \tilde{f}(x_t)\|^2 \leq f(x_0)-f(x_T)+T(\eta\eta_L K)\Phi \, .
\end{align}

Which implies:

\begin{align}
\frac{1}{T}\sum_{t=1}^{T-1} \E\|\nabla \tilde{f}(x_t)\|^2\leq \frac{f_0-f_*}{c\eta\eta_LK T}+\Phi \, ,
\end{align}

\begin{align}
\Phi
&= \frac{1}{c} [
\frac{5\eta_L^2KL^2}{2}(\sigma_L^2 +4K\sigma_G^2) + \frac{\eta\eta_L L}{2}\sigma_L^2 +20L^2K^2(A^2+1)\eta_L^2\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2] \, .
\end{align}

Then, given the result of $\epsilon_{opt}$, we can derive the convergence rate of $\|\nabla f(x_t)\|$ by substitute $\epsilon_{opt}$ back to (<ref>):

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2 & \leq 2\left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] \epsilon_{\mathrm{opt}}+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \\
&\leq 2 \left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] (\frac{f_0-f_*}{c\eta\eta_LK T}+\Phi)+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, .
\label{app convergence upper bound of FedEBa}
\end{align}

Suppose $\eta_L$ and $\eta$ are $\eta_L=\mathcal{O}\left(\frac{1}{\sqrt{T}KL}\right)$ and $\eta=\mathcal{O}\left(\sqrt{Km}\right)$ such that the conditions mentioned above are satisfied. Then for sufficiently large T, the iterates of FedEBA+ with $\alpha = 0$ satisfy:

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2
&\leq \mathcal{O}\left(\frac{(f^0-f^*)}{\sqrt{mKT}} \right)+\mathcal{O}\left(\frac{\sqrt{m}\sigma_L^2}{2\sqrt{KT}} \right) + \mathcal{O}\left(\frac{5(\sigma_L^2+4K\sigma_G^2)}{2KT} \right) \notag \\
&+ \mathcal{O}\left(\frac{20(A^2+1)\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2}{T} \right) + 2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, .
\end{align}

§.§ Analysis with $\alpha \neq 0$

To derivate the convergence rate of FedEBA+ with $\alpha \neq 0$, we need the following assumption:
[Distance bound between practical aggregated gradient and ideal fair gradient]

In each round, we assume the aggregated gradient $\nabla \overline{f}(x_t)=\sum_{i\in S_t}p_iF_i(x_t)$ and the fair gradient $\nabla \tilde{f}(x_t)$ is bounded:
$\E\| \nabla \overline{f}(x_t) -\nabla \tilde{f}(x_t)\|^2 \leq \rho^2$, $\forall i,t$.

To simplify the notation, we define $h_{t,k}^i = (1-\alpha)\nabla F_i(x_{t,k}^i )+ \alpha \nabla \overline{f}(x_t)$.

For any step-size satisfying $\eta_L \leq \frac{1}{8LK}$, we can have the following results:

\begin{align}
\E\|x_{i,k}^t-x_t\|^2 &\leq 5K(1-\alpha)^2(\eta_L^2\sigma_L^2+6K\eta_L^2\sigma_G^2) + +30K^2\eta_L^2\alpha^2\rho^2 \notag \\
&+ 30K^2\eta_L^2(1+A^2(1-\alpha)^2)\|\nabla \tilde{f}(x_t)\|^2 \, .
\end{align}

\begin{align}
&\quad \E_t\|x_{t,k}^i-x_t\|^2 \notag \\
&=\E_t\|x_{t,k-1}^i-x_t-\eta_L h_{t,k-1}^t\|^2   \notag\\
&=\E_t\|x_{t,k-1}^i-x_t-\eta_L ( (1-\alpha) g_{t,k-1}^t + \alpha \nabla\overline{f}(x_t) -(1-\alpha)\nabla F_i(x_{t,k-1}^i) \notag \\
&+(1-\alpha)\nabla F_i(x_{t,k-1}^i)
-(1-\alpha)\nabla F_i(x_t)
+(1-\alpha)\nabla F_i(x_t) +\nabla \tilde{f}(x_t)-\nabla \tilde{f}(x_t)  ) \|^2     \notag\\
% &\leq (1+\frac{1}{2K-1})\E_t\|x_{t,k-1}^i-x_t\|^2+\eta_L^2(1-\alpha)^2\E_t\|(g_{t,k-1}^t-\nabla F_i(x_{t,k}^i))\|^2 \notag \\
& +4K \E_t[\|\eta_L(\nabla F_i(x_{t,K-1}^i)-\nabla F_i(x_t))\|^2] + 4K\eta_L^2\E_t\|\nabla F_i(x_t)\|^2              \notag\\
& \leq (1+\frac{1}{2K-1})\E_t\|x_{t,k-1}^i-x_t\|^2+(1-\alpha)^2\eta_L^2\sigma_{L}^2+6K\eta_L^2L^2\E_t\|x_{t,k-1}^i-x_t\|^2\notag  \notag\\
&+6K\eta_L^2\alpha^2\E\|\nabla \overline{f}(x_t)-\nabla \tilde{f}(x_t) \|^2+6K\eta_L^2(1-\alpha)^2(\sigma_G^2+A^2\|\nabla \tilde{f}(x_t)\|^2)+ 6K\eta_L^2\|\nabla \tilde{f}(x_t)\|^2   \notag \\
& \leq (1+\frac{1}{K-1})\E_t\|x_{t,k-1}^i-x_t\|^2+(1-\alpha)^2\eta_L^2\sigma_{L}^2 \notag  \notag\\
&+6K\eta_L^2\alpha^2\rho^2+6K\eta_L^2(1-\alpha)^2(\sigma_G^2+A^2\|\nabla \tilde{f}(x_t)\|^2)+ 6K\eta_L^2\|\nabla \tilde{f}(x_t)\|^2 \, ,
% &\leq (1+\frac{1}{K-1})\E\|x_{t,k-1}^i-x_t\|^2+ (1-\alpha)^2\eta_L^2\sigma_{L}^2+4K\eta_L^2\sigma_{G}^2+4K(A^2+1)\|\eta_L\nabla \tilde{f}(x_t)\|^2  \, .
\end{align}

Unrolling the recursion, we obtain:

\begin{align}
&\quad \E_t\|x_{t,k}^i-x_t\|^2 \notag\\
&\leq \sum_{p=0}^{k-1}(1+\frac{1}{K-1})^p\left((1-\alpha)^2\eta_L^2\sigma_{L}^2+6K(1-\alpha)^2\eta_L^2\sigma_{G}^2
+6K\alpha^2\eta_L^2\rho^2 \right. \notag \\
&\left.+6K\eta_L^2(A^2(1-\alpha)^2+1)\|\nabla \tilde{f}(x_t)\|^2\right) \notag\\
&\leq (K-1)\left[(1+\frac{1}{K-1})^K-1\right]\left[(1-\alpha)^2\eta_L^2\sigma_{L}^2  \right.\notag\\
& \left. +6K(1-\alpha)^2\eta_L^2\sigma_{G}^2+6K\alpha^2\eta_L^2\rho^2 +6K\eta_L^2(A^2(1-\alpha)^2+1)\|\nabla \tilde{f}(x_t)\|^2\right] \notag\\
&\leq 5K\eta_L^2(1-\alpha)^2(\sigma_L^2+6K\sigma_G^2) +30K^2\eta_L^2\alpha^2\rho^2 + 30K^2\eta_L^2(A^2(1-\alpha)^2+1)\|\nabla \tilde{f}(x_t)\|^2 \, .
\end{align}

Similarly, to get the convergence rate of objective $f(x_t)$, we first focus on $\tilde{f}(x_t)$:

\begin{align}
&\E_t[\tilde{f}(x_{t+1})]  \overset{(a1)}{\leq} \tilde{f}(x_t) + \left \langle \nabla \tilde{f}(x_t),\E_t[x_{t+1}-x_t] \right \rangle + \frac{L}{2}\E_t[\left \| x_{t+1}-x_t \right \|^2] \notag\\
&=\tilde{f}(x_t)+\left \langle \nabla \tilde{f}(x_t),\E_t[\eta \Delta_t+\eta\eta_L K\nabla \tilde{f}(x_t)-\eta\eta_L K \nabla \tilde{f}(x_t)] \right \rangle+\frac{L}{2}\eta^2\E_t[\left \|\Delta_t \right \|^2]\notag \\
&= \tilde{f}(x_t)-\eta\eta_L K\left \|\nabla \tilde{f}(x_t)\right \|^2 + \eta\underbrace{\left \langle \nabla \tilde{f}(x_t),\E_t[\Delta_t+\eta_L K\nabla \tilde{f}(x_t)] \right\rangle}_{A_1}+\frac{L}{2}\eta^2\underbrace{\E_t\|\Delta_t\|^2}_{A_2} \, ,
\end{align}

where (a1) follows from the Lipschitz continuity condition. Here, the expectation is over the local data SGD and the filtration of $x_t$. However, in the next analysis, the expectation is over all randomness, including client sampling. This is achieved by taking expectation on both sides of the above equation over client sampling.

To begin with, we consider $A_1$:

\begin{align}
&A_1=\left \langle \nabla \tilde{f}(x_t),\E_t[\Delta_t+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle  \notag\\
&=\left \langle \nabla \tilde{f}(x_t),
\E_t[-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\eta_Lh_{t,k}^i+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle \notag\\
&\overset{(a2)}{=}\left \langle \nabla \tilde{f}(x_t),
\E_t[-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\eta_L[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \overline{f}(x_t)]+\eta_LK\nabla \tilde{f}(x_t)]\right\rangle \notag\\
&= \langle \sqrt{\eta_LK}\nabla \tilde{f}(x_t), \notag\\
&-\frac{\sqrt{\eta_L}}{\sqrt{K}}\E_t\left(\sum_{i=1}^mw_i\sum_{k=0}^{K-1}(1-\alpha)[\nabla F_i(x_{t,k}^i)-\nabla \tilde{f}(x_t)]  +\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\alpha[\nabla \overline{f}(x_t)-\nabla \tilde{f}(x_t)]\right)\rangle \notag\\
&\overset{(a3)}{=}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2
- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2 \notag\\
&+\frac{\eta_L}{2K}\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\left((1-\alpha)[\nabla F_i(x_{t,k}^i)-\nabla \tilde{f}(x_t)]+\alpha[\nabla \overline{f}(x_t)-\nabla \tilde{f}(x_t)]\right)\right\|^2 \notag \\
&\overset{(a4)}{\leq}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_L(1-\alpha)^2}{2}\sum_{k=0}^{K-1}\sum_{i=1}^mw_i\E_t\left\|\nabla F_i(x_{t,k}^i)-\nabla F_i(x_t) \right\|^2 \notag \\
&+\frac{\eta_L\alpha^2}{2}\sum_{k=0}^{K-1}\sum_{i=1}^mw_i\E\|\nabla \overline{f}(x_t)-\nabla \tilde{f}(x_t)\|^2
- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2 \notag \\
&\overset{(a5)}{\leq}\frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_L(1-\alpha)^2L^2}{2m}\sum_{i=1}^m\sum_{k=0}^{K-1}\E_t\left\|x_{t,k}^i-x_t \right\|^2 \notag \\
&+\frac{\eta_L\alpha^2}{2m}\sum_{i=1}^m\sum_{k=0}^{K-1}\E\|\nabla \overline{f}(x_t)-\nabla \tilde{f}(x_t)\|^2
- \frac{\eta_L}{2 K}\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2 \notag \\
&\leq \frac{\eta_LK}{2}\|\nabla \tilde{f}(x_t)\|^2+\frac{\eta_L(1-\alpha)^2}{2m}\sum_{i=1}^m\sum_{k=0}^{K-1}\left(5K\eta_L(1-\alpha)^2(\sigma_L^2+6K\sigma_G^2)+30K^2\eta_L^2[\alpha^2\rho^2 \right.\notag \\
&\left. +(1+A^2(1-\alpha)^2)\|\nabla \tilde{f}(x_t\|^2] \right)
+\frac{\eta_L^2\alpha^2}{2}K\rho^2 - \frac{\eta_L}{2K}\E\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2 \, ,
\end{align}

where (a2) follows from Assumption <ref>. (a3) is due to $\langle x,y\rangle=\frac{1}{2}\left[\|x\|^2+\|y\|^2-\|x-y\|^2\right]$ and (a4) uses Jensen's Inequality: $\left\|\sum_{i=1}^m w_i z_i\right\|^2 \leq \sum_{i=1}^m w_i\left\|z_i\right\|^2$, (a5) comes from Assumption <ref>.

Then we consider $A_2$:

\begin{align}
A_2&=\E_t\|\Delta_t\|^2 \notag \\
&=\E_t\left\|\eta_L\sum_{i=1}^mw_i\sum_{k=0}^{K-1}h_{t,k}^i\right\|^2 \notag \\
&=\eta_L^2\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\left[ (1-\alpha)\nabla F_i(x_{t,k}^i;\xi_t^i)+\alpha \overline{f}(x_t) \right] \right\|^2 \notag \\
& \leq \eta_L^2\E\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\left[ (1-\alpha)\nabla F_i(x_{t,k}^i;\xi_t^i)+\alpha \overline{f}(x_t) \right] \notag \\
&-(1-\alpha)\nabla F_i(x_{t,k}^i)+(1-\alpha)\nabla F_i(x_{t,k}^i)\|^2 \notag \\
& \overset{(a6)}{\leq} \eta_L^2K(1-\alpha)^2\sigma_L^2  + \eta_L^2\E\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2
% &=\eta_L^2\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}g_{t,k}^i-\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2 +\eta_L^2\E_t\left\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2 \notag \\
% &\leq \eta_L^2\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\E\|g_i(x_{t,k}^i)-\nabla F_i(x_{t,k}^i)\|^2 +\eta_L^2\E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2 \notag \\
% & \overset{(a6)}{\leq} \eta_L^2K\sigma_L^2
% + \eta_L^2 \E_t\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\|^2    \, .
\end{align}

where (a6) follows from Assumption <ref>.

Now we substitute the expressions for $A_1$ and $A_2$ and take the expectation over the client sampling distribution on both sides. It should be noted that the derivation of $A_1$ and $A_2$ above is based on considering the expectation over the sampling distribution:

\begin{align}
& f(x_{t+1})
\leq f(x_t)-\eta\eta_LK\E_t\left \|\nabla \tilde{f}(x_t)\right \|^2 + \eta\E_t\left \langle \nabla \tilde{f}(x_t),\Delta_t+\eta_LK\nabla \tilde{f}(x_t) \right\rangle +\frac{L}{2}\eta^2\E_t\|\Delta_t\|^2 \notag \\
&\overset{(a7)}{\leq} f(x_t) -\eta\eta_LK\left(\frac{1}{2}-30\alpha^2 L^2 K^2\eta_L^2((1-\alpha)^2A^2+1) \right)\E\left\|\nabla \tilde{f}(x_t)\right\|^2 \notag \\
&+\frac{5(1-\alpha)^2\eta\eta_L^3L^2K^2}{2}\left[5(1-\alpha)^2(\sigma_L^2 +6K\sigma_G^2) + 30K\alpha^2\rho^2 \right]
+\frac{\eta\eta_L^2\alpha^2}{2}K\rho^2 \notag \\
&+ \frac{L\eta^2\eta_L^2}{2}(1-\alpha)^2K\sigma_L^2 - (\frac{\eta\eta_L}{2K}-\frac{\eta^2\eta_L^2L}{2})\E\|\sum_{i=1}^mw_i\sum_{k=0}^{K-1}[(1-\alpha)\nabla F_i(x_{t,k}^i)+\alpha \nabla \overline{f}(x_t)]\|^2
% &\overset{(a8)}{\leq} f(x_t) -c\eta\eta_LKE\left\|\nabla \tilde{f}(x_t)\right\|^2
% +\frac{5\eta\eta_L^3L^2K^2}{2}(\sigma_L^2 +4K\sigma_G^2)  \notag \\
% &+\frac{\eta^2\eta_L^2KL}{2}\sigma_L^2 + 20L^2K^3(A^2+1)\eta\eta_L^3\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2
% -\left(\frac{\eta\eta_L}{2K}-\frac{L\eta^2\eta_L^2}{2}\right)\E_t\left\|\frac{1}{m}\sum_{i=1}^m\sum_{k=0}^{K-1}\nabla F_i(x_{t,k}^i)\right\|^2  \notag \\
% &\overset{(a9)}{\leq} f(x_t) - c\eta\eta_LK\E\|\nabla \tilde{f}(x_t)\|^2 +\frac{5\eta\eta_L^3L^2K^2}{2}(\sigma_L^2 +4K\sigma_G^2) + \frac{\eta^2\eta_L^2KL}{2}\sigma_L^2 +20L^2K^3(A^2+1)\eta\eta_L^3\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2\sigma_G^2 \, ,
\end{align}

where $\frac{1}{2}-15\alpha^2 L^2 K^2\eta_L^2((1-\alpha)^2A^2+1) \textgreater c \textgreater 0$ and $\frac{\eta\eta_L}{2K}-\frac{\eta\eta_L^2L}{2}\geq 0$.

Rearranging and summing from $t=0,\ldots,T-1$, we have:

\begin{align}
\sum_{t=1}^{T-1}c\eta\eta_LK\E\|\nabla \tilde{f}(x_t)\|^2 \leq f(x_0)-f(x_T)+T(\eta\eta_L K)\Phi \, .
\end{align}

Which implies:

\begin{align}
\frac{1}{T}\sum_{t=1}^{T-1} \E\|\nabla \tilde{f}(x_t)\|^2\leq \frac{f_0-f_*}{c\eta\eta_LK T}+\tilde{\Phi} \, ,
\end{align}

\begin{align}
\tilde{\Phi}
&= \frac{1}{c} [
\frac{5\eta_L^2KL^2(1-\alpha)^4}{2}(\sigma_L^2 +6K\sigma_G^2) + 15K^2\eta_L^2(1-\alpha)^2\alpha^2\rho^2 +\frac{\eta\eta_L L(1-\alpha)^2}{2}\sigma_L^2 +\frac{\eta_L\alpha^2\rho^2}{2}] \, .
\label{app convergence upper bound of FedEBA+}
\end{align}

Then, given the result of $\epsilon_{opt}$, we can derive the convergence rate of $\|\nabla f(x_t)\|$ by substitute $\epsilon_{opt}$ back to (<ref>):

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2 & \leq 2\left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] \epsilon_{\mathrm{opt}}+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \\
&\leq 2 \left[\chi_{\boldsymbol{w} \| \boldsymbol{p}}^2A^2+1\right] (\frac{f_0-f_*}{c\eta\eta_LK T}+\tilde{\Phi})+2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, .
\end{align}

Suppose $\eta_L$ and $\eta$ are $\eta_L=\mathcal{O}\left(\frac{1}{\sqrt{T}KL}\right)$ and $\eta=\mathcal{O}\left(\sqrt{Km}\right)$ such that the conditions mentioned above are satisfied. Then for sufficiently large T, the iterates of FedEBA+ with $\alpha \neq0$ satisfy:

\begin{align}
\min _{t \in[T]}\left\|\nabla f\left(\boldsymbol{x}_t\right)\right\|^2
&\leq \mathcal{O}\left(\frac{(f^0-f^*)}{\sqrt{mKT}} \right)+\mathcal{O}\left(\frac{(1-\alpha)^2\sqrt{n}\sigma_L^2}{2\sqrt{KT}} \right) + \mathcal{O}\left(\frac{5(1-\alpha)^2(\sigma_L^2+6K\sigma_G^2)}{2KT} \right) \notag \\
% &+ \mathcal{O}\left(\frac{20(A^2+1)\chi_{\boldsymbol{w} \| \boldsymbol{p}}\sigma_G^2}{T} \right)
&+ \mathcal{O}\left(\frac{15(1-\alpha)^2\alpha^2\rho^2}{T}\right) + \mathcal{O}\left(\frac{\alpha^2\rho^2}{2\sqrt{T}K}\right)
+ 2 \chi_{\boldsymbol{w} \| \boldsymbol{p}}^2 \sigma_G^2 \, .
\end{align}

§ UNIQUENESS OF OUR AGGREGATION STRATEGY

In this section, we prove the proposed entropy-based aggregation strategy is unique.

Recall our optimization objective of constrained maximum entropy:

\begin{align}
H(p(x)) = -\sum(p(x)  \log(p(x))) \, ,
\end{align}

subject to certain contains, which is $\sum_i p_i =1, p_i\geq 0, \sum_i p_i f_i = \tilde{f}$.

Based on equation <ref>, and writing the entropy in matrix form, we have:

\begin{align}
H_{i, j}(p)= \begin{cases}p_i(\frac{f_i}{\tau} - \log \sum e^{f_i/\tau})=-a p_i & \text { for } i=j \\ 0 & \text { otherwise }\end{cases}  \, ,
\end{align}

where $a$ is some positive constant.

For every non-zero vector $v$ we have that:

\begin{align}
v^T H(p) v=\sum_{j \in \mathcal{N}} -ap_i v_j^2<0 .
\end{align}

The Hessian is thus negative definite.

Furthermore, since the constraints are linear, both convex and concave, the constrained maximum entropy function is strictly concave and thus has a unique global maximum.

§ FAIRNESS ANALYSIS VIA VARIANCE

To demonstrate the ability of FedEBA+ to enhance fairness in federated learning, we first employ a two-user toy example to demonstrate how FedEBA+ can achieve a more balanced performance between users in comparison to FedAvg and q-FedAvg, thus ensuring fairness. Additionally, we use a general class of regression models to show how FedEBA+ reduces the variance among users and thus improves fairness.Similarly, to simplify the analysis, we consider the degenerate scenario of FedEBA+ where the parameter $\alpha=0$.

§.§ Toy Case for Illustrating Fairness

In this section, we examine the performance fairness of our algorithm.
In particular, we consider two clients participating in training, each with a regression model:
$f_1(x_t) = 2(x-2)^2$,
$f_1(x_t) = \frac{1}{2}(x+4)^2$.

\begin{align}
\nabla f_1(x_t) = 4(x-2)\, ,
\end{align}

\begin{align}
\nabla f_2(x_t) = (x+4) \, .
\end{align}

When the global model parameter $x_t = 0$ is sent to each client, each client will update the model by running gradient decent, here w.l.o.g, we consider one single-step gradient decent, and stepsize $\lambda = \frac{1}{4}$:

\begin{align}
x_1^{t+1} = x_t - \lambda \nabla f_1(x_t) = 2 \, . \\
x_2^{t+1} = x_t - \lambda \nabla f_2(x_t) = -1 \, .
\end{align}

Thus, for uniform aggregation:

\begin{align}
x^{t+1}_{uniform} = \frac{1}{2}(x_1^{t+1}+x_2^{t+1})=\frac{1}{2} \, .
\end{align}

While for FedEBA+:

\begin{align}
x^{t+1}_{EBA+}=\frac{e^{f_1(x_1^{t+1})}}{e^{f_1(x_1^{t+1})}+e^{f_2(x_2^{t+1})}}x_1^{t+1} +\frac{e^{f_2(x_2^{t+1})}}{e^{f_1(x_1^{t+1})}+e^{f_2(x_2^{t+1})}}x_2^{t+1} \approx -0.1 \, .
\end{align}

\begin{align}
\mathbf{Var}_{uniform} = \frac{1}{2}\sum_{i=1}^2\left(f_i(x^{t+1}_{uniform})-\frac{1}{2}\sum_{i=1}^2(f_i(x^{t+1}_{uniform})\right) = 2*(2.81)^2 \, . \\
\mathbf{Var}_{EBA+} = \frac{1}{2}\sum_{i=1}^2\left(f_i(x^{t+1}_{EBA+})-\frac{1}{2}\sum_{i=1}^2(f_i(x^{t+1}_{EBA+})\right) = 2*(0.6)^2 \, .
\end{align}

Thus, we prove that FedEBA+ achieves a much smaller variance than uniform aggregation.

Furthermore, for q-FedAvg, we consider $q=2$ that is also used in the proof of  <cit.>:

\begin{align}
\nabla x_1^t = L(x^t - x_1^{t+1})=-2 \, . \\
\nabla x_2^t = L(x^t - x_2^{t+1})=1 \, .
\end{align}

Thus, we have:

\begin{align}
\Delta_1^t = f_1^q(x_t)\nabla x_1^t = 8*(-2) = -16 \, . \\
h_1^t = qf_1^{q-1}(x_t)\|\nabla x_1^t\|^2 + Lf_1^q(x_t) = 1\times 1\times 2^2+8 = 12 \, . \\
\Delta_2^t = f_2^q(x_t)\nabla x_2^t = 8*(1) = 8 \, . \\
h_2^t = qf_2^{q-1}(x_t)\|\nabla x_2^t\|^2 + Lf_2^q(x_t) = 1\times 1\times 1^2+8 = 9 \, .
\end{align}

Finally, we can update the global parameter as:

\begin{align}
x^{t+1}_{qfedavg} = x^t - \frac{\sum_i \Delta_i^t}{\sum_i h_i^t} \approx -0.4 \, .
\end{align}

Then we can easily get:

$$\mathbf{Var}_{qfedavg} =\frac{1}{2}\sum_{i=1}^2\left(f_i(x^{t+1}_{qfedavg})-\frac{1}{2}\sum_{i=1}^m(f_i(x^{t+1}_{qfedavg})\right) = 2*(2.52)^2 $$

In conclusion, we prove that

\begin{align}
\mathbf{Var}_{EBA+} \leq \mathbf{Var}_{qfedavg} \leq \mathbf{Var}_{uniform} \, .
\end{align}

§.§ Analysis Fairness by Generalized Linear Regression Model

Our setting.
In this section, we consider a generalized linear regression setting, which follows from that in <cit.>.

Suppose that the true parameter on client $i$ is $\mathbf{x}_i$, and there are $n$ samples on each client.

The observations are generated by $\hat{y}_{i,k}(\mathbf{x_i},\xi_{i,k}) = T(\xi_{i,k})^{\top}\mathbf{x}_i-A(\mathbf{\mathbf{x}_i})$, where the $A(\xi_{i,k})$ are i.i.d and distributed as $\mathcal{N}\left(0, \sigma_1^2\right)$.

Then the loss on client $i$ is $F_i\left(\mathbf{x}_i\right)=$ $\frac{1}{2 n} \sum_{k=1}^n\left(y_{i,k}-\hat{y}_{i,k}\right)^2$.

We compare the performance of fairness of different aggregation methods. Recall Defination <ref>. We measure performance fairness in terms of the variance of the test accuracy/losses.

Solutions of different methods
First, we derive the solutions of different methods. Let $\boldsymbol{\Xi}_i=\left(T(\xi_{i, 1}), T(\xi_{i, 2}), \ldots, T(\xi_{i, n})\right)^{\top}$ , $\mathbf{A}_i = \left(A(\xi_{i, 1}),A(\xi_{i, 2}),\ldots, A(\xi_{i, n})\right)^{\top}$and $\mathbf{y}_i=\left(y_{i, 1}, y_{i, 2}, \ldots, y_{i, n}\right)^{\top}$. Then the loss on client $i$ can be rewritten as $F_i\left(\mathbf{x}_i\right)=$ $\frac{1}{2 n}\left\|\boldsymbol{\Xi}_i \mathbf{x}_i-\mathbf{y}_i\right\|_2^2$, where $\operatorname{rank}\left(\boldsymbol{\Xi}_i\right)=d$. The least-square estimator of $\mathbf{w}_i$ is

\begin{align}
\left(\boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1}  \boldsymbol{\Xi}_i^{\top} (\mathbf{y}_i+\mathbf{A}_i )\, .
\end{align}

For FedAvg, the solution is defined as $\mathbf{w}^{\text {Avg }}=\operatorname{argmin}_{\mathbf{w} \in \mathbb{R}^d} \frac{1}{m} \sum_{i=1}^m F_i(\mathbf{w})$. One can check that $\mathbf{w}^{\text {Avg }}=\left(\sum_{i=1}^m \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1} \sum_{i=1}^m \boldsymbol{\Xi}_i^{\top} (\mathbf{y}_i+\mathbf{A}_i)=\left(\sum_{i=1}^m \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1} \sum_{i=1}^m \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i \hat{\mathbf{x}}_i +\Lambda$, where $\Lambda = \left(\sum_{i=1}^m \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1}\sum_{i=1}^m \boldsymbol{\Xi}_i^{\top}A_i$.

For our method FedEBA+, the solution of the global model is $\mathbf{w}^{\text {EBA+ }}=\operatorname{argmin}_{\mathbf{w} \in \mathbb{R}^d} \sum_{i=1}^m p_i F_i(\mathbf{w}) = \left(\sum_{i=1}^m p_i \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1} \sum_{i=1}^m p_i \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i \hat{\mathbf{w}}_i+\hat{\Lambda}$, where $p_i  \propto e^{F_i}(\mathbf{w_i})$, and $\Lambda = \left(\sum_{i=1}^mp_i \boldsymbol{\Xi}_i^{\top} \boldsymbol{\Xi}_i\right)^{-1}\sum_{i=1}^mp_i \boldsymbol{\Xi}_i^{\top}A_i$

Following the setting of  <cit.>, to make the calculations clean, we assume  $\boldsymbol{\Xi}_i \boldsymbol{\Xi}_i=$ $n b_i \boldsymbol{I}_d$. Then the solutions of different methods can be simplified as

* FedAvg: $\mathbf{w}^{\text {Avg }}=\frac{\sum_{i=1}^mb_i \hat{(\mathbf{w}}_i+A_i)}{\sum_{i=1}^m b_i} \text {. }$

* FedEBA+: $\mathbf{w}^{\text {Avg }}=\frac{\sum_{i=1}^m b_i p_i(\hat{\mathbf{w}}_i+A_i)}{\sum_{i=1}^m b_ip_i} \text {. }$

Test Loss
We compute the test losses of different methods. In this part, we assume $b_i=b$ to make calculations clean. This is reasonable since we often normalize the data.

Recall that the dataset on client $i$ is $\left(\boldsymbol{\Xi}_i, \mathbf{y}_i\right)$, where $\boldsymbol{\Xi}_i$ is fixed and $\mathbf{y}_i$ follows Gaussian distribution $\mathcal{N}\left(\boldsymbol{\Xi}_i \mathbf{w}_i, \sigma_2^2 \boldsymbol{I}_n\right)$. Then the data heterogeneity across clients only lies in the heterogeneity of $\mathbf{w}_i$. Besides, since distribution of $\Lambda$ also follows gaussian distribution $\mathcal{N}\left(0, \sigma_1^2 \boldsymbol{I}_n\right)$, thus $w_i+A_i$ follows from $\mathcal{N}\left(\boldsymbol{\Xi}_i \mathbf{w}_i, \sigma^2 \boldsymbol{I}_n\right)$, where $\sigma^2= \sigma_1^2+\sigma_2^2$. Then,
we can obtain the distribution of the solutions of different methods.
Let $\overline{\mathbf{w}}=\frac{\sum_{i=1}^N \mathbf{w}_i}{N}$. We have

* FedAvg: $\mathbf{w}^{\text {Avg }} \sim \mathcal{N}\left(\overline{\mathbf{w}}, \frac{\sigma^2}{b N n} \boldsymbol{I}_d\right)$.

* FedEBA+:  $\mathbf{w}^{\text {EBA+ }} \sim \mathcal{N}\left(\tilde{\mathbf{w}}, \sum_{i=1}^N p_i^2\frac{\sigma^2}{b  n} \boldsymbol{I}_d\right)$, where $ \tilde{\mathbf{w}} = \sum_{i=1}^N p_i w_i$.

Since $\boldsymbol{\Xi}_i$ is fixed, we assume the test data is $\left(\boldsymbol{\Xi}_i, \mathbf{y}_i^{\prime}\right)$ where $\mathbf{y}_i^{\prime}=\boldsymbol{\Xi}_i \mathbf{w}_i+\mathbf{z}_i^{\prime}$ with $\mathbf{z}_i^{\prime} \sim$ $\mathcal{N}\left(\mathbf{0}_n, \sigma_z^2 \boldsymbol{I}_n\right)$ independent of $\mathbf{z}_i$. Then the test loss on client $k$ is defined as:

\begin{align}
F_i^{\mathrm{te}}\left(\mathbf{x}_i\right) & =\frac{1}{2 n} \mathbb{E}\left\|\mathbf{\Xi}_i \mathbf{x}_i + A_i-\mathbf{y}_i^{\prime}\right\|_2^2 \notag \\
& =\frac{1}{2 n} \mathbb{E}\left\|\boldsymbol{\Xi}_i \mathbf{x}_i + A_i-\left(\mathbf{\Xi}_i \mathbf{w}_i+\mathbf{z}_i^{\prime}\right)\right\|_2^2 \notag \\
& =\frac{\tilde{\sigma}^2}{2}+\frac{1}{2 n} \mathbb{E}\left\|\mathbf{\Xi}_i\left(\mathbf{x}_i-\mathbf{w}_i\right)\right\|_2^2 \notag \\
& =\frac{\tilde{\sigma}^2}{2}+\frac{b}{2} \mathbb{E}\left\|\mathbf{x}_i-\mathbf{w}_i\right\|_2^2 \notag \\
& =\frac{\tilde{\sigma}^2}{2}+\frac{b}{2} \operatorname{tr}\left(\operatorname{var}\left(\mathbf{x}_i\right)\right)+\frac{b}{2}\left\|\mathbb{E} \mathbf{x}_i-\mathbf{w}_i\right\|_2^2 \, .
\end{align}

where $\tilde{\sigma}$ is a Gaussian variance, which comes from the fact that both $A_i$ and $z_i^{\prime}$ follow Gaussian distribution with mean 0.

Therefore, for different methods, we can compute that

\begin{align}
f_i^{\mathrm{te}}\left(\mathbf{w}^{\mathrm{Avg}}\right)=\frac{\tilde{\sigma}^2}{2}+\frac{\tilde{\sigma}^2 d}{2 N n}+\frac{b}{2}\left\|\overline{\mathbf{w}}-\mathbf{w}_i\right\|_2^2
\end{align}

\begin{align}
f_i^{\mathrm{te}}\left(\mathbf{w}^{\mathrm{EBA+}}\right)=\frac{\tilde{\sigma}^2}{2}+\sum_{k=1}^N p_i^2 \frac{\tilde{\sigma}^2 d}{2  n}+\frac{b}{2}\left\|\tilde{\mathbf{w}}-\mathbf{w}_i\right\|_2^2  \, .
\label{test loss of EBA}
\end{align}

Define $\operatorname{var}$ as the variance operator.
Then we give the formal version of Theorem <ref>.

The variance of test losses on different clients of different aggregation methods are as follows:

\begin{align}
V^{\text{Avg}}=\operatorname{var}\left(f_i^{t e}\left(\mathbf{w}^{A v g}\right)\right)=\frac{b^2}{4} \operatorname{var}\left(\left\|\overline{\mathbf{w}}-\mathbf{w}_i\right\|_2^2\right)  \, . \\
V^{\text{EBA+}}=\operatorname{var}\left(f_i^{t e}\left(\mathbf{w}^{EBA+}\right)\right)=\frac{b^2}{4} \operatorname{var}\left(\left\|\tilde{\mathbf{w}}-\mathbf{w}_i\right\|_2^2\right)  \, .
\end{align}

Based on a simple fact: assign larger weights to smaller values and smaller weights to larger values, and give a detailed mathematical proof to show that the variance of such a distribution is smaller than the variance of a uniform distribution. Which means $V^{\text{EBA+}}\leq V^{\text{Avg}}$.

Formally, let $\|\tilde{\mathbf{w}}-\mathbf{w}_i\|^2 = A_i$.
From equation (<ref>), we know that $f_i^{te}(\mathbf{w^{EBA+}}) \propto A_i$, and $p_i \propto f_i$. Thus, we know $p_i \propto A_i$.

Then, we consider the expression of $V^{\text{EBA+}} = \frac{b^2}{4}var_i(A_i)$.
Assume $A_i = [A_1> A_2> \cdots> A_m]$, then the corresponding aggregation probability distribution is $[p_1>p_2>\cdots>p_m]$.

We show the analysis of variance with set size 2, while the analysis can be easily extended to the number $K$.
For FedEBA+, we have

\begin{align}
var_i(A_i) &= \sum_{i=1}^m p_i \left(A_i-\sum_i p_i A_i\right)^2 \\
& = p_1(A_1 - (p_1A_1 + p_2A_2))^2 +p_2(A_2 - (p_1A_1 + p_2A_2))^2\\
&= p_1(1-p_1)^2A_1^2 - 2(1-p_1)p_1p_2A_1A_2 + p_1p_2^2A_2^2 \notag \\
&\ + p_2(1-p_2)^2A_2^2 - 2(1-p_2)p_1p_2A_1A_2 + p_1^2p_2A_1^2 \\
&=(p_1p_2^2+p_1^2p_2)A_1^2 - 2p_1p_2(2-p_1-p_2)A_1A_2 + (p_1p_2^2+p_1^2p_2)A_2^2 \\
&\overset{(a1)}{=}p_1p_2(A_1^2+A_2^2) - 2p_1p_2A_1A_2 \\
& = p_1p_2(A_1-A_2)^2 \, ,
\end{align}

where $(a1)$ follows from the fact $\sum_i p_i =1$.

According to our previous analysis, $p_1 >p_2$ while $A_1 > A_2$.According to Cauchy-Schwarz inequality, one can easily prove that $p_1p_2 \leq \frac{1}{4}$, where $\frac{1}{4}$ comes from uniform aggregation.

Therefore, we prove that $V^{\text{EBA+}}\leq V^{\text{Avg}}$.

§ PARETO-OPTIMALITY ANALYSIS

In this section, we demonstrate the Proposition <ref>. In particular, we consider the degenerate setting of FedEBA+ where the parameter $\alpha=0$. We first provide the following lemma that illustrates the correlation between Pareto-optimality and monotonicity.

The allocation strategy $\varphi(p)=\underset{p \in \mathcal{P}}{\arg \max }~h(p(f))$ is Pareto optimal if $h$ is a strictly monotonically increasing function.

In order for this paper to be self-contained, we restate the proof of Property 1 in <cit.> here:

Proof Sketch:
We prove the result by contradiction. Consider that $p^*=\varphi(\mathcal{P})$ is not Pareto optimal; thus, there exists an alternative $p \in \mathcal{P}$ such that
\begin{align}
\sum_ip_if_i=\frac{\sum_ip_i\log p_i}{Z} \geq \sum_ip_i^*f_i=\frac{\sum_ip_i^*\log p_i^*}{Z}  \, ,
\end{align}

where $Z>0$ is a constant. Since $h(p)$ is a strictly monotonically increasing function, we have $h(p)>h\left(p^*\right)$. This is a contradiction because $h^*$ maximizes $h(\cdot)$.

According to the above lemma, to show our algorithm achieves Pareto-optimal, we only need to show it is monotonically increasing.

Recall the objective of maximum entropy:

\begin{align}
\mathbb{H}(p) = -\sum p(x) log(p(x)) \, ,
\end{align}

subject to certain constraints on the probabilities $p(x)$.

To show that the proposed aggregation strategy is monotonically increasing, we need to prove that if the constraints on the probabilities $p(x)$ are relaxed, then the maximum entropy of the aggregation probability increases.

One way to do this is to use the properties of the logarithm function. The logarithm function is strictly monotonically increasing. This means that for any positive real numbers a and b, if $a \leq b$, then $\log(a) \leq \log(b)$.

Now, suppose that we have two sets of constraints on the probabilities $p(x)$, and that the second set of constraints is a relaxation of the first set. This means that the second set of constraints allows for a larger set of probability distributions than the first set of constraints.

If we maximize the entropy subject to the first set of constraints, we get some probability distribution $p(x)$. If we then maximize the entropy subject to the second set of constraints, we get some probability distribution $q(x)$ such that $p(x) \leq q(x)$ for all x.

Using the properties of the logarithm function and the definition of the entropy, we have:

\begin{align}
H(p(x)) &= -\sum(p(x)  \log(p(x))) \notag \\
&\leq -\sum (p(x) \log(q(x)))  \notag \\
&= -\sum ((p(x)/q(x))  q(x)  \log(q(x)))  \notag \\
&= H(q(x)) - \sum ((\frac{p(x)}{q(x)} q(x)  \log(p(x)/q(x)))  \notag \\
&\leq H(q(x)) \, .
\end{align}

This means that the entropy $H(q(x))$ is greater or equal to $H(p(x))$ when the second set of constraints is a relaxation of the first set of constraints. As the entropy increases when the constraints are relaxed, the maximum entropy-based aggregation strategy is monotonically increasing.

Up to this point, we proved that our proposed aggregation strategy is monotonically increasing. Combined with the Lemma <ref>, we can prove that equation (<ref>) is Pareto optimal.

§ EXPERIMENT DETAILS

§.§ Experimental Environment

For all experiments, we use NVIDIA GeForce RTX 3090 GPUs. Each simulation trail with 2000 communication rounds and three random seeds.

Federated datasets.
We tested the performance of FedEBA+ on four public datasets: MNIST, Fashion MNIST, CIFAR-10, and CIFAR-100.
We use two methods to split the real datasets into non-iid datasets: (1) following the setting of <cit.>, where 100 clients participate in the federated system, and according to the labels, we divide all the data of MNIST, FashionMNIST, CIFAR-10 and CIFAR-100 into 200 shards separately, and each user randomly picks up 2 shards for local training. (2) we leverage Latent Dirichlet Allocation (LDA) to control the distribution drift with the Dirichlet parameter $\alpha=0.1$.
As for the model, we use an MLP model with 2 hidden layers on MNIST and Fashion-MNIST, and a CNN model with 2 convolution layers on CIFAR-10 and CIFAR-100.

We compared several advanced FL fairness algorithms with FedEBA+, including FedAvg  <cit.>, q-FFL  <cit.>, FedFV <cit.>, FedMGDA+  <cit.>,PropFair <cit.>, TERM <cit.>, and AFL <cit.>. We compare these algorithms on all four datasets.

As shown in Table $3$, we tuned some hyper-parameters of baselines to ensure the performance in line with the previous studies and listed parameters used in FedEBA+. All experiments are running over 2000 rounds for a single local epoch ($K=10$) with local batch size $B_{MNIST} = 200$, $B_{Fashion-MNIST} \in \{50, full\}$, $B_{CIFAR-10} \in \{50, full\}$ and $B_{CIFAR-100} = 64$. The learning rate remains the same for different methods, that is $\eta = 0.1$ on MNIST, Fasion-MNIST, CIFAR-10, $\eta = 0.05$ on Tiny-ImageNet and $\eta = 0.01$ on CIFAR-100 with decay rate $d = 0.999$.

Hyperparameters of all experimental algorithms.

Algorithm     Hyper Parameters
$q-FFL$      $q \in \{0.001, 0.01, 0.1, 0.5, 10, 15\}$

$PropFair$     $M \in \{0.2, 5.0\}, thres = 0.2$

$Scaffold$     ${\mu = 1.0}$

$AFL$     $\lambda \in \{0.01, 0.1, 0.5, 0.7\}$

$TERM$     $T \in \{0.1, 0.5, 0.8\}$

$FedMGDA+$     $\epsilon \in \{0, 0.03, 0.08\}$

$FedProx$     $\mu = 0.1 $

$Scaffold$     $\eta = 1.0 $

$FedFV$       $\alpha \in \{0.1, 0.2, 0.5\}, \tau \in \{0, 1, 10\}$

$FedEBA+$     $\tau \in \{ 0.5, 0.1\}, \alpha \in \{0.0, 0.5,0.9\}$

§ ADDITIONAL EXPERIMENT RESULTS

Fairness of FedEBA+
In this section, we provide additional experimental results to illustrate FedEBA+ is superior over other baselines.

7.611Performance of algorithms on FashionMNIST and CIFAR-10. We report the accuracy of global model, variance fairness, worst $5\%$, and best $5\%$ accuracy. The data is divided into 100 clients, with 10 clients sampled in each round.
All experiments are running over 2000 rounds for a single local epoch ($K=10$) with local batch size $= 50$, and learning rate $\eta = 0.1$. The reported results are averaged over 5 runs with different random seeds. We highlight the best and the second-best results by using bold font and blue text.

2*Algorithm     4cFashionMNIST (MLP)     4cCIFAR-10 (CNN)

(lr)2-5 (lr)6-9
Global Acc.      Var.          Worst 5%      Best 5%      Global Acc.     Var.      Worst 5%      Best 5%

FedAvg                             86.49 0.5± 0.09     62.440.5±4.55      71.270.5±1.14     95.840.5± 0.35     67.790.5±0.35     103.830.5±10.46     45.000.5±2.83     85.130.5±0.82

$q-FFL|_{q=0.001}$                 87.050.5± 0.25     66.670.5± 1.39      72.110.5± 0.03     95.090.5± 0.71     68.530.5± 0.18     97.420.5± 0.79      48.400.5± 0.60     84.700.5± 1.31

$q-FFL|_{q=0.01}$                 86.620.5± 0.03     58.110.5± 3.21      71.360.5± 1.98     95.290.5±0.27      68.850.5± 0.03     95.170.5± 1.85     48.200.5±0.80     84.100.5±0.10

$q-FFL|_{q=0.5}$                   86.570.5± 0.19     54.910.5± 2.82      70.880.5± 0.98     95.060.5±0.17      68.760.5± 0.22     97.810.5± 2.18     48.330.5±0.84     84.510.5±1.33

$q-FFL|_{q=10.0}$                  77.290.5± 0.20     47.200.5± 0.82     61.990.5± 0.48     92.250.5±0.57      40.780.5± 0.06     85.930.5± 1.48     22.700.5±0.10     56.400.5±0.21

75.770.5±0.42     46.580.5±0.75      61.630.5±0.46	     89.600.5±0.42     36.890.5±0.14     79.650.5±5.17      19.300.5±0.70     51.300.5±0.09

$FedMGDA+|_{\epsilon=0.0}$        86.010.5±0.31     58.870.5±3.23	     71.490.5±0.16	     95.450.5±0.43     67.160.5±0.33     97.330.5±1.68     46.000.5±0.79     83.300.5±0.10

$FedMGDA+|_{\epsilon=0.03}$        84.830.5±0.31     58.680.5±11.21     73.830.5±1.43     93.170.5±0.12	     65.190.5±0.87     89.780.5±5.87     48.840.5±1.12     81.940.5±0.67

$FedMGDA+|_{\epsilon=0.08}$        84.810.5±0.29    61.470.5±13.10     73.860.5±0.96     92.940.5±0.04	     65.060.5±0.69     93.700.5±14.10     48.230.5±0.82     82.010.5±0.09

$AFL|_{\lambda=0.7} $             85.140.5±0.18     57.390.5±6.13      70.090.5±0.69     95.940.5±0.09     66.210.5±1.21     79.750.5±1.25      47.540.5±0.61     82.080.5±0.77

$AFL|_{\lambda=0.5} $              84.140.5±0.18     90.760.5±3.33      60.110.5±0.58     96.000.5±0.09     65.110.5±2.44     86.190.5±9.46      44.730.5±3.90     82.100.5±0.62

$AFL|_{\lambda=0.1} $              84.910.5±0.71     69.390.5±6.50      69.240.5±0.35      95.390.5±0.72     65.630.5±0.54     88.740.5±3.39      47.290.5±0.30     82.330.5±0.41

$PropFair|_{M=0.2, thres=0.2}$     85.510.5±0.28     75.270.5±5.38     63.600.5±0.53     97.600.5±0.19      65.790.5±0.53     79.670.5±5.71      49.880.5±0.93     82.400.5±0.40

$PropFair|_{M=5.0, thres=0.2}$     84.590.5±1.01     85.310.5±8.62     61.400.5±0.55     96.400.5±0.29      66.910.5±1.43     78.900.5±6.48      50.160.5±0.56     85.400.5±0.34

$TERM|_{T=0.1}   $              84.310.5±0.38     73.460.5±2.06     68.230.5±0.10     94.160.5±0.16      65.410.5±0.37     91.990.5±2.69      49.080.5±0.66     81.980.5±0.19

$TERM|_{T=0.5}   $              82.190.5±1.41     87.820.5±2.62     62.110.5±0.71     93.250.5±0.39       61.040.5±1.96     96.780.5±7.67      42.450.5±1.73     80.060.5±0.62

$TERM|_{T=0.8}   $                81.330.5±1.21     95.650.5±9.56     56.410.5±0.56     92.880.5±0.70       59.210.5±1.45     82.630.5±3.64      41.330.5±0.68     77.390.5±1.04

$FedFV|_{\alpha=0.1, \tau_{fv}=1} $     86.510.5±0.28     49.730.5±2.26      71.330.5±1.16     95.890.5±0.23      68.940.5±0.27     90.840.5±2.67      50.530.5±4.33     86.000.5±1.23

$FedFV|_{\alpha=0.2, \tau_{fv}=0} $     86.420.5±0.38     52.410.5±5.94     71.220.5±1.35     95.470.5±0.43      68.890.5±0.15     82.990.5±3.10      50.080.5±0.40     86.240.5±1.17

$FedFV|_{\alpha=0.5, \tau_{fv}=10} $     86.880.5±0.26     47.630.5±1.79      71.490.5±0.39     95.620.5±0.29      69.420.5±0.60     78.100.5±3.62      52.800.5±0.34     85.760.5±0.80

$FedFV|_{\alpha=0.1, \tau_{fv}=10} $     86.980.5±0.45     56.630.5±1.85      66.400.5±0.57     98.800.5±0.12     71.100.5±0.44     86.500.5±7.36      49.800.5±0.72     88.420.5±0.25

$FedEBA+|_{\alpha=0, \tau=0.1}$      86.700.5±0.11     50.270.5±5.60      71.130.5±0.69     95.470.5±0.27      69.380.5±0.52     89.490.5±10.95      50.400.5±1.72     86.070.5±0.90

$FedEBA+|_{\alpha=0.5, \tau=0.1}$     87.210.5±0.06     40.020.5±1.58     73.070.5±1.03     95.810.5±0.14     72.390.5±0.47     70.600.5±3.19      55.270.5±1.18     86.270.5±1.16

$FedEBA+|_{\alpha=0.9, \tau=0.1}$     87.500.5±0.19     43.410.5±4.34      72.070.5±1.47     95.910.5±0.19     72.750.5±0.25     68.710.5±4.39      55.800.5±1.28     86.930.5±0.52

Performance of all the methods in terms of Fairness (Var.).

Figure <ref> illustrates that, on the MNIST dataset, FedEBA+ demonstrates faster convergence, increased stability, and superior results in comparison to baselines. As for the CIFAR-10 dataset, its complexity causes some instability for all methods, however, FedEBA+ still concludes the training with the most favorable fairness results.

Performance of FedEBA+ on Fashion-MNIST with different fair angle $\theta$.
This table shows our schedule of using the fair angle $\theta$ to control the gradient alignment times is effective, as it largely reduces the communication rounds with larger angle. In addition, compared with the results of baseline in Table <ref>, the results illustrate that our algorithm keeps effective when we increase the fair angle.
All experiments are running over 2000 rounds on the MLP model for a single local epoch ($K=10$) with local batch size $= 50$ and learning rate $\eta = 0.1$. The reported results are averaged over 5 runs with different random seeds.

$FedEBA+$                     Global Acc.    Var.           Extra Communication Rounds
$\theta = 0^{\circ}$              87.50±0.19     43.41±4.34     2000

$\theta = 15^{\circ}$             87.14±0.12     43.95±5.12     1892

$\theta = 45^{\circ}$             86.94±0.26     46.63±4.38     88

$\theta = 90^{\circ}$             86.78±0.47     48.91±3.62     0

$\theta = 180^{\circ}$            86.78±0.47     48.91±3.62     0

Performance of algorithms on CIFAR-10 using MLP. We report the global model's accuracy, fairness of accuracy, worst $5\%$ and best $5\%$ accuracy. All experiments are running over 2000 rounds for a single local epoch ($K=10$) with local batch size $= 50$, and learning rate $\eta = 0.1$. The reported results are averaged over 5 runs with different random seeds. We highlight the best and the second-best results by using bold font and blue text.

Method                             Global Acc.    Var.           Worst 5%      Best 5%
FedAvg                             46.85±0.65     12.57±1.50     19.84±6.55     69.28±1.17
$q-FFL|_{q=0.1}$                 47.02±0.89     13.16±1.84     18.72±6.94     70.16±2.06

$q-FFL|_{q=0.2}$                 46.91±0.90     13.09±1.84     18.88±7.00     70.16±2.10

$q-FFL|_{q=1.0}$                 46.79±0.73     11.72±1.00     22.80±3.39     68.00±1.60

$q-FFL|_{q=2.0}$                 46.36±0.38     10.85±0.76     24.64±2.17     66.80±2.02

$q-FFL|_{q=5.0}$                 45.25±0.42     9.59±0.36      26.56±1.03     63.60±1.13
$Ditto|_{\lambda=0.0}$             52.78±1.23     10.17±0.24     31.80±2.27     71.47±1.20

$Ditto|_{\lambda=0.5}$             53.77±1.02     8.89±0.32      36.27±2.81     71.27±0.52
$AFL|_{\lambda=0.01}$              52.69±0.19     10.57±0.37     34.00±1.30     71.33±0.57

$AFL|_{\lambda=0.1} $              52.68±0.46     10.64±0.14     33.27±1.75     71.53±0.52
$TERM|_{T=1.0}   $                 45.14±2.25     9.12±0.35      27.07±3.49     62.73±1.37
$FedMGDA+|_{\epsilon=0.01}$        45.65±0.21     10.94±0.87     25.12±2.34     67.44±1.20

$FedMGDA+|_{\epsilon=0.05}$        45.58±0.21     10.98±0.81     25.12±1.87     67.76±2.27

$FedMGDA+|_{\epsilon=0.1}$         45.52±0.17     11.32±0.86     24.32±2.24     68.48±2.68

$FedMGDA+|_{\epsilon=0.5}$         45.34±0.21     11.63±0.69     24.00±1.93     68.64±3.11

$FedMGDA+|_{\epsilon=1.0}$         45.34±0.22     11.64±0.66     24.00±1.93     68.64±3.11
$FedFV|_{\alpha=0.1, \tau_{fv}=1} $     54.28±0.37     9.25±0.42      35.25±1.01     71.13±1.37
$FedEBA|_{\alpha=0.9, \tau=0.1}$      53.94±0.13     9.25±0.95      35.87±1.80     69.93±1.00

$FedEBA+|_{\alpha=0.5, \tau=0.1}$     53.14±0.05     8.48±0.32     36.03±2.08     69.20±0.75

$FedEBA+|_{\alpha=0.9, \tau=0.1}$     54.43±0.24     8.10±0.17     40.07±0.57     69.80±0.16

Table <ref> shows FedEBA+ outperforms other baselines on CIFAR-10 using MLP model. The results in Table <ref> demonstrate that 1) FedEBA+ consistently achieves a smaller variance of accuracy compared to other baselines, thus is fairer. 2) FedEBA+ significantly improves the performance of the worst 5% clients and 3) FedEBA+ performances steady in terms of best 5% clients. A significant improvement in worst 5% is achieved with relatively no compromise in best 5 %, thus is fairer.

Fairness in Different Non-i.i.d. Cases
We adopt two kinds of data splitation strategies to change the degree of non-i.i.d., which are data devided by labels mentioned in the main text, and the data partitioning in deference to the Latent Dirichlet Allocation (LDA) with the Dirichlet parameter . Based on FedAvg, we have experimented with various data segmentation strategies for FedEBA+ to verify the performance of FedEBA+ for scenarios with different kinds of data held by clients.

Performance comparison between FedAvg and FedEBA+ on CIFAR-100 using ResNet18 (devided by Dirichlet Distribution with $\alpha\in\{0.1, 0.5, 1.0\}$). We report the global model's accuracy, fairness of accuracy, worst $5\%$ and best $5\%$ accuracy.
All experiments are running over 2000 rounds for a single local epoch ($K=10$) with local batch size $= 64$, and learning rate $\eta = 0.01$. The reported results are averaged over 5 runs with different random seeds.

2*Algorithm     3cGlobal Acc.     3cVar.     3cWorst 5%     3cBest 5%

(lr)2-4 (lr)5-7 (lr)8-10 (lr)11-13
alpha=0.1     alpha=0.5     alpha=1.0     alpha=0.1     alpha=0.5     alpha=1.0     alpha=0.1     alpha=0.5     alpha=1.0     alpha=0.1     alpha=0.5     alpha=1.0

FedAvg     30.94±0.04     54.69±0.25     64.91±0.02     17.24±0.08     7.92±0.03     5.18±0.06     0.20±0.00     38.79±0.24     54.36±0.11     65.90±1.48     70.10±0.25     75.43±0.39

FedEBA+     33.39±0.22     58.55±0.41     65.98±0.04     16.92±0.04     7.71±0.08     4.44±0.10     0.95±0.15     41.63±0.16     58.20±0.17     68.51±0.21     74.03±0.07     74.96±0.16

Global Accuracy of FedEBA+

The maximum and minimum 5% performance of all baselines and FedEBA+ on CIFAR-10.

We run all methods on the CNN model, regarding the CIFAR-10 figure. Under different hyper-parameters, FedEBA+ can reach a stable high performance of worst 5% while guaranteeing best 5%, as shown in Figure <ref>.

The maximum and minimum 5% performance of all baselines and FedEBA+ on FashionMNSIT.

As for FashionMNIST using MLP model, the worst 5% and best 5% performance of FedEBA+ are similar to that of CIFAR-10. We can see that FedEBA+ has a more significant lead in worst 5% with almost no loss in best 5%, as shown in Figure <ref>.

Ablation study.

For the annealing schedule of $\tau$ in Section <ref>,
Figure <ref> shows that the annealing schedule has advantages in reducing the variance compared with constant $\tau$. Besides, the global accuracy is robust to the annealing strategy, and the annealing strategy is robust to the initial temperature $T_0$.

[Fairness and Accuracy on Fashion-MNIST]

[Fairness and Accuracy on MNIST]

Ablation study for Annealing schedule $\tau$

We provide the ablation studies for $\theta$, the tolerable fair angle.

Performance of $FedEBA+$ under different $\theta$ in terms of global accuracy.

Performance of $FedEBA+$ under different $\theta$ in terms of Max $5\%$ test accuracy.

Performance of $FedEBA+$ under different $\theta$ in terms of Min $5\%$ test accuracy.

The results in Figure <ref> <ref> <ref> show our algorithm is relatively robust to the tolerable fair angle $\theta$, though the choice of $\theta = 45$ may slow the performance slightly on global accuracy and min 5% accuracy over CIFAR-10.

Performance of $FedEBA+$ under different $\theta$ in terms of Fairness (Std.).