Byzantine Fault-Tolerance in Federated Local SGD Under $2f$-Redundancy
Nirupam Gupta, Thinh T. Doan, Nitin H. Vaidya · IEEE Transactions on Control of Network Systems · 2023
In this article, we study the problem of Byzantine fault-tolerance in a federated optimization setting, where there is a group of agents communicating with a centralized coordinator. We allow up to$f$Byzantine-faulty agents, which may not follow a prescribed algorithm correctly, and may share arbitrarily incorrect information with the coordinator. Associated with each nonfaulty agent is a local cost function. The goal of the nonfaulty agents is to compute a minimizer of their aggregate cost function. For solving this problem, we propose a local gradient-descent algorithm that incorporates a novelcomparative eliminationfilter (aka. aggregation scheme) to provably mitigate the detrimental impact of Byzantine faults. In the deterministic setting, when the agents can compute their local gradients accurately, our algorithm guaranteesexactfault-tolerance against a bounded fraction of Byzantine agents, provided the nonfaulty agents satisfy the known necessary condition of$2f$-redundancy. In the stochastic setting, when the agents can only compute stochastic estimates of their gradients, our algorithm guaranteesapproximatefault-tolerance where the approximation error is proportional to the variance of stochastic gradients and the fraction of Byzantine agents.