Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients

1. Regarding Weakness 1

With regard to Weakness 1, the motivation behind normalization stems from its low computational complexity compared to existing robust algorithms, as justified between Line 50 and Line 58 and detailed in Table 1. Specifically, Fed-NGA benefits from reduced aggregation time complexity through normalization: normalizing and aggregating vectors at the central server incurs a complexity of $\mathcal{O}(pM)$. This is substantially lower than that of other robust aggregation methods, such as $\mathcal{O}(pM \log(M))$ for Median and $\mathcal{O}(pM^2)$ for Krum, as reported in Table 1 on Page 2. Empirical results in Table 3 on Page 8 and Figure 3 on Page 9 further validate the algorithm’s efficiency gains in aggregation speed.

2. Regarding Weakness 2

With regard to Weakness 2, to the best of our knowledge, no existing work has achieved a zero optimality gap, which remains the ultimate goal in convergence analysis, as also noted on Line 75 and Line 799. For the first time, we provide a theoretical condition under which a zero optimality gap can be guaranteed. Moreover, this condition is practically attainable, for example, in scenarios involving full-batch training on IID datasets, or when the inner error and data heterogeneity, as measured by gradient direction, are sufficiently constrained during training, as detailed in Appendix A.

Last but not least, we would like to emphasize that this result is only one of the three theoretical contributions presented in our work, beyond which we also have algorithmic and empirical contributions. As such, this particular theoretical result is not intended to be the primary contribution of the paper.

3. Regarding Weakness 3

With regard to Weakness 3, we would like to clarify that it is common practice in the literature to establish theoretical analysis under either the strongly convex or non-convex setting and then evaluate the proposed aggregation algorithms using standard and widely adopted training models, regardless of the specific assumptions made in the theoretical analysis. This practice is prevalent and generally accepted in our research community.

For example, CClip [1], whose convergence guarantee is established under the non-convex setting, is empirically compared with RFA, which is only theoretically justified under the strongly convex setting. Conversely, MCA [2], with theoretical support under the strongly convex setting, is experimentally compared with Krum, whose analysis assumes the non-convex setting. Therefore, our evaluation protocol follows the standard experimental practices adopted in this field.

[1] Karimireddy, Sai Praneeth, Lie He, and Martin Jaggi. "Learning from history for byzantine robust optimization." International conference on machine learning. PMLR, 2021.

[2] Luan, Zhirong, et al. "Robust federated learning: Maximum correntropy aggregation against Byzantine attacks." IEEE Transactions on Neural Networks and Learning Systems 36.1 (2024): 62-75.

4. Regarding Weakness 4

With regard to Weakness 4, we would like to emphasize that the primary advantage and contribution of our work lie in the final test accuracy achieved after convergence under various types and intensities of Byzantine attacks, rather than in the convergence speed.

In terms of the convergence performance of our Fed-NGA, we would like to clarify that, theoretically, as stated in both the Abstract and the summary of contributions (Line 71), we only specify that Fed-NGA achieves a convergence rate of $\mathcal{O}(1/T^{1/2-\delta})$, but we do not present this as an advantage over the baselines in terms of convergence speed. Experimentally, we also observe that sometimes Fed-NGA tends to converge slowly than some baselines.

Regarding the conceptual distinction between convergence speed and final test accuracy, we would like to emphasize that convergence rate is not necessarily indicative of the final accuracy. This phenomenon is illustrated in Figure 6 (Page 14) and Table 4 (Page 15). For instance, when training the LeNet model, Fed-NGA demonstrates slightly faster convergence than most baselines and ultimately achieves superior final accuracy. In contrast, when training the MLP model, Fed-NGA converges marginally slower but still outperforms the baselines in terms of final accuracy.

On the other hand, as explained in the paper starting from Line 490, we intentionally adopt a favorable learning rate setup for the baselines to improve their convergence speed compared to using our learning rate directly, in the interest of fairness. In summary, we did not tune the learning rate in a biased manner to gain an unfair advantage over the baselines.

