Entropy-Based Aggregation for Fair and Effective Federated Learning

Dear reviewer 8Wxv, Thank you very much for your thoughtful review and for recognizing the contributions of our paper. Below is our response to your question.

Q1. Please explain how the convergence rate range mentioned in lines 396 to 397 of the main text is derived.

Thank you for your constructive comment.

From Theorem 5.1, we know that

$\min _{t \in[T]}\mathbb{E}\left\|\nabla f\left(x_t\right)\right\|^2 \leq \mathcal{O}\left(\frac{(f^0-f^*)}{\sqrt{mKT}} \right)+\mathcal{O}\left(\frac{\sqrt{m}\sum_iw_i^2\sigma_L^2}{2\sqrt{KT}} \right) + \mathcal{O}\left(\frac{5(\sigma_L^2+4K\sigma_G^2)}{2KT} \right) \+ \mathcal{O}\left(\frac{20(A^2+1) \chi ^2\sigma_G^2 }{T} \right) \, .$

According to the properties of unified probability, we have $\frac{1}{m} \leq \sum_{i=1}^m w_i^2 \leq 1$. The upper bound arises from $\sum_i w_i^2 \leq \sum_i w_i$, and the lower bound follows from the Cauchy-Schwarz inequality.

When $w_i = \frac{1}{m}$, $\sum_{i=1}^m w_i^2 = \frac{1}{m}$, and substituting this into the convergence rate gives an upper bound of $\mathcal{O}\left(\frac{1}{\sqrt{mKT}} + \frac{1}{T}\right)$.

On the other hand, when $\sum_{i=1}^m w_i^2 = 1$, the convergence rate becomes $\mathcal{O}\left(\frac{\sqrt{m}}{\sqrt{KT}} + \frac{1}{T}\right)$. Therefore, we conclude that the upper bound of the convergence rate lies between $\mathcal{O}\left(\frac{1}{\sqrt{mKT}} + \frac{1}{T}\right)$ and $\mathcal{O}\left(\frac{\sqrt{m}}{\sqrt{KT}} + \frac{1}{T}\right)$.

Q2. The explanation of the entropy-based aggregation method could be more detailed, particularly in terms of how it differs from and improves upon existing methods.

Thank you for your suggestion.

We clarify the differences compared to existing aggregation methods by:

• The aggregation formulation is different. Our aggregation probability $p_i = e^{\frac{F_i(x)/\tau}{Z}}$ is proportional to the exponential term of loss with a controllable parameter $\tau$. Unlike heuristic fair approaches that assign weights proportional to client loss $p_i \propto F_i(x)$[1, 5,6], our method is derived from a well-defined constrained optimization problem.
• The goal is different. Existing entropy-based aggregation methods [3,4] and softmax-based reweighting approaches [5,6] have entirely different objectives from fair FL. These methods focus on improving model accuracy but lack the ability to enhance fairness.
• Novelty in the Entropy Model for FL: To extend entropy to FL fairness, we introduce a novel constrained entropy model, the first of its kind in the FL fairness community. This model incorporates a constraint that adjusts the distribution to prioritize underperforming clients, resulting in a weighted fair aggregation.

The advantages of our approach over existing methods lie in:

• The exponent form and control term $\tau$ benefit the fairness level and enhance existing fair aggregation methods. For our model, $p_i = e^{\frac{F_i(x)/\tau}{Z}}$, the exponent effectively addresses extreme loss (extreme unfairness), since the exponent grows faster with increasing loss. Additionally, the controllable term $\tau$ regulates the fairness level by determining the spread of weights assigned to each client. As Remark 4.2 shows, by choosing an appropriate expression for $\tau$, we can recover existing fair aggregation algorithms like FedAvg, AFL, and q-FFL [2].
• Empirically more effective in fairness than others. Compared with existing fair aggregation methods like q-FFL and TERM, our entropy aggregation (FedEBA+ with $\alpha=0$) shows better performance in both accuracy and fairness, as shown in Tables 1 and 2 of the submission.

[1]Fairness-aware loss history based federated learning heuristic algorithm[J]. Knowledge-Based Systems, 2024, 288: 111467.

[2]Fair Resource Allocation in Federated Learning[C]//International Conference on Learning Representations.

[3]Self-Driven Entropy Aggregation for Byzantine-Robust Heterogeneous Federated Learning. ICML 2024.

