Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation

Thinh Doan, Justin Romberg
Proceedings of the 2nd Conference on Learning for Dynamics and Control, PMLR 120:26-36, 2020.

Abstract

Two-time-scale stochastic approximation is a popular iterative method for finding the solution of a system of two equations. Such methods have found broad applications in many areas, especially in machine learning and reinforcement learning. In this paper, we propose a distributed variant of this method over a network of agents, where the agents use two graphs representing their communication at different speeds due to the nature of their two-time-scale updates. Our main contribution is to provide a finite-time analysis for the performance of the proposed method. In particular, we establish an upper bound for the convergence rates of the mean square errors at the agents to zero as a function of the step sizes and the network topology. We believe that the proposed method and analysis studied in this paper can be applicable to many other interesting applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v120-doan20a, title = {Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation}, author = {Doan, Thinh and Romberg, Justin}, booktitle = {Proceedings of the 2nd Conference on Learning for Dynamics and Control}, pages = {26--36}, year = {2020}, editor = {Bayen, Alexandre M. and Jadbabaie, Ali and Pappas, George and Parrilo, Pablo A. and Recht, Benjamin and Tomlin, Claire and Zeilinger, Melanie}, volume = {120}, series = {Proceedings of Machine Learning Research}, month = {10--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v120/doan20a/doan20a.pdf}, url = {https://proceedings.mlr.press/v120/doan20a.html}, abstract = {Two-time-scale stochastic approximation is a popular iterative method for finding the solution of a system of two equations. Such methods have found broad applications in many areas, especially in machine learning and reinforcement learning. In this paper, we propose a distributed variant of this method over a network of agents, where the agents use two graphs representing their communication at different speeds due to the nature of their two-time-scale updates. Our main contribution is to provide a finite-time analysis for the performance of the proposed method. In particular, we establish an upper bound for the convergence rates of the mean square errors at the agents to zero as a function of the step sizes and the network topology. We believe that the proposed method and analysis studied in this paper can be applicable to many other interesting applications. } }
Endnote
%0 Conference Paper %T Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation %A Thinh Doan %A Justin Romberg %B Proceedings of the 2nd Conference on Learning for Dynamics and Control %C Proceedings of Machine Learning Research %D 2020 %E Alexandre M. Bayen %E Ali Jadbabaie %E George Pappas %E Pablo A. Parrilo %E Benjamin Recht %E Claire Tomlin %E Melanie Zeilinger %F pmlr-v120-doan20a %I PMLR %P 26--36 %U https://proceedings.mlr.press/v120/doan20a.html %V 120 %X Two-time-scale stochastic approximation is a popular iterative method for finding the solution of a system of two equations. Such methods have found broad applications in many areas, especially in machine learning and reinforcement learning. In this paper, we propose a distributed variant of this method over a network of agents, where the agents use two graphs representing their communication at different speeds due to the nature of their two-time-scale updates. Our main contribution is to provide a finite-time analysis for the performance of the proposed method. In particular, we establish an upper bound for the convergence rates of the mean square errors at the agents to zero as a function of the step sizes and the network topology. We believe that the proposed method and analysis studied in this paper can be applicable to many other interesting applications.
APA
Doan, T. & Romberg, J.. (2020). Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation. Proceedings of the 2nd Conference on Learning for Dynamics and Control, in Proceedings of Machine Learning Research 120:26-36 Available from https://proceedings.mlr.press/v120/doan20a.html.

Related Material