Mar, 2024

DASA：延迟自适应多智能体随机逼近

PDF
TL;DR我们提出了一种延迟自适应的算法 exttt {DASA}，在多智能体随机逼近中实现了收敛速度的 $N$ 倍加速，同时仅依赖于混合时间 $ mix$ 和平均延迟 $ au_{avg}$，这一结果领先于现有研究。
stochastic approximationdelay-adaptive algorithmmulti-agentconvergence ratemarkovian sampling
发现论文，激发创造
  • 具有延迟更新的随机逼近：马尔科夫采样下的有限时间收敛速率

    基于大规模和多智能体强化学习的应用，我们研究了在马尔可夫采样下具有延迟更新的随机逼近（SA）方案的非渐近性能。我们首先表明，在时间变化的有界延迟下，延迟的 SA 更新规则保证了 “最后迭代” 指数级快速收敛到 SA 操作符固定点周围的球体。与传统的延迟 SA 规则相比，我们的研究减缓了最大延迟对收敛速率的影响，并且不需要关于延迟序列的先验知识来进行步长调整。我们的理论发现揭示了延迟对一类算法的有限时间效果，包括 TD 学习、Q 学习和马尔可夫采样下的随机梯度下降。

    Feb, 2024

  • AdaDelay: 延迟自适应的分布式随机凸优化

    该研究探讨并分析了实际分布式计算网络情况下的延迟梯度模型，允许参数更新对实际延迟进行敏感处理以产生更大的步长，从而在保持相同渐近复杂度的同时实现更快收敛，针对包含数十亿个数据和特征的真实数据集展开分布式实验，并取得鼓舞人心的改进。

    Aug, 2015

  • 异步和延迟的去中心化一致性优化

    本研究提出了一种异步、分散的共识优化算法，可在没有全局时序同步的情况下，利用本地计算和信息传递，在有限延迟和随机代理假设下收敛于精确解。

    Dec, 2016

  • DSA：去中心化双随机平均梯度下降算法

    该论文提出了分布式双随机平均梯度算法 (DSA) 来解决大规模机器学习问题，具有线性收敛特性，相对于其他分散式随机优化方法，可以减少收敛时间和处理的功能向量数量。

    Jun, 2015

  • 分布式随机逼近算法的性能

    本文研究了一种分布式随机逼近算法，可应用于去中心化的估算、优化、控制或计算。该算法包含本地步骤和交换步骤，通过微小的步长逼近算法和局部加权平均计算。通过研究约束子空间内平均场的 Lyapunov 函数和随机权重矩阵的收缩性质，建立估计向共识收敛的证明，并进行了二阶分析和多项式平均版本的研究。

    Mar, 2012

  • 面向更高效的随机分散式学习：更快的收敛与稀疏通信

    本研究提出了一种名为 DSBA 的随机算法，通过将分散的优化问题推广为单调算子求根问题来解决这一问题，具有线性收敛速度和只需稀疏通讯的优点，同时还能有效地处理像 AUC 最大化这样的学习问题。

    May, 2018

  • 分布式延迟随机优化

    该文主要研究基于梯度的优化算法中的延迟随机梯度信息的收敛性，以及如何应用于分布式优化算法中克服通信瓶颈和同步要求的问题，结果表明在平滑随机问题中，延迟是渐近可以忽略的，且能达到最优收敛效果。

    Apr, 2011

  • 带有延迟的多智能体在线优化：异步性、适应性和乐观主义

    本研究提出并分析了一种自适应二元平均方案，解决多智能体在延迟和异步性存在情况下的联合在线学习问题，并提供了一个适用于完全去中心化和异步环境中的自适应学习策略及优化方案。

    Dec, 2020

  • 具有马尔可夫噪声的双时间尺度线性随机逼近的紧限定时间界

    用马尔可夫噪声对线性二时间尺度随机逼近算法进行了收敛性分析，得到了该算法各种步长选择下的收敛行为，应用结果到 TDC 算法得到了比之前工作更好的收敛性样本复杂度，该结果还适用于确定各种强化学习算法的收敛行为，如带有 Polyak 平均的 TD 学习，GTD 和 GTD2。

    Dec, 2023

  • 分布式检测的数据辅助感知

    研究数据辅助感知在无线传感器网络中的应用，提出一种基于 J - 差异的节点选择方法，以实现可靠决策。研究结果表明，相对于其他方法，基于 J - 差异的节点选择方法可以使用更少的传感器实现可靠决策。

    Nov, 2020