LiD-FL: Towards List-Decodable Federated Learning

Hong Liu, Liren Shan, Han Bao, Ronghui You, Yuhao Yi, Jiancheng Lv

TL;DR

LiD-FL introduces a "list-decodable" framework for federated learning that remains robust even when the vast majority of participants (up to 80% in experiments) are malicious. By maintaining a small list of candidate models rather than a single global one, the server ensures that at least one "honest" model survives the noise and sabotage of a Byzantine majority.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple clients to train a model collectively without sharing their raw data. However, this openness makes it vulnerable to Byzantine attacks, where malicious clients send poisoned updates to collapse the model or install backdoors.

Most existing "Byzantine-robust" algorithms have a fundamental breaking point: they fail if more than 50% of the clients are malicious. In the real world, attackers can use Sybil attacks to create thousands of fake identities, easily outnumbering honest users. While some recent work has pushed past this 50% limit, those methods usually require the server to hold a "clean" validation dataset, which is often impossible in privacy-sensitive applications. LiD-FL tackles the "malicious majority" problem without requiring the server to have its own data.

Methods

The authors propose LiD-FL (List-Decodable Federated Learning), which draws inspiration from error-correcting codes. Instead of trying to find one perfect model in a sea of lies, the server maintains a list of $q$ models.

The algorithm operates in two main phases:

  1. Randomized Update: In each round, the server randomly picks one model from its list and one client from the pool. The client performs local training and sends back an update. Because the server only picks one client, there is a constant probability ($\gamma$, the fraction of honest clients) that the update is "clean."
  2. Voting & Pruning: The server broadcasts the updated list to all clients. Honest clients act as a "validation oracle," testing the models on their local data and voting for the one with the lowest loss. The server then discards the model that received the fewest votes.

The key insight is that as long as the list size $q$ is large enough ($q \ge 1/\gamma$), the voting process ensures that at least one valid, unpoisoned model is preserved in the list at all times.

Datasets

The researchers evaluated LiD-FL using two standard computer vision benchmarks:

  • FEMNIST (Federated Extended MNIST): A dataset of handwritten characters and digits. They tested both a simple Logistic Regression (LR) model and a Convolutional Neural Network (CNN).
  • CIFAR-10: A popular dataset of 60,000 color images across 10 classes, using a CNN architecture.

To simulate real-world conditions, they used an "imbalanced" data distribution where different clients held different amounts of data.

Key Insights and Ideas

  • The Power of the List: In a majority-malicious setting, a single aggregated update is almost certainly poisoned. By maintaining a list, the algorithm doesn't need to identify the "truth" immediately; it just needs to ensure the truth stays "on the menu."
  • Redefining the Breaking Point: Standard aggregators (like Coordinate-wise Median or Trimmed Mean) collapse when honest clients are in the minority. LiD-FL proves that you can achieve convergence regardless of the malicious fraction, provided you know a lower bound for the number of honest clients.
  • Validation Oracles: The paper assumes clients can accurately estimate loss on their local data. This shifts the burden of verification from the server (which has no data) to the clients (who do).
  • List Decoding as a Defense: This is a clever cross-pollination of ideas from coding theory and distributed optimization, showing that "list-decodable" learning is a viable path for extreme adversarial environments.

Key Results

The authors tested LiD-FL against six different types of attacks (including label flipping and sophisticated "Omniscient" attacks) at Byzantine fractions of 0.4, 0.6, and 0.8.

  • Resilience to Malicious Majorities: When 60% of clients were malicious, all baseline methods (FedAvg, GM, Norm, CWM) collapsed, often yielding accuracies near 0-5%. In contrast, LiD-FL maintained 72-73% accuracy on FEMNIST-CNN.
  • Extreme Scenarios: Even at an 80% malicious rate, LiD-FL achieved roughly 50-70% accuracy across various models, while baselines remained completely broken.
  • Stability: The experiments showed that larger list sizes lead to better stability and smaller standard deviations in accuracy across different training runs.

Limitations and Future Work

While LiD-FL is a significant step forward, the authors and the architecture suggest a few hurdles:

  • Efficiency: The current version samples only one client per round to ensure a clean update probability. This doesn't take advantage of the parallel computing power of the thousands of clients typically available in FL.
  • Data Heterogeneity: The theoretical convergence proof assumes "i.i.d." (independent and identically distributed) data. In reality, FL data is usually highly non-i.i.d. (heterogeneous), which might complicate the voting process.
  • Non-Convex Theory: While the experiments on CNNs (non-convex) were successful, the formal convergence proof is currently limited to strongly convex and smooth loss functions.
  • Future Directions: The authors suggest integrating "robust aggregation rules" into the list-generation process to improve efficiency and exploring how the framework handles highly heterogeneous data.

Summary updated

Abstract

Federated learning is often used in environments with many unverified participants. Therefore, federated learning under adversarial attacks receives significant attention. This paper proposes an algorithmic framework for list-decodable federated learning, where a central server maintains a list of models, with at least one guaranteed to perform well. The framework has no strict restriction on the fraction of honest workers, extending the applicability of Byzantine federated learning to the scenario with more than half adversaries. Under proper assumptions on the loss function, we prove a convergence theorem for our method. Experimental results, including image classification tasks with both convex and non-convex losses, demonstrate that the proposed algorithm can withstand the malicious majority under various attacks.
BibTeX
@inproceedings{liu2025lid,
  author = {Hong Liu and Liren Shan and Han Bao and Ronghui You and Yuhao Yi and Jiancheng Lv},
  title = {{LiD-FL: Towards List-Decodable Federated Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i18.34072},
}
Figure