Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs
Abstract
We propose a novel decentralized convex optimization algorithm called ASY-DAGP, where each agent has its own distinct objective function and constraint set. Agents compute at different speeds, and their communication is delayed and directed. Employing local buffers, ASY-DAGP enhances asynchronous communication and is robust to challenging scenarios such as message failure. We validate these features by numerical experiments. By analyzing ASY-DAGP, we provide the first sublinear convergence rate for the above setup under mild assumptions. This rate depends on a novel characterization of delay profiles, which we term the delay factor. We calculate the delay factor for the well-known bounded delay profiles, providing new insights for these scenarios. Our analysis is conducted by introducing a novel approach tied to the celebrated PEP framework. Our approach does not require the design of Lyapunov functions and instead provides a novel insight into the optimization algorithms as linear systems.
Cite
Text
Shahriari-Mehr and Panahi. "Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Shahriari-Mehr and Panahi. "Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/shahriarimehr2025aistats-asynchronous/)BibTeX
@inproceedings{shahriarimehr2025aistats-asynchronous,
title = {{Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs}},
author = {Shahriari-Mehr, Firooz and Panahi, Ashkan},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {2575-2583},
volume = {258},
url = {https://mlanthology.org/aistats/2025/shahriarimehr2025aistats-asynchronous/}
}