Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps

在分布式机器学习中，跨越不同数据分布的多个代理进行高效训练存在重大挑战。即使有一个集中协调员，目前实现最优通信复杂度的算法通常需要大批量的小批量数据或者在梯度复杂度上做出妥协。在这项工作中，我们处理了强凸、凸和非凸目标的集中式和去中心化设置。我们首先展示了基本的原始-对偶方法，即（加速）梯度上升多随机梯度下降（GA-MSGD），应用于分布式优化的拉格朗日函数时，由于在原始变量上运行随机梯度下降的内部循环不需要代理间通信，因此本质上包含了局部更新。值得注意的是，对于强凸目标，我们展示了（加速）GA-MSGD在通信回合中实现了线性收敛，尽管拉格朗日函数仅在对偶变量中是线性的。这是由于一种独特的结构性质，即对偶变量被限制在耦合矩阵的范围内，使得对偶问题强凸。当与Catalyst框架集成时，我们的方法在各种设置中实现了接近最优的通信复杂度，而无需小批量数据。此外，在随机去中心化问题中，它实现了与确定性设置中相当的通信复杂度，优于现有算法。

解决分布式机器学习中，不同数据分布的多个代理之间进行高效训练的问题。目前的算法要么需要大批量数据，要么需要降低梯度复杂度才能达到最优通信复杂度。

本文提出了基于Lagrangian的原始-对偶方法（加速）梯度上升多随机梯度下降（GA-MSGD），通过在原始变量上运行随机梯度下降的内部循环，实现了本地更新。对于强凸目标，本文证明（加速）GA-MSGD在通信轮次上实现了线性收敛，这是由于对偶变量被限制在耦合矩阵的范围内，使得对偶问题强凸。结合Catalyst框架，本文的方法在各种设置下实现了几乎最优的通信复杂度，无需小批量数据。此外，在随机分散问题中，它实现了与确定性设置中相当的通信复杂度，改进了现有算法。

本文的方法不需要大批量数据，同时可以实现几乎最优的通信复杂度。在随机分散问题中，它实现了与确定性设置中相当的通信复杂度。本文的方法可以结合Catalyst框架使用。本文的方法具有良好的收敛性能。

在分布式机器学习领域，还有许多相关研究。例如，A decentralized primal-dual method for constrained optimization with large-scale datasets（2018），Communication-Efficient Distributed Optimization using an Approximate Newton-type Method（2019），Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss（2019）等。