[4]Enhancing Federated Learning Convergence with Dynamic Data Queue and Data Entropy-driven Participant Selection[J]. IEEE Internet of Things Journal, 2024.

[5]A dynamic reweighting strategy for fair federated learning[C]//ICASSP 2022.

[6]Fair federated learning for heterogeneous data[C]//9th ACM IKDD CODS and 27th COMAD 2022.

Q3. The concept of "ideal loss" appears somewhat confusing. Since f(x) represents the ideal loss, which signifies the global model’s performance under an ideal training setting, it is unclear why the gradient of the ideal loss can be estimated by averaging local one-step gradients during the model alignment procedure, yet it should be estimated by Equation.10 during the gradient alignment procedure. Could the authors give more intuition to clarify this point?

Thank you for your comment. We would like to clarify that the ideal loss$\tilde{f}(x$) has two different estimations depending on the improvement goals:

• For global accuracy improvement, it is estimated by Eq. (9) instead of Eq. (10). Eq. (9) represents the averaging of local one-step gradients. The rationale for using Eq. (9) as a good estimation for global updates is as follows:
  1. A single local update corresponds to an unshifted update on local data, whereas multiple local updates introduce model bias in heterogeneous FL~[1,2].
  2. The expectation of sampled clients’ data over rounds represents the global data due to unbiased random sampling, as stated in submission L340–343.
• For fairness improvement, it is estimated by Eq. (10), which reweights the current model’s gradient. First, it uses the global model’s loss to calculate the fair weights for each participating client, based on the proposed entropy-based aggregation strategy. Then, using the global model’s gradient ensures an unshifted update on local data, capturing the ideal fair update.

For example, ideally, if each client performs full gradient descent for one local epoch:

• Eq. (9) will represent the true update averaged over all data, similar to centralized learning.
• Eq. (10) will represent the true fair update of the current model $x_t$ across these clients, using the entropy-based aggregation probabilities derived in our paper.

[1]Scaffold: Stochastic controlled averaging for federated learning[C]//ICML 2020.

[2]Local learning matters: Rethinking data heterogeneity in federated learning[C]//CVPR 2022.

Dear reviewer Tsda, we would like to thank you for your time spent reviewing our paper and for providing constructive comments. Please kindly find our responses to your raised questions below:

Q1. The paper would benefit from a more ****intuitive explanation of the connection between entropy and fairness.

Thank you for your suggestion.

Entropy is widely used to promote fairness in resource allocation [1] and data processing [2].

A motivation for its use in these scenarios is contained in the entropy concentration theorem [3], which posits that maximum entropy provides the least biased solution for determining prior probabilities.

However, the existing entropy concentration theorem cannot be directly applied to federated learning settings. In existing fairness applications, maximizing entropy without considering constraints will lead to a uniform distribution, where all users share equal resources. This conflicts with the natural heterogeneity in federated learning; aggregation with equal weights of all users cannot achieve the goal of fairness, i.e., equal performance across users. We address this challenge by introducing constraints to adjust weights, aligning aggregated performance with that of the ideal fair model. This constrained entropy approach focuses more on underperforming clients, assigning them higher weights and reducing performance unfairness.

[Toy example]

We present a toy example to demonstrate how entropy and fairness work. FedAvg uses uniform aggregation, which is equivalent to entropy without constraints.

In particular, consider two clients with loss function $f_1\left(x_t\right)=2(x-2)^2, f_2\left(x_t\right)=\frac{1}{2}(x+4)^2$ respectively.

Assuming $x_t=0$, w.l.o.g, we consider one single-step gradient decent with stepsize=1/4. Then $x_1^{t+1}=x_t-\lambda \nabla f_1\left(x_t\right)=2, x_2^{t+1}=x_t-\lambda \nabla f_2\left(x_t\right)=-1$.

Thus, the aggregation probabilities for FedAvg, q-FFL, and FedEBA will be:

($\frac{1}{2}, \frac{1}{2}$), ($\frac{4}{13},\frac{4}{13}$), ($\frac{1}{1+e^{9/2}}, \frac{e^{9/2}}{1+e^{9/2}}$).

Then the variance of $x_{t+1}$ will be:

$Var_{AVG} = 2*(2.81)^2, Var_{q-FFL}=2*(2.52)^2, Var_{EBA+}=2*(0.6)^2$

