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.
Type de document :
Article dans une revue
IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, 2017, 62 (11), pp.5522 - 5537. 〈10.1109/TAC.2017.2685559〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01668247
Contributeur : Eric Moulines <>
Soumis le : mardi 19 décembre 2017 - 22:38:15
Dernière modification le : jeudi 10 mai 2018 - 02:05:57

Lien texte intégral

Identifiants

Citation

Hoi-To Wai, Jean Lafond, Anna Scaglione, Eric 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〉

Partager

Métriques

Consultations de la notice

253