A Distributed Frank-Wolfe Framework for Learning Low-Rank Matrices with the Trace Norm
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.
Code (1)
Similar Papers 제목 키워드 기반
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously…
An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion
Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. This i…
Low-Rank Matrix CompletionMatrix CompletionCommunication-Efficient Projection-Free Algorithm for Distributed Optimization
Distributed optimization has gained a surge of interest in recent years. In this paper we propose a distributed projection free algorithm named Distributed Conditional Gradient Sliding(DCGS). Compared to the state-of-the…
Distributed OptimizationMatrix CompletionBeyond Short Steps in Frank-Wolfe Algorithms
We introduce novel techniques to enhance Frank-Wolfe algorithms by leveraging function smoothness beyond traditional short steps. Our study focuses on Frank-Wolfe algorithms with step sizes that incorporate primal-dual g…
A Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron
We consider the problem of minimizing a smooth and convex function over the $n$-dimensional spectrahedron -- the set of real symmetric $n\times n$ positive semidefinite matrices with unit trace, which underlies numerous …