Byzantine-Robust Federated Representation Learning

Leonardo F. Toso, James Anderson, Rafael Pinot, Nirupam GuptaarXiv 2026 · arXiv

TL;DR

This paper tackles the "heterogeneity bottleneck" in Byzantine-robust federated learning by separating a shared nonlinear representation from personalized linear heads for each client. By doing so, the authors provide the first non-asymptotic guarantees for robust representation learning that eliminate the irreducible "heterogeneity bias" typically found in standard robust federated learning.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple clients to train a model collaboratively without sharing their raw data. However, two major hurdles often collide: heterogeneity (clients have very different data distributions) and Byzantine attacks (malicious clients sending arbitrary updates to corrupt the model).

Standard Byzantine-robust FL methods try to learn a single global model. The problem is that under heterogeneity, even "honest" updates look very different from one another. Robust aggregators—designed to filter out outliers—struggle to distinguish between a malicious update and an honest client who simply has unique data. This confusion leads to an "irreducible model-heterogeneity bias," meaning the model remains inaccurate even with infinite data. The authors ask: Should we instead separate what is shared from what is specific to each client?

Methods

The authors propose a framework for Adversarially Robust Nonlinear Representation Learning. Instead of one global model, the architecture is split:

  1. Shared Nonlinear Representation ($\phi_B$): A complex backbone (like a neural network) that extracts features, shared by all clients.
  2. Personalized Linear Heads ($h_i$): A simple linear layer unique to each client that maps features to specific outputs.

The training follows an alternating minimization approach:

  • Local Head Estimation: Each client first fits its own personalized linear head using a local batch of data while keeping the shared representation fixed.
  • Robust Representation Update: Clients then compute gradients for the shared representation parameter ($B$) using a second, independent batch of data. These updates are sent to the server.
  • Robust Aggregation: The server uses a $(f, \kappa)$-robust aggregator (such as Krum, Geometric Median, or Trimmed Mean) to combine these updates while filtering out potential Byzantine interference.

The core innovation is theoretical: they prove that after fitting personalized heads, the remaining diversity in honest gradients is governed only by estimation noise and representation error—not by the inherent differences in client data.

Datasets

The authors validated their approach on three heterogeneous datasets:

  • CIFAR-10: Partitioned such that each client only sees examples from two specific classes (highly non-IID).
  • FEMNIST: A character recognition dataset that uses a natural writer-based partition to maintain real-world heterogeneity.
  • School Exam Score: A regression dataset where each of the 139 schools acts as a client, predicting exam scores based on student features.

Key Insights and Ideas

  • Breaking the Curse of Heterogeneity: The "aha moment" is that personalization isn't just a feature for better user experience; it's a mathematical necessity for robustness. By letting clients "absorb" their local quirks into the linear head, the updates for the shared backbone become much more aligned across honest clients.
  • Endogenous Heterogeneity: In their analysis, gradient heterogeneity becomes "endogenous"—it naturally shrinks as the representation improves. This allows the error bounds to decay with the number of communication rounds ($T$) and samples per client ($\tau$).
  • Classification via Regression: The paper demonstrates that their nonlinear regression guarantees can be transferred to multiclass classification. Under a "margin condition" (where the correct class is sufficiently separated from others), the classification error inherits the same favorable convergence rates.

Key Results

The empirical results show massive improvements over standard "common-model" Byzantine-robust baselines:

  • Accuracy Boost: On CIFAR-10, representation learning improved accuracy by 38.3–42.1 percentage points under attack. On FEMNIST, the improvement was 18.9–22.1 points.
  • Attack Resilience: The method remained stable against sophisticated attacks like ALIE ("A Little Is Enough") and Mimic attacks, where attackers try to blend in by copying honest updates.
  • Regression Performance: On the School Exam dataset, the proposed method reduced Mean Squared Error (MSE) by up to 17.7% compared to the baseline, outperforming both pooled and per-school mean predictors.

Limitations and Future Work

  • Exact Head Estimation: The current theoretical analysis assumes that clients can solve the local head estimation exactly (Empirical Risk Minimization). In practice, clients might only perform a few steps of SGD, which could introduce additional local estimation errors not yet fully captured in the bounds.
  • Robustness Coefficient Constraints: The theory requires the robustness coefficient $\kappa$ (related to the fraction of Byzantine clients) to be relatively small. The authors note that recent work in simpler settings suggests this might be an analytical artifact rather than a fundamental limit, and they suggest exploring this as future work.
  • Communication Efficiency: While the method is robust, it still requires many rounds of communication. Future research could look into combining this robust representation learning with communication-compression techniques.

Summary updated

Abstract

We study federated learning (FL) with adversarial clients, where the goal is to minimize the average loss of the honest (non-adversarial) clients without knowing their identity. Under heterogeneity, a single shared model parameter is statistically inappropriate: it cannot capture the distinct data-generating processes across clients, incurring an irreducible model-heterogeneity bias and severely limiting robustness to adversarial clients (a.k.a. Byzantine-robustness). We address this problem through representation learning, where each client learns a personalized linear head, while collaboratively estimating a shared nonlinear representation through Byzantine-robust aggregation. We demonstrate that the heterogeneity among honest representation gradients is controlled by the representation error and statistical errors that decay either with the number of data samples per client ($τ$) or the number of iterations ($T$). In particular, our non-asymptotic parameter recovery error bound reveals three terms: (i) an initialization-dependent error that goes away with $T$, (ii) finite-sample noise terms that decreases with $τ$ and the number of honest clients, and (iii) a stochastic gradient variance term that also reduces with $T$. Importantly, with no irreducible model-heterogeneity bias in our bounds. We extend the regression analysis to multiclass classification, and empirically validate it on CIFAR-10, FEMNIST, and School Exam Score datasets.
BibTeX
@misc{toso2026byzantine,
  author = {Leonardo F. Toso and James Anderson and Rafael Pinot and Nirupam Gupta},
  title = {{Byzantine-Robust Federated Representation Learning}},
  year = {2026},
  eprint = {2609.36660},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36660},
}
Figure