2024/07/18 by H S Choi, Choi, Hyogi, Woocheol Choi +3
Computer Science · Engineering · #Advanced Vision and Imaging #FOS: Electrical engineering #FOS: Mathematics #Image Processing Techniques and Applications #Image and Video Stabilization #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2407.13564
openalex publication_date 2024/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The gradient-push algorithm is a fundamental algorithm for the distributed optimization problem minx ∈ ℝd f(x) = ∑j=1n fj (x), where each local cost fj is only known to agent ai for 1 ≤ i ≤ 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 fi is strongly convex and L-smooth, 2) Each local cost fi is convex quadratic and L-smooth while the aggregate cost f is strongly convex, we show that the gradient-push algorithm with stepsize α>0 converges to an O(α)-neighborhood of the minimizer of f for a range α∈ (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 α>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.