Seminar Details
2021-09-21 (14h) : From theoretical to computable convergence rate of push-sum for consensus
At Euler building (room a.002)
Organized by Mathematical Engineering
Speaker :
Gerencser, Balazs
Abstract :
We know that reaching average consensus using only local communication along a network is a fundamental building block in the area of distributed computing, leading to applications such as sensor fusion and distributed optimization.
We currently analyze schemes based on one such protocol, push-sum, and our target is to understand their convergence speed. We prove a bound on the almost sure convergence rate that is also computable for a class of push-sum algorithms. This extends the works of Iutzeler, Ciblat and Hachem (2013) on similar bounds but in a more restrictive setup and conclusion, and complements the results of Gerencsér and Gerencsér (2019) identifying the exact convergence rate but providing no computable access or approximation