`

Timezone: »

 
Poster
Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)
El Mahdi El-Mhamdi · Sadegh Farhadkhani · Rachid Guerraoui · Arsany Guirguis · Lê-Nguyên Hoang · Sébastien Rouault

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @ None #None
We study \emph{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 \emph{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 \geq 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 \geq 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.

Author Information

El Mahdi El-Mhamdi (Ecole Polytechnique)
Sadegh Farhadkhani (EPFL)
Rachid Guerraoui (EPFL)

EPFL Professor

Arsany Guirguis (EPFL)

PhD student focusing on practical perspectives of distributed ML.

Lê-Nguyên Hoang (EPFL)
Sébastien Rouault (Swiss Federal Institute of Technology Lausanne)

More from the Same Authors