Multi-agent systems. Accuracy guarantees for a class of randomized averaging algorithms

 
Speaker:
Julien M. Hendrickx
Affiliation:
ICTEAM Institute, Université catholique de Louvain, Belgium
When:
Wednesday 10th May 2017
Time:
14:15:00
Where:
Multi-agent systems. Accuracy guarantees for a class of randomized averaging algorithms
Abstract:
We consider a class of algorithms meant for averaging data in a decentralized way, but where the value computed might differ from the real average due to asymmetric or asynchronous communications and lost messages. We provide a new general upper bound on the mean difference between the value computed and the initial average. We particularize our results to various algorithms in the literature (and their generalization), obtaining bounds that match or outperform the previously available ones, and establishing the accuracy of several methods for which the question was open. We also compare the robustness of these algorithms with that of the push-sum method, which is specifically tailored for directed asynchronous communications. Our results are based on a novel approach apparently unrelated to the convergence properties of the systems, and lead to bounds depending on local parameters easily controlled by the designer. Contatto: domenico.brunetto@polimi.it
PDF: