Federated Variance-Reduced Stochastic Gradient Descent With Robustness to Byzantine Attacks
Open accessThe DOI matches its Crossref record; 47 of the 51 references it cites were found in a registry or an index.
Abstract
This paper deals with distributed finite-sum optimization for learning over multiple workers in the presence of malicious Byzantine attacks. Most resilient approaches so far combine stochastic gradient descent (SGD) with different robust aggregation rules. However, the sizeable SGD-induced stochastic gradient noise challenges discerning malicious messages sent by the Byzantine attackers from noisy stochastic gradients sent by the `honest' workers. This motivates reducing the variance of stochastic gradients as a means of robustifying SGD. To this end, a novel Byzantine attack resilient distributed (Byrd-) SAGA approach is introduced for federated learning tasks involving multiple workers. Rather than the mean employed by distributed SAGA, the novel Byrd-SAGA relies on the geometric median to aggregate the corrected stochastic gradients sent by the workers. When less than half of the workers are Byzantine attackers, Byrd-SAGA attains provably linear convergence to a neighborhood of the optimal solution, with the asymptotic learning error determined by the number of Byzantine workers. Numerical tests corroborate the robustness to various Byzantine attacks, as well as the merits of Byrd-SAGA over Byzantine attack resilient distributed SGD.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“To address Byzantine attacks (i.e., the faulty edge device can behave arbitrarily badly by modifying its local updates) in FL with a server-client architecture, various robust and secure model aggregation schemes (e.g., geometric median [168], trimmed mean [169], and Krum [170]) were proposed to tolerate the Byzantine corrupted edge devices.”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [168]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
The Byzantine generals problem
Lamport, L., Shostak, R., & Pease, M. (1982) · ACM Transactions on Programming Languages and Systems · doi:10.1145/357172.357176 · Cited by 6,023 · cited 1×
“We will henceforth focus on the class of malicious attacks known as Byzantine attacks [8].”
BackgroundLarge-Scale Machine Learning with Stochastic Gradient Descent
Bottou, L. (2010) · Proceedings of COMPSTAT'2010 · doi:10.1007/978-3-7908-2604-3_16 · Cited by 5,795 · cited 1×
“When all workers are honest, a popular solver of (1) is SGD [34].”
BackgroundIntroductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 2,961
Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., & He, K. (2017) · arXiv · doi:10.48550/arxiv.1706.02677 · Cited by 2,294 · cited 2×
“In addition, other variance reduction techniques, such as minibatch [22], are also available to alleviate the gradient noise.”
BackgroundAccelerating Stochastic Gradient Descent using Predictive Variance Reduction
Johnson, R., & Zhang, T. (2013) · Cited by 1,889
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335438 · Cited by 1,719
Federated Optimization: Distributed Machine Learning for On-Device Intelligence
Konečný, J., McMahan, H. B., Ramage, D., & Richtárik, P. (2016) · arXiv · doi:10.48550/arxiv.1610.02527 · Cited by 1,563
(2017) · neural information processing systems · Cited by 1,413
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
Yin, D., Chen, Y., Ramchandran, K., & Bartlett, P. (2018) · arXiv · doi:10.48550/arxiv.1803.01498 · Cited by 1,130
Minimizing finite sums with the stochastic average gradient
Schmidt, M., Le Roux, N., & Bach, F. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1030-6 · Cited by 922
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
Defazio, A., Bach, F., & Lacoste-Julien, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.0202 · Cited by 834
Stochastic dual coordinate ascent methods for regularized lossPreprint
Shalev‐Shwartz, S., & Zhang, T. (2013) · Cited by 637
Katyusha: the first direct acceleration of stochastic gradient methods
Allen-Zhu, Z. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055448 · Cited by 461
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2017) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3154503 · Cited by 390
Li, L., Xu, W., Chen, T., Giannakis, G. B., & Ling, Q. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33011544 · Cited by 373
Self-citationLAG: Lazily Aggregated Gradient for Communication-Efficient Distributed LearningPreprint
Chen, T., Giannakis, G. B., Sun, T., & Yin, W. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.09965 · Cited by 329
Self-citationSARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive GradientPreprint
Nguyen, L. M., Liu, J., Scheinberg, K., & Takáč, M. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1703.00102 · Cited by 325
Geometric median and robust estimation in Banach spaces
Minsker, S. (2015) · Bernoulli · doi:10.3150/14-bej645 · Cited by 261
On the point for which the sum of the distances to n given points is minimum
Weiszfeld, E., & Plastria, F. (2009) · Annals of Operations Research · doi:10.1007/s10479-008-0352-z · Cited by 248
Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
Shalev‐Shwartz, S., & Zhang, T. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.1873 · Cited by 240
Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
Chen, Y., Su, L., & Xu, J. (2018) · Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems · doi:10.1145/3219617.3219655 · Cited by 228
Generalized Byzantine-tolerant SGD
Xie, C., Koyejo, S., & Gupta, I. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.10116 · Cited by 166
D$^2$: Decentralized Training over Decentralized Data
Tang, H., Lian, X., Yan, M., Zhang, C., & Liu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.07068 · Cited by 159
BRIDGE: Byzantine-Resilient Decentralized Gradient Descent
Fang, C., Yang, Z., & Bajwa, W. U. (2022) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2022.3188456 · Cited by 154
Distributed Inference with Byzantine Data: State-of-the-Art Review on Data Falsification Attacks
Vempaty, A., Tong, L., & Varshney, P. K. (2013) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2262116 · Cited by 146
Yang, Z., Gang, A., & Bajwa, W. U. (2020) · IEEE Signal Processing Magazine · doi:10.1109/msp.2020.2973345 · Cited by 112
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
Reddi, S. J., Hefny, A., Sra, S., Póczos, B., & Smola, A. J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.06840 · Cited by 99
Defending Against Saddle Point Attack in Byzantine-Robust Distributed LearningPreprint
Yin, D., Chen, Y., Ramchandran, K., & Bartlett, P. L. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.05358 · Cited by 87
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.6000 · Cited by 86
The Internet of Things: Secure Distributed Inference
Chen, Y., Kar, S., & Moura, J. M. F. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2842097 · Cited by 77
DETOX: A redundancy-based framework for faster and more robust gradient aggregation
Rajput, S., Wang, H., Charles, Z., & Papailiopoulos, D. (2019) · arXiv · doi:10.48550/arxiv.1907.12205 · Cited by 72
Zhou, L., Yeh, K.-H., Hancke, G., Liu, Z., & Su, C. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2018.2846297 · Cited by 65
Robust Distributed Consensus Using Total Variation
Ben‐Ameur, W., Bianchi, P., & Jakubowicz, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2471755 · Cited by 53
Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation
Xie, C., Koyejo, S., & Gupta, I. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.03936 · Cited by 51
Efficient Distributed SGD with Variance Reduction
De, S., & Goldstein, T. (2016) · Proceedings · doi:10.1109/icdm.2016.0022 · Cited by 44
Variance-Reduced Stochastic Learning Under Random Reshuffling
Ying, B., Yuan, K., & Sayed, A. H. (2020) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2020.2968280 · Cited by 43
Securing Distributed Gradient Descent in High Dimensional Statistical LearningPreprint
Su, L., & Xu, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1804.10140 · Cited by 37
Feng, J., Xu, H., & Mannor, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.5937 · Cited by 30
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients
Chen, L., Wang, H., Charles, Z., & Papailiopoulos, D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.09877 · Cited by 28
Securing Distributed Machine Learning in High DimensionsPreprint
Su, L., & Xu, J. (2018) · arXiv (Cornell University) · Cited by 25
BRIDGE: Byzantine-resilient Decentralized Gradient DescentPreprint
Fang, C., Yang, Z., & Bajwa, W. U. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.08098 · Cited by 19
Stochastic Optimization with Variance Reduction for Infinite Datasets with Finite-Sum StructurePreprint
Bietti, A., & Mairal, J. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1610.00970 · Cited by 19
Byzantine-resilient Distributed Large-scale Matrix Completion
Lin, F., Ling, Q. H., & Xiong, Z. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683121 · Cited by 19
Self-citationDistributed SAGA: Maintaining linear convergence rate with limited communicationPreprint
Calauzènes, C., & Roux, N. L. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.10405 · Cited by 7
COVER: A Cluster-based Variance Reduced Method for Online Learning
Yuan, K., Ying, B., & Sayed, A. H. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8682527 · Cited by 6
Research works printed but not linked: 2
- tang, 0, D2: Decentralized training over decentralized data, Proc Int Conf Mach Learn, 4855
- yang, 2019, Federated Learning
Cited by
Edge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“, geometric median [168], trimmed mean [169], and Krum [170]) were proposed to tolerate the Byzantine corrupted edge devices.”
BackgroundRobust Aggregation for Federated Learning
Pillutla, K., Kakade, S. M., & Harchaoui, Z. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3153135 · Cited by 801
Rodríguez-Barroso, N., Jiménez-López, D., Luzón, M. V., Herrera, F., & Martínez-Cámara, E. (2023) · Information Fusion · doi:10.1016/j.inffus.2022.09.011 · Cited by 296
Federated Learning of a Mixture of Global and Local Models
Hanzely, F., & Richtárik, P. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2002.05516 · Cited by 230
An Experimental Study of Byzantine-Robust Aggregation Schemes in Federated Learning
Li, S., Ngai, E. C. ‐., & Voigt, T. (2023) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2023.3237397 · Cited by 176
Metadata
- Authors
- Wu, Z., Ling, Q., Chen, T., & Giannakis, G. B.
- Affiliations
- Sun Yat-sen University (CN)
- Rensselaer Polytechnic Institute (US)
- University of Minnesota (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2020
- Volume
- 68
- Pages
- 4583-4596
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W3046449784
- Cited by
- 226
- References
- 51
- Citations by year
- 2026: 22 · 2025: 45 · 2024: 41 · 2023: 40 · 2022: 38 · 2021: 32 · 2020: 8
- FWCI
- 11.60
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- NSF (61573331, 61973324, 1509040, 1508993, 1711471, 1901134)
- Fundamental Research Funds for the Central Universities
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Keywords
- federated learning, Byzantine attacks, variance reduction, stochastic gradient descent, sagas, geometric median, robust aggregation, distributed optimization, finite-sum optimization, linear convergence, malicious workers
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.