Skip to Main content Skip to Navigation
Journal articles

Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems

Abstract : 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 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 O(1/t) for convex objectives; is O(1/t2) for strongly convex objectives with the optimal solution in the interior of the constraint set; and is O(1/√t) toward a stationary point for smooth but nonconvex objectives. We then show that a consensus-based DeFW algorithm meets the above guarantees with two communication rounds per iteration. 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Eric Moulines Connect in order to contact the contributor
Submitted on : Tuesday, December 19, 2017 - 10:38:15 PM
Last modification on : Friday, April 30, 2021 - 10:02:15 AM

Links full text




Hoi-To Wai, Jean Lafond, Anna Scaglione, Éric Moulines. Decentralized Frank–Wolfe Algorithm for Convex and Nonconvex Problems. IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2017, 62 (11), pp.5522 - 5537. ⟨10.1109/TAC.2017.2685559⟩. ⟨hal-01668247⟩



Record views