On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias

Abstract

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 $\mathcal{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.

Accepted to IEEE CDC 2020. 16 pages. FIxed a few typos

References in corpus (12)

• D${}^2$: Decentralized Training over Decentralized Data
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Convergence of adaptive and interacting Markov chain Monte Carlo algorithms
• Non-asymptotic Analysis of Biased Stochastic Approximation Scheme
• Distributed stochastic optimization with gradient tracking over strongly-connected networks
• Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
• Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomness
• Non-asymptotic Error Bounds For Constant Stepsize Stochastic Approximation For Tracking Mobile Agents
• Decentralized Markov Chain Gradient Descent
• Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation
• Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning
• A Distributed Stochastic Gradient Tracking Method