Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909063409827840 |
|---|---|
| author | Shahriari-Mehr, Firooz Panahi, Ashkan |
| author_facet | Shahriari-Mehr, Firooz Panahi, Ashkan |
| contents | We address a decentralized convex optimization problem, where every agent has its unique local objective function and constraint set. Agents compute at different speeds, and their communication may be delayed and directed. For this setup, we propose an asynchronous double averaging and gradient projection (ASY-DAGP) algorithm. Our algorithm handles difficult scenarios such as message failure, by employing local buffers and utilizing the temporal correlation in the transmitted messages. We guarantee the convergence speed of our algorithm using performance estimation problems (PEP). In particular, we introduce the concept of the linear quadratic (LQ) PEP. This approach simplifies the analysis of smooth convex optimization problems, going beyond Lyapunov function analyses and avoiding restrictive assumptions such as strong-convexity. Numerical experiments validate the effectiveness of our proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03136 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs Shahriari-Mehr, Firooz Panahi, Ashkan Optimization and Control We address a decentralized convex optimization problem, where every agent has its unique local objective function and constraint set. Agents compute at different speeds, and their communication may be delayed and directed. For this setup, we propose an asynchronous double averaging and gradient projection (ASY-DAGP) algorithm. Our algorithm handles difficult scenarios such as message failure, by employing local buffers and utilizing the temporal correlation in the transmitted messages. We guarantee the convergence speed of our algorithm using performance estimation problems (PEP). In particular, we introduce the concept of the linear quadratic (LQ) PEP. This approach simplifies the analysis of smooth convex optimization problems, going beyond Lyapunov function analyses and avoiding restrictive assumptions such as strong-convexity. Numerical experiments validate the effectiveness of our proposed algorithm. |
| title | Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2401.03136 |