Subgradient-Push Is of the Optimal Convergence Rate

arXiv2203.16623MaRDI QIDQ6395204

Ji Liu, Yixuan Lin

Publication date: 30 March 2022

Abstract: 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(lnt/sqrtt)$. This paper shows that the push-subgradient algorithm actually converges at a rate of $O(1/sqrtt)$, 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.

This page was built for publication: Subgradient-Push Is of the Optimal Convergence Rate

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6395204)