The corresponding variance rank is $Var_{EBA+}<Var_{q-FFL}<Var_{AVG}$.

In this case, the normalized performance's entropy, after maxing the constrained entropy of aggregation probability, exhibits a relationship akin to variance (greater entropy corresponds to improved fairness). $\operatorname{Entropy}\left(f\left(x_{E B A+}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{E B A+}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{E B A+}^{t+1}\right)} \log \left(\frac{f_j\left(x_{E B A+}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{E B A+}^{t+1}\right)}\right) \approx 0.996$, where $f_1\left(x_{E B A+}^{t+1}\right)=2 *(2.1)^2, f_2\left(x_{E B A+}^{t+1}\right)=\frac{1}{2} *(3.9)^2$. $\operatorname{Entropy}\left(f\left(x_{q-FFL}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{q-FFL}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{q-FFL}^{t+1}\right)} \log \left(\frac{f_j\left(x_{q-FFL}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{q-FFL}^{t+1}\right)}\right) \approx 0.942$, where $f_1\left(x_{q-FFL}^{t+1}\right)=2 *(2.4)^2, f_2\left(x_{q-FFL}^{t+1}\right)=\frac{1}{2} *(3.6)^2$. $\operatorname{Entropy}\left(f\left(x_{AVG}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{\text {avg}}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{\text {AVG}}^{t+1}\right)} \log \left(\frac{f_j\left(x_{\text {AVG}}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{\text {AVG}}^{t+1}\right)}\right) \approx 0.890$, where $f_1\left(x_{AVG}^{t+1}\right)=2 *(1.5)^2, f_2\left(x_{AVG}^{t+1}\right)=\frac{1}{2} *(4.5)^2$.

Therefore, $Entropy(f(x_{EBA+}^{t+1}))>Entropy(f(x_{q-FFL}^{t+1}))>Entropy(f(x_{AVG}^{t+1}))$ and $Var_{EBA+}<Var_{q-FFL}<Var_{AVG}$.

We have mentioned this in Appendix I.1 of the revised manuscript.

