An improved convergence guarantee for the gradient-push algorithm with a constant stepsize

The gradient-push algorithm is a fundamental algorithm for the distributed optimization problem $$\begin{aligned} \min _{x \in {\mathbb{R}}^d} f(x) = \sum _{i=1}^n f_i (x), \end{aligned}$$ where each local cost $$f_i$$ is only known to agent $$a_i$$ for $$1 \le i \le n$$ and the agents are connected by a directed graph. In this paper, we obtain convergence results for the gradient-push algorithm with constant stepsize whose range is sharp in terms the order of the smoothness constant $$L>0$$ . Precisely, under the two settings: (1) Each local cost $$f_i$$ is strongly convex and L-smooth, (2) each local cost $$f_i$$ is convex quadratic and L-smooth while the aggregate cost f is strongly convex, we show that the gradient-push algorithm with stepsize $$\alpha>0$$ converges to an $$O(\alpha )$$ -neighborhood of the minimizer of f for a range $$\alpha \in (0, c/L]$$ with a value $$c>0$$ independent of $$L>0$$ . As a benefit of the result, we suggest a hybrid algorithm that performs the gradient-push algorithm with a relatively large stepsize $$\alpha>0$$ for a number of iterations and then go over to perform the Push-DIGing algorithm. It is verified by a numerical test that the hybrid algorithm enhances the performance of the Push-DIGing algorithm significantly. The convergence results of the gradient-push algorithm are also supported by numerical tests.