  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.