[1]Johansson M, Sternad M. Resource allocation under uncertainty using the maximum entropy principle[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4103-4117.

[2]Celis L E, Keswani V, Vishnoi N. Data preprocessing to mitigate bias: A maximum entropy based approach[C]//International conference on machine learning. PMLR, 2020: 1349-1359.

[3]Jaynes E T. On the rationale of maximum-entropy methods[J]. Proceedings of the IEEE, 1982, 70(9): 939-952.

Dear reviewer 591F, we would like to thank you for your time spent reviewing our paper and for providing constructive comments. Please kindly find our responses to your raised questions below:

Weaknesses:

W1. Lack of Novelty in Aggregation Strategy

See reply to Questions.

W2. Overemphasis on Entropy

See reply to Questions.

W3. Limited Innovation in Fairness-Performance Trade-off: Although the paper claims to balance fairness and performance, the approach primarily adjusts aggregation weights based on client loss. Many existing algorithms adjust client weights in some form, and the use of entropy as a fairness mechanism does not seem to introduce substantial improvements beyond what is already available in the literature.

• The approach consists of two main parts: aggregation and alignment updates.
• For aggregation alone, the benefits of using the proposed aggregation probability are twofold:
  • It generalizes many existing aggregation methods and has a clear theoretical foundation, as opposed to heuristic approaches that are simply proportional to loss, as seen in many works [1,5,6].
  • The improvement over existing aggregation-only methods is significant. Compared to methods like q-FFL and TERM, our entropy-based aggregation (FedEBA+ with α=0) demonstrates better performance in terms of both accuracy and fairness, as shown in Table 1 and Table 2 of the submission.

Questions:

Q1. Novelty of Exponential Normalization: The core aggregation strategy is based on an exponential normalization of client losses. Could the authors clarify how this approach fundamentally differs from existing techniques that also adjust aggregation weights based on client performance? How does the use of entropy provide a significant advantage over these existing methods?

Thank you for your suggestion.

We clarify the differences compared to existing aggregation methods by:

• The aggregation formulation is different. Our aggregation probability $p_i = e^{\frac{F_i(x)/\tau}{Z}}$ is proportional to the exponential term of loss with a controllable parameter $\tau$. Unlike heuristic fair approaches that assign weights proportional to client loss $p_i \propto F_i(x)$[1, 5,6], our method is derived from a well-defined constrained optimization problem.
• The goal is different. Existing entropy-based aggregation methods [3,4] and softmax-based reweighting approaches [5,6] have entirely different objectives from fair FL. These methods focus on improving model accuracy but lack the ability to enhance fairness.
• Novelty in the Entropy Model for FL: To extend entropy to FL fairness, we introduce a novel constrained entropy model, the first of its kind in the FL fairness community. This model incorporates a constraint that adjusts the distribution to prioritize underperforming clients, resulting in a weighted fair aggregation.

The advantages of our approach over existing methods lie in:

• The exponent form and control term $\tau$ benefit the fairness level and enhance existing fair aggregation methods. For our model, $p_i = e^{\frac{F_i(x)/\tau}{Z}}$, the exponent effectively addresses extreme loss (extreme unfairness), since the exponent grows faster with increasing loss. Additionally, the controllable term $\tau$ regulates the fairness level by determining the spread of weights assigned to each client. As Remark 4.2 shows, by choosing an appropriate expression for $\tau$, we can recover existing fair aggregation algorithms like FedAvg, AFL, and q-FFL [2].
• Empirically more effective in fairness than others. Compared with existing fair aggregation methods like q-FFL and TERM, our entropy aggregation (FedEBA+ with $\alpha=0$) shows better performance in both accuracy and fairness, as shown in Tables 1 and 2 of the submission.

[1]Mollanejad A, Navin A H, Ghanbari S. Fairness-aware loss history based federated learning heuristic algorithm[J]. Knowledge-Based Systems, 2024, 288: 111467.

[2]Li T, Sanjabi M, Beirami A, et al. Fair Resource Allocation in Federated Learning[C]//International Conference on Learning Representations.

[3] Huang, W., Shi, Z., Ye, M., Li, H. & Du, B. Self-Driven Entropy Aggregation for Byzantine-Robust Heterogeneous Federated Learning. ICML 2024

[4]Herath C, Liu X, Lambotharan S, et al. Enhancing Federated Learning Convergence with Dynamic Data Queue and Data Entropy-driven Participant Selection[J]. IEEE Internet of Things Journal, 2024.

[5]Zhao Z, Joshi G. A dynamic reweighting strategy for fair federated learning[C]//ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022: 8772-8776.

[6]Kanaparthy S, Padala M, Damle S, et al. Fair federated learning for heterogeneous data[C]//Proceedings of the 5th Joint International Conference on Data Science & Management of Data (9th ACM IKDD CODS and 27th COMAD). 2022: 298-299.

In this case, the normalized performance's entropy, after maxing the constrained entropy of aggregation probability, exhibits a relationship akin to variance (greater entropy corresponds to improved fairness). $\operatorname{Entropy}\left(f\left(x_{E B A+}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{E B A+}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{E B A+}^{t+1}\right)} \log \left(\frac{f_j\left(x_{E B A+}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{E B A+}^{t+1}\right)}\right) \approx 0.996$, where $f_1\left(x_{E B A+}^{t+1}\right)=2 *(2.1)^2, f_2\left(x_{E B A+}^{t+1}\right)=\frac{1}{2} *(3.9)^2$. $\operatorname{Entropy}\left(f\left(x_{q-FFL}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{q-FFL}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{q-FFL}^{t+1}\right)} \log \left(\frac{f_j\left(x_{q-FFL}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{q-FFL}^{t+1}\right)}\right) \approx 0.942$, where $f_1\left(x_{q-FFL}^{t+1}\right)=2 *(2.4)^2, f_2\left(x_{q-FFL}^{t+1}\right)=\frac{1}{2} *(3.6)^2$. $\operatorname{Entropy}\left(f\left(x_{AVG}^{t+1}\right)\right)=-\sum_{i=1}^2 \frac{f_i\left(x_{\text {avg}}^{t+1}\right)}{\sum_{j=1}^2 f_j\left(x_{\text {AVG}}^{t+1}\right)} \log \left(\frac{f_j\left(x_{\text {AVG}}^{t+1}\right)}{\sum_{i=j}^2 f_i\left(x_{\text {AVG}}^{t+1}\right)}\right) \approx 0.890$, where $f_1\left(x_{AVG}^{t+1}\right)=2 *(1.5)^2, f_2\left(x_{AVG}^{t+1}\right)=\frac{1}{2} *(4.5)^2$.

Therefore, $Entropy(f(x_{EBA+}^{t+1}))>Entropy(f(x_{q-FFL}^{t+1}))>Entropy(f(x_{AVG}^{t+1}))$ and $Var_{EBA+}<Var_{q-FFL}<Var_{AVG}$.

We have mentioned this in Appendix I.1 of the revised manuscript.

[1]Johansson M, Sternad M. Resource allocation under uncertainty using the maximum entropy principle[J]. IEEE Transactions on Information Theory, 2005, 51(12): 4103-4117.

[2]Celis L E, Keswani V, Vishnoi N. Data preprocessing to mitigate bias: A maximum entropy based approach[C]//International conference on machine learning. PMLR, 2020: 1349-1359.

[3]Jaynes E T. On the rationale of maximum-entropy methods[J]. Proceedings of the IEEE, 1982, 70(9): 939-952.

Q3-1. In the alignment to improve global accuracy why are the pi's computed using the loss of the local models? (Line 312). In my understanding, since we are fixing x , when solving the inner problem, the p  should be computed using the loss of the global model, i.e, the expression in Line 351?

We believe you are referring to Line 320, where $p_i$ is computed based on the loss of the model after local updates.

The difference between Line 320 and Line 351 lies in their objectives. In Line 320, the focus is on improving global accuracy, so the alignment update is calculated as the average of local updates. Here, $p_i$, representing client aggregation weights, is used to ensure that the aggregated model for each client closely aligns with the ideal fair gradient. Thus, it is computed using the loss of the local models.

In contrast, in Line 351, $p_i$ is employed in the alignment update to approximate the ideal fair gradient. Since the ideal local update corresponds to a one-epoch update, the associated weights should be computed using the loss of the global model.

To summarize:

• When $p_i$ is used in standard model update aggregation, it is computed based on the loss of the local model.
• When $p_i$ is used in the alignment term, it is computed based on the loss of the global model.

Q3-2. In the alignment to improve fairness why is the local optimization at clients changed (Eq. 11 and Line 11 in Algorithm 1)? In my understanding only global aggregation should change?

The aggregation and local alignment update (Eq.11) are both to improve fairness.

If only the global aggregation is modified, it corresponds to FedEBA without alignment update. Specifically, Eq. (11) is derived from Eq. (7), which provides the outer-loop solution for the model parameters. Additionally, the alignment process is executed locally to refine each epoch’s local update direction, ensuring it does not deviate significantly from the fair direction, as illustrated in Figure 2.

As a result, given the formulation of the model parameter updates (Eq. 7) and the alignment process performed during each local epoch, the local optimization process must be changed accordingly.

Dear reviewer acXK, thank you very much for taking the time to review our paper. We have carefully revised the writing and clarified the motivation in the paper based on your suggestions. Below, you can find our detailed responses to your questions:

Q1. It is a bit surprising to me that the expression for the aggregation probabilities in Eq. (4) does not depend on the desired $\tilde{f}(x)$ in Eq. (3). Is there an intuitive explanation for why this is the case?

Thank you for your comment.

In derivation of Eq. (3) $p_i=\frac{\left.\exp \left[F_i\left(x_i\right) / \tau\right)\right]}{\sum_{i=1}^N \exp \left[F_i\left(x_i\right) / \tau\right]}$, $\tau$ is related to $\tilde{f}(x)$ according to Eq. (24).

