Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
arXiv:1409.6086
Abstract
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously, which helps attain speedups on multicore machines as well as in distributed environments. Moreover, instead of worst-case bounded delays, our methods only depend (mildly) on \emph{expected} delays, allowing them to be robust to stragglers and faulty worker threads. Our algorithms assume block-separable constraints, and subsume the recent Block-Coordinate Frank-Wolfe (BCFW) method~\citep{lacoste2013block}. Our analysis reveals problem-dependent quantities that govern the speedups of our methods over BCFW. We present experiments on structural SVM and Group Fused Lasso, obtaining significant speedups over competing state-of-the-art (and synchronous) methods.
References in corpus (4)
Cited by in corpus (13)
- Quantum Differentially Private Sparse Regression Learning
- Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
- A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
- First-Order Methods for Large-Scale Market Equilibrium Computation
- Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
- One Sample Stochastic Frank-Wolfe
- Revisiting Projection-free Online Learning: the Strongly Convex Case
- Communication-Efficient Projection-Free Algorithm for Distributed Optimization
- Bayesian posterior approximation via greedy particle optimization
- Distributed stochastic optimization with large delays
- Robust Structured Statistical Estimation via Conditional Gradient Type Methods
- Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
- Scalable Projection-Free Optimization