<i>Prox-DBRO-VR</i>: A Unified Analysis on Byzantine-Resilient Decentralized Stochastic Composite Optimization With Variance Reduction and Nonasymptotic Convergence Rates

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 article aims to handle a class of general composite optimization problems over multiagent 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-VR</i>, 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 (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SAGA</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">LSVRG</i>) into <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-VR</i> to design <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-SAGA</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-LSVRG</i>. 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-SAGA</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Prox-DBRO-LSVRG</i>, with a well-designed constant (resp., decaying) step-size, converge linearly (resp., sublinearly) inside an error ball around the optimal solution to the original problem under standard assumptions. A tradeoff between convergence accuracy and Byzantine resilience in both linear and sublinear 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.