While$\tilde{f}(x)$ influences $\tau$, it is treated as a constant during the derivation and approximated later, making $p_i$ independent of $\tilde{f}(x)$ and the estimation of $\tilde{f}(x)$ is explicitly inflected in $\tau$.

In particular, by optimizing $L\left(p, \lambda_0, \lambda_1\right):=-\left[\sum_{i=1}^N p_i \log 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\left(x_i\right)\right)\right]$ over $p_i$, we get that $p_i=\frac{\left.\exp \left[\lambda_1 F_i\left(x_i\right)\right)\right]}{Z}$ (Eq. 22). Thus the max entropy can be expressed as $\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\left(x_i\right) =\lambda_0+1-\lambda_1 \mu .\end{aligned}$ (Eq. 23) and $-\frac{\partial H_{\max }}{\partial \mu}=: \frac{1}{\tau}$ (Eq. 24), where $\tilde{f}(x)=\mu$ , as stated below Eq. (8) of the submission.

As a result, the expression in Eq. (4) does not explicitly depend on the estimation $\tilde{f}(x)$ because it is treated as a constant during the derivation. Intuitively, fair aggregation should depend on each client’s performance, i.e., their loss, rather than the ideal estimation term.

We have stated the connection between Eq. (4) and $\tilde{f}(x)$ in the main paper.

