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

arXiv: https://arxiv.org/abs/1404.2644 · HTML: https://mlsanity.com/paper/1404.2644/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2014.

## Built on by (most cited first, 7 of 7)

- [Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features](https://mlsanity.com/paper/2304.11737/) (2023)
- [How much pre-training is enough to discover a good subnetwork?](https://mlsanity.com/paper/2108.00259/) (2021)
- [Majority Vote for Distributed Differentially Private Sign Selection](https://mlsanity.com/paper/2209.04419/) (2022)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Convex optimization over a probability simplex](https://mlsanity.com/paper/2305.09046/) (2023)
- [Scalable High-Dimensional Multivariate Linear Regression for Feature-Distributed Data](https://mlsanity.com/paper/2307.03410/) (2023)
- [Generalization Analysis of Distributed Kernel-based Robust Gradient Descent Algorithms](https://mlsanity.com/paper/2609.11712/) (2026)

## Abstract (arXiv)

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 ε 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 ε-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.