2026-07-22T21:48:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15779 2024-03-06T10:56:08Z ddc:004 open_access

Arbitrarily Accurate Aggregation Scheme for Byzantine SGD Maurer, Alexandre distributed machine learning Byzantine failures stochastic gradient descent A very common optimization technique in Machine Learning is Stochastic Gradient Descent (SGD). SGD can easily be distributed: several workers try to estimate the gradient of a loss function, and a central parameter server gathers these estimates. When all workers behave correctly, the more workers we have, the more accurate the gradient estimate is. We call this the Arbitrary Aggregation Accuracy (AAA) property. However, in practice, some workers may be Byzantine (i.e., have an arbitrary behavior). Interestingly, when a fixed fraction of workers is assumed to be Byzantine (e.g. 20%), no existing aggregation scheme has the AAA property. In this paper, we propose the first aggregation scheme that has this property despite a fixed fraction of Byzantine workers (less than 50%). We theoretically prove this property, and then illustrate it with simulations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandre Maurer 2022 Is Part Of LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2021.4 urn:nbn:de:0030-drops-157793 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.4 eng https://creativecommons.org/licenses/by/4.0/legalcode