Abstract
Distributed learning systems are increasingly vulnerable to Byzantine attacks, where malicious workers send arbitrary messages to bias the learning process. This paper presents a Byzantine-robust stochastic Alternating Direction Method of Multipliers (ADMM) based on a Total Variation (TV) norm-penalized approximation. By leveraging the separable structure of the problem, the proposed method achieves an $O(1/k)$ convergence rate to a bounded neighborhood of the optimal solution. Numerical experiments on MNIST and COVERTYPE datasets demonstrate superior performance compared to existing subgradient-based methods, particularly in non-i.i.d. settings.
Introduction
In distributed machine learning, a central master node coordinates multiple worker nodes to solve a global optimization problem. Standard algorithms assume all workers are honest; however, hardware failures, data corruption, or malicious attacks can introduce "Byzantine" behavior. Byzantine workers can send arbitrary updates, potentially leading to model divergence. While robust aggregation techniques like the geometric median exist, they often struggle with non-i.i.d. data distributions common in federated learning. This work addresses these challenges by introducing a robust stochastic ADMM framework.
Problem Formulation
The objective is to minimize a global loss function $f(w) = \sum_{i=1}^n f_i(w)$, where $n$ is the number of workers. In a Byzantine environment, a subset of workers $\mathcal{B}$ is malicious, while the rest $\mathcal{R}$ are regular. To handle this, we employ a Total Variation (TV) norm-penalized approximation: $$\min_{\{w_i\}, z} \sum_{i \in \mathcal{R} \cup \mathcal{B}} f_i(w_i) + \lambda \sum_{i=1}^n \|w_i - z\|_1$$ Here, $z$ represents the global model at the master, and $w_i$ are local models. The $L_1$-style TV penalty forces regular workers' models to stay close to the global consensus while providing the sparsity needed to tolerate extreme outliers from Byzantine workers.
The Proposed Stochastic ADMM
Unlike previous methods like Robust Stochastic Aggregation (RSA) that rely on subgradients, our approach utilizes the ADMM framework to exploit the problem's separable structure.
Algorithm Design
We introduce auxiliary variables to decouple local loss functions from global constraints. The ADMM updates involve:
- Local Primal Update: Workers update their local models $w_i$ using a stochastic gradient step.
- Global Primal Update: The master updates the global model $z$ by aggregating local models.
- Dual Update: Dual variables are updated to enforce consensus.
A key innovation is the simplification of these steps, ensuring that the communication and computation costs remain equivalent to simpler subgradient methods like SGD, despite the added robustness of the ADMM framework.
Theoretical Analysis
The paper establishes that the proposed stochastic ADMM converges at a rate of $O(1/k)$ under mild assumptions (e.g., strong convexity of local losses). The algorithm converges to a neighborhood of the optimal solution, where the size of the neighborhood is proportional to the number of Byzantine workers. This provides a formal guarantee of stability even under persistent attack. The use of a projection operator on dual variables makes the algorithm significantly less sensitive to small, "sneaky" perturbations from attackers compared to sign-function-based methods.
Experimental Evaluation
The algorithm was tested on the MNIST and COVERTYPE datasets under various attack scenarios, including Gaussian noise and sign-flipping attacks (where attackers send the negative of the true update).
Key Findings
- Efficiency: On the COVERTYPE dataset, Stochastic ADMM converged significantly faster than RSA and other robust benchmarks.
- Robustness: Under sign-flipping attacks on MNIST, the proposed method maintained high accuracy, whereas standard SGD failed to converge entirely.
- Non-i.i.d. Resilience: In scenarios where data was partitioned by class (non-i.i.d.), the ADMM approach outperformed RSA in both speed and final accuracy, demonstrating its ability to distinguish between legitimate data heterogeneity and malicious outliers.
Conclusion
The Byzantine-robust stochastic ADMM offers a powerful solution for secure distributed learning. By combining the stability of primal-dual methods with the robustness of TV-norm penalties, it provides a scalable and efficient algorithm capable of handling both malicious attacks and non-i.i.d. data distributions. Future work includes extending these guarantees to non-convex loss functions and optimizing the selection of the penalty parameter $\lambda$.
Summary updated