论文标题
平均算法收敛速率的几何界限
Geometric Bounds for Convergence Rates of Averaging Algorithms
论文作者
论文摘要
我们开发了一种通用方法，以界定具有随时间变化的网络的多代理系统中运行的平均算法的收敛速率，在该系统中，相关随机矩阵具有时间独立的Perron vector。该方法提供了统一和完善大多数先前已知界限的收敛速率的界限。它们取决于动态通信图的几何参数，例如归一化直径或瓶颈量度。 作为这些几何范围的推论，我们表明，在$ n $代理系统系统中，大都市算法的收敛速率与任何可能及时变化但已永久连接和双向的通信图的$ 1-1/4N^2 $少于$ 1-1/4N^2 $。在其他假设下，我们证明了相似的算法的相似上限，即每个代理的邻居数量是恒定的，并且通信图并不过于规则。此外，我们的界限为几种平均算法和特定的通信图系列提供了提高的收敛率。 最后，我们将方法扩展到了时变的perron载体，并显示收敛时间如何显着下降，甚至有限的perron载体变化。
We develop a generic method for bounding the convergence rate of an averaging algorithm running in a multi-agent system with a time-varying network, where the associated stochastic matrices have a time-independent Perron vector. This method provides bounds on convergence rates that unify and refine most of the previously known bounds. They depend on geometric parameters of the dynamic communication graph such as the normalized diameter or the bottleneck measure. As corollaries of these geometric bounds, we show that the convergence rate of the Metropolis algorithm in a system of $n$ agents is less than $1-1/4n^2$ with any communication graph that may vary in time, but is permanently connected and bidirectional. We prove a similar upper bound for the EqualNeighbor algorithm under the additional assumptions that the number of neighbors of each agent is constant and that the communication graph is not too irregular. Moreover our bounds offer improved convergence rates for several averaging algorithms and specific families of communication graphs. Finally we extend our methodology to a time-varying Perron vector and show how convergence times may dramatically degrade with even limited variations of Perron vectors.
