Dec, 2023

无延迟参数的异步分布式优化

PDF
TL;DR该研究开发了两种分布式算法（Prox-DGD 和 DGD-ATC）的异步版本，用于解决无向网络上的共识优化问题，并且与其他算法相比，我们的算法可以使用与延迟无关的步长来收敛到它们的同步对应算法的固定点集。该研究还在部分异步和完全异步情况下，为强凸和弱凸问题建立了收敛保证，并展示了两种异步方法的收敛速度能够适应实际异步程度而不受最坏情况的限制。数值实验表明我们的异步算法具有很强的实际性能。
asynchronous distributed optimizationconvergence guaranteesundirected networksprox-dgddgd-atc
发现论文，激发创造
  • 异步和延迟的去中心化一致性优化

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

    Dec, 2016

  • 分布式延迟随机优化

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

    Apr, 2011

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

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

    Aug, 2015

  • 异步分布式半随机梯度优化

    本文提出了一种基于异步随机梯度下降的快速分布式机器学习算法，采用变量规约技术，可使用常量的学习率，并保证线性收敛到最优解，在 Google 云计算平台上的实验表明，该算法在墙时钟时间和解的质量方面优于最先进的分布式异步算法。

    Aug, 2015

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

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

    May, 2024

  • 异步随机凸优化

    本文表明，渐进地，完全异步的随机梯度程 序可以在几乎与标准随机梯度程 序的渐进最优性相同的条件下实现解决凸优化问题的最优（甚至是常数因子）收敛率。大体而言，随机近似方案固有的噪音支配了任何来自异步的噪音。我们还提供了经验性 证据，证明了异步、并行的随机优化方案的强大性能，这表明随机近似问题固有的稳健性允许更快的并行和异步解决方法。

    Aug, 2015

  • 异步并行和分布式优化的进展

    本文综述了近年来在大规模优化问题中应用的异步优化方法的最新发展，旨在提高计算资源利用率和收敛速度，在处理信息延迟、节点延迟等问题时，尤其是在随机优化方法中，异步更新方式具有更为优越的性能。

    Jun, 2020

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

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

    Feb, 2017

  • 随机交替方向乘子法异步分布式优化

    本文提出了一类新的随机异步分布式优化方法，将标准的交替方向乘子法推广到异步设置中，其中随机的高斯 - 塞德尔迭代用于找到两个单调算子求和的零点，最终收敛性在连接性条件下得到保证，数值结果证明了我们的理论。

    Mar, 2013

  • 更加现实的假设下的异步坐标下降

    本篇论文研究非同步并行块协调下降算法，证明了更实际的假设条件下算法的收敛性，并构建了直接模拟目标进展和延迟的李雅普诺夫函数。

    May, 2017