<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1506_Article_IEq1.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha >0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>α</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> converges exponentially fast to an <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1506_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$O(\alpha )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>α</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-neighborhood of the optimizer if the stepsize <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10898_2025_1506_Article_IEq3.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="14" /> </InlineMediaObject> <EquationSource Format="TEX">$\alpha $</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> 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.</p>

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

期刊论文
发表日期：

2025年5月22日

查看全文

Woocheol Choi,
Doheon Kim,
Seok-Bae Yun

摘要

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.