On The Convergence Of Consensus Algorithms With Markovian Noise And Gradient Bias
2020 · Hoi-To Wai
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 \(\{\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.
Authors
(none)
Tags
Stats
Related papers
- Finite Time Analysis Of Linear Two-timescale Stochastic Approximation With Markovian Noise (2020)0.00
- Non-asymptotic Analysis Of Biased Stochastic Approximation Scheme (2019)0.00
- Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
- Finite-sample Analysis Of Nonlinear Stochastic Approximation With Applications In Reinforcement Learning (2019)10.35
- Asynchronous Stochastic Approximations With Asymptotically Biased Errors And Deep Multi-agent Learning (2018)0.00
- Convergence Of Decentralized Actor-critic Algorithm In General-sum Markov Games (2024)3.58
- Almost Sure Convergence Rates And Concentration Of Stochastic Approximation And Reinforcement Learning With Markovian Noise (2024)0.00
- Central Limit Theorem For Two-timescale Stochastic Approximation With Markovian Noise: Theory And Applications (2024)0.00