On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias
This work provides theoretical guarantees for decentralized algorithms in machine learning and multi-agent systems, though it is incremental as it extends existing centralized results to a decentralized setting.
The paper tackles the problem of analyzing convergence rates for decentralized stochastic approximation algorithms under Markovian noise and time-varying communication graphs, achieving an expected convergence rate of O(log T / sqrt(T)) for non-convex cost functions.
This paper presents a finite time convergence analysis for a decentralized stochastic approximation (SA) scheme. The scheme generalizes several algorithms for decentralized machine learning and multi-agent reinforcement learning. Our proof technique involves separating the iterates into their respective consensual parts and consensus error. The consensus error is bounded in terms of the stationarity of the consensual part, while the updates of the consensual part can be analyzed as a perturbed SA scheme. Under the Markovian noise and time varying communication graph assumptions, the decentralized SA scheme has an expected convergence rate of ${\cal O}(\log T/ \sqrt{T} )$, where $T$ is the iteration number, in terms of squared norms of gradient for nonlinear SA with smooth but non-convex cost function. This rate is comparable to the best known performances of SA in a centralized setting with a non-convex potential function.