On Distributed Stochastic Gradient Descent for Nonconvex Functions in the Presence of Byzantines
Saikiran Bulusu, Prashant Khanduri, Pranay Sharma, Pramod K. Varshney · 2020
We consider the distributed stochastic optimization problem of minimizing a nonconvex function f in an adversarial setting. All the w worker nodes in the network are expected to send their stochastic gradient vectors to the fusion center (or server). However, some (at most α-fraction) of the nodes may be Byzantines, which may send arbitrary vectors instead. Vanilla implementation of distributed stochastic gradient descent (SGD) cannot handle such misbehavior from the nodes. We propose a robust variant of distributed SGD which is resilient to the presence of Byzantines. The fusion center employs a novel filtering rule that identifies and removes the Byzantine nodes. We show that T = Õ (1/wϵ2+ α2/ϵ2) iterations are needed to achieve an ϵ-approximate stationary point (x such that ∥∇f(x)∥2≤ ϵ) for the nonconvex learning problem. Unlike other existing approaches, the proposed algorithm is independent of the problem dimension.