On the convergence result of the gradient-push algorithm on directed graphs with constant stepsize

Woocheol Choi (), Doheon Kim () and Seok-Bae Yun ()
Additional contact information
Woocheol Choi: Sungkyunkwan University
Doheon Kim: Hanyang University
Seok-Bae Yun: Sungkyunkwan University

Journal of Global Optimization, 2025, vol. 92, issue 3, No 8, 713-736

Abstract: Abstract Distributed optimization has received a lot of interest due to its wide applications in various fields. It involves multiple agents connected by a graph that optimize a total cost in a collaborative way. Often, in applications, the graph of the agents is a directed graph. The gradient-push algorithm is a fundamental algorithm for distributed optimization when the agents are connected by a directed graph. Despite its wide usage in the literature, its convergence property has not been well established for the important case where the stepsize is constant and the domain is the entire space. This work proves that the gradient-push algorithm with stepsize $$\alpha >0$$ α > 0 converges exponentially fast to an $$O(\alpha )$$ O ( α ) -neighborhood of the optimizer if the stepsize $$\alpha $$ α is less than a specific value. For the result, we assume that each cost is smooth and the total cost is strongly convex. Numerical experiments are provided to support the theoretical convergence result. We also present a numerical test showing that the gradient-push algorithm may approach a small neighborhood of the minimizer faster than the Push-DIGing algorithm which is a variant of the gradient-push algorithm which involves agents sharing their gradient information.

Keywords: Gradient-push algorithm; Push-sum algorithm; Convex optimization; Primary 90C25; 68Q25 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01506-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:3:d:10.1007_s10898-025-01506-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01506-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().