Q.2 Authors are encouraged to provide an intuitive explanation for why maximizing constrained entropy can improve fairness. Right now, entropy-based aggregation just appears to be a black box to improve fairness

Thank you for your suggestion.

Entropy is widely used to promote fairness in resource allocation [1] and data processing [2].

A motivation for its use in these scenarios is contained in the entropy concentration theorem [3], which posits that maximum entropy provides the least biased solution for determining prior probabilities.

However, the existing entropy concentration theorem cannot be directly applied to federated learning settings. In existing fairness applications, maximizing entropy without considering constraints will lead to a uniform distribution, where all users share equal resources. This conflicts with the natural heterogeneity in federated learning; aggregation with equal weights of all users cannot achieve the goal of fairness, i.e., equal performance across users. We address this challenge by introducing constraints to adjust weights, aligning aggregated performance with that of the ideal fair model. This constrained entropy approach focuses more on underperforming clients, assigning them higher weights and reducing performance unfairness.

[Toy example]

We present a toy example to demonstrate how entropy and fairness work. FedAvg uses uniform aggregation, which is equivalent to entropy without constraints.

In particular, consider two clients with loss function $f_1\left(x_t\right)=2(x-2)^2, f_2\left(x_t\right)=\frac{1}{2}(x+4)^2$ respectively.

Assuming $x_t=0$, w.l.o.g, we consider one single-step gradient decent with stepsize=1/4. Then $x_1^{t+1}=x_t-\lambda \nabla f_1\left(x_t\right)=2, x_2^{t+1}=x_t-\lambda \nabla f_2\left(x_t\right)=-1$.

Thus, the aggregation probabilities for FedAvg, q-FFL, and FedEBA will be:

($\frac{1}{2}, \frac{1}{2}$), ($\frac{4}{13},\frac{4}{13}$), ($\frac{1}{1+e^{9/2}}, \frac{e^{9/2}}{1+e^{9/2}}$).

Then the variance of $x_{t+1}$ will be:

$Var_{AVG} = 2*(2.81)^2, Var_{q-FFL}=2*(2.52)^2, Var_{EBA+}=2*(0.6)^2$

The corresponding variance rank is $Var_{EBA+}<Var_{q-FFL}<Var_{AVG}$.

The experimental setups are: FedMGDA+ with $\eta=1.0 , \epsilon=0.1$; PropFair with $M=5.0, thres=0.2$; TERM with $t=0.1$. The other setups, like learning rate and batch size, are the same as the submission.

Q9-1. Theoretically, we don't see any effect of θ in Theorem 1, which is a bit surprising to me.

Thank you for your insightful suggestion.

In our Theorem 1, $\theta$ shows no theoretical impact on convergence since the gradient of ideal loss is uniformly bounded regardless of the choice of $\theta$ .

In particular, Assumption 4 bounds the gradient of the ideal loss and the practical aggregated gradient. It applies to both the ideal fair loss and the ideal global loss, allowing their gradients to be uniformly bounded and analyzed. While $\theta$ determines whether to estimate the ideal fair or global loss, both are uniformly bounded in the derivation, which is why $\theta$ doesn’t explicitly appear in the convergence rate.

Q9-2. In practice, I would also suggest moving Table 7 to the main text and discuss the trade-off in setting θ in more detail.

For the setting of $\theta$, it balances the communication cost and performance improvement.

• A smaller $\theta$ increases communication costs. This happens because a smaller $\theta$ requires more frequent fair alignment updates, needing more communication rounds. However, it also leads to greater performance improvements.
• According to Table 7, if the communication cost is affordable, $\theta = 0$ should be chosen for optimal performance. Otherwise, we recommend using the Prac-FedEBA+ algorithm with the default $\theta = 15^\circ$, which requires no additional communication cost but with better performance than SOTA baselines.

