Lighter-Communication Distributed Machine Learning via Sufficient Factor Broadcasting

Pengtao Xie Carnegie Mellon University, Jin Kyu Kim Carnegie Mellon University, Yi Zhou Syracuse University, Qirong Ho, Abhimanu Kumar Groupon Inc., Yaoliang Yu, Eric Xing Carnegie Mellon University
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:28-37, 2016.

Abstract

Matrix-parametrized models (MPMs) are widely used in machine learning (ML) applications. In large-scale ML problems, the parameter matrix of a MPM can grow at an unexpected rate, resulting in high communication and parameter synchronization costs. To address this issue, we offer two contributions: first, we develop a computation model for a large family of MPMs, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, \ie the outer product of two “sufficient factors" (SFs). Second, we implement a decentralized, peer-to-peer system, Sufficient Factor Broadcasting (SFB), which broadcasts the SFs among worker machines, and reconstructs the update matrices locally at each worker. SFB takes advantage of small rank-1 matrix updates and efficient partial broadcasting strategies to dramatically improve communication efficiency. We propose a graph optimization based partial broadcasting scheme, which minimizes the delay of information dissemination under the constraint that each machine only communicates with a subset rather than all of machines. Furthermore, we provide theoretical analysis to show that SFB guarantees convergence of algorithms (under full broadcasting) without requiring a centralized synchronization mechanism. Experiments corroborate SFB’s efficiency on four MPMs.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-university16a, title = {Lighter-Communication Distributed Machine Learning via Sufficient Factor Broadcasting}, author = {University, Pengtao Xie Carnegie Mellon and University, Jin Kyu Kim Carnegie Mellon and University, Yi Zhou Syracuse and Ho, Qirong and Inc., Abhimanu Kumar Groupon and Yu, Yaoliang and University, Eric Xing Carnegie Mellon}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {28--37}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/university16a/university16a.pdf}, url = {https://proceedings.mlr.press/r14/university16a.html}, abstract = {Matrix-parametrized models (MPMs) are widely used in machine learning (ML) applications. In large-scale ML problems, the parameter matrix of a MPM can grow at an unexpected rate, resulting in high communication and parameter synchronization costs. To address this issue, we offer two contributions: first, we develop a computation model for a large family of MPMs, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, \ie the outer product of two “sufficient factors" (SFs). Second, we implement a decentralized, peer-to-peer system, Sufficient Factor Broadcasting (SFB), which broadcasts the SFs among worker machines, and reconstructs the update matrices locally at each worker. SFB takes advantage of small rank-1 matrix updates and efficient partial broadcasting strategies to dramatically improve communication efficiency. We propose a graph optimization based partial broadcasting scheme, which minimizes the delay of information dissemination under the constraint that each machine only communicates with a subset rather than all of machines. Furthermore, we provide theoretical analysis to show that SFB guarantees convergence of algorithms (under full broadcasting) without requiring a centralized synchronization mechanism. Experiments corroborate SFB’s efficiency on four MPMs.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Lighter-Communication Distributed Machine Learning via Sufficient Factor Broadcasting %A Pengtao Xie Carnegie Mellon University %A Jin Kyu Kim Carnegie Mellon University %A Yi Zhou Syracuse University %A Qirong Ho %A Abhimanu Kumar Groupon Inc. %A Yaoliang Yu %A Eric Xing Carnegie Mellon University %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-university16a %I PMLR %P 28--37 %U https://proceedings.mlr.press/r14/university16a.html %V R14 %X Matrix-parametrized models (MPMs) are widely used in machine learning (ML) applications. In large-scale ML problems, the parameter matrix of a MPM can grow at an unexpected rate, resulting in high communication and parameter synchronization costs. To address this issue, we offer two contributions: first, we develop a computation model for a large family of MPMs, which share the following property: the parameter update computed on each data sample is a rank-1 matrix, \ie the outer product of two “sufficient factors" (SFs). Second, we implement a decentralized, peer-to-peer system, Sufficient Factor Broadcasting (SFB), which broadcasts the SFs among worker machines, and reconstructs the update matrices locally at each worker. SFB takes advantage of small rank-1 matrix updates and efficient partial broadcasting strategies to dramatically improve communication efficiency. We propose a graph optimization based partial broadcasting scheme, which minimizes the delay of information dissemination under the constraint that each machine only communicates with a subset rather than all of machines. Furthermore, we provide theoretical analysis to show that SFB guarantees convergence of algorithms (under full broadcasting) without requiring a centralized synchronization mechanism. Experiments corroborate SFB’s efficiency on four MPMs. %Z Reissued by PMLR on 04 October 2026.
APA
University, P.X.C.M., University, J.K.K.C.M., University, Y.Z.S., Ho, Q., Inc., A.K.G., Yu, Y. & University, E.X.C.M.. (2016). Lighter-Communication Distributed Machine Learning via Sufficient Factor Broadcasting. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:28-37 Available from https://proceedings.mlr.press/r14/university16a.html. Reissued by PMLR on 04 October 2026.

Related Material