稀疏八卦网络中公平时效性的基于学习的方案
通过模拟比较四种标准赌博算法,同时结合分析性保证,我们对多源系统中的调度问题进行了研究,并对任何策略能够达到的累计遗憾下限进行了界定。
Oct, 2023
针对在网络传感器中的应用,该研究综述了流言算法在计算机科学、控制、信号处理和信息论领域的最新发展,重点介绍了算法收敛速度、在无线链路中传输的问题以及在分布式估计、信号源定位和压缩等方面的应用。
Mar, 2010
本文研究基于成对 “流言” 通信和更新的数字链接网络上的平均共识问题,并提出一组算法。我们研究了这些算法的收敛性质,旨在回答两个设计问题:代理应该通过确定性或随机量化器编码其通信,以及他们应该如何使用自己状态的精确信息来更新。
Jul, 2009
分布式异步学习系统通过模型更新和模型混合过程实现用户模型在有限时间内的收敛,并证明了当网络规模很大时,具有对数规模的用户混合能够保证用户模型的收敛,而有界的陈旧度只能通过至少与用户数量成线性关系的分布式机会方案来保证。
Apr, 2024
本文研究了一种名为地理流言算法的多跳通信网络消息传递方案,通过使用行程信息与 Markov 链混合时间不等式技术对随机化消息传递算法进行性能分析,提高了流言算法的效率。
Feb, 2008
研究在流言传播模型中的分布式多臂赌博设置在 n 个。内存受限节点的人口中:在每个回合中,每个节点本地采取 m 个手臂之一,观察从手臂中获得的回报(敌意选择)分布,然后与随机抽样的邻居进行通信,交换信息以确定其在下一轮中的策略。我们引入和分析了这个任务的几族动力学,这些动力学是分散的;每个节点的决策完全是本地的,并且仅取决于最近获得的奖励及其抽样邻居的奖励。我们展示了这些分散动态的全局演化与某种 “零和” 乘性权重更新算法之间的联系,并且我们开发了一个通用框架来分析这些自然协议的种群水平遗憾。利用这个框架,在广泛的参数范围下 (即人口规模和臂数),我们推导出静态奖励设置 (每个臂的分布均值随时间固定) 和敌意奖励设置 (均值随时间可变) 的次线性遗憾界。此外,我们还表明,当奖励分布是由随机梯度量规产生时,这些协议可以近似地优化面对单纯形的凸函数。
Jun, 2023
本文研究了在图形网络游戏中使用分布式八卦方法寻找纳什均衡的方法,介绍了干扰图和通信图的概念,设计了通信图以使玩家仅交换必要的信息,证明了使用干扰和通信图的八卦方法在收敛步长逐渐缩小的情况下能够几乎一定收敛于纳什均衡。
Mar, 2017
本文介绍了一种名为 Gossip-PGA 的算法,该算法将定期全局平均合并到 Gossip SGD 中,通过控制平均周期 H,可以控制网络拓扑结构的影响,而此算法在大规模训练中存在这样的优点,它使得瞬变阶段的收敛速度优于 Local SGD 且远优于原有的 Gossip SGD。
May, 2021
我们提出了一种称为 DT-GO 的新颖基于八卦的算法,它在不需要了解节点出度的情况下适用于一般的有向网络,对于拥有延迟或有限确认能力的网络。我们推导了凸和非凸目标的收敛速率,并证明我们的算法实现了与集中式随机梯度下降相同的复杂度顺序,也就是说,图的拓扑结构和延迟效应只影响高阶项。此外,我们扩展了分析以适应时变网络拓扑。通过数值仿真来支持我们的理论发现。
May, 2024