# Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2016.

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

- [On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network](https://mlsanity.com/paper/2206.15025/) (2022)
- [Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy](https://mlsanity.com/paper/2212.07534/) (2022)
- [LeanVec: Searching vectors faster by making them fit](https://mlsanity.com/paper/2312.16335/) (2023)
- [How much pre-training is enough to discover a good subnetwork?](https://mlsanity.com/paper/2108.00259/) (2021)
- [Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach](https://mlsanity.com/paper/2404.02511/) (2024)
- [One Gradient Frank-Wolfe for Decentralized Online Convex and Submodular Optimization](https://mlsanity.com/paper/2210.16790/) (2022)
- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [Online Decentralized Frank-Wolfe: From theoretical bound to applications in smart-building](https://mlsanity.com/paper/2208.00522/) (2022)
- [Federated Frank-Wolfe Algorithm](https://mlsanity.com/paper/2408.10090/) (2024)
- [Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA](https://mlsanity.com/paper/2602.03682/) (2026)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)

## Abstract (arXiv)

Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high dimensional constrained problems, as the projection step becomes computationally prohibitive to compute. To address this problem, this paper adopts a projection-free optimization approach, a.k.a.~the Frank-Wolfe (FW) or conditional gradient algorithm. We first develop a decentralized FW (DeFW) algorithm from the classical FW algorithm. The convergence of the proposed algorithm is studied by viewing the decentralized algorithm as an inexact FW algorithm. Using a diminishing step size rule and letting t be the iteration number, we show that the DeFW algorithm's convergence rate is cal O(1/t) for convex objectives; is cal O(1/t2) for strongly convex objectives with the optimal solution in the interior of the constraint set; and is cal O(1/√t) towards a stationary point for smooth but non-convex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. Furthermore, we demonstrate the advantages of the proposed DeFW algorithm on low-complexity robust matrix completion and communication efficient sparse learning. Numerical results on synthetic and real data are presented to support our findings.