Robust Distributed Optimization With Randomly Corrupted Gradients

Abstract

In this paper, we propose a first-order distributed optimization algorithm that is provably robust to Byzantine failures-arbitrary and potentially adversarial behavior, where all the participating agents are prone to failure. We model each agent's state over time as a two-state Markov chain that indicates Byzantine or trustworthy behaviors at different time instants. We set no restrictions on the maximum number of Byzantine agents at any given time. We design our method based on three layers of defense: 1) temporal robust aggregation, 2) spatial robust aggregation, and 3) gradient normalization. We study two settings for stochastic optimization, namely Sample Average Approximation and Stochastic Approximation. We provide convergence guarantees of our method for strongly convex and smooth non-convex cost functions.

arXiv comment21 pages, 5 figures

References in corpus (21)

• Deep Learning with Differential Privacy
• Federated Learning: Strategies for Improving Communication Efficiency
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• How To Backdoor Federated Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Large Batch Training of Convolutional Networks
• Can You Really Backdoor Federated Learning?
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning
• Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
• ByRDiE: Byzantine-resilient distributed coordinate descent for decentralized learning
• Adversary-resilient Distributed and Decentralized Statistical Inference and Machine Learning: An Overview of Recent Advances Under the Byzantine Threat Model
• On the Convergence Rate of Incremental Aggregated Gradient Algorithms
• The Internet of Things: Secure Distributed Inference
• Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
• The Power of Normalization: Faster Evasion of Saddle Points
• Optimal Hoeffding bounds for discrete reversible Markov chains
• Resilient Primal-Dual Optimization Algorithms for Distributed Resource Allocation
• Distributed stochastic optimization via matrix exponential learning
• Greedy Sparsity-Promoting Algorithms for Distributed Learning