ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS

ACHIEVING GEOMETRIC CONVERGENCE FOR DISTRIBUTED OPTIMIZATION OVER TIME-VARYING GRAPHS

20 Mar 2017 | ANGELIA NEDIĆ, ALEX OLSHEVSKY, AND WEI SHI
This paper addresses the problem of distributed optimization over time-varying graphs, focusing on both undirected and directed graphs. For undirected graphs, a distributed algorithm called DIGing is introduced, which combines a distributed inexact gradient method with a gradient tracking technique. DIGing uses doubly stochastic mixing matrices and fixed step-sizes to drive all agents' iterates to a global and consensual minimizer. For directed graphs, the Push-DIGing algorithm is proposed, which incorporates the push-sum protocol into the DIGing structure, using column stochastic matrices and fixed step-sizes. Both algorithms achieve R-linear (geometric) convergence rates under strong convexity assumptions, with explicit estimates for the convergence rates provided. The paper also demonstrates that DIGing scales polynomially in the number of agents for undirected graphs. Numerical experiments validate the theoretical findings.This paper addresses the problem of distributed optimization over time-varying graphs, focusing on both undirected and directed graphs. For undirected graphs, a distributed algorithm called DIGing is introduced, which combines a distributed inexact gradient method with a gradient tracking technique. DIGing uses doubly stochastic mixing matrices and fixed step-sizes to drive all agents' iterates to a global and consensual minimizer. For directed graphs, the Push-DIGing algorithm is proposed, which incorporates the push-sum protocol into the DIGing structure, using column stochastic matrices and fixed step-sizes. Both algorithms achieve R-linear (geometric) convergence rates under strong convexity assumptions, with explicit estimates for the convergence rates provided. The paper also demonstrates that DIGing scales polynomially in the number of agents for undirected graphs. Numerical experiments validate the theoretical findings.
Reach us at info@study.space