H-nobs: Achieving Certified Fairness and Robustness in Distributed Learning on Heterogeneous Datasets
Authors: Guanqiang Zhou
Ping Xu
Yue Wang
Zhi Tian
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed learning
federated learning
fairness
robustness
Byzantine attack
norm-based screening
q-FFL
optimization
convergence analysis
TL;DR: This paper studies several unexplored key questions on fair and robust distributed learning.

Abstract: Fairness and robustness are two important goals in the design of modern distributed learning systems. Despite a few prior works attempting to achieve both fairness and robustness, some key aspects of this direction remain underexplored. In this paper, we try to answer three largely unnoticed and unaddressed questions that are of paramount significance to this topic: (i) What makes jointly satisfying fairness and robustness difficult? (ii) Is it possible to establish theoretical guarantee for the dual property of fairness and robustness? (iii) How much does fairness have to sacrifice at the expense of robustness being incorporated into the system? To address these questions, we first identify data heterogeneity as the key difficulty of combining fairness and robustness. Accordingly, we propose a fair and robust framework called H-nobs which can offer certified fairness and robustness through the adoption of two key components, a fairness-promoting objective function and a simple robust aggregation scheme called norm-based screening (NBS). We explain in detail why NBS is the suitable scheme in our algorithm in contrast to other robust aggregation measures. In addition, we derive three convergence theorems for H-nobs in cases of the learning model being nonconvex, convex, and strongly convex respectively, which provide theoretical guarantees for both fairness and robustness. Further, we empirically investigate the influence of the robust mechanism (NBS) on the fairness performance of H-nobs, the very first attempt of such exploration.

H-nobs: Achieving Certified Fairness and Robustness in Distributed Learning on Heterogeneous Datasets
Guanqiang Zhou George Mason University gzhou48gmu. edu
Ping Xu
Yue Wang Georgia State University
University of Texas Rio Grande Valley ping www.trgg..ee.. edu
yvang1820gsu. edu
Zhi Tian
George Mason University ztian Ggmu edu
Abstract
Fairness and robustness are important goals in the design of modern dis- tributed learning systems. Despite few prior works attempting to achieve both fairness and robustness, some key aspects of this direction remain underexplored. In this paper, we try to answer three largely unnoticed and unaddressed questions that are of paramount significance to this topic: (i) What makes jointly satisfying fairness and robustness difficult? (ii) Is it possible to establish theoretical guaran- tee for the dual property of fairness and robustness? (iii) How much does fairness have to sacrifice at the expense of robustness being incorporated into the system? To address these questions, we first identify data heterogeneity as the key diffi- culty of combining fairness and robustness. Accordingly, we propose a fair and robust framework called H-nobs which can offer certified fairness and robustness through the adoption of two key components, fairness promoting objective func- tion and a simple robust aggregation scheme called norm- norm-based screening (NBS). We explain in detail why NBS is the suitable scheme in our algorithm in contrast addition, we derive three convergence
to other robust aggregation measures. theorems for H-nobs cases of the learning model being nonconvex, convex, and strongly convex, respectively, which provide theoretical guarantees for both fair- ness and robustness. Further, empirically investigate the influence of the robust mechanism (NBS) on the fairness performance of H-nobs, the very first attempt of such exploration.
Introduction
Distributed learning has been widely applied solve large-scale machine learning (ML) problems, where a number of computing nodes (users) collectively carry out the task of training a model under the coordination of central node (server). Federated learning is typical example of distributed learning where each device collects its own local data and keeps them private [1]. In this paper we distributed learning and federated learning interchangeably.
Aside from the basic expectation of high model accuracy, it is increasingly emphasized in the lat- est ML research design distributed learning algorithms that can jointly satisfy several pragmatic constraints such as fairness and robustness [2]. Here we consider the most common definitions where fairness specifically refers to egalitarian faimeess and robustness refers Byzantine robust- ness, which respectively stipulate that the trained model exhibits somewhat uniform performances on the local users (see Section 2.1), and that the system is resilient Byzantine attacks where portion of users defect or malfunction (see Section 2.2). In this paper, we strive for simultaneously
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

attaining faimess and robustness. Although a few prior efforts have been made towards fair and robust distributed learning [3, 4, 5]. this direction largely underexplored, and some key issues have not been addressed yet. In this paper, we seek to answer three questions that are of paramount importance to the understanding of this topie.
The first question is "What makes jointly satisfying fairness and robustness difficult?" According to the recent literature, (un)fairness issues normally arise in the non-iid settings where the training data residing on local users are heterogeneous [6]. However, for a system to be Byzantine-robust a typical underlying assumption is that the local data are homogeneous//id [7, 8, 9, 10, 11J. Such conflict would invalidate most of the existing vyzantine-robus methodologies developed under the iid assumptions. Therefore, to meaningfully achieve fairness and robustness at the same time, one has to address data heterogeneity, which entails both theoretical and empirical challenges illustrated as follows.
The second question is "Is it possible to establish theoretical guarantee for the dual property fair- ness and robustness?" According the literature, providing convergence guarantees for Byzantine- robust methods (alone) is challenging enough [12]. This is because these methods not only rely on the iid assumption, but also require strong assumptions on the distribution of local gradients, such as sub-exponential [9] or sub-Gaussian [10] (see Section 4.3 for more details). These distributional assumptions usually fall short of proper justifications, and they become even harder to justify under the modified objectives with fairness constraints. Due to these two major obstacles, there has not yet been any work that manages to provide theoretical guarantees for both fairness and robustness.
The third question is "How much does fairness have to sacrifice at the cost of robustness? ?" To dis- play the inherent conflicts between these two goals, we consider the principles achieve either goal separately. On one hand, fairness is typically enforced by up-weighting the local objective function of the worst-performing users, which would make their local gradients also heavily-weighted. On the other hand, robustness is typically enforced by the server discarding partial gradients that look suspicious. Since the server cannot decide whether the suspicious gradients (by having large norms or prominent entries) are sent by the Byzantine users or generated from the up- weighted objectives, the latter can be easily filtered out by the deployed robust mechanism, which would inevitably im- pair the fairness performance. Although this issue was first recognized by a prior work [4], such internal conflicts have not been studied, either theoretically or empirically. Consequently, there are no reported results or understanding on this matter.
Our contributions. In this paper, we propose fair and robust framework called H-nobs, which contains two key components: a faimess-promoting objective function (the H part) and a simple robust aggregation scheme called norm-based screening/NBS (the nobs part). On one hand, in our algorithm, the certified fairness comes from the Bairness-promotinn objective function, which can be directly adopted from existing works with theoretical fairness guarantees (see Section 3.2 for a couple of representative examples). On the other hand, we show that the deployed NBS is able to gracefully handle Byzantine attacks and theoretically guarantee the convergence of our algorithm without requiring the rid assumption that is ubiquitous for convergence analysis. Accordingly, we de- rive three convergence theorems for H-nobs in cases of the learning model being nonconvex, convex, and strongly convex, respectively. In addition, we explain in great detail why NBS is distinctively suitable for our framework, and how it may not be the case for other robust aggregation measures. We achieve this by illustrating three notable theoretical advantages of NBS over its counterparts (see Section 4.3). To address the conflicts between fairness and robustness, we empirically investigate the influence of several robust aggregation schemes, including NBS and other widely-known bench- marks, on the fairness performance (see Section 5). Our results show that although the screening of some chirness-enhaneee
gradients is inevitable, the overall performance of H-nobs is satisfying. To the best of our knowledge, our work is the first that touches on all of the aforementioned aspects in the pursuit of fair and robust distributed learning.
The major contributions of this work can be summarized as follows:
We recognize the major challenges in obtaining joint fairness and robustness in distributed learning by identifying three important yet largely overlooked questions. In this work, we have addressed these questions to varying degrees.
We propose H-nobs, the first algorithm that takes the (obvious but challenging) route of incorporating robust aggregation into existing fair objectives to achieve fair and robust distributed learning.
2

---

