Enhancing Parallelism in Decentralized Stochastic Convex Optimization

Ofri Eisen, Ron Dorfman, Kfir Yehuda Levy
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:15105-15129, 2025.

Abstract

Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-eisen25a, title = {Enhancing Parallelism in Decentralized Stochastic Convex Optimization}, author = {Eisen, Ofri and Dorfman, Ron and Levy, Kfir Yehuda}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {15105--15129}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/eisen25a/eisen25a.pdf}, url = {https://proceedings.mlr.press/v267/eisen25a.html}, abstract = {Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.} }
Endnote
%0 Conference Paper %T Enhancing Parallelism in Decentralized Stochastic Convex Optimization %A Ofri Eisen %A Ron Dorfman %A Kfir Yehuda Levy %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-eisen25a %I PMLR %P 15105--15129 %U https://proceedings.mlr.press/v267/eisen25a.html %V 267 %X Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.
APA
Eisen, O., Dorfman, R. & Levy, K.Y.. (2025). Enhancing Parallelism in Decentralized Stochastic Convex Optimization. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:15105-15129 Available from https://proceedings.mlr.press/v267/eisen25a.html.

Related Material