本文研究了分布式优化中最近提出的 subgradient-push 方法在时变有向图上的收敛速度,并证明在强凸函数和具有 Lipschitz 梯度的情况下,即使只有随机梯度样本可用,其收敛速度为 O ((ln t)/t),这比先前已知的(一般)凸函数的 O ((ln t)/√t) 更快。
Jun, 2014
该研究分析分布式非凸优化问题,针对多智能体网络模型,利用一些技术假设证明分布式推送算法在目标函数的临界点处收敛,并利用扰动动力学证明扰动过程的几乎肯定收敛性。
Dec, 2015
本文介绍了一种新的分布式梯度方法,称为 “推 - 拉梯度方法”,利用两种不同的图形实现代理之间的信息交换,并在同步和异步随机传递的情况下,线性地收敛于重要的自治网络。
Oct, 2018
在时间变化的网络上,解决非光滑凸分布式优化问题时,本文首次确定了通信和子梯度计算复杂性的下界,并发展了与下界匹配且在理论性能方面明显优于现有技术的最优算法。
May, 2024
本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题,并显示它们是最优的算法,具有复杂性的保证。
Jun, 2020
本文提出了一种名为 ADD-OPT 的分布式优化算法,它能够在具有强全局性连续 Lipschitz 梯度的强凸目标函数情况下,以最佳已知收敛速度 O (μ^k),k 为迭代次数。此外,ADD-OPT 支持一定范围的步长,并对此进行了模拟。
Jul, 2016
我们提出了一种称为 DT-GO 的新颖基于八卦的算法,它在不需要了解节点出度的情况下适用于一般的有向网络,对于拥有延迟或有限确认能力的网络。我们推导了凸和非凸目标的收敛速率,并证明我们的算法实现了与集中式随机梯度下降相同的复杂度顺序,也就是说,图的拓扑结构和延迟效应只影响高阶项。此外,我们扩展了分析以适应时变网络拓扑。通过数值仿真来支持我们的理论发现。
本文提出了一种异步多代理分布式优化算法,每个代理都有一个局部的强凸平滑函数,共同目标是达成对将代理的局部函数之和最小化的参数进行共识。实验结果表明,与同步一阶方法相比,Asynchronous Gradient-Push 算法收敛速度更快,更具鲁棒性,并且随着网络规模的增大,它的扩展性更好。
Mar, 2018
该论文在两个设置中确定了强凸和光滑分布式优化的最优收敛速率:中央集权和去中心化通信。对于中央集权算法,作者表明分布式 Nesterov 加速梯度下降算法是最优的。对于基于流言蜚语 (gossip) 的去中心化算法,作者提供了第一个最优算法 MSDA 方法,并通过最小二乘回归和分类的逻辑回归问题验证了其效率。
Feb, 2017
我们提出了一个分布式优化的离散时间模型,适用于具有动态有向图的连续时间分布式学习,并消除了对链接进行随机权重设计的需求,通过共识算法、矩阵扰动理论和 Lyapunov 理论,我们证明了梯度跟踪步长和离散时间步长的收敛性和动态稳定性,该工作在链接删除或数据丢失的情况下改善了现有随机权重无向网络的性能,而无需重新运行耗时和计算复杂的算法。该提出的优化框架在分布式分类和学习中具有应用价值。
Nov, 2023