Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
复制标题
DOI：
--
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Boyue Li;Shicong Cen;Yuxin Chen;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Boyue Li;Shicong Cen;Yuxin Chen;Yuejie Chi
对于分散网络的大规模机器学习和优化，例如在多学院学习和联合学习的背景下。由于迫在眉睫的需要减轻沟通负担，近年来，对沟通效率分布式优化算法的调查（尤其是对于经验风险最小化）近年来一直蓬勃发展。这些算法中的很大一部分是为主/从设置开发的，依赖于可以与所有代理通信的中央参数服务器。本文着重于网络上的分布式优化或分散的优化，在该优化中，每个代理只能从其邻居中汇总信息。通过与适当的校正结合使用局部平均值来正确调整全球梯度估计，我们开发了一个通信效率近似的牛顿型方法网络 - 台网，该台词将dane推广到分散的场景。我们的关键想法可以系统地应用，以获取其他主/从分布式算法的分散版本。网络SVRG/SARAH是一个值得注意的发展，它采用差异来进一步加速局部计算。我们建立了网络 - 民站和网络SVRG的线性收敛，以实现强烈凸出损失，以及用于二次损失的网络 - 萨拉，这揭示了数据同质性，网络连接性以及局部平均收敛速度的影响。我们通过允许非平滑惩罚项将Network-Dane进一步扩展到复合优化。提供了数值证据，以证明我们算法对竞争基线的算法具有吸引力的性能，从沟通和计算效率方面。我们的工作表明，每次迭代进行一定数量的本地通信和计算可以大大提高整体效率。
There is growing interest in large-scale machine learning and optimization over decentralized networks, e.g. in the context of multi-agent learning and federated learning. Due to the imminent need to alleviate the communication burden, the investigation of communication-efficient distributed optimization algorithms - particularly for empirical risk minimization - has flourished in recent years. A large fraction of these algorithms have been developed for the master/slave setting, relying on a central parameter server that can communicate with all agents. This paper focuses on distributed optimization over networks, or decentralized optimization, where each agent is only allowed to aggregate information from its neighbors. By properly adjusting the global gradient estimate via local averaging in conjunction with proper correction, we develop a communication-efficient approximate Newton-type method Network-DANE, which generalizes DANE to the decentralized scenarios. Our key ideas can be applied in a systematic manner to obtain decentralized versions of other master/slave distributed algorithms. A notable development is Network-SVRG/SARAH, which employs variance reduction to further accelerate local computation. We establish linear convergence of Network-DANE and Network-SVRG for strongly convex losses, and Network-SARAH for quadratic losses, which shed light on the impacts of data homogeneity, network connectivity, and local averaging upon the rate of convergence. We further extend Network-DANE to composite optimization by allowing a nonsmooth penalty term. Numerical evidence is provided to demonstrate the appealing performance of our algorithms over competitive baselines, in terms of both communication and computation efficiency. Our work suggests that performing a certain amount of local communications and computations per iteration can substantially improve the overall efficiency.