Byzantine Resilient Non-Convex SVRG with Distributed Batch Gradient Computations

2019/12/10 by Prashant Khanduri, Saikiran Bulusu, Khanduri, Prashant +5 · 2 citations
Computer Science · #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1912.04531

openalex publication_date 2019/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this work, we consider the distributed stochastic optimization problem of minimizing a non-convex function f(x) = 𝔼_{ξ∼ D} f(x; ξ) in an adversarial setting, where the individual functions f(x; ξ) can also be potentially non-convex. We assume that at most α-fraction of a total of K nodes can be Byzantines. We propose a robust stochastic variance-reduced gradient (SVRG) like algorithm for the problem, where the batch gradients are computed at the worker nodes (WNs) and the stochastic gradients are computed at the server node (SN). For the non-convex optimization problem, we show that we need O( \frac1ε^5/3 K^2/3 + \fracα^4/3ε^5/3 ) gradient computations on average at each node (SN and WNs) to reach an ε-stationary point. The proposed algorithm guarantees convergence via the design of a novel Byzantine filtering rule which is independent of the problem dimension. Importantly, we capture the effect of the fraction of Byzantine nodes α present in the network on the convergence performance of the algorithm.

Citations

• Phocas: dimensional Byzantine-resilient stochastic gradient descent
• Zeno: Distributed Stochastic Gradient Descent with Suspicion-based\n Fault-tolerance
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent

Cited by

• Distributed Stochastic Non-Convex Optimization: Momentum-Based Variance\n Reduction
• Byzantine-Robust Variance-Reduced Federated Learning over Distributed Non-i.i.d. Data

Related

• Byzantine-Resilient Non-Convex Stochastic Gradient Descent
• Byzantine Stochastic Gradient Descent
• Byzantine-Robust Loopless Stochastic Variance-Reduced Gradient
• Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data
• Efficient Byzantine-Resilient Stochastic Gradient Desce