Byzantine-Robust Decentralized Stochastic Optimization

In this paper, we consider the Byzantine-robust stochastic optimization problem defined over a decentralized network, where the agents collaboratively minimize the summation of expectations of stochastic local cost functions, but some of the agents are unreliable. Due to data corruptions, equipment failures or cyber-attacks, these Byzantine agents can send faulty values to their neighbors and bias the optimization process. Our key idea to handle the Byzantine attacks is to formulate a total variation (TV) norm-penalized approximation of the Byzantine-free problem, where the penalty term forces the local models of regular agents to be close, but also allows the existence of outliers from the Byzantine agents. A stochastic subgradient method is applied to solve the penalized problem. We prove that the proposed method converges to a near-optimal solution of the Byzantine-free problem under mild assumptions, and the gap is determined by the number of Byzantine agents and the network topology. Numerical experiments corroborate the theoretical analysis, as well as demonstrate the robustness of proposed method to Byzantine attacks and its superior performance over existing methods.