Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls

Jiacheng Zhuo, Qi Lei, Alex Dimakis, Constantine Caramanis
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1464-1474, 2020.

Abstract

Large-scale machine learning training suffers from two prior challenges, specifically for nuclear-norm constrained problems with distributed systems: the synchronization slowdown due to the straggling workers, and high communication costs. In this work, we propose an asynchronous Stochastic Frank Wolfe (SFW-asyn) method, which, for the first time, solves the two problems simultaneously, while successfully maintaining the same convergence rate as the vanilla SFW. We implement our algorithm in python (with MPI) to run on Amazon EC2, and demonstrate that SFW-asyn yields speed-ups almost linear to the number of machines compared to the vanilla SFW.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-zhuo20a, title = {Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls}, author = {Zhuo, Jiacheng and Lei, Qi and Dimakis, Alex and Caramanis, Constantine}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1464--1474}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/zhuo20a/zhuo20a.pdf}, url = {https://proceedings.mlr.press/v108/zhuo20a.html}, abstract = {Large-scale machine learning training suffers from two prior challenges, specifically for nuclear-norm constrained problems with distributed systems: the synchronization slowdown due to the straggling workers, and high communication costs. In this work, we propose an asynchronous Stochastic Frank Wolfe (SFW-asyn) method, which, for the first time, solves the two problems simultaneously, while successfully maintaining the same convergence rate as the vanilla SFW. We implement our algorithm in python (with MPI) to run on Amazon EC2, and demonstrate that SFW-asyn yields speed-ups almost linear to the number of machines compared to the vanilla SFW.} }
Endnote
%0 Conference Paper %T Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls %A Jiacheng Zhuo %A Qi Lei %A Alex Dimakis %A Constantine Caramanis %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-zhuo20a %I PMLR %P 1464--1474 %U https://proceedings.mlr.press/v108/zhuo20a.html %V 108 %X Large-scale machine learning training suffers from two prior challenges, specifically for nuclear-norm constrained problems with distributed systems: the synchronization slowdown due to the straggling workers, and high communication costs. In this work, we propose an asynchronous Stochastic Frank Wolfe (SFW-asyn) method, which, for the first time, solves the two problems simultaneously, while successfully maintaining the same convergence rate as the vanilla SFW. We implement our algorithm in python (with MPI) to run on Amazon EC2, and demonstrate that SFW-asyn yields speed-ups almost linear to the number of machines compared to the vanilla SFW.
APA
Zhuo, J., Lei, Q., Dimakis, A. & Caramanis, C.. (2020). Communication-Efficient Asynchronous Stochastic Frank-Wolfe over Nuclear-norm Balls. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1464-1474 Available from https://proceedings.mlr.press/v108/zhuo20a.html.

Related Material