Delay-agnostic Asynchronous Coordinate Update Algorithm

Xuyang Wu, Changxin Liu, Sindri Magnússon, Mikael Johansson
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:37582-37606, 2023.

Abstract

We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges with both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-wu23n, title = {Delay-agnostic Asynchronous Coordinate Update Algorithm}, author = {Wu, Xuyang and Liu, Changxin and Magn\'{u}sson, Sindri and Johansson, Mikael}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {37582--37606}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/wu23n/wu23n.pdf}, url = {https://proceedings.mlr.press/v202/wu23n.html}, abstract = {We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges with both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.} }
Endnote
%0 Conference Paper %T Delay-agnostic Asynchronous Coordinate Update Algorithm %A Xuyang Wu %A Changxin Liu %A Sindri Magnússon %A Mikael Johansson %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-wu23n %I PMLR %P 37582--37606 %U https://proceedings.mlr.press/v202/wu23n.html %V 202 %X We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges with both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.
APA
Wu, X., Liu, C., Magnússon, S. & Johansson, M.. (2023). Delay-agnostic Asynchronous Coordinate Update Algorithm. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:37582-37606 Available from https://proceedings.mlr.press/v202/wu23n.html.

Related Material