A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm

Wenjie Zheng 1 Aurélien Bellet 2 Patrick Gallinari 1
1 MLIA - Machine Learning and Information Access
LIP6 - Laboratoire d'Informatique de Paris 6
2 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : We consider the problem of learning a high-dimensional but low-rank matrix from a large-scale dataset distributed over several machines, where low-rankness is enforced by a convex trace norm constraint. We propose DFW-Trace, a distributed Frank-Wolfe algorithm which leverages the low-rank structure of its updates to achieve efficiency in time, memory and communication usage. The step at the heart of DFW-Trace is solved approximately using a distributed version of the power method. We provide a theoretical analysis of the convergence of DFW-Trace, showing that we can ensure sublinear convergence in expectation to an optimal solution with few power iterations per epoch. We implement DFW-Trace in the Apache Spark distributed programming framework and validate the usefulness of our approach on synthetic and real data, including the ImageNet dataset with high-dimensional features extracted from a deep neural network.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01672066
Contributeur : Aurélien Bellet <>
Soumis le : samedi 23 décembre 2017 - 07:18:23
Dernière modification le : vendredi 30 novembre 2018 - 01:30:36
Document(s) archivé(s) le : samedi 24 mars 2018 - 12:32:01

Fichier

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

Identifiants

Citation

Wenjie Zheng, Aurélien Bellet, Patrick Gallinari. A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm. [Research Report] Inria Lille. 2017, pp.1-19. 〈hal-01672066〉

Partager

Métriques

Consultations de la notice

529

Téléchargements de fichiers

73