DASA: Delay-Adaptive Multi-Agent Stochastic Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911974982418432 |
|---|---|
| author | Fabbro, Nicolò Dal Adibi, Arman Poor, H. Vincent Kulkarni, Sanjeev R. Mitra, Aritra Pappas, George J. |
| author_facet | Fabbro, Nicolò Dal Adibi, Arman Poor, H. Vincent Kulkarni, Sanjeev R. Mitra, Aritra Pappas, George J. |
| contents | We consider a setting in which $N$ agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt{DASA}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt{DASA} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt{DASA} is the first algorithm whose convergence rate depends only on the mixing time $τ_{mix}$ and on the average delay $τ_{avg}$ while jointly achieving an $N$-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17247 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | DASA: Delay-Adaptive Multi-Agent Stochastic Approximation Fabbro, Nicolò Dal Adibi, Arman Poor, H. Vincent Kulkarni, Sanjeev R. Mitra, Aritra Pappas, George J. Artificial Intelligence Robotics Systems and Control Optimization and Control Machine Learning We consider a setting in which $N$ agents aim to speedup a common Stochastic Approximation (SA) problem by acting in parallel and communicating with a central server. We assume that the up-link transmissions to the server are subject to asynchronous and potentially unbounded time-varying delays. To mitigate the effect of delays and stragglers while reaping the benefits of distributed computation, we propose \texttt{DASA}, a Delay-Adaptive algorithm for multi-agent Stochastic Approximation. We provide a finite-time analysis of \texttt{DASA} assuming that the agents' stochastic observation processes are independent Markov chains. Significantly advancing existing results, \texttt{DASA} is the first algorithm whose convergence rate depends only on the mixing time $τ_{mix}$ and on the average delay $τ_{avg}$ while jointly achieving an $N$-fold convergence speedup under Markovian sampling. Our work is relevant for various SA applications, including multi-agent and distributed temporal difference (TD) learning, Q-learning and stochastic optimization with correlated data. |
| title | DASA: Delay-Adaptive Multi-Agent Stochastic Approximation |
| topic | Artificial Intelligence Robotics Systems and Control Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2403.17247 |