5. Regarding Question 1

With regard to Question 1, we explain the definition of $\delta$ in Line 194 of our paper as “$\delta$ is an arbitrary value lying between $(0, 1/2)$.” This actually implies the $\delta$ serves solely as a tunable parameter for setting the learning rate and is not related to the proportion of Byzantine clients or any other physical parameters. Conceptually, $\delta$ can be viewed as a parameter that influences the convergence rate. Its presence indicates that convergence is guaranteed as long as the learning rate for given $t$ falls within a certain range, rather than requiring a specific fixed value.

Thank you for the explanation regarding $\delta$—I appreciate the effort.

Regarding the motivation for using normalization, I recommend that the authors provide more discussion and justification in the paper. In particular, it remains unclear why normalization is chosen as an improved technique under Byzantine threats, especially in the absence of sufficient supporting discussion.

Currently, the paper lacks a clear explanation of where normalization techniques have been applied in prior literature, what kinds of improvements they achieved in those contexts, and how those insights motivate their potential benefits in the Byzantine setting. Without such discussion, the use of normalization may seem lacking in principled motivation, even if it brings theoretical or empirical gains.

To enhance clarity and justification, I suggest incorporating related works that showcase the effectiveness of normalization in other scenarios. Representative works include, but are not limited to:

[1] Dai, Yan, Kwangjun Ahn, and Suvrit Sra. "The crucial role of normalization in sharpness-aware minimization." Advances in Neural Information Processing Systems 36 (2023): 67741-67770.

[2] Jakovetić, Dus̆an, et al. "Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise." SIAM Journal on Optimization 33.2 (2023): 394-423.

[3] Li, Xiaoxiao, et al. "Fedbn: Federated learning on non-iid features via local batch normalization." arXiv preprint arXiv:2102.07623 (2021).

[4] Wang, Jianyu, et al. "Tackling the objective inconsistency problem in heterogeneous federated optimization." Advances in neural information processing systems 33 (2020): 7611-7623.

Drawing such connections and clearly explaining how they inform the current application would help readers understand the rationale and novelty of using normalization under Byzantine threats.

Given the importance of this clarification, I believe this issue warrants further revision and possibly another round of review. Thank you again for the thoughtful response. I appreciate the authors' efforts and hope these suggestions are helpful in further improving the clarity and impact of the paper.

2. Regarding the selection of region $(0, 1/2)$ for $\delta$

The choice of $\delta$ is determined by the convergence condition of Fed-NGA, which is specified in Line 190 as “$\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} \eta^t \rightarrow \infty$ and $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} (\eta^t)^2 < \infty$”. This condition can be inferred from Equation (20). To satisfy this convergence condition, we define $\displaystyle \eta^t = {\eta}/{(t+c)^{1/2+\delta}}$ with $c > 0$ and $\delta \in (0, 1/2)$, with the convergence rate given by $\mathcal{O} (\frac{1}{T^{1/2-\delta}})$.

On the other hand, for other intervals or selected values of $\delta$, convergence may still be achievable, but they do not lead to improved convergence performance.

In the first step, it is worth noting that the left-hand side of Equation (20) can still converge under a relaxed condition, specifically when $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} \eta^t \rightarrow \infty$ and $\displaystyle \lim_{T \rightarrow \infty} \frac{\sum_{t=1}^{T-1} (\eta^t)^2}{\sum_{t=1}^{T-1} \eta^t} < \infty$.

Looking into the case for $\delta \in (-1/2, 0)$, which also promises convergence through the newly highlighted condition, the convergence rate becomes $\frac{\mathcal{O} (T^{-2\delta})}{\mathcal{O}(T^{1/2-\delta})} = \mathcal{O} (\frac{1}{T^{1/2+\delta}})$. It is straightforward to verify that the convergence rate $\mathcal{O} (\frac{1}{T^{1/2+\delta}})$ for $\delta \in (-1/2, 0)$ is the same as $\mathcal{O} (\frac{1}{T^{1/2-\delta}})$ for $\delta \in (0, 1/2)$. Thus, the convergence condition $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} \eta^t \rightarrow \infty$ and $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} (\eta^t)^2 < \infty$ with $\delta \in (0, 1/2)$ suffices to cover this case.

