Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms

By Yu-Xiang Wang, Veeranjaneyulu Sadhanala, Wei Dai, Willie Neiswanger, Suvrit Sra, Eric P. Xing. 2014

44 citations recorded by the source corpus.

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-Julien et al., 2013), but our analysis subsumes BCFW and reveals problemdependent 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jean-Baptiste Alayrac
2. Simon Lacoste-Julien
3. Jarrid Rector-Brooks
4. Barzan Mozafari
5. Jun-Kun Wang
6. Anton Osokin
7. Puneet Kumar Dokania
8. Jian Lou

In Computational Theory and Mathematics

1. Simon Lacoste-Julien
2. Jarrid Rector-Brooks
3. Yiu-ming Cheung
4. Anton Osokin
5. Jian Lou
6. Barzan Mozafari
7. Jun-Kun Wang
8. Peter Richtárik

In Computer Networks and Communications

1. Simon Lacoste-Julien
2. Jarrid Rector-Brooks
3. Yiu-ming Cheung
4. Jian Lou
5. Barzan Mozafari
6. Jun-Kun Wang

In Optimization & Training

1. Jean-Baptiste Alayrac
2. Simon Lacoste-Julien
3. Jarrid Rector-Brooks
4. Barzan Mozafari
5. Jun-Kun Wang
6. Anton Osokin
7. Puneet Kumar Dokania
8. Isabella Lukasewitz

Citations in the corpus

• Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, background): “Their FASOLE algorithm also contains a version of gap sampling in the form of variable shrinking: if a block gap becomes small enough, the block is not visited again, until all the counters are reset.”
• Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? (2018, unknown): “…coordinate descent (Liu et al., 2014; Avron et al., 2015; Liu & Wright, 2015; Tappenden et al., 2017; Fercoq & Richtárik, 2015), dual coordinate descent (Tran et al., 2015), block coordinate descent (Wang et al., 2016; Marecek et al., 2015; Wright, 2015), ADMM (Zhang & Kwok, 2014; Hong, 2017), etc.”
• Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data (2018, methodology): “It enjoys greater flexibility than existing analysis (Lacoste-julien et al. 2013; Wang et al. 2016) whose analysis is highly dependent on the specific samplings.”
• Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, background): “…structural SVM, computer vision, sparse PCA, metric learning, and many other settings (Jaggi, Sulovsk, and others 2010; Lacoste-Julien et al. 2013; Osokin et al. 2016; Wang et al. 2016; Chari et al. 2015; Harchaoui et al. 2012; Hazan and Kale 2012; Shalev-Shwartz, Gonen, and Shamir 2011).”
• The Frank-Wolfe Algorithm: A Short Introduction (2023, unknown): “This makes them very effective in the context of large-scale machine learning problems (see, e.g., Lacoste-Julien et al. [54], Jaggi [48], Négiar et al. [64], Dahik [26], Jing et al. [49]), image processing (see, e.g., Joulin et al. [50], Tang et al. [75]), quantum physics (see, e.g., Gilbert [41], ”