Computable convergence rate bound for ratio consensus algorithms

2021/04/10 by Gerencsér, Balázs · 1 citation
#37A25 (Primary) 90B18 #68W15 (Secondary) #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR)

paper · doi:10.48550/arxiv.2104.04802

Abstract

The objective of the paper is to establish a computable upper bound for the almost sure convergence rate for a class of ratio consensus algorithms defined via column-stochastic matrices. Our result extends the works of Iutzeler et al. (2013) on similar bounds that have been obtained in a more restrictive setup with limited conclusions. The present paper complements the results of Gerencsér and Gerencsér (2021), identifying the exact almost sure convergence rate of a wide class of ratio consensus algorithms in terms of a spectral gap, which is, however, not computable in general. The upper bound provided in the paper will be compared to the actual rate of almost sure convergence experimentally on a range of modulated random geographic graphs with random local interactions.

Cited by

• Low complexity convergence rate bounds for push-sum algorithms with homogeneous correlation structure

Related

• Tight bounds on the convergence rate of generalized ratio consensus\n algorithms
• Consensus Seminorms and their Applications
• On the convergence of weighted-average consensus
• On the Influence of Noise in Randomized Consensus Algorithms
• Convergence Rate Estimates for Consensus over Random Graphs