We further analyze the three boundary cases: $\delta = -1/2$, $\delta = 0$, and $\delta = 1/2$. For $\delta = -1/2$, we have $\eta^t = \eta$, which implies $\displaystyle \lim_{T \rightarrow \infty} \frac{\sum_{t=1}^{T-1} (\eta^t)^2}{\sum_{t=1}^{T-1} \eta^t} = \eta$. In this case, the optimality gap expands to $\mathcal{O} (\eta + \sigma + \theta)$, which is larger than $\mathcal{O} (\sigma + \theta)$ observed in other cases. For $\delta = 0$, $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} (\eta^t)^2 \rightarrow \infty$, and the convergence rate degrades to $\mathcal{O} (\frac{\log(T)}{T^{1/2}})$. For $\delta = 1/2$, while the convergence condition is satisfied, the convergence rate degrades to $\mathcal{O} (\frac{1}{\log(T)})$. Both of these rates are slower than our presented $\mathcal{O} (\frac{1}{T^{1/2-\delta}})$.

And for $\delta<-1/2$, $\displaystyle \lim_{T \rightarrow \infty} \frac{\sum_{t=1}^{T-1} (\eta^t)^2}{\sum_{t=1}^{T-1} \eta^t} \rightarrow \infty$, while $\displaystyle \lim_{T \rightarrow \infty} \sum_{t=1}^{T-1} \eta^t < \infty$ for $\delta>1/2$. None of the above two cases can promise the convergence of left-hand side of Equation (20).

In light of the above analysis and comparison, we set $\delta \in (0, 1/2)$ to ensure the convergence condition is met and to express the result in the most concise manner.

Thanks for the discussion.

1. Regarding the motivation

Firstly, we would like to reiterate that our motivation is solely grounded in addressing the limitations of prior works, particularly their high computational complexity. As stated in Line 57: “In this paper, we aim to fill this research gap, i.e., to reduce the cost of computational complexity for aggregation while preserving generality to data heterogeneity.”

Secondly, regarding the rationale for why normalization could serve as a viable or even effective operator against Byzantine attacks, we acknowledge that normalized gradient has been applied in machine learning without attack, such as in [1]. However, to the best of our knowledge, no prior work has utilized normalized aggregation specifically as a defense mechanism against Byzantine attacks in FL. Therefore, how normalization behaves under Byzantine threats remains unclear, and existing literature does not provide sufficient motivation to adopt it for Byzantine robustness.

Thirdly, regarding our initial motivation to choose normalization as the core aggregator, it comes from the intuition that normalization can reduce the influence of vector magnitude in FL training, particularly for outlier vectors, which is important for achieving robustness against Byzantine attacks. In addition, normalization preserves the directional information of vectors, which supports convergence in the absence of attacks, as discussed in [1]. However, we acknowledge that this intuition alone is not sufficient to serve as a solid motivation. It is only through our rigorous theoretical analysis and extensive empirical validation, both conducted for the first time in this work, that the effectiveness of normalization under Byzantine settings is confirmed. Therefore, at the stage of motivation, it would not be appropriate to present this intuition without theoretical or experimental support.

In summary, the only reason we adopted normalization at the motivation stage was its low computational complexity, without relying on any presumed benefits beyond that.

[1] Cutkosky, Ashok, and Harsh Mehta. "Momentum improves normalized sgd." International conference on machine learning. PMLR, 2020.

1. Regarding Weakness 1

