Subgradient-Push Is of the Optimal Convergence Rate
Subgradient-Push Is of the Optimal Convergence Rate
复制标题
DOI：
10.1109/cdc51059.2022.9992842
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Yixuan Lin;Ji Liu
中科院分区：
文献类型：
--
作者：
Yixuan Lin;Ji Liu
基于推和的次梯度法是求解非平衡有向图上分布凸优化问题的一种重要方法，其收敛速度为O\left（{\ln t/\sqrt t } \right）$。本文表明，subgradient-push算法实际上以O\left（{1/\sqrt t } \right）$的速度收敛，这与单智能体subgradient算法相同，因此是最优的。所提出的工具，用于分析推和算法是独立的利益。
The push-sum based subgradient is an important method for distributed convex optimization over unbalanced directed graphs, which is known to converge at a rate of $O\left( {\ln t/\sqrt t } \right)$. This paper shows that the subgradient-push algorithm actually converges at a rate of $O\left( {1/\sqrt t } \right)$, which is the same as that of the single-agent subgradient and thus optimal. The proposed tool for analyzing push-sum based algorithms is of independent interest.