使用不精确 Prox 的 Primal-Dual 加速算法加速本地梯度方法的通讯

MMJul, 2022

使用不精确 Prox 的 Primal-Dual 加速算法加速本地梯度方法的通讯

Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox

Abdurakhmon Sadiev, Dmitry Kovalev, Peter Richtárik

TL;DR本文提出一种新的算法，基于 Chambolle 和 Pock (2011) 的方法，在一些非平滑的强凸共轭鞍点问题上的表现优于 ProxSkip。该算法在联邦学习中的应用需要较少的本地步骤，并且是一种确定性方法，而且也适用于连接网络上的优化。

Abstract

Inspired by a recent breakthrough of Mishchenko et al (2022), who for the first time showed that local gradient steps can lead to provable communication acceleration, we propose an alternative algorithm which obtains the same communication acceleration as their method (ProxSkip). Our a

communication acceleration proximal gradient strongly convex-concave saddle-point problems federated learning bilinear coupling

发现论文，激发创造

ProxSkip：局部梯度步骤可证明提高通信加速！终于！

ProxSkip 是一种简单且高效的方法，用于减小平滑函数 (f) 和昂贵的不平滑的可逼近函数 (psi) 函数的总和。这种方法可以有效地加速通信复杂度，特别适用于联邦学习的情况。

Feb, 2022

分布式优化加速：基于原始对偶视角的局部步骤

在分布式机器学习中，有效地进行具有不同数据分布的多个代理的训练面临着重大挑战。本研究解决了分布式优化问题中的集中式和分散式设置，并提出了一种基于原始对偶方法的新方法，即（加速）梯度上升的多随机梯度下降（GA-MSGD），它自然地融合了本地更新，实现了线性收敛，并且几乎达到了最优的通信复杂性。

Jul, 2024

一种快速的分布式近端梯度法

该研究提出了一种基于分布式近端梯度方法来优化平均凸函数的方法，每个凸函数都是网络中各个代理的本地目标函数。该方法通过交换估计值来实现每个代理迭代更新全局最小值的目标，并使用 Nesterov-type 加速技术和多个通信步骤进行迭代，表明这种方法的收敛速率为 1/k（其中 k 是代理之间的通信轮数），这比现有的分布式方法的收敛速度更快。数值实验也验证了该方法的卓越收敛速度。

Oct, 2012

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

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

Feb, 2017

具有线性收敛率的分散近端梯度算法

本文研究了一类非光滑的分散式多智能体最优化问题，该代理旨在最小化局部强凸光滑组成部分和一个共同的非光滑项。我们提出了一个通用的原始对偶算法框架，统一了许多现有的最先进的算法。我们在非光滑项存在的情况下，证明了所提出的方法向确切解的线性收敛。此外，对于更一般的具有代理特定非光滑术语的问题类，我们展示了使用光滑和非光滑部分的梯度和临界映射的算法类别的线性收敛在最坏的情况下无法实现。我们进一步提供了一个数字反例，展示了某些最先进的算法如何在强凸目标和不同的局部非光滑项的情况下无法线性收敛。

Sep, 2019

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

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

Jan, 2017

分布式变分不等式的通信高效梯度下降方法：统一分析与本地更新

针对分布式变分不等式问题提出了一种统一的收敛分析方法和几种新的本地训练算法，采用了一般的随机估计假设，证明了算法的收敛性，同时解决了分布式最小化和最大化优化问题。

Jun, 2023

DADAO: 分离的加速去中心化异步优化

DADAO 是第一个分布式异步算法，可通过分别使用独立的泊松点过程模拟本地梯度更新和闲话通信过程进行并行计算和加速通信，而不需要使用内部循环或其他特定机制，例如误差反馈，梯度跟踪或近端算子。

Jul, 2022

分布式和联合优化中压缩梯度下降的加速

本文提出了第一种加速压缩梯度下降方法 (ACGD)，并在实验中证实了在分布式学习问题中，ACGD 具有实际优越性，并提出了分布式 ACGD 的变体。

Feb, 2020

自适应近端梯度方法用于凸优化

本文探讨了凸优化中的两个基本一阶算法，梯度下降法（GD）和近端梯度法（ProxGD）。我们着重于通过利用光滑函数的局部曲率信息，使这些算法完全自适应。我们提出了基于观察到的梯度差异的 GD 和 ProxGD 的自适应版本，因此没有额外的计算成本。此外，我们证明了方法的收敛性，仅需假设梯度在局部利普希茨连续。此外，所提出的版本允许使用比 [MM20] 最初建议的更大的步长。

Aug, 2023