Abstract
Distributed learning systems are increasingly vulnerable to adversarial attacks, leading to the widespread adoption of "robust" aggregators designed to filter out malicious updates. This paper challenges the conventional wisdom that these robust tools are always superior. Focusing on label poisoning attacks—where malicious workers flip labels rather than sending arbitrary values—we demonstrate that the simple mean aggregator often outperforms sophisticated alternatives like Trimmed Mean, FABA, or Centered Clipping. This is especially true in heterogeneous (non-i.i.d.) settings, where robust aggregators struggle to distinguish between malicious noise and legitimate, unique data. Our theoretical analysis and empirical results on MNIST and CIFAR-10 show that the mean aggregator is not only more accurate in many practical scenarios but also more stable as the proportion of compromised workers grows.
Introduction
Distributed learning relies on a central server to aggregate gradients from multiple workers. While efficient, this architecture is susceptible to Byzantine attacks, where malicious nodes send arbitrary, often extreme, data to disrupt the model. To counter this, researchers have developed robust aggregators (e.g., Trimmed Mean, Median, Centered Clipping) that attempt to identify and discard outliers to find the "true" update.
However, many real-world attacks are more subtle and structured. Label poisoning, where an attacker flips labels (e.g., changing "spam" to "non-spam"), represents a practical data-level attack. This paper investigates a surprising gap: robust aggregators are often too conservative for these attacks. In reality, when the data across workers is highly diverse (heterogeneous), robust aggregators cannot distinguish between a "malicious" update and a "legitimate but unique" update, leading them to perform worse than a simple average.
Theoretical Framework
The authors provide a rigorous theoretical comparison between the mean aggregator and state-of-the-art robust defenses. A critical contribution is the formalization of label poisoning disturbances. Unlike arbitrary Byzantine noise, poisoned gradients in models like softmax regression are bounded by the scale of input features. This is formalized in Assumption 4 (Bounded Disturbances), which proves that the "poisoned" gradient isn't infinitely bad.
The analysis shows that the learning error of the mean aggregator is $O(\delta^2 \xi^2)$, where $\delta$ is the fraction of poisoned workers and $\xi$ represents data heterogeneity. In contrast, robust aggregators like Centered Clipping exhibit higher error terms ($O(\delta \xi^2)$). Furthermore, sophisticated aggregators like TriMean and FABA have error terms that "explode" (go to infinity) as the percentage of poisoned workers approaches certain thresholds (like 33% or 50%). The mean aggregator, by contrast, is insensitive to these thresholds and degrades gracefully.
Empirical Performance
The theory was validated using MNIST and CIFAR-10 benchmarks under varying degrees of data distribution, from perfectly uniform (IID) to highly heterogeneous (Non-IID). Two attack types were simulated:
- Static Label Flipping: Labels are flipped according to a fixed rule (e.g., 0 becomes 9).
- Dynamic Label Flipping: Labels are flipped to the "least probable" class based on the current model, making the attack more adaptive.
As shown in the experimental results above, the mean aggregator consistently maintains higher classification accuracy than TriMean, FABA, and Centered Clipping in highly heterogeneous environments. In these settings, robust aggregators mistakenly discard valuable, unique updates from legitimate workers, treating them as malicious outliers. This confirms that "robustness" is relative; in non-IID settings, a worker with unique, valid data looks like an outlier, and robust aggregators accidentally throw away this valuable information.
The "Sweet Spot" for the Mean
The relative performance of the mean versus robust aggregators depends on the interplay between attack strength (flipping probability $p$) and data heterogeneity (Dirichlet distribution $\alpha$).
This "sweet spot" is illustrated in the heatmap. As data becomes more heterogeneous (moving right on the x-axis) or the attack remains moderate, the mean aggregator (orange) becomes the superior choice. Robust aggregators only maintain an edge in highly homogeneous settings with extreme poisoning. This suggests that if you know your system is facing data-level poisoning rather than arbitrary network-level "garbage" injection, you are likely better off sticking with the simple mean.
Conclusion
This research suggests a paradigm shift in distributed learning security. The findings indicate that the simple mean aggregator is not just a baseline but a powerful, resilient tool against practical label poisoning attacks, especially in the non-IID environments typical of real-world federated learning. Future work will aim to extend these deterministic theoretical bounds to stochastic settings and explore these dynamics in decentralized, peer-to-peer architectures.
Summary updated