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

Sep, 2017

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

Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization

Angelia Nedić, Alex Olshevsky, Michael G. Rabbat

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

Abstract

In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of appli

decentralized optimization distributed estimation robust algorithms convergence rates network topology

发现论文，激发创造

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

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

May, 2024

一种灵活的梯度追踪方法的计算 - 通讯权衡

提出了一种灵活的梯度跟踪方法，用于解决非独立同分布情况下网络上的分布式随机优化问题，利用设计良好的李亚普诺夫函数，导出了计算和通信复杂度，以实现在光滑和强凸目标函数上的任意精度。

Jun, 2023

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

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

Jan, 2017

非光滑凸分散时间变网络优化的下界与最优算法

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

May, 2024

在有限通信条件下维持分布式学习和优化的线性收敛性

研究分布式优化和机器学习中如何通过压缩信息和设计通信协议来降低通信时间并保持算法收敛性的方法和框架。

Feb, 2019

分布式优化的双重平均：收敛分析和网络扩展

本文研究了分布式网络中去中心化优化的问题，尤其是基于双重平均子梯度的分布式算法及其收敛速度与网络大小和拓扑结构的关系，同时探讨了算法收敛和网络结构限制之间的关系，并证明了我们算法所需的迭代次数与网络谱隙成反比例关系。

May, 2010

具梯度跟踪和方差缩减的网络分布式优化通信效率提高

本文提出了一种基于去中心化网络的、通信效率高且线性收敛的近似牛顿方法，该方法可以用于复合优化，并且通过本地通信和计算，可以显著提高总体效率。

Sep, 2019

分布式优化中通信与计算的平衡

本文采用自适应成本框架和显示分解算法的方法对分布式梯度下降（DGD）算法进行了改进，并将其应用于机器学习中的二次函数和分类问题中，结果表明，新算法 NEAR-DGD^+ 在迭代、梯度评估和通信方面的性能优于基本算法。

Sep, 2017

具有动态拓扑和本地更新的去中心化 SGD 的统一理论

这篇论文介绍了一种统一的收敛性分析方法，涵盖了许多分散式随机梯度下降方法，具有计算成本低、数据本地性和沟通效率等优点，并包括本地随机梯度下降更新和自适应网络拓扑上的同步和成对传递更新，我们推导了光滑（凸和非凸）问题的通用收敛率，并在不同的数据分布和 iid 数据设置下进行了插值。

Mar, 2020

分布式梯度方法：拓扑结构是否重要？

该论文研究了分布式优化方法中工作通讯拓扑对收敛速度的影响，并提出通过使用稀疏拓扑来提高收敛速度的方法。

Feb, 2020