May, 2020

分散式有限和优化的最优算法

PDF
TL;DR本文提出了一种名为 ADFS 的高效分布式算法，利用局部碰撞更新和节点之间的分布式通信，在单机上运行时比现代加速随机算法要慢，但在 n 个机器上最小化目标函数与在一个机器上 m 个样本的最优算法相同的时间内完成。我们证明了 ADFS 是分散化算法中最佳的，并通过实验证明了 ADFS 相对于现有方法的改进。
decentralized algorithmstochastic optimizationdistributed computingaccelerationproximal updates
发现论文，激发创造
  • 分散优化中平滑强凸问题的最优实用算法

    本文提出了两种基于加速的前后向算法的分散优化新算法以解决存储在网络节点上的光滑强凸函数之和的最小化问题，并显示它们是最优的算法，具有复杂性的保证。

    Jun, 2020

  • 一种联合梯度估计和跟踪的分散非凸优化样本和通信复杂度改进方法

    该文章提出了一种名为 D-GET 的去中心化随机算法，可以提高大规模机器学习中高度非凸问题的性能，同时在减少多节点通信轮数的同时，访问最少量的局部数据样本，以实现确定性有限和在线问题的小样本复杂度和通信复杂度，并优于现有方法的复杂度。

    Oct, 2019

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

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

    Feb, 2017

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

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

    May, 2018

  • DSA：去中心化双随机平均梯度下降算法

    该论文提出了分布式双随机平均梯度算法 (DSA) 来解决大规模机器学习问题，具有线性收敛特性，相对于其他分散式随机优化方法，可以减少收敛时间和处理的功能向量数量。

    Jun, 2015

  • ADMM 在分散式一致优化中的线性收敛性

    本文研究了具有强凸局部目标函数的去中心化一致性优化问题，并建立了其线性收敛速率及加速的指导原则，其中采用了交替方向乘子方法 (ADMM) 来解决该问题，该方法可在单个代理处进行迭代计算并在邻居之间进行信息交换。

    Jul, 2013

  • 分散随机优化与梯度追踪简介

    本文综述了基于梯度追踪和方差减少的去中心化随机一阶优化方法，介绍了这些算法在去中心化机器学习模型训练中的应用。

    Jul, 2019

  • 网络分布式 ADMM 的收敛速率

    本研究提出了基于 ADMM 算法的分布式算法，用于通过网络通信最小化局部已知的凸函数之和，研究表明，在函数为凸函数时，目标函数值和可行性冲突都会收敛，当函数是强凸函数且有 Lipschitz 连续梯度时，该算法生成的序列会线性收敛到最优解。此外，我们的分析还通过节点的最大和最小度以及网络的代数连通度凸显了网络结构对收敛速度的影响。

    Jan, 2016

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

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

    Jan, 2017

  • 联邦加速随机梯度下降

    本文提出了 Federated Accelerated Stochastic Gradient Descent (FedAc)，它是 Federated Averaging (FedAvg) 的一种加速方法，可以提高收敛速度和通信效率，特别是在凸函数和三阶平滑函数上有更强的性能表现。该技术基于基于潜力的扰动迭代分析、广义加速 SGD 的新型稳定性分析和加速与稳定性之间的战略权衡。

    Jun, 2020