Jun, 2023
流言模型中的分散式学习动态
Decentralized Learning Dynamics in the Gossip Model
TL;DR研究在流言传播模型中的分布式多臂赌博设置在n个。内存受限节点的人口中：在每个回合中，每个节点本地采取m个手臂之一，观察从手臂中获得的回报（敌意选择）分布，然后与随机抽样的邻居进行通信，交换信息以确定其在下一轮中的策略。我们引入和分析了这个任务的几族动力学，这些动力学是分散的；每个节点的决策完全是本地的，并且仅取决于最近获得的奖励及其抽样邻居的奖励。我们展示了这些分散动态的全局演化与某种“零和”乘性权重更新算法之间的联系，并且我们开发了一个通用框架来分析这些自然协议的种群水平遗憾。利用这个框架，在广泛的参数范围下 (即人口规模和臂数)，我们推导出静态奖励设置 (每个臂的分布均值随时间固定)和敌意奖励设置(均值随时间可变)的次线性遗憾界。此外，我们还表明，当奖励分布是由随机梯度量规产生时，这些协议可以近似地优化面对单纯形的凸函数。