具有理论保证的压缩通信分布式求解变分不等式方法

Oct, 2021

具有理论保证的压缩通信分布式求解变分不等式方法

Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees

Aleksandr Beznosikov, Peter Richtárik, Michael Diskin, Max Ryabinin, Alexander Gasnikov

TL;DR本文介绍了使用压缩通信解决变分不等式和鞍点问题的分布式方法：MASHA1 和 MASHA2，并通过两个实验验证了结论的正确性。

Abstract

variational inequalities in general and saddle point problems in particular are increasingly relevant in machine learning applications, including

variational inequalities saddle point problems distributed computing compressed communication adversarial learning

发现论文，激发创造

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

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

Jun, 2023

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

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

Jul, 2015

DASHA：分布式非凸优化，包含通信压缩，最优化 Oracle 复杂度，无须客户端同步

我们开发和分析了 DASHA：一种新的非凸分布式优化问题方法，同时考虑了通信复杂度和理论 oracle。我们的新方法改善了以前的最先进的方法，特别是在有限和期望形式的本地函数的情况下。新的方法发送压缩向量，并且永远不会同步节点，这使得它们对联邦学习更加实用。我们还将结果扩展到满足 Polyak-Lojasiewicz 条件的情况。在分类和深度学习模型的培训实验中，实践证实了我们的理论。

Feb, 2022

压缩梯度的分布式学习

该论文提出了一种针对大规模机器学习的分布式梯度方法的统一分析框架，通过非渐进界限来推导了几种优化算法的收敛速率和信息交换，并得到了步长的显式表达式，表征了异步度和压缩精度如何影响迭代和通信复杂性保证，数值结果证实了限制信息交换下不同梯度压缩算法的收敛性能，以及快速收敛确实是可能的。

Jun, 2018

压缩联邦学习：统一分析和精确保证

通过定期压缩通信的算法，分析其收敛性并探讨其与局部计算的关系，提出了一种本地梯度追踪方案，以缓解数据异质性，实现了更快的收敛速度和更好的算法效果。

Jul, 2020

分布式随机优化中的下限与通信压缩加速算法

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

May, 2023

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

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