Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms

We study parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. In both cases, we perform computations asynchronously whenever possible. We assume block-separable constraints as in Block-Coordinate Frank-Wolfe (BCFW) method (Lacoste et. al. , 2013), but our analysis subsumes BCFW and reveals problem-dependent quantities that govern the speedups of our methods over BCFW. A notable feature of our algorithms is that they do not depend on worst-case bounded delays, but only (mildly) on **expected** delays, making them robust to stragglers and faulty worker threads. We present experiments on structural SVM and Group Fused Lasso, and observe significant speedups over competing state-of-the-art (and synchronous) methods.

Authors

• Yu-Xiang Wang 0003
• Veeranjaneyulu Sadhanala
• Wei Dai 0003
• Willie Neiswanger
• Suvrit Sra
• Eric P. Xing

Keywords

No keywords are indexed for this paper.