With regard to Weakness 1, we acknowledge that the performance degradation of Fed-NGA is not entirely uniform. However, as shown in Figure 7 (Page 15) and Figure 9 (Page 16), nearly all baselines exhibit an inflection point where the degradation pattern shifts from a gradual to a markedly faster decline in test accuracy. For instance, Figure 7(b) and Figure 9(b) demonstrate that MCA and CClip experience a modest decline when $\bar{C_{\alpha}} \leq 0.1$, followed by a steep drop under the Same-value attack, reaching their lowest performance at $\bar{C_{\alpha}} = 0.2$. Similarly, Figure 7(e) and Figure 9(e) show that Median, Krum, and GM also undergo slow degradation up to their respective inflection points, after which the performance decreases rapidly under the FoE attack ($\bar{C_{\alpha}} = 0.3$ for Median and Krum, and $\bar{C_{\alpha}} = 0.2$ for GM).

These observations suggest that such abrupt performance degradation beyond certain Byzantine ratios is a common vulnerability in existing approaches. In contrast, Fed-NGA maintains a more stable performance trajectory, with test accuracy degrading slowly over a wider range of Byzantine ratios. The onset of sharp degradation is postponed to significantly higher Byzantine ratios, particularly under the Same-value and Sign-flip attacks. Moreover, Figures 7 and 9 show that Fed-NGA outperforms the baseline methods across the evaluated attack scenarios in most cases.

2. Regarding Weakness 2

We acknowledge that the performance of Fed-NGA degrades as $\beta$ decreases. However, as shown in Table 4 (Page 15), Table 5 (Page 17), and Table 6 (Page 18), the performance of nearly all baselines decreases as $\beta$ decreases. And the performance fluctuations under different $\beta$ settings are summarized in the table below (We omit FedAvg from the comparison here, as the algorithm barely converges under attacks.).

Table: Fluctuation of accuracy under different $\beta$ settings with $\bar{C_{\alpha}}=0.2$ over five attack types. - indicates that the algorithm does not converge under this setting.

From this table, the results indicate that Fed-NGA's (achieved 4 best performance) adaptability to data heterogeneity is comparable to that of GM (achieved 5 best performance) and MCA (achieved 4 best performance), and better than other robust algorithms. Additionally, even in suboptimal scenarios, Fed-NGA performs comparably to its optimal-case performance.

The above analysis confirms that Fed-NGA exhibits top-tier adaptability to data heterogeneity compared to all baselines, without displaying heightened sensitivity to it.

We would like to express our sincere gratitude for your diligent review of our paper. Your constructive comments have been instrumental instrumental in enhancing the quality of our paper, and we deeply value the insights you’ve shared. We are also thankful for your positive assessment of our theory, which serves as great encouragement for us to continue refining our work. Thank you once more for your time and invaluable support.

1. Regarding the communication cost issue

Regarding the communication cost issue, as detailed in Algorithm 1 on Page 5, Fed-NGA normalizes the uploaded vectors at the central server, requiring each participating client to upload its gradient (real or fake depending on whether it is malicious). This design yields exactly the same communication cost as all the robust baselines, and thus does not introduce any additional communication overhead.

2. Regarding clients contributing higher data quality, quantity, or training effort could deserve greater weight

We acknowledge that clients contributing higher data quality, quantity, or training effort could deserve greater weight. Nonetheless, under the threat of uncertain Byzantine behavior, relying on such trust becomes precarious. To be specific, Byzantine clients may gradually build credibility over multiple rounds before launching attacks, making over-reliance on them risky. On the other hand, this type of time-varying behavior highlights the need for robust methods that can adapt to dynamic adversaries. Although our analysis assumes fixed Byzantine clients, the proposed method actually remains effective even when the set of Byzantine clients changes over time, as long as the per-round Byzantine ratio $\bar{C}_{\alpha} < 0.5$ is maintained.

3. Regarding partial client participation and dropped clients

