A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning

By Aurélien Bellet, Yingyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, Fei Sha. 2014

48 citations recorded by the source corpus.

Learning sparse combinations is a frequent theme in machine learning. In this paper, we study its associated optimization problem in the distributed setting where the elements to be combined are not centrally located but spread over a network. We address the key challenges of balancing communication costs and optimization errors. To this end, we propose a distributed Frank-Wolfe (dFW) algorithm. We obtain theoretical guarantees on the optimization error $\epsilon$ and communication cost that do not depend on the total number of combining elements. We further show that the communication cost of dFW is optimal by deriving a lower-bound on the communication cost required to construct an $\epsilon$-approximate solution. We validate our theoretical analysis with empirical studies on synthetic and real-world data, which demonstrate that dFW outperforms both baselines and competing methods. We also study the performance of dFW when the conditions of our analysis are relaxed, and show that dFW is fairly robust.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

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. Willie Neiswanger
2. Eric P. Xing
3. Jian Lou
4. Wei Dai
5. Yiu-ming Cheung
6. Peng Liu
7. Di Niu
8. Yu-Xiang Wang

In Computational Mechanics

1. Wei Dai
2. Yiu-ming Cheung
3. Eric P. Xing
4. Jian Lou
5. Peng Liu
6. Yu-Xiang Wang
7. Jean Lafond
8. Eric Moulines

In Computer Networks and Communications

1. Willie Neiswanger
2. Wei Dai
3. Yiu-ming Cheung
4. Eric P. Xing
5. Jian Lou
6. Peng Liu
7. Di Niu
8. Yu-Xiang Wang

Citations in the corpus

• Learning Privately over Distributed Features: An ADMM Sharing Approach (2019, background): “A few recent studies [8, 9, 10, 11, 12, 13, 14] have revisited vertically partitioned features under the setting of distributed learning, which is motivated by the increase in feature dimensionality as well as the opportunity of cooperation between multiple parties that may hold different aspects of”
• Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data (2018, methodology): “Recall the global curvature Cf of (Jaggi 2013; Bellet et al. 2015) under elementary sampling, the product curvature C⊗f of (Lacoste-julien et al. 2013) under uniform serial sampling, and expected set curvature Cτf of (Wang et al. 2016) under τ -nice sampling as introduced in Subsection .”
• Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, methodology): “While preparing our manuscript, we discovered the preprint (Bellet et al., 2014) which also studies distributed Frank-Wolfe.”
• D-FW: Communication efficient distributed algorithms for high-dimensional sparse optimization (2016, methodology): “In fact, a communication-efficient distributed algorithm based on Frank-Wolfe algorithm has been studied in [19].”