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

Abstract : 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.
Type de document :
Communication dans un congrès
SIAM International Conference on Data Mining (SDM 2015), Apr 2015, Vancouver, Canada. 〈http://www.siam.org/meetings/sdm15/〉. 〈10.1137/1.9781611974010.54〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01430851
Contributeur : Aurélien Bellet <>
Soumis le : mardi 10 janvier 2017 - 12:43:30
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39
Document(s) archivé(s) le : mardi 11 avril 2017 - 14:37:01

Fichier

sdm15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Aurélien Bellet, Yingyu Liang, Alireza Bagheri Garakani, Maria-Florina Balcan, Fei Sha. A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning. SIAM International Conference on Data Mining (SDM 2015), Apr 2015, Vancouver, Canada. 〈http://www.siam.org/meetings/sdm15/〉. 〈10.1137/1.9781611974010.54〉. 〈hal-01430851〉

Partager

Métriques

Consultations de la notice

116

Téléchargements de fichiers

89