Abstract
This work presents a new distributed Byzantine tolerant federated learning algorithm, HoldOut SGD, for Stochastic Gradient Descent (SGD) optimization. HoldOut SGD uses the well known machine learning technique of holdout estimation, in a distributed fashion, in order to select parameter updates that are likely to lead to models with low loss values. This makes it more effective at discarding Byzantine workers inputs than existing methods that eliminate outliers in the parameter-space of the learned model. HoldOut SGD first randomly selects a set of workers that use their private data in order to propose gradient updates. Next, a voting committee of workers is randomly selected, and each voter uses its private data as holdout data, in order to select the best proposals via a voting scheme. We propose two possible mechanisms for the coordination of workers in the distributed computation of HoldOut SGD. The first uses a truthful central server and corresponds to the typical setting of current federated learning. The second is fully distributed and requires no central server, paving the way to fully decentralized federated learning. The fully distributed version implements HoldOut SGD via ideas from the blockchain domain, and specifically the Algorand committee selection and consensus processes. We provide formal guarantees for the HoldOut SGD process in terms of its convergence to the optimal model, and its level of resilience to the fraction of Byzantine workers. Empirical evaluation shows that HoldOut SGD is Byzantine-resilient and efficiently converges to an effectual model for deep-learning tasks, as long as the total number of participating workers is large and the fraction of Byzantine workers is less than half (<1/3 for the fully distributed variant).
Introduction
Federated Learning (FL) has emerged as a powerful paradigm for training machine learning models across distributed devices while preserving data privacy. However, the open nature of these systems introduces a significant security vulnerability: Byzantine workers. These participants may submit malicious or "poisoned" updates—due to hardware failure or adversarial intent—to prevent model convergence or degrade accuracy.
Traditional defenses against Byzantine attacks typically rely on geometric outlier detection, filtering out updates that appear mathematically distant from the average. However, sophisticated attackers can craft subtle perturbations that remain within the expected geometric distribution while still successfully poisoning the model. This paper introduces HoldOut SGD, a novel approach that shifts the defense mechanism from geometric analysis to empirical utility.
The HoldOut SGD Framework
HoldOut SGD adapts the classic concept of "holdout validation" to a distributed environment. Rather than evaluating an update based on its position in a high-dimensional parameter space, HoldOut SGD evaluates an update based on its actual impact on the model's loss function.
The process operates in iterative rounds consisting of four primary stages:
- Proposer Selection: A random subset of workers is chosen to calculate gradient updates based on their local, private datasets.
- Committee Selection: A separate, disjoint subset of workers is randomly selected to serve as a voting committee.
- Holdout Evaluation: Committee members receive the proposed updates and test them against their own private data (acting as a holdout set). They calculate the resulting loss for each proposed update.
- Voting and Aggregation: Committee members vote for the top-performing updates—those that most effectively lower the loss. The system then aggregates only those updates that receive a majority of votes.
Coordination Models
The researchers propose two distinct implementations for HoldOut SGD:
- Semi-Distributed: This version utilizes a trusted central server to coordinate the voting process and aggregate the successful updates, fitting the standard architecture of modern federated learning.
- Fully Decentralized: This version removes the need for a central authority by employing blockchain-inspired techniques. By utilizing Verifiable Random Functions (VRFs) and consensus mechanisms from the Algorand protocol, the system can securely select committees and reach consensus in a peer-to-peer fashion.
Empirical Evaluation and Results
The effectiveness of HoldOut SGD was tested using the MNIST and CIFAR-10 datasets, simulating a pool of 100 nodes where up to 33% were Byzantine attackers using sophisticated "margin of poisoning" attacks.
- Superior Robustness: On the MNIST dataset, HoldOut SGD maintained high accuracy even under heavy attack. In contrast, the popular Krum algorithm failed, experiencing a 50% drop in accuracy.
- Deep Learning Performance: On the more complex CIFAR-10 task, HoldOut SGD significantly outperformed both Trimmed-Mean and Krum. While those methods saw accuracy plummet by 50-65%, HoldOut SGD only experienced a modest ~15% decrease.
- Efficiency: In environments without attackers, HoldOut SGD performs comparably to standard SGD, demonstrating that the added security does not come at the cost of baseline performance.
Theoretical Guarantees and Limitations
The paper provides formal proofs showing that HoldOut SGD converges to an optimal model as long as the fraction of Byzantine workers ($f$) remains below 0.5 for the server-based version and below 1/3 for the decentralized version.
While the empirical results are promising for non-convex deep learning tasks, the current theoretical convergence proofs assume a convex loss function. Additionally, while the system is robust against poisoning, the authors note that "backdoor attacks"—where an adversary targets a specific, rare trigger—were not part of this study. Future work will also need to address the communication overhead inherent in the decentralized version's message-passing requirements.
Conclusion
HoldOut SGD represents a significant step forward in Byzantine-tolerant federated learning. By prioritizing the utility of updates over their geometric properties and utilizing randomized committees, it provides a robust defense against sophisticated adversarial attacks in both centralized and fully decentralized environments.
Summary updated