Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs

Firooz Shahriari-Mehr, Ashkan Panahi
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:2575-2583, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v258-shahriari-mehr25a, 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}, pages = {2575--2583}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/shahriari-mehr25a/shahriari-mehr25a.pdf}, url = {https://proceedings.mlr.press/v258/shahriari-mehr25a.html}, 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.} }
Endnote
%0 Conference Paper %T Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs %A Firooz Shahriari-Mehr %A Ashkan Panahi %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-shahriari-mehr25a %I PMLR %P 2575--2583 %U https://proceedings.mlr.press/v258/shahriari-mehr25a.html %V 258 %X 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.
APA
Shahriari-Mehr, F. & Panahi, A.. (2025). Asynchronous Decentralized Optimization with Constraints: Achievable Speeds of Convergence for Directed Graphs. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:2575-2583 Available from https://proceedings.mlr.press/v258/shahriari-mehr25a.html.

Related Material