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 \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.


翻译:我们研究拜占庭合作学习, 在那里, 美元节点寻求从彼此的本地数据中集体学习。 数据分布可能因节点而不同。 诺节点是信任的, 美元 < n美元节点可以任意行事。 我们证明合作学习相当于一种新形式的协议, 我们称之为平均协议。 在这个问题中, 节点从最初的矢量开始, 并寻求大致商定一个共同矢量, 接近于诚实节点初始矢量的平均值。 我们为平均协议提出了两种不同步的解决方案, 每一个都证明在某些维度上是最佳的。 首先, 以最小直径平均值为基础, 需要 $\ geq 6f+1 美元, 但要在理论上实现最佳的平均平均常数, 直至一个多复制的常数。 第二, 根据可靠的广播和协调的三重量平均值, 实现最佳的拜占庭的复原力, 即 $n\ geq 3f+1$。 每一种这些算法都根据某种维度平均值, 要求一个最佳的拜占庭合作学习中度协议。

0
下载
关闭预览

相关内容

最新《联邦学习Federated Learning》报告,Federated Learning
专知会员服务
86+阅读 · 2020年12月2日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
Federated Learning: 架构
AINLP
4+阅读 · 2020年9月20日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Federated Learning with Personalization Layers
Arxiv
4+阅读 · 2019年12月2日
VIP会员
相关VIP内容
最新《联邦学习Federated Learning》报告,Federated Learning
专知会员服务
86+阅读 · 2020年12月2日
【普林斯顿大学-微软】加权元学习,Weighted Meta-Learning
专知会员服务
39+阅读 · 2020年3月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
相关资讯
Federated Learning: 架构
AINLP
4+阅读 · 2020年9月20日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Ray RLlib: Scalable 降龙十八掌
CreateAMind
8+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Top
微信扫码咨询专知VIP会员