With regard to the case of partial participation, to the best of our knowledge, none of the existing robust aggregation methods, including ours, explicitly consider this setting. This is primarily due to a fundamental limitation. Byzantine clients, whose objective is to disrupt the training process, may consistently participate in each training round. If some honest clients are inactive due to partial participation, the instantaneous Byzantine ratio $\bar{C}_{\alpha}$ in a given round can exceed 0.5. This challenges the core assumption required by all Byzantine-resilient algorithms, namely that honest clients form the majority in each round, and poses a fundamental limitation on defending against Byzantine attacks without leveraging external trusted information. Even in scenarios where the central server randomly drops clients, regardless of whether they are Byzantine or honest, the resulting Byzantine ratio after dropping cannot be guaranteed to stay below 0.5, either.

On the other hand, partial participation or client dropout can be accommodated in our framework by treating inactive or dropped clients as Byzantine, since Byzantine clients are allowed to upload arbitrary gradients to the central server, including the null vector. Under this modeling, our theoretical results still guarantee convergence as long as the effective Byzantine ratio $\bar{C}_{\alpha} < 0.5$ in each training round, where inactive or dropped clients are also counted as Byzantine.

It is also worth noting that the set of tolerable inactive or dropped clients and Byzantine clients can vary across training rounds. Although our theoretical analysis assumes a fixed set of Byzantine clients, the proposed Fed-NGA actually remains effective even when the Byzantine set changes over time, demonstrating robustness under more dynamic and realistic conditions.

2. Regarding the concern 2

Regarding the scenario where dropped clients might increase the effective Byzantine ratio beyond 0.5, we have revisited the problem. Instead of treating dropped clients as Byzantine, our approach can in fact tolerate a higher number of Byzantine and dropped clients simultaneously.

To be specific, by excluding dropped clients from the aggregation and assuming the worst-case scenario where Byzantine clients never drop out, the proportion of Byzantine clients in the aggregation remains lower than that of honest clients as long as the condition 1 - dropout ratio $>$ 2 $\times$ Byzantine ratio holds. Several representative configurations characterizing this bound include: (1) Byzantine ratio = 0.1, dropout ratio = 0.8; (2) Byzantine ratio = 0.2, dropout ratio = 0.6; (3) Byzantine ratio = 0.3, dropout ratio = 0.4; (4) Byzantine ratio = 0.4, dropout ratio = 0.2. As long as the Byzantine and dropout ratios fall within these bounds, convergence is still guaranteed for our Fed-NGA. This refined analysis provides a tighter characterization of the feasible region, allowing for a higher tolerance of dropped clients, which better reflects practical scenarios.

To validate this, we conducted experiments under the two settings, evaluating final accuracy (%) using the LeNet model on the CIFAR10 dataset under the Sign-flip attack with the Byzantine ratio = 0.2 and $\beta = 0.6$. In the table, Bold indicates that the algorithm achieves SOTA performance, while Italic indicates that the algorithm failed to converge.

From the first row of the table, where the Byzantine ratio is 0.2 and the dropout ratio is 0.5, which does not violate the newly established bound, Fed-NGA achieves SOTA performance. This is because, after removing 50% of the clients and keeping the 20% Byzantine clients active, the effective Byzantine ratio among the remaining clients becomes 0.2 / 0.5 = 0.4, which is within the tolerable range derived in our analysis. In contrast, the second row corresponds to a Byzantine ratio of 0.2 and a dropout ratio of 0.7, which exceeds the derived bound. In this case, no algorithm is able to maintain convergence under such a high dropout rate in the presence of Byzantine clients. This highlights the existence of a critical dropout ratio threshold beyond which convergence cannot be guaranteed for any algorithm under Byzantine attacks.

Thanks for the discussion.

1. Regarding the concern 1

In practice, nearly all robust aggregation algorithms are implemented on the central server. They operate by taking the gradient vectors uploaded by clients as input and producing an updated gradient as output. This updated gradient is then used to generate the updated model parameters, which are broadcasted to all clients for the next training round. In both the uploading stage from clients to the server and the broadcasting stage from the server to clients, the aggregation algorithm does not alter the content or dimensionality of the transmitted vectors. Therefore, the communication cost between the server and each client is solely determined by the number of parameters in the vector and the storage format (e.g., float32 by default in PyTorch).

