Low Complexity Convergence Rate Bounds for the Synchronous Gossip Subclass of Push-Sum Algorithms

We develop easily accessible quantities for bounding the almost sure exponential convergence rate of push-sum algorithms. We analyze the scenario of i.i.d. synchronous gossip, every agent communicating independently towards at most a single target at every step. Multiple bounding expressions are developed depending on the generality of the setup, all functions of the network’s spectrum. Numerical experiments demonstrate the quality of the bounds obtained together with the computational speedup for acquiring them.