We achieve certified fairness and robustness for H-nobs even under the challenging pon-iid scenarios, by establishing theoretical convergence guarantees with multiple levels of as- sumptions on the model convexity. Also, we clearly identify the major technical challenges that may hinder this goal, and illustrate how those challenges can overcome by NBS through its theoretical robust property.
We take the initiative to investigate the empirical conflicts between faimess and robust- ness under a specific metric and objective fairness, and demonstrate the robustness and fairness benefits of H-nobs.
2 Related work
2.1 Fairness in federated learning
Differing from the common notion fairness with respect to certain protected attributes (such as race and gender [13]). fairness in federated learning is typically defined over the model accuracies of local devices [14, 15], including two major faimess metrics, i.e., collaborative fairness [3] and egalitarian fairness [16]. These two metrics serve different purposes and suit for the corresponding scenarios. In particular, collaborative faimess enforces each user to receive a personalized model after each iteration according its contribution the training [3], which runs counter our work assuming a single shared model for all users. Therefore, in this paper we only consider egalitarian fairness, which aims to achieve not only satisfactory overall model accuracy, but also somewhat uniform local performances for all participating users [16].
To enforce faimess, one common approach is to replace the empirical training loss with modified objective function that puts a higher emphasis on the worst- porss-performin users. For example, in an earlier work, [17] proposes Agnostic Federated Learning (AFL), minimax optimization scheme to minimize the training loss of the worst-off client among all users. However, AFL is reported to perform well only on very small networks consisting of a handful of devices, and its generalization guarantees may not be applicable in a large-scale setting [ [14]. To improve upon AFI., [16] proposes q-Fair Federated Learning (g-FFL.), fairness- prreessin objective, which enjoys better scalability and more favorable accuracy/fairees tradeoffs than AFL. The exact formulation of q-FFL is given in Section 3.2. In Section we adopt egalitarian fairness the fairness metric and q-FFL as the objective function to empirically evaluate the effectiveness of our framework.
2.2 Byzantine-robust techniques
Byzantine attack/failure refers the issue where a small portion of failed nodes may send distorted or even adversarial messages to the server during training [18]. To cope with Byzantine attacks, there are generally two distinet approaches. The first approach assigns each user redundant data, and relies on this redundancy to eliminate the effects of erroneous messages [19, 12]. This approach may not be applicable to federated learning where data cannot be replicated and reassigned for user privacy. The second approach is based on certain robust aggregation mechanisms at the server's 's end, such as Krum [7], geometric median [8], coordinate- wise median [9), iterative filtering [10], etc. Due to its wide variety of aggregation rules and applicability to federated learning, robust aggregation is commonly viewed as the mainstream approach for mitigating Byzantine attacks.
Although it is an intuitive and seemingly straightforward idea to incorporate robust aggregation into the prrmess-prommting objectives for one achieve both fairness and robustness, we observe that few works take this route due to the two stringent assumptions mentioned in Introduction. To ad- dress these technical difficulties, we resort to based screening (NBS), low-profile screening scheme among the robust aggregation cohorts. Although NBS has previously been implemented in the Byzantine- Prrannine-proneeeee prone settings [11, 20), few realize its effectiveness in the challenging non-iid envi- ronments and its handiness for convergence analysis without necessitating the stringent assumptions. In Section 4, we demonstrate that NBS enjoys a desirable property which allows it to guarantee con- vergence under much milder assumptions.
3

---

3 Proposed framework
3.1 Basic setting
Data division. We consider typical distributed learning setup with one server and m users, each holding n data points with a total of mn = N training samples. Note that we do not assume that the local data are iid, despite the same sample size for each user. Also, uneven data allocation cases with varying local sample sizes can easily fit into our framework with minor adjustments.
Byzantine attack. We assume that a percentage a of local users are Byzantine and the remaining 1 a normal/honest. The sets of Byzantine users and honest users denoted as B and M respectively, with [B] = arn and [M] = (1 a.m. During each training iteration, the server would ask all users conduct certain computational task based on their respective local data and report the results back to the server. While honest users would follow the given instructions faithfully, Byzantine users need not to adhere the protocol and can send arbitrary messages to the server.
3.2 Proposed algorithm
On the macro level, our algorithm is variant of distributed gradient descent, characterized by two distinctive elements, i.e., fairness- aware objective and norm-based screening.
Fairness-aware objective. Let x(0;z,) be the point-wise training loss, we denote the local train- 1)ann
ing loss on node: as (.) = 1, E -)-((-1)=+1 f0; and the global training loss as F(0) = 1 (0) + Fm (0)] Since minimizing F(0) can produce unfair models, we instead adopt m
fairness-awand objective function (0) from existing literature which has a decomposable form Hm (0)], with (0) being the fairness-oriented version of F:(0) that
H()) 1 Hi (0)
solely relies on the local data of user i. few such examples include:
(+) = +. - 1n+ (f; pl? proposed by [6] where y is hyper- prper-paramete..
H.(0) (F()))t)) (i.e., FFLL proposed by [16] where q a hyper-paramette
Note that each specific (0) may aim to address different notion of faimess, with the former example seeking to mitigate representation disparity between majority and minority groups and the latter promoting egalitarian fairness. We also want point out that our work applies to a broad range of fairnsss-rooottin objectives that are decomposable, thus not limited to the given two examples.
Norm- screening (NBS). After the local gradients are computed by honest users (w.r.t. H, (0)) and sent to the server (while Byzantine users craft disruptive gradients denoted as *), we propose to use NBS to aggregate all local gradients before applying its output to update the model. As robust aggregation measure, the idea NBS is fairly simple: leave out the gradients with large norms and take the average of the remaining gradients as output. We formally define NBS as a function "Norm_ "Norm_Screen" as detailed in Algorithm
Algorithm 1 Norm-Based Screening
Input: 91, .1..... Jm (m local gradients), screening percentage /
Output: G=
(g),........ 9m) .0m)
1: generate new set of indices (1), (m), such that [|ا .... < (1
2: define an index set U {(1),..., ((1 3)m)}, which specifies the unscreened gradients
3: calculate the output by averaging the unscreened gradients G І. Σieu 9i
Despite its simplicity, NBS can gracefully handle Byzantine users, because any faulty gradient either is filtered out with a large norm, or can only shift the output to bounded degree. In this way. if some Byzantine gradients bypass NBS, their influence on the output can offset or mitigated if they are outnumbered by honest gradients that also remain unscreened. In Section 4, this property of NBS is formally stated as an inequality, which will serve as the bedrock of our convergence proofs later on. Combining the above two elements, we summarize the proposed algorithm in Algorithm 2.

---

Algorithm 2 H-nobs: Fair & Byzantine-Robus, Distributed Gradient Descent
Input: screening percentage 3 (2 o), learning rate 7), model initialization do. total iteration T
Output: completed model 0r
1: for = 0.1....... ,....,
do
2: Server: send 0, all users
3: ior 1, 2,...... ... do
4: User receive model 0g from the server
5: calculate (0,) according to the chosen form of (0,))
6: generate (=(O,) = (H,( i
iEB
7: send g:())) to the server
8: end for
9: Server: collect 91 (0.), . Im (0.) from the users
10: compute the aggregated gradient G(O,) Norm_Screen (0:))
11: update model 8.41 = P, 77 G(
12: end for
Convergence analysis
In this section, we begin by establishing a key theoretical property of NBS, and then develop three main convergence theorems, and conclude with a discussion that concretely states the distinctive advantages of NBS over other robust aggregation methods.
4.1 Preliminaries
Previously explain how NBS properly upper-bound the influence of Byzantine in intuitive way. Here we theoretically quantify this bound in Lemma 1, whose proof is deferred to Appendix A.
Lemma 1, Suppose that a percentage of S 3 among m local gradients g1.... 9m are Byzantine, whose indices compose B (IB) om), and the index of honest gradients denoted as M. and 3 2 a, the following inequality holds:
With G Norm g
2a
|G - VH S
max |H
1apll1vee -VHI
(1)
I-3 B
SEM
where VH [H + Hm with H, being the honest gradient of user i.
The inequality (1) critical the convergence analysis. In Algorithm 2 the model is refined using G, which is the sum of two terms V and G VH, with the former being the true gradient (noise- free) and the latter being noise
that take any direction. To prove convergence, must upper-bound the norm of G H as (1) does.
To enable further analysis, adopt Assumption I to bound the second term in the RHS of (1). Assumption 1. For any specific Or, it always holds that
(H.
1 m VV Sa.
max
IStsm
Assumption obviously stands due to the simple fact that the distance between any single vector and the vector mean is always upper-bounded.
Moreover, make Assumption 2 to ensure that the gradient ( exists.
Assumption 2. The fairess--wware objective H (0) is H-mooothh
4.2 Main theorems
Nonconvex losses. We first consider the most general case of the objective function H()) being nonconvex in For this case, we derive Theorem that guarantees convergence our algorithm to stationary point of H0).. The proof of Theorem 1 is deferred to Appendix B.

---

Theorem 1. Suppose that Assumptions 1-2 hold and a < Taking 3,, Algorithm 2 satisfies
"La'
2L.
(1 11+1/rjo²
T
VH(()) (1-(1+)) ((())) H[00]] + 1 -1
(1 r)
(3)
where 0t is the global minimizer of (0), C. = 3. and r should satisfy 0 < r <
1-f 2c
Convex losses. Now we consider the case where the loss function convex as in Assumption 3. Additionally, make Assumption which suggests that all the intermediate iterations would not be infinitely worse than the initialization lg. We derive Theorem that grants our algorithm convergence guarantee in the convex regime. The proof of Theorem 2 is deferred to Appendix C. Assumption 3. H (0) convex.
Assumption 4. There exists a fixed Io such that 1|0, 184-6% 1 S k|160 8- holds 0, O......, ......TTIII..... T-11
Theorem 2. Suppose that Assumptions 1-4 hold and a < 3. Taking LH Algorithm 2 satisfies
4LH D2
2(1+ Do + (1 (1+1/r)o (1 r)
H(0r)-H(00) & max
(4)
( (1 + C))
2L
2nx where = k-100 - 11, C. = I-3 and 0 <r<<<
L 2a
1, which are the same as in Theorem
Strongly convex losses. Finally, we assume strong convexity on the objective function as in As- sumption 5, in which case we derive Theorem 3 that guarantees convergence of our algorithm to the optimal model 0" The proof of Theorem 3 is deferred Appendix D)
Assumption 5. (0) is λσ strongly convex.
Theorem 3. Suppose that Assumptions 1-2 and 5 hold, and a < 1+26n/AH <
+/4 Taking
=
An Algorithm 2 satisfies (with Ca
-
1[0 -011 (2LHCa + LH λy 1100-0 0- NH L.n.a
(5)
LA + AH
Observations. According to Theorems 1-3, Algorithm is capable of achieving degree of con- vergence under varying assumptions regarding the model's convexity. Mcanwhile, we can clearly identify the effects of Byzantine percentage a: larger a (i.e., larger C.) not only decreases convergence speed, but also increases convergence error. In contrast, the a in (2) only affects the convergence error and has impact on the convergence rate.
4.3 Discussion
The tightness of (1) in Lemma 1. Since all three convergence theorems are derived based upon Lemma 1, it is important examine the tightness of (1). In practice, one almost always find a way to upper-bound ||G VH]. normally through some mathematical tricks and engineering approximations. However, convergence guarantees based upon loose bounds may be less effective or even risk losing their meaningfulnesss altogether. In this regard, we use a one-dimensional toy problem to demonstrate the tightmess of (1).
Given H1 = 4, VH2 = 5, VH2 = 6, and V 5. Now suppose that one of the three users Byzantine, say user 2, who can send the server an arbitrary value d2 instead of the honest gradient VH2 = 5. To implement NBS, we impose that = = - We can verify that (1) always holds, with the RHS equal to 6 and the LHS never reaching 6 no matter what value 92 takes. However, the LHS can infinitely approach if g2 is selected judiciously. For example, for the set gradients Ø1 = 4, 92 5.98, 93 6, the LHS is equal to 5.99. In this case, the Byzantine gradient ø2 carefully chosen such that able to bypass the screening, and meanwhile exerts maximum adversarial perturbation is Byzantine. This example shows that (1) precisely measures the worst-case deviation by Byzantine users and that it cannot be further tightened.
the output. Readers verify that (1) also holds when user user 3
The advantages of NBS over its counterparts. Aside from NBS, most of the other robust ag- gregation measures are meuuss-mean-bassee [7, 8, 9, 10), with the goal of computing a robust mean

---

gradient for every single iteration. Given the neat convergence guarantees resulted from NBS, a natural question arises: "Can any of those robust-mean-ber based methods lead to similar convergence results?" It turns out that the answer to this question might be negative, due to three major theoret- ical advantages of NBS over its counterparts, which make the latter not only require over-stringent assumptions but also produce less informative bounds.
First, unlike robust-mean-basee based methods, NBS does not require the assumption that local data are iid. As explained in Section 4.1, bounding the noise term || V H || is crucial for convergence, where G represents the output of robust aggregation, whether it is NBS or one of its counterparts. For the latter, the iid assumption is indispensable since it ensures that the honest gradients are iid samples of the true global gradient V.. Without this assumption, ||G VH| cannot be upper-bounde bounded theoretically.
Second, unlike its counterparts, NBS does not require local gradients follow certain distribution, which often lacks proper justification in practice. For oobust-mean-basedd methods, this distributional assumption determines the level which honest local gradients concentrated. Without this assumption, || - VH || also cannot be upper-bounded theoretically. In contrast, in order to bound ||G V |, NBS only requires Assumption 1, which always holds explained previously and does not have the justification issue.
Third (and most importantly). NBS's bound ||G VH || is tighter. therefore more useful, than that of its counterparts. To reach convergence, the noise term ||G - VH| has to be bounded for every iteration, suggesting that the distributional assumption needs to be made repeatedly for robust- mean-based methods. Although the distribution of honest gradients is supposed to become more and more concentrated as the model makes steady progress towards the optimum, such dynamic distributional change is unknown to us and there is no way to accurately incorporate this piece of information into the distributional assumption at each iteration. Therefore, one has little choice but to compromise by imposing the same distributional assumption on local gradients for all iterations, which inevitably leads to a loose bound on ||G II. For example, the authors of [9] assume that the partial derivatives of the objective follow the same sub-exponentic distribution for all iterations. As a result, they can only bound |G VHI as a constant A irrespective of the iteration index (see Theorem 8 and Theorem 11 therein). Clearly. the inequality ||G | < A is not tight since it completely ignores the ever-concentrating effect of honest gradients as training proceeds. In contrast, NBS leads to (1), i.e., |[ V S C.I|VHII + a, which accurately captures the supposed shrinkage of |G - H as | H|l decreases.
To summarize, NBS enjoys the above three distinctive advantages over its pobust-mean-bee -bsed coun- terparts in theoretically upper-bounding ||G VlIll, making it suitable for to derive meaningful convergence guarantees.
The effects of non-iid data. Although our convergence analysis applies to both iid and non-iid settings, the heterogeneity of local data does have an impact on the convergence results. This is reflected in (2) where the distance between any local gradient and the true global gradient is upper- bounded by a (maxigigm HV V S o), which is determined by data heterogeneity. In the most homogeneous case where each user has the same data, is equal to O. As data heterogeneity increases, a should also increase accordingly. Through the adoption of such a universal upper bound o, we are able to derive meaningful convergence guarantees without the normally required iid assumption. This analytical approach, i.e., making assumptions in the spirit of (2) and imposing a universal upper bound to eliminate local gradients' differences, might serve as a pathway for future works to bypass the non-iid issue theoretically in the convergence analysis.
guavergeneeguuranttee
Simulation
5.1 Experimental setup
Dataset and allocation. In this section, we empirically evaluate the performance of our algorithm for a classification task using the logistic regression model on the Spambase dataset [21]. We assign of the 4601 total samples for training and the other 3 for testing. We evenly split the training data among = 20 nodes, with 8 of them exclusively holding spams (labelled as 1) and the remaining 12 exclusively holding non-spams (labelled as 0). Each node has the same number of data points = 153. Although in theory there are numerous ways to create non-iid setting, splitting data
7

---

according to their labels seems to be the common practice, In the Byzantine setting, we pick am = 4 nodes as Byzantine from each group). Upon the completion of training, we use the percentage of correct classifications on the test set as the performance metric of model accuracy.
Objective and fairness metric. To achieve fairness, adopt q-FFL. [16] where the local objective takes the form of (0) पे. [F with (, = -)j=(--1n= f(O; 2() and f(é; 22) being the cross-entropy loss that is common for classification tasks. As explained in Section 3.2, g-FFL promotes egalitarian fairness. We follow [16] to use the variance of the local classification accuracy as the metric of fairness (only the accuracies of honest users are counted for a > 0). Note that our framework is not limited to the q-FFL objective and it readily suits for other ctimess-orientee objectives as long as they can be decomposed in the form of H 1/ HH +.... Hm]
Byzantine models and robust benchmarks. To generate Byzantine gradients, experiment with four different strategies, i.e., sign-flipping attack [22]. label-flipping attack [9), Inner Product Ma- nipulation (IPM) attack (for regimes of 0.5 and 50 respectively) [23], and "A Little Is Enough" (ALJE) attack [24]. These four types of Byzantine models are commonly considered in the literature [25], and they represent wide range of attacks varying in aspects such as the gradi- ent norms and adversary's 's knowledge. To test the effectiveness of NBS, we compare it with several robust aggregation measures Krum [7], coordinate-wise median (CM) [9] and coordinate-win trimmed mean (CTM) [9], as benchmarks, along with the plain averaging (ERM). For Krum, CTM, and NBS, the screening/rrimming parameter is chosen based on the Byzantine percentage a. This allows these robust schemes to effectively aggregate gradient information and achieve better performance compared to schemes that do not consider a. In practice, can be set as the estimated upper bound of the Byzantine percentage, as the exact value of a may not always be available or reliable during the training process.
5.2 Evaluation
First, we seek inspect the robustness of NBS compared with other benehmarks, without incorpo- rating q-FFL for the moment. This is because reasonably high accuracy should always be the first priority of model training, without which other parallel goals such as fairness would be meaningless. In Figure 1, we plot the performance curves of model accuracy for the five considered aggregation measures (ERM, NBS, CTM, CM, Krum) under various attack regimes, using learning rate 7) and number of iterations T = 300. From Figure 1, we can see that NBS enjoys the best overall performance, due to its ability to utilize redundant information as well as its resilience to large-norm attacks (such as sign-flipping attack and IPM attack with 50 where ERM performs poorly).
EEM
0.8
0.7
CTM
1021
0.7
0.6
frum
FRP
NE5
555
0.5
0.4
0.6
52
100
150
330
102
150
150 Resstion
Beration
(a) No attack
(b) Sign-flipping attack
(c) Label-flipping attack
0.0
5.9
0.9-
0.6
0.6
CTM
0.7
0.5
0.6
15
0.5
CIM
0.4
52
100
150
203
250
310
50
100
150
200
253
300
120
150
200
250
300
Baration
Ierofon
Iuration
(d) IPM attack (e 0.5)
(e) IPM attack (E 50)
(f) ALIE attack
Figure 1: Model accuracy of different robust aggregation schemes under various attacks.
8

---

This result verifies that the theoretical advantages of NBS over other robust benchmarks in handling Byzantine attacks can extend to practical applications. In contrast, CM and Krum fail converge to functioning model even in the absence of Byzantine attacks. The only other robust scheme with comparable robustness performance to NBS is CTM, which achieves a worst-case test aceuracy of 79.7% compared to 85.4% for NBS.
Next, we incorporate the q-FFL objective (Step in Algorithm 2) into NBS and investigate how NBS, while ensuring Byzantine robustness, affects the fairness performance. In Table 1, we document both the model accuracy and the variance of local accuracies (the metric of model fairness) using different values of and screening percentage 3. The learning rate 1j and number of iterations T for each q value are carefully selected to ensure fast and stable convergence. Table shows that vanilla q-FFL (under 3 = 0) achieves the intended tradeoff between utility (high accuracy) and fairness (low variance), with larger q focusing more on fairness. In particular, q = leads to a desirable tradeoff by significantly reducing the variance (from 480 to 269) while only marginally decreasing the model accuracy (from 92.5% to 91.3%) ) By comparison, the study in [16] reports that q-FFI. reduces the variance of accuracies across devices by an average of 45% with similar decrease in overall accuracy. Therefore, we choose = for the q-FFL scheme in the remaining experiments.
Table I: The impact of screening on the performance of H-nobs (with no attack).
3
10%
3 20%
| =0%
(n) T))
9 = 0
92.5% (480)
92.7% (389)
92.5% (396)
92.2% (392)
(1, 300)
9 0.5
92.0% (405)
92.4% (364)
92.3% (368)
92.2% (381)
(0.5, 1000)
0 = 1
91.3% (269)
92.0% (327)
91.9% (331)
91.1% (349)
(0.5, 1000)
9 = 2
86.9% (156)
89.5% (253)
89.0% (243)
88.9% (260)
(0.2, 1500)
From Table observe that increasing 3 does not have obvious effect the model accuracy, since screening up to 30% of gradients still leaves enough redundant information in the absence of Byzantine attacks. On the other hand, the effects of screening on fairness are quite different for small and large g regimes. Specifically, when = O, the variance is at its highest, which sug- gests a relatively wide gap on the local accuracies. In that case, screening up to 30% of gradients coincidentally suppresses some of the divisive nodes and makes the results fairer. However, when q 2 1, the variance is small, in which case the screening operation begins to compromise fairness by increasing the variance, since it inevitably filters out certain fairness fairness-enhancing gradients. This phenomenon corroborates our hypothesis in Introduction about the internal conflicts between fair- ness (up-weighted objective) and robustness (filtering of outliers). Despite the inevitable impaired performance on fairness compared to vanilla q-FFI., H-nobs (e.g., with q = and B = 20%) strikes good balance between robustness and fairesss, being able to defend against up to 20% of Byzan- tine nodes while securing some fairness gains. In addition, we observe a similar interplay between robustness and fairness in the Law School dataset [26] and the Credit Card Client dataset [27], both of which are commonly considered in the context of fairness-aware machine learning [28]. The results for these two datasets are presented in Appendix E.
Table 2: The influence of various attacks on both robustness (accuracy) and fairness (variance).
q-FFL
q-FFL+ + NBS
q-FFL + CTM
q-FFL CM
q-FFL + Krum
No attack
91.3% (269)
91.9% (331)
91.5% (316)
62.0% (N/A)
62.8% (N/A)
Sign-flipping
61.1% (N/A)
91.0% % (265)
87.4% (143)
47.3% (N/A)
82.1% (291)
Label-flippigg
80. % (150)
81.5% (220)
87.9% (61)
45.8% (N/A)
57.9% (N/A)
IPM (e 0.5)
89.8% (76)
87.1% % (437)
90.8% (357)
54.4% (N/A)
57.4% (N/A)
IPM (c = 50)
61.1% (N/A)
90.3 % (94)
71.1% (186)
54.6% (N/A)
88.5% (245)
ALIE
76.0% (211)
90.0% (72)
88.1% (62)
48.4% (N/A)
88.5% (245)
9

---

Finally, we compare H-nobs (i.e., q-FFL + NBS) with the combinations of q-FFL and other ag- gregation schemes in the Byzantine setting with 4 Byzantine nodes. The robustness and fairness performance of candidate algorithms under various attacks is summarized in Table 2, using learning rate 7/ = 0.5 and number of iterations = 1000. We exclude the variance if the model accuracy falls below 65%. In Table 2, we can see that in the Byzantine-free case, both NBS and CTM effec- tively maintain the fairness improvements achieved by q-FFL, as they have a much lower variance than ERM (480), which uses the traditional training loss F instead of the fair objective H. When Byzantine attacks are introduced, NBS demonstrates the highest level overall robustness, achiev- ing worst-case test accuracy of 81.5%. In comparison, the second-bes, performer, CTM, reaches 71.1%. This suggesting an even wider performance gap than when considering these two schemes without integrating with q- q-FFL, which had worst-case accuracies of 85,4% and 79.7% respectively. These findings further support our choice of NBS as the aggregation method, which showcases not only theoretical but also empirical advantages over its robust-mean-bot fairnsss, both NBS and CTM exhibit varying performance depending on the specific attack regimes, due to the unpredictability of Byzantine gradients. As result, no definitive conclusion can be drawn regarding the tradeoff between robustness and fairness in the presence of Byzantine attacks,
counterparts. In terms of
5.3 Summary and discussion
In this section, we first empirically illustrate the effectiveness of NBS against various Byzantine at- tacks and its advantage over other robust benchmarks. Then, we investigate the influence of screen- ing on the fairness performance for H-nobs, verifying the internal conflicts between robustness and fairness. Finally, we compare H-nobs with other benchmarks under different attack regimes, demon- strating the robust performance of H-nobs and indicating that the fairness gains vary significantly depending on the attack regimes.
We want to point out two limitations of our empirical exploration. First, our simulations are based on fixed Byzantine percentage a 20% and fixed level of data heterogeneity (i.e., in (2)), both of which can have impact on the convergence demonstrated in Theorems 1-3. However, as a or a increases, overcoming Byzantine failure might become an intractable task due to the insufficient redundancy among the honest users. We leave the exploration on the robustness/fairness tradeoff under different o/a regimes for future work. Second, our evaluation of fairness is conducted based the specific q-FFL objective under the egalitarian fairness notion. Whether not empirical results apply to other fairness notions or objectives is an open question and deserves further investigation in the future.
6 Conclusion
In this paper, we recognize three important but underexplored questions related to fair and robust dis- tributed learning. We address these questions by proposing a new framework H-nobs that achieves joint fairness and robustness. The convergence of the proposed algorithm, even under the challeng- ing non-iid settings, is theoretically guaranteed for different types of learning models. We empir- ically verify the effectiveness of our algorithm under various attack regimes, and we also take the initiative to investigate the influence of robisteess-oriented screening on the performance of fairness.
Acknowledgments and Disclosure of Funding
This work was partly supported by the NSF grants No. 1939553, No. 2003211, and No.223 2231
10

---

References
[1] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--fiien -eftiionefffiient learning of deep networks from decentralized data. In Artificial In- telligence and Statistics, pages 1273-1288 1282. PMLR, 2017.
[2] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji. Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210 2021.
[3] Xinyi Xu and Lingjuan Lyu. Towards building a robust and fair federated learning system. arXiv preprint arXiv:201 1..:26411.004,, 2026.
[4] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pages 6357-6368. PMLR, 2021.
[5] Zeou Hu, Kiarash Shaloudegi. Guojun Zhang, and Yaoliang Yu. Federated learning meets multi-objective optimization. IEEE Transactions on Network Science and Engineering, 0(4):2039-2051,22))
[6] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, pages 1939-1938. PMLR, 2018.
[7] Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learn- ing with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
[8] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 12)):1255, 2017.
[9] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust dis- tributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages $650-5659 PMLR, 2018
[10] Lili Su and Jiaming Xu. Securing distributed gradient descent in high dimensional statisti- cal learning. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(1):1-41,2019,
[11] Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramachan- dran. Communication efficient and byzantine tolerant distributed learning. In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2545-2550. IEEE, 2020.
[12] Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Detox: A
rcdundancy-based framework for faster and more robust gradient aggregation. Advances in Neural Information Processing Systems, 32, 2019.
[13] Solon Barocas and Andrew D Selbst. Big data's disparate impact. California Law Review, pages 67 171-732. 2016.
[14] Shi, H Yu, and C Leung. survey of fairness-aware federated learning. arxiv 2021. arXiv preprint 1xXiv:2111.0188
[15] Kate Donahue and Jon Kleinberg. Models of faimess in federated learning. arXiv preprint 1rX00:211..008/8, 2021.
[16] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. International Conference on Learning Representations, 2020.
[17] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In International Conference on Machine Learning, pages 4615-462. PMLR, 2019.

