论文标题
亚级别 - 乘以最佳收敛速率
Subgradient-Push Is of the Optimal Convergence Rate
论文作者
论文摘要
基于推送的亚级别是在不平衡的有向图上进行分布式凸优化的重要方法，该图的分布式凸优化是以$ o（\ ln t/\ sqrt {t}）$的速率收敛的。本文表明，亚级别push算法实际上以$ o（1/\ sqrt {t}）$的速率收敛，该算法与单人亚级别的速率相同，因此相同。提出的用于分析基于推和的算法的工具具有独立的兴趣。
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(\ln t/\sqrt{t})$. This paper shows that the subgradient-push algorithm actually converges at a rate of $O(1/\sqrt{t})$, 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.
