Prox-DBRO-VR: A Unified Analysis on Byzantine-Resilient Decentralized Stochastic Composite Optimization With Variance Reduction and Nonasymptotic Convergence Rates
针对多智能体系统中存在未知数量拜占庭故障智能体的问题，提出了一种拜占庭鲁棒的去中心化随机近端梯度算法框架Prox-DBRO-VR，并融入两种局部方差缩减技术，证明了算法在常步长和衰减步长下的线性与次线性收敛性，适用于解决去中心化稀疏机器学习问题。
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.