The experiments below demonstrate, for different aggregation algorithms, the number of parameters transmitted from each client to the central server per round or received by each client, the total parameter storage size, and the communication bandwidth required to upload these parameters within 1 second. These results are illustrated using the LeNet model on the MNIST and CIFAR10 datasets.

As shown in the table above, all algorithms, including Fed-NGA and baselines, require the same upload bandwidth. This is because aggregation algorithms do not alter the size of the parameters before upload or download. Compared with baseline algorithms, Fed-NGA is not an exception and consequently does not introduce any additional communication overhead.

Thanks for the discussion.

1. Regarding question 1

In fact, our work has clear distinctions from the referenced paper in both core objectives and technical approaches. The referenced paper focuses on achieving partial participation with Byzantine robustness simultaneously, employing gradient difference clipping between two adjacent local training steps to facilitate partial participation, while relying on existing Byzantine-resilient aggregation methods for robustness. In contrast, our work introduces a novel Byzantine-resilient aggregation method, Fed-NGA, which is specifically designed to defend against Byzantine attacks. This method demonstrates robustness and features low aggregation time complexity, with its core contribution lying in the innovation of the aggregation mechanism itself rather than addressing partial participation.

2. Regarding question 2

We attribute this phenomenon to the role of normalization, which helps mitigate the impact of data heterogeneity [1], [2]. All our experiments are conducted in a data heterogeneous environment, where data heterogeneity can be viewed as a form of perturbation. Fed-NGA is robust to Byzantine attacks, and as such, it naturally exhibits resilience to the perturbations induced by data heterogeneity. Consequently, based on the arguments outlined above, this indicates that Fed-NGA may outperform FedAvg in the no attack scenario. FedAvg is a classic FL algorithm, yet this does not imply it is well-suited to data heterogeneity. For instance, our experimental results show that MCA and GM sometimes achieve slightly higher accuracy than FedAvg, particularly under high data heterogeneity. This can be attributed to the fact that robust algorithms exhibit resilience to slight perturbations, such as those induced by data heterogeneity.

[1] Li, Xiaoxiao, et al. "Fedbn: Federated learning on non-iid features via local batch normalization." arXiv preprint arXiv:2102.07623 (2021).

[2] Wang, Jianyu, et al. "Tackling the objective inconsistency problem in heterogeneous federated optimization." Advances in neural information processing systems 33 (2020): 7611-7623.

3. Regarding question 3

The Fed-NGA algorithm we propose involves normalizing the vectors uploaded by clients, a process that alters the modulus of the aggregated vector $g^t$ and consequently impacts the tuning of the learning rate. This issue is also elaborated on in Line 490.

For the training model employed in our experiments, we observed that the vector modulus derived from local training is generally greater than 1. To address this, relative to the baselines, we increased the initial learning rate of Fed-NGA and reduced its learning rate decay rate to ensure convergence (Line 483). Additionally, we noted that baselines fail to perform adequately when using the learning rate parameters optimized for our algorithm (Line 491).

Furthermore, the normalization stabilizes the modulus of the aggregated gradient vector across rounds. This, in turn, reduces the sensitivity of convergence to the learning rate and does not increase the burden of learning rate tuning.

4. Regarding question 4

Under the conditions you specified, our simulations show that the average wall time required for one round of local training of the LeNet model on the CIFAR10 dataset is 42.3 ms on clients. Below, we take a Byzantine ratio of 0.3 as an example to present the per-round wall time considering only the aggregation time (ms) on the central server.

Specifically, the aggregation time of Fed-NGA accounts for only 0.2%-0.26% of the total per-round time (local training + aggregation). In contrast, Krum’s aggregation time exceeds 50% of the total round time across all attack scenarios, and GM’s aggregation time ranges from 27% (No Attack) to 63% (FoE) of the total time. This stark contrast demonstrates that Fed-NGA offers significant advantages in terms of runtime efficiency. The results clearly validate that the reduction in per-round FL time time achieved by Fed-NGA is practically meaningful.