Empire byzantin | EPFL Graph Search

L’'Empire byzantin' ou Empire romain d'Orient désigne l'État apparu vers le dans la partie orientale de l'Empire romain, au moment où celui-ci se divise progressivement en deux. Il se caractérise par sa longévité : il puise ses origines dans la fondation même de Rome, et la datation de ses débuts change selon les critères choisis par chaque historien. La fondation de Constantinople, sa capitale, par en 330, autant que la division d’un Empire romain de plus en plus difficile à gouverner et qui devient définitive en 395, sont parfois citées. Plus dynamique qu’un monde romain occidental dont l'administration effective est de plus en plus réalisée par les élites barbares à la suite de leur arrivée progressive par traité ou par conquête, l’Empire d’Orient s’affirme progressivement comme une construction politique originale. Indubitablement romain, cet empire est aussi chrétien et de langue principalement grecque. En 476, c'est la chute de l'Empire romain d'Occident, l'Empire byzantin de

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

El Mahdi El Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Hany Abdelmessih Guirguis, Le Nguyen Hoang, Sébastien Louis Alexandre Rouault

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborative learning is equivalent to a new form of agreement, which we call averaging agreement. In this problem, nodes start each with an initial vector and seek to approximately agree on a common vector, which is close to the average of honest nodes' initial vectors. We present two asynchronous solutions to averaging agreement, each we prove optimal according to some dimension. The first, based on the minimum-diameter averaging, requires n ≥ 6f+1, but achieves asymptotically the best-possible averaging constant up to a multiplicative constant. The second, based on reliable broadcast and coordinate-wise trimmed mean, achieves optimal Byzantine resilience, i.e., n≥3f+1. Each of these algorithms induces an optimal Byzantine collaborative learning protocol. In particular, our equivalence yields new impossibility theorems on what any collaborative learning algorithm can achieve in adversarial and heterogeneous environments.

2021

The Hidden Vulnerability of Distributed Learning in Byzantium

El Mahdi El Mhamdi, Rachid Guerraoui, Sébastien Louis Alexandre Rouault

While machine learning is going through an era of celebrated success, concerns have been raised about the vulnerability of its backbone: stochastic gradient descent (SGD). Recent approaches have been proposed to ensure the robustness of distributed SGD against adversarial (Byzantine) workers sending \emph{poisoned} gradients during the training phase. Some of these approaches have been proven \emph{Byzantine--resilient}: they ensure the \emph{convergence} of SGD despite the presence of a minority of adversarial workers. We show in this paper that \emph{convergence is not enough}. In high dimension

d \gg 1

, an adver-sary can build on the loss function's non--convexity to make SGD converge to \emph{ineffective} models. More precisely, we bring to light that existing Byzantine--resilient schemes leave a \emph{margin of poisoning} of

\bigOmega\left(f(d)\right)

, where

f(d)

increases at least like

\sqrt{d}

. Based on this \emph{leeway}, we build a simple attack, and experimentally show its strong to utmost effectivity on CIFAR--10 and MNIST. We introduce \emph{Bulyan}, and prove it significantly reduces the attacker's leeway to a narrow

\bigO\,( \sfrac{1}{\sqrt{d~}})

bound. We empirically show that Bulyan does not suffer the fragility of existing aggregation rules and, at a reasonable cost in terms of required batch size, achieves convergence \emph{as if} only non--Byzantine gradients had been used to update the model.

2018

AGGREGATHOR: Byzantine Machine Learning via Robust Gradient Aggregation

Georgios Damaskinos, El Mahdi El Mhamdi, Rachid Guerraoui, Arsany Hany Abdelmessih Guirguis, Sébastien Louis Alexandre Rouault

We present AGGREGATHOR, a framework that implements state-of-the-art robust (Byzantine-resilient) distributed stochastic gradient descent. Following the standard parameter server model, we assume that a minority of worker machines can be controlled by an adversary and behave arbitrarily. Such a setting has been theoretically studied with several of the existing approaches using a robust aggregation of the workers’ gradient estimations. Yet, the question is whether a Byzantine-resilient aggregation can leverage more workers to speedup learning. We answer this theoretical question, and implement these state-of-the-art theoretical approaches on AGGREGATHOR, to assess their practical costs. We built AGGREGATHOR around TensorFlow and introduce modifications for vanilla TensorFlow towards making it usable in an actual Byzantine setting. AGGREGATHOR also permits the use of unreliable gradient transfer over UDP to provide further speed-up (without losing the accuracy) over the native communication protocols (TCP-based) of TensorFlow in saturated networks. We quantify the overhead of Byzantine resilience of AGGREGATHOR to 19% and 43% (to ensure weak and strong Byzantine resilience respectively) compared to vanilla TensorFlow.

2019

The Hidden Vulnerability of Distributed Learning in Byzantium

El Mahdi El Mhamdi, Rachid Guerraoui, Sébastien Louis Alexandre Rouault

d \gg 1

\bigOmega\left(f(d)\right)

, where

f(d)

increases at least like

\sqrt{d}

\bigO\,( \sfrac{1}{\sqrt{d~}})

2018