Learning from History for Byzantine Robust Optimization

Sai Praneeth Karimireddy, Lie He, Martin Jaggi
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5311-5319, 2021.

Abstract

Byzantine robustness has received significant attention recently given its importance for distributed and federated learning. In spite of this, we identify severe flaws in existing algorithms even when the data across the participants is identically distributed. First, we show realistic examples where current state of the art robust aggregation rules fail to converge even in the absence of any Byzantine attackers. Secondly, we prove that even if the aggregation rules may succeed in limiting the influence of the attackers in a single round, the attackers can couple their attacks across time eventually leading to divergence. To address these issues, we present two surprisingly simple strategies: a new robust iterative clipping procedure, and incorporating worker momentum to overcome time-coupled attacks. This is the first provably robust method for the standard stochastic optimization setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-karimireddy21a, title = {Learning from History for Byzantine Robust Optimization}, author = {Karimireddy, Sai Praneeth and He, Lie and Jaggi, Martin}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5311--5319}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/karimireddy21a/karimireddy21a.pdf}, url = {https://proceedings.mlr.press/v139/karimireddy21a.html}, abstract = {Byzantine robustness has received significant attention recently given its importance for distributed and federated learning. In spite of this, we identify severe flaws in existing algorithms even when the data across the participants is identically distributed. First, we show realistic examples where current state of the art robust aggregation rules fail to converge even in the absence of any Byzantine attackers. Secondly, we prove that even if the aggregation rules may succeed in limiting the influence of the attackers in a single round, the attackers can couple their attacks across time eventually leading to divergence. To address these issues, we present two surprisingly simple strategies: a new robust iterative clipping procedure, and incorporating worker momentum to overcome time-coupled attacks. This is the first provably robust method for the standard stochastic optimization setting.} }
Endnote
%0 Conference Paper %T Learning from History for Byzantine Robust Optimization %A Sai Praneeth Karimireddy %A Lie He %A Martin Jaggi %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-karimireddy21a %I PMLR %P 5311--5319 %U https://proceedings.mlr.press/v139/karimireddy21a.html %V 139 %X Byzantine robustness has received significant attention recently given its importance for distributed and federated learning. In spite of this, we identify severe flaws in existing algorithms even when the data across the participants is identically distributed. First, we show realistic examples where current state of the art robust aggregation rules fail to converge even in the absence of any Byzantine attackers. Secondly, we prove that even if the aggregation rules may succeed in limiting the influence of the attackers in a single round, the attackers can couple their attacks across time eventually leading to divergence. To address these issues, we present two surprisingly simple strategies: a new robust iterative clipping procedure, and incorporating worker momentum to overcome time-coupled attacks. This is the first provably robust method for the standard stochastic optimization setting.
APA
Karimireddy, S.P., He, L. & Jaggi, M.. (2021). Learning from History for Byzantine Robust Optimization. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5311-5319 Available from https://proceedings.mlr.press/v139/karimireddy21a.html.

Related Material