May, 2024

时变网络中的去中心化优化与任意延迟

PDF
TL;DR我们提出了一种称为 DT-GO 的新颖基于八卦的算法，它在不需要了解节点出度的情况下适用于一般的有向网络，对于拥有延迟或有限确认能力的网络。我们推导了凸和非凸目标的收敛速率，并证明我们的算法实现了与集中式随机梯度下降相同的复杂度顺序，也就是说，图的拓扑结构和延迟效应只影响高阶项。此外，我们扩展了分析以适应时变网络拓扑。通过数值仿真来支持我们的理论发现。
decentralized optimizationcommunication delaysdirected graphsgossip-based algorithmconvergence rates
发现论文，激发创造
  • 非光滑凸分散时间变网络优化的下界与最优算法

    在时间变化的网络上，解决非光滑凸分布式优化问题时，本文首次确定了通信和子梯度计算复杂性的下界，并发展了与下界匹配且在理论性能方面明显优于现有技术的最优算法。

    May, 2024

  • 分布式延迟随机优化

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

    Apr, 2011

  • 分布式优化中的网络拓扑和通讯计算权衡

    本文介绍了去中心化优化中最近的研究进展，并概述了针对不同场景的算法和分析，强调了网络拓扑在这些方法中的作用。

    Sep, 2017

  • 动态有向图中的离散分布优化

    我们提出了一个分布式优化的离散时间模型，适用于具有动态有向图的连续时间分布式学习，并消除了对链接进行随机权重设计的需求，通过共识算法、矩阵扰动理论和 Lyapunov 理论，我们证明了梯度跟踪步长和离散时间步长的收敛性和动态稳定性，该工作在链接删除或数据丢失的情况下改善了现有随机权重无向网络的性能，而无需重新运行耗时和计算复杂的算法。该提出的优化框架在分布式分类和学习中具有应用价值。

    Nov, 2023

  • 强健且通信高效的协作学习

    本文提出了一种名为 QuanTimed-DSGD 的新型分布式渐进优化算法，通过调整每个节点在算法每一步中本地计算梯度的截止时间和节点间交换量化本地模型的机制来解决分布式计算中经常遇到的滞后和通信效率低的问题，数值评估结果表明该算法与最先进的分布式优化方法相比，运行时间可提速至多 3 倍。

    Jul, 2019

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

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

    Dec, 2016

  • 时变有向图上的分布式优化

    本文研究了通过节点之间的交流来进行分布式优化的问题，提出了一种基于广播的算法，即 subgradient-push algorithm, 计算其收敛速率.

    Mar, 2013

  • 网络中平滑且强凸分布式优化的最优算法

    该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率：中央集权和去中心化通信。对于中央集权算法，作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法，作者提供了第一个最优算法 MSDA 方法，并通过最小二乘回归和分类的逻辑回归问题验证了其效率。

    Feb, 2017

  • 去中心化和随机优化的通讯高效算法

    本文提出了一种新的去中心化一阶方法解决在多代理网络上的非光滑和随机优化问题，其中主要贡献为提出了基于去中心化通讯滑动算法的去中心化原始 - 对偶算法，以解决在去中心化优化中通讯瓶颈。

    Jan, 2017

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

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

    Aug, 2015