Prox-DBRO-VR: A Unified Analysis on Byzantine-Resilient Decentralized Stochastic Composite Optimization with Variance Reduction and Non-Asymptotic Convergence Rates
For multi-agent systems facing Byzantine failures, this work provides a unified theoretical analysis and practical algorithms for resilient decentralized optimization with provable convergence guarantees.
This paper proposes a Byzantine-resilient decentralized stochastic proximal-gradient algorithm (Prox-DBRO-VR) for composite optimization, incorporating variance reduction techniques (SAGA and LSVRG). The algorithms achieve linear convergence with constant step-size and sub-linear convergence with decaying step-size to an error ball around the optimum, demonstrated on a decentralized sparse machine-learning problem under Byzantine attacks.
Decentralized stochastic gradient algorithms efficiently solve large-scale finite-sum optimization problems when all agents in the network are reliable. However, most of these algorithms are not resilient to adverse conditions, such as malfunctioning agents, software bugs, and cyber attacks. This paper aims to handle a class of general composite optimization problems over multi-agent systems (MASs) in the presence of an unknown number of Byzantine agents. Building on a resilient aggregation mechanism and the proximal-gradient mapping method, a Byzantine-resilient decentralized stochastic proximal-gradient algorithmic framework is proposed, dubbed Prox-DBRO-VR, which achieves an optimization and control goal using only local computations and communications. To asymptotically reduce the noise variance arising from local gradient estimation and accelerate the convergence, we incorporate two localized variance-reduced (VR) techniques (SAGA and LSVRG) into Prox-DBRO-VR to design Prox-DBRO-SAGA and Prox-DBRO-LSVRG. By analyzing the contraction relationships among the gradient-learning error, resilient consensus condition, and convergence error in a unified theoretical framework, it is proved that both Prox-DBRO-SAGA and Prox-DBRO-LSVRG, with a well-designed constant (resp., decaying) step-size, converge linearly (resp., sub-linearly) inside an error ball around the optimal solution to the original problem under standard assumptions. A trade-off between convergence accuracy and Byzantine resilience in both linear and sub-linear cases is also characterized. In numerical experiments, the effectiveness and practicability of the proposed algorithms are manifested via resolving a decentralized sparse machine-learning problem under various Byzantine attacks.