Projected Penalty-Gradient Tracking for Communication-Efficient Byzantine-Resilient Federated Learning

Yanjie DongarXiv 2026 · arXiv

TL;DR

This paper introduces a new framework for Federated Learning (FL) that remains robust against malicious "Byzantine" workers while significantly reducing communication overhead through data compression. By projecting accumulated worker states onto a bounded "penalty-gradient ball" at the server, the authors ensure that malicious updates cannot grow unbounded, even when using lossy compression techniques.

What Problem Does This Paper Address?

Federated Learning faces two massive hurdles when deployed in the real world: Byzantine attacks and communication bottlenecks.

  1. Byzantine Attacks: Malicious workers can upload arbitrary, harmful data to derail the global model. While "penalty-based" methods (like RSA or FRPG) naturally limit a worker's influence by bounding their gradients, these defenses often break down when communication is compressed.
  2. Communication Bottlenecks: Large models require massive bandwidth. To save time, researchers use compression (like sparsification). However, standard compression algorithms use "error feedback"—they store the difference between the true update and the compressed one. A Byzantine worker can exploit this stored state at the server to slowly accumulate a massive, harmful influence that bypasses the original penalty bounds.

The authors aim to bridge this gap, creating a system that is both communication-efficient and provably resilient to attackers, even when data is heterogeneous (non-i.i.d.).

Methods

The core innovation is the Projected Penalty-Gradient Tracking framework. Instead of just projecting the incoming message, the server tracks each worker's state and projects the accumulated state onto a known penalty-gradient ball. This ensures the influence of any worker remains bounded, regardless of what they actually upload.

The paper introduces two specific algorithms within this framework:

  • FRPG-CS (Consistent Sparsification): Workers share a communication mask. To prevent attackers from manipulating which features are sent, the server combines robustly ranked features (using a trimmed mean) with "reserve rows"—randomly selected features that guarantee the compression remains effective even under adversarial manipulation.
  • LAG-FRPG (Lazy Aggregation): An event-triggered approach where honest workers only upload their updates if the change since their last upload exceeds a specific, decaying threshold.

Datasets

The authors evaluated their methods using 10-class linear softmax regression on two classic computer vision benchmarks:

  • MNIST: Handwritten digits.
  • Fashion-MNIST: Images of clothing items.

They compared their approach against ten established benchmarks, including Krum, Geometric Median, and Byz-EF21-SGDM, across various attack scenarios like Min-Max, IPM, and ALIE attacks.

Key Insights and Ideas

  • State Projection is Essential: The "aha moment" is realizing that in compressed FL, the server-side state is the vulnerability. By projecting the state itself, the server regains a "hard limit" on how much any single worker can move the global model.
  • The Power of Reserve Rows: In sparsification, if you only send the "top-k" most important values, an attacker can trick the system into ignoring important updates. Adding a small set of random "reserve" features ensures that honest updates eventually get through, maintaining a mathematical property called "contraction."
  • Decoupled Error Floors: A major theoretical finding is that the "Byzantine error floor" (the minimum error caused by attackers) is independent of the compression factor. This means you can compress heavily to save bandwidth without making the system more vulnerable to attacks.

Key Results

The proposed algorithms demonstrated superior resilience, particularly under the sophisticated Min-Max attack.

  • Accuracy: On the MNIST dataset under a Min-Max attack, FRPG-CS achieved 88.46% accuracy, outperforming the best benchmark (Projected FRPG at 85.97%) by nearly 2.5 percentage points.
  • Robustness: As seen in Figure 1, the test cross-entropy for FRPG-CS and LAG-FRPG remains stable and low under attack, whereas many traditional robust aggregation methods (like Krum or Trimmed Mean) see significant performance degradation.
  • Efficiency: LAG-FRPG significantly reduced communication frequency, with the fraction of active uploading slots decaying at a rate of $O(\sqrt{\ln K/K})$.

![Fig.

  1. Test cross-entropy (log scale) versus oracle slots for all twelve methods in the attack-free and Min-Max scenarios.](/figures/art_1c8114771ca647439f48eabded289a0c)
Table I: Test accuracy comparison across different methods and scenarios.

Limitations and Future Work

  • Convexity Requirements: The current theoretical proofs rely on the loss functions being smooth and strongly convex. This covers linear models and logistic regression but does not yet formally extend to deep neural networks with non-convex landscapes.
  • Trusted Server: The framework assumes the central server is honest and follows the protocol.
  • Future Directions: The authors suggest extending the framework to handle non-convex losses, implementing downlink compression (server-to-worker), and testing against even more aggressive, protocol-specific attacks.

Summary updated

Abstract

We investigate communication-efficient federated learning over heterogeneous datasets in the presence of Byzantine adversaries capable of uploading arbitrary information. Penalty-based methods bound the influence of each worker through the bounded gradient of a penalty function; however, the bound is lost once the uploads are compressed, since a Byzantine worker can accumulate an unbounded state at the server. To retain the Byzantine resilience under compressed uploads, we propose a projected penalty-gradient tracking framework, where each honest worker uploads a compressed residual of its penalty gradient and the server projects each reconstructed state onto the known penalty-gradient ball. The framework accommodates any contractive compressor and yields two algorithms: fault-resilient proximal gradient with consistent sparsification (FRPG-CS), whose shared mask is protected by freshly drawn reserve rows, and lazily aggregated FRPG (LAG-FRPG), whose uploads are event-triggered. For smooth and strongly convex losses, we establish a finite-time bound on the expected objective gap, where the Byzantine error floor is independent of the compressor and the compression error decays faster than the optimization error. We also bound the expected number of lazy uploads and derive certificates that separate the finite-penalty model bias from the optimization error. Experiments on MNIST and Fashion-MNIST show that the proposed algorithms attain the highest accuracy among twelve methods under the Min-Max attack, whereas a compressed-momentum benchmark and a local-update benchmark remain preferable in attack-free accuracy and total traffic, respectively.
BibTeX
@misc{dong2026projected,
  author = {Yanjie Dong},
  title = {{Projected Penalty-Gradient Tracking for Communication-Efficient Byzantine-Resilient Federated Learning}},
  year = {2026},
  eprint = {2611.22929},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22929},
}
Figure