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

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