Subgradient-Push Is of the Optimal Convergence Rate
| Autor: | Lin, Yixuan, Liu, Ji |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: We correct the term "push-subgradient" to "subgradient-push" in this version |
| Databáze: | arXiv |
| Externí odkaz: |
|