We have moved Table 7 into the main text and discussed it in detail according to the reviewer’s suggestion.

Q4. I don't follow how in Prac-FedEPA+ clients need to only communicate once. If we follow Algorithm 3 then it appears that communication can happen twice within a round: first in Line 6-8 and then again in Lines 18-22. I found this to be very confusing and authors should clarify what is the communication cost in their experiments.

Apologies for the unclear description of Algorithm 3. We would like to clarify the following:

• In Algorithm 3, only Line 5 (where the server broadcasts to clients) and Line 12 (where clients upload to the server) involve communication. Therefore, the communication occurs only once per round.
• For Lines 13-25, including Lines 18-22, all computations are performed on the server, as it has already received all the necessary information. Specifically, for Lines 18-22, the gradient information has already been obtained, and the aggregation can be directly performed on the server side using Eq. (8).

Thanks for pointing out this issue. The server-side gradient aggregation does not require additional communication. We have carefully revised the descriptions in the revised manuscript.

Q5. A is not defined in Theorem 5.1. Similarly w is not defined, although from context it appears to be the prior aggregation weights of client objectives.

Thank you for your suggestion. $A\geq0$ is a constant defined in Assumption 3, and $\mathbb{w}$ is the prior aggregation defined in Lemma H.1.

Due to the page limit, we moved the Assumptions and Lemmas to the Appendix in our original submission. We have clarified these details in the revised manuscript.

Q6. It seems a little strange to see discussion on the lower bound of an upper bound in Remark 5.2. Authors should just state the worst possible convergence rate of FedEBA+ by considering that $\sum_{i=1}^m w_i^2\leq 1$.

Thank you for your suggestion. In the original submission, we provide the lower bound to help understand the performance of FedEBA+ ($\alpha=0$) when $w_i = \frac{1}{m}$, i.e., uniform aggregation. In this case, the bound is the same as FedAvg.

We appreciate your suggestion and have stated the case when $\sum_{i=1}^m w_i^2\leq 1$ in Remark 5.2.

Q7-1. In Remark 5.3. it appears that to show convergence of α≠0 we need to assume k<<m. Is this correct? If so, authors should clearly mention this and explain why this is the case.

Yes, it is correct.

In this paper, $K$ represents the local epoch times (in each communication round) and $m$ represents the client numbers, usually client numbers is larger than local epoch in the cross-device FL. For example, in our paper,$m=100, K=10$.

We have revised the manuscript and mention this in our paper.

Q7-2. Also I don't follow the argument that the proposed alignment results in a faster convergence rate than FedAvg since both seem to be achieving O(1/mKT) rate.

The rate order of the proposed alignment remains the same as $\frac{1}{\sqrt{mKT}}$, and we state a faster convergence rate due to the constant term improvement.

As for showing the improvement of alignment compared with FedAvg by setting $w_i=\frac{1}{m}$, when using the alignment update further ($\alpha \neq 0$), term $\mathcal{O}(\frac{\sigma_L^2}{\sqrt{mKT}})$ changes into $\mathcal{O}(\frac{(1-\alpha)^2 \sigma_L^2+\alpha^2 \sqrt{K / m} \rho^2}{\sqrt{m K T}})$, since $0<\alpha<1,\frac{K}{m}<1,\rho \sim \sigma_L$, the constant term becomes smaller in the rate order, where a larger $\alpha$ leads to a faster convergence rate by degrading the influence of $\frac{1}{\sqrt{mKT}}$.

Q8. Why is FedMGDA+, PropFair and TERM incompatible in Table 2?

Thank you for your suggestion. We have provided the results of these three algorithms after carefully fine-tuning their hyperparameters and running them multiple times. These algorithms are not stable and were excluded from the original submission because they performed poorly with commonly used random seeds, such as 12345, that are used for other baselines in the paper.

In the table below, we report the best 3 seeds out of 10 random trials, which demonstrates FedEBA+'s advantage over the other algorithms.

Thank you for the rebuttal. Some points regarding the theory and algorithm are clearer now. However, I am still unsure about some aspects which I discuss below.

