Exact Diffusion for Distributed Optimization and Learning-Part II: Convergence Analysis

Part I of this paper developed the exact diffusion algorithm to remove the bias that is characteristic of distributed solutions for deterministic optimization problems. The algorithm was shown to be applicable to the larger set of locally balanced left-stochastic combination policies than the set of doubly-stochastic policies. These balanced policies endow the algorithm with faster convergence rate, more flexible step-size choices and better privacy-preserving properties. In this Part II, we examine the convergence and stability properties of exact diffusion in some detail and establish its linear convergence rate. We also show that it has a wider stability range than the EXTRA consensus solution, meaning that it is stable for a wider range of step-sizes and can, therefore, attain faster convergence rates. Analytical examples and numerical simulations illustrate the theoretical findings.