Online Multi-Agent Decentralized Byzantine-robust Gradient Estimation

The main goal of this paper is to derive a decentralized algorithm which can efficiently learn the gradient of a black-box model, in a multi-agent context. In a black-box model it is assumed that a function f is unknown but can be accessed through queries to a zero-th order oracle [6]. Being able to compute the gradient can be used, for instance to design efficient distributed optimization algorithms to find the minimum of f. We assume that there is a finite number of processors/servers (called nodes or agents in the rest of the paper) which participate in the distributed computation of the gradient. We also assume that some agents can have Byzantine behaviors: that is, they will try to deviate from the suggested protocol. Such behaviors are well known in the literature of distributed algorithms (consensus and leader election algorithms, for instance) and have also recently been studied in the context of machine learning [7, 12, 11]. In such contexts, three major points need to be tackled: (1) The fact that unidentifiable Byzantines nodes are present in the system and that it is not possible to guarantee the safety of a given node; (2) the algorithms should be decentralized and each "good" node, should have a good estimation of the gradient (3) the algorithms should be efficient (in terms of speed of convergence and number of operations per iterations). Our solution is based on a generalization of the gradient estimator algorithm developed in [4], using two-timescale stochastic approximations and secure estimation [8]. We are also able to derive sufficient conditions to ensure that our algorithm will be able to be robust to Byzantine nodes.