Differential Privacy and Byzantine Resilience in SGD: Do They Add Up?

2021/02/16 by Rachid Guerraoui, Nirupam Gupta, Guerraoui, Rachid +7 · 2 citations
Computer Science · #Age of Information Optimization #Cryptography and Security (cs.CR) #Distributed #FOS: Computer and information sciences #Machine Learning (cs.LG) #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #cs.CR #cs.DC #cs.LG

paper · pdf · doi:10.48550/arxiv.2102.08166

openalex publication_date 2021/02/16 · arxiv created 2021/06/24 · arxiv updated 2021/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper addresses the problem of combining Byzantine resilience with privacy in machine learning (ML). Specifically, we study if a distributed implementation of the renowned Stochastic Gradient Descent (SGD) learning algorithm is feasible with both differential privacy (DP) and (α,f)-Byzantine resilience. To the best of our knowledge, this is the first work to tackle this problem from a theoretical point of view. A key finding of our analyses is that the classical approaches to these two (seemingly) orthogonal issues are incompatible. More precisely, we show that a direct composition of these techniques makes the guarantees of the resulting SGD algorithm depend unfavourably upon the number of parameters of the ML model, making the training of large models practically infeasible. We validate our theoretical results through numerical experiments on publicly-available datasets; showing that it is impractical to ensure DP and Byzantine resilience simultaneously.

Citations

• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
• Gradient-based learning applied to document recognition
• Federated Learning: Strategies for Improving Communication Efficiency
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Phocas: dimensional Byzantine-resilient stochastic gradient descent
• Zeno: Distributed Stochastic Gradient Descent with Suspicion-based Fault-tolerance
• Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
• Byzantine-Resilient Secure Federated Learning

Cited by

• Beyond Trade-offs: A Unified Framework for Privacy, Robustness, and Communication Efficiency in Federated Learning
• Towards Trustworthy Federated Learning with Untrusted Participants

Related

• Combining Differential Privacy and Byzantine Resilience in Distributed SGD
• On the Tradeoff between Privacy Preservation and Byzantine-Robustness in Decentralized Learning
• ImprovDML: Improved Trade-off in Private Byzantine-Resilient Distributed Machine Learning
• Data Heterogeneity Differential Privacy: From Theory to Algorithm
• Bridging Differential Privacy and Byzantine-Robustness via Model Aggregation