Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs

This paper considers the problem of distributed optimization over time-varying graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, based on a combination of a distributed inexact gradient method and a gradient tracking technique. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all the agents' iterates to a global and consensual minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining the Push-DIGing algorithm. Push-DIGing uses…

• NS
  National Science Foundation

  Award: CNS 15-44953
• UA
  U.S. Air Force

  Award: AF FA95501510394
• OO
  Office of Naval Research

  Award: N00014-12-1-0998