May, 2023

分布式随机逼近的稳定性和收敛性与大型无界随机信息延迟

PDF
TL;DR本文介绍了一种新的分布式随机逼近方法 —— 信息时效性随机过程 (AoIP)，并给出了基于 AoIP 之上的广义 Borkar-Meyn 稳定性定理 (BMT)。同时本文还提出了一种适用于时变下限求和的新型 Gronwall 不等式，并将此应用于优化问题。
distributed stochastic approximationsage of information processesstabilitygronwall-type inequalityoptimization
发现论文，激发创造
  • 具有微分包含的异步随机逼近

    采用伪轨迹法和两种时间尺度方法，通过异步随机逼近和组距平均场，实现对异步算法的收敛性分析并应用于马尔可夫决策过程的学习问题。

    Dec, 2011

  • 具有延迟更新的随机逼近：马尔科夫采样下的有限时间收敛速率

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

    Feb, 2024

  • 关于无通信延迟的异步随机逼近稳定性的注记

    本文研究没有通信延迟的异步随机逼近算法，主要贡献是通过扩展 Borkar 和 Meyn 的方法来进行这些算法的稳定性证明，我们还从稳定性结果中导出收敛性结果，并讨论其在重要的平均奖励强化学习问题中的应用。

    Dec, 2023

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

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

    Mar, 2012

  • 分布式延迟随机优化

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

    Apr, 2011

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

    我们提出了一种延迟自适应的算法 exttt {DASA}，在多智能体随机逼近中实现了收敛速度的 $N$ 倍加速，同时仅依赖于混合时间 $ mix$ 和平均延迟 $ au_{avg}$，这一结果领先于现有研究。

    Mar, 2024

  • 多聚类随机块模型中的检测：实现猜想的证明，无环 BP 和信息计算差距

    该论文证明了随机块模型的一个猜想，提出了一种非对称的社区检测算法，并将其与信念传播和谱方法联系起来，同时展示了信息论计算差距在其中的应用。

    Dec, 2015

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

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

    Dec, 2023

  • 随机顺序消息传递算法在近似推理中的分析

    本文采用随机协方差矩阵和动力学平均场方程来分析一种用于大型高斯潜变量模型的随机顺序消息传递算法，包括模型不匹配情境和算法收敛的模型参数取值范围.

    Feb, 2022

  • 随机逼近的收敛速度：有偏差噪声与无界方差，及其应用

    该研究论文主要讨论了随机逼近算法在嘈杂测量、凸凹优化、强化学习以及马尔可夫逼近方面的应用，并且扩展了该算法以包含具有非零条件均值和 / 或无界条件方差的错误，从而证明了算法在这些情况下的收敛性，并计算了 “优化步长序列” 以最大化估计的收敛速率。

    Dec, 2023