1. Expression for aggregation probabilities: This is still unclear to me. From Eq. (21) we have a relation between $\lambda_0$ and $\lambda_1$, i.e. $\lambda_0 = \log \sum_{i=1}^N \exp(\lambda_1 F_i(x_i)) - 1$. We can substitute this expression for $\lambda_0$ in the expression for entropy H_\max = \lambda_0 + 1 - \lambda_1\sum_{i=1}^N p_iF_i(x_i) and find the value of $\lambda_1$ which maximizes entropy. Therefore why do we need to introduce the additional hyperparameter $\tau$ ?

2. Changes made to the algorithm for ideal fair gradient vs ideal global gradient: I would suggest to the authors to explicitly write the objective that they are solving in each case and then derive the gradient and explain any approximations they are making. Right now the authors are just writing down the direct gradient (Eq. 8 and Eq. 10) for the two cases which is making it hard to understand what exactly is the objective they are trying to solve in each case.

3. Instability of FedMGDA+, PropFair and TERM: Have other works also observed a similar phenomenon? In any case it would be good to mention how the hyperparameters of these algorithms were tuned and include plots where the algorithms diverged.

4. Why do we need $K \ll m$? Although it may be satisfied in practice, it is still an unnatural condition which other FL convergence works don't need.

5. Effect of $\theta$: I'm not sure what the authors mean by the gradient of ideal loss is uniformly bounded. Could you explain this in more detail or point me where in the proof this property is being used? Intuitively it seems like if you set $\theta$ to be too small or too large then you will just be doing ideal fair aggregation or ideal global aggregation always, which should have some impact on the convergence.

Also please highlight any new edits to the paper in a different color so it becomes easier to see what exactly has changed.

Thank you for your response. Some parts are still unclear as I discuss below:

1. Expression for aggregation probabilities

The authors write

To find the value of that maximizes the entropy, we set $\lambda_1 = - \frac{\partial H_{\max}}{\partial \mu}$ for the maximum entropy.

My question is why is this step necessary? Since $\sum_{i}p_iF_i(x_i) = \mu$ we know that

$\frac{\sum_{i=1}^N \exp(\lambda_1 F_i(x_i))F_i(x_i)}{\sum_{i=1}^N \exp(\lambda_1 F_i(x_i))} = \mu.$

So we can solve the above equation to find $\lambda_1$ in terms of $\mu$ and $\\{F_i(x_i)\\}_{i=1}^N$ . Why are we not doing this?

2 . Changes made to the algorithm for ideal fair gradient vs ideal global gradient:

Thank you for the clarification, but my question still remains.

In the global model alignment case, clients are performing the following optimization: $x_{t,k+1}^i = x_{t,k}^i - \eta_l \nabla F_i(x_{t,k}^i, \xi_i)$ and in the fair alignment case, clients are performing: $x_{t,k+1}^{i} = x_{t,k}^{i} - \eta_l h_{t,k}^{i}$ where $h_{t,k}^{i} = (1-\alpha) \nabla F_i(x_{t,k}^i, \xi_i) + \alpha \tilde{g}^{b,t}$

My question is why is the local optimization changing in the fair alignment case?

The local optimization that occurs for fair alignment (i.e, $h_{t,k}^{i} = (1-\alpha) \nabla F_i(x_{t,k}^i, \xi_i) + \alpha \tilde{g}^{b,t}$) looks similar to the idea of using a control variate that has appeared in several works starting from SCAFFOLD [a] (see Equation 10 in Algorithm 1) to deal with the problem of client-drift. But in the context of this work, I don't see the theoretical motivation for using such a control-variate based idea.

In fact, the Prac-FedEBA+ algorithm where local optimization remains the same for both fair and global alignment is the one which I expect to see and is the one which is more intuitive to me.

3. $K \ll m$ condition

The authors write

The convergence rate is $O(1/\sqrt{mKT})$ no matter the relation between $K$ and $m$ because the term $\sqrt{K/m}$ is just a constant term in the order

Why is it a constant order (unless authors assume so)? Other FL works for instance SCAFFOLD, do not place any restriction on $K$ so $K$ could be any polynomial of $m$ for instance, $K = \mathcal{O}(m^3)$. In this case $\sqrt{K/m} = \mathcal{O}(m)$ which is not constant order.

References

[a] Karimireddy, Sai Praneeth, et al. "Scaffold: Stochastic controlled averaging for on-device federated learning." arXiv preprint arXiv:1910.06378 2.6 (2019).