---

[18] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concurrency: The Works of Leslie Lamport, pages 203-226 2019.
[19] Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine-resilient distributed training via redundant gradients. In International Conference on Machine Learning, pages 903-912. PMLR, 2018.
[20] Avishek Ghosh, Raj Kumar Maity, and Arya Mazumdar. Distributed newton can communi- cate less and resist byzantine workers. Advances in Neural Information Processing Systems, 01188000888388 2020.
[21] Mark Hopkins, Erik Reeber, George Forman, and Jaap Suermondt. Spambase, 1999.
[22] Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. Rsa: Byzantine- robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1554-1551, 2019.
[23] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine- tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pages 261-270. PMLR, 2020.
[24] Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
[25] Shenghui Li, Edith C-H Ngai, and Thiemo Voigt. An experimental study of byzantine-robust aggregation schemes in federated learning. IEEE Transactions on Big Data, 2023.
[26] Linda Wightman. Law school admissions bar passage, 1998.
[27] I-Cheng Yeh. Default of credit card clients, 2016.
[28] Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey datasets for fairness-aware machine learning. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(3):e142,, 2022.
12

---

Appendices
A Proof of Lemma 1
1 For G
Tि. EiEu 9s with =
3)m)} and any specific vector S, we have
| 5||
9:
S
12
EN
9 5)
[24]]
iEM
(g: - S)+ +
Σ
(g. S)
[
HEWMM
iEVnnB
19 - S|| +
Σ
119: S/1
U
iEMinS
For 24 0 M, |1: S|| S (we define maxieM 1lg, S)))
For i E 21 n B, we bound
||:: - S|| as follows:
11: - S| 2199: + ||||
((((1))mm || + |||||
(19((1))mm)l + ||||
max ||9:1 || ||||||
.EM
max |1 - + S| + |||||
iEM
max ||:; - S + S||
FEM
=A A S||-
Combining the above results, we have
| -
UMM A UnB B) (A 2((Ss))
17
[4] A + 2 ||$T]
24 B
+
|||||
2x
<A +
|||||
1 8
which is exactly the conclusion in Lemma 1 after we replace S with VH. Note that in (6), the last inequality only holds on condition that [3] < [U], i.e., S - 3, which, combined with 3 a, suggests that < 3
13

---

B Proof of Theorem 1
According Assumption (0) is smoothh.hh According the property of smoothness, we have
H (6 & H())) + (VH(0)), 01) + Lu 0 - 0ell
2
= H(0)) (V,) + LH "/111(00)11
2
= -O.))) 1 (O)(0)),G(0)) VH(0,) + VH(O))) + 1 -1G(()) V + VH(0))
TH
2T
- = -H(0)) 1 VH(O))) + (IVH( - -VH(0.11
T
2TH
1
= -(()) 2LH
(H())))
|G((0) VH(0.)1
2L
where the first equality follows from 0.41 - G(O,) and the second equality follows from
7 ZØ Note that the derivation of (7) is common trick in analyzing the convergence of smooth
functions which shifts the burden of proving convergence into the relatively easy task of quantifying
[G(0,) (0.)))
Combining Lemma and Assumption 1, we have [[G(0,) VH(0)) & C. VH) + a, which leads to
|G(0,) CHH +2
(8)
< ([++))
for any r 0. 0.
Combining (7) and (8), we have
1 (1+
VH(0))1 + 1+1/r
((0+11) H(0))
0²
(9)
2LH
2L
which is equivalent
2LH
1 1/r
[VH(1 < 1- (1 + r)
(0.) (100))(((0++))) + 1 + r)2
(10)
Summing up (10) fort 0,1,..., T- 1 before divided by T gives
2LH
[H(0)) H(rr)] + 1 1+ 1/r
(VH())
(1 (1+ C22
(1 + r)
(1I)
2LH
1+
[H())) H(O'] 1 (1 r)
(1- (1++)))
which is exactly the conclusion in Theorem
Note that the transition from (9) to (10) only stands under the condition that 1- > 0, which
constrains the less than T 1. On the other hand, > O, which requires C.. I-3 <
i.e. 2a 3 < 1. Since B > we can conclude that (11) holds if and only if and 0 < r
1.

---

C
Proof of Theorem 2
According to Assumption the convexity of (0) suggests that (0)) ( (V Q,), which leads to
H(O,)) H(00) < (O:) (,, -
< VH)) ||0, 0*
(12)
- DIIVH((O))
in which D = kl|00 1- The third inequality of (12) follows from Assumption 4. As result, we obtain (13) as key property for the subsequent analysis.
1 - [1(0)) H[O)] IV Z D
(13)
Since Theorem 2 keeps all the assumptions made in Theorem 1, all the intermediate steps in the proof of Theorem I also apply here. In this regard, we borrow (9), i.e.
H(0++1) (0.) S A (0))l + B
(14)
in which we define A 1- 1-(1+) and B (1+1/r)a²
for convenience.
2L
2L
Next, we consider two cases in regard to the relationship between A ( and B.
Case 1. Suppose for all i T holds that B < 4 (0.)1 In this case, have
H(O++1) H(0)) - - VHH))
(15)
Combining (13) and (15) gives
2D2
( =H0000)0= < (1H(O))-H(0')) -(00)) H(00)] (0(0)))) H(O)))
(16)
A
which, after divided by (O:) H (00) [H(0++H) - H (0+)] on both sides, leads to
(O:)) - (0')) 2D²
((0++1) - (0*) < According to (15), (0+41) S H(.)). Therefore, -((-)-H(00))
- ((00))
(17)
A 1(0++1)-H(0)
2 a,d (17) can simplified as H(014:)-H10*)
1
1
A
(18)
H(0++1) H()))
H(O,) H(8))
2n
Summing up (18) for t 0.1...., T gives
AT
2
+
H(Or) H(0))
2D
H(Oo) H(0))
(19)
AT
2D
which leads
2D2
H(Or) H(0*) <
(20)
AT
Case 2. Suppose 3 to E {0, 10.1....,7 T 1}. such that B 4 (0.,). In this case, we have
2B
(H. <
(21)
A
Combining (13) and (21) gives
2B
H(0") DV H(O,,) (10)))H((8)))
(22)
A
15

---

Next we show by contradiction that for all f 2 to. it holds that
2B
H(O)) H((0) D
B.
(23)
A
Suppose that there exists f 2 to such that
2B
H(O,,) H(00) > DV
+ B.
(24)
According to (14), we have
H(O,)) - H(0 5 ( BB
(25)
B.
Combining (24) and (25) gives
2B
- H(0)) > D -(B(
(26)
A
Combining (26) and (13) gives
(0., 2B
(27)
A
Plugging (27) into (14), we obtain H() 2 (O,,)++ which suggests that (24) also holds with replaced by 1 1. By the same token, by all t < t1. This is in clear contradiction with the incident of to as shown in (22). Therefore, (23) valid for all to stated.
conclude that (24) should hold with 4 replaced
Finally, combining the results of Case (20) and Case 2 (23), we achieve that
2D
2B
H(Or) - -(O0) S max
D
+
AT
A
(28)
AL. DD
2(1 + 1/r)
(1 11+1/r)0²
max
(1-
(1+ (1)
Do +
2L
which completes the proof of Theorem 2.
16

---

D Proof of Theorem 3
According Assumption 2, (0) is -mmoothhh and according to Assumption 5, (0) is Ag- strongly convex. In convex optimization theory, it is well known that smooth and strongly convex functions enjoy linear convergence rate with gradient descent. Here we will first establish and then use such a property with specific convergence factor. We start with the following equality
00 7 ( (0.) 0*| |0:- 0t' 1 2ny ( H (8,), 0r 0*) + r² (VH().))
(29)
According to the co-coercivity of smooth and strongly convex function, we have
1
LμA# 110 10 (30)
(H.))) VH(0")1 LH + d Since 6* is the global minimizer of (0)) and therefore (H*) 0, (30) reduces to |VH())) +
(V. - (H)))). 0: 8*) 2
LH Hy
LиdN
(V.( 02 - 0-) 2 LH + λH
110 1-
(31)
Lи + Aн
Plugging (31) into (29), we have
|00 |0.-NVH(0)- < (1 211 LH + AH
2n
110, 110.-0012+
17"
VH(0))1 (32)
LH AH In order to eliminate the last term (32), we take 17 = Iu+ and simplify (32) as
AT.1AH ) |10- - 1-11
- ( - -011
(33)
(LH + )
which is the same
- ( - 10 Lu A 1| - 0-
(34)
LH + AH
which verifies linear convergence with factor of Lu+AM
Lu-AH,
Note that (34) holds on condition that
Ln+An Next, we try evaluate the single-step progress made by our algorithm follows:
|10++1 - 0' = 10: n),(),) 0'll
10: (H()) 0" (V. -(.))-
S 00: ((,)) 001l + v/lV - G(O.)II
LH NH
2
(35)
||0; - -8"11 +
[[G(0)) - VH(IIII
LH + λH
LH + AH
LH AH
2C.
2a
110, 0*1 +
(HH +
Ln AH
Lu AH
LH An
in which the second inequality follows from (34) by taking 77 = Iu+An and the third inequality follows from Lemma and Assumption 1.
According to the properties of (0) being -mooth, we have
LH
[H(0)) ((,))) H(00) s
10,
0" 12
2LH
2
which leads
VHH < LH LH 1-
(36)
Plugging (36) into (35), we have
2T + Lu Au 110 0*
2x
|00+1 0-ll N
(37)
LH + dH
Lu + A
By iterating (37) obtain
0r 0' CT. Ton - An
T
1100-011
(38)
LH + A
Aн LHC.
which is exactly the conclusion in Theorem 3.
Note that the transition from (37) to (38) only stands under the condition that 24n Chu < 1, Lu+An i.e., 2a Lu + B 1. Since 8 2 a, we can conclude that (38)
which requires C. 1-88 <
Au. T
Ah
holds if and only if (z < T42Ln/Ag
17

---

E
The interplay between robustness and fairness in two additional datasets
Table The performance of H-nobs on the Law School dataset (with no attack).
[ =
3 = 10%
3 = 20%
B = 30%
(1). T)
9 0
90.7% (559)
90.6% (523)
90.6% (512)
90.6% (507)
(0.1, 500)
9 = 0.5
89.8% (483)
90.3% (478)
90.3% (470)
90.4% (465)
(0.05, 1000)
0 = 1
87.3% (353)
89.9% (449)
90.2% (451)
90.2% (448)
(0.02, 2000)
9= 2
66.2% (228)
73.3% (428)
74.0% (447)
73.9% (445)
(0.005, 5000)
Table 4: The performance of H-nobs on the Credit Card Client dataset (with no attack).
3 10%
3 =
20%
B = 30%
(7) T)
9 = 0
80.7% (1195)
80.5% (1143)
80.6% (1181)
80.6% (1 (484)
(0.2, 500)
9 = 0.5
81.0% (1123)
80.3% (1081)
80.3% (1140)
80.4% (1105)
(0.1, 2000)
0 = 1
81.0% (987)
80.1% (1006)
79.8% (1058)
80.0% (1035)
(0.1, 2000)
9 2
78.9% (869)
79.1% (887)
79.0% (930)
79.3% (966)
(0.05, 5000)
For both the Law School dataset and the Credit Card Client dataset, we use 3 as the training/testing split ratio and divide the training data into two groups based on the male/female feature (instead of the label), which a commonly considered attribute in fairness research. Similar to the previous setup, distribute the grouped training data across 20 nodes in balanced manner. The perfor- mance of H-nobs on these two datasets detailed in Table 3 and Table 4, respectively.
Tables 3 and 4 exhibit pattern similar to that in Table 1: when the variance is high (under small regimes), increasing 33 does not impair fairness; however, when g-FFL achieves significant fairness gains (under large y regimes), fairness is compromised by the screening operation. Note that here we only consider the effects of screening, not in combination with attacks. When Byzantine attacks play, Table 2 demonstrates satisfying robustness performance of H-nobs, although the fairesss gains achieved by q- q-FFL can vary considerably depending on the attack regimes.
18


Reviews:
[{"review_id": "lvvfQ3m4Xt", "reviewer": "Reviewer_hrXW", "summary": "This paper acknowledges and tackles the challenges associated with fair and robust distributed learning. It addresses these challenges by introducing the H-nobs framework and provides convergence guarantees under different convexity assumptions. The proposed algorithm is then evaluated through experiments under various attack regimes to demonstrate its effectiveness.", "questions": "* Can H-nobs support minimax fairness notions such as AFL or DRO, as stated in line 143? Given that NBS removes the gradients with large norms, my understanding is that picking such fairness notions might result in a model with low fairness or even no utility.\n    If this is indeed the case, this ans similar statements require revision.\n   \n* Is there a principled way to define $\\alpha$? In my view, there should be at least an experimental ablation study showcasing how $\\alpha$ impacts the performance of the proposed approach.\n    \n* What is the value of $q$ for the q-FFL in the experiments? Other relevant implementation details about hyper-paramenters are missing etc.,\n \nMinor:\n\n* references across the paper are not hyperlinked\n* line 128: does the percentage $\\alpha \\in [0,1)$?", "limitations": "The authors could further enhance their discussion on the limitations of the proposed work. While they acknowledge the limitations related to fixed data heterogeneity and Byzantine users, there are additional experimental constraints that should be acknowledged. Additionally, it would be valuable for the authors to address any potential conflicts between the proposed framework and certain fairness definitions that may require further attention. For more details, please refer to the weaknesses and questions highlighted earlier.", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "* Addressing the combinatorial issue of achieving fairness across clients and robustness in federated learning holds significant importance.\n* Convergence guarantees under various convexity assumptions are provided, along with the respective discussion.\n* The paper addresses novel questions regarding robustness and fairness trade-offs in FL settings.", "weaknesses": "* My main concern is the experimental evaluation. In particular, the paper considers just one dataset, examines a single value of $\\alpha$, one data heterogeneity setting. A single setting cannot provide enough evidence to thoroughly evaluate the applicability and utility of the proposed approach with confidence.\n\n* The reproducibility of the presented results is limited due to the insufficient information provided about the experiments, such as the learning rate, the value of $q$, and other relevant details.\n\n* The number of Byzantine users $\\alpha$ must be known a priori and is fixed throughout the training process. \n\n\n*  The work assumes that the data is balanced across clients, which may be unrealistic in federated learning settings. Although the paper briefly acknowledges that imbalancedness can be supported (line 126), there is limited practical information provided on how this can be effectively implemented or realized.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** *My main concern is the experimental evaluation. In particular, the paper considers just one dataset, examines a single value of $\\alpha$, one data heterogeneity setting. A single setting cannot provide enough evidence to thoroughly evaluate the applicability and utility of the proposed approach with confidence.*\n\n**Response:**\nThank you for your insightful comment. We believe that thoroughly addressing this concern is very important. Please refer to the **[Fairness Evaluation on $q$-FFL]** and **[Additional Empirical Settings]** sections in the global response, where we provide sufficient clarification on this matter.\n\n**Comment:** *The reproducibility of the presented results is limited due to the insufficient information provided about the experiments, such as the learning rate, the value of $q$, and other relevant details.*\n\n**Response:**\nThank you for pointing out this issue. Here is a detailed breakdown of our experiment executions.\n- **Data split.** As in Lines 275-278, we evenly split the training data among 20 nodes, 8 of which only hold spams (labelled as 1) and the other 12 only hold non-spams (labelled as 0). In the Byzantine setting, we pick 4 nodes as Byzantine (2 from each group). We set $\\alpha m=4$ because our previous work shows that NBS can tolerate up to 4 Byzantine nodes while guaranteeing 80\\% test accuracy.\n- **Hyper-parameters.** For Figure 1, we set the learning rate $\\eta=1$ and number of iterations $T=300$ for all the tested cases. For all the experiments in Table 1 and Table 2, we set $q=1$, $\\eta=0.5$ and $T=1000$. We use a smaller learning rate for the latter case because it is easier to diverge due to the up-weighting effect of $q$-FFL. Throughout, the five (or six) tested algorithms all start from the same randomly-generated initial model, and each experiment is repeated 10 times using different random initialization to obtain the averaged results.\n\n**Comment:** *The number of Byzantine users $\\alpha$ must be known a priori and is fixed throughout the training process.*\n\n**Response:**\nThank you for your comment. We believe that having to know/fix $\\alpha$ beforehand may not necessarily be a weakness, since knowing $\\alpha$ allows the scheme to flexibly aggregate the available information and achieve better performance. To see this, let's compare two coordinate-wise schemes: CTM, which requires $\\alpha$, and CM, which does not. From Figure 1 in the manuscript, we notice that CTM consistently outperforms CM under all cases by a large margin. This is because CTM utilizes a flexible combination of filtering and aggregating based on $\\alpha$. In practice, one can set $\\alpha$ as the estimated upper-bound of Byzantine percentage, say 20\\%. Note that in a practical non-iid setting, if the actual Byzantine percentage exceeds 20\\%, then achieving robustness might become an insurmountable task due to the lack of available redundancy (see Fig.1 (e)-(h) in the attached PDF).\n\n**Comment:** *The work assumes that the data is balanced across clients, which may be unrealistic in federated learning settings. Although the paper briefly acknowledges that imbalancedness can be supported (line 126), there is limited practical information provided on how this can be effectively implemented or realized.*\n\n**Response:**\nThank you for your question. To demonstrate unbalanced data allocation, let's consider a simplified case with two users, holding 3 and 7 samples respectively. Using the objective in Line 143, the local training losses on these two users are $H_1(\\theta)=\\frac{1}{3}\\sum_{j=1}^{3}[f(\\theta;x_j)-\\mu]^2_+$ and $H_2(\\theta)=\\frac{1}{7}\\sum_{j=4}^{10}[f(\\theta;x_j)-\\mu]^2_+$ respectively, which reflect a sense of fairness and can be incorporated into our framework.\n\n\n**Comment:** *Can H-nobs support minimax fairness notions such as AFL or DRO ...*\n\n**Response:**\nTo address this concern, we want to point out that H-nobs only removes large-norm gradients on an iterative basis, which means that the honest users whose gradients are discarded in certain iterations would always have a chance to catch up in later iterations. Also, within a single iteration, even if the honest gradients with the largest norms are removed, not all is lost because the surviving honest gradients still carry the goal of fairness, which is reflected in the expression of up-weighted objectives in both Line 143 and 144. On the other hand, discarding the gradients with the largest norms and siding with the majority of all gradients is the defining characteristic of all Byzantine-robust approaches, not just NBS. Although such a practice would inevitably cause conflicts with fairness, it may not necessarily lead to an unfair model, as illustrated in our empirical exploration.\n\n**Comment:** *Is there a principled way to define $\\alpha$? In my view, there should be at least an experimental ablation study showcasing how $\\alpha$ impacts the performance of the proposed approach.*\n\n**Response:**\nAs explained in a previous response, one can set $\\alpha$ as the estimated upper-bound of Byzantine percentage, which normally should not exceed 20\\%. Also, we have done such an empirical study as suggested but did not include it into the original manuscript. Please see the **[Additional Empirical Settings]** section in the global response.\n\n**Comment:** *What is the value of $q$ for the q-FFL in the experiments? Other relevant implementation details about hyper-parameters are missing etc.*\n\n**Response:**\nWe set $q=1$ throughout, which leads to decent fairness gains in our setting (see Table 1). The $q$-FFL paper [8] also uses $q=1$ for some empirical cases (see Table 1 therein). Note that we do not present results with different $q$ values because our focus is to address the conflicts between fairness and robustness, instead of finding the best $q$ value for $q$-FFL. For more implementation details, please refer to our response to your second comment regarding reproducibility.\n\n\n"}, {"review_id": "8xoNbUr5bn", "reviewer": "Reviewer_fgN6", "summary": "The paper explores robustness to byzantine attacks/failures as well as fairness in a federated learning setting.\nThe main focus of the paper is on a heterogenous user setting, i.e. data is non-iid between users. Particularly, the paper considers egalitarian fairness, i.e. uniform performance for all users.\nTo address this setting the paper combines (previously proposed) fairness-promoting losses with norm-based screening (NBS) for Byzantine robustness.\nIn a theoretical analysis, the authors show convergence (under suitable assumptions) where convergence speed depends on the number of Byzantine users.\nIn an empirical evaluation, the proposed method compares favorably in terms of accuracy, even in the presence of malicious users, and fairness (as measured by variance).", "questions": "- Can you clarify the contributions of the paper and comment on the novelty of the different aspects of the proposed approach?\n- Can you clarify whether the $\\eta$ in Line 143 (hyper-parameter of the fairness-aware loss) and $\\eta$ in Algorithm 2 Line 11 (learning rate) are indeed different?\n\n\nEDIT POST REBUTTAL: As my main question as sufficiently addressed I have increased my score.", "limitations": "A short explicit paragraph on limitations is given and limitations are discussed throughout the text.\nThis seems sufficient for the work at hand.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Byzantine robustness aspect is well done: theoretical grounding, empirical evaluation (fairness less so, see below).\n- Well written and easy to follow.\n- Good empirical results.\n- Intersection of fairness and robustness is an interesting and important topic. As a non-expert (in federated learning and the particular notion of fairness) this appears as a reasonable contribution to the field.", "weaknesses": "- With regards to novelty and contribution: Both NBS and fairness-promoting losses are not novel. While there is definitely value in the combination, \"framework ... containing them\" (L64) seem to be a bit of a stretch. The theoretical analysis of NBS though indeed seems novel.\n- Minor presentation issues.\n\nSee questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** *With regards to novelty and contribution: Both NBS and fairness-promoting losses are not novel. Can you clarify the contributions of the paper and comment on the novelty of the different aspects of the proposed approach?*\n\n**Response:**\nThank you for your insightful question. Although both NBS and fairness-promoting losses are not novel individually, no prior work has combined the two, or any other robust aggregation scheme with a fair objective. This combination might appear straightforward but is, in fact, highly challenging and non-trivial, as discussed in Section 4.3. The primary innovation of our work lies in establishing the theoretical foundation for attaining certified fairness and robustness within challenging non-iid scenarios. We achieve this by showcasing how NBS can be employed to address the formidable theoretical challenges, which might attract other researchers and inspire them to come up with better ideas and results. In addition, we take the lead in investigating the internal conflicts between fairness and robustness. Our preliminary results validate our initial hypotheses, potentially inspiring greater engagement within the community to invest more effort and gain a deeper understanding of the topic. In summary, the major contributions of our work are listed as follows:\n- We recognize the major challenges in obtaining joint fairness and robustness in distributed learning by identifying three important but largely unnoticed and unaddressed questions. Through this work, we have addressed these questions to varying degrees.\n- We propose H-nobs, the first algorithm that takes the (obvious but challenging) route of incorporating robust aggregation into existing fair objectives to achieve fair and robust distributed learning.\n- We achieve certified fairness and robustness for H-nobs even under the challenging non-iid scenarios, by establishing theoretical convergence guarantees with multiple levels of assumptions on the model convexity. Also, we clearly identify the major technical challenges that may hinder this goal, and illustrate how those challenges can be overcome by NBS through its theoretical robust property.\n- We empirically demonstrate the robustness and fairness benefits of H-nobs and take the initiative to investigate the empirical conflicts between fairness and robustness under a specific metric and objective of fairness.\n\n**Comment:** *Can you clarify whether the $\\eta$ in Line 143 (hyper-parameter of the fairness-aware loss) and $\\eta$ in Algorithm 2 Line 11 (learning rate) are indeed different?*\n\n**Response:**\nYes, they are indeed different. We should have used $\\mu$ for the hyper-parameter in Line 143 instead of $\\eta$, which denotes the learning rate. Thank you for this keen observation."}, {"review_id": "MtoVBOpK5M", "reviewer": "Reviewer_waox", "summary": "This paper proposes a protocol to address both fairness and Byzantine robustness in federated learning, and specifically i) the objective function is designed to take fairness into account, and ii) the algorithm takes an average of gradients with large norms and reduces the influences of large gradients. In addition to theoretical analysis, another important part of this paper is the discussion of these problems: 1) what makes achieving both fairness and robustness difficult; 2) to what extent does fairness harm robustness.", "questions": "I do not have additional questions other than those in the weaknesses section.", "limitations": "As mentioned in the weaknesses section, one may not be convinced that the NBS protocol is the uniquely suitable one with those advantages. It may be reasonable to mention this or alternatively provides more explicit support for that claim.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper thoroughly discusses the deep problem of fairness and robustness; such discussion in Section 1 provides insights on the principal aspects on some unexplored questions.\n\n2. The theoretical analysis is extensive, with multiple levels of assumptions (e.g. non-convexity vs convexity vs strong convexity) and corresponding guarantees.\n\n3. Section 4.3 provides convincing defense on the NBS protocol.", "weaknesses": "1. I’m not sure why having a large norm (at least possibly) implies maliciousness? I’m not an expert in Byzantine robustness, but if this is a result in this area, I’d certainly prefer to have a reference or at least a brief discussion.\n\n2. Even if the discussion in Section 4.3 clearly explains the advantages of the protocol, but claiming it as a “unique” protocol with those advantages (non-IID, no distributions on gradients, theoretical guarantees) may lack support.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** *I’m not sure why having a large norm (at least possibly) implies maliciousness? I’m not an expert in Byzantine robustness, but if this is a result in this area, I’d certainly prefer to have a reference or at least a brief discussion.*\n\n**Response:**\nThank you for your question. Let's first consider the one-dimensional case, where the averaging operation is sensitive to outliers (compare $\\frac{2+2+2}{3}=2$ and $\\frac{2+2+200}{3}=68$). In order to mitigate the influence of outliers, robust measures will discard the largest values when doing aggregation to avoid the worst case as in $\\frac{2+2+200}{3}$. Similarly, in high-dimensional cases, large-norm gradients are deemed as outliers that can potentially cause the most harm and therefore need to be removed.\n\n**Comment:** *Even if the discussion in Section 4.3 clearly explains the advantages of the protocol, but claiming it as a “unique” protocol with those advantages (non-IID, no distributions on gradients, theoretical guarantees) may lack support. Therefore, one may not be convinced that the NBS protocol is the uniquely suitable one with those advantages. It may be reasonable to mention this or alternatively provides more explicit support for that claim.*\n\n**Response:**\nThank you for this keen observation. Indeed, having certain advantages does not necessarily make a scheme unique and it is quite possible to discover other schemes with similar traits in the future. We appreciate your constructive suggestion and will change the wording in the revised version to avoid overstatement.\n"}, {"review_id": "tTPxXQObJ7", "reviewer": "Reviewer_9BqC", "summary": "This paper introduces a fair and robust algorithm in distributed learning setup, which combines q-FFL [8] (or the one by [6]) with the norm-based screening robust method. Three convergence results w.r.t. the algorithm are developed for non-convex, convex and strongly convex models. Experimental results are presented on the Spambase dataset. ", "questions": "Please see the Weaknesses in the above. ", "limitations": "Please see the Weaknesses in the above. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses an important issue dealing with both fairness and robustness aspects in distributed learning.  \n\n2. It derives three convergence theorems based on Lemma 1. The tightness of the bound in Lemma 1 is discussed via an illustrated example.\n\n3. The effectiveness of the considered algorithm and the relationship between fairness and robustness are explored via experiments. \n", "weaknesses": "1. The developed algorithm looks a simple combination of the prior works: ([6],[8]) for fairness objectives and [4] for gaining insights for NBS. \n\n2. The convergence theorems are derived under a certain regime, alpha <1/3. Also it  is not quite clear as to how the theorems explain the advantage of NBS over its counterparts. In addition, it would be more informative if the implication and meaning of the statements in the theorems are elaborated. \n\n3. It considers only one fairness notion, egalitarian fairness, under accuracy disparity. Any implications to other fairness notions and those beyond accuracy disparity?\n\n4. Oracle baselines (centralized fair and robust algorithms prevalent in the literat) could be considered in experiments. Also more extensive experiments (beyond only Spambase dataset) are preferred to be included.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comment:** *The developed algorithm looks a simple combination of the prior works: ([6],[8]) for fairness objectives and [4] for gaining insights for NBS.*\n\n**Response:**\nThank you for your comment. While it is true that the key elements of our framework, NBS and fairness objectives, both come from prior works, we want to emphasize that no previous endeavor has incorporated the two (or any other robust aggregation scheme with fairness objectives). The seeming simplicity of such combination belies its actual complexity, which we expound upon in Section 4.3. Accordingly, we illustrate how NBS can be employed to address the major theoretical challenges, which might attract other researchers and inspire them to come up with better ideas and results. In addition, we take the lead in investigating the internal conflicts between fairness and robustness. Our preliminary results validate our initial hypotheses, potentially inspiring greater engagement within the community to invest more effort and gain a deeper understanding of the topic. For more details, please refer to the **[Significance of This Work]** section in the global response.\n\n**Comment:** *The convergence theorems are derived under a certain regime $\\alpha<\\frac{1}{3}$. Also it is not quite clear as to how the theorems explain the advantage of NBS over its counterparts. In addition, it would be more informative if the implication and meaning of the statements in the theorems are elaborated.*\n\n**Response:**\nThank you for your comment. Although the theoretical convergence of our algorithm can only be achieved under no more than 33\\% of Byzantine users, we want to point out that this would have little practical impact. In a realistic non-iid setting, if the actual Byzantine percentage exceeds 20\\%, achieving robustness might become an insurmountable task due to the lack of available redundancy (see Fig. 1(e)-(h) in the attached PDF). As in Lines 228-230, we demonstrate that the typical and prevalent robust-mean-based methods not only require stringent/impractical assumptions but also lead to uninformative/loose bounds, making them unfavorable compared to NBS. For example, as one of very few works that provide convergence guarantees for robust-mean-based methods, [17] requires the iid assumption as well as the sub-exponential distributional assumption on the local gradients at all iterations (see Assumption 6 therein). In return, it can only bound $\\|G-\\nabla H\\|$ as a universal constant, which is directly applied to the developed convergence theorems, making the resulted inequality highly loose and potentially impractical. In contrast, our convergence results are grounded in a closely bounded $\\|G-\\nabla H\\|$, offering a more informative and realistic perspective. Moreover, our results achieve this without necessitating the assumptions of iid-ness and specific distributions on the gradients. Finally, Lines 203-206 demonstrate the respective influence of the Byzantine percentage $\\alpha$ and the data heterogeneity level $\\sigma$ on the convergence under multiple levels of assumptions on the model convexity.\n\n**Comment:** *It considers only one fairness notion, egalitarian fairness, under accuracy disparity. Any implications to other fairness notions and those beyond accuracy disparity?*\n\n**Response:**\nThank you for your question. We believe it is important to provide clarification on this matter, which is addressed in the global response. Please see the **[Fairness Evaluation on $q$-FFL]** section therein.\n\n**Comment:** *Oracle baselines (centralized fair and robust algorithms prevalent in the literature) could be considered in experiments. Also more extensive experiments (beyond only Spambase dataset) are preferred to be included.*\n\n**Response:**\nAs far as we understand, centralized algorithms are not applicable in the distributed setting unless they can be made decomposable/parallelizable through some means. Therefore, centralized fair and robust algorithms may not be comparable with our framework. Also, we have done additional empirical studies but did not include them into the manuscript. Please see the **[Additional Empirical Settings]** section in the global response for more details."}]

Author rebuttal:
We thank all the reviewers for their valuable time and helpful comments. Here we first want to highlight two key aspects of our work and then address two major concerns raised by the reviewers. In particular, we note that a reject recommendation was made mainly based on the extensiveness of our simulations, not on the technical merits of the proposed work. We provide detailed explanation on our evaluation to demonstrate that the evaluation is convincing, and thus does not warrant a reject decision. 

### [Significance of This Work]

- First, while deriving convergence guarantees, our work clearly exposes the decisive technical challenges thwarting this process, (i.e., stringent assumptions and loose bounds), and how those challenges can be overcome using NBS. Such revelations are the first of their kind, and may inspire future researchers to explore the commonalities of all qualifying schemes and propose other solutions beyond NBS. 
- Second, our proposed framework encompasses a broad category of fair objectives (i.e., decomposable), thus not limited to $q$-FFL. Unfortunately, there are not many such objectives in the current literature, since the goal of fairness has mostly been considered under the traditional (centralized) setting where all the data are accessible at a single node. As a result, the developed objectives often are not directly decomposable. However, this situation may soon change for the better as the distributed setting gains popularity these days, and we observe a trend of more centralized algorithms being customized into the distributed setting. For example, the objective in Line 143 was originally adapted from a centralized DRO objective, and then made decomposable using the duality transformation. The significance of our theoretical framework lies in that, whenever new decomposable fairness-aware objectives are developed in the future, our theoretical guarantees would still be applicable.

### [Fairness Evaluation on $q$-FFL]

In Lines 354-357, we comment that our empirical evaluation on fairness is focused on $q$-FFL, while the evaluation of other fairness metrics is left for future work. Both Reviewer hrXW and Reviewer 9BqC raised a concern that such evaluation does not appear to be general enough. Following our previous argument, we want to reiterate the current shortage of decomposable fairness-aware objectives. In fact, we only have two such objectives in the distributed setting (in Lines 143-144). We decide to stick with only one in order to streamline the presentation and avoid potential confusions. $q$-FFL is our choice because a) it is associated with egalitarian fairness, which is a well-defined fairness metric; b) it has better empirical performance than the alternative. Based upon the $q$-FFL objective, our work makes two important observations:
- Table 1 shows that under the Byzantine-free setting, the fairness gains introduced by $q$-FFL are unanimously reduced by the integration of robust measures. This result corroborates our analysis in Introduction about the internal conflicts between fairness (up-weighted objective) and robustness (filtering of outliers).
- Table 2 shows that under the Byzantine-prone setting, the negative correlation between fairness and model accuracy no longer holds due to the unpredictability of Byzantine gradients. Specifically, the fairness gains of each candidate algorithm can vary significantly depending on the attack regimes, and there appears to be no definitive conclusions on the tradeoff between robustness and fairness.	

Since the objective in Line 143 also utilizes the idea of up-weighting, we can expect very similar observations if we incorporate another set of experiments based on this alternative objective (and its own fairness metric), which may appear to be cumbersome/redundant for our presentation and also confusing due to the new fairness metric. In short, our evaluation of $q$-FFL might appear to be limiting, but is convincing enough to reveal the intricacy in addressing both fairness and robustness issues for general distributed learning applications. We note that Reviewer hrXW, while recognizing the significance and novelty of our work, made a reject decision citing limited evaluation. We hope that our justifications on the evaluation portion have sufficiently addressed such concerns.

### [Additional Empirical Settings]

Reviewer hrXW pointed out the lack of an experiment on the impact of $\alpha$. Such an empirical study has actually been done by another paper of ours (referred to as Paper A), which focuses on addressing both distributional shift and Byzantine failure. Paper A thoroughly compares NBS with other benchmarks under various circumstances and it finds that NBS functions well under different $\alpha$ and data distribution. In the attached PDF, we incorporate two tables and one figure that validate the effectiveness of NBS:
- TABLE I compares the test accuracy of different aggregation rules under $\alpha m=6$ Byzantine nodes (out of $m=20$) in the iid setting, and shows that all robust measures perform well due to the high level of homogeneity among the local gradients.
- TABLE II documents the same experiment in the non-iid setting and shows that no scheme can outperform all the other schemes across the board, but NBS clearly enjoys the best overall performance.
- Fig. 1 displays the performance curves under varying number of Byzantine nodes in both iid and non-iid settings. In the non-iid setting, NBS can tolerate up to 4 Byzantine nodes while guaranteeing 80\% test accuracy in all cases, the best among all candidates.

Note that we did not include too many of these results into the manuscript because our focus is the interaction between fairness and robustness. Nevertheless, we hope that these results offer convincing arguments on the usefulness of NBS and H-nobs. Also, we can send Paper A to the committee if requested, which is currently under submission to a journal.


Meta-review: This work explores tensions between fairness and robustness in distributed learning, and proposes an approach for solving a fair objective while enabling robustness to malicious updates. Reviewers agreed that this is an important problem to consider and appreciated the theoretical exploration of the topic, including rigorously studying the tension between fairness/robustness. However, as noted by multiple reviewers (and partially addressed during updated experiments in the rebuttal phase), the paper could be strengthened significantly by revising/updating the empirical section to include a broader set of datasets and more thorough comparison with baselines and existing methods.
Decision: Accept (poster)