Enhanced Byzantine-Robust Federated Learning Via Truncated-Quadratic Loss for Heterogeneous Data

Problem Statement
Federated Learning (FL) enables the training of deep learning models across distributed clients (e.g., mobile devices, sensors) without sharing raw data, thereby enhancing privacy. However, this distributed architecture introduces vulnerabilities to Byzantine attacks, where malicious clients send arbitrary updates to disrupt the learning process. Furthermore, real-world FL scenarios often involve heterogeneous data (non-IID), where data distributions vary significantly across clients. Existing robust aggregation rules, such as Krum, Coordinate-wise Median (CM), and Robust Federated Aggregation (RFA), often assume data homogeneity and degrade under heterogeneity. While Centered Clipping (CC) and Huber loss-based aggregators have been proposed to handle heterogeneous data, this paper identifies that they suffer from a critical flaw: they produce biased solutions when faced with large-magnitude outliers, particularly under conditions of high data heterogeneity or a substantial fraction of Byzantine clients. This bias compounds over communication rounds, leading to learning failure.

Methodology
The paper proposes a new robust aggregation rule based on the Truncated-Quadratic (TQ) loss. The methodology proceeds through the following steps:

1. Theoretical Analysis of Existing Methods: The authors first utilize convex conjugate theory to demonstrate the equivalence between Centered Clipping (CC) and Huber loss minimization for Byzantine-robust FL. They prove that both satisfy $(f, \kappa)$-robustness but share a common limitation: they employ the $\ell_1$-norm (or equivalent clipping mechanisms) to resist outliers. The paper theoretically analyzes and demonstrates that this approach yields a bias that grows with data heterogeneity and the fraction of Byzantine clients.
2. Proposal of Truncated-Quadratic (TQ) Loss: To mitigate the bias inherent in Huber/CC, the authors introduce the TQ loss function. Unlike Huber, which grows linearly for large errors, TQ clips the loss of outliers entirely once they exceed a threshold $\tau$. The aggregation problem is formulated as minimizing the sum of TQ losses over client updates.
3. Optimization and Implementation: Since the TQ loss is non-smooth and non-convex, the authors use convex conjugate theory to recast the minimization problem into an equivalent iterative form (Algorithm 1). This allows for efficient computation where updates are clipped based on the distance from the current aggregate.
4. Hyperparameter Estimation: The TQ rule requires a threshold parameter $\tau_k$ and knowledge of the number of Byzantine clients ($f$). The paper proposes a robust deviation estimation strategy using the Median and Median Absolute Deviation (MAD) to estimate the mean and variance of good clients without prior knowledge. Additionally, the authors analyze the scenario where only an estimate of the number of Byzantine clients ($\hat{f}$) is available, showing that the aggregator remains robust even if $\hat{f}$ is an overestimate (up to the breakdown point).
5. FL Algorithm Integration: The TQ aggregator is integrated into a Byzantine-robust FL framework (Algorithm 2) utilizing momentum to reduce gradient variance and combat time-coupled attacks.

Key Contributions

• Equivalence and Bias Analysis: The paper formally establishes the equivalence between Huber loss and Centered Clipping via convex conjugate theory. It provides a theoretical analysis showing that both methods produce biased solutions under heterogeneity and outliers, explaining their empirical failures.
• TQ Aggregator: The authors propose the TQ-based aggregator, which effectively mitigates the bias of existing methods by completely clipping large-magnitude outliers.
• Robustness Guarantees: The paper proves that the TQ aggregator satisfies $(f, \kappa)$-robustness with a breakdown point $\delta_{min} = 0.5$. It demonstrates that TQ achieves order-optimal Byzantine-robust learning under nonconvex loss functions and heterogeneous data.
• Practical Estimation Strategies: A robust deviation estimation strategy is provided for the TQ hyperparameter, and the paper analyzes the impact of estimating the number of Byzantine clients, showing that the method remains effective even with imperfect estimates.

Experimental Results
The proposed TQ aggregator was evaluated on MNIST, Fashion-MNIST, and CIFAR-10 datasets under various conditions:

• Attack Types: Performance was tested against six distinct attacks: Gaussian Attack (GA), Label-Flipping (LF), Bit-Flipping (BF), Inner Product Manipulation (IPM), MIMIC, and "A Little Is Enough" (ALIE).
• Heterogeneity: Experiments covered varying degrees of data heterogeneity ($\rho$).
• Comparisons: TQ was compared against RFA, CM, TM, Krum, Huber, and Maximum Correntropy Aggregation (MCA), both with and without pre-aggregation steps like Bucketing and Nearest Neighbor Mixing (NNM).

Findings:

• Superior Robustness: TQ consistently outperformed competing aggregators, particularly under high data heterogeneity and high fractions of Byzantine clients (up to 50%).
• Bias Mitigation: Unlike Huber and CC, which showed significant performance degradation and bias accumulation as the number of Byzantine clients increased, TQ maintained high accuracy.
• Mixed Attacks: In scenarios where different Byzantine clients launched different types of attacks simultaneously, TQ significantly outperformed other methods across varying heterogeneity levels.
• Estimation Robustness: The results indicated that TQ maintains robustness even when the number of Byzantine clients is estimated rather than known exactly.

Significance and Claims
The paper claims that the proposed TQ aggregator enhances the reliability of federated learning systems by addressing the specific failure modes of current state-of-the-art methods under data heterogeneity. By proving that TQ achieves order-optimal learning error (aligning with the theoretical lower bound described in Lemma 2), the authors argue that their method represents a significant step forward in Byzantine-robust FL. The work provides both theoretical justification for the failure of Huber/CC in heterogeneous settings and a practical, robust alternative that does not require precise knowledge of the number of malicious clients.