Subgradient-Push Is of the Optimal Convergence Rate

Yixuan Lin; Ji Liu

doi:10.1109/CDC51059.2022.9992842

Subgradient-Push Is of the Optimal Convergence Rate

Yixuan Lin
, Ji Liu

Electrical Engineering

Stony Brook University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

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(ln t/√t). This paper shows that the subgradient-push algorithm actually converges at a rate of O(1/√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.

Original language	English
Title of host publication	2022 IEEE 61st Conference on Decision and Control, CDC 2022
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	5849-5856
Number of pages	8
ISBN (Electronic)	9781665467612
DOIs	https://doi.org/10.1109/CDC51059.2022.9992842
State	Published - 2022
Event	61st IEEE Conference on Decision and Control, CDC 2022 - Cancun, Mexico Duration: Dec 6 2022 → Dec 9 2022

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2022-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	61st IEEE Conference on Decision and Control, CDC 2022
Country/Territory	Mexico
City	Cancun
Period	12/6/22 → 12/9/22

Access to Document

10.1109/CDC51059.2022.9992842

Cite this

@inproceedings{e5c3757c81d74b63a12c58e00afa243d,

title = "Subgradient-Push Is of the Optimal Convergence Rate",

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(ln t/√t). This paper shows that the subgradient-push algorithm actually converges at a rate of O(1/√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.",

author = "Yixuan Lin and Ji Liu",

note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 61st IEEE Conference on Decision and Control, CDC 2022 ; Conference date: 06-12-2022 Through 09-12-2022",

year = "2022",

doi = "10.1109/CDC51059.2022.9992842",

language = "English",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "5849--5856",

booktitle = "2022 IEEE 61st Conference on Decision and Control, CDC 2022",

}

Lin, Y & Liu, J 2022, Subgradient-Push Is of the Optimal Convergence Rate. in 2022 IEEE 61st Conference on Decision and Control, CDC 2022. Proceedings of the IEEE Conference on Decision and Control, vol. 2022-December, Institute of Electrical and Electronics Engineers Inc., pp. 5849-5856, 61st IEEE Conference on Decision and Control, CDC 2022, Cancun, Mexico, 12/6/22. https://doi.org/10.1109/CDC51059.2022.9992842

Subgradient-Push Is of the Optimal Convergence Rate. / Lin, Yixuan; Liu, Ji.
2022 IEEE 61st Conference on Decision and Control, CDC 2022. Institute of Electrical and Electronics Engineers Inc., 2022. p. 5849-5856 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2022-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Subgradient-Push Is of the Optimal Convergence Rate

AU - Lin, Yixuan

AU - Liu, Ji

PY - 2022

Y1 - 2022

N2 - 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/√t). This paper shows that the subgradient-push algorithm actually converges at a rate of O(1/√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.

AB - 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/√t). This paper shows that the subgradient-push algorithm actually converges at a rate of O(1/√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.

UR - https://www.scopus.com/pages/publications/85139147519

U2 - 10.1109/CDC51059.2022.9992842

DO - 10.1109/CDC51059.2022.9992842

M3 - Conference contribution

AN - SCOPUS:85139147519

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 5849

EP - 5856

BT - 2022 IEEE 61st Conference on Decision and Control, CDC 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 61st IEEE Conference on Decision and Control, CDC 2022

Y2 - 6 December 2022 through 9 December 2022

ER -

Subgradient-Push Is of the Optimal Convergence Rate

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this