Oct, 2023

RandCom: 随机通信跳过方法用于分散随机优化

PDF
TL;DR通过引入随机通信跳过的分布式优化方法，本文提出了一种名为 RandCom 的分散优化方法，并分析了其在随机非凸、凸和强凸环境中的性能，证明其能够通过通信概率来渐进地减少通信开销，并在节点数量增加时实现线性加速。此外，通过将 RandCom 应用于联合学习，得出了在非凸设置中实现线性加速的潜力和概率局部更新方法的适用性的积极结果。
distributed optimizationrandom communication skipsdecentralized optimizationcommunication overheadfederated learning
发现论文，激发创造
  • 分布式随机优化中的下限与通信压缩加速算法

    本文研究了利用通信压缩的分布式随机优化算法的性能上限，并提出了 NEOLITHIC 算法，该算法在温和条件下实现所建立的理论下限。

    May, 2023

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

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

    Jan, 2017

  • 去中心化随机优化和 Gossip 算法的压缩通信

    提出了一种基于 gossip 的分散随机优化算法 CHOCO-SGD 和解决平均一致性问题的新型 gossip 算法 CHOCO-GOSSIP，旨在在机器学习任务上实现数据分布和优化，有效降低通信成本并能提高算法效率。

    Feb, 2019

  • 分布式优化的线性收敛算法：免费发送更少的比特！

    提出了一种新的基于随机压缩算子的一阶随机算法和方差约简技术，能够在去除了通信中数据量的一定压缩的前提下，快速地在分散的装置上完成模型的机器学习训练并收敛于最优解。

    Nov, 2020

  • 分布式随机方差减少梯度方法与通信复杂度下限

    本论文研究了用于最小化凸函数平均值的分布式优化算法，应用于统计机器学习的经验风险最小化问题。我们设计了一种分布式随机方差减少梯度算法，其在条件数方面同时增强了最佳并行运行时间、通信量和所有分布式一阶方法的通信轮数。此外，当条件数相对于每个机器中的数据大小不太大时，我们的方法及其加速扩展还可以优于现有的分布式算法，此外，还证明了广泛分布的课程的有关通信轮数的下限。我们证明了我们的加速分布式随机方差减少梯度算法实现了这一下限，从而它使用最少的通信轮数。

    Jul, 2015

  • 分布式牛顿法通信成本降低并抵抗拜占庭工人

    我们提出了一种分布式的二阶优化算法，该算法具有通信效率和对其工作机的拜占庭故障的强鲁棒性，并通过使用一种简单的基于阈值的规则来过滤工作机来进一步压缩本地信息，由此建立了改进的收敛保证.

    Jun, 2020

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

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

    Jun, 2023

  • CORE: 分布式优化的通用随机重建算法及可证明低通信复杂度

    基于 Common randOm REconstruction (CORE) 技术，本研究提出了一种可以压缩传输信息、降低通信复杂度的分布式机器学习算法，并通过应用于线性模型和非凸优化等分布式任务，设计了新的具有更低通信复杂度的分布式算法。

    Sep, 2023

  • MG-Skip：用于非光滑分布式优化的随机多八卦跳跃方法

    基于概率局部更新的分布式优化方法在通信加速方面引起了人们的关注，然而，这种能力只在损失函数平滑且网络连接充分的情况下有效。本文提出了第一种具有概率局部更新的线性收敛方法 MG-Skip 用于非平滑分布式优化，无需额外条件对网络连接性能，大多数迭代可以跳过多轮 “传闲话” 通信，其迭代复杂度为 O (κ log (1/ε))，通信复杂度仅为 O (√(κ/(1-ρ)) log (1/ε))，其中 κ 是损失函数的条件数，ρ 反映了网络拓扑的连通性。据我们所知，当损失函数具有平滑（强凸）+ 非平滑（凸）复合形式时，MG-Skip 实现了最佳的通信复杂度。

    Dec, 2023

  • 面向更高效的随机分散式学习：更快的收敛与稀疏通信

    本研究提出了一种名为 DSBA 的随机算法，通过将分散的优化问题推广为单调算子求根问题来解决这一问题，具有线性收敛速度和只需稀疏通讯的优点，同时还能有效地处理像 AUC 最大化这样